merkle

Documentation

Index

• Variables
• 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) Put(key []byte, val []byte) (bool, error)

Variables

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

Types

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