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 (i.e. inclusion of key/value pairs)
- non-membership (i.e. exclusion of keys)
- insertion
- deletion
- update (i.e. deletation followed by insertion)
...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.1.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 and operations. On top of that, including the MPF library as a dependency adds ~2.5KB of generated UPLC.
| size | proof size (bytes) | insert or delete | update | membership | non-membership |
|---|---|---|---|---|---|
| 10² | ~200 | mem: 188.5K cpu: 53.9M |
mem: 222.5K cpu: 64.5M |
mem: 111.3K cpu: 32.3M |
mem: 77.3K cpu: 21.6M |
| 10³ | ~340 | mem: 252.5K cpu: 72M |
mem: 284.5K cpu: 82M |
mem: 142.3K cpu: 41M |
mem: 110.3K cpu: 31M |
| 10⁴ | ~480 | mem: 316.5K cpu: 90.1M |
mem: 346.5K cpu: 99.5M |
mem: 173.3K cpu: 49.8M |
mem: 143.3K cpu: 40.3M |
| 10⁵ | ~620 | mem: 380.5K cpu: 108.2M |
mem: 408.5K cpu: 117M |
mem: 204.3K cpu: 58.5M |
mem: 176.3K cpu: 49.7M |
| 10⁶ | ~760 | mem: 444.5K cpu: 126.3M |
mem: 470.5K cpu: 134.5M |
mem: 235.3K cpu: 67.3M |
mem: 209.3K cpu: 59M |
| 10⁷ | ~900 | mem: 508.5K cpu: 144.4M |
mem: 532.5K cpu: 152M |
mem: 266.3K cpu: 76M |
mem: 242.3K cpu: 68.4M |
| 10⁸ | ~1040 | mem: 572.5K cpu: 162.5M |
mem: 594.5K cpu: 169.5M |
mem: 297.3K cpu: 84.8M |
mem: 275.3K cpu: 77.7M |
| 10⁹ | ~1180 | mem: 636.5K cpu: 180.6M |
mem: 656.5K cpu: 187M |
mem: 328.3K cpu: 93.5M |
mem: 308.3K cpu: 87.1M |
Note
On current mainnet, 140K mem units and 100M cpu units corresponds respectively to 1% of the maximum transaction mem and cpu budgets.