Charles-Edouard LADARI

Thomas Liu

In the Gray Paper, Appendix D delves into the concept of the 

 for the entire system state. This article aims to simplify and explain these concepts, making them accessible to readers who may not be familiar with the technical details.

 (Practical Algorithm to Retrieve Information Coded in Alphanumeric) is a space-optimized version of a trie (prefix tree) that is used to store a mapping from keys to values. In the context of the Gray Paper, it is used to organize state components efficiently.

: Each key is represented as a sequence of bits (0s and 1s), forming a path from the root to a leaf node.

: Common prefixes are stored only once, reducing redundancy.

: Enables quick retrieval of values based on their keys.

The state components are encoded into binary paths using the 

 defined in Appendix D.1. These functions map state components to 32-byte sequences, which are then converted into bit sequences to form paths in the trie.

Here are the paths representing different state components:

[1, 1, 1, 1, 1, 1, 1, 1, s₁¹, s₁², ...]

The sequence of bits leads to a leaf node containing the encoded state component.

In a Patricia Trie, each state component is mapped to a 

 sequence, meaning each path would typically consist of 256 bits. However, the trie compresses these paths to eliminate unnecessary bits when only a single path exists.

For example, the full path that leads to 

, but the trie structure is compressed. Since there are no other branches, the trie doesn't traverse all the way through the remaining 0s. Instead, it terminates at the first few significant bits, which in this case is 

This compression mechanism makes the Patricia Trie more space-efficient and faster to traverse while retaining all the necessary information to map the path to its corresponding state component. The same applies to all other paths—only the necessary portion of the bit sequence is stored.

To better understand the structure, you can visualize the Patricia Trie using a graph. Each node represents a state in the traversal, and edges represent the bits (0 or 1). The leaves contain the encoded values.

The Merklization process involves computing a 

 from the leaf values, similar to how a regular Merkle tree works. However, in the Patricia Trie, there are special considerations for encoding leaves and branches.

 defined in Appendix D.1. This ensures that the path information is included in the encoding.

: The bit representation of the byte encoding the length of the value 

: The bit array is padded with zeros to reach 512 bits.

: Take the first 248 bits of the path encoding to include in the leaf encoding.

 to get the byte representation of the value's length.

: Pad the combined bits with zeros to reach 512 bits.

: Reverse the entire bit array (interpreted as bytes in little-endian order).

: Compute the hash of the reversed bit array to get the leaf hash.

: For the left side of a branch, the first bit is replaced with 

: Similar to leaves, the bit array is padded to 512 bits and reversed in little-endian order before hashing.

: Replace the first bit of the left side with 

: Pad the bit array to 512 bits with zeros.

: Reverse the bit array as bytes in little-endian order.

: Compute the hash to get the branch hash.

When computing the hash for a node that doesn't have a neighbor (i.e., no sibling node):

: The missing neighbor is assumed to have a hash value of zero.

: The hash of the parent node is computed using the existing child hash and the zero hash.

By applying the encoding and hashing procedures to all leaves and branches, you can compute the root hash of the Patricia Trie. This root hash serves as a cryptographic commitment to the entire system state, allowing for efficient and secure verification of any state component.

Given that the Patricia Trie representing the entire system state is too large to fit in memory, most implementations utilize a 

 to store the nodes. This allows the structure to scale efficiently, especially as the state grows over time.

The approach to storing nodes in the database is flexible, but most implementations follow a common pattern:

: Each node in the Patricia Trie is stored in the database, where the 

: The value stored for each node typically includes the 

. This allows for efficient reconstruction of the tree when needed without storing the full structure in memory.

By storing nodes this way, the Patricia Trie can be incrementally updated without requiring the entire structure to be kept in memory.

One of the most critical aspects of the Patricia Trie implementation is the 

efficient computation of the updated root hash

 whenever a leaf value is modified. Recomputing the entire Merkle root from all leaves would be highly inefficient, so instead, the trie is designed to update the root 

: When a leaf node is modified (for example, when an account balance changes), only the hashes along the path from that leaf to the root need to be recomputed.

: The hash of each parent node along the path is updated based on the new hashes of its children, working upwards to the root. Since this process only affects the path from the updated leaf to the root, it minimizes the number of nodes that need to be recomputed, significantly reducing the computational complexity.

Providing Merkle Proofs for Light Clients

Storing node hashes as keys in the database (rather than storing the full paths as keys) provides another important benefit: it enables the node to 

Since the hash of each node (and its children) is stored, the node can generate cryptographic proofs for specific parts of the state.

This allows light clients to verify the inclusion (or exclusion) of specific data in previous states, without needing access to the full state tree.

This method of storage ensures that the Patricia Trie remains scalable, efficient, and capable of supporting light clients with cryptographic guarantees, even as the system state evolves over time.

Patricia Trie: Key to Efficient State Management in JAM Protocol