mpt

package
v0.76.1 Latest Latest
Warning

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

 Go to latest Published: Jul 15, 2020 License: MIT Imports: 10 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 = 1125

MaxKeyLength is the max length of the extension node key.

View Source 
const MaxValueLength = 1024 * 1024

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 ToNeoStorageKey 

func ToNeoStorageKey(key []byte) []byte

ToNeoStorageKey converts storage key to C# neo node's format. Key is expected to be at least 20 bytes in length. our format: script hash in BE + key neo format: script hash in LE + key with 0 between every 16 bytes, padded to len 16.

func ToNeoStorageValue 

func ToNeoStorageValue(si *state.StorageItem) []byte

ToNeoStorageValue serializes si to a C# neo node's format. It has additional version (0x00) byte at the beginning.

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.

func (*BaseNode) IsFlushed 

func (b *BaseNode) IsFlushed() bool

IsFlushed checks for node flush status.

func (*BaseNode) SetFlushed 

func (b *BaseNode) SetFlushed()

SetFlushed sets 'flushed' flag to true for this node.

type BaseNodeIface 

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

BaseNodeIface abstracts away basic Node functions.

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

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

Hash implements Node interface.

func (*HashNode) IsEmpty 

func (h *HashNode) IsEmpty() bool

IsEmpty returns true iff 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) 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.

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
	HashT      NodeType = 0x02
	LeafT      NodeType = 0x03
)

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