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 sub-trie 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 merkle-patricia-forestry/off-chain :: 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
Constructing
since 1.0.0
Construct a new MerklePatriciaForestry from its
root. On-chain, we actually only need the / root
The root MUST be 32-bytes long. For an empty trie, see empty.
since 1.0.0
Construct a new empty MerklePatriciaForestry.
Querying
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 off-chain from the whole trie containing the element.
Returns False
when the element isn’t in the tree.
Modifying
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 re-add 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.
Transforming
since 1.1.0
Get the root hash digest of a MerklePatriciaForestry.
since | 1.0.0 |
---|
Construct a new MerklePatriciaForestry from its root. On-chain, we actually only need the / root
The root MUST be 32-bytes long. For an empty trie, see empty.
since | 1.0.0 |
---|
Construct a new empty MerklePatriciaForestry.
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 off-chain from the whole trie containing the element.
Returns False
when the element isn’t in the tree.
Modifying
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 re-add 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.
Transforming
since 1.1.0
Get the root hash digest of a MerklePatriciaForestry.
since | 1.1.0 |
---|
Get the root hash digest of a MerklePatriciaForestry.