merkletree

package module
v0.4.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: 16 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.

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.

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

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.

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")
)
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")
)

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.

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) 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.

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) 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 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.