trie

package
v0.5.0-alpha.6 Latest Latest
Warning

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

 Go to latest Published: Feb 15, 2023 License: Apache-2.0 Imports: 14 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 (
	// 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")
	ErrNotAllBytesConsumed = errors.New("serialization error: not all bytes were consumed")
)

Functions

func CopyAll 

func CopyAll(dst KVWriter, src KVIterator)

CopyAll flushes KVIterator to KVWriter. It is up to the iterator correctly stop iterating

Types

type BinaryStreamFileIterator 

type BinaryStreamFileIterator struct {
	*BinaryStreamIterator
	// contains filtered or unexported fields
}

func OpenKVStreamFile 

func OpenKVStreamFile(fname string) (*BinaryStreamFileIterator, error)

OpenKVStreamFile opens existing file with key/value stream for reading

func (*BinaryStreamFileIterator) Close 

func (fs *BinaryStreamFileIterator) Close() error

type BinaryStreamFileWriter 

type BinaryStreamFileWriter struct {
	*BinaryStreamWriter
	// contains filtered or unexported fields
}

func CreateKVStreamFile 

func CreateKVStreamFile(fname string) (*BinaryStreamFileWriter, error)

CreateKVStreamFile create a new BinaryStreamFileWriter

func (*BinaryStreamFileWriter) Close 

func (fw *BinaryStreamFileWriter) Close() error

type BinaryStreamIterator 

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

func NewBinaryStreamIterator 

func NewBinaryStreamIterator(r io.Reader) *BinaryStreamIterator

func (BinaryStreamIterator) Iterate 

func (b BinaryStreamIterator) Iterate(fun func(k []byte, v []byte) bool) error

type BinaryStreamWriter 

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

func NewBinaryStreamWriter 

func NewBinaryStreamWriter(w io.Writer) *BinaryStreamWriter

func (*BinaryStreamWriter) Stats 

func (b *BinaryStreamWriter) Stats() (int, int)

func (*BinaryStreamWriter) Write 

func (b *BinaryStreamWriter) Write(key, value []byte) error

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

MustInitRoot initializes a new empty trie

func ReadHash 

func ReadHash(r io.Reader) (ret Hash, err error)

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

type InMemoryKVStore map[string][]byte

func NewInMemoryKVStore 

func NewInMemoryKVStore() InMemoryKVStore

func (InMemoryKVStore) Get 

func (im InMemoryKVStore) Get(k []byte) []byte

func (InMemoryKVStore) Has 

func (im InMemoryKVStore) Has(k []byte) bool

func (InMemoryKVStore) Iterate 

func (im InMemoryKVStore) Iterate(f func(k []byte, v []byte) bool)

func (InMemoryKVStore) IterateKeys 

func (im InMemoryKVStore) IterateKeys(f func(k []byte) bool)

func (InMemoryKVStore) Iterator 

func (im InMemoryKVStore) Iterator(prefix []byte) KVIterator

func (InMemoryKVStore) Set 

func (im InMemoryKVStore) Set(k, v []byte)

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 KVStreamIterator 

type KVStreamIterator interface {
	Iterate(func(k, v []byte) bool) error
}

KVStreamIterator is an interface to iterate stream In general, order is non-deterministic

type KVStreamWriter 

type KVStreamWriter interface {
	// Write writes key/value pair
	Write(key, value []byte) error
	// Stats return num k/v pairs and num bytes so far
	Stats() (int, int)
}

KVStreamWriter represents an interface to write a sequence of key/value pairs

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

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 RandStreamIterator 

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

func NewRandStreamIterator 

func NewRandStreamIterator(p ...RandStreamParams) *RandStreamIterator

func (*RandStreamIterator) Iterate 

func (r *RandStreamIterator) Iterate(fun func(k []byte, v []byte) bool) error

type RandStreamParams 

type RandStreamParams struct {
	// Seed for deterministic randomization
	Seed int64
	// NumKVPairs maximum number of key value pairs to generate. 0 means infinite
	NumKVPairs int
	// MaxKey maximum length of key (randomly generated)
	MaxKey int
	// MaxValue maximum length of value (randomly generated)
	MaxValue int
}

RandStreamParams represents parameters of the RandStreamIterator

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, cacheSize ...int) (*TrieReader, error)

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

func (tr *TrieReader) Snapshot(destStore KVWriter)

Snapshot writes the whole trie (including values) from specific root to another store

func (*TrieReader) SnapshotData 

func (tr *TrieReader) SnapshotData(dest KVWriter)

SnapshotData writes all key/value pairs, committed in the specific root, to a store

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, cacheSize ...int) (*TrieUpdatable, error)

func (*TrieUpdatable) Commit 

func (tr *TrieUpdatable) Commit(store KVWriter) Hash

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

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.