Skip to content

aiken-lang/merkle-patricia-forestry

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

73 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Merkle Patricia Forestry

Merkle Patricia Forestry

A set of (on-chain & off-chain) libraries for working with Merkle Patricia Tries on Cardano.


Licence Continuous Integration NPM


Overview

A Merkle Patricia Trie is a persistent & authenticated data structure to map between arbitrary keys and values. It's like a hashmap on steroids, which isn't tamperable. The items are represented in a space-optimized trie (a.k.a prefix tree) of radix 16. The hash digest of their keys gives the path to values in the trie. For more details, read the wiki.

The use cases are numerous, such as maintaining large on-chain registries (e.g. domains) or providing unreasonably large oracled datasets of intrinsic data (e.g. a map of delegators/delegatees) or extrinsic data (e.g. GitHub data pertaining to an ecosystem of projects). It's also perfectly suited for long-running datasets that grow at a slow rate (e.g. a PoW blockchain).

Features

Using only a root hash digest (32 bytes) and a succinct proof (<1KB), Merkle Patricia Tries provides rapid:

  • membership
  • insertion
  • deletion

...of any key/value item in a large (billions) store.

Getting Started

Off-chain (JavaScript / Node.js)

yarn add @aiken-lang/merkle-patricia-forestry

See off-chain for usage.

On-chain (Aiken)

aiken add aiken-lang/merkle-patricia-forestry --version 2.0.0

See on-chain for usage.

Performances

This library implements a few optimizations. We borrow ideas from the Ethereum's Modified Merkle Patricia Trie (MPT) and also introduce a novel approach for organizing nodes as tiny Sparse Merkle Trees that result in much smaller proof sizes, and gives the name to the structure: Merkle Patricia Forestry. This optimization and overall approach are covered in more detail in the wiki.

While this optimization sacrifices some memory and CPU execution units for smaller proof sizes, the library ultimately achieves a good trade-off. The table below summarizes the proof size, memory units, and CPU units for various sizes of tries. Note that the numbers in the table correspond to one proof verification (e.g., membership). Insertion and deletion in the trie both require two proof verifications, so double the numbers!

trie size avg proof size (bytes) avg proof mem units avg proof cpu units
10² 250 70K (0.70%) 18M (0.12%)
10³ 350 100K (1.00%) 26M (0.19%)
10⁴ 460 130K (1.30%) 35M (0.25%)
10⁵ 560 160K (1.60%) 44M (0.31%)
10⁶ 670 190K (1.90%) 53M (0.38%)
10⁷ 780 220K (2.20%) 62M (0.44%)
10⁸ 880 250K (2.50%) 71M (0.51%)
10⁹ 990 280K (2.80%) 79M (0.56%)

Note

On current mainnet, 140K mem units and 100M cpu units corresponds respectively to 1% of the maximum transaction mem and cpu budgets.