MerkleTrie
Merkle Trie operations providing key-value storage with cryptographic verification.
A Merkle Trie is a tree structure where:
- Keys are represented as Nibbles (4-bit sequences)
- Each node has a hash computed from its contents
- The root hash uniquely identifies the entire tree state
All operations are effectful and maintain state through MerkleTrieState, which tracks the root hash and accumulated differences.
Attributes
- See also
-
MerkleTrieNode for node structure
MerkleTrieState for state management
Nibbles for key representation
- Source
- MerkleTrie.scala
- Graph
-
- Supertypes
-
class Objecttrait Matchableclass Any
- Self type
-
MerkleTrie.type
Members list
Type members
Classlikes
Attributes
- Companion
- trait
- Source
- MerkleTrie.scala
- Supertypes
-
trait Sumtrait Mirrorclass Objecttrait Matchableclass Any
- Self type
-
StrictTraversalError.type
Typed failures returned by strict trie traversal APIs.
Typed failures returned by strict trie traversal APIs.
Attributes
- Companion
- object
- Source
- MerkleTrie.scala
- Supertypes
-
trait Serializabletrait Producttrait Equalsclass Objecttrait Matchableclass AnyShow all
- Known subtypes
-
class MissingNodeclass NodeStoreFailure
Identifies where a strict traversal failed to resolve a referenced node.
Identifies where a strict traversal failed to resolve a referenced node.
Attributes
- Source
- MerkleTrie.scala
- Supertypes
-
trait Enumtrait Serializabletrait Producttrait Equalsclass Objecttrait Matchableclass AnyShow all
Types
Storage layer for retrieving nodes by hash.
Storage layer for retrieving nodes by hash.
Type parameters
- F
-
the effect type
Attributes
- Source
- MerkleTrie.scala
Value members
Concrete methods
Retrieves a value by key from the Merkle Trie.
Retrieves a value by key from the Merkle Trie.
Traverses the trie from the root, following the nibble path to find the value associated with the given key.
Type parameters
- F
-
the effect type
Value parameters
- key
-
the key to look up
Attributes
- Returns
-
stateful computation returning the value if found
- Source
- MerkleTrie.scala
Computes the common prefix and remainders of two Nibbles.
Computes the common prefix and remainders of two Nibbles.
Finds the longest common prefix and splits both Nibbles accordingly.
Value parameters
- nibbles0
-
first Nibbles
- nibbles1
-
second Nibbles
Attributes
- Returns
-
(common prefix, remainder0, remainder1)
- Source
- MerkleTrie.scala
Retrieves the root node from state.
Retrieves the root node from state.
Checks the diff first, then falls back to the node store.
Type parameters
- F
-
the effect type
Value parameters
- ns
-
the node store
- state
-
the trie state
Attributes
- Returns
-
Some(node) if root exists, None otherwise
- Source
- MerkleTrie.scala
Retrieves the root node and its hash from state.
Retrieves the root node and its hash from state.
Checks the diff first, then falls back to the node store.
Type parameters
- F
-
the effect type
Value parameters
- ns
-
the node store
- state
-
the trie state
Attributes
- Returns
-
Some((node, hash)) if root exists, None otherwise
- Source
- MerkleTrie.scala
Inserts or updates a key-value pair in the Merkle Trie.
Inserts or updates a key-value pair in the Merkle Trie.
Updates the trie structure, creating or modifying nodes as needed. The state is updated with the new root hash and accumulated differences.
Type parameters
- F
-
the effect type
Value parameters
- key
-
the key to insert
- value
-
the value to associate with the key
Attributes
- Returns
-
stateful computation that updates the trie
- Source
- MerkleTrie.scala
Removes a key-value pair from the Merkle Trie.
Removes a key-value pair from the Merkle Trie.
Deletes the node at the given key and updates parent nodes. May collapse branches when they become unnecessary.
Type parameters
- F
-
the effect type
Value parameters
- key
-
the key to remove
Attributes
- Returns
-
stateful computation returning true if key was found and removed
- Source
- MerkleTrie.scala
Streams key-value pairs in reverse lexicographic order.
Streams key-value pairs in reverse lexicographic order.
Returns pairs starting with keyPrefix, up to (but not including) keyPrefix
- keySuffix if provided.
Type parameters
- F
-
the effect type
Value parameters
- keyPrefix
-
the key prefix (inclusive)
- keySuffix
-
optional suffix to limit the range (exclusive)
Attributes
- Returns
-
stateful computation returning a reverse stream of (key, value) pairs
- Source
- MerkleTrie.scala
Streams all key-value pairs starting from the given key.
Streams all key-value pairs starting from the given key.
Returns pairs in lexicographic order by key.
Type parameters
- F
-
the effect type
Value parameters
- key
-
the starting key (inclusive)
Attributes
- Returns
-
stateful computation returning a stream of (key, value) pairs
- Source
- MerkleTrie.scala
Strictly streams key-value pairs in reverse lexicographic order.
Strictly streams key-value pairs in reverse lexicographic order.
A non-empty root or referenced descendant that cannot be resolved is a typed failure rather than an empty or partial stream.
Attributes
- Source
- MerkleTrie.scala
Strictly streams all key-value pairs starting from the given key.
Strictly streams all key-value pairs starting from the given key.
Unlike streamFrom, a non-empty root or referenced descendant that cannot be resolved from the state diff or node store is returned as a typed StrictTraversalError.MissingNode failure.
Attributes
- Source
- MerkleTrie.scala