mpt

package
v0.98.5 Latest Latest
Warning

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

 Go to latest Published: May 13, 2022 License: MIT Imports: 12 Imported by: 0

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

View Source 
const (

	// MaxKeyLength is the max length of the key to put in trie
	// before transforming to nibbles.
	MaxKeyLength = maxPathLength / 2
)
View Source 
const MaxValueLength = 3 + storage.MaxStorageValueLen + 1

MaxValueLength is a max length of a leaf node value.

Variables

View Source 
var ErrNotFound = errors.New("item not found")

ErrNotFound is returned when requested trie item is missing.

View Source 
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 

func GetChildrenPaths(path []byte, node Node) map[util.Uint256][][]byte

GetChildrenPaths returns a set of paths to node's children who are non-empty HashNodes based on the node's path.

func IsActiveValue added in v0.98.2 

func IsActiveValue(v []byte) bool

func VerifyProof 

func VerifyProof(rh util.Uint256, key []byte, proofs [][]byte) ([]byte, bool)

VerifyProof verifies that path indeed belongs to a MPT with the specified root hash. It also returns value for the key.

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 

type BaseNodeIface interface {
	Hash() util.Uint256
	Type() NodeType
	Bytes() []byte
}

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.

func MapToMPTBatch added in v0.98.2 

func MapToMPTBatch(m map[string][]byte) Batch

MapToMPTBatch makes a Batch from unordered set of storage changes.

type Billet added in v0.97.3 

type Billet struct {
	TempStoragePrefix storage.KeyPrefix
	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:

  1. Refcount can only be incremented (we don't change MPT structure during restore, thus don't need to decrease refcount).
  2. Each time the part of Billet is completely restored, it is collapsed into HashNode.
  3. 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 

func NewBillet(rootHash util.Uint256, mode TrieMode, prefix storage.KeyPrefix, store *storage.MemCachedStore) *Billet

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 

func (b *Billet) GetFromStore(h util.Uint256) (Node, error)

GetFromStore returns MPT node from the storage.

func (*Billet) RestoreHashNode added in v0.97.3 

func (b *Billet) RestoreHashNode(path []byte, node Node) error

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 

type BranchNode struct {
	BaseNode
	Children [childrenCount]Node
}

BranchNode represents MPT's branch node.

func NewBranchNode 

func NewBranchNode() *BranchNode

NewBranchNode returns new branch node.

func (*BranchNode) Bytes 

func (b *BranchNode) Bytes() []byte

Bytes implements BaseNode interface.

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

func (b *BranchNode) Type() NodeType

Type 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) Bytes added in v0.97.2 

func (e EmptyNode) Bytes() []byte

Bytes implements Node interface.

func (EmptyNode) Clone added in v0.97.3 

func (EmptyNode) Clone() Node

Clone implements Node interface.

func (EmptyNode) DecodeBinary added in v0.97.2 

func (e EmptyNode) DecodeBinary(*io.BinReader)

DecodeBinary implements io.Serializable interface.

func (EmptyNode) EncodeBinary added in v0.97.2 

func (e EmptyNode) EncodeBinary(*io.BinWriter)

EncodeBinary implements io.Serializable interface.

func (EmptyNode) Hash added in v0.97.2 

func (e EmptyNode) Hash() util.Uint256

Hash implements Node interface.

func (EmptyNode) MarshalJSON added in v0.97.2 

func (e EmptyNode) MarshalJSON() ([]byte, error)

MarshalJSON implements Node interface.

func (EmptyNode) Size added in v0.97.2 

func (EmptyNode) Size() int

Size implements Node interface.

func (EmptyNode) Type added in v0.97.2 

func (e EmptyNode) Type() NodeType

Type implements Node interface.

func (EmptyNode) UnmarshalJSON added in v0.97.2 

func (e EmptyNode) UnmarshalJSON(bytes []byte) error

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

func (e ExtensionNode) Type() NodeType

Type implements Node interface.

func (*ExtensionNode) UnmarshalJSON 

func (e *ExtensionNode) UnmarshalJSON(data []byte) error

UnmarshalJSON implements json.Unmarshaler.

type HashNode 

type HashNode struct {
	BaseNode
	Collapsed bool
}

HashNode represents MPT's hash node.

func NewHashNode 

func NewHashNode(h util.Uint256) *HashNode

NewHashNode returns hash node with the specified hash.

func (*HashNode) Bytes 

func (h *HashNode) Bytes() []byte

Bytes returns serialized HashNode.

func (*HashNode) Clone added in v0.97.3 

func (h *HashNode) Clone() Node

Clone implements Node interface.

func (*HashNode) DecodeBinary 

func (h *HashNode) DecodeBinary(r *io.BinReader)

DecodeBinary implements io.Serializable.

func (HashNode) EncodeBinary 

func (h HashNode) EncodeBinary(w *io.BinWriter)

EncodeBinary implements io.Serializable.

func (*HashNode) Hash 

func (h *HashNode) Hash() util.Uint256

Hash implements Node interface.

func (*HashNode) MarshalJSON 

func (h *HashNode) MarshalJSON() ([]byte, error)

MarshalJSON implements json.Marshaler.

func (*HashNode) Size added in v0.97.2 

func (h *HashNode) Size() int

Size implements Node interface.

func (*HashNode) Type 

func (h *HashNode) Type() NodeType

Type implements Node interface.

func (*HashNode) UnmarshalJSON 

func (h *HashNode) UnmarshalJSON(data []byte) error

UnmarshalJSON implements json.Unmarshaler.

type LeafNode 

type LeafNode struct {
	BaseNode
	// contains filtered or unexported fields
}

LeafNode represents MPT's leaf node.

func NewLeafNode 

func NewLeafNode(value []byte) *LeafNode

NewLeafNode returns hash node with the specified value.

func (*LeafNode) Bytes 

func (n *LeafNode) Bytes() []byte

Bytes implements BaseNode interface.

func (*LeafNode) Clone added in v0.97.3 

func (n *LeafNode) Clone() Node

Clone implements Node interface.

func (*LeafNode) DecodeBinary 

func (n *LeafNode) DecodeBinary(r *io.BinReader)

DecodeBinary implements io.Serializable.

func (LeafNode) EncodeBinary 

func (n LeafNode) EncodeBinary(w *io.BinWriter)

EncodeBinary implements io.Serializable.

func (*LeafNode) Hash 

func (n *LeafNode) Hash() util.Uint256

Hash implements BaseNode interface.

func (*LeafNode) MarshalJSON 

func (n *LeafNode) MarshalJSON() ([]byte, error)

MarshalJSON implements json.Marshaler.

func (*LeafNode) Size added in v0.97.2 

func (n *LeafNode) Size() int

Size implements Node interface.

func (LeafNode) Type 

func (n LeafNode) Type() NodeType

Type implements Node interface.

func (*LeafNode) UnmarshalJSON 

func (n *LeafNode) UnmarshalJSON(data []byte) error

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 

func DecodeNodeWithType(r *io.BinReader) Node

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 NodeType 

type NodeType byte

NodeType represents node type.. 

const (
	BranchT    NodeType = 0x00
	ExtensionT NodeType = 0x01
	LeafT      NodeType = 0x02
	HashT      NodeType = 0x03
	EmptyT     NodeType = 0x04
)

Node types definitions.

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, mode TrieMode, 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 

func (t *Trie) Collapse(depth int)

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

func (t *Trie) Delete(key []byte) error

Delete removes key from trie. It returns no error on missing key.

func (*Trie) Find added in v0.97.3 

func (t *Trie) Find(prefix, from []byte, max int) ([]storage.KeyValue, error)

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(index uint32)

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

func (t *Trie) Get(key []byte) ([]byte, error)

Get returns value for the provided key in t.

func (*Trie) GetProof 

func (t *Trie) GetProof(key []byte) ([][]byte, error)

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

func (t *Trie) Put(key, value []byte) error

Put puts key-value pair in t.

func (*Trie) PutBatch added in v0.93.0 

func (t *Trie) PutBatch(b Batch) (int, error)

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.

func (*Trie) StateRoot 

func (t *Trie) StateRoot() util.Uint256

StateRoot returns root hash of t.

type TrieMode added in v0.98.2 

type TrieMode byte

TrieMode is the storage mode of trie, it affects the DB scheme. 

const (
	// ModeAll is used to store everything.
	ModeAll TrieMode = 0
	// ModeLatest is used to only store the latest root.
	ModeLatest TrieMode = 0x01
	// ModeGCFlag is a flag for GC.
	ModeGCFlag TrieMode = 0x02
	// ModeGC is used to store a set of roots with GC possible, it combines
	// GCFlag and Latest (because it needs RC, but it has GC enabled).
	ModeGC TrieMode = 0x03
)

TrieMode is the storage mode of trie.

func (TrieMode) GC added in v0.98.2 

func (m TrieMode) GC() bool

GC returns true when garbage collection is enabled.

func (TrieMode) RC added in v0.98.2 

func (m TrieMode) RC() bool

RC returns true when reference counting is enabled.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.