merkle-patricia-forestry vmain/on-chain

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.

sizeavg proof sizeavg proof memavg proof cpu
10²25070K28M
10³350100K42M
10⁴460130K56M
10⁵560160K70M
10⁶670190K84M
10⁷780220K98M
10⁸880250K112M
10⁹990280K126M

Types

MerklePatriciaForestry

since1.0.0

A Merkle Patricia Forestry, typically constructed from a root hash digest using from_root.

let trie =
  mpf.from_root(
    #"225a4599b804ba53745538c83bfa699ecf8077201b61484c91171f5910a4a8f9",
  )

Neighbor

since1.0.0

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

Constructors

  • Neighbor { nibble: Int, prefix: ByteArray, root: ByteArray }

Proof

since1.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>

ProofStep

since1.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

from_root(root: ByteArray) -> MerklePatriciaForestry

since1.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.

empty() -> MerklePatriciaForestry

since1.0.0

Construct a new empty MerklePatriciaForestry.

Querying

is_empty(self: MerklePatriciaForestry) -> Bool

since1.0.0

Check whether a MerklePatriciaForestry is empty.

mpf.is_empty(mpf.empty()) == True


has(
  self: MerklePatriciaForestry,
  key: ByteArray,
  value: ByteArray,
  proof: Proof,
) -> Bool

since1.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

insert(
  self: MerklePatriciaForestry,
  key: ByteArray,
  value: ByteArray,
  proof: Proof,
) -> MerklePatriciaForestry

since1.0.0

Insert an element in the trie. This requires a Proof of inclusion for the element. The latter can be obtained off-chain from the whole trie containing the element.

Fails when

  • The Proof is invalid.
  • There’s already an element in the trie at the given key.

delete(
  self: MerklePatriciaForestry,
  key: ByteArray,
  value: ByteArray,
  proof: Proof,
) -> MerklePatriciaForestry

since1.0.0

Remove an element from the trie. This requires a Proof of inclusion for the element. The latter can be obtained off-chain from the whole trie containing the element.

Fails when

  • the Proof is invalid
  • there’s already an element in the trie at the given key

update(
  self: MerklePatriciaForestry,
  key: ByteArray,
  proof: Proof,
  old_value: ByteArray,
  new_value: ByteArray,
) -> MerklePatriciaForestry

since1.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

root(self: MerklePatriciaForestry) -> ByteArray

since1.1.0

Get the root hash digest of a MerklePatriciaForestry.

Search Document