merkletree

README

merkletree

A Merkle Hash Trees implementation according to RFC 6962, written in Go.

Documentation

Index

• Constants
• func Append(store Storer, b []byte)
• func AppendHash(store Storer, h *[sha256.Size]byte)
• func Depth(store Storer) int
• func IsFrozen(layer uint8, index, at uint64) bool
• func LeafHash(b []byte) [sha256.Size]byte
• func MPath(m uint64, D [][]byte) (path [][sha256.Size]byte)
• func MProof(m uint64, D [][]byte) [][sha256.Size]byte
• func MTH(D [][]byte) [sha256.Size]byte
• func Root(store Storer) [sha256.Size]byte
• type Path
  • func ConsistencyProof(store Storer, at, i uint64) (p Path)
  • func InclusionProof(store Storer, at, i uint64) (p Path)
  • func (p *Path) FromSlice(slice [][]byte)
  • func (p Path) ToSlice() [][]byte
  • func (p Path) VerifyConsistency(second, first uint64, secondHash, firstHash [sha256.Size]byte) bool
  • func (p Path) VerifyInclusion(at, i uint64, root, leaf [sha256.Size]byte) bool
• type Storer
  • func NewMemStore() Storer

Constants

const (
	LeafPrefix = byte(0)
	NodePrefix = byte(1)
)

Prefixes for leaves and nodes

Functions

func Append

func Append(store Storer, b []byte)

Append computes the hash of the given content b, appends it to the next free slot in the tree, then incrementally builds the intermediate nodes up to the root.

func AppendHash

func AppendHash(store Storer, h *[sha256.Size]byte)

AppendHash appends the given hash _h_ to the next free slot in the tree, then incrementally builds the intermediate nodes up to the root. AppendHash re-uses _h_ internally, as side-effect the new root will be set to _h_.

func Depth

func Depth(store Storer) int

Depth returns the length of the path from leaves to the root. When the tree is empty then -1 is returned.

func IsFrozen

func IsFrozen(layer uint8, index, at uint64) bool

IsFrozen returns true when the node (_layer_, _index_) in a tree of width = (_at_ + 1) is frozen, otherwise false. Once a given subtree in the node has no more slots, the hash for the root node of that subtree is frozen (i.e., will not change as future nodes are added). In a tree with position _at_ (i.e. width = _at_ + 1), node (_layer_, _index_) is frozen

func LeafHash

func LeafHash(b []byte) [sha256.Size]byte

LeafHash computes the leaf's hash of the given content b.

func MPath

func MPath(m uint64, D [][]byte) (path [][sha256.Size]byte)

MPath returns the Merkle Audit Path for the (_m_+1)th input of the given ordered list of n inputs _D_. The Merkle Audit Path is defined only for 0 <= _m_ < n. For undefined paths, MPath returns a _nil_ slice. Reference implementation as per https://tools.ietf.org/html/rfc6962#section-2.1.1

func MProof

func MProof(m uint64, D [][]byte) [][sha256.Size]byte

MProof returns the Merke Consistency Proof for the MTH(_D_[n]) and the previously advertised MTH(_D_[_m_:0]) of the first _m_ leaves when _m_ <= n, let n the length of the given ordered list of inputs _D_. The Merke Consistency Proof is defined only for 0 < _m_ < n. For undefined proofs, MProof returns a _nil_ slice. Reference implementation as per https://tools.ietf.org/html/rfc6962#section-2.1.2

func MTH

func MTH(D [][]byte) [sha256.Size]byte

MTH returns the Merkle Tree Hash, given an ordered list of n inputs _D_. Reference implementation as per https://tools.ietf.org/html/rfc6962#section-2.1

func Root

func Root(store Storer) [sha256.Size]byte

Root returns the root hash of the tree. Panic if store is empty.

Types

type Path

type Path [][sha256.Size]byte

Path is a list of additional nodes required for proving inclusion or consistency.

func ConsistencyProof

func ConsistencyProof(store Storer, at, i uint64) (p Path)

ConsistencyProof returns the list of nodes required to verify that the first (_i_+1) inputs are equal in both (sub-)trees constructed up to the (_i_+1)th leaf and the (_at_+1)th leaf stored into the given _store_. The number of nodes in the resulting proof is bounded above ceil(log2(at+1))+1.

func InclusionProof

func InclusionProof(store Storer, at, i uint64) (p Path)

InclusionProof returns the shortest list of additional nodes required to compute the root (i.e., MTH) from the (_i_+1)th leaf, assuming the (sub-)tree constructed up to the (_at_+1)th leaf and stored into a given _store_.

func (*Path) FromSlice

func (p *Path) FromSlice(slice [][]byte)

FromSlice sets _Path_ from the give _slice_.

func (Path) ToSlice

func (p Path) ToSlice() [][]byte

ToSlice returns a copy of _Path_ content as slice of byte slices.

func (Path) VerifyConsistency

func (p Path) VerifyConsistency(second, first uint64, secondHash, firstHash [sha256.Size]byte) bool

VerifyConsistency returns true when the Path _p_ proves that the first (_first_+1) inputs are equal in both (sub-)trees described by _firtsHash_ and _secondHash_, respectively constructed up to the (_first_+1)th leaf and the (_second_+1)th leaf, otherwise false.

VerifyConsistency assumes Path _p_ has been generated by using ConsistencyProof func.

func (Path) VerifyInclusion

func (p Path) VerifyInclusion(at, i uint64, root, leaf [sha256.Size]byte) bool

VerifyInclusion returns true when the Path _p_ proves that the given _leaf_ is the (_i_+1)th leaf of the tree defined by _root_ and width = (_at_ + 1), otherwise false.

VerifyConsistency assumes Path _p_ has been generated by using InclusionProof func.

type Storer

type Storer interface {
	// Width returns the number of leaves present in the tree.
	Width() uint64
	// Set assigns _value_ to the node referenced by _layer_ and _index_.
	Set(layer uint8, index uint64, value [sha256.Size]byte)
	// Get returns value of the node referenced by _layer_ and _index_.
	Get(layer uint8, index uint64) *[sha256.Size]byte
}

Storer is the interface that wraps the basic methods to access a tree storage.

A tree storage provides a way set and get nodes in a tree by using _layer_ and _index_ coordinates. The _layer_ indicates the node level from bottom to top (_layer_ is always 0 for leaves), _index_ is the position from left to right. Both _layer_ and _index_ are zero-based.

func NewMemStore

func NewMemStore() Storer

NewMemStore returns an in-memory implementation for the _Storer_ interface, mainly intended for testing purpose.