bobg/merkle: streaming Merkle roots and inclusion proofs in Go

What it is

bobg/merkle is a small Go package (one source file of about 250 lines) for two related jobs: computing the Merkle root hash of a sequence of byte strings, and producing a compact proof that one particular string belongs in such a tree. It is published as module github.com/bobg/merkle/v2, requires Go 1.20 or later, has a test dependency on golang.org/x/crypto (with an indirect requirement for golang.org/x/sys), and carries the MIT license.

The distinguishing design choice is streaming: you feed strings one at a time with Add, and the package keeps incremental state that grows logarithmically in the number of inputs — O(log N) — rather than buffering everything. That makes it practical for sequences of unbounded length where holding all input in memory would be wasteful or impossible.

Two layers, two entry points

The public surface is split into a convenience layer and a lower-level layer:

• Tree works on raw byte strings. You hand it a hash.Hash, add strings with Add, and read the result with Root().
• HTree works directly on leaf hashes — the output of calling LeafHash on each string. A Tree is really just an HTree that converts its input to leaf hashes first.

The split matters because it lets callers who already hold hashes (say, from a prior pass) skip re-hashing raw data. The source code makes the relationship explicit: "a Tree works by converting its input from a sequence of strings to the corresponding sequence of leaf hashes and feeding those to an HTree."

Computing a root is straightforward:

tree := merkle.NewTree(sha256.New())
for str := range ch {
    tree.Add(str)
}
fmt.Printf("merkle root hash is %x\n", tree.Root())

Producing and verifying proofs

The second feature is inclusion proofs. NewProofTree takes the reference string you will later want to prove membership for, alongside the hasher:

tree := merkle.NewProofTree(sha256.New(), ref)
for str := range ch {
    tree.Add(str)
}
proof := tree.Proof()

The returned Proof is a compact object: an ordered list of sibling hashes (Steps []ProofStep, each carrying the hash and whether it sat on the left). A verifier who holds only the root hash can confirm membership without rebuilding the whole tree:

if bytes.Equal(rootHash, proof.Hash(sha256.New(), ref)) {
    fmt.Println("Verified!")
}

The needsLeafHashing flag distinguishes proofs built from a Tree (where the reference string must be leaf-hashed first) from those built directly on an HTree (where it is already a hash). The tests exercise both paths, including negative cases where a slightly different chunk fails to verify.

How the incremental state works

The core of the streaming behavior lives in HTree.Add. Rather than building and storing every node, it keeps one slot per tree height. For each incoming leaf hash it walks up from height zero: if that level is vacant it fills it; if full, it combines the two hashes into an interior node, vacates the level, and carries the combined hash upward until a free slot appears.

That is why memory stays logarithmic — at any moment there are only as many stored hashes as there are levels in the tree. finish() then folds whatever partial state remains up to a single root when you call Root() or Proof(). The code notes it is an error to call Add after either of those.

Two details show attention to correctness:

• Domain separators. Leaves and interior nodes are hashed with different leading bytes (0x00 for leaves, 0x01 for interiors), a defense against second-preimage attacks documented in the code with a link to the Wikipedia article.
• Proof capture during combination. When building an inclusion proof, interiorHash checks whether either child matches the reference hash being tracked and, if so, records the sibling as a proof step while advancing the reference up the tree.

Tests against known vectors

The test suite pins behavior to fixed expected hashes. TestMerkleRoot uses SHA3-256 "for historical reasons (to wit, verifying that the implementation agrees with the one in github.com/chain/txvm)" and asserts exact hex roots for inputs from empty up to seven elements. TestText, TestTreeProof and TestHTreeProof run over a real text file (testdata/udhr.txt) chunked into 256-byte pieces. TestText checks the root hash; TestTreeProof and TestHTreeProof also check that proofs verify, or fail to verify when given the wrong reference chunk.

There is also a benchmark, BenchmarkTextMerkleTree, for measuring throughput on the same chunked input. The README carries badges for Go Reference docs, Go Report Card, CI tests, coverage via Coveralls, and an "Awesome Go" mention.

Who it is for

This is a focused library for developers who need Merkle roots or membership proofs over data that arrives incrementally. It does not implement a full tree structure you can traverse; there are no methods to walk nodes or fetch arbitrary leaves after the fact. What it offers is exactly what its title promises: efficient calculation of roots and proofs, with unbounded streaming input as the headline feature.

The API is deliberately small — NewTree/NewHTree, the proof constructors NewProofTree/NewProofHTree, then Add, Root, Proof, Hash, and LeafHash. There is no HTree.Hash: Hash lives only on Proof, while both Tree and HTree expose Add, Root and Proof. That restraint keeps the surface easy to audit, which matters for a piece of code whose whole job is producing hashes people will trust. The last release tag is v2.1.2.