A set of (on-chain & off-chain) libraries for working with Merkle Patricia Tries on Cardano.
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).
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.
yarn add @aiken-lang/merkle-patricia-forestrySee off-chain for usage.
aiken add aiken-lang/merkle-patricia-forestry --version 2.0.0See on-chain for usage.
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.