trie

package
v0.0.0-...-92d349b Latest Latest
Warning

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

 Go to latest Published: Dec 15, 2023 License: GPL-3.0 Imports: 30 Imported by: 0

Documentation

Overview

Package trie implements Merkle Patricia Tries.

Visualisation of Merkle Patricia Tries.

Index

Constants

View Source 
const (
	AccountFieldNonceOnly     uint32 = 0x01
	AccountFieldBalanceOnly   uint32 = 0x02
	AccountFieldStorageOnly   uint32 = 0x04
	AccountFieldCodeOnly      uint32 = 0x08
	AccountFieldSSizeOnly     uint32 = 0x10
	AccountFieldSetNotAccount uint32 = 0x00
)

Various values of the account field set

View Source 
const (
	ColumnStructure  = StatsColumn("structure")
	ColumnHashes     = StatsColumn("hashes")
	ColumnCodes      = StatsColumn("codes")
	ColumnLeafKeys   = StatsColumn("leaf_keys")
	ColumnLeafValues = StatsColumn("leaf_values")
	ColumnTotal      = StatsColumn("total_witness_size")
)
View Source 
const WitnessVersion = uint8(1)

WitnessVersion represents the current version of the block witness in case of incompatible changes it should be updated and the code to migrate the old witness format should be present

Variables

View Source 
var EmptyCodeHash = crypto.Keccak256Hash(nil)
View Source 
var (
	// EmptyRoot is the known root hash of an empty trie.
	// DESCRIBED: docs/programmers_guide/guide.md#root
	EmptyRoot = libcommon.HexToHash("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421")
)

Functions

func AddrHashFromCodeKey 

func AddrHashFromCodeKey(codeKey []byte) []byte

func CalcRoot 

func CalcRoot(logPrefix string, tx kv.Tx) (libcommon.Hash, error)

CalcRoot is a combination of `ResolveStateTrie` and `UpdateStateTrie` DESCRIBED: docs/programmers_guide/guide.md#organising-ethereum-state-into-a-merkle-tree

func CastTrieNodeValue 

func CastTrieNodeValue(hashes, rootHash []byte) []libcommon.Hash

func CodeHexFromHex 

func CodeHexFromHex(hex []byte) []byte

func CodeKeyFromAddrHash 

func CodeKeyFromAddrHash(addrHash []byte) []byte

func EncodeAsValue 

func EncodeAsValue(data []byte) ([]byte, error)

func FullKeys 

func FullKeys(t *Trie) []string

FullKeys construct the list of full keys (i.e. keys that can be accessed without resolution via DB) that are present in the given trie

func FullNode1 

func FullNode1()

func FullNode2 

func FullNode2()

func FullNode3 

func FullNode3()

func FullNode4 

func FullNode4()

func GenStructStep 

func GenStructStep(
	retain func(prefix []byte) bool,
	curr, succ []byte,
	e structInfoReceiver,
	h HashCollector2,
	data GenStructStepData,
	groups []uint16,
	hasTree []uint16,
	hasHash []uint16,
	trace bool,
) ([]uint16, []uint16, []uint16, error)

func GenStructStepEx 

func GenStructStepEx(
	retain func(prefix []byte) bool,
	curr, succ []byte,
	e structInfoReceiver,
	h HashCollector2,
	data GenStructStepData,
	groups []uint16,
	hasTree []uint16,
	hasHash []uint16,
	trace bool,
	retainProof func(prefix []byte) *proofElement,
	cutoff bool,
) ([]uint16, []uint16, []uint16, error)

GenStructStepEx is extended to support optional generation of an Account Proof during trie_root.go CalcTrieRoot(). The wrapper below calls it with nil/false defaults so that other callers do not need to be modified.

func GenStructStepOld 

func GenStructStepOld(
	retain func(prefix []byte) bool,
	curr, succ []byte,
	e structInfoReceiver,
	h HashCollector,
	data GenStructStepData,
	groups []uint16,
	trace bool,
) ([]uint16, error)

func Hash1 

func Hash1()

func Hash2 

func Hash2()

func Hash3 

func Hash3()

func Hash4 

func Hash4()

func Hash5 

func Hash5()

func Hash6 

func Hash6()

func Hash7 

func Hash7()

func HashWithModifications 

func HashWithModifications(
	t *Trie,
	aKeys common.Hashes, aValues []*accounts.Account, aCodes [][]byte,
	sKeys common.StorageKeys, sValues [][]byte,
	storagePrefixLen int,
	newStream *Stream,
	hb *HashBuilder,
	trace bool,
) (libcommon.Hash, error)

HashWithModifications computes the hash of the would-be modified trie, but without any modifications

func IsPointingToCode 

func IsPointingToCode(key []byte) bool

func KeyToQuad 

func KeyToQuad(key []byte) []byte

KeyToQuad converts a key in KEY encoding to QUAD encoding (similar to HEX encoding, but uses digits 0..3 instead of digits 0..15)

func MarshalTrieNode 

func MarshalTrieNode(hasState, hasTree, hasHash uint16, hashes, rootHash []byte, buf []byte) []byte

func MarshalTrieNodeTyped 

func MarshalTrieNodeTyped(hasState, hasTree, hasHash uint16, h []libcommon.Hash, buf []byte) []byte

func NewShortNode 

func NewShortNode(key []byte, value node) *shortNode

func ShortNode1 

func ShortNode1()

func ShortNode2 

func ShortNode2()

func StarkStats 

func StarkStats(witness *Witness, w io.Writer, trace bool) error

StarkStats collects Keccak256 stats from the witness and write them into the file

func StorageKey 

func StorageKey(addressHash []byte, incarnation uint64, prefix []byte) []byte

func StreamHash 

func StreamHash(it *StreamMergeIterator, storagePrefixLen int, hb *HashBuilder, trace bool) (libcommon.Hash, error)

StreamHash computes the hash of a stream, as if it was a trie

func UnmarshalTrieNode 

func UnmarshalTrieNode(v []byte) (hasState, hasTree, hasHash uint16, hashes, rootHash []byte)

func UnmarshalTrieNodeTyped 

func UnmarshalTrieNodeTyped(v []byte) (hasState, hasTree, hasHash uint16, hashes []libcommon.Hash, rootHash libcommon.Hash)

func Visual 

func Visual(t *Trie, w io.Writer, opts *VisualOpts)

Visual creates visualisation of trie with highlighting

Types

type AccTrieCursor 

type AccTrieCursor struct {
	SkipState bool
	// contains filtered or unexported fields
}

AccTrieCursor - holds logic related to iteration over AccTrie bucket has 2 basic operations: _preOrderTraversalStep and _preOrderTraversalStepNoInDepth

func AccTrie 

func AccTrie(canUse func([]byte) (bool, []byte), hc HashCollector2, c kv.Cursor, quit <-chan struct{}) *AccTrieCursor

func (*AccTrieCursor) AtPrefix 

func (c *AccTrieCursor) AtPrefix(prefix []byte) (k, v []byte, hasTree bool, err error)

func (*AccTrieCursor) FirstNotCoveredPrefix 

func (c *AccTrieCursor) FirstNotCoveredPrefix() []byte

func (*AccTrieCursor) Next 

func (c *AccTrieCursor) Next() (k, v []byte, hasTree bool, err error)

type BlockWitnessStats 

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

func (*BlockWitnessStats) BlockWitnessSize 

func (s *BlockWitnessStats) BlockWitnessSize() uint64

func (*BlockWitnessStats) CodesSize 

func (s *BlockWitnessStats) CodesSize() uint64

func (*BlockWitnessStats) HashesSize 

func (s *BlockWitnessStats) HashesSize() uint64

func (*BlockWitnessStats) LeafKeysSize 

func (s *BlockWitnessStats) LeafKeysSize() uint64

func (*BlockWitnessStats) LeafValuesSize 

func (s *BlockWitnessStats) LeafValuesSize() uint64

func (*BlockWitnessStats) StructureSize 

func (s *BlockWitnessStats) StructureSize() uint64

type ByteArrayWriter 

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

func (*ByteArrayWriter) Setup 

func (w *ByteArrayWriter) Setup(dest []byte, pos int)

func (*ByteArrayWriter) Write 

func (w *ByteArrayWriter) Write(data []byte) (int, error)

type FlatDBTrieLoader 

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

FlatDBTrieLoader reads state and intermediate trie hashes in order equal to "Preorder trie traversal" (Preorder - visit Root, visit Left, visit Right)

It produces stream of values and send this stream to `receiver` It skips storage with incorrect incarnations

Each intermediate hash key firstly pass to RetainDecider, only if it returns "false" - such AccTrie can be used.

func NewFlatDBTrieLoader 

func NewFlatDBTrieLoader(logPrefix string, rd RetainDeciderWithMarker, hc HashCollector2, shc StorageHashCollector2, trace bool) *FlatDBTrieLoader

func (*FlatDBTrieLoader) CalcTrieRoot 

func (l *FlatDBTrieLoader) CalcTrieRoot(tx kv.Tx, quit <-chan struct{}) (libcommon.Hash, error)

CalcTrieRoot algo: 

	for iterateIHOfAccounts {
		if canSkipState
         goto SkipAccounts

		for iterateAccounts from prevIH to currentIH {
			use(account)
			for iterateIHOfStorage within accountWithIncarnation{
				if canSkipState
					goto SkipStorage

				for iterateStorage from prevIHOfStorage to currentIHOfStorage {
					use(storage)
				}
           SkipStorage:
				use(ihStorage)
			}
		}
   SkipAccounts:
		use(AccTrie)
	}

func (*FlatDBTrieLoader) SetProofRetainer 

func (l *FlatDBTrieLoader) SetProofRetainer(pr *ProofRetainer)

type GenStructStepAccountData 

type GenStructStepAccountData struct {
	FieldSet    uint32
	Balance     uint256.Int
	Nonce       uint64
	Incarnation uint64
}

func (GenStructStepAccountData) GenStructStepData 

func (GenStructStepAccountData) GenStructStepData()

type GenStructStepData 

type GenStructStepData interface {
	GenStructStepData()
}

type GenStructStepHashData 

type GenStructStepHashData struct {
	Hash    libcommon.Hash
	HasTree bool
}

func (GenStructStepHashData) GenStructStepData 

func (GenStructStepHashData) GenStructStepData()

type GenStructStepLeafData 

type GenStructStepLeafData struct {
	Value rlphacks.RlpSerializable
}

func (GenStructStepLeafData) GenStructStepData 

func (GenStructStepLeafData) GenStructStepData()

type HashBuilder 

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

HashBuilder implements the interface `structInfoReceiver` and opcodes that the structural information of the trie is comprised of DESCRIBED: docs/programmers_guide/guide.md#separation-of-keys-and-the-structure

func NewHashBuilder 

func NewHashBuilder(trace bool) *HashBuilder

NewHashBuilder creates a new HashBuilder

func (*HashBuilder) Reset 

func (hb *HashBuilder) Reset()

Reset makes the HashBuilder suitable for reuse

func (*HashBuilder) RootHash 

func (hb *HashBuilder) RootHash() (libcommon.Hash, error)

type HashCollector 

type HashCollector func(keyHex []byte, hash []byte) error

hashCollector gets called whenever there might be a need to create intermediate hash record

type HashCollector2 

type HashCollector2 func(keyHex []byte, hasState, hasTree, hasHash uint16, hashes, rootHash []byte) error

type HashNodeFunc 

type HashNodeFunc func(node, bool, []byte) (int, error)

type HexStdOutWriter 

type HexStdOutWriter struct{}

func (*HexStdOutWriter) Write 

func (*HexStdOutWriter) Write(p []byte) (n int, err error)

type Iterator 

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

Iterator helps iterate over a trie according to a given resolve set

func NewIterator 

func NewIterator(t *Trie, rl *RetainList, trace bool) *Iterator

NewIterator creates a new iterator from scratch from a given trie and resolve set

func (*Iterator) Next 

func (it *Iterator) Next() (itemType StreamItem, hex1 []byte, aValue *accounts.Account, hash []byte, value []byte)

Next delivers the next item from the iterator

func (*Iterator) Reset 

func (it *Iterator) Reset(t *Trie, rl *RetainList, trace bool)

Reset prepares iterator to be reused

type Keybytes 

type Keybytes struct {
	Data        []byte
	Odd         bool
	Terminating bool
}

Keybytes represent a packed encoding of hex sequences where 2 nibbles per byte are stored in Data + an additional flag for terminating nodes.

func CompactToKeybytes 

func CompactToKeybytes(c []byte) Keybytes

CompactToKeybytes translates from COMPACT to KEYBYTES encoding.

func (*Keybytes) DecodeRLP 

func (x *Keybytes) DecodeRLP(s *rlp.Stream) error

DecodeRLP implements rlp.Decoder and decodes Keybytes from the COMPACT encoding.

func (*Keybytes) EncodeRLP 

func (x *Keybytes) EncodeRLP(w io.Writer) error

EncodeRLP implements rlp.Encoder and encodes Keybytes in the COMPACT encoding.

func (*Keybytes) Nibbles 

func (x *Keybytes) Nibbles() int

Nibbles returns the number of nibbles.

func (*Keybytes) ToCompact 

func (x *Keybytes) ToCompact() []byte

ToCompact translates from KEYBYTES to COMPACT encoding.

func (*Keybytes) ToHex 

func (x *Keybytes) ToHex() []byte

ToHex translates from KEYBYTES to HEX encoding.

type LoadFunc 

type LoadFunc func(*SubTrieLoader, *RetainList, [][]byte, []int) (SubTries, error)

type LoadRequestForCode 

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

LoadRequestForCode Code expresses the need to fetch code from the DB (by its hash) and attach to a specific account leaf in the trie.

func (*LoadRequestForCode) String 

func (lrc *LoadRequestForCode) String() string

type MerklePathLimiter 

type MerklePathLimiter struct {
	RetainDecider RetainDecider
	HashFunc      HashNodeFunc
}

type MissingNodeError 

type MissingNodeError struct {
	NodeHash libcommon.Hash // hash of the missing node
	Path     []byte         // hex-encoded path to the missing node
}

MissingNodeError is returned by the trie functions (TryGet, TryUpdate, TryDelete) in the case where a trie node is not present in the local database. It contains information necessary for retrieving the missing node.

func (*MissingNodeError) Error 

func (err *MissingNodeError) Error() string

type OperatorBranch 

type OperatorBranch struct {
	Mask uint32
}

func (*OperatorBranch) LoadFrom 

func (o *OperatorBranch) LoadFrom(loader *OperatorUnmarshaller) error

func (*OperatorBranch) WriteTo 

func (o *OperatorBranch) WriteTo(output *OperatorMarshaller) error

type OperatorCode 

type OperatorCode struct {
	Code []byte
}

func (*OperatorCode) LoadFrom 

func (o *OperatorCode) LoadFrom(loader *OperatorUnmarshaller) error

func (*OperatorCode) WriteTo 

func (o *OperatorCode) WriteTo(output *OperatorMarshaller) error

type OperatorEmptyRoot 

type OperatorEmptyRoot struct{}

func (*OperatorEmptyRoot) LoadFrom 

func (o *OperatorEmptyRoot) LoadFrom(loader *OperatorUnmarshaller) error

func (*OperatorEmptyRoot) WriteTo 

func (o *OperatorEmptyRoot) WriteTo(output *OperatorMarshaller) error

type OperatorExtension 

type OperatorExtension struct {
	Key []byte
}

func (*OperatorExtension) LoadFrom 

func (o *OperatorExtension) LoadFrom(loader *OperatorUnmarshaller) error

func (*OperatorExtension) WriteTo 

func (o *OperatorExtension) WriteTo(output *OperatorMarshaller) error

type OperatorHash 

type OperatorHash struct {
	Hash libcommon.Hash
}

func (*OperatorHash) LoadFrom 

func (o *OperatorHash) LoadFrom(loader *OperatorUnmarshaller) error

func (*OperatorHash) WriteTo 

func (o *OperatorHash) WriteTo(output *OperatorMarshaller) error

type OperatorKindCode 

type OperatorKindCode uint8

OperatorKindCode is "enum" type for defining the opcodes of the stack machine that reconstructs the structure of tries from Structure tape 

const (
	// OpLeaf creates leaf node and pushes it onto the node stack, its hash onto the hash stack
	OpLeaf OperatorKindCode = iota
	// OpExtension pops a node from the node stack, constructs extension node from it and its operand's key, and pushes this extension node onto
	// the node stack, its hash onto the hash stack
	OpExtension
	// OpBranch has operand, which is a bitset representing digits in the branch node. Pops the children nodes from the node stack (the number of
	// children is equal to the number of bits in the bitset), constructs branch node and pushes it onto the node stack, its hash onto the hash stack
	OpBranch
	// OpHash and pushes the hash them onto the stack.
	OpHash
	// OpCode constructs code node and pushes it onto the node stack, its hash onto the hash stack.
	OpCode
	// OpAccountLeaf constructs an account node (without any storage and code) and pushes it onto the node stack, its hash onto the hash stack.
	OpAccountLeaf
	// OpEmptyRoot places nil onto the node stack, and empty root hash onto the hash stack.
	OpEmptyRoot

	// OpNewTrie stops the processing, because another trie is encoded into the witness.
	OpNewTrie = OperatorKindCode(0xBB)
)

type OperatorLeafAccount 

type OperatorLeafAccount struct {
	Key        []byte
	Nonce      uint64
	Balance    *big.Int
	HasCode    bool
	HasStorage bool
	CodeSize   uint64
}

func (*OperatorLeafAccount) LoadFrom 

func (o *OperatorLeafAccount) LoadFrom(loader *OperatorUnmarshaller) error

func (*OperatorLeafAccount) WriteTo 

func (o *OperatorLeafAccount) WriteTo(output *OperatorMarshaller) error

type OperatorLeafValue 

type OperatorLeafValue struct {
	Key   []byte
	Value []byte
}

func (*OperatorLeafValue) LoadFrom 

func (o *OperatorLeafValue) LoadFrom(loader *OperatorUnmarshaller) error

func (*OperatorLeafValue) WriteTo 

func (o *OperatorLeafValue) WriteTo(output *OperatorMarshaller) error

type OperatorMarshaller 

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

OperatorMarshaller is responsible for encoding operators to a stream and collecting stats IMPORTANT: not thread-safe! use from a single thread only

func NewOperatorMarshaller 

func NewOperatorMarshaller(w io.Writer) *OperatorMarshaller

func (*OperatorMarshaller) GetStats 

func (w *OperatorMarshaller) GetStats() *BlockWitnessStats

func (*OperatorMarshaller) WithColumn 

func (w *OperatorMarshaller) WithColumn(column StatsColumn) *OperatorMarshaller

func (*OperatorMarshaller) Write 

func (w *OperatorMarshaller) Write(p []byte) (int, error)

func (*OperatorMarshaller) WriteByteArrayValue 

func (w *OperatorMarshaller) WriteByteArrayValue(value []byte) error

func (*OperatorMarshaller) WriteByteValue 

func (w *OperatorMarshaller) WriteByteValue(value byte) error

func (*OperatorMarshaller) WriteCode 

func (w *OperatorMarshaller) WriteCode(value []byte) error

func (*OperatorMarshaller) WriteHash 

func (w *OperatorMarshaller) WriteHash(hash libcommon.Hash) error

func (*OperatorMarshaller) WriteKey 

func (w *OperatorMarshaller) WriteKey(keyNibbles []byte) error

func (*OperatorMarshaller) WriteOpCode 

func (w *OperatorMarshaller) WriteOpCode(opcode OperatorKindCode) error

func (*OperatorMarshaller) WriteUint64Value 

func (w *OperatorMarshaller) WriteUint64Value(value uint64) error

type OperatorUnmarshaller 

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

OperatorMarshaller provides all needed primitives to read witness operators from a serialized form.

func NewOperatorUnmarshaller 

func NewOperatorUnmarshaller(r io.Reader) *OperatorUnmarshaller

func (*OperatorUnmarshaller) ReadByte 

func (l *OperatorUnmarshaller) ReadByte() (byte, error)

func (*OperatorUnmarshaller) ReadByteArray 

func (l *OperatorUnmarshaller) ReadByteArray() ([]byte, error)

func (*OperatorUnmarshaller) ReadHash 

func (l *OperatorUnmarshaller) ReadHash() (libcommon.Hash, error)

func (*OperatorUnmarshaller) ReadKey 

func (l *OperatorUnmarshaller) ReadKey() ([]byte, error)

func (*OperatorUnmarshaller) ReadUInt64 

func (l *OperatorUnmarshaller) ReadUInt64() (uint64, error)

func (*OperatorUnmarshaller) ReadUint32 

func (l *OperatorUnmarshaller) ReadUint32() (uint32, error)

type ProofRetainer 

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

ProofRetainer is a wrapper around the RetainList passed to the trie builder. It is responsible for aggregating proof values from the trie computation and will return a valid accounts.AccProofresult after the trie root hash calculation has completed.

func NewProofRetainer 

func NewProofRetainer(addr libcommon.Address, a *accounts.Account, storageKeys []libcommon.Hash, rl *RetainList) (*ProofRetainer, error)

NewProofRetainer creates a new ProofRetainer instance for a given account and set of storage keys. The trie keys corresponding to the account key, and its storage keys are added to the given RetainList. The ProofRetainer should be set onto the FlatDBTrieLoader via SetProofRetainer before performing its Load operation in order to appropriately collect the proof elements.

func (*ProofRetainer) ProofElement 

func (pr *ProofRetainer) ProofElement(prefix []byte) *proofElement

ProofElement requests a new proof element for a given prefix. This proof element is retained by the ProofRetainer, and will be utilized to compute the proof after the trie computation has completed. The prefix is the standard nibble encoded prefix used in the rest of the trie computations.

func (*ProofRetainer) ProofResult 

func (pr *ProofRetainer) ProofResult() (*accounts.AccProofResult, error)

ProofResult may be invoked only after the Load function of the FlatDBTrieLoader has successfully executed. It will populate the Address, Balance, Nonce, and CodeHash from the account data supplied in the constructor, the StorageHash, storageKey values, and proof elements are supplied by the Load operation of the trie construction.

type RetainDecider 

type RetainDecider interface {
	Retain([]byte) bool
	IsCodeTouched(libcommon.Hash) bool
}

type RetainDeciderWithMarker 

type RetainDeciderWithMarker interface {
	RetainDecider
	// AddKeyWithMarker adds a key in KEY encoding with marker and returns the
	// nibble encoded key.
	AddKeyWithMarker(key []byte, marker bool) []byte
	RetainWithMarker(prefix []byte) (retain bool, nextMarkedKey []byte)
}

type RetainList 

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

RetainList encapsulates the list of keys that are required to be fully available, or loaded (by using `BRANCH` opcode instead of `HASHER`) after processing of the sequence of key-value pairs DESCRIBED: docs/programmers_guide/guide.md#converting-sequence-of-keys-and-value-into-a-multiproof

func NewRetainList 

func NewRetainList(minLength int) *RetainList

NewRetainList creates new RetainList

func (*RetainList) AddCodeTouch 

func (rl *RetainList) AddCodeTouch(codeHash libcommon.Hash)

AddCodeTouch adds a new code touch into the resolve set

func (*RetainList) AddHex 

func (rl *RetainList) AddHex(hex []byte)

AddHex adds a new key (in HEX encoding) to the list

func (*RetainList) AddKey 

func (rl *RetainList) AddKey(key []byte) []byte

AddKey adds a new key (in KEY encoding) to the list

func (*RetainList) AddKeyWithMarker 

func (rl *RetainList) AddKeyWithMarker(key []byte, marker bool) []byte

func (*RetainList) IsCodeTouched 

func (rl *RetainList) IsCodeTouched(codeHash libcommon.Hash) bool

func (*RetainList) Len 

func (rl *RetainList) Len() int

func (*RetainList) Less 

func (rl *RetainList) Less(i, j int) bool

func (*RetainList) Retain 

func (rl *RetainList) Retain(prefix []byte) bool

Retain decides whether to emit `HASHER` or `BRANCH` for a given prefix, by checking if this is prefix of any of the keys added to the set Since keys in the set are sorted, and we expect that the prefixes will come in monotonically ascending order, we optimise for this, though the function would still work if the order is different

func (*RetainList) RetainWithMarker 

func (rl *RetainList) RetainWithMarker(prefix []byte) (bool, []byte)

func (*RetainList) Rewind 

func (rl *RetainList) Rewind()

Rewind lets us reuse this list from the beginning

func (*RetainList) String 

func (rl *RetainList) String() string

func (*RetainList) Swap 

func (rl *RetainList) Swap(i, j int)

type RootHashAggregator 

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

RootHashAggregator - calculates Merkle trie root hash from incoming data stream

func NewRootHashAggregator 

func NewRootHashAggregator() *RootHashAggregator

func (*RootHashAggregator) Receive 

func (r *RootHashAggregator) Receive(itemType StreamItem,
	accountKey []byte,
	storageKey []byte,
	accountValue *accounts.Account,
	storageValue []byte,
	hash []byte,
	hasTree bool,
	cutoff int,
) error

func (*RootHashAggregator) RetainNothing 

func (r *RootHashAggregator) RetainNothing(_ []byte) bool

func (*RootHashAggregator) Root 

func (r *RootHashAggregator) Root() libcommon.Hash

type StarkStatsBuilder 

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

func NewStarkStatsBuilder 

func NewStarkStatsBuilder() *StarkStatsBuilder

type StateCursor 

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

func NewStateCursor 

func NewStateCursor(c kv.Cursor, quit <-chan struct{}) *StateCursor

func (*StateCursor) Next 

func (c *StateCursor) Next() ([]byte, []byte, []byte, error)

func (*StateCursor) Seek 

func (c *StateCursor) Seek(seek []byte) ([]byte, []byte, []byte, error)

type StatsColumn 

type StatsColumn string

type StorageHashCollector 

type StorageHashCollector func(accWithInc []byte, keyHex []byte, hash []byte) error

type StorageHashCollector2 

type StorageHashCollector2 func(accWithInc []byte, keyHex []byte, hasState, hasTree, hasHash uint16, hashes, rootHash []byte) error

type StorageTrieCursor 

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

StorageTrieCursor - holds logic related to iteration over AccTrie bucket

func StorageTrie 

func StorageTrie(canUse func(prefix []byte) (bool, []byte), shc StorageHashCollector2, c kv.Cursor, quit <-chan struct{}) *StorageTrieCursor

func (*StorageTrieCursor) FirstNotCoveredPrefix 

func (c *StorageTrieCursor) FirstNotCoveredPrefix() []byte

func (*StorageTrieCursor) Next 

func (c *StorageTrieCursor) Next() (k, v []byte, hasTree bool, err error)

func (*StorageTrieCursor) PrevKey 

func (c *StorageTrieCursor) PrevKey() []byte

func (*StorageTrieCursor) SeekToAccount 

func (c *StorageTrieCursor) SeekToAccount(accWithInc []byte) (k, v []byte, hasTree bool, err error)

type Stream 

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

Stream represents the collection of key-value pairs, sorted by keys, where values may belong to three different types - accounts, strage item leaves, and intermediate hashes

func (*Stream) Reset 

func (s *Stream) Reset()

Reset sets all slices to zero sizes, without de-allocating

type StreamItem 

type StreamItem uint8

StreamItem is an enum type for values that help distinguish different types of key-value pairs in the stream of values produce by function `ToStream` 

const (
	// NoItem is used to signal the end of iterator
	NoItem StreamItem = iota
	// AccountStreamItem used for marking a key-value pair in the stream as belonging to an account
	AccountStreamItem
	// StorageStreamItem used for marking a key-value pair in the stream as belonging to a storage item leaf
	StorageStreamItem
	// AHashStreamItem used for marking a key-value pair in the stream as belonging to an intermediate hash
	// within the accounts (main state trie)
	AHashStreamItem
	// SHashStreamItem used for marking a key-value pair in the stream as belonging to an intermediate hash
	// within the storage items (storage tries)
	SHashStreamItem
	// CutoffStremItem used for marking the end of the subtrie
	CutoffStreamItem
)

type StreamIterator 

type StreamIterator interface {
	Next() (itemType StreamItem, hex1 []byte, aValue *accounts.Account, hash []byte, value []byte)
}

type StreamMergeIterator 

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

StreamMergeIterator merges an Iterator and a Stream

func NewStreamMergeIterator 

func NewStreamMergeIterator(it *Iterator, s *Stream, trace bool) *StreamMergeIterator

NewStreamMergeIterator create a brand new StreamMergeIterator

func (*StreamMergeIterator) Next 

func (smi *StreamMergeIterator) Next() (itemType1 StreamItem, hex1 []byte, aValue *accounts.Account, aCode []byte, hash []byte, value []byte)

Next returns the next item in the merged iterator

func (*StreamMergeIterator) Reset 

func (smi *StreamMergeIterator) Reset(it *Iterator, s *Stream, trace bool)

Reset prepares StreamMergeIterator for reuse

type SubTrieLoader 

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

Resolver looks up (resolves) some keys and corresponding values from a database. One resolver per trie (prefix). See also ResolveRequest in trie.go

func NewSubTrieLoader 

func NewSubTrieLoader() *SubTrieLoader

func (*SubTrieLoader) AddCodeRequest 

func (stl *SubTrieLoader) AddCodeRequest(req *LoadRequestForCode)

AddCodeRequest add a request for code loading

func (*SubTrieLoader) Reset 

func (stl *SubTrieLoader) Reset()

type SubTries 

type SubTries struct {
	Hashes []libcommon.Hash // Root hashes of the sub-tries
	// contains filtered or unexported fields
}

SubTrie is a result of loading sub-trie from either flat db or witness db. It encapsulates sub-trie root (which is of the un-exported type `node`) If the loading is done for verification and testing purposes, then usually only sub-tree root hash would be queried

type Trie 

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

Trie is a Merkle Patricia Trie. The zero value is an empty trie with no database. Use New to create a trie that sits on top of a database.

Trie is not safe for concurrent use. Deprecated use package turbo/trie

func BuildTrieFromWitness 

func BuildTrieFromWitness(witness *Witness, trace bool) (*Trie, error)

func HexToQuad 

func HexToQuad(t *Trie) *Trie

HexToQuad converts hexary trie to quad trie with the same set of keys

func Load 

func Load(r io.Reader) (*Trie, error)

func New 

func New(root libcommon.Hash) *Trie

New creates a trie with an existing root node from db.

If root is the zero hash or the sha3 hash of an empty string, the trie is initially empty and does not require a database. Otherwise, New will panic if db is nil and returns a MissingNodeError if root does not exist in the database. Accessing the trie loads nodes from db on demand. Deprecated use package turbo/trie

func NewTestRLPTrie 

func NewTestRLPTrie(root libcommon.Hash) *Trie

NewTestRLPTrie treats all the data provided to `Update` function as rlp-encoded. it is usually used for testing purposes.

func (*Trie) DeepHash 

func (t *Trie) DeepHash(keyPrefix []byte) (bool, libcommon.Hash)

DeepHash returns internal hash of a node reachable by the specified key prefix. Note that if the prefix points into the middle of a key for a leaf node or of an extension node, it will return the hash of a modified leaf node or extension node, where the key prefix is removed from the key. First returned value is `true` if the node with the specified prefix is found.

func (*Trie) Delete 

func (t *Trie) Delete(key []byte)

Delete removes any existing value for key from the trie. DESCRIBED: docs/programmers_guide/guide.md#root

func (*Trie) DeleteSubtree 

func (t *Trie) DeleteSubtree(keyPrefix []byte)

DeleteSubtree removes any existing value for key from the trie. The only difference between Delete and DeleteSubtree is that Delete would delete accountNode too, wherewas DeleteSubtree will keep the accountNode, but will make the storage sub-trie empty

func (*Trie) EvictNode 

func (t *Trie) EvictNode(hex []byte)

func (*Trie) ExtractWitness 

func (t *Trie) ExtractWitness(trace bool, rl RetainDecider) (*Witness, error)

func (*Trie) ExtractWitnessForPrefix 

func (t *Trie) ExtractWitnessForPrefix(prefix []byte, trace bool, rl RetainDecider) (*Witness, error)

func (*Trie) FindSubTriesToLoad 

func (t *Trie) FindSubTriesToLoad(rl RetainDecider) (prefixes [][]byte, fixedbits []int, hooks [][]byte)

FindSubTriesToLoad walks over the trie and creates the list of DB prefixes and corresponding list of valid bits in the prefix (for the cases when prefix contains an odd number of nibbles) that would allow loading the missing information from the database It also create list of `hooks`, the paths in the trie (in nibbles) where the loaded sub-tries need to be inserted.

func (*Trie) Fold 

func (t *Trie) Fold(keys [][]byte)

Fold modifies the trie by folding the given set of keys, making sure that they are inaccessible without resolution via DB

func (*Trie) Get 

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

Get returns the value for key stored in the trie.

func (*Trie) GetAccount 

func (t *Trie) GetAccount(key []byte) (value *accounts.Account, gotValue bool)

func (*Trie) GetAccountCode 

func (t *Trie) GetAccountCode(key []byte) (value []byte, gotValue bool)

func (*Trie) GetAccountCodeSize 

func (t *Trie) GetAccountCodeSize(key []byte) (value int, gotValue bool)

func (*Trie) Hash 

func (t *Trie) Hash() libcommon.Hash

Hash returns the root hash of the trie. It does not write to the database and can be used even if the trie doesn't have one. DESCRIBED: docs/programmers_guide/guide.md#root

func (*Trie) HashOfHexKey 

func (t *Trie) HashOfHexKey(hexKey []byte) (libcommon.Hash, error)

func (*Trie) HookSubTries 

func (t *Trie) HookSubTries(subTries SubTries, hooks [][]byte) error

func (*Trie) NeedLoadCode 

func (t *Trie) NeedLoadCode(addrHash libcommon.Hash, codeHash libcommon.Hash, bytecode bool) (bool, *LoadRequestForCode)

func (*Trie) NewLoadRequestForCode 

func (t *Trie) NewLoadRequestForCode(addrHash libcommon.Hash, codeHash libcommon.Hash, bytecode bool) *LoadRequestForCode

func (*Trie) NumberOfAccounts 

func (t *Trie) NumberOfAccounts() int

func (*Trie) Print 

func (t *Trie) Print(w io.Writer)

func (*Trie) PrintDiff 

func (t *Trie) PrintDiff(t2 *Trie, w io.Writer)

func (*Trie) PrintTrie 

func (t *Trie) PrintTrie()

func (*Trie) Prove 

func (t *Trie) Prove(key []byte, fromLevel int, storage bool) ([][]byte, error)

Prove constructs a merkle proof for key. The result contains all encoded nodes on the path to the value at key. The value itself is also included in the last node and can be retrieved by verifying the proof.

If the trie does not contain a value for key, the returned proof contains all nodes of the longest existing prefix of the key (at least the root node), ending with the node that proves the absence of the key.

func (*Trie) Reset 

func (t *Trie) Reset()

func (*Trie) Root 

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

Root returns the root hash of the trie. Deprecated: use Hash instead.

func (*Trie) TrieSize 

func (t *Trie) TrieSize() int

func (*Trie) Update 

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

Update associates key with value in the trie. Subsequent calls to Get will return value. If value has length zero, any existing value is deleted from the trie and calls to Get will return nil.

The value bytes must not be modified by the caller while they are stored in the trie. DESCRIBED: docs/programmers_guide/guide.md#root

func (*Trie) UpdateAccount 

func (t *Trie) UpdateAccount(key []byte, acc *accounts.Account)

func (*Trie) UpdateAccountCode 

func (t *Trie) UpdateAccountCode(key []byte, code codeNode) error

UpdateAccountCode attaches the code node to an account at specified key

func (*Trie) UpdateAccountCodeSize 

func (t *Trie) UpdateAccountCodeSize(key []byte, codeSize int) error

UpdateAccountCodeSize attaches the code size to the account

type VisualOpts 

type VisualOpts struct {
	Highlights     [][]byte // Collection of keys, in the HEX encoding, that need to be highlighted with digits
	IndexColors    []string // Array of colors for representing digits as colored boxes
	FontColors     []string // Array of colors, the same length as indexColors, for the textual digits inside the coloured boxes
	CutTerminals   int      // Specifies how many digits to cut from the terminal short node keys for a more convinient display
	Values         bool     // Whether to display value nodes (as box with rounded corners)
	CodeCompressed bool     // Whether to turn the code from a large rectangle to a small square for a more convinient display
	ValCompressed  bool     // Whether long values (over 10 characters) are shortened using ... in the middle
	ValHex         bool     // Whether values should be displayed as hex numbers (otherwise they are displayed as just strings)
	SameLevel      bool     // Whether the leaves (and hashes) need to be on the same horizontal level
}

VisualOpts contains various configuration options fo the Visual function It has been introduced as a replacement for too many arguments with options

type Witness 

type Witness struct {
	Header    WitnessHeader
	Operators []WitnessOperator
}

func ExtractWitnesses 

func ExtractWitnesses(subTries SubTries, trace bool, retainDec RetainDecider) ([]*Witness, error)

ExtractWitnesses extracts witnesses for subtries starting from the specified root if retainDec param is nil it will make a witness for the full subtrie, if retainDec param is set to a RetainList instance, it will make a witness for only the accounts/storages that were actually touched; other paths will be hashed.

func NewWitness 

func NewWitness(operands []WitnessOperator) *Witness

func NewWitnessFromReader 

func NewWitnessFromReader(input io.Reader, trace bool) (*Witness, error)

func (*Witness) WriteDiff 

func (w *Witness) WriteDiff(w2 *Witness, output io.Writer)

func (*Witness) WriteInto 

func (w *Witness) WriteInto(out io.Writer) (*BlockWitnessStats, error)

type WitnessBuilder 

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

func NewWitnessBuilder 

func NewWitnessBuilder(root node, trace bool) *WitnessBuilder

func (*WitnessBuilder) Build 

func (b *WitnessBuilder) Build(limiter *MerklePathLimiter) (*Witness, error)

type WitnessHeader 

type WitnessHeader struct {
	Version uint8
}

WitnessHeader contains version information and maybe some future format bits the version is always the 1st bit.

func (*WitnessHeader) LoadFrom 

func (h *WitnessHeader) LoadFrom(input io.Reader) error

func (*WitnessHeader) WriteTo 

func (h *WitnessHeader) WriteTo(out *OperatorMarshaller) error

type WitnessOperator 

type WitnessOperator interface {
	WriteTo(*OperatorMarshaller) error

	// LoadFrom always assumes that the opcode value was already read
	LoadFrom(*OperatorUnmarshaller) error
}

WitnessOperator is a single operand in the block witness. It knows how to serialize/deserialize itself.

type WitnessStorage 

type WitnessStorage interface {
	GetWitnessesForBlock(uint64, uint32) ([]byte, error)
}

WitnessStorage is an interface representing a single

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.