merkle

package
v0.31.5-fix-AN-transac... Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 9, 2023 License: AGPL-3.0 Imports: 6 Imported by: 2

Documentation

Index

Constants

This section is empty.

Variables

View Source
var EmptyTreeRootHash []byte
View Source
var ErrorIncompatibleKeyLength = errors.New("key has incompatible size")

Functions

func IsInvalidProofError added in v0.23.9

func IsInvalidProofError(err error) bool

IsInvalidProofError checks if err is a InvalidProofError

func IsMalformedProofError added in v0.23.9

func IsMalformedProofError(err error) bool

IsMalformedProofError checks if err is a MalformedProofError

Types

type InvalidProofError added in v0.23.9

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 added in v0.23.9

func (e InvalidProofError) Error() string

func (InvalidProofError) Unwrap added in v0.23.9

func (e InvalidProofError) Unwrap() error

Unwrap unwraps the error

type MalformedProofError added in v0.23.9

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

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

func NewMalformedProofErrorf added in v0.23.9

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

NewMalformedProofErrorf constructs a new MalformedProofError

func (MalformedProofError) Error added in v0.23.9

func (e MalformedProofError) Error() string

func (MalformedProofError) Unwrap added in v0.23.9

func (e MalformedProofError) Unwrap() error

Unwrap unwraps the error

type Proof added in v0.23.9

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 added in v0.23.9

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 added in v0.29.0

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 added in v0.29.0

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 added in v0.23.9

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL