trie

package
v0.14.1 Latest Latest
Warning

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

 Go to latest Published: Mar 14, 2025 License: Apache-2.0 Imports: 14 Imported by: 1

Documentation

Overview

Package trie implements a dense Merkle Patricia Trie. See the documentation on Trie for details.

Index

Constants

View Source 
const (
	MaxBitArraySize = 33 // (1 + 4 * 8) bytes
)

Variables

This section is empty.

Functions

func RunOnTempTriePedersen added in v0.12.0 

func RunOnTempTriePedersen(height uint8, do func(*Trie) error) error

RunOnTempTriePedersen creates an in-memory Trie of height `height` and runs `do` on that Trie

func RunOnTempTriePoseidon added in v0.12.0 

func RunOnTempTriePoseidon(height uint8, do func(*Trie) error) error

func VerifyProof added in v0.11.8 

func VerifyProof(root, keyFelt *felt.Felt, proof *ProofNodeSet, hash crypto.HashFn) (*felt.Felt, error)

VerifyProof verifies that a proof path is valid for a given key in a binary trie. It walks through the proof nodes, verifying each step matches the expected path to reach the key.

The verification process: 1. Starts at the root hash and retrieves the corresponding proof node 2. For each proof node:

  • Verifies the node's computed hash matches the expected hash
  • For Binary nodes: -- Uses the next unprocessed bit in the key to choose left/right path -- If key bit is 0, takes left path; if 1, takes right path
  • For Edge nodes: -- Verifies the compressed path matches the corresponding bits in the key -- Moves to the child node if paths match

3. Continues until all bits in the key are processed

The proof is considered invalid if:

  • Any proof node is missing from the OrderedSet
  • Any node's computed hash doesn't match its expected hash
  • The path bits don't match the key bits
  • The proof ends before processing all key bits

func VerifyRangeProof added in v0.12.0 

func VerifyRangeProof(root, first *felt.Felt, keys, values []*felt.Felt, proof *ProofNodeSet) (bool, error)

VerifyRangeProof checks the validity of given key-value pairs and range proof against a provided root hash. The key-value pairs should be consecutive (no gaps) and monotonically increasing. The range proof contains two edge proofs: one for the first key and another for the last key. Both edge proofs can be for existent or non-existent keys. This function handles the following special cases:

  • All elements proof: The proof can be nil if the range includes all leaves in the trie.
  • Single element proof: Both left and right edge proofs are identical, and the range contains only one element.
  • Zero element proof: A single edge proof suffices for verification. The proof is invalid if there are additional elements.

The function returns a boolean indicating if there are more elements and an error if the range proof is invalid.

TODO(weiihann): Given a binary leaf and a left-sibling first key, if the right sibling is removed, the proof would still be valid. Conversely, given a binary leaf and a right-sibling last key, if the left sibling is removed, the proof would still be valid. Range proof should not be valid for both of these cases, but currently is, which is an attack vector. The problem probably lies in how we do root hash calculation.

Types

type Binary added in v0.11.8 

type Binary struct {
	LeftHash  *felt.Felt
	RightHash *felt.Felt
}

func (*Binary) Hash added in v0.12.3 

func (b *Binary) Hash(hash crypto.HashFn) *felt.Felt

func (*Binary) Len added in v0.12.3 

func (b *Binary) Len() uint8

func (*Binary) String added in v0.13.0 

func (b *Binary) String() string

type BitArray added in v0.13.0 

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

Represents a bit array with length representing the number of used bits. It uses a little endian representation to do bitwise operations of the words efficiently. For example, if len is 10, it means that the 2^9, 2^8, ..., 2^0 bits are used. The max length is 255 bits (uint8), because our use case only need up to 251 bits for a given trie key. Although words can be used to represent 256 bits, we don't want to add an additional byte for the length.

func NewBitArray added in v0.13.0 

func NewBitArray(length uint8, val uint64) BitArray

func (*BitArray) And added in v0.13.0 

func (b *BitArray) And(x, y *BitArray) *BitArray

func (*BitArray) Append added in v0.13.0 

func (b *BitArray) Append(x, y *BitArray) *BitArray

Sets the bit array to the concatenation of x and y and returns the bit array. For example: 

x = 000 (len=3)
y = 111 (len=3)
Append(x,y) = 000111 (len=6)

func (*BitArray) AppendBit added in v0.13.0 

func (b *BitArray) AppendBit(x *BitArray, bit uint8) *BitArray

Sets the bit array to the concatenation of x and a single bit.

func (*BitArray) AppendZeros added in v0.13.0 

func (b *BitArray) AppendZeros(x *BitArray, n uint8) *BitArray

Sets the bit array to the concatenation of x and n zeros.

func (*BitArray) Bit added in v0.13.0 

func (b *BitArray) Bit(n uint8) uint8

Returns the bit value at position n, where n = 0 is MSB. If n is out of bounds, returns 0.

func (*BitArray) BitFromLSB added in v0.13.0 

func (b *BitArray) BitFromLSB(n uint8) uint8

Returns the bit value at position n, where n = 0 is LSB. If n is out of bounds, returns 0.

func (*BitArray) Bytes added in v0.13.0 

func (b *BitArray) Bytes() [32]byte

Returns the bytes representation of the bit array in big endian format

func (*BitArray) Cmp added in v0.13.0 

func (b *BitArray) Cmp(x *BitArray) int

Cmp compares two bit arrays lexicographically. The comparison is first done by length, then by content if lengths are equal. Returns: 

-1 if b < x
 0 if b == x
 1 if b > x

func (*BitArray) CommonMSBs added in v0.13.0 

func (b *BitArray) CommonMSBs(x, y *BitArray) *BitArray

Sets the bit array to the longest sequence of matching most significant bits between two bit arrays. For example: 

x = 1101 0111 (len=8)
y = 1101 0000 (len=8)
CommonMSBs(x,y) = 1101 (len=4)

func (*BitArray) Copy added in v0.13.0 

func (b *BitArray) Copy() BitArray

Returns a deep copy of the bit array.

func (*BitArray) EncodedLen added in v0.13.0 

func (b *BitArray) EncodedLen() uint

Returns the length of the encoded bit array in bytes.

func (*BitArray) EncodedString added in v0.13.0 

func (b *BitArray) EncodedString() string

Returns the encoded string representation of the bit array.

func (*BitArray) Equal added in v0.13.0 

func (b *BitArray) Equal(x *BitArray) bool

Checks if two bit arrays are equal

func (*BitArray) EqualMSBs added in v0.13.0 

func (b *BitArray) EqualMSBs(x *BitArray) bool

Checks if the current bit array share the same most significant bits with another, where the length of the check is determined by the shorter array. Returns true if either array has length 0, or if the first min(b.len, x.len) MSBs are identical.

For example: 

a = 1101 (len=4)
b = 11010111 (len=8)
a.EqualMSBs(b) = true  // First 4 MSBs match

a = 1100 (len=4)
b = 1101 (len=4)
a.EqualMSBs(b) = false // All bits compared, not equal

a = 1100 (len=4)
b = [] (len=0)
a.EqualMSBs(b) = true  // Zero length is always a prefix match

func (*BitArray) Felt added in v0.13.0 

func (b *BitArray) Felt() felt.Felt

Returns the felt representation of the bit array.

func (*BitArray) IsBitSet added in v0.13.0 

func (b *BitArray) IsBitSet(n uint8) bool

func (*BitArray) IsBitSetFromLSB added in v0.13.0 

func (b *BitArray) IsBitSetFromLSB(n uint8) bool

Returns true if bit n-th is set, where n = 0 is LSB.

func (*BitArray) IsEmpty added in v0.13.0 

func (b *BitArray) IsEmpty() bool

func (*BitArray) LSB added in v0.13.0 

func (b *BitArray) LSB() uint8

func (*BitArray) LSBs added in v0.13.0 

func (b *BitArray) LSBs(x *BitArray, n uint8) *BitArray

Returns the least significant bits of `x` with `n` counted from the most significant bit, starting at 0. Think of this method as array[n:] For example: 

x = 11001011 (len=8)
LSBs(x, 1) = 1001011 (len=7)
LSBs(x, 10) = 0 (len=0)
LSBs(x, 0) = 11001011 (len=8, original x)

func (*BitArray) LSBsFromLSB added in v0.13.0 

func (b *BitArray) LSBsFromLSB(x *BitArray, n uint8) *BitArray

Sets the bit array to the least significant 'n' bits of x. n is counted from the least significant bit, starting at 0. If length >= x.len, the bit array is an exact copy of x. For example: 

x = 11001011 (len=8)
LSBsFromLSB(x, 4) = 1011 (len=4)
LSBsFromLSB(x, 10) = 11001011 (len=8, original x)
LSBsFromLSB(x, 0) = 0 (len=0)

func (*BitArray) Len added in v0.13.0 

func (b *BitArray) Len() uint8

func (*BitArray) Lsh added in v0.13.0 

func (b *BitArray) Lsh(x *BitArray, n uint8) *BitArray

Lsh sets the bit array to x << n and returns the bit array.

func (*BitArray) MSB added in v0.13.0 

func (b *BitArray) MSB() uint8

Returns the bit value at the most significant bit

func (*BitArray) MSBs added in v0.13.0 

func (b *BitArray) MSBs(x *BitArray, n uint8) *BitArray

Sets the bit array to the most significant 'n' bits of x, that is position 0 to n (exclusive). If n >= x.len, the bit array is an exact copy of x. Think of this method as array[0:n] For example: 

x = 11001011 (len=8)
MSBs(x, 4) = 1100 (len=4)
MSBs(x, 10) = 11001011 (len=8, original x)
MSBs(x, 0) = 0 (len=0)

func (*BitArray) Ones added in v0.13.0 

func (b *BitArray) Ones(length uint8) *BitArray

Sets the bit array to a sequence of ones of the specified length.

func (*BitArray) Or added in v0.13.0 

func (b *BitArray) Or(x, y *BitArray) *BitArray

Sets the bit array to x | y and returns the bit array.

func (*BitArray) Rsh added in v0.13.0 

func (b *BitArray) Rsh(x *BitArray, n uint8) *BitArray

Sets the bit array to x >> n and returns the bit array.

func (*BitArray) Set added in v0.13.0 

func (b *BitArray) Set(x *BitArray) *BitArray

Sets the bit array to the same value as x.

func (*BitArray) SetBit added in v0.13.0 

func (b *BitArray) SetBit(bit uint8) *BitArray

Sets the bit array to a single bit.

func (*BitArray) SetBytes added in v0.13.0 

func (b *BitArray) SetBytes(length uint8, data []byte) *BitArray

Interprets the data as the big-endian bytes, sets the bit array to that value and returns it. If the data is larger than 32 bytes, only the first 32 bytes are used.

func (*BitArray) SetFelt added in v0.13.0 

func (b *BitArray) SetFelt(length uint8, f *felt.Felt) *BitArray

Sets the bit array to the bytes representation of a felt.

func (*BitArray) SetFelt251 added in v0.13.0 

func (b *BitArray) SetFelt251(f *felt.Felt) *BitArray

Sets the bit array to the bytes representation of a felt with length 251.

func (*BitArray) SetUint64 added in v0.13.0 

func (b *BitArray) SetUint64(length uint8, data uint64) *BitArray

Sets the bit array to the uint64 representation of a bit array.

func (*BitArray) String added in v0.13.0 

func (b *BitArray) String() string

Returns a string representation of the bit array. This is typically used for logging or debugging.

func (*BitArray) Subset added in v0.13.0 

func (b *BitArray) Subset(x *BitArray, startPos, endPos uint8) *BitArray

Sets the bit array to a subset of x from startPos (inclusive) to endPos (exclusive), where position 0 is the MSB. If startPos >= endPos or if startPos >= x.len, returns an empty BitArray. Think of this method as array[start:end] For example: 

x = 001011011 (len=9)
Subset(x, 2, 5) = 101 (len=3)

func (*BitArray) UnmarshalBinary added in v0.13.0 

func (b *BitArray) UnmarshalBinary(data []byte) error

Deserialises the BitArray from a bytes buffer in the following format: - First byte: length of the bit array (0-255) - Remaining bytes: the necessary bytes included in big endian order Example: 

[0x0A, 0x03, 0xFF] -> BitArray{len: 10, words: [4]uint64{0x03FF}}

func (*BitArray) Write added in v0.13.0 

func (b *BitArray) Write(buf *bytes.Buffer) (int, error)

Serialises the BitArray into a bytes buffer in the following format: - First byte: length of the bit array (0-255) - Remaining bytes: the necessary bytes included in big endian order Example: 

BitArray{len: 10, words: [4]uint64{0x03FF}} -> [0x0A, 0x03, 0xFF]

func (*BitArray) Xor added in v0.13.0 

func (b *BitArray) Xor(x, y *BitArray) *BitArray

Sets the bit array to x ^ y and returns the bit array.

func (*BitArray) Zeros added in v0.13.0 

func (b *BitArray) Zeros(length uint8) *BitArray

type Edge added in v0.11.8 

type Edge struct {
	Child *felt.Felt // child hash
	Path  *BitArray  // path from parent to child
}

func (*Edge) Hash added in v0.12.3 

func (e *Edge) Hash(hash crypto.HashFn) *felt.Felt

func (*Edge) Len added in v0.12.3 

func (e *Edge) Len() uint8

func (*Edge) String added in v0.13.0 

func (e *Edge) String() string

type NewTrieFunc added in v0.2.1 

type NewTrieFunc func(*Storage, uint8) (*Trie, error)

type Node 

type Node struct {
	Value     *felt.Felt
	Left      *BitArray
	Right     *BitArray
	LeftHash  *felt.Felt
	RightHash *felt.Felt
}

A Node represents a node in the Trie https://docs.starknet.io/architecture-and-concepts/network-architecture/starknet-state/#trie_construction

func (*Node) Hash 

func (n *Node) Hash(path *BitArray, hashFn crypto.HashFn) *felt.Felt

Hash calculates the hash of a Node

func (*Node) HashFromParent added in v0.12.0 

func (n *Node) HashFromParent(parentKey, nodeKey *BitArray, hashFn crypto.HashFn) *felt.Felt

Hash calculates the hash of a Node

func (*Node) String added in v0.13.0 

func (n *Node) String() string

func (*Node) UnmarshalBinary added in v0.4.0 

func (n *Node) UnmarshalBinary(data []byte) error

UnmarshalBinary deserializes a Node from a byte array

func (*Node) Update added in v0.13.0 

func (n *Node) Update(other *Node) error

Update the receiver with non-nil fields from the `other` Node. If a field is non-nil in both Nodes, they must be equal, or an error is returned.

This method modifies the receiver in-place and returns an error if any field conflicts are detected.

func (*Node) WriteTo added in v0.4.0 

func (n *Node) WriteTo(buf *bytes.Buffer) (int, error)

type ProofNode added in v0.11.8 

type ProofNode interface {
	Hash(hash crypto.HashFn) *felt.Felt
	Len() uint8
	String() string
}

type ProofNodeSet added in v0.13.0 

type ProofNodeSet = utils.OrderedSet[felt.Felt, ProofNode]

func NewProofNodeSet added in v0.13.0 

func NewProofNodeSet() *ProofNodeSet

type Storage 

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

Storage is a database transaction on a trie.

func NewStorage added in v0.11.6 

func NewStorage(txn db.Transaction, prefix []byte) *Storage

func (*Storage) Delete 

func (t *Storage) Delete(key *BitArray) error

func (*Storage) DeleteRootKey added in v0.4.0 

func (t *Storage) DeleteRootKey() error

func (*Storage) Get 

func (t *Storage) Get(key *BitArray) (*Node, error)

func (*Storage) Put 

func (t *Storage) Put(key *BitArray, value *Node) error

func (*Storage) PutRootKey added in v0.4.0 

func (t *Storage) PutRootKey(newRootKey *BitArray) error

func (*Storage) RootKey added in v0.4.0 

func (t *Storage) RootKey() (*BitArray, error)

func (*Storage) SyncedStorage added in v0.11.6 

func (t *Storage) SyncedStorage() *Storage

type StorageNode added in v0.12.0 

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

storageNode is the on-disk representation of a Node, where key is the storage key and node is the value.

func NewPartialStorageNode added in v0.13.0 

func NewPartialStorageNode(key *BitArray, value *felt.Felt) *StorageNode

NewPartialStorageNode creates a new StorageNode with a given key and value, where the right and left children are nil.

func NewStorageNode added in v0.12.0 

func NewStorageNode(key *BitArray, node *Node) *StorageNode

func (*StorageNode) Key added in v0.12.0 

func (sn *StorageNode) Key() *BitArray

func (*StorageNode) String added in v0.13.0 

func (sn *StorageNode) String() string

func (*StorageNode) Update added in v0.13.0 

func (sn *StorageNode) Update(other *StorageNode) error

func (*StorageNode) Value added in v0.13.0 

func (sn *StorageNode) Value() *felt.Felt

type StorageNodeSet added in v0.13.0 

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

StorageNodeSet wraps OrderedSet to provide specific functionality for StorageNodes

func NewStorageNodeSet added in v0.13.0 

func NewStorageNodeSet() *StorageNodeSet

func (*StorageNodeSet) Get added in v0.13.0 

func (s *StorageNodeSet) Get(key BitArray) (*StorageNode, bool)

func (*StorageNodeSet) List added in v0.13.0 

func (s *StorageNodeSet) List() []*StorageNode

List returns the list of StorageNodes in the set.

func (*StorageNodeSet) Put added in v0.13.0 

func (s *StorageNodeSet) Put(key BitArray, node *StorageNode) error

Put adds a new StorageNode or updates an existing one.

func (*StorageNodeSet) Size added in v0.13.0 

func (s *StorageNodeSet) Size() int

type Trie 

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

Trie is a dense Merkle Patricia Trie (i.e., all internal nodes have two children).

This implementation allows for a "flat" storage by keying nodes on their path rather than their hash, resulting in O(1) accesses and O(log n) insertions.

The state trie specification describes a sparse Merkle Trie. Note that this dense implementation results in an equivalent commitment.

Terminology:

  • path: represents the path as defined in the specification. Together with len, represents a relative path from the current node to the node's nearest non-empty child.
  • len: represents the len as defined in the specification. The number of bits to take from the fixed-length path to reach the nearest non-empty child.
  • key: represents the storage key for trie [Node]s. It is the full path to the node from the root.

func NewTriePedersen added in v0.2.1 

func NewTriePedersen(storage *Storage, height uint8) (*Trie, error)

func NewTriePoseidon added in v0.2.1 

func NewTriePoseidon(storage *Storage, height uint8) (*Trie, error)

func (*Trie) Commit added in v0.4.0 

func (t *Trie) Commit() error

Commit forces root calculation

func (*Trie) Dump 

func (t *Trie) Dump()

func (*Trie) FeltToKey added in v0.13.0 

func (t *Trie) FeltToKey(k *felt.Felt) BitArray

FeltToKey converts a key, given in felt, to a trie.Key which when followed on a Trie, leads to the corresponding Node

func (*Trie) Get 

func (t *Trie) Get(key *felt.Felt) (*felt.Felt, error)

Get the corresponding `value` for a `key`

func (*Trie) GetNodeFromKey added in v0.11.8 

func (t *Trie) GetNodeFromKey(key *BitArray) (*Node, error)

GetNodeFromKey returns the node for a given key.

func (*Trie) GetRangeProof added in v0.13.0 

func (t *Trie) GetRangeProof(leftKey, rightKey *felt.Felt, proofSet *ProofNodeSet) error

GetRangeProof generates a range proof for the given range of keys. The proof contains the proof nodes on the path from the root to the closest ancestor of the left and right keys.

func (*Trie) HashFn added in v0.13.0 

func (t *Trie) HashFn() crypto.HashFn

func (*Trie) Prove added in v0.13.0 

func (t *Trie) Prove(key *felt.Felt, proof *ProofNodeSet) error

Prove generates a Merkle proof for a given key in the trie. The result contains the proof nodes on the path from the root to the leaf. The value is included in the proof if the key is present in the trie. If the key is not present, the proof will contain the nodes on the path to the closest ancestor.

func (*Trie) Put 

func (t *Trie) Put(key, value *felt.Felt) (*felt.Felt, error)

Put updates the corresponding `value` for a `key`

func (*Trie) PutInner added in v0.12.0 

func (t *Trie) PutInner(key *BitArray, node *Node) error

Put updates the corresponding `value` for a `key`

func (*Trie) PutWithProof added in v0.12.0 

func (t *Trie) PutWithProof(key, value *felt.Felt, proof []*StorageNode) (*felt.Felt, error)

Put updates the corresponding `value` for a `key`

func (*Trie) Root 

func (t *Trie) Root() (*felt.Felt, error)

Root returns the commitment of a Trie

func (*Trie) RootKey 

func (t *Trie) RootKey() *BitArray

RootKey returns db key of the Trie root node

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.