Batching timestamps with a Merkle tree (Bayer, Haber and Stornetta 1993)

Linking every document into a chain costs one record per document. Bayer, Haber and Stornetta batched them: put a round’s documents in a Merkle tree and timestamp only the root. Each document keeps a short proof linking it to that root. This is exactly how a block commits to its transactions.

What to look for

One 32-byte root timestamps a thousand documents, and each proof grows only logarithmically. A block’s header commits to its transactions the same way.

The history behind this experiment: Breakthroughs in Authenticated Data Structures. See Exercises: ledgers and data structures for a worked solution to the exercise.

Timestamp a round of documents with one root

import matplotlib.pyplot as plt

import blockchainkit as bk

documents = [f"contract {i}".encode() for i in range(1000)]
tree = bk.structures.MerkleTree(documents)
stamp = bk.structures.BlockHeader(merkle_root=tree.root, height=0, timestamp=1993, difficulty=0)
proof = tree.proof(617)
assert bk.structures.verify_proof(documents[617], proof, stamp.merkle_root)
size = sum(32 for sibling in proof.siblings if sibling is not None)
print(f"1000 documents, one root; proof for contract 617: {size} bytes")

1000 documents, one root; proof for contract 617: 320 bytes

A block does the same for its transactions

alice = bk.crypto.public_key(7)
bob = bk.structures.address(bk.crypto.public_key(11))
payments = tuple(
    bk.structures.Transaction(alice, bob, 1, n).signed(7, signing_nonce=100 + n) for n in range(5)
)
block = bk.structures.Block(transactions=payments, difficulty=0)
assert block.merkle_root == bk.structures.MerkleTree(tx.to_bytes() for tx in payments).root

Records needed: one per document, or one per round

counts = [2**k for k in range(1, 15)]
proof_bytes = [32 * (n - 1).bit_length() for n in counts]
fig, ax = plt.subplots(figsize=(7, 4))
ax.loglog(counts, counts, "--", label="linked records (one per document)")
ax.loglog(counts, [1] * len(counts), "-", label="batched records (one per round)")
ax.loglog(counts, proof_bytes, "o-", label="proof bytes per document")
ax.set(xlabel="documents per round", title="Batching: one timestamp, logarithmic proofs")
ax.legend()
fig.tight_layout()

Exercise

OpenTimestamps batches documents worldwide into one Bitcoin transaction per round. Estimate the proof length for a round of a million documents.