Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
var EmptyTreeRootHash []byte
var ErrorIncompatibleKeyLength = errors.New("key has incompatible size")
Functions ¶
func IsInvalidProofError ¶ added in v0.23.9
IsInvalidProofError checks if err is a InvalidProofError
func IsMalformedProofError ¶ added in v0.23.9
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
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 ¶
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
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 ¶
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 ¶
Get will retrieve the value associated with the given key. It returns true if the key was found and false otherwise.
func (*Tree) Hash ¶
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
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 ¶
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.
Source Files