This package provides a Node.js backend for working with an authenticated key/value store, a.k.a Merkle Patricia Forestry. It comes with an out-of-the-box on-disk storage solution based on level.js, but it also has an in-memory store available for debugging.
The library provides ways of constructing the trie incrementally (by inserting items into it) while keeping a low memory footprint. By default, only the topmost node is kept in memory, and children are only references to nodes stored on disk.
This package also allows producing succinct proofs for items, thus allowing the proof of membership, insertion, and deletion of items in the trie only from root hashes (and proofs!).
yarn add @aiken-lang/merkle-patricia-forestry
You can construct a new trie using new Trie, providing an (optional) store as a parameter. Using an on-disk store for non-trivial tries is strongly recommended, so only omit this argument for dummy scenarios.
import { Store, Trie } from '@aiken-lang/merkle-patricia-forestry';
// Construct a new trie with on-disk storage under the file path 'db'.
const trie = new Trie(new Store('db'));With
Item = { key: string|Buffer, value: string|Buffer }
Using Trie. fromList, you can rapidly bootstrap a new trie from many items. This method is convenient for small tries and rapid prototyping. The store is optional and defaults to in-memory when omitted.
const trie = await Trie.fromList([
{ key: 'apple', value: '🍎'},
{ key: 'blueberry', value: '🫐'},
{ key: 'cherries', value: '🍒'},
{ key: 'grapes', value: '🍇'},
{ key: 'tangerine', value: '🍊'},
{ key: 'tomato', value: '🍅'},
]);While Trie.fromList provides a convenient way to create small tries, mainly for testing purposes, the primary way of constructing tries is by repeatedly calling .insert for each item to insert. It returns the same reference to the trie as a Promise for convenience.
Note that you can only insert one item at a time, so make sure to await promises before attempting a new insert. Not doing so will trigger an exception. An exception is also raised when trying to insert an item at an already-known key. Delete first!
// Insert items one-by-one
await trie.insert('apple', '🍎');
await trie.insert('blueberry', '🫐');
await trie.insert('cherries', '🍒');
await trie.insert('grapes', '🍇');
await trie.insert('tangerine', '🍊');
await trie.insert('tomato', '🍅');
// Insert many items
const items = [
{ key: 'apple', value: '🍎'},
{ key: 'blueberry', value: '🫐'},
{ key: 'cherries', value: '🍒'},
{ key: 'grapes', value: '🍇'},
{ key: 'tangerine', value: '🍊'},
{ key: 'tomato', value: '🍅'},
];
await items.reduce(async (trie, { key, value }) => {
return (await trie).insert(key, value);
}, trie);Tip
Both the key and value must be either strings or byte Buffer. When a string is provided, it is treated as a UTF-8 byte Buffer.
Similarly, the reverse operation delete is available to remove elements from the trie. It fails with an exception if the given key is not in the trie. For convenience, it returns the same reference to the trie as a Promise.
// Remove 'apple'
await trie.delete('apple');
// Throws an exception, apple is no longer in the trie.
await trie.delete('apple');Tip
The key must be either strings or byte Buffer. When a string is provided, it is treated as a UTF-8 byte Buffer.
Using Trie. load, you can load any previously constructed trie back from disk. In this case, the store argument must be provided.
import { Store, Trie } from '@aiken-lang/merkle-patricia-forestry';
// Construct a new trie with on-disk storage under the file path 'db'.
const trie = await Trie.load(new Store('db'));You can inspect any trie using the util.inspect from Node.js or simply by calling console.log:
console.log(trie);
// ╔═══════════════════════════════════════════════════════════════════╗
// ║ #ee54d685370064b61cd8921f8476e54819990a67f6ebca402d1280ba1b03c75f ║
// ╚═══════════════════════════════════════════════════════════════════╝
// ┌─ 0 #33af5a3bbf8f
// ├─ 1 #a38f7e65ebf6
// ├─ 3 #ac9d183ca637
// └─ 9 #75eba4e4dae1The output is a pretty-printed visualisation of the tree, with the entire root hash first in a box, followed by the rest of the trie. For each sub-trie, a summary of their hashes is shown using a pound sign (e.g. #eceea58af726) as well as the branch path and prefix, if any, that leads to that point.
For leaves, the remaining path (a.k.a suffix) is shown but truncated for brevity. The output also includes the key/value pertaining to that leaf.
Finally, the function is synchronous and thus doesn't have access to children beyond their hashes. You can, however, fetch more children using:
The depth parameter is optional and must be a positive integer when provided. It corresponds to the number of sub-levels to fetch.
await trie.fetchChildren(2);
console.log(trie);
// ╔═══════════════════════════════════════════════════════════════════╗
// ║ #ee54d685370064b61cd8921f8476e54819990a67f6ebca402d1280ba1b03c75f ║
// ╚═══════════════════════════════════════════════════════════════════╝
// ┌─ 09ad7..[55 digits]..19d9 #33af5a3bbf8f { apple → 🍎 }
// ├─ 1 #a38f7e65ebf6
// │ ├─ b021f..[54 digits]..2290 #e5f9beffc856 { tomato → 🍅 }
// │ └─ e7b4b..[54 digits]..0675 #b5e92076b81f { cherries → 🍒 }
// ├─ 39cd4..[55 digits]..9e65 #ac9d183ca637 { blueberry → 🫐 }
// └─ 9 #75eba4e4dae1
// ├─ 702e3..[54 digits]..3a28 #c8b244fad188 { grapes → 🍇 }
// └─ b19ae..[54 digits]..962c #830b96edc35b { tangerine → 🍊 }Tip
To retrieve the entire trie, use Number.MAX_SAFE_INTEGER. But be careful, for large tries may not fit in memory!
To replace children with references again, use trie.save().
await trie.save();
console.log(trie);
// ╔═══════════════════════════════════════════════════════════════════╗
// ║ #ee54d685370064b61cd8921f8476e54819990a67f6ebca402d1280ba1b03c75f ║
// ╚═══════════════════════════════════════════════════════════════════╝
// ┌─ 0 #33af5a3bbf8f
// ├─ 1 #a38f7e65ebf6
// ├─ 3 #ac9d183ca637
// └─ 9 #75eba4e4dae1Note
There's, in principle, no need to manually save the trie otherwise. Operations on the trie such as insert or remove automatically modify the store.
You can efficiently fetch any value from the trie from its key using the trie.get method.
await trie.get('cherries');
// 🍒
await trie.get('cherrie');
// undefinedYou can retrieve any child from the trie at a given path. A path is a sequence of hexadecimal digits (a.k.a nibbles) given by the hash digest (blake2b-256) of the key, encoded in base16.
import blake2b from 'blake2b';
// Manually constructed, from a plain string prefix.
const cherries = await trie.childAt('1e');
// 7b4b..[54 digits]..0675 #b5e92076b81f { cherries → 🍒 }
const none = await trie.childAt('ffff');
// undefined
// Using the hash digest
const apple = await trie.childAt(
blake2b(32).update(Buffer.from('apple')).digest('hex')
);
// 9ad7..[55 digits]..19d9 #33af5a3bbf8f { apple → 🍎 }Let's get to the exciting part! The whole point of building a Merkle Patricia Forestry is to provide succinct proofs for items. A proof is portable and bound to both:
- A specific item
- A specific trie
Proofs are only valid for a precise trie root hash and state. So inserting (resp. removing) any item into (resp. from) the trie will invalidate any previously generated proof.
const proofTangerine = await trie.prove('tangerine');
// Proof {}A proof can be verified by calling .verify on it. The verification is fully synchronous and yields a hash as a byte Buffer. If that hash matches the trie root hash, the proof is valid.
proofTangerine.verify().equals(trie.hash);
// trueProofs can be computed in two manners. By default, they include the item in the proof, thus checking for inclusion in the trie. However, by setting includingItem to false, the proof will check for exclusion and yield the root hash of the trie without the item.
const previousHash = trie.hash;
await trie.insert('banana', '🍌');
const proofBanana = await trie.prove('banana');
proofBanana.verify(true).equals(trie.hash);
// true
proofBanana.verify(false).equals(previousHash);
// trueTip
Hence, you insert an element in the trie from just a proof and a current root hash (without the item), yielding a new root hash that includes just the item.
function insert(root, proof) {
assert(proof.verify(false).equals(root));
return proof.verify(true);
}Proofs are opaque but can be serialised into various formats, such as JSON. The proof format is explained in greater detail in the wiki.
proofTangerine.toJSON();
// [
// {
// type: 'branch',
// skip: 0,
// neighbors: '17a27bc4ce61078d26372800d331d6b8c4b00255080be66977c78b1554aabf8985c09af929492a871e4fae32d9d5c36e352471cd659bcdb61de08f17
// 22acc3b10eb923b0cbd24df54401d998531feead35a47a99f4deed205de4af81120f97610000000000000000000000000000000000000000000000000000000000000000
// '
// },
// {
// type: 'leaf',
// skip: 0,
// neighbor: {
// key: '9702e39845bfd6e0d0a5b6cb4a3a1c25262528c11bcff857867a50a0670e3a28',
// value: 'b5898c51c32083e91b8c18c735d0ba74e08f964a20b1639c189d1e8704b78a09'
// }
// }
// ]JSON is cool, but proofs are ultimately meant to be passed on-chain as redeemer or datum. Thus, we provide a method .toCBOR to serialise a proof into a format compatible with the on-chain expectations.
proofTangerine.toCBOR().toString('hex');
// 9fd8799f005f58404be28f4839135e1f8f5372a90b54bb7bfaf997a5d13711bb4d7d93f9d4e04fbefa63eb4576001d8658219f928172eccb5448b4d7d62cd6d95228e13ebcbd53505840c1e96bcc431893eef34e03989814375d439faa592edf75c9e5dc10b3c30766700000000000000000000000000000000000000000000000000000000000000000ffffffFor convenience, you can also generate Aiken code that works with the on-chain part of the library using .toAiken.
proofTangerine.toAiken();
// [
// Branch { skip: 0, neighbors: #"17a27bc4ce61078d26372800d331d6b8c4b00255080be66977c78b1554aabf8985c09af929492a871e4fae32d9d5c36e352471c
// d659bcdb61de08f1722acc3b10eb923b0cbd24df54401d998531feead35a47a99f4deed205de4af81120f976100000000000000000000000000000000000000000000000
// 00000000000000000" },
// Leaf { skip: 0, key: #"9702e39845bfd6e0d0a5b6cb4a3a1c25262528c11bcff857867a50a0670e3a28", value: #"b5898c51c32083e91b8c18c735d0ba74e08
// f964a20b1639c189d1e8704b78a09" },
// ]