merkletree gives Go developers three tree constructions, and warns about the default

What a Merkle tree buys you, and how this one is built

The project describes itself as an implementation of a Merkle Tree written in Go, where a Merkle Tree is a hash tree that provides an efficient way to verify the contents of a set of data are present and untampered with.

The mechanism is described in the readme in a way that is worth reading, because it explains both the value and the cost. At its core a Merkle tree is a list of items representing the data that should be verified. Each item is inserted into a leaf node and a tree of hashes is constructed bottom up using a hash of the nodes left and right children's hashes. The root node is therefore effectively a hash of all the other nodes in the tree, and the tree can be reproduced and thus verified by the hash of the root node.

The efficiency claim is that verifying any single content entry in the tree requires only n log2(n) steps in the worst case. That is the reason to use a Merkle tree rather than a hash of the whole list: proving one entry is present does not require re-hashing everything above it.

The module is github.com/cbergoon/merkletree and it requires go 1.21, with no dependencies at all in the go.mod beyond the standard library. The repository is a flat package with merkle_tree.go, proof.go, serialize.go and doc.go, plus a long list of test files that indicate what is actually verified: golden tests, property tests, hardening tests, error path tests, sort order tests, parallel tests, leaf index tests and a fuzz test for serialization. There is also an oracle directory, which suggests cross-checking against an independent implementation rather than only against itself.

Three constructions, and the roots are not interchangeable

The tree can be built three ways, and the readme is emphatic that they produce different roots and are not interchangeable, so you pick one when the tree is created.

The default is Bitcoin-style, built with NewTree or NewTreeWithHashStrategy. It pairs siblings in order and duplicates the last node on an odd count.

Sorted siblings, built with NewTreeWithHashStrategySorted or WithSortedSiblings, orders each pair before hashing, matching the OpenZeppelin MerkleProof behaviour.

The third is RFC 6962, built with WithRFC6962, which uses prefixed leaf and interior hashes and splits instead of padding.

That the default follows Bitcoin is explained by the goal: so that roots line up with Bitcoin-style trees, and with them two well known properties come along. Which is the subject of the next section, and it is the most valuable part of the readme.

The RFC 6962 construction is the one to look at if you need a property the default cannot give. It is built as RFC 6962 section 2.1 specifies:

tree, err := merkletree.NewTreeWithOptions(list, merkletree.WithRFC6962())

Leaf hashes are computed as H(0x00 concatenated with digest) and interior hashes as H(0x01 concatenated with left concatenated with right), so a forged leaf would need a genuine collision between two differently prefixed inputs rather than a rearrangement. Odd node counts are split at the largest power of two below their length instead of being padded, so every distinct leaf sequence gets a distinct root and [A, B, C] no longer collides with [A, B, C, C].

The default construction has two documented weaknesses

This is the section that makes the readme worth reading, and it is unusually direct about the problems with the default.

The first is CVE-2012-2459. A level holding an odd number of nodes duplicates its last node so it can be paired, which means a tree built from an odd number of leaves has the same root as a tree that spells the duplicate out:

[A, B, C]  and  [A, B, C, C]  ->  same root
[A]        and  [A, A]        ->  same root

The second is that there is no separation between leaf and interior hashes, because both are computed the same way, so an interior digest can be handed back as a leaf. A two leaf tree whose leaves are the two subtree hashes of a four leaf tree reproduces the original root exactly, and the forged tree verifies against itself.

Sorted mode shares both of those problems and additionally discards leaf order. The readme spells it out: [A B C D], [B A C D] and [D C B A] all produce the same root, because each pair is ordered before it is hashed. Only regrouping which leaves are paired changes the root. The advice is to check tree.Sorted() if you depend on the root committing to order.

So there is a real decision here rather than a default you inherit. Bitcoin-style for compatibility, sorted for OpenZeppelin compatibility, RFC 6962 for the cryptographic properties.

One caveat that will bite a Certificate Transparency user

The RFC 6962 mode comes with a caveat that the readme states plainly, and it is the kind of detail that would cost an afternoon to find otherwise.

RFC 6962 hashes raw leaf data, whereas this tree hashes whatever CalculateHash returns. Roots match a Certificate Transparency log only if your CalculateHash returns the leaf bytes themselves rather than a digest of them.

So if you want a root that a CT verifier would accept, your hash function has to return the raw bytes, not a hash of them. If it returns a digest, you get a tree that follows the RFC's structure but produces roots that no CT log would have signed.

There is also a combination rule. WithRFC6962() cannot be combined with WithSortedSiblings(), because RFC 6962 specifies its own sibling ordering.

The tree records the construction it used when it is serialized, which is what makes decoding self-checking later. So a tree built one way, serialized, and then decoded does not silently become a tree of a different kind.

Parallel construction, with a measured result and a warning

WithParallelism(n) builds the tree across up to n goroutines, or GOMAXPROCS of them when n is less than one, and it is off by default.

tree, err := merkletree.NewTreeWithOptions(list, merkletree.WithParallelism(0))

The warning is about your code, not the library. Content.CalculateHash is called concurrently when this is set, so your implementation has to be safe for that. Nothing else in the package calls it concurrently, and the tree has no way to check whether yours is safe.

The measured table is unusually useful, because it shows where the option stops being a win. Parallel CalculateHash costs measured on an M5 Max: for short strings with 256 leaves, serial takes 26.5 microseconds and parallel 43.7, so 0.61 times, which is slower. At 4,096 leaves it is 1.43 times, at 65,536 leaves 2.99 times. For a 4KB blob at 4,096 leaves the speedup is 7.21 times.

The pattern is clear enough to act on. Parallelism costs a fixed overhead, so it loses on small trees and on cheap hashes, and wins increasingly as the hash gets more expensive relative to that overhead. The option covers each construction type including WithRFC6962, and an RFC build of 65,536 short leaves drops from 9.98ms serial to 2.01ms in parallel.

One smaller detail: parallelism is not recorded when a tree is serialized, since it has no bearing on the root.

Proof serving, and the allocation argument

Proof serving is where the library is most opinionated, and the reasoning is about garbage collection rather than about hashing.

GetMerklePath locates content by scanning every leaf. Building with WithLeafIndex turns that into one hash and a map probe, or you can address leaves by position with GetMerklePathByIndex. But when proofs are served at rate, the two slices each proof returns become the bottleneck and the garbage collector turns into the shared resource every goroutine queues on.

The Append forms generate the same proofs into buffers you own, so a server that reuses them allocates nothing per proof:

var path [][]byte
var index []int64
for i := range list {
  path, index, err = t.AppendMerklePathByIndex(path[:0], index[:0], i)
  // path holds the sibling hashes, index which side each sits on
}

Two things to note about that loop. The hashes appended are the tree's own rather than copies, so you treat them as read-only and copy any proof that must outlive the next reuse of its buffer. And the buffers are reset with path[:0] and index[:0], so the slices are reused rather than reallocated.

The numbers are what justify the design. At 65,536 leaves a proof appends in about 17 nanoseconds against about 76 nanoseconds for returning fresh slices. Under 18 goroutines serving from one shared tree the append form runs at 2.9 nanoseconds per proof, 28 times the slice-returning form, because with no allocation there is nothing shared left to queue on.

Serialization that checks itself on the way back in

A tree can be written out and read back, and what gets written is the content the tree is rebuilt from: the ordered leaf content, the name of the hash strategy, the sibling sort flag, and the Merkle root.

The recorded root makes decoding self-checking, so a payload that has been altered, or that is decoded with the wrong hash strategy, fails as expected. That is the property that matters: the format cannot be silently misread.

Registering your content type lets the standard codecs work directly:

merkletree.RegisterContent(TestContent{}) // needs MarshalBinary/UnmarshalBinary

err := gob.NewEncoder(&buf).Encode(tree)

var decoded merkletree.MerkleTree
err = gob.NewDecoder(&buf).Decode(&decoded)

And the other encodings are available too. MarshalBinary, UnmarshalBinary, MarshalJSON and UnmarshalJSON are all provided, so anything built on encoding.BinaryMarshaler or json.Marshaler works as well.

The repository also has a benchmarks directory, a scripts directory, an oracle directory and an example_serialize_test.go, and the documentation lives on pkg.go.dev rather than in the repository, with the readme pointing there. The version badge in the readme says 0.5.0, the repository publishes no GitHub releases, and the last push was on 2026-08-14.

Editorial conclusion

Adopt merkletree if you are implementing a Merkle tree in Go and want the construction choice made explicit rather than inherited by accident, since the readme names the weaknesses of the Bitcoin-style default and offers RFC 6962 as the fix. Do not adopt it without reading the construction section, because the default carries the CVE-2012-2459 duplication collision and the leaf and interior hash ambiguity. Before you pick a mode, check three things: whether your verifier expects a Bitcoin-style root, since the roots differ between modes and are not interchangeable, whether your CalculateHash returns raw leaf bytes rather than a digest if you want RFC 6962 roots to match a Certificate Transparency log, and whether your hash implementation is safe for concurrent calls if you enable WithParallelism.

Frequently asked questions

Official sources

1. cbergoon/merkletree on GitHub
2. Issues
3. License: MIT
4. README