mpt

package
v0.95.4 Latest Latest
Warning

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

 Go to latest Published: Jul 9, 2021 License: MIT Imports: 11 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.

Functions

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
	EncodeBinaryAsChild(w *io.BinWriter)
}

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 (*Batch) Add added in v0.93.0 

func (b *Batch) Add(key []byte, value []byte)

Add adds key-value pair to batch. If there is an item with the specified key, it is replaced.

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) 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) EncodeBinaryAsChild added in v0.94.1 

func (b *BranchNode) EncodeBinaryAsChild(w *io.BinWriter)

EncodeBinaryAsChild implements BaseNode interface.

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) 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 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) 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) EncodeBinaryAsChild added in v0.94.1 

func (e *ExtensionNode) EncodeBinaryAsChild(w *io.BinWriter)

EncodeBinaryAsChild implements BaseNode interface.

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

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) 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) EncodeBinaryAsChild added in v0.94.1 

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

EncodeBinaryAsChild implements BaseNode interface.

func (*HashNode) Hash 

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

Hash implements Node interface.

func (*HashNode) IsEmpty 

func (h *HashNode) IsEmpty() bool

IsEmpty returns true if h is an empty node i.e. contains no hash.

func (*HashNode) MarshalJSON 

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

MarshalJSON implements json.Marshaler.

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) 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) EncodeBinaryAsChild added in v0.94.1 

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

EncodeBinaryAsChild implements BaseNode interface.

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

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

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.