merkletree

package module
v0.5.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 14, 2026 License: MIT Imports: 18 Imported by: 103

README

Merkle Tree in Golang

Build Docs Version

An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the contents of a set data are present and untampered with.

At its core, a Merkle Tree is a list of items representing the data that should be verified. Each of these items 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. This means that the root node will effictively be a hash of all other nodes (hashes) in the tree. This property allows the tree to be reproduced and thus verified by on the hash of the root node of the tree. The benefit of the tree structure is verifying any single content entry in the tree will require only nlog2(n) steps in the worst case.

Documentation

See the docs here.

Constructions

The tree can be built three ways. All of them are supported; they produce different roots and are not interchangeable, so pick one when the tree is created.

Construction Built with Notes
Bitcoin-style (default) NewTree, NewTreeWithHashStrategy Pairs siblings in order, duplicates the last node on an odd count
Sorted siblings NewTreeWithHashStrategySorted, WithSortedSiblings() Orders each pair before hashing, matching OpenZeppelin MerkleProof
RFC 6962 WithRFC6962() Prefixed leaf and interior hashes, splits instead of padding

The default follows Bitcoin deliberately, so the roots line up with Bitcoin-style trees. That construction carries two well-known properties:

Duplicated odd nodes. 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 — this is CVE-2012-2459:

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

No separation between leaf and interior hashes. 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, and additionally discards leaf order: [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. Check tree.Sorted() if you depend on the root committing to order.

RFC 6962

WithRFC6962() builds the tree specified by RFC 6962 section 2.1, which closes both of the above:

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

Leaf hashes are computed as H(0x00 ‖ digest) and interior hashes as H(0x01 ‖ left ‖ 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].

Two things to know. 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. The structural guarantees hold either way. And a single-leaf tree is its own root, so its audit path is legitimately empty.

WithRFC6962() cannot be combined with WithSortedSiblings(); RFC 6962 specifies its own sibling ordering, and asking for both returns an error.

Parallel construction

WithParallelism(n) builds the tree across up to n goroutines, or GOMAXPROCS of them when n < 1. It is off by default.

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

Content.CalculateHash is called concurrently when this is set, and your implementation must be safe for that. Nothing else in the package calls it concurrently and the tree cannot check whether yours is safe, so this requirement is the entire cost of the option and the reason it is not the default.

The root is unaffected — every hash lands in a slot fixed by its position, so a tree built in parallel is byte for byte the tree built serially.

Whether it pays depends almost entirely on what CalculateHash costs. Measured on an M5 Max, best of 3:

Content Leaves Serial Parallel
short string 256 26.5µs 43.7µs 0.61× — slower
short string 4,096 476µs 333µs 1.43×
short string 65,536 6.40ms 2.14ms 2.99×
4KB blob 4,096 5.21ms 723µs 7.21×

Content hashing is always spread across the goroutine budget, since its cost belongs to you and cannot be guessed here — which is why the option wins big on expensive leaves at any size, and can lose on a small tree of cheap ones. Interior hashing is our own work and known to be small, so it stays serial until the tree is large enough to be worth splitting. Measure before adopting it for small trees.

The option covers every construction, including WithRFC6962: the unbalanced interior an RFC tree builds forks across goroutines the same way, so an RFC build of 65,536 short leaves drops from 9.98ms serial to 2.01ms in parallel.

Parallelism is not recorded when a tree is serialized, since it has no bearing on the root; a tree read back rebuilds serially unless built again with the option.

Serving proofs

GetMerklePath locates content by scanning every leaf; build with WithLeafIndex to make that one hash and a map probe, or address leaves by position with GetMerklePathByIndex. When proofs are served at rate, the two slices each proof returns become the bottleneck — 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
}

The appended hashes are the tree's own, not copies: treat them as read-only, and copy any proof that must outlive the next reuse of its buffer.

The difference is not subtle. At 65,536 leaves a proof appends in ~17ns against ~76ns returning fresh slices, and under 18 goroutines serving from one shared tree the append form runs at 2.9ns per proof — 28× the slice-returning form, because with no allocation there is nothing shared left to queue on. The comparison tables below carry the cross-library context.

Serialization

A tree can be written out and read back. What gets written is not the node graph but 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. Everything else is derived, and the recorded root makes decoding self-checking — a payload that has been altered, or that is decoded with the wrong hash strategy, fails rather than producing a tree that quietly verifies against nothing.

Register your content type and 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)

MarshalBinary, UnmarshalBinary, MarshalJSON, and UnmarshalJSON are all available, so anything built on encoding.BinaryMarshaler or json.Marshaler works too.

To avoid the package-level registry entirely — in a library, or for content that already has an encoding of its own — supply the content codec directly:

data, err := tree.MarshalWith(func(c merkletree.Content) ([]byte, error) {
  return []byte(c.(TestContent).x), nil
})

decoded, err := merkletree.UnmarshalWith(data, func(b []byte) (merkletree.Content, error) {
  return TestContent{x: string(b)}, nil
})

Hash strategies are recorded by name, since a function cannot be serialized. Everything in the standard library is registered for you; anything else is one call:

merkletree.RegisterHashStrategy("keccak256", sha3.NewLegacyKeccak256)
tree, err := merkletree.NewTreeWithHashStrategy(list, sha3.NewLegacyKeccak256)

Note that a tree with reference cycles cannot be handed to a reflection-based codec directly — Node points back at its Tree and its Parent. Before these marshalers existed, gob.Encode(tree) did not return an error, it crashed the process with a stack overflow. The marshalers above are the supported path.

Comparison

Measured against the other Merkle tree libraries in the Go ecosystem — txaty/go-merkletree, wealdtech/go-merkletree, onrik/gomerkle, xsleonard/go-merkle and jvsteiner/merkle — with SHA-256 and the same leaf data throughout. The benchmarks, the methodology and the caveats are in benchmarks/ANALYSIS.md; the numbers below are from an Apple M5 Max on Go 1.26, so treat the ratios as the durable part.

txaty/go-merkletree gets its own column because it is the closest competitor — the only other library here with parallel construction, and the one whose published comparisons prompted this exercise. Where it is also the best of the field, the two columns agree.

merkletree txaty best of the rest rank
Construction, serial (65,536 leaves) 7.67 ms 9.67 ms onrik 7.61 ms 2 / 6
Construction, parallel (65,536 leaves) 3.08 ms 6.47 ms txaty 6.47 ms 1 / 2
Parallel speedup, 16 KiB leaves 12.8× 11.9× txaty 11.9× 1 / 2
Allocations building 65,536 leaves 131,140 328,230 onrik 131,090 2 / 6
Memory building 65,536 leaves 18.4 MB 24.8 MB wealdtech 11.5 MB 4 / 6
Single proof (65,536 leaves) 16.7 ns 128 ns txaty 128 ns 1 / 6
Full proof set (4,096 leaves) 25.4 ns/proof 158 ns/proof txaty 158 ns/proof 1 / 6
Verify a proof (65,536 leaves) 934 ns 1,212 ns onrik 1,108 ns 1 / 4
Concurrent proofs, 18 goroutines 2.9 ns/op 165 ns/op jvsteiner 153 ns/op 1 / 6
Concurrent scaling, 1 → 18 goroutines 16.4× 1.14× wealdtech 13.1× 1 / 6
Proof size on the wire, depth 16 640 B 516 B txaty 516 B 2 / 2

The proof rows are AppendMerklePathByIndex serving into reused buffers, which allocates nothing per proof; the slice-returning GetMerklePathByIndex runs at 76 ns and the WithLeafIndex lookup at 135 ns, still ahead of or level with everything else. Without any of the three, locating content is a scan and a full proof set is quadratic. Serial construction is a near-tie because every implementation is waiting on SHA-256 — at 16 KiB leaves all six land within 3% of each other, and parallelism is the only thing that still separates them.

merkletree txaty wealdtech onrik xsleonard jvsteiner
Proof generation ✅ ✅ ✅ ✅ ❌ ✅
Proof by leaf position 1 ✅ ✅ ❌ ✅ ❌ ✅
Allocation-free proofs 2 ✅ ❌ ❌ ❌ ❌ ❌
Verify without the tree 3 ✅ ✅ ✅ ❌ ❌ ✅
Parallel construction ✅ ✅ ❌ ❌ ❌ ❌
Pluggable hash ✅ ✅ ✅ ✅ ✅ ❌
Sorted siblings (OpenZeppelin) ✅ ✅ ❌ ❌ ✅ ❌
RFC 6962 ✅ ❌ ❌ ❌ ❌ ❌
Serialization ✅ ❌ ❌ ❌ ❌ ❌
Runtime dependencies none x/sync x/crypto none none protobuf
Odd leaf count duplicate 4 duplicate pad to 2ⁿ promote promote 5 promote

1 Addressing a leaf by position rather than by value, which avoids hashing the query. txaty offers this only through the precomputed Proofs slice in ModeProofGen. It matters more than it looks: at 16 KiB leaves, by position is 95× faster than by value. 2 AppendMerklePath and AppendMerklePathByIndex write into slices the caller supplies and keeps, so a proof server reusing its buffers generates proofs without allocating at all. No other library here exposes the proof buffers; every one of them returns freshly allocated structures. It is what makes the concurrency row possible — a proof that allocates nothing shares nothing, so it scales with cores instead of contending on the garbage collector. 3 A package-level verify taking a proof, a root and the data. onrik's is a method, so it needs a Tree value it does not otherwise use. 4 Or split, under WithRFC6962. 5 Or duplicate, with DoubleOddNodes.

That last row decides interoperability, not speed. These libraries agree on the root for any power-of-two leaf count and split into three groups otherwise, so a proof from one group will not verify against a root from another. merkletree's default agrees with txaty and with xsleonard's DoubleOddNodes; its WithRFC6962 mode is checked against the Certificate Transparency reference vectors in oracle/.

Install

go get github.com/cbergoon/merkletree

Example Usage

Below is an example that makes use of the entire API - its quite small.

package main

import (
  "crypto/sha256"
  "errors"
  "log"

  "github.com/cbergoon/merkletree"
)

//TestContent implements the Content interface provided by merkletree and represents the content stored in the tree.
type TestContent struct {
  x string
}

//CalculateHash hashes the values of a TestContent
func (t TestContent) CalculateHash() ([]byte, error) {
  h := sha256.New()
  if _, err := h.Write([]byte(t.x)); err != nil {
    return nil, err
  }

  return h.Sum(nil), nil
}

//Equals tests for equality of two Contents
func (t TestContent) Equals(other merkletree.Content) (bool, error) {
  otherTC, ok := other.(TestContent)
  if !ok {
    return false, errors.New("value is not of type TestContent")
  }
  return t.x == otherTC.x, nil
}

func main() {
  //Build list of Content to build tree
  var list []merkletree.Content
  list = append(list, TestContent{x: "Hello"})
  list = append(list, TestContent{x: "Hi"})
  list = append(list, TestContent{x: "Hey"})
  list = append(list, TestContent{x: "Hola"})

  //Create a new Merkle Tree from the list of Content
  t, err := merkletree.NewTree(list)
  if err != nil {
    log.Fatal(err)
  }

  //Get the Merkle Root of the tree
  mr := t.MerkleRoot()
  log.Println(mr)

  //Verify the entire tree (hashes for each node) is valid
  vt, err := t.VerifyTree()
  if err != nil {
    log.Fatal(err)
  }
  log.Println("Verify Tree: ", vt)

  //Verify a specific content in in the tree
  vc, err := t.VerifyContent(list[0])
  if err != nil {
    log.Fatal(err)
  }

  log.Println("Verify Content: ", vc)

  //String representation
  log.Println(t)
}

Sample

merkletree

Testing

go test -race ./...       # unit, property, golden, and regression tests
scripts/fuzz.sh           # every fuzz target, 30s each
scripts/bench.sh          # benchmarks, 6 runs each

The suite checks roots against a reference implementation written directly from each construction's definition, and pins golden roots and golden serialized payloads that were produced outside this repository. A change to the hashing or the wire format has to be made in several independent places before it can pass unnoticed; regenerating a golden payload to make a test pass is a compatibility break, not a fix.

Fuzzing

A normal test run only replays each target's seed corpus. scripts/fuzz.sh does the actual fuzzing, one target at a time, discovering targets from the source so a newly added FuzzXxx is picked up automatically:

scripts/fuzz.sh                       # every target, 30s each
scripts/fuzz.sh FuzzUnmarshalBinary   # just one
FUZZTIME=5m scripts/fuzz.sh           # longer budget per target
Target What it drives
FuzzTreeInvariants Tree construction, verification, and proof replay across every construction
FuzzUnmarshalBinary The binary decoder: no faults, decoded trees verify, payloads are canonical
FuzzUnmarshalJSON The JSON decoder
FuzzPayloadCorruption That an altered payload can never decode to a different Merkle root

CI fuzzes on every pull request for 60s per target, and on every merge to master for 180s per target. Both share a corpus cached between runs, so the search accumulates across builds rather than restarting each time. A failing input is written to testdata/fuzz/<Target>/ and uploaded as a build artifact; committing that file turns the finding into a permanent regression test.

Benchmarks

scripts/bench.sh covers construction, verification, proof generation, rebuilds, and all three codecs, across each construction and a range of leaf counts. Timings are noisy, so it runs each benchmark six times by default and can hand the results to benchstat:

scripts/bench.sh                          # everything
scripts/bench.sh Verify                   # only benchmarks matching /Verify/
scripts/bench.sh -o before.txt            # save a baseline
scripts/bench.sh -o after.txt -b before.txt   # ...and compare against it
scripts/bench.sh -s                       # smoke: one iteration, just checks they run

License

This project is licensed under the MIT License.

Documentation

Overview

Package merkletree implements a Merkle Tree capable of storing arbitrary content.

A Merkle Tree is a hash tree that provides an efficient way to verify the contents of a set data are present and untampered with. At its core, a Merkle Tree is a list of items representing the data that should be verified. Each of these items 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. This means that the root node will effictively be a hash of all other nodes (hashes) in the tree. This property allows the tree to be reproduced and thus verified by on the hash of the root node of the tree. The benefit of the tree structure is verifying any single content entry in the tree will require only nlog2(n) steps in the worst case.

Creating a new merkletree requires that the type that the tree will be constructed from implements the Content interface. 

type Content interface {
	CalculateHash() ([]byte, error)
	Equals(other Content) (bool, error)
}

A slice of the Content items should be created and then passed to the NewTree method. 

t, err := merkletree.NewTree(list)

t represents the Merkle Tree and can be verified and manipulated with the API methods described below.

Constructions

By default the tree is built the way Bitcoin builds one: sibling hashes are concatenated in the order given, and a level holding an odd number of nodes duplicates its last node so it can be paired. NewTreeWithHashStrategySorted additionally orders each pair of siblings before hashing, matching the OpenZeppelin MerkleProof convention.

Both of those constructions inherit two well known properties. The last node duplication means [A B C] and [A B C C] hash to the same root, which is CVE-2012-2459. And because leaf and interior hashes are computed the same way, an interior digest can be presented as a leaf: a two leaf tree whose leaves are the two subtree hashes of a four leaf tree reproduces the original root, and verifies.

NewTreeWithOptions with WithRFC6962 builds the tree specified by RFC 6962 section 2.1 instead, which closes both. Leaf and interior hashes carry distinct one byte prefixes, and node lists are split at the largest power of two below their length rather than padded, so every distinct leaf sequence has a distinct root. 

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

The constructions produce different roots and are not interchangeable, so pick one when the tree is created. See WithRFC6962 for the details, including how it relates to Certificate Transparency.

Parallel construction

WithParallelism builds a tree across several goroutines. It is off by default, because it calls Content.CalculateHash concurrently and only the caller knows whether their implementation is safe for that. 

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

The root is unaffected: results are written to slots fixed by position, so a tree built in parallel is byte for byte the tree built serially. What it is worth depends on what CalculateHash costs, and is large when content is expensive to hash and negative on a small tree of cheap content. See WithParallelism.

Proof lookup

GetMerklePath and VerifyContent locate their content by scanning every leaf, which makes a single proof cost O(n) in the leaf count even though the walk it performs afterwards is only O(log n), and a full set of proofs O(n²). Two options avoid the scan.

WithLeafIndex records a lookup table from leaf hash to leaf position at construction, so a lookup becomes one hash and one map probe whatever the leaf count: 

t, err := merkletree.NewTreeWithOptions(list, merkletree.WithLeafIndex())

It costs memory proportional to the leaf count and changes how content is located, from Content.Equals to a comparison of hashes. The Content interface already requires the two to agree, so any implementation honoring that contract gets the same leaf either way. See WithLeafIndex.

GetMerklePathByIndex takes the position in Leafs directly, needs no option and no extra memory, and is the better choice when the caller already tracks which item is which.

AppendMerklePath and AppendMerklePathByIndex produce the same proofs into caller supplied slices, so a proof server reusing its buffers generates proofs without allocating at all: 

path, index, err = t.AppendMerklePathByIndex(path[:0], index[:0], i)

Verifying a proof without the tree

VerifyProof checks an audit path against a root and needs no tree, which is the operation a verifier performs when it holds a root from a source it trusts and a proof from one it does not: 

ok, err := merkletree.VerifyProof(content, path, index, root, merkletree.WithRFC6962())

The options must describe the construction the proof was produced under. A verifier that has no Content implementation can use VerifyProofWithDigest instead, and one that does hold the tree can call the MerkleTree.VerifyProof method and skip restating the options.

This is a different question from MerkleTree.VerifyContent, which walks a tree it already has and recomputes every hash on the path from its own stored nodes. VerifyContent is the stronger check where the tree is available; VerifyProof is the only one available where it is not. See VerifyProof for what a verified proof does and does not establish, and why WithRFC6962 matters more for proofs from untrusted sources.

Serialization

A tree holds reference cycles - a Node points back at its Tree and at its Parent - so it cannot be handed to a reflection-based codec directly. Use the marshalers instead, which write the content the tree is rebuilt from rather than the node graph: the ordered leaf content, the name of the hash strategy, the construction the tree was built with, and the Merkle root. The recorded root is checked against the rebuilt tree on decode, so a payload that has been tampered with, truncated, or decoded with the wrong hash strategy is rejected.

Register the content type and encoding/gob, encoding/json, and anything else built on encoding.BinaryMarshaler or json.Marshaler will work: 

merkletree.RegisterContent(MyContent{})
err := gob.NewEncoder(&buf).Encode(t)

Content types registered this way must implement encoding.BinaryMarshaler, and a pointer to them must implement encoding.BinaryUnmarshaler.

To serialize without touching a package-level registry, supply the content codec directly with MarshalWith and UnmarshalWith.

Hash strategies are recorded by name, because a function value cannot be serialized. The standard library strategies are registered automatically; register anything else, such as keccak256 or blake2b, with RegisterHashStrategy before marshaling a tree that uses it.

Example (Serialization)

Example_serialization stores a tree with encoding/gob and reads it back. Registering the content type is what lets the decoder rebuild concrete Record values from an interface field. 

package main

import (
	"bytes"
	"crypto/sha256"
	"encoding/gob"
	"fmt"

	"github.com/cbergoon/merkletree"
)

// Record is the content stored in the trees below. Alongside the Content interface it
// implements encoding.BinaryMarshaler and encoding.BinaryUnmarshaler, which is what
// makes it serializable through the package registry.
type Record struct {
	Name string
}

func (r Record) CalculateHash() ([]byte, error) {
	h := sha256.New()
	if _, err := h.Write([]byte(r.Name)); err != nil {
		return nil, err
	}
	return h.Sum(nil), nil
}

func (r Record) Equals(other merkletree.Content) (bool, error) {
	o, ok := other.(Record)
	if !ok {
		return false, nil
	}
	return r.Name == o.Name, nil
}

func (r Record) MarshalBinary() ([]byte, error) { return []byte(r.Name), nil }

func (r *Record) UnmarshalBinary(data []byte) error {
	r.Name = string(data)
	return nil
}

func main() {
	merkletree.RegisterContent(Record{})

	list := []merkletree.Content{Record{Name: "Alice"}, Record{Name: "Bob"}, Record{Name: "Carol"}}
	tree, err := merkletree.NewTree(list)
	if err != nil {
		fmt.Println(err)
		return
	}

	var buf bytes.Buffer
	if err := gob.NewEncoder(&buf).Encode(tree); err != nil {
		fmt.Println(err)
		return
	}

	var decoded merkletree.MerkleTree
	if err := gob.NewDecoder(&buf).Decode(&decoded); err != nil {
		fmt.Println(err)
		return
	}

	fmt.Println("same root:", bytes.Equal(tree.MerkleRoot(), decoded.MerkleRoot()))

	found, err := decoded.VerifyContent(Record{Name: "Bob"})
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Println("contains Bob:", found)

}

Output:
same root: true
contains Bob: true

Index

Examples

Constants

This section is empty.

Variables

View Source 
var (
	// ErrNoContent is returned when a tree is built from an empty list of content.
	ErrNoContent = errors.New("error: cannot construct tree with no content")

	// ErrNilContent is returned when a list of content holds a nil entry.
	ErrNilContent = errors.New("error: cannot construct tree with nil content")

	// ErrContentNotFound is returned by GetMerklePath when the requested content is
	// not held by any leaf of the tree. Test for it with errors.Is.
	ErrContentNotFound = errors.New("error: content not found in tree")

	// ErrMalformedTree is returned by the verification methods when the tree they
	// are asked to walk is not one a constructor could have produced: a zero value
	// MerkleTree, or a node graph whose interior nodes are missing a child or a tree
	// back-pointer. Node exposes its fields, so a caller can assemble such a graph by
	// hand or by editing a decoded tree; verification reports it rather than faulting.
	ErrMalformedTree = errors.New("error: tree is empty or malformed")
)
View Source 
var (
	// ErrUnsupportedVersion is returned when decoding a tree written by a newer
	// format version than this build understands.
	ErrUnsupportedVersion = errors.New("merkletree: unsupported serialization version")
	// ErrCorruptData is returned when a serialized tree is malformed, truncated,
	// or not a merkletree payload at all.
	ErrCorruptData = errors.New("merkletree: corrupt serialized tree")
	// ErrRootMismatch is returned when the tree rebuilt from a payload does not
	// hash to the Merkle root recorded in that payload.
	ErrRootMismatch = errors.New("merkletree: rebuilt Merkle root does not match the encoded root")
	// ErrNoHashStrategy is returned when a hash strategy cannot be named at encode
	// time or resolved at decode time.
	ErrNoHashStrategy = errors.New("merkletree: unknown hash strategy")
	// ErrNoContentType is returned when a content type cannot be named at encode
	// time or resolved at decode time.
	ErrNoContentType = errors.New("merkletree: unregistered content type")
)
View Source 
var ErrMalformedProof = errors.New("error: proof is malformed")

ErrMalformedProof is returned when a proof cannot be walked at all: a path and an index of different lengths, or a side marker that is neither 0 nor 1. It reports a proof that is the wrong shape rather than one that is the right shape and does not verify, which is an ordinary false. Test for it with errors.Is.

Functions

func HashStrategyNames added in v0.4.0 

func HashStrategyNames() []string

HashStrategyNames returns the sorted names of every registered hash strategy.

func RegisterContent added in v0.4.0 

func RegisterContent(c Content)

RegisterContent makes a Content type serializable by the registry-backed marshalers (MarshalBinary, MarshalJSON, and anything built on them such as encoding/gob), under a name derived from its package path and type name.

The value passed is a template, not data: pass a zero value of the type exactly as it is stored in the tree. Registering TestContent{} round-trips leaves back to TestContent values; registering &TestContent{} round-trips them back to pointers.

The type must marshal itself. c must implement encoding.BinaryMarshaler and a pointer to it must implement encoding.BinaryUnmarshaler, which is the usual pairing of a value receiver for MarshalBinary and a pointer receiver for UnmarshalBinary. RegisterContent panics if either is missing, or if the type is unnamed.

Callers who would rather not use a package-level registry can skip registration entirely and use MarshalWith and UnmarshalWith instead.

func RegisterContentName added in v0.4.0 

func RegisterContentName(name string, c Content)

RegisterContentName is RegisterContent with an explicit name. Use it to pin a stable name into the wire format so that renaming or moving the Go type does not invalidate payloads already written.

func RegisterHashStrategy added in v0.4.0 

func RegisterHashStrategy(name string, strategy func() hash.Hash)

RegisterHashStrategy makes a hash strategy serializable under the given name. The hash strategies in the standard library are registered automatically; anything else - keccak256, blake2b, or a strategy of your own - must be registered before a tree using it can be marshaled or unmarshaled. 

merkletree.RegisterHashStrategy("keccak256", sha3.NewLegacyKeccak256)
t, err := merkletree.NewTreeWithHashStrategy(list, sha3.NewLegacyKeccak256)

Registration is idempotent: registering the same name and strategy again is a no-op. Registering a different strategy under a name already in use panics, because doing so would silently change the meaning of previously written payloads. Registering a second name for an already registered strategy is allowed, but the first name wins when encoding.

RegisterHashStrategy is safe for concurrent use, though the natural place to call it is package initialization.

func VerifyProof added in v0.5.0 

func VerifyProof(content Content, path [][]byte, index []int64, root []byte, opts ...TreeOption) (bool, error)

VerifyProof reports whether content, the audit path and the side index returned by GetMerklePath together reproduce root.

This is the operation a verifier performs when it holds a root obtained from somewhere it trusts, and a proof obtained from somewhere it does not. It needs no tree: the whole point is that the party checking the proof does not have to hold, rebuild, or have ever seen the tree the proof came from. MerkleTree.VerifyContent answers a different question, on a tree it already has.

The options configure the construction the proof was produced under, and they must match the tree that produced it or verification fails. Only the options that affect hashing are meaningful here: WithHasher, WithSortedSiblings and WithRFC6962. The others describe how a tree is built rather than how its hashes are computed, and are accepted and ignored so that the same option list can be shared with the constructor. A tree's own settings are readable through MerkleTree.Sorted and MerkleTree.RFC6962.

Returns false when the proof simply does not reproduce root, and an error when the proof is malformed or hashing the content fails.

What a verified proof does and does not establish

It establishes that content sits in some tree whose root is root. It says nothing about whether root is the root a verifier should be trusting; that has to arrive through a channel the verifier already trusts, and this function cannot check it.

Under the default construction it establishes less than it appears to. Leaf and interior hashes are computed the same way, so nothing distinguishes a leaf digest from an interior one, and a path can be presented that treats an interior node as though it were a leaf. Building the tree with WithRFC6962 closes this: the two kinds of hash carry distinct prefixes, so a forgery of that shape would need a genuine collision. The distinction matters far more here than it does for VerifyContent, which walks a real tree and so can only be shown nodes that are really in it. Prefer WithRFC6962 for proofs that arrive from somewhere untrusted.

func VerifyProofWithDigest added in v0.5.0 

func VerifyProofWithDigest(digest []byte, path [][]byte, index []int64, root []byte, opts ...TreeOption) (bool, error)

VerifyProofWithDigest is VerifyProof for a verifier that holds the leaf digest rather than the content itself, and so has no reason to implement Content.

The digest is the value Content.CalculateHash returns for the leaf, which is the leaf hash the tree records under the default construction. Under WithRFC6962 the tree records the prefixed hash of that digest instead, and this function applies the prefix itself, so the argument is the same value either way: what CalculateHash returned, not what the tree stored.

Types

type Content 

type Content interface {
	CalculateHash() ([]byte, error)
	Equals(other Content) (bool, error)
}

Content represents the data that is stored and verified by the tree. A type that implements this interface can be used as an item in the tree.

Implementations are expected to keep Equals and CalculateHash consistent: two items that report equal should hash equal, and two items that hash equal should report equal. Lookups by content return the first matching leaf, so a type that breaks this correspondence can be located by one method and hashed by the other.

type ContentMarshalFunc added in v0.4.0 

type ContentMarshalFunc func(Content) ([]byte, error)

ContentMarshalFunc encodes a single content item to bytes. It must be deterministic: two content items that are Equals must encode identically, or a decoded tree will not reproduce the root it was encoded with.

type ContentUnmarshalFunc added in v0.4.0 

type ContentUnmarshalFunc func([]byte) (Content, error)

ContentUnmarshalFunc decodes a single content item produced by a ContentMarshalFunc.

type MarshalOption added in v0.4.0 

type MarshalOption func(*marshalConfig)

MarshalOption adjusts how a tree is encoded.

func WithHashStrategyName added in v0.4.0 

func WithHashStrategyName(name string) MarshalOption

WithHashStrategyName records the given name for the tree's hash strategy instead of looking the strategy up in the package registry. Pair it with WithHashStrategy at decode time to serialize trees without touching global state at all.

type MerkleTree 

type MerkleTree struct {
	Root *Node

	Leafs []*Node
	// contains filtered or unexported fields
}

MerkleTree is the container for the tree. It holds a pointer to the root of the tree, a list of pointers to the leaf nodes, and the merkle root.

Note that Node points back at its Tree and at its Parent, so the tree contains reference cycles and cannot be handed directly to a reflection-based codec. Use the marshalers in serialize.go, which encode the content the tree is rebuilt from rather than the node graph itself.

func NewTree 

func NewTree(cs []Content) (*MerkleTree, error)

NewTree creates a new Merkle Tree using the content cs.

func NewTreeWithHashStrategy added in v0.2.0 

func NewTreeWithHashStrategy(cs []Content, hashStrategy func() hash.Hash) (*MerkleTree, error)

NewTreeWithHashStrategy creates a new Merkle Tree using the content cs using the provided hash strategy. Note that the hash type used in the type that implements the Content interface must match the hash type provided to the tree.

func NewTreeWithHashStrategySorted added in v0.3.0 

func NewTreeWithHashStrategySorted(cs []Content, hashStrategy func() hash.Hash, sort bool) (*MerkleTree, error)

NewTreeWithHashStrategySorted just like NewTreeWithHashStrategy but sorts the siblings before hashing, mostly to follow the OpenZepplin Merkle implementation https://github.com/OpenZeppelin/openzeppelin-contracts-ethereum-package/blob/master/contracts/cryptography/MerkleProof.sol

func NewTreeWithOptions added in v0.4.0 

func NewTreeWithOptions(cs []Content, opts ...TreeOption) (*MerkleTree, error)

NewTreeWithOptions creates a new Merkle Tree using the content cs, configured by the given options. With no options it is equivalent to NewTree.

func UnmarshalWith added in v0.4.0 

func UnmarshalWith(data []byte, dec ContentUnmarshalFunc, opts ...UnmarshalOption) (*MerkleTree, error)

UnmarshalWith decodes a tree written by MarshalWith, using dec to decode each content item. The rebuilt tree is verified against the Merkle root recorded in data, so a successful return means the tree hashes exactly as it did when it was encoded.

func (*MerkleTree) AppendMerklePath added in v0.5.0 

func (m *MerkleTree) AppendMerklePath(path [][]byte, index []int64, content Content) ([][]byte, []int64, error)

AppendMerklePath appends the audit path for the leaf holding content to path, and the side each sibling sits on to index, returning the extended slices. It is GetMerklePath in the style of strconv.AppendInt: the proof produced is identical, but where the slices land is the caller's decision. Passing slices with capacity to spare - most simply the previous proof's, resliced to length zero - makes proof generation allocate nothing, which is worth having where proofs are served at rate: the per-proof slice allocations are otherwise the ceiling on concurrent throughput, with the garbage collector as the shared resource every goroutine queues on. 

var path [][]byte
var index []int64
for _, c := range contents {
	path, index, err = tree.AppendMerklePath(path[:0], index[:0], c)
	...
}

The appended hashes are the tree's own, not copies; treat them as read only, and note that reusing the path buffer overwrites the positions of the previous proof, so a proof that must outlive the next call has to be copied out.

Content is located exactly as GetMerklePath locates it, including the leaf index when the tree has one and the first-match rule. If no leaf holds the content, the returned error wraps ErrContentNotFound and the slices are returned unchanged.

func (*MerkleTree) AppendMerklePathByIndex added in v0.5.0 

func (m *MerkleTree) AppendMerklePathByIndex(path [][]byte, index []int64, i int) ([][]byte, []int64, error)

AppendMerklePathByIndex appends the audit path for the leaf at position i in Leafs to path, and the side each sibling sits on to index, returning the extended slices. It is to GetMerklePathByIndex what AppendMerklePath is to GetMerklePath, and the notes there - identical proofs, reused buffers making generation allocation free, appended hashes being the tree's own - apply unchanged.

Returns ErrContentNotFound and the slices unchanged if i is outside the range of Leafs.

func (*MerkleTree) GetMerklePath 

func (m *MerkleTree) GetMerklePath(content Content) ([][]byte, []int64, error)

GetMerklePath returns the sibling hashes on the path from the leaf holding content up to the root, together with an index describing which side each sibling sits on: 1 when the sibling is the right hand node, 0 when it is the left hand node.

Content is located by Content.Equals and the first matching leaf wins, so a value stored in more than one leaf yields the proof for the earliest of them. If no leaf holds the content, the returned error wraps ErrContentNotFound.

Locating the content is a scan over every leaf, which makes this O(n) in the leaf count while the walk it performs afterwards is only O(log n). Build the tree with WithLeafIndex to replace the scan with a single hash and map probe, or use GetMerklePathByIndex when the position is already known. AppendMerklePath produces the same proof into caller supplied slices, for callers generating proofs at a rate where the two returned slices are a cost worth removing.

func (*MerkleTree) GetMerklePathByIndex added in v0.5.0 

func (m *MerkleTree) GetMerklePathByIndex(i int) ([][]byte, []int64, error)

GetMerklePathByIndex returns the same audit path as GetMerklePath for the leaf at position i in Leafs, without locating it by content first. It costs one step per level of the tree whatever the leaf count, where GetMerklePath has to find the leaf before it can walk.

The index is a position in Leafs, which is the order the content was supplied in. Note that a tree built from an odd number of items holds one more leaf than it was given, the last being a copy of the one before it; that copy is addressable here and yields a valid path, though its content is not distinct.

Returns ErrContentNotFound if i is outside the range of Leafs.

func (MerkleTree) MarshalBinary added in v0.4.0 

func (m MerkleTree) MarshalBinary() ([]byte, error)

MarshalBinary encodes the tree using the package content registry, implementing encoding.BinaryMarshaler. This is what makes a tree work with encoding/gob and any other codec that honors BinaryMarshaler: 

merkletree.RegisterContent(MyContent{})
err := gob.NewEncoder(&buf).Encode(tree)

Every content type in the tree must have been registered with RegisterContent, and the tree's hash strategy must have been registered with RegisterHashStrategy. Use MarshalWith to avoid the registries.

func (MerkleTree) MarshalJSON added in v0.4.0 

func (m MerkleTree) MarshalJSON() ([]byte, error)

MarshalJSON encodes the tree using the package content registry, implementing json.Marshaler. Byte fields are base64 encoded by encoding/json as usual.

Without this method json.Marshal would recurse forever on the tree's parent and tree back-pointers. Content is encoded through encoding.BinaryMarshaler, the same as MarshalBinary, so the JSON form carries opaque content payloads rather than the content's own JSON shape. Use MarshalWith when you need control over that.

func (MerkleTree) MarshalWith added in v0.4.0 

func (m MerkleTree) MarshalWith(enc ContentMarshalFunc, opts ...MarshalOption) ([]byte, error)

MarshalWith encodes the tree, using enc to encode each content item. It requires no package-level registration, which makes it the right choice for libraries and for content types that already have an encoding of their own.

Only the leaf content, the hash strategy name, the sibling sort flag, and the Merkle root are written; the tree structure is rebuilt on decode. Pair this with UnmarshalWith and a decoder that is the exact inverse of enc.

Example

ExampleMerkleTree_MarshalWith serializes a tree without registering anything, by supplying the content codec directly. 

package main

import (
	"bytes"
	"crypto/sha256"
	"fmt"

	"github.com/cbergoon/merkletree"
)

// Record is the content stored in the trees below. Alongside the Content interface it
// implements encoding.BinaryMarshaler and encoding.BinaryUnmarshaler, which is what
// makes it serializable through the package registry.
type Record struct {
	Name string
}

func (r Record) CalculateHash() ([]byte, error) {
	h := sha256.New()
	if _, err := h.Write([]byte(r.Name)); err != nil {
		return nil, err
	}
	return h.Sum(nil), nil
}

func (r Record) Equals(other merkletree.Content) (bool, error) {
	o, ok := other.(Record)
	if !ok {
		return false, nil
	}
	return r.Name == o.Name, nil
}

func (r Record) MarshalBinary() ([]byte, error) { return []byte(r.Name), nil }

func (r *Record) UnmarshalBinary(data []byte) error {
	r.Name = string(data)
	return nil
}

func main() {
	list := []merkletree.Content{Record{Name: "Alice"}, Record{Name: "Bob"}}
	tree, err := merkletree.NewTree(list)
	if err != nil {
		fmt.Println(err)
		return
	}

	data, err := tree.MarshalWith(func(c merkletree.Content) ([]byte, error) {
		return []byte(c.(Record).Name), nil
	})
	if err != nil {
		fmt.Println(err)
		return
	}

	decoded, err := merkletree.UnmarshalWith(data, func(b []byte) (merkletree.Content, error) {
		return Record{Name: string(b)}, nil
	})
	if err != nil {
		fmt.Println(err)
		return
	}

	// UnmarshalWith rebuilds the tree and checks it against the root recorded in the
	// payload, so reaching this point already proves the tree is intact.
	fmt.Println("same root:", bytes.Equal(tree.MerkleRoot(), decoded.MerkleRoot()))

}

Output:
same root: true

func (*MerkleTree) MerkleRoot 

func (m *MerkleTree) MerkleRoot() []byte

MerkleRoot returns the unverified Merkle Root (hash of the root node) of the tree.

The returned slice is the tree's own, not a copy; treat it as read only.

func (*MerkleTree) RFC6962 added in v0.4.0 

func (m *MerkleTree) RFC6962() bool

RFC6962 reports whether the tree was built with WithRFC6962, meaning leaf and interior hashes carry distinct prefixes and odd node counts are split rather than duplicated.

func (*MerkleTree) RebuildTree 

func (m *MerkleTree) RebuildTree() error

RebuildTree is a helper function that will rebuild the tree reusing only the content that it holds in the leaves.

func (*MerkleTree) RebuildTreeWith 

func (m *MerkleTree) RebuildTreeWith(cs []Content) error

RebuildTreeWith replaces the content of the tree and does a complete rebuild; while the root of the tree will be replaced the MerkleTree completely survives this operation. Returns an error if the list of content cs contains no entries.

func (*MerkleTree) Sorted added in v0.4.0 

func (m *MerkleTree) Sorted() bool

Sorted reports whether the tree orders each pair of siblings before hashing them, as chosen by NewTreeWithHashStrategySorted.

Sorting siblings makes the root independent of the order the content was supplied in: [A B C D] and [B A C D] and [D C B A] all produce the same root, because each pair is ordered before it is hashed and the pairing itself is all that survives. Only regrouping which items are paired together changes the root. Callers that depend on the root committing to leaf order should check this is false.

func (*MerkleTree) String 

func (m *MerkleTree) String() string

String returns a string representation of the tree. Only leaf nodes are included in the output.

func (*MerkleTree) UnmarshalBinary added in v0.4.0 

func (m *MerkleTree) UnmarshalBinary(data []byte) error

UnmarshalBinary rebuilds the tree from a payload written by MarshalBinary, implementing encoding.BinaryUnmarshaler. The receiver is left untouched if decoding fails for any reason, including the rebuilt root failing to match the recorded one.

func (*MerkleTree) UnmarshalJSON added in v0.4.0 

func (m *MerkleTree) UnmarshalJSON(data []byte) error

UnmarshalJSON rebuilds the tree from a payload written by MarshalJSON, implementing json.Unmarshaler. As with UnmarshalBinary the receiver is left untouched on failure.

func (*MerkleTree) VerifyContent 

func (m *MerkleTree) VerifyContent(content Content) (bool, error)

VerifyContent indicates whether a given content is in the tree and the hashes are valid for that content. Returns true if the expected Merkle Root is equivalent to the Merkle root calculated on the critical path for a given content. Returns true if valid and false otherwise.

func (*MerkleTree) VerifyProof added in v0.5.0 

func (m *MerkleTree) VerifyProof(content Content, path [][]byte, index []int64) (bool, error)

VerifyProof reports whether the given proof reproduces this tree's root, using this tree's construction settings.

It is the convenience form of the package level VerifyProof for a caller that does hold the tree, and saves restating the tree's options. It still verifies the proof it is given rather than looking anything up, so it will reject a proof for content this tree holds if that proof was generated somewhere else under different settings.

func (*MerkleTree) VerifyTree 

func (m *MerkleTree) VerifyTree() (bool, error)

VerifyTree verify tree validates the hashes at each level of the tree and returns true if the resulting hash at the root of the tree matches the resulting root hash; returns false otherwise.

type Node 

type Node struct {
	Tree   *MerkleTree
	Parent *Node
	Left   *Node
	Right  *Node

	Hash []byte
	C    Content
	// contains filtered or unexported fields
}

Node represents a node, root, or leaf in the tree. It stores pointers to its immediate relationships, a hash, the content stored if it is a leaf, and other metadata.

func (*Node) String added in v0.2.0 

func (n *Node) String() string

String returns a string representation of the node.

type TreeOption added in v0.4.0 

type TreeOption func(*MerkleTree)

TreeOption configures a tree built by NewTreeWithOptions.

func WithHasher added in v0.4.0 

func WithHasher(strategy func() hash.Hash) TreeOption

WithHasher sets the hash strategy used for interior nodes, and for the leaf prefix under WithRFC6962. It defaults to sha256.New.

The hash a Content implementation returns from CalculateHash must be produced by a compatible algorithm; the tree does not and cannot check this.

func WithLeafIndex added in v0.5.0 

func WithLeafIndex() TreeOption

WithLeafIndex builds a lookup table from leaf hash to leaf position, so that GetMerklePath and VerifyContent find their content by hashing it once instead of scanning every leaf. It is off by default.

Without it, locating content is a linear scan calling Content.Equals on each leaf, which makes a single proof O(n) and a full set of proofs O(n²). At a hundred thousand leaves that is around 98µs per proof and roughly ten seconds for the whole set. With it, a lookup is one hash and one map probe whatever the leaf count.

The index costs memory proportional to the leaf count, on the order of the digest width plus map overhead per leaf, which is why it is opt in rather than automatic. It costs no extra hashing to build: every leaf hash it records was already computed and stored during construction.

It changes how content is located, which is the reason to think before reaching for it. Without the index a leaf is found by Content.Equals; with it a leaf is found by comparing the hash of the query against the recorded leaf hashes. The Content interface already requires the two to agree - items that are equal must hash equal, and items that hash equal must be equal - so for any implementation that honors that contract both routes return the same leaf, including the rule that the earliest matching leaf wins. For an implementation that does not, the two disagree, and only the scan reflects Equals.

One consequence is worth stating plainly, because it shows up in error handling: an indexed lookup hashes the content it is given and never calls Equals, where a scan calls Equals on each leaf and never hashes what it was given. A query whose CalculateHash returns an error therefore fails only on the indexed path, and content whose Equals returns an error surfaces that only on the scanning path.

The root is unaffected, and neither is anything a proof is checked against. Like WithParallelism the index is absent from the serialized form, so a tree read back with UnmarshalBinary or UnmarshalJSON has no index unless it is asked for again; RebuildTree and RebuildTreeWith do regenerate it.

func WithParallelism added in v0.5.0 

func WithParallelism(n int) TreeOption

WithParallelism builds the tree using up to n goroutines, or GOMAXPROCS of them when n is less than one. It is off by default.

Content.CalculateHash is called concurrently from several goroutines when this is set, and implementations must be safe for that. Nothing else in this package calls it concurrently and the tree cannot check whether yours is safe, so this requirement is the whole cost of the option and the reason it is not the default.

The root is unaffected. Every hash is written to a slot fixed by its position, so the order the goroutines finish in cannot change the result: a tree built with this option is byte for byte the tree built without it.

How much it buys depends almost entirely on what CalculateHash costs. Hashing the interior of the tree parallelizes too, but that work is small and fixed, so it is left serial below a threshold where the coordination would cost more than it saves. Content hashing is neither small nor knowable in advance, so it is always spread across the goroutine budget when this option is set, whatever the leaf count.

That last point cuts both ways, and it is worth measuring rather than assuming. Where content is expensive to hash this option is worth several times the serial build, and the advantage grows with the cost. Where content is cheap the leaves finish so quickly that handing them out costs more than it saves on a small tree: a few thousand leaves of a short string is roughly the break-even, and below it a parallel build can be slower than a serial one.

Parallelism is not recorded when a tree is serialized, because it has no bearing on the root. A tree read back with UnmarshalBinary or UnmarshalJSON rebuilds serially unless it is built again with this option.

func WithRFC6962 added in v0.4.0 

func WithRFC6962() TreeOption

WithRFC6962 builds the tree the way RFC 6962 section 2.1 specifies, which closes two weaknesses in the default Bitcoin-style construction:

Leaf and interior hashes are computed behind distinct one byte prefixes, 0x00 and 0x01. Without them 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. With them a forgery would need a genuine collision between two differently prefixed inputs.

Odd node counts are split rather than duplicated. The default construction pairs the last node with itself, so [A B C] and [A B C C] hash alike, which is CVE-2012-2459. RFC 6962 splits each node list at the largest power of two below its length instead, so every distinct leaf sequence has a distinct root.

Note that RFC 6962 hashes raw leaf data, whereas this tree hashes whatever Content.CalculateHash returns. Roots therefore match a Certificate Transparency log only if CalculateHash returns the leaf bytes themselves rather than a digest of them. The structural guarantees above hold either way.

Trees built this way do not share roots with trees built any other way, so this is a choice to make when a tree is created rather than one to change later.

func WithSortedSiblings added in v0.4.0 

func WithSortedSiblings() TreeOption

WithSortedSiblings orders each pair of siblings by their big-endian integer value before hashing them, matching the OpenZeppelin MerkleProof convention. It is the option form of NewTreeWithHashStrategySorted.

Sorting makes the root independent of the order content was supplied in; see MerkleTree.Sorted. It cannot be combined with WithRFC6962, which specifies its own unsorted ordering.

type UnmarshalOption added in v0.4.0 

type UnmarshalOption func(*unmarshalConfig)

UnmarshalOption adjusts how a tree is decoded.

func WithHashStrategy added in v0.4.0 

func WithHashStrategy(strategy func() hash.Hash) UnmarshalOption

WithHashStrategy rebuilds the tree with the given hash strategy instead of resolving the name recorded in the payload through the package registry. The recorded name is still preserved, so re-encoding the decoded tree reproduces the original name.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.