Module smoldot::trie

Radix-16 Merkle-Patricia trie.

This Substrate/Polkadot-specific radix-16 Merkle-Patricia trie is a data structure that associates keys with values, and that allows efficient verification of the integrity of the data.

Overview

The key-value storage that the blockchain maintains is represented by a tree, where each key-value pair in the storage corresponds to a node in that tree.

Each node in this tree has what is called a Merkle value associated to it. This Merkle value consists, in its essence, in the combination of the storage value associated to that node and the Merkle values of all of the node’s children. If the resulting Merkle value would be too long, it is first hashed.

Since the Merkle values of a node’s children depend, in turn, of the Merkle value of their own children, we can say that the Merkle value of a node depends on all of the node’s descendants.

Consequently, the Merkle value of the root node of the tree depends on the storage values of all the nodes in the tree.

See also the Wikipedia page for Merkle tree for a different explanation.

Efficient updates

When a storage value gets modified, the Merkle value of the root node of the tree also gets modified. Thanks to the tree layout, we don’t need to recalculate the Merkle value of the entire tree, but only of the ancestors of the node which has been modified.

If the storage consists of N entries, recalculating the Merkle value of the trie root requires on average only log16(N) operations.

Proof of storage entry

In the situation where we want to know the storage value associated to a node, but we only know the Merkle value of the root of the trie, it is possible to ask a third-party for the unhashed Merkle values of the desired node and all its ancestors. This is called a Merkle proof.

After having verified that the third-party has provided correct values, and that they match the expected root node Merkle value known locally, we can extract the storage value from the Merkle value of the desired node.

Details

This data structure is a tree composed of nodes, each node being identified by a key. A key consists in a sequence of 4-bits values called nibbles. Example key: [3, 12, 7, 0].

Some of these nodes contain a value.

A node A is an ancestor of another node B if the key of A is a prefix of the key of B. For example, the node whose key is [3, 12] is an ancestor of the node whose key is [3, 12, 8, 9]. B is a descendant of A.

Nodes exist only either if they contain a value, or if their key is the longest shared prefix of two or more nodes that contain a value. For example, if nodes [7, 2, 9, 11] and [7, 2, 14, 8] contain a value, then node [7, 2] also exist, because it is the longest prefix shared between the two.

The Merkle value of a node is composed, amongst other things, of its associated value and of the Merkle value of its descendants. As such, modifying a node modifies the Merkle value of all its ancestors. Note, however, that modifying a node modifies the Merkle value of only its ancestors. As such, the time spent calculating the Merkle value of the root node of a trie mostly depends on the number of modifications that are performed on it, and only a bit on the size of the trie.

Trie entry version

In the Substrate/Polkadot trie, each trie node that contains a value also has a version associated to it.

This version changes the way the hash of the node is calculated and how the Merkle proof is generated. Version 1 leads to more succinct Merkle proofs, which is important when these proofs are sent over the Internet.

Note that most of the time all the entries of the trie have the same version. However, it is possible for the trie to be in a hybrid state where some entries have a certain version and other entries a different version. For this reason, most of the trie-related APIs require you to provide a trie entry version alongside with the value.

Modules

• branch_search
  Allows searching for the closest branch node in a trie when only the storage trie nodes are known.
• calculate_root
  Freestanding function that calculates the root of a radix-16 Merkle-Patricia trie.
• prefix_proof
  Scanning, through trie proofs, the list of all keys that share a certain prefix.
• proof_decode
  Decodes and verifies a trie proof.
• proof_encode
• trie_node
• trie_structure
  Manages the structure of a trie. Allows inserting and removing nodes, but does not store any value. Only the structure is stored.

Structs

• BytesToNibbles
  Turns an iterator of bytes into an iterator of nibbles corresponding to these bytes.
• Nibble
  A single nibble with four bits.

Enums

• HashFunction
  Hash algorithm used during trie calculations.
• NibbleFromU8Error
  Error when building a Nibble from a u8.
• TrieEntryVersion
  The format of the nodes of trie has two different versions.

Constants

• EMPTY_BLAKE2_TRIE_MERKLE_VALUE
  Merkle value of the root node of an empty trie using HashFunction::Blake2.
• EMPTY_KECCAK256_TRIE_MERKLE_VALUE
  Merkle value of the root node of an empty trie using HashFunction::Keccak256.

Functions

• all_nibbles
  Returns an iterator of all possible nibble values, in ascending order.
• bytes_to_nibbles
  Turns an iterator of bytes into an iterator of nibbles corresponding to these bytes.
• nibbles_to_bytes_prefix_extend
  Turns an iterator of nibbles into an iterator of bytes.
• nibbles_to_bytes_suffix_extend
  Turns an iterator of nibbles into an iterator of bytes.
• nibbles_to_bytes_truncate
  Turns an iterator of nibbles into an iterator of bytes.
• ordered_root
  Returns the Merkle value of a trie containing the entries passed as parameter, where the keys are the SCALE-codec-encoded indices of these entries.
• trie_root
  Returns the Merkle value of a trie containing the entries passed as parameter. The entries passed as parameter are (key, value).