mpt

package
v0.107.2 Latest Latest
Warning

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

 Go to latest Published: Dec 13, 2024 License: MIT Imports: 12 Imported by: 0

Documentation

Overview

Package mpt implements MPT (Merkle-Patricia Trie).

An MPT stores key-value pairs and is a trie over 16-symbol alphabet. https://en.wikipedia.org/wiki/Trie A trie is a tree where values are stored in leafs and keys are paths from the root to the leaf node. An MPT consists of 4 types of nodes:

  • Leaf node only contains a value.
  • Extension node contains both a key and a value.
  • Branch node contains 2 or more children.
  • Hash node is a compressed node and only contains the actual node's hash. The actual node must be retrieved from the 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 a zero-length key - Extension node cannot have another Extension node in its next field

Thanks to these restrictions, there is a single root hash for every set of key-value pairs irregardless of the order they were added/removed in. 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 quite beneficial: When we perform get/put/delete on a specific path, every Hash node which was retrieved from the storage is replaced by its uncompressed form, so that subsequent hits of this don't need to access the storage.

Index

Constants

View Source 
const (

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

MaxValueLength is the max length of a leaf node value.

Variables

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

ErrNotFound is returned when the 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 the 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 the 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 a 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 an 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 an 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 the MPT structure during restore, thus don't need to decrease refcount).
  2. Each time a part of a Billet is completely restored, it is collapsed into HashNode.
  3. Any pair (node, path) must be restored only once. It's a duty of an 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 a 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. Another benefit is 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 the MPT as small as possible by collapsing those parts of the 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 an MPT's branch node.

func NewBranchNode 

func NewBranchNode() *BranchNode

NewBranchNode returns a new branch node.

func (*BranchNode) Bytes 

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

Bytes implements the 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 the BaseNode interface.

func (*BranchNode) MarshalJSON 

func (b *BranchNode) MarshalJSON() ([]byte, error)

MarshalJSON implements the json.Marshaler.

func (*BranchNode) Size added in v0.97.2 

func (b *BranchNode) Size() int

Size implements the Node interface.

func (*BranchNode) Type 

func (b *BranchNode) Type() NodeType

Type implements the Node interface.

func (*BranchNode) UnmarshalJSON 

func (b *BranchNode) UnmarshalJSON(data []byte) error

UnmarshalJSON implements the json.Unmarshaler.

type EmptyNode added in v0.97.2 

type EmptyNode struct{}

EmptyNode represents an 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 the io.Serializable interface.

func (EmptyNode) EncodeBinary added in v0.97.2 

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

EncodeBinary implements the 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 an MPT's extension node.

func NewExtensionNode 

func NewExtensionNode(key []byte, next Node) *ExtensionNode

NewExtensionNode returns a hash node with the specified key and the next node. Note: since it is a part of a Trie, the 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 the 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 the json.Unmarshaler.

type HashNode 

type HashNode struct {
	BaseNode
	Collapsed bool
}

HashNode represents an MPT's hash node.

func NewHashNode 

func NewHashNode(h util.Uint256) *HashNode

NewHashNode returns a 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 the 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 the json.Unmarshaler.

type LeafNode 

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

LeafNode represents an MPT's leaf node.

func NewLeafNode 

func NewLeafNode(value []byte) *LeafNode

NewLeafNode returns a 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 the 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 the json.Unmarshaler.

type Node 

type Node interface {
	io.Serializable
	json.Marshaler
	json.Unmarshaler
	Size() int
	Clone() Node
	BaseNodeIface
}

Node represents a common interface of all MPT nodes.

func DecodeNodeWithType added in v0.78.2 

func DecodeNodeWithType(r *io.BinReader) Node

DecodeNodeWithType decodes the node together with its type.

type NodeObject 

type NodeObject struct {
	Node
}

NodeObject represents a 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 the json.Unmarshaler.

type NodeType 

type NodeType byte

NodeType represents a 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 a 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. Another benefit is 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 the key from the trie. It returns no error on a missing key.

func (*Trie) Find added in v0.97.3 

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

Find returns a 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 `maxNum` number of elements is returned at max.

func (*Trie) Flush 

func (t *Trie) Flush(index uint32)

Flush puts every node (except Hash ones) in the trie to the storage. Because we care about block-level changes only, there is no need to put every new node to the 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 the value for the provided key in t.

func (*Trie) GetProof 

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

GetProof returns a proof that the key belongs to t. The proof consists of serialized nodes occurring on the 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 a batch to a trie. It is not atomic (and probably cannot be without substantial slow-down) and returns the 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 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 a 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 a 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.

type TrieStore added in v0.99.0 

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

TrieStore is an MPT-based storage implementation for storing and retrieving historic blockchain data. TrieStore is supposed to be used within transaction script invocations only, thus only contract storage related operations are supported. All storage-related operations are being performed using historical storage data retrieved from MPT state. TrieStore is read-only and does not support put-related operations, thus, it should always be wrapped into MemCachedStore for proper puts handling. TrieStore never changes the provided backend store.

func NewTrieStore added in v0.99.0 

func NewTrieStore(root util.Uint256, mode TrieMode, backed storage.Store) *TrieStore

NewTrieStore returns a new ready to use MPT-backed storage.

func (*TrieStore) Close added in v0.99.0 

func (m *TrieStore) Close() error

Close implements the Store interface.

func (*TrieStore) Get added in v0.99.0 

func (m *TrieStore) Get(key []byte) ([]byte, error)

Get implements the Store interface. It can return errors.ErrUnsupported for unsupported operations.

func (*TrieStore) PutChangeSet added in v0.99.0 

func (m *TrieStore) PutChangeSet(puts map[string][]byte, stor map[string][]byte) error

PutChangeSet implements the Store interface. It's not supported, so it always returns errors.ErrUnsupported.

func (*TrieStore) Seek added in v0.99.0 

func (m *TrieStore) Seek(rng storage.SeekRange, f func(k, v []byte) bool)

Seek implements the Store interface.

func (*TrieStore) SeekGC added in v0.99.0 

func (m *TrieStore) SeekGC(rng storage.SeekRange, keep func(k, v []byte) bool) error

SeekGC implements the Store interface. It's not supported, so it always returns errors.ErrUnsupported.

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.