merkle

Documentation

Index

• Variables
• func IsInvalidProofError(err error) bool
• func IsMalformedProofError(err error) bool
• type InvalidProofError
  • func (e InvalidProofError) Error() string
  • func (e InvalidProofError) Unwrap() error
• type MalformedProofError
  • func NewMalformedProofErrorf(msg string, args ...interface{}) *MalformedProofError
  • func (e MalformedProofError) Error() string
  • func (e MalformedProofError) Unwrap() error
• type Proof
  • func (p *Proof) Verify(expectedRootHash []byte) error
• type Tree
  • func NewTree(keyLength int) (*Tree, error)
  • func (t *Tree) ComputeMaxDepth() uint
  • func (t *Tree) Del(key []byte) (bool, error)
  • func (t *Tree) Get(key []byte) ([]byte, bool)
  • func (t *Tree) Hash() []byte
  • func (t *Tree) MakeItReadOnly()
  • func (t *Tree) Prove(key []byte) (*Proof, bool)
  • func (t *Tree) Put(key []byte, val []byte) (bool, error)

Variables

var EmptyTreeRootHash []byte

var ErrorIncompatibleKeyLength = errors.New("key has incompatible size")

Functions

func IsInvalidProofError

func IsInvalidProofError(err error) bool

IsInvalidProofError checks if err is a InvalidProofError

func IsMalformedProofError

func IsMalformedProofError(err error) bool

IsMalformedProofError checks if err is a MalformedProofError

Types

type InvalidProofError

type InvalidProofError struct {
	// contains filtered or unexported fields
}

InvalidProofError is returned when proof verification has failed (semantic check). The most common case for this error is when the computed root hash doesn't match the root hash provided to the Verify method.

func (InvalidProofError) Error

func (e InvalidProofError) Error() string

func (InvalidProofError) Unwrap

func (e InvalidProofError) Unwrap() error

Unwrap unwraps the error

type MalformedProofError

type MalformedProofError struct {
	// contains filtered or unexported fields
}

MalformedProofError is returned when a proof format has some issues (syntax checks).

func NewMalformedProofErrorf

func NewMalformedProofErrorf(msg string, args ...interface{}) *MalformedProofError

NewMalformedProofErrorf constructs a new MalformedProofError

func (MalformedProofError) Error

func (e MalformedProofError) Error() string

func (MalformedProofError) Unwrap

func (e MalformedProofError) Unwrap() error

Unwrap unwraps the error

type Proof

type Proof struct {
	// Key used to insert and look up the value
	Key []byte
	// Value stored in the trie for the given key
	Value []byte
	// InterimNodeTypes is designed to be consumed bit by bit to determine if the next node
	// is a short node or full node while traversing the trie downward (0: fullnode, 1: shortnode).
	// The very first bit corresponds to the root of the trie and last bit is the last
	// interim node before reaching the leaf.
	// The slice represents a bit vector where the lowest index byte represents the first 8 node types,
	// while the most significant bit of the byte represents the first node type (big endianness).
	// Note that we always allocate the minimal number of bytes needed to capture all
	// the nodes in the path (padded with zero)
	InterimNodeTypes []byte
	// ShortPathLengths is read when we reach a short node, and the value represents non-zero number of common bits that were included
	// in the short node (shortNode.count). Elements are ordered from root to leaf.
	ShortPathLengths []uint16
	// SiblingHashes is read when we reach a full node. The corresponding element represents
	// the hash of the non-visited sibling node for each full node on the path. Elements are ordered from root to leaf.
	SiblingHashes [][]byte
}

Proof captures all data needed for proving inclusion of a single key/value pair inside a merkle trie. Verifying a proof requires knowledge of the trie path structure (node types), traversing the trie from the leaf to the root, and computing hash values.

func (*Proof) Verify

func (p *Proof) Verify(expectedRootHash []byte) error

Verify verifies the proof by constructing the hash values bottom up and cross-check the constructed root hash with the given one. For valid proofs, `nil` is returned. During normal operations, the following error returns are expected:

• MalformedProofError if the proof has a syntactically invalid structure
• InvalidProofError if the proof is syntactically valid, but the reconstructed root hash does not match the expected value.

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree represents a binary patricia merkle tree. The difference with a normal merkle tree is that it compresses paths that lead to a single leaf into a single intermediary node, which makes it significantly more space-efficient and a lot harder to exploit for denial-of-service attacks. On the downside, it makes insertions and deletions more complex, as we need to split nodes and merge them, depending on whether there are leaves or not.

CONVENTION:

• If the tree contains _any_ elements, the tree is defined by its root vertex. This case follows completely the convention for nodes: "In any existing tree, all nodes are non-nil."
• Without any stored elements, there exists no root vertex in this data model, and we set `root` to nil.

func NewTree

func NewTree(keyLength int) (*Tree, error)

NewTree creates a new empty patricia merkle tree, with keys of the given `keyLength` (length measured in bytes). The current implementation only works with 1 ≤ keyLength ≤ 8191. Otherwise, the sentinel error `ErrorIncompatibleKeyLength` is returned.

func (*Tree) ComputeMaxDepth

func (t *Tree) ComputeMaxDepth() uint

ComputeMaxDepth returns the maximum depth of the tree by traversing all paths

Warning: this could be a very expensive operation for large trees, as nodes don't cache the depth of children and have to compute by traversing.

func (*Tree) Del

func (t *Tree) Del(key []byte) (bool, error)

Del removes the value associated with the given key from the patricia merkle trie. It returns true if they key was found and false otherwise. Internally, any parent nodes between the leaf up to the closest shared path will be deleted or merged, which keeps the trie deterministic regardless of insertion and deletion orders.

func (*Tree) Get

func (t *Tree) Get(key []byte) ([]byte, bool)

Get will retrieve the value associated with the given key. It returns true if the key was found and false otherwise.

func (*Tree) Hash

func (t *Tree) Hash() []byte

Hash returns the root hash of this patricia merkle tree. Per convention, an empty trie has an empty hash.

func (*Tree) MakeItReadOnly

func (t *Tree) MakeItReadOnly()

MakeItReadOnly makes the tree read only, this operation is not reversible. when tree becomes readonly, while doing operations it starts caching hashValues for faster operations.

func (*Tree) Prove

func (t *Tree) Prove(key []byte) (*Proof, bool)

Prove constructs an inclusion proof for the given key, provided the key exists in the trie. It returns: - (proof, true) if key is found - (nil, false) if key is not found Proof is constructed by traversing the trie from top to down and collects data for proof as follows:

• if full node, append the sibling node hash value to sibling hash list
• if short node, appends the node.shortCount to the short count list
• if leaf, would capture the leaf value

func (*Tree) Put

func (t *Tree) Put(key []byte, val []byte) (bool, error)

Put stores the given value in the trie under the given key. If the key already exists, it will replace the value and return true. All inputs are internally stored and copied where necessary, thereby allowing external code to re-use the slices. Returns:

• (false, nil): key-value pair is stored; key did _not_ yet exist prior to update
• (true, nil): key-value pair is stored; key existed prior to update and the old value was overwritten
• (false, error): with possible error returns
• ErrorIncompatibleKeyLength if `key` has different length than the pre-configured value No other errors are returned.