mpt

package module
v0.0.0-...-21b1c8f Latest Latest
Warning

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

 Go to latest Published: May 23, 2021 License: MIT Imports: 8 Imported by: 0

README

merkle-patricia-trie

MPT in Go

What is merkle-patricia-trie

Merkle trees and Patricia tries can be used in combination to create data structures in different ways depending on the aspect a protocol needs to optimize, such as speed,memory-efficiency, or code simplicity. A particularly interesting combination example is the MPT (merkle patricia trie) found in the Ethereum protocol. MPT also forms the basis of the architecture for the Hyperledger Indy distributed ledger.

All MPT nodes have a hash value called a key. Key-values are paths on the MPT just like the Radix tree image example.

a radix tree example

MPT offers a cryptographically authenticated data structure that can be used to store key-value bindings in a fully deterministic way. This means that when you are provided with the same starting information, you will get the exact same trie with a O(log(n)) efficiency.

Ref

Ethereum white paper Merkle Patricia Trie(1) Merkle Patricia Trie(2)

Documentation

Index

Constants

View Source 
const EthereumRootHash = "56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421"

Variables

View Source 
var (
	EmptyNodeRaw     = []byte{}
	EmptyNodeHash, _ = hex.DecodeString(EthereumRootHash)
)

Functions

func Hash 

func Hash(node Node) []byte

func IsEmptyNode 

func IsEmptyNode(node Node) bool

func IsNibble 

func IsNibble(nibble byte) bool

func Keccak256 

func Keccak256(data ...[]byte) []byte

Keccak256 calculates and returns the Keccak256 hash of the input data.

func PrefixMatchedLen 

func PrefixMatchedLen(node1 []Nibble, node2 []Nibble) int

[0,1,2,3], [0,1,2] => 3 [0,1,2,3], [0,1,2,3] => 4 [0,1,2,3], [0,1,2,3,4] => 4

func Serialize 

func Serialize(node Node) []byte

func ToBytes 

func ToBytes(ns []Nibble) []byte

ToBytes converts a slice of nibbles to a byte slice assuming the nibble slice has even number of nibbles.

func VerifyProof 

func VerifyProof(rootHash []byte, key []byte, proof Proof) (value []byte, err error)

VerifyProof verify the proof for the given key under the given root hash using go-ethereum's VerifyProof implementation. It returns the value for the key if the proof is valid, otherwise error will be returned

Types

type BranchNode 

type BranchNode struct {
	Branches [16]Node
	Value    []byte
}

BranchNode each node can have up to 16 branches

func NewBranchNode 

func NewBranchNode() *BranchNode

func (BranchNode) HasValue 

func (b BranchNode) HasValue() bool

func (BranchNode) Hash 

func (b BranchNode) Hash() []byte

func (BranchNode) Raw 

func (b BranchNode) Raw() []interface{}

func (*BranchNode) RemoveBranch 

func (b *BranchNode) RemoveBranch(nibble Nibble)

func (*BranchNode) RemoveValue 

func (b *BranchNode) RemoveValue()

func (BranchNode) Serialize 

func (b BranchNode) Serialize() []byte

func (*BranchNode) SetBranch 

func (b *BranchNode) SetBranch(nibble Nibble, node Node)

func (*BranchNode) SetValue 

func (b *BranchNode) SetValue(value []byte)

type ExtensionNode 

type ExtensionNode struct {
	Path []Nibble
	Next Node
}

In the MPT, there is one more type of nodes apart from the branch nodes and the leaf nodes. They are extension nodes. An extension node is an optimized node of the branch node. In the Ethereum state, quite frequently, there are branch nodes that have only one child node. This is the reason why the MPT compresses branch nodes that contain only one child into extension nodes that have a path and the hash of the child.

func NewExtensionNode 

func NewExtensionNode(nibbles []Nibble, next Node) *ExtensionNode

func (ExtensionNode) Hash 

func (e ExtensionNode) Hash() []byte

func (ExtensionNode) Raw 

func (e ExtensionNode) Raw() []interface{}

func (ExtensionNode) Serialize 

func (e ExtensionNode) Serialize() []byte

type LeafNode 

type LeafNode struct {
	Path  []Nibble
	Value []byte
}

func NewLeafNodeFromBytes 

func NewLeafNodeFromBytes(key, value []byte) *LeafNode

func NewLeafNodeFromKeyValue 

func NewLeafNodeFromKeyValue(key, value string) *LeafNode

func NewLeafNodeFromNibbleBytes 

func NewLeafNodeFromNibbleBytes(nibbles []byte, value []byte) (*LeafNode, error)

func NewLeafNodeFromNibbles 

func NewLeafNodeFromNibbles(nibbles []Nibble, value []byte) *LeafNode

func (LeafNode) Hash 

func (l LeafNode) Hash() []byte

func (LeafNode) Raw 

func (l LeafNode) Raw() []interface{}

func (LeafNode) Serialize 

func (l LeafNode) Serialize() []byte

type Nibble 

type Nibble byte

1 nibble == 4 bit == 0.5 byte

func FromByte 

func FromByte(b byte) []Nibble

func FromBytes 

func FromBytes(bs []byte) []Nibble

func FromNibbleByte 

func FromNibbleByte(n byte) (Nibble, error)

func FromNibbleBytes 

func FromNibbleBytes(nibbles []byte) ([]Nibble, error)

nibbles contain one nibble per byte

func FromString 

func FromString(s string) []Nibble

func ToPrefixed 

func ToPrefixed(ns []Nibble, isLeafNode bool) []Nibble

ToPrefixed add nibble prefix to a slice of nibbles to make its length even the prefix indicts whether a node is a leaf node.

type Node 

type Node interface {
	Hash() []byte
	Raw() []interface{}
}

Key-values of the Ethereum state are used as paths on the MPT. Nibble is the unit used to distinguish key values in the MPT, so each node can have up to 16 branches. Additionally, since a node has its own value, a branch node is an array of 17 items composed of 1 node value and 16 branches.

type Proof 

type Proof interface {
	// Put inserts the given value into the key-value data store.
	Put(key []byte, value []byte) error

	// Delete removes the key from the key-value data store.
	Delete(key []byte) error

	// Has retrieves if a key is present in the key-value data store.
	Has(key []byte) (bool, error)

	// Get retrieves the given key if it's present in the key-value data store.
	Get(key []byte) ([]byte, error)
}

type ProofDB 

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

func NewProofDB 

func NewProofDB() *ProofDB

func (*ProofDB) Delete 

func (w *ProofDB) Delete(key []byte) error

func (*ProofDB) Get 

func (w *ProofDB) Get(key []byte) ([]byte, error)

func (*ProofDB) Has 

func (w *ProofDB) Has(key []byte) (bool, error)

func (*ProofDB) Put 

func (w *ProofDB) Put(key []byte, value []byte) error

type Transaction 

type Transaction struct {
	AccountNonce uint64          `json:"nonce"    `
	Price        *big.Int        `json:"gasPrice" `
	GasLimit     uint64          `json:"gas"      `
	Recipient    *common.Address `json:"to"       `
	Amount       *big.Int        `json:"value"    `
	Payload      []byte          `json:"input"    `

	// Signature values
	V *big.Int `json:"v" `
	R *big.Int `json:"r" `
	S *big.Int `json:"s" `
}

func (Transaction) GetRLP 

func (t Transaction) GetRLP() ([]byte, error)

type Trie 

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

func NewTrie 

func NewTrie() *Trie

func (*Trie) Get 

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

func (*Trie) Hash 

func (t *Trie) Hash() []byte

func (*Trie) Prove 

func (t *Trie) Prove(key []byte) (Proof, bool)

Prove returns the merkle proof for the given key, which is

func (*Trie) Put 

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

Put adds a key value pair to the trie In general, the rule is: - When stopped at an EmptyNode, replace it with a new LeafNode with the remaining path. - When stopped at a LeafNode, convert it to an ExtensionNode and add a new branch and a new LeafNode. - When stopped at an ExtensionNode, convert it to another ExtensionNode with shorter path and create a new BranchNode points to the ExtensionNode.

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.