Skip to main content

​
Purpose and Scope

This document explains the Merkle Patricia Trie data structure used to store trie nodes in StableNet and the underlying database layer.
The trie provides a cryptographically authenticated key-value store with efficient lookups, proof generation, and deterministic root hash computation. Main topics covered:
  • Trie Structure: Node types (shortNode, fullNode, valueNode, hashNode) and tree composition
  • Node Encoding: Key encoding schemes (keybytes, hex, compact) and RLP serialization
  • Trie Database: Storage schemas (hash-based, path-based) and node persistence
  • Merkle Proofs: Proof generation, verification, and use cases
For how StateDB uses these tries for state management, see State Management.
For snapshot-based optimizations, see Caching and Snapshots.
For the ancient store handling historical block data, see Ancient Store and Data Lifecycle.

​
Merkle Patricia Trie Overview

The Merkle Patricia Trie is a cryptographically authenticated data structure that combines properties of Merkle trees and Patricia tries (radix trees). It enables:
  • Efficient key-value storage and lookup with O(log n) complexity
  • State commitment via Merkle root hashing
  • State proof generation without holding the entire state
  • Deterministic root computation where all nodes derive the same result
StableNet uses tries for two purposes:
  1. Account Trie
    Maps account addresses to account state (balance, nonce, storage root, code hash).
  2. Storage Trie
    Each contract account has an independent storage trie mapping storage slots to values.

​
Trie Node Types

​
Node Type Description

Node TypePurposeStructureUsage
shortNodeCommon prefix path compressionKey []byte, Val nodeWhen multiple keys share a prefix
fullNodeBranch nodeChildren [17]node16 nibble branches + value slot
valueNodeLeaf value[]byteStores the actual RLP-encoded value
hashNodeCompact reference32-byte hashReferences a sub-trie stored on disk
The nodeFlag structure manages the cache state of a node: 
type nodeFlag struct {
    hash  hashNode // cached hash of the node
    dirty bool     // whether the node has been modified
}

​
Key Encoding Schemes

The trie uses three key encoding formats for different purposes.

​
Encoding Formats

FormatDescriptionUsageExample (key = 0x123)
keybytesRaw bytesExternal APIs[0x12, 0x03]
hexNibble array + terminatorInternal trie operations[1, 2, 3, 16]
compactCompressed nibble formatSerialization / proofsnibbles + flag bits
The hex format represents each 4-bit nibble as a byte, where the value 16 indicates the end of the path.
The compact format compresses nibbles and encodes leaf/extension information and length in flag bits.

​
2-Trie Architecture

​
Account Trie

The account trie uses the Keccak256-hashed address as the key.
The value is the RLP-encoded types.StateAccount structure.

​
Storage Trie

Each contract has its own storage trie, structured as follows:
  • Owner: Keccak256 hash of the account address
  • Key: Keccak256 hash of the storage slot
  • Value: RLP-encoded storage value (leading zeros removed)

​
Trie Operations

​
Get Operation

Trie.get() recursively traverses nodes from the root.
When encountering a hashNode, it loads the referenced node from the database.

​
Update Operation

Updates do not immediately compute hashes. Nodes are marked dirty instead.
Actual hashing occurs during the commit phase, and the unhashed counter tracks the number of unhashed leaves.

​
Delete Operation

Delete removes a key-value pair.
Branch nodes with only a single remaining child are collapsed into a shortNode.

​
Hashing and Commit

​
Hasher Component

The hasher performs top-down hash computation:
  1. Recursively hash child nodes
  2. Collapse nodes into hashNode if the RLP-encoded size is ≥ 32 bytes
  3. Serialize the node structure with RLP
  4. Compute the Keccak256 hash
  5. Cache the result in nodeFlag.hash

​
Committer Component

The committer traverses the fully hashed trie and collects dirty nodes. Output:
trienode.NodeSet – a set mapping paths to node data, used for database writes.

​
State Root Calculation

The state root is calculated through the following steps:
  1. Finalise
    Move dirty storage to pending and update storage roots
  2. updateRoot()
    Apply per-account storage trie roots
  3. updateStateObject()
    Write account data into the account trie
  4. IntermediateRoot()
    Hash the account trie
  5. Commit()
    Commit all tries and generate the NodeSet

​
Proof Generation and Verification

​
Proof Structure

A Merkle proof consists of a sequence of RLP-encoded nodes from the root to a specific leaf.
  • Proof size: O(log n)
    Approximately 500–2000 bytes for Ethereum state
Use Cases:
  • Light client state verification
  • State synchronization
  • Storage proofs for cross-chain bridges

​
Trie Database Layer

The trie database layer persists trie nodes to disk and resolves hashNode or path-based references into actual nodes. StableNet supports two storage schemas.

​
Hash-Based Schema (Legacy)

Node key: Keccak256(RLP(node)) 
Key:   32-byte hash
Value: RLP-encoded node
Characteristics:
  • Simple key-value structure
  • No path information retained
  • Requires garbage collection
  • Inefficient for historical state access

​
Path-Based Schema (Modern)

Node key: owner_hash + path_from_root 
Key:   owner (32 bytes) + path
Value: RLP-encoded node
Characteristics:
  • Path-based addressing
  • Supports state history and fast rollbacks
  • Change tracking via diff layers
  • Suitable for archive nodes

​
Integration with State Management

​
Operation Flow

Account Access:
  1. Check StateDB cache
  2. Load from snapshot or account trie
  3. Decode types.StateAccount
  4. Create stateObject
Storage Access:
  1. Lookup in dirty → pending → origin order
  2. Fallback to storage trie on miss
  3. RLP decoding
Commit Flow:
  1. Finalise()
  2. updateRoot()
  3. updateStateObject()
  4. Commit()
  5. triedb.Update()

​
Key Implementation Details

​
Trie Prefetching

triePrefetcher asynchronously preloads nodes likely to be accessed during transaction execution to reduce latency. 
- Spawn goroutines per storage trie
- Prefetch based on expected access paths
- Improves transaction execution performance

​
Node Iterator

nodeIterator traverses all trie nodes using a pre-order traversal. 
- Used for state synchronization
- Used for proof generation
- Lazily loads hashNodes
- Maintains path and stack

​
Tracer

tracer tracks trie modifications for use in path-based schemas and debugging. 
- Records insertions and deletions
- Maps access paths
- Essential component for path-based DB
Summary:
The Merkle Patricia Trie is the core cryptographic structure of the StableNet state store.
Through the dual account/storage trie design and flexible storage schemas, StableNet efficiently and securely supports historical state access and light client verification.