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 (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.

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.1.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 and operations. On top of that, including the MPF library as a dependency adds ~2.5KB of generated UPLC.

[!NOTE]

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