trie

package
v1.0.1-rc.16 Latest Latest
Warning

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

 Go to latest Published: Jan 12, 2024 License: Apache-2.0 Imports: 11 Imported by: 0

Documentation

Overview

package trie implements an immutable Merkle Patricia Trie, used by the state package to store the chain state.

The code is based on the trie.go package by Evaldas Drasutis: https://github.com/iotaledger/trie.go

This is a simplified version, keeping only the features that are relevant for our use case. Namely:

- Arity is fixed at 16 - Hash size is fixed at 20 bytes - Hashing algorithm is blake2b - No mutable trie implementation

This file contains functions for verification of the proofs of inclusion or absence in the trie with trie_blake2b commitment model. The package only depends on the commitment model implementation and the proof format it defines. The verification package is completely independent on the implementation of the Merkle tree (the trie)

DISCLAIMER: THE FOLLOWING CODE IS SECURITY CRITICAL. ANY POTENTIAL BUG WHICH MAY LEAD TO FALSE POSITIVES OF PROOF VALIDITY CHECKS POTENTIALLY CREATES AN ATTACK VECTOR. THEREFORE, IT IS HIGHLY RECOMMENDED THE VERIFICATION CODE TO BE WRITTEN BY THE VERIFYING PARTY ITSELF, INSTEAD OF CLONING THIS PACKAGE. DO NOT TRUST ANYBODY BUT YOURSELF. IN ANY CASE, PERFORM A DETAILED AUDIT OF THE PROOF-VERIFYING CODE BEFORE USING IT

Index

Constants

View Source 
const (
	HashSizeBits  = 160
	HashSizeBytes = HashSizeBits / 8
)
View Source 
const KeyMaxLength = 256
View Source 
const (
	// NumChildren is the maximum amount of children for each trie node
	NumChildren = 16
)

Variables

View Source 
var (
	ErrWrongNibble = errors.New("key16 byte must be less than 0x0F")
	ErrEmpty       = errors.New("encoded key16 can't be empty")
	ErrWrongFormat = errors.New("encoded key16 wrong format")
)

Functions

func DebugDump 

func DebugDump(store KVStore, roots []Hash)

DebugDump prints the structure of the whole DB to stdout, for debugging purposes.

func Diff 

func Diff(store KVStore, root1, root2 Hash) (onlyOn1, onlyOn2 map[Hash]*NodeData)

Diff computes the difference between two given trie roots, returning the collections of nodes that are exclusive to each trie.

func RestoreSnapshot 

func RestoreSnapshot(r io.Reader, store KVStore) error

Types

type CommitStats 

type CommitStats struct {
	CreatedNodes  uint
	CreatedValues uint
}

type Hash 

type Hash [HashSizeBytes]byte

Hash is a blake2b 160 bit (20 bytes) hash

func HashFromBytes 

func HashFromBytes(data []byte) (ret Hash, err error)

func MustInitRoot 

func MustInitRoot(store KVStore) Hash

MustInitRoot initializes a new empty trie

func (Hash) Bytes 

func (h Hash) Bytes() []byte

func (Hash) Clone 

func (h Hash) Clone() (ret Hash)

func (Hash) Equals 

func (h Hash) Equals(other Hash) bool

func (*Hash) Read 

func (h *Hash) Read(r io.Reader) error

func (Hash) String 

func (h Hash) String() string

func (Hash) Write 

func (h Hash) Write(w io.Writer) error

type HiveKVStoreAdapter 

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

HiveKVStoreAdapter maps a partition of the Hive KVStore to trie_go.KVStore

func NewHiveKVStoreAdapter 

func NewHiveKVStoreAdapter(kvs kvstore.KVStore, prefix []byte) *HiveKVStoreAdapter

NewHiveKVStoreAdapter creates a new KVStore as a partition of hive.go KVStore

func (*HiveKVStoreAdapter) Del 

func (kvs *HiveKVStoreAdapter) Del(key []byte)

func (*HiveKVStoreAdapter) Get 

func (kvs *HiveKVStoreAdapter) Get(key []byte) []byte

func (*HiveKVStoreAdapter) Has 

func (kvs *HiveKVStoreAdapter) Has(key []byte) bool

func (*HiveKVStoreAdapter) Iterate 

func (kvs *HiveKVStoreAdapter) Iterate(fun func(k []byte, v []byte) bool)

func (*HiveKVStoreAdapter) IterateKeys 

func (kvs *HiveKVStoreAdapter) IterateKeys(fun func(k []byte) bool)

func (*HiveKVStoreAdapter) Set 

func (kvs *HiveKVStoreAdapter) Set(key, value []byte)

type IterateNodesAction 

type IterateNodesAction byte
const (
	IterateStop IterateNodesAction = iota
	IterateContinue
	IterateSkipSubtree
)

type KVIterator 

type KVIterator interface {
	Iterate(func(k, v []byte) bool)
	IterateKeys(func(k []byte) bool)
}

KVIterator is an interface to iterate through a set of key/value pairs. Order of iteration is NON-DETERMINISTIC in general

type KVReader 

type KVReader interface {
	// Get retrieves value by key. Returned nil means absence of the key
	Get(key []byte) []byte
	// Has checks presence of the key in the key/value store
	Has(key []byte) bool // for performance
}

KVReader is a key/value reader

type KVStore 

type KVStore interface {
	KVReader
	KVWriter
	KVIterator
}

KVStore is a compound interface

type KVWriter 

type KVWriter interface {
	// Set writes new or updates existing key with the value.
	// value == nil means deletion of the key from the store
	Set(key, value []byte)
	Del(key []byte)
}

KVWriter is a key/value writer

type MerkleProof 

type MerkleProof struct {
	Key  []byte
	Path []*MerkleProofElement
}

MerkleProof is a proof of inclusion or absence

func (*MerkleProof) IsProofOfAbsence 

func (p *MerkleProof) IsProofOfAbsence() bool

IsProofOfAbsence checks if it is proof of absence. MerkleProof that the trie commits to something else in the place where it would commit to the key if it would be present

func (*MerkleProof) MustKeyWithTerminal 

func (p *MerkleProof) MustKeyWithTerminal() ([]byte, []byte)

MustKeyWithTerminal returns key and terminal commitment the proof is about. It returns: - key - terminal commitment. If it is nil, the proof is a proof of absence It does not verify the proof, so this function should be used only after Validate()

func (*MerkleProof) Validate 

func (p *MerkleProof) Validate(rootBytes []byte) error

Validate check the proof against the provided root commitments

func (*MerkleProof) ValidateValue 

func (p *MerkleProof) ValidateValue(trieRoot Hash, value []byte) error

func (*MerkleProof) ValidateWithTerminal 

func (p *MerkleProof) ValidateWithTerminal(rootBytes, terminalBytes []byte) error

ValidateWithTerminal checks the proof and checks if the proof commits to the specific value The check is dependent on the commitment model because of valueOptimisationThreshold

type MerkleProofElement 

type MerkleProofElement struct {
	PathExtension []byte
	Children      [NumChildren]*Hash
	Terminal      []byte
	ChildIndex    int
}

type NodeData 

type NodeData struct {
	// if PathExtension != nil, this is an extension node (i.e. if there are
	// no branching nodes along the PathExtension).
	// See https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/#optimization
	PathExtension []byte

	// if Terminal != nil, it contains the commitment to a value in the trie
	Terminal *Tcommitment

	// Children contains pointers to up to 16 other nodes, one for each
	// possible nibble
	Children [NumChildren]*Hash

	// Commitment is hash(pathExtension|terminal|children), which is persisted in the key
	Commitment Hash
}

NodeData represents a node of the trie, which is stored in the trieStore with key = commitment.Bytes()

func (*NodeData) Bytes 

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

func (*NodeData) ChildrenCount 

func (n *NodeData) ChildrenCount() int

func (*NodeData) Clone 

func (n *NodeData) Clone() *NodeData

Clone deep copy

func (*NodeData) Read 

func (n *NodeData) Read(r io.Reader) error

func (*NodeData) String 

func (n *NodeData) String() string

func (*NodeData) Write 

func (n *NodeData) Write(w io.Writer) error

type PruneStats 

type PruneStats struct {
	DeletedNodes  uint
	DeletedValues uint
}

func Prune 

func Prune(store KVStore, trieRoot Hash) (PruneStats, error)

type Refcounts 

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

func (*Refcounts) DebugDump 

func (r *Refcounts) DebugDump()

func (*Refcounts) Dec 

func (r *Refcounts) Dec(node *NodeData) (deleteNode, deleteValue bool)

func (*Refcounts) GetNode 

func (r *Refcounts) GetNode(commitment Hash) uint32

func (*Refcounts) Inc 

func (r *Refcounts) Inc(node *bufferedNode) (uint32, uint32)

type Tcommitment 

type Tcommitment struct {
	Data    []byte
	IsValue bool
}

Tcommitment (short for terminal commitment) commits to data of arbitrary size.

func CommitToData 

func CommitToData(data []byte) *Tcommitment

func (*Tcommitment) Bytes 

func (t *Tcommitment) Bytes() []byte

func (*Tcommitment) Clone 

func (t *Tcommitment) Clone() *Tcommitment

func (*Tcommitment) Equals 

func (t *Tcommitment) Equals(o *Tcommitment) bool

func (*Tcommitment) ExtractValue 

func (t *Tcommitment) ExtractValue() ([]byte, bool)

func (*Tcommitment) Read 

func (t *Tcommitment) Read(r io.Reader) error

func (*Tcommitment) String 

func (t *Tcommitment) String() string

func (*Tcommitment) Write 

func (t *Tcommitment) Write(w io.Writer) error

type Traversable 

type Traversable interface {
	Iterator(prefix []byte) KVIterator
}

Traversable is an interface which provides with partial iterators

type TrieIterator 

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

TrieIterator implements KVIterator interface for keys in the trie with given prefix

func (*TrieIterator) Iterate 

func (ti *TrieIterator) Iterate(fun func(k []byte, v []byte) bool)

func (*TrieIterator) IterateKeys 

func (ti *TrieIterator) IterateKeys(fun func(k []byte) bool)

type TrieReader 

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

TrieReader direct read-only access to trie

func NewTrieReader 

func NewTrieReader(store KVReader, root Hash) (*TrieReader, error)

func (*TrieReader) DebugDump 

func (tr *TrieReader) DebugDump()

DebugDump prints the structure of the tree to stdout, for debugging purposes.

func (*TrieReader) Get 

func (tr *TrieReader) Get(key []byte) []byte

Get reads the trie with the key

func (*TrieReader) GetStr 

func (tr *TrieReader) GetStr(key string) string

func (*TrieReader) Has 

func (tr *TrieReader) Has(key []byte) bool

Has check existence of the key in the trie

func (*TrieReader) HasStr 

func (tr *TrieReader) HasStr(key string) bool

func (*TrieReader) Iterate 

func (tr *TrieReader) Iterate(f func(k []byte, v []byte) bool)

Iterate iterates all the key/value pairs in the trie

func (*TrieReader) IterateKeys 

func (tr *TrieReader) IterateKeys(f func(k []byte) bool)

IterateKeys iterates all the keys in the trie

func (*TrieReader) IterateNodes 

func (tr *TrieReader) IterateNodes(fun func(nodeKey []byte, n *NodeData, depth int) IterateNodesAction)

IterateNodes iterates nodes of the trie in the lexicographical order of trie keys in "depth first" order

func (*TrieReader) Iterator 

func (tr *TrieReader) Iterator(prefix []byte) KVIterator

Iterator returns iterator for the sub-trie

func (*TrieReader) MerkleProof 

func (tr *TrieReader) MerkleProof(key []byte) *MerkleProof

func (*TrieReader) Root 

func (tr *TrieReader) Root() Hash

func (*TrieReader) TakeSnapshot 

func (tr *TrieReader) TakeSnapshot(w io.Writer) error

type TrieUpdatable 

type TrieUpdatable struct {
	*TrieReader
	// contains filtered or unexported fields
}

TrieUpdatable is an updatable trie implemented on top of the unpackedKey/value store. It is virtualized and optimized by caching of the trie update operation and keeping consistent trie in the cache

func NewTrieUpdatable 

func NewTrieUpdatable(store KVReader, root Hash) (*TrieUpdatable, error)

func (*TrieUpdatable) Commit 

func (tr *TrieUpdatable) Commit(store KVStore) (Hash, CommitStats)

Commit calculates a new mutatedRoot commitment value from the cache, commits all mutations and writes it into the store. The nodes and values are written into separate partitions The buffered nodes are garbage collected, except the mutated ones By default, it sets new root in the end and clears the trie reader cache. To override, use notSetNewRoot = true

func (*TrieUpdatable) Delete 

func (tr *TrieUpdatable) Delete(key []byte)

Delete deletes Key/value from the TrieUpdatable

func (*TrieUpdatable) DeletePrefix 

func (tr *TrieUpdatable) DeletePrefix(pathPrefix []byte) bool

DeletePrefix deletes all kv pairs with the prefix. It is a very fast operation, it modifies only one node and all children (any number) disappears from the next root

func (*TrieUpdatable) DeleteStr 

func (tr *TrieUpdatable) DeleteStr(key interface{})

DeleteStr removes key from trie

func (*TrieUpdatable) SetRoot 

func (tr *TrieUpdatable) SetRoot(h Hash) error

SetRoot overloaded for updatable trie

func (*TrieUpdatable) Update 

func (tr *TrieUpdatable) Update(key []byte, value []byte)

Update updates TrieUpdatable with the unpackedKey/value. Reorganizes and re-calculates trie, keeps cache consistent

func (*TrieUpdatable) UpdateStr 

func (tr *TrieUpdatable) UpdateStr(key interface{}, value interface{})

UpdateStr updates key/value pair in the trie

Source Files

View all Source files

Directories

Path Synopsis

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.