merkle

Documentation

Index

• Variables
• func CountUint16EncodingToInt(inp uint16) int
• func IsInvalidProofError(err error) bool
• func IsMalformedProofError(err error) bool
• type InvalidProofError
  • func NewInvalidProofErrorf(msg string, args ...interface{}) *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) Del(key []byte) bool
  • func (t *Tree) Get(key []byte) ([]byte, bool)
  • func (t *Tree) Hash() []byte
  • 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 CountUint16EncodingToInt

func CountUint16EncodingToInt(inp uint16) int

CountUint16EncodingToInt is the reverse method to CountAsUint16Encoding see `CountAsUint16Encoding` for more details.

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 NewInvalidProofErrorf

func NewInvalidProofErrorf(msg string, args ...interface{}) *InvalidProofError

NewInvalidProofErrorf constructs a new InvalidProofError

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 nodes or full nodes 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 to the leaf.
	// Note that we always allocated 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 number of common bits that were included
	// in the short node (shortNode.count). Elements are ordered from root to leaf.
	// WARNING, similar to the serializedPathSegmentLength method using by the trie, the uint16 encoding here requires special handling of value zero,
	// since shortNode.count can only have values in the range of [1, 65536], and a uint16 supports range of [0, 65535],
	// zero should be mapped to 65536 (all other values are the same)
	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 proof requires knowledge of the trie path structure (node types) and 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 ≤ 8192. Otherwise, the sentinel error `ErrorIncompatibleKeyLength` is returned.

func (*Tree) Del

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

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) 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 a proof and a boolean (true if key exist and false if key 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.