Documentation
¶
Overview ¶
Package mpt implements MPT (Merkle-Patricia Tree).
MPT stores key-value pairs and is a trie over 16-symbol alphabet. https://en.wikipedia.org/wiki/Trie Trie is a tree where values are stored in leafs and keys are paths from root to the leaf node. MPT consists of 4 type of nodes:
- Leaf node contains only value.
- Extension node contains both key and value.
- Branch node contains 2 or more children.
- Hash node is a compressed node and contains only actual node's hash. The actual node must be retrieved from storage or over the network.
As an example here is a trie containing 3 pairs: - 0x1201 -> val1 - 0x1203 -> val2 - 0x1224 -> val3 - 0x12 -> val4
ExtensionNode(0x0102), Next
_______________________| |
BranchNode [0, 1, 2, ...], Last -> Leaf(val4)
| | | ExtensionNode [0x04], Next -> Leaf(val3) | BranchNode [0, 1, 2, 3, ...], Last -> HashNode(nil) | | | Leaf(val2) | Leaf(val1)
There are 3 invariants that this implementation has: - Branch node cannot have <= 1 children - Extension node cannot have zero-length key - Extension node cannot have another Extension node in it's next field
Thank to these restrictions, there is a single root hash for every set of key-value pairs irregardless of the order they were added/removed with. The actual trie structure can vary because of node -> HashNode compressing.
There is also one optimization which cost us almost nothing in terms of complexity but is very beneficial: When we perform get/put/delete on a speficic path, every Hash node which was retreived from storage is replaced by its uncompressed form, so that subsequent hits of this not don't use storage.
Index ¶
- Constants
- Variables
- func GetChildrenPaths(path []byte, node Node) map[util.Uint256][][]byte
- func VerifyProof(rh util.Uint256, key []byte, proofs [][]byte) ([]byte, bool)
- type BaseNode
- type BaseNodeIface
- type Batch
- type Billet
- type BranchNode
- func (b *BranchNode) Bytes() []byte
- func (b *BranchNode) Clone() Node
- func (b *BranchNode) DecodeBinary(r *io.BinReader)
- func (b *BranchNode) EncodeBinary(w *io.BinWriter)
- func (b *BranchNode) Hash() util.Uint256
- func (b *BranchNode) MarshalJSON() ([]byte, error)
- func (b *BranchNode) Size() int
- func (b *BranchNode) Type() NodeType
- func (b *BranchNode) UnmarshalJSON(data []byte) error
- type EmptyNode
- func (e EmptyNode) Bytes() []byte
- func (EmptyNode) Clone() Node
- func (e EmptyNode) DecodeBinary(*io.BinReader)
- func (e EmptyNode) EncodeBinary(*io.BinWriter)
- func (e EmptyNode) Hash() util.Uint256
- func (e EmptyNode) MarshalJSON() ([]byte, error)
- func (EmptyNode) Size() int
- func (e EmptyNode) Type() NodeType
- func (e EmptyNode) UnmarshalJSON(bytes []byte) error
- type ExtensionNode
- func (e *ExtensionNode) Bytes() []byte
- func (e *ExtensionNode) Clone() Node
- func (e *ExtensionNode) DecodeBinary(r *io.BinReader)
- func (e ExtensionNode) EncodeBinary(w *io.BinWriter)
- func (e *ExtensionNode) Hash() util.Uint256
- func (e *ExtensionNode) MarshalJSON() ([]byte, error)
- func (e *ExtensionNode) Size() int
- func (e ExtensionNode) Type() NodeType
- func (e *ExtensionNode) UnmarshalJSON(data []byte) error
- type HashNode
- func (h *HashNode) Bytes() []byte
- func (h *HashNode) Clone() Node
- func (h *HashNode) DecodeBinary(r *io.BinReader)
- func (h HashNode) EncodeBinary(w *io.BinWriter)
- func (h *HashNode) Hash() util.Uint256
- func (h *HashNode) MarshalJSON() ([]byte, error)
- func (h *HashNode) Size() int
- func (h *HashNode) Type() NodeType
- func (h *HashNode) UnmarshalJSON(data []byte) error
- type LeafNode
- func (n *LeafNode) Bytes() []byte
- func (n *LeafNode) Clone() Node
- func (n *LeafNode) DecodeBinary(r *io.BinReader)
- func (n LeafNode) EncodeBinary(w *io.BinWriter)
- func (n *LeafNode) Hash() util.Uint256
- func (n *LeafNode) MarshalJSON() ([]byte, error)
- func (n *LeafNode) Size() int
- func (n LeafNode) Type() NodeType
- func (n *LeafNode) UnmarshalJSON(data []byte) error
- type Node
- type NodeObject
- type NodeType
- type Trie
- func (t *Trie) Collapse(depth int)
- func (t *Trie) Delete(key []byte) error
- func (t *Trie) Find(prefix, from []byte, max int) ([]storage.KeyValue, error)
- func (t *Trie) Flush()
- func (t *Trie) Get(key []byte) ([]byte, error)
- func (t *Trie) GetProof(key []byte) ([][]byte, error)
- func (t *Trie) Put(key, value []byte) error
- func (t *Trie) PutBatch(b Batch) (int, error)
- func (t *Trie) StateRoot() util.Uint256
Constants ¶
const ( // MaxKeyLength is the max length of the key to put in trie // before transforming to nibbles. MaxKeyLength = maxPathLength / 2 )
const MaxValueLength = 3 + storage.MaxStorageValueLen + 1
MaxValueLength is a max length of a leaf node value.
Variables ¶
var ErrNotFound = errors.New("item not found")
ErrNotFound is returned when requested trie item is missing.
var ( // ErrRestoreFailed is returned when replacing HashNode by its "unhashed" // candidate fails. ErrRestoreFailed = errors.New("failed to restore MPT node") )
Functions ¶
func GetChildrenPaths ¶ added in v0.97.3
GetChildrenPaths returns a set of paths to node's children who are non-empty HashNodes based on the node's path.
Types ¶
type BaseNode ¶
type BaseNode struct {
// contains filtered or unexported fields
}
BaseNode implements basic things every node needs like caching hash and serialized representation. It's a basic node building block intended to be included into all node types.
type BaseNodeIface ¶
BaseNodeIface abstracts away basic Node functions.
type Batch ¶ added in v0.93.0
type Batch struct {
// contains filtered or unexported fields
}
Batch is batch of storage changes. It stores key-value pairs in a sorted state.
type Billet ¶ added in v0.97.3
type Billet struct { Store *storage.MemCachedStore // contains filtered or unexported fields }
Billet is a part of MPT trie with missing hash nodes that need to be restored. Billet is based on the following assumptions:
- Refcount can only be incremented (we don't change MPT structure during restore, thus don't need to decrease refcount).
- Each time the part of Billet is completely restored, it is collapsed into HashNode.
- Pair (node, path) must be restored only once. It's a duty of MPT pool to manage MPT paths in order to provide this assumption.
func NewBillet ¶ added in v0.97.3
NewBillet returns new billet for MPT trie restoring. It accepts a MemCachedStore to decouple storage errors from logic errors so that all storage errors are processed during `store.Persist()` at the caller. This also has the benefit, that every `Put` can be considered an atomic operation.
func (*Billet) GetFromStore ¶ added in v0.97.3
GetFromStore returns MPT node from the storage.
func (*Billet) RestoreHashNode ¶ added in v0.97.3
RestoreHashNode replaces HashNode located at the provided path by the specified Node and stores it. It also maintains MPT as small as possible by collapsing those parts of MPT that have been completely restored.
func (*Billet) Traverse ¶ added in v0.97.3
func (b *Billet) Traverse(process func(pathToNode []byte, node Node, nodeBytes []byte) bool, ignoreStorageErr bool) error
Traverse traverses MPT nodes (pre-order) starting from the billet root down to its children calling `process` for each serialised node until true is returned from `process` function. It also replaces all HashNodes to their "unhashed" counterparts until the stop condition is satisfied.
type BranchNode ¶
BranchNode represents MPT's branch node.
func (*BranchNode) Clone ¶ added in v0.97.3
func (b *BranchNode) Clone() Node
Clone implements Node interface.
func (*BranchNode) DecodeBinary ¶
func (b *BranchNode) DecodeBinary(r *io.BinReader)
DecodeBinary implements io.Serializable.
func (*BranchNode) EncodeBinary ¶
func (b *BranchNode) EncodeBinary(w *io.BinWriter)
EncodeBinary implements io.Serializable.
func (*BranchNode) Hash ¶
func (b *BranchNode) Hash() util.Uint256
Hash implements BaseNode interface.
func (*BranchNode) MarshalJSON ¶
func (b *BranchNode) MarshalJSON() ([]byte, error)
MarshalJSON implements json.Marshaler.
func (*BranchNode) Size ¶ added in v0.97.2
func (b *BranchNode) Size() int
Size implements Node interface.
func (*BranchNode) UnmarshalJSON ¶
func (b *BranchNode) UnmarshalJSON(data []byte) error
UnmarshalJSON implements json.Unmarshaler.
type EmptyNode ¶ added in v0.97.2
type EmptyNode struct{}
EmptyNode represents empty node.
func (EmptyNode) DecodeBinary ¶ added in v0.97.2
DecodeBinary implements io.Serializable interface.
func (EmptyNode) EncodeBinary ¶ added in v0.97.2
EncodeBinary implements io.Serializable interface.
func (EmptyNode) MarshalJSON ¶ added in v0.97.2
MarshalJSON implements Node interface.
func (EmptyNode) UnmarshalJSON ¶ added in v0.97.2
UnmarshalJSON implements Node interface.
type ExtensionNode ¶
type ExtensionNode struct { BaseNode // contains filtered or unexported fields }
ExtensionNode represents MPT's extension node.
func NewExtensionNode ¶
func NewExtensionNode(key []byte, next Node) *ExtensionNode
NewExtensionNode returns hash node with the specified key and next node. Note: because it is a part of Trie, key must be mangled, i.e. must contain only bytes with high half = 0.
func (*ExtensionNode) Bytes ¶
func (e *ExtensionNode) Bytes() []byte
Bytes implements BaseNode interface.
func (*ExtensionNode) Clone ¶ added in v0.97.3
func (e *ExtensionNode) Clone() Node
Clone implements Node interface.
func (*ExtensionNode) DecodeBinary ¶
func (e *ExtensionNode) DecodeBinary(r *io.BinReader)
DecodeBinary implements io.Serializable.
func (ExtensionNode) EncodeBinary ¶
func (e ExtensionNode) EncodeBinary(w *io.BinWriter)
EncodeBinary implements io.Serializable.
func (*ExtensionNode) Hash ¶
func (e *ExtensionNode) Hash() util.Uint256
Hash implements BaseNode interface.
func (*ExtensionNode) MarshalJSON ¶
func (e *ExtensionNode) MarshalJSON() ([]byte, error)
MarshalJSON implements json.Marshaler.
func (*ExtensionNode) Size ¶ added in v0.97.2
func (e *ExtensionNode) Size() int
Size implements Node interface.
func (*ExtensionNode) UnmarshalJSON ¶
func (e *ExtensionNode) UnmarshalJSON(data []byte) error
UnmarshalJSON implements json.Unmarshaler.
type HashNode ¶
HashNode represents MPT's hash node.
func NewHashNode ¶
NewHashNode returns hash node with the specified hash.
func (*HashNode) DecodeBinary ¶
DecodeBinary implements io.Serializable.
func (HashNode) EncodeBinary ¶
EncodeBinary implements io.Serializable.
func (*HashNode) MarshalJSON ¶
MarshalJSON implements json.Marshaler.
func (*HashNode) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler.
type LeafNode ¶
type LeafNode struct { BaseNode // contains filtered or unexported fields }
LeafNode represents MPT's leaf node.
func NewLeafNode ¶
NewLeafNode returns hash node with the specified value.
func (*LeafNode) DecodeBinary ¶
DecodeBinary implements io.Serializable.
func (LeafNode) EncodeBinary ¶
EncodeBinary implements io.Serializable.
func (*LeafNode) MarshalJSON ¶
MarshalJSON implements json.Marshaler.
func (*LeafNode) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler.
type Node ¶
type Node interface { io.Serializable json.Marshaler json.Unmarshaler Size() int Clone() Node BaseNodeIface }
Node represents common interface of all MPT nodes.
func DecodeNodeWithType ¶ added in v0.78.2
DecodeNodeWithType decodes node together with it's type.
type NodeObject ¶
type NodeObject struct {
Node
}
NodeObject represents Node together with it's type. It is used for serialization/deserialization where type info is also expected.
func (*NodeObject) DecodeBinary ¶
func (n *NodeObject) DecodeBinary(r *io.BinReader)
DecodeBinary implements io.Serializable.
func (NodeObject) EncodeBinary ¶
func (n NodeObject) EncodeBinary(w *io.BinWriter)
EncodeBinary implements io.Serializable.
func (*NodeObject) UnmarshalJSON ¶
func (n *NodeObject) UnmarshalJSON(data []byte) error
UnmarshalJSON implements json.Unmarshaler.
type Trie ¶
type Trie struct { Store *storage.MemCachedStore // contains filtered or unexported fields }
Trie is an MPT trie storing all key-value pairs.
func NewTrie ¶
func NewTrie(root Node, enableRefCount bool, store *storage.MemCachedStore) *Trie
NewTrie returns new MPT trie. It accepts a MemCachedStore to decouple storage errors from logic errors so that all storage errors are processed during `store.Persist()` at the caller. This also has the benefit, that every `Put` can be considered an atomic operation.
func (*Trie) Collapse ¶
Collapse compresses all nodes at depth n to the hash nodes. Note: this function does not perform any kind of storage flushing so `Flush()` should be called explicitly before invoking function.
func (*Trie) Find ¶ added in v0.97.3
Find returns list of storage key-value pairs whose key is prefixed by the specified prefix starting from the specified `prefix`+`from` path (not including the item at the specified `prefix`+`from` path if so). The `max` number of elements is returned at max.
func (*Trie) Flush ¶
func (t *Trie) Flush()
Flush puts every node in the trie except Hash ones to the storage. Because we care only about block-level changes, there is no need to put every new node to storage. Normally, flush should be called with every StateRoot persist, i.e. after every block.
func (*Trie) GetProof ¶
GetProof returns a proof that key belongs to t. Proof consist of serialized nodes occurring on path from the root to the leaf of key.
func (*Trie) PutBatch ¶ added in v0.93.0
PutBatch puts batch to trie. It is not atomic (and probably cannot be without substantial slow-down) and returns number of elements processed. If an error is returned, the trie may be in the inconsistent state in case of storage failures. This is due to the fact that we can remove multiple children from the branch node simultaneously and won't strip the resulting branch node. However it is used mostly after the block processing to update MPT and error is not expected.