Merkle Patricia Forestry

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

[![Licence](https://img.shields.io/github/license/aiken-lang/merkle-patricia-forestry?style=for-the-badge)](https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/LICENSE) [![Continuous Integration](https://img.shields.io/github/actions/workflow/status/aiken-lang/merkle-patricia-forestry/continuous-integration.yml?style=for-the-badge&label=continuous%20integration)](https://github.com/aiken-lang/merkle-patricia-forestry/actions/workflows/continuous-integration.yml) [![NPM](https://img.shields.io/npm/v/%40aiken-lang%2Fmerkle-patricia-forestry?style=for-the-badge)](https://www.npmjs.com/package/@aiken-lang/merkle-patricia-forestry)

## 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](https://github.com/aiken-lang/merkle-patricia-forestry/wiki/Technical-analysis). 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: - [x] membership (i.e. inclusion of key/value pairs) - [x] non-membership (i.e. exclusion of keys) - [x] insertion - [x] deletion - [x] update (i.e. deletation followed by insertion) ...of any key/value item in a large (billions) store. ## Getting Started ### Off-chain (JavaScript / Node.js) ```bash yarn add @aiken-lang/merkle-patricia-forestry ``` See [off-chain](https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain#readme) for usage. ### On-chain (Aiken) ```bash aiken add aiken-lang/merkle-patricia-forestry --version 2.1.0 ``` See [on-chain](https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/on-chain#readme) for usage. ## Performances This library implements a few optimizations. We borrow ideas from the [Ethereum's Modified Merkle Patricia Trie (MPT)](https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/) and also introduce a novel approach for organizing nodes as tiny [Sparse Merkle Trees](https://eprint.iacr.org/2016/683.pdf) 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](https://github.com/aiken-lang/merkle-patricia-forestry/wiki/Technical-analysis#forestry). 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.

aiken-lang/merkle-patricia-forestry

Contributors

Latest Releases

Repository Info

Watching