Merkle Patricia Forestry

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

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 use aiken-lang/merkle-patricia-forestry --version 1.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	28M
10³	350	100K	42M
10⁴	460	130K	56M
10⁵	560	160K	70M
10⁶	670	190K	84M
10⁷	780	220K	98M
10⁸	880	250K	112M
10⁹	990	280K	126M

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 Goto Github PK