aiken/merkle_patricia_forestry
A Merkle Patricia Forestry (MPF) is a key:value structure which stores elements in a radix trie folowing a key, and where nodes also contains a cryptographic hash digest of the subtrie or value they hold.
This library enforces (through hashing) that we use trie of radix 16 (hexadecimal alphabet). This means that each level in the trie has up to 16 branches.
An MPF allows for checking membership, insertion and deletion in the trie using only root hashes and a succinct proofs. They are quite efficient in both cpu and mem units. And they also provide proofs that are a / lot smaller than traditional Merkle Patricia Trie; proofs remain however the / main limiting factor.
Here’s a little table that summarizes the average proof’s sizes in bytes given a number of elements.
We also consider the average memory and CPU execution units for verifying
a proof for various sizes. Note that insert
and
delete
require two proofs verifications.
size  avg proof size  avg proof mem  avg proof cpu 

10²  250  70K  28M 
10³  350  100K  42M 
10⁴  460  130K  56M 
10⁵  560  160K  70M 
10⁶  670  190K  84M 
10⁷  780  220K  98M 
10⁸  880  250K  112M 
10⁹  990  280K  126M 
Types
since  1.0.0 

A Merkle Patricia Forestry, typically constructed from a root hash digest
using from_root
.
let trie =
mpf.from_root(
#"225a4599b804ba53745538c83bfa699ecf8077201b61484c91171f5910a4a8f9",
)
since  1.0.0 

A neighbor node used in a proof. See Proof for details.
Constructors

Neighbor { nibble: Int, prefix: ByteArray, root: ByteArray }
since  1.0.0 

A Proof is a list of Step which is processed from left to right, which corresponds to the neighbor nodes along the path to the element being proved.
See merklepatriciaforestry/offchain :: Proving for details about generating a proof.
Alias
Proof = List<ProofStep>
since  1.0.0 

We distinguish three kind of proof steps: Branch, Fork and Leaf. Each step
contains a skip
value which corresponds to the length of the common prefix
at that particular level.
The details of each level is documented in the wiki :: Proof Format.
Constructors

Branch { skip: Int, neighbors: ByteArray }

Fork { skip: Int, neighbor: Neighbor }

Leaf { skip: Int, key: ByteArray, value: ByteArray }
Functions
delete(
self: MerklePatriciaForestry,
key: ByteArray,
value: ByteArray,
proof: Proof,
) > MerklePatriciaForestry
empty() > MerklePatriciaForestry
since  1.0.0 

Construct a new empty MerklePatriciaForestry.
from_root(root: ByteArray) > MerklePatriciaForestry
since  1.0.0 

Construct a new MerklePatriciaForestry from its root. Onchain, we actually only need the / root
The root MUST be 32bytes long. For an empty trie, see empty.
has(
self: MerklePatriciaForestry,
key: ByteArray,
value: ByteArray,
proof: Proof,
) > Bool
since  1.0.0 

Test whether an element is present in the trie with a specific value. This requires a Proof of inclusion for the element. The latter can be obtained offchain from the whole trie containing the element.
Returns False
when the element isn’t in the tree.
insert(
self: MerklePatriciaForestry,
key: ByteArray,
value: ByteArray,
proof: Proof,
) > MerklePatriciaForestry
is_empty(self: MerklePatriciaForestry) > Bool
root(self: MerklePatriciaForestry) > ByteArray
since  1.1.0 

Get the root hash digest of a MerklePatriciaForestry.
update(
self: MerklePatriciaForestry,
key: ByteArray,
proof: Proof,
old_value: ByteArray,
new_value: ByteArray,
) > MerklePatriciaForestry
since  1.1.0 

Update an element in the trie with a a new value. This requires a Proof of the old element, to ensure its in the list, and a Proof of the new element, to readd it.
Can be thought of as a delete, followed by an insert, but is able to do it with one fewer membership checks
fails when
 The Proof is invalid.
 There’s no element in the trie at the given key.