Documentation
¶
Overview ¶
Package trie implements a dense Merkle Patricia Trie. See the documentation on Trie for details.
Index ¶
- Constants
- func RunOnTempTriePedersen(height uint8, do func(*Trie) error) error
- func RunOnTempTriePoseidon(height uint8, do func(*Trie) error) error
- func VerifyProof(root, keyFelt *felt.Felt, proof *ProofNodeSet, hash crypto.HashFn) (*felt.Felt, error)
- func VerifyRangeProof(root, first *felt.Felt, keys, values []*felt.Felt, proof *ProofNodeSet) (bool, error)
- type Binary
- type BitArray
- func (b *BitArray) And(x, y *BitArray) *BitArray
- func (b *BitArray) Append(x, y *BitArray) *BitArray
- func (b *BitArray) AppendBit(x *BitArray, bit uint8) *BitArray
- func (b *BitArray) AppendZeros(x *BitArray, n uint8) *BitArray
- func (b *BitArray) Bit(n uint8) uint8
- func (b *BitArray) BitFromLSB(n uint8) uint8
- func (b *BitArray) Bytes() [32]byte
- func (b *BitArray) Cmp(x *BitArray) int
- func (b *BitArray) CommonMSBs(x, y *BitArray) *BitArray
- func (b *BitArray) Copy() BitArray
- func (b *BitArray) EncodedLen() uint
- func (b *BitArray) EncodedString() string
- func (b *BitArray) Equal(x *BitArray) bool
- func (b *BitArray) EqualMSBs(x *BitArray) bool
- func (b *BitArray) Felt() felt.Felt
- func (b *BitArray) IsBitSet(n uint8) bool
- func (b *BitArray) IsBitSetFromLSB(n uint8) bool
- func (b *BitArray) IsEmpty() bool
- func (b *BitArray) LSB() uint8
- func (b *BitArray) LSBs(x *BitArray, n uint8) *BitArray
- func (b *BitArray) LSBsFromLSB(x *BitArray, n uint8) *BitArray
- func (b *BitArray) Len() uint8
- func (b *BitArray) Lsh(x *BitArray, n uint8) *BitArray
- func (b *BitArray) MSB() uint8
- func (b *BitArray) MSBs(x *BitArray, n uint8) *BitArray
- func (b *BitArray) Ones(length uint8) *BitArray
- func (b *BitArray) Or(x, y *BitArray) *BitArray
- func (b *BitArray) Rsh(x *BitArray, n uint8) *BitArray
- func (b *BitArray) Set(x *BitArray) *BitArray
- func (b *BitArray) SetBit(bit uint8) *BitArray
- func (b *BitArray) SetBytes(length uint8, data []byte) *BitArray
- func (b *BitArray) SetFelt(length uint8, f *felt.Felt) *BitArray
- func (b *BitArray) SetFelt251(f *felt.Felt) *BitArray
- func (b *BitArray) SetUint64(length uint8, data uint64) *BitArray
- func (b *BitArray) String() string
- func (b *BitArray) Subset(x *BitArray, startPos, endPos uint8) *BitArray
- func (b *BitArray) UnmarshalBinary(data []byte) error
- func (b *BitArray) Write(buf *bytes.Buffer) (int, error)
- func (b *BitArray) Xor(x, y *BitArray) *BitArray
- func (b *BitArray) Zeros(length uint8) *BitArray
- type Edge
- type NewTrieFunc
- type Node
- func (n *Node) Hash(path *BitArray, hashFn crypto.HashFn) *felt.Felt
- func (n *Node) HashFromParent(parentKey, nodeKey *BitArray, hashFn crypto.HashFn) *felt.Felt
- func (n *Node) String() string
- func (n *Node) UnmarshalBinary(data []byte) error
- func (n *Node) Update(other *Node) error
- func (n *Node) WriteTo(buf *bytes.Buffer) (int, error)
- type ProofNode
- type ProofNodeSet
- type Storage
- func (t *Storage) Delete(key *BitArray) error
- func (t *Storage) DeleteRootKey() error
- func (t *Storage) Get(key *BitArray) (*Node, error)
- func (t *Storage) Put(key *BitArray, value *Node) error
- func (t *Storage) PutRootKey(newRootKey *BitArray) error
- func (t *Storage) RootKey() (*BitArray, error)
- func (t *Storage) SyncedStorage() *Storage
- type StorageNode
- type StorageNodeSet
- type Trie
- func (t *Trie) Commit() error
- func (t *Trie) Dump()
- func (t *Trie) FeltToKey(k *felt.Felt) BitArray
- func (t *Trie) Get(key *felt.Felt) (*felt.Felt, error)
- func (t *Trie) GetNodeFromKey(key *BitArray) (*Node, error)
- func (t *Trie) GetRangeProof(leftKey, rightKey *felt.Felt, proofSet *ProofNodeSet) error
- func (t *Trie) HashFn() crypto.HashFn
- func (t *Trie) Prove(key *felt.Felt, proof *ProofNodeSet) error
- func (t *Trie) Put(key, value *felt.Felt) (*felt.Felt, error)
- func (t *Trie) PutInner(key *BitArray, node *Node) error
- func (t *Trie) PutWithProof(key, value *felt.Felt, proof []*StorageNode) (*felt.Felt, error)
- func (t *Trie) Root() (*felt.Felt, error)
- func (t *Trie) RootKey() *BitArray
Constants ¶
const (
MaxBitArraySize = 33 // (1 + 4 * 8) bytes
)
Variables ¶
This section is empty.
Functions ¶
func RunOnTempTriePedersen ¶ added in v0.12.0
RunOnTempTriePedersen creates an in-memory Trie of height `height` and runs `do` on that Trie
func RunOnTempTriePoseidon ¶ added in v0.12.0
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 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 (*BitArray) Append ¶ added in v0.13.0
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
Sets the bit array to the concatenation of x and a single bit.
func (*BitArray) AppendZeros ¶ added in v0.13.0
Sets the bit array to the concatenation of x and n zeros.
func (*BitArray) Bit ¶ added in v0.13.0
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
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
Returns the bytes representation of the bit array in big endian format
func (*BitArray) Cmp ¶ added in v0.13.0
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
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) EncodedLen ¶ added in v0.13.0
Returns the length of the encoded bit array in bytes.
func (*BitArray) EncodedString ¶ added in v0.13.0
Returns the encoded string representation of the bit array.
func (*BitArray) EqualMSBs ¶ added in v0.13.0
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) IsBitSetFromLSB ¶ added in v0.13.0
Returns true if bit n-th is set, where n = 0 is LSB.
func (*BitArray) LSBs ¶ added in v0.13.0
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
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) MSBs ¶ added in v0.13.0
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
Sets the bit array to a sequence of ones of the specified length.
func (*BitArray) SetBytes ¶ added in v0.13.0
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
Sets the bit array to the bytes representation of a felt.
func (*BitArray) SetFelt251 ¶ added in v0.13.0
Sets the bit array to the bytes representation of a felt with length 251.
func (*BitArray) SetUint64 ¶ added in v0.13.0
Sets the bit array to the uint64 representation of a bit array.
func (*BitArray) String ¶ added in v0.13.0
Returns a string representation of the bit array. This is typically used for logging or debugging.
func (*BitArray) Subset ¶ added in v0.13.0
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
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
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]
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) HashFromParent ¶ added in v0.12.0
Hash calculates the hash of a Node
func (*Node) UnmarshalBinary ¶ added in v0.4.0
UnmarshalBinary deserializes a Node from a byte array
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) DeleteRootKey ¶ added in v0.4.0
func (*Storage) PutRootKey ¶ added in v0.4.0
func (*Storage) SyncedStorage ¶ added in v0.11.6
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 NewTriePoseidon ¶ added in v0.2.1
func (*Trie) FeltToKey ¶ added in v0.13.0
FeltToKey converts a key, given in felt, to a trie.Key which when followed on a Trie, leads to the corresponding Node
func (*Trie) GetNodeFromKey ¶ added in v0.11.8
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) 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) PutWithProof ¶ added in v0.12.0
Put updates the corresponding `value` for a `key`