> ## Documentation Index
> Fetch the complete documentation index at: https://docs.stablenet.network/llms.txt
> Use this file to discover all available pages before exploring further.

# Database Layer and Merkle Patricia Trie

## 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](/en/core-architecture/3.3-state-management).\
For snapshot-based optimizations, see [Caching and Snapshots](/en/storage-architecture/9.2-caching-and-snapshots).\
For the ancient store handling historical block data, see [Ancient Store and Data Lifecycle](/en/storage-architecture/9.3-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 Type     | Purpose                        | Structure              | Usage                                |
| ------------- | ------------------------------ | ---------------------- | ------------------------------------ |
| **shortNode** | Common prefix path compression | `Key []byte, Val node` | When multiple keys share a prefix    |
| **fullNode**  | Branch node                    | `Children [17]node`    | 16 nibble branches + value slot      |
| **valueNode** | Leaf value                     | `[]byte`               | Stores the actual RLP-encoded value  |
| **hashNode**  | Compact reference              | 32-byte hash           | References a sub-trie stored on disk |

The `nodeFlag` structure manages the cache state of a node:

```text theme={null}
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

| Format       | Description               | Usage                    | Example (key = 0x123) |
| ------------ | ------------------------- | ------------------------ | --------------------- |
| **keybytes** | Raw bytes                 | External APIs            | `[0x12, 0x03]`        |
| **hex**      | Nibble array + terminator | Internal trie operations | `[1, 2, 3, 16]`       |
| **compact**  | Compressed nibble format  | Serialization / proofs   | nibbles + 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))`

```text theme={null}
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`

```text theme={null}
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.

```text theme={null}
- 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.

```text theme={null}
- 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.

```text theme={null}
- 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.