### Install Merkle Patricia Forestry Package

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Installs the @aiken-lang/merkle-patricia-forestry package using yarn.

```bash
yarn add @aiken-lang/merkle-patricia-forestry
```

--------------------------------

### Merkle Patricia Forestry - Installation

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/on-chain/README.md

Instructions on how to install the Merkle Patricia Forestry Aiken library.

```APIDOC
## Installation

```bash
aiken add aiken-lang/merkle-patricia-forestry --version 2.1.0
```
```

--------------------------------

### Merkle Patricia Forestry - Example Usage

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/on-chain/README.md

An example demonstrating the usage of Merkle Patricia Forestry primitives like `from_root`, `insert`, and `delete` with a fruit map.

```APIDOC
## Examples

A non-trivial example of a [fruit map](https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/on-chain/lib/aiken/merkle-patricia-forestry.tests.ak#L90) is available in the source. It illustrate how to use the various `from_root`, `has`, `insert` and `delete` primitives.

```aiken
test insert_bitcoin_block_845602() {
  let trie =
    mpf.from_root(
      #"225a4599b804ba53745538c83bfa699ecf8077201b61484c91171f5910a4a8f9",
    )

  let block_hash =
    #"0000000000000000000261a131bf48cc5a19658ade8cfede99dc1c3933300d60"

  let block_body =
    #"26f711634eb26999169bb927f629870938bb4b6b4d1a078b44a6b4ec54f9e8df"

  mpf.insert(trie, block_hash, block_body, proof_bitcoin_845602()) == mpf.from_root(
    #"507c03bc4a25fd1cac2b03592befa4225c5f3488022affa0ab059ca350de2353",
  )
}

fn proof_bitcoin_845602() -> Proof {
  [
    Branch {
      skip: 0,
      neighbors: #"bc13df27a19f8caf0bf922c900424025282a892ba8577095fd35256c9d553ca120b8645121ebc9057f7b28fa4c0032b1f49e616dfb8dbd88e4bffd7c0844d29b011b1af0993ac88158342583053094590c66847acd7890c86f6de0fde0f7ae2479eafca17f9659f252fa13ee353c879373a65ca371093525cf359fae1704cf4a",
    },
    Branch {
      skip: 0,
      neighbors: #"255753863960985679b4e752d4b133322ff567d210ffbb10ee56e51177db057460b547fe42c6f44dfef8b3ecee35dfd4aa105d28b94778a3f1bb8211cf2679d7434b40848aebdd6565b59efdc781ffb5ca8a9f2b29f95a47d0bf01a09c38fa39359515ddb9d2d37a26bccb022968ef4c8e29a95c7c82edcbe561332ff79a51af",
    },
    Branch {
      skip: 0,
      neighbors: #"9d95e34e6f74b59d4ea69943d2759c01fe9f986ff0c03c9e25ab561b23a413b77792fa78d9fbcb98922a4eed2df0ed70a2852ae8dbac8cff54b9024f229e66629136cfa60a569c464503a8b7779cb4a632ae052521750212848d1cc0ebed406e1ba4876c4fd168988c8fe9e226ed283f4d5f17134e811c3b5322bc9c494a598b",
    },
    Branch {
      skip: 0,
      neighbors: #"b93c3b90e647f90beb9608aecf714e3fbafdb7f852cfebdbd8ff435df84a4116d10ccdbe4ea303efbf0f42f45d8dc4698c3890595be97e4b0f39001bde3f2ad95b8f6f450b1e85d00dacbd732b0c5bc3e8c92fc13d43028777decb669060558821db21a9b01ba5ddf6932708cd96d45d41a1a4211412a46fe41870968389ec96",
    },
    Branch {
      skip: 0,
      neighbors: #"f89f9d06b48ecc0e1ea2e6a43a9047e1ff02ecf9f79b357091ffc0a7104bbb260908746f8e61ecc60dfe26b8d03bcc2f1318a2a95fa895e4d1aadbb917f9f2936b900c75ffe49081c265df9c7c329b9036a0efb46d5bac595a1dcb7c200e7d590000000000000000000000000000000000000000000000000000000000000000",
    },
  ]
}

> [!WARNING]
> The proofs themselves have been generated from a trie built with the [off-chain package](../off-chain). While theoretically possible, the Aiken library doesn't contain any primitives for constructing tries _on-chain_, even for debugging.
```

--------------------------------

### Example Usage: Constructing and Modifying a Trie

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Provides practical examples of how to use the Trie class for common operations like initialization, insertion, and deletion.

```APIDOC
## Example Usage: Constructing and Modifying a Trie

### Initialize Trie with On-Disk Store

```js
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'));
```

### Bootstrap Trie from a List

```js
const trie = await Trie.fromList([
  { key: 'apple', value: '🍎'},
  { key: 'blueberry', value: '🫐'},
  { key: 'cherries', value: '🍒'},
]);
```

### Incremental Insertion

```js
// Insert items one-by-one
await trie.insert('apple', '🍎');
await trie.insert('blueberry', '🫐');

// Insert many items using reduce
const items = [
  { key: 'cherries', value: '🍒'},
  { key: 'grapes', value: '🍇'},
];

await items.reduce(async (trie, { key, value }) => {
  return (await trie).insert(key, value);
}, trie);
```

### Deleting an Item

```js
// Remove 'apple'
await trie.delete('apple');

// Throws an exception, 'apple' is no longer in the trie.
// await trie.delete('apple');
```

### Loading a Trie from Disk

```js
import { Store, Trie } from '@aiken-lang/merkle-patricia-forestry';

// Load a trie from the 'db' directory
const trie = await Trie.load(new Store('db'));
```

> **Note**: Both keys and values can be `string` or `Buffer`. Strings are treated as UTF-8 encoded Buffers.
```

--------------------------------

### Aiken Example: Insert Bitcoin Block into Merkle Patricia Trie

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/on-chain/README.md

Illustrates the insertion of a Bitcoin block's hash and body into a Merkle Patricia trie using the `mpf.from_root` and `mpf.insert` functions. It verifies the resulting trie's root hash against an expected value. This example relies on a `proof_bitcoin_845602` function to provide the necessary proof data.

```aiken
test insert_bitcoin_block_845602() {
  let trie =
    mpf.from_root(
      #"225a4599b804ba53745538c83bfa699ecf8077201b61484c91171f5910a4a8f9",
    )

  let block_hash =
    #"0000000000000000000261a131bf48cc5a19658ade8cfede99dc1c3933300d60"

  let block_body =
    #"26f711634eb26999169bb927f629870938bb4b6b4d1a078b44a6b4ec54f9e8df"

  mpf.insert(trie, block_hash, block_body, proof_bitcoin_845602()) == mpf.from_root(
    #"507c03bc4a25fd1cac2b03592befa4225c5f3488022affa0ab059ca350de2353",
  )
}

fn proof_bitcoin_845602() -> Proof {
  [
    Branch {
      skip: 0,
      neighbors: #"bc13df27a19f8caf0bf922c900424025282a892ba8577095fd35256c9d553ca120b8645121ebc9057f7b28fa4c0032b1f49e616dfb8dbd88e4bffd7c0844d29b011b1af0993ac88158342583053094590c66847acd7890c86f6de0fde0f7ae2479eafca17f9659f252fa13ee353c879373a65ca371093525cf359fae1704cf4a",
    },
    Branch {
      skip: 0,
      neighbors: #"255753863960985679b4e752d4b133322ff567d210ffbb10ee56e51177db057460b547fe42c6f44dfef8b3ecee35dfd4aa105d28b94778a3f1bb8211cf2679d7434b40848aebdd6565b59efdc781ffb5ca8a9f2b29f95a47d0bf01a09c38fa39359515ddb9d2d37a26bccb022968ef4c8e29a95c7c82edcbe561332ff79a51af",
    },
    Branch {
      skip: 0,
      neighbors: #"9d95e34e6f74b59d4ea69943d2759c01fe9f986ff0c03c9e25ab561b23a413b77792fa78d9fbcb98922a4eed2df0ed70a2852ae8dbac8cff54b9024f229e66629136cfa60a569c464503a8b7779cb4a632ae052521750212848d1cc0ebed406e1ba4876c4fd168988c8fe9e226ed283f4d5f17134e811c3b5322bc9c494a598b",
    },
    Branch {
      skip: 0,
      neighbors: #"b93c3b90e647f90beb9608aecf714e3fbafdb7f852cfebdbd8ff435df84a4116d10ccdbe4ea303efbf0f42f45d8dc4698c3890595be97e4b0f39001bde3f2ad95b8f6f450b1e85d00dacbd732b0c5bc3e8c92fc13d43028777decb669060558821db21a9b01ba5ddf6932708cd96d45d41a1a4211412a46fe41870968389ec96",
    },
    Branch {
      skip: 0,
      neighbors: #"f89f9d06b48ecc0e1ea2e6a43a9047e1ff02ecf9f79b357091ffc0a7104bbb260908746f8e61ecc60dfe26b8d03bcc2f1318a2a95fa895e4d1aadbb917f9f2936b900c75ffe49081c265df9c7c329b9036a0efb46d5bac595a1dcb7c200e7d590000000000000000000000000000000000000000000000000000000000000000",
    },
  ]
}
```

--------------------------------

### Install Merkle Patricia Forestry Package

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/on-chain/README.md

Command to add the Merkle Patricia Forestry package to your Aiken project. Specifies the version to be installed.

```bash
aiken add aiken-lang/merkle-patricia-forestry --version 2.1.0
```

--------------------------------

### Construct Trie with On-Disk Store

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Demonstrates how to construct a new Trie instance using an on-disk store. The 'db' argument specifies the directory for storing trie data. This is recommended for non-trivial tries.

```javascript
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'));
```

--------------------------------

### Bootstrap Trie from List of Items

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Shows how to rapidly bootstrap a new Trie from an array of key-value items using the Trie.fromList static method. If no store is provided, it defaults to an in-memory store. This is convenient for small tries and rapid prototyping.

```javascript
const trie = await Trie.fromList([
  { key: 'apple', value: '🍎'},
  { key: 'blueberry', value: '🫐'},
  { key: 'cherries', value: '🍒'},
  { key: 'grapes', value: '🍇'},
  { key: 'tangerine', value: '🍊'},
  { key: 'tomato', value: '🍅'},
]);
```

--------------------------------

### Insert Element from Proof

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Demonstrates how to use a proof to verify a root hash and derive a new root hash that includes a specific item.

```javascript
function insert(root, proof) {
  assert(proof.verify(false).equals(root));
  return proof.verify(true);
}
```

--------------------------------

### Load Trie from Store

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Shows how to load a previously constructed trie from disk using the Trie.load static method. The 'store' argument must be provided, specifying the location of the trie data.

```javascript
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'));
```

--------------------------------

### GET /trie/value

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Retrieves a value associated with a specific key from the trie. Returns undefined if the key is not found.

```APIDOC
## GET /trie/value

### Description
Fetches a value from the trie based on the provided key. If the key does not exist, the operation returns undefined.

### Method
GET

### Parameters
#### Query Parameters
- **key** (string) - Required - The key to look up in the trie.

### Request Example
{ "key": "apple" }

### Response
#### Success Response (200)
- **value** (any) - The value associated with the key.

#### Response Example
{ "value": "🍎" }
```

--------------------------------

### Load Trie from Disk

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Shows how to persist a trie to a database store and reload it later. Requires a valid store path to initialize the database connection.

```javascript
import { Store, Trie } from '@aiken-lang/merkle-patricia-forestry';

const store = new Store('./my-database');
const trie = new Trie(store);
await trie.insert('apple', '🍎');
await trie.insert('banana', '🍌');

const loadedTrie = await Trie.load(new Store('./my-database'));
console.log(loadedTrie.hash.equals(trie.hash));

const value = await loadedTrie.get('apple');
console.log(value.toString());
```

--------------------------------

### Proof Reconstruction and Serialization

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Demonstrates how to reconstruct a Proof object from JSON and serialize it to CBOR and Aiken formats.

```APIDOC
## Proof Reconstruction and Serialization

### Description
Demonstrates how to reconstruct a Proof object from JSON and serialize it to CBOR and Aiken formats.

### Methods
#### `proof.fromJSON(key, value, steps): Proof`
Reconstructs a JavaScript Proof object from a serialized JSON value. Requires the original key/value pair.

#### `proof.toCBOR(): Buffer`
Serializes the proof into a CBOR-formatted Buffer, suitable for on-chain use.

#### `proof.toAiken(): string`
Generates Aiken code representing the proof, useful for on-chain smart contracts.

### Request Example (fromJSON)
```javascript
const proofTangerine = Proof.fronJSON(
  'tangerine',
  '🍊',
  [
    {
      type: 'branch',
      skip: 0,
      neighbors: '17a27bc4ce61078d26372800d331d6b8c4b00255080be66977c78b1554aabf8985c09af929492a871e4fae32d9d5c36e352471cd659bcdb61de08f17
  22acc3b10eb923b0cbd24df54401d998531feead35a47a99f4deed205de4af81120f97610000000000000000000000000000000000000000000000000000000000000000'
    },
    {
      type: 'leaf',
      skip: 0,
      neighbor: {
        key: '9702e39845bfd6e0d0a5b6cb4a3a1c25262528c11bcff857867a50a0670e3a28',
        value: 'b5898c51c32083e91b8c18c735d0ba74e08f964a20b1639c189d1e8704b78a09'
      }
    }
  ]
);
```

### Request Example (toCBOR)
```javascript
proofTangerine.toCBOR().toString('hex');
// 9fd8799f005f58404be28f4839135e1f8f5372a90b54bb7bfaf997a5d13711bb4d7d93f9d4e04fbefa63eb4576001d8658219f928172eccb5448b4d7d62cd6d95228e13ebcbd53505840c1e96bcc431893eef34e03989814375d439faa592edf75c9e5dc10b3c30766700000000000000000000000000000000000000000000000000000000000000000ffffff
```

### Request Example (toAiken)
```javascript
proofTangerine.toAiken();
```

### Response Example (toAiken)
```aiken
[
  Branch {
    skip: 0,
    neighbors: #"17a27bc4ce61078d26372800d331d6b8c4b00255080be66977c78b1554aabf8985c09af929492a871e4fae32d9d5c36e352471cd659bcdb61de08f1722acc3b10eb923b0cbd24df54401d998531feead35a47a99f4deed205de4af81120f97610000000000000000000000000000000000000000000000000000000000000000",
  },
  Leaf {
    skip: 0,
    key: #"9702e39845bfd6e0d0a5b6cb4a3a1c25262528c11bcff857867a50a0670e3a28",
    value: #"b5898c51c32083e91b8c18c735d0ba74e08f964a20b1639c189d1e8704b78a09",
  },
]
```
```

--------------------------------

### Trie Initialization

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Methods for creating new empty tries or bootstrapping them from existing datasets.

```APIDOC
## Initialize Trie

### Description
Creates a new Merkle Patricia Forestry trie instance. Supports both in-memory storage for testing and persistent on-disk storage for production environments.

### Method
Constructor

### Parameters
#### Request Body
- **store** (Store) - Optional - An instance of `Store` for persistent storage (e.g., level.js).

### Request Example
```javascript
const store = new Store('./my-database');
const trie = new Trie(store);
```

### Response
#### Success Response (200)
- **trie** (Object) - A new Trie instance ready for operations.

## Create Trie from List

### Description
Bootstraps a new trie from an array of key/value pairs.

### Method
Static Method

### Parameters
#### Request Body
- **items** (Array) - Required - An array of objects containing 'key' and 'value' properties.

### Request Example
```javascript
const trie = await Trie.fromList([{ key: 'apple', value: '🍎' }]);
```
```

--------------------------------

### Initialize Merkle Patricia Forestry in Aiken

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Demonstrates how to initialize a trie from a root hash or create an empty trie within an Aiken smart contract.

```aiken
use aiken/merkle_patricia_forestry as mpf

let trie = mpf.from_root(#"4acd78f345a686361df77541b2e0b533f53362e36620a1fdd3a13e0b61a3b078")
let empty_trie = mpf.empty
let is_empty = mpf.is_empty(empty_trie)
let root_hash = mpf.root(trie)
```

--------------------------------

### Update Proof Values in JavaScript

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Shows how to reuse an existing proof for a key when the value associated with that key changes, avoiding the need to regenerate the entire proof.

```javascript
import { Trie } from '@aiken-lang/merkle-patricia-forestry';

const trie = await Trie.fromList([
  { key: 'apple', value: '🍎' },
  { key: 'banana', value: '🍌' },
]);

const proof = await trie.prove('banana');
await trie.delete('banana');
await trie.insert('banana', '🍌🍌');

proof.setValue('🍌🍌');
console.log(proof.verify(true).equals(trie.hash));
```

--------------------------------

### Trie Construction

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Demonstrates different methods for constructing a Merkle Patricia Trie, including initialization with a store, bootstrapping from a list of items, and incremental insertion.

```APIDOC
## Trie Construction

### `new Trie(store?: Store): Trie`

Initializes a new Trie instance. An optional `Store` can be provided for persistent storage; otherwise, an in-memory store is used.

### `Trie.fromList(items: Array<Item>, store?: Store): Promise<Trie>`

Creates a new Trie and populates it with a list of key-value `Item`s. The `store` is optional and defaults to an in-memory store.

`Item` is defined as `{ key: string|Buffer, value: string|Buffer }`.

### `trie.insert(key: string|Buffer, value: string|Buffer) -> Promise<Trie>`

Inserts a single key-value pair into the Trie. This method should be awaited before subsequent insertions to avoid errors. It returns a Promise resolving to the Trie instance.

### `trie.delete(key: string|Buffer) -> Promise<Trie>`

Removes a key-value pair from the Trie. This method fails with an exception if the key does not exist. It returns a Promise resolving to the Trie instance.

### `Trie.load(store: Store): Promise<Trie>`

Loads a previously saved Trie from the specified `Store`. The `store` argument is mandatory for this operation.
```

--------------------------------

### Serialize and Deserialize Proofs in JavaScript

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Demonstrates how to generate a proof from a trie and serialize it into JSON, CBOR, Aiken code, and UPLC formats. It also shows how to reconstruct a proof from JSON to verify it against the trie.

```javascript
import { Trie, Proof } from '@aiken-lang/merkle-patricia-forestry';

const trie = await Trie.fromList([
  { key: 'apple', value: '🍎' },
  { key: 'banana', value: '🍌' },
]);

const proof = await trie.prove('banana');

const json = proof.toJSON();
const cborBytes = proof.toCBOR();
const aikenCode = proof.toAiken();
const uplcCode = proof.toUPLC();

const reconstructedProof = Proof.fromJSON('banana', '🍌', json);
console.log(reconstructedProof.verify(true).equals(trie.hash));
```

--------------------------------

### POST /trie/load

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Loads a trie structure from a persistent storage location on disk.

```APIDOC
## POST /trie/load

### Description
Initializes and loads an existing trie from a specified database store on disk.

### Method
POST

### Parameters
#### Request Body
- **path** (string) - Required - The file system path to the database store.

### Request Example
{ "path": "./my-database" }

### Response
#### Success Response (200)
- **status** (string) - Confirmation that the trie was loaded successfully.
```

--------------------------------

### Insert Item into Trie

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Illustrates the primary method of constructing a trie by repeatedly calling the .insert method for each item. It's crucial to await each insert promise before the next to avoid exceptions. Inserting an item at an already-known key will also raise an exception.

```javascript
// 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);
```

--------------------------------

### POST /trie/proof

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Generates a cryptographic proof for a key, supporting both membership and non-membership verification.

```APIDOC
## POST /trie/proof

### Description
Generates a proof for a specific key. This can be used to verify if a key exists in the trie or to prove its absence.

### Method
POST

### Parameters
#### Request Body
- **key** (string) - Required - The key to generate a proof for.
- **allowMissing** (boolean) - Optional - Set to true to generate a non-membership proof.

### Request Example
{ "key": "banana", "allowMissing": false }

### Response
#### Success Response (200)
- **proof** (object) - The generated cryptographic proof object.

#### Response Example
{ "proof": { "root": "...", "path": [...] } }
```

--------------------------------

### On-chain Serialization

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Proofs can be converted to CBOR for on-chain usage or generated as Aiken code for integration with on-chain smart contracts.

```javascript
proofTangerine.toCBOR().toString('hex');
proofTangerine.toAiken();
```

```aiken
[
  Branch {
    skip: 0,
    neighbors: #"17a27bc4ce61078d26372800d331d6b8c4b00255080be66977c78b1554aabf8985c09af929492a871e4fae32d9d5c36e352471cd659bcdb61de08f1722acc3b10eb923b0cbd24df54401d998531feead35a47a99f4deed205de4af81120f97610000000000000000000000000000000000000000000000000000000000000000",
  },
  Leaf {
    skip: 0,
    key: #"9702e39845bfd6e0d0a5b6cb4a3a1c25262528c11bcff857867a50a0670e3a28",
    value: #"b5898c51c32083e91b8c18c735d0ba74e08f964a20b1639c189d1e8704b78a09",
  },
]
```

--------------------------------

### Verify Membership in Aiken

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Shows how to verify that a specific key-value pair exists in the trie using a proof generated off-chain.

```aiken
use aiken/merkle_patricia_forestry.{Branch, Leaf, Proof} as mpf

let trie = mpf.from_root(#"4acd78f345a686361df77541b2e0b533f53362e36620a1fdd3a13e0b61a3b078")
let key = "apple[uid: 58]"
let value = "🍎"
let proof: Proof = [Branch { skip: 0, neighbors: #"..." }, Leaf { skip: 0, key: #"...", value: #"..." }]

let is_member = mpf.has(trie, key, value, proof)
```

--------------------------------

### Create Merkle Patricia Trie from List (JavaScript)

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Rapidly bootstraps a new trie from an array of key/value pairs. This is convenient for small tries and prototyping. Both keys and values can be strings or Buffers. The resulting trie will contain the provided data and its root hash will be computed.

```javascript
import { Trie } from '@aiken-lang/merkle-patricia-forestry';

// Create a trie from a list of fruits
const trie = await Trie.fromList([
  { key: 'apple', value: '🍎' },
  { key: 'blueberry', value: '🫐' },
  { key: 'cherry', value: '🍒' },
  { key: 'grapes', value: '🍇' },
  { key: 'tangerine', value: '🍊' },
  { key: 'tomato', value: '🍅' },
]);

console.log(trie.size);  // 6
console.log(trie.hash);  // Buffer containing the root hash

// Pretty-print the trie structure
console.log(trie);
// ╔═══════════════════════════════════════════════════════════════════╗
// ║ #ee54d685370064b61cd8921f8476e54819990a67f6ebca402d1280ba1b03c75f ║
// ╚═══════════════════════════════════════════════════════════════════╝
//  ┌─ 0 #33af5a3bbf8f
//  ├─ 1 #a38f7e65ebf6
//  ├─ 3 #ac9d183ca637
//  └─ 9 #75eba4e4dae1
```

--------------------------------

### Serialize and Deserialize Proofs

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Proofs can be serialized to JSON for storage or transport and reconstructed using the fromJSON method with the original key and value.

```javascript
proofTangerine.toJSON();
const proofTangerine = Proof.fronJSON('tangerine', '🍊', [...steps]);
```

--------------------------------

### Generate Non-Membership Proofs

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Demonstrates how to prove that a key is absent from the trie. These proofs can also be repurposed for future insertions.

```javascript
import { Trie } from '@aiken-lang/merkle-patricia-forestry';

const trie = await Trie.fromList([
  { key: 'apple', value: '🍎' },
  { key: 'banana', value: '🍌' },
]);

const proof = await trie.prove('melon', true);
const isExcluded = proof.verify(false).equals(trie.hash);
console.log('melon is not in trie:', isExcluded);

await trie.insert('melon', '🍈');
proof.setValue('🍈');
console.log(proof.verify(true).equals(trie.hash));
```

--------------------------------

### Create Merkle Patricia Trie (JavaScript)

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Constructs a new empty Merkle Patricia Forestry trie. Supports both in-memory and persistent on-disk storage using level.js. The Store keeps memory usage low by only holding the topmost node in memory.

```javascript
import { Store, Trie } from '@aiken-lang/merkle-patricia-forestry';

// Create an empty trie with in-memory storage (for testing)
const inMemoryTrie = new Trie();

// Create a trie with persistent on-disk storage (recommended for production)
const store = new Store('./my-database');
const persistentTrie = new Trie(store);

// Check if a trie is empty
console.log(inMemoryTrie.isEmpty()); // true
console.log(inMemoryTrie.hash);      // null (empty tries have no hash)
```

--------------------------------

### Generate Membership Proofs

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Covers the creation of cryptographic proofs to verify that a specific key exists within the trie. Proofs can be verified against the current root hash.

```javascript
import { Trie } from '@aiken-lang/merkle-patricia-forestry';

const trie = await Trie.fromList([
  { key: 'apple', value: '🍎' },
  { key: 'banana', value: '🍌' },
  { key: 'cherry', value: '🍒' },
]);

const proof = await trie.prove('banana');
const isValid = proof.verify(true).equals(trie.hash);
console.log('Proof is valid:', isValid);

const hashWithoutBanana = proof.verify(false);
```

--------------------------------

### Inspecting the Trie

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

You can inspect the trie's structure using Node.js's `util.inspect` or `console.log`. This provides a pretty-printed visualization of the tree, including root hash, branch paths, prefixes, and leaf key/value pairs. For leaves, the remaining path (suffix) is shown, truncated for brevity, along with the key/value.

```APIDOC
## Inspecting the Trie

### Description
Visualize the trie's structure using `console.log` or `util.inspect`. The output shows the root hash, branch paths, prefixes, and leaf details (key/value, truncated suffix).

### Method
Synchronous (console.log, util.inspect)

### Endpoint
N/A (In-memory operation)

### Request Example
```javascript
console.log(trie);
```

### Response Example
```
// ╔═══════════════════════════════════════════════════════════════════╗
// ║ #ee54d685370064b61cd8921f8476e54819990a67f6ebca402d1280ba1b03c75f ║
// ╚═══════════════════════════════════════════════════════════════════╝
//  ┌─ 0 #33af5a3bbf8f
//  ├─ 1 #a38f7e65ebf6
//  ├─ 3 #ac9d183ca637
//  └─ 9 #75eba4e4dae1
```
```

--------------------------------

### Define Merkle Patricia Forestry Proof Types

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Demonstrates the construction of different proof step types: Branch, Fork, and Leaf. These steps are used to verify paths within the Merkle Patricia trie.

```aiken
use aiken/merkle_patricia_forestry.{Branch, Fork, Leaf, Neighbor, Proof} as mpf

let branch_step = Branch { skip: 0, neighbors: #"bc13df27a19f8caf0bf922c900424025282a892ba8577095fd35256c9d553ca1..." }

let fork_step = Fork {
  skip: 1,
  neighbor: Neighbor {
    nibble: 12,
    prefix: #"",
    root: #"cbf9b55ffdf4dbc9964cb51a01e6d66fae05bfb1704c057b8b0affb9eb8f6d3b",
  },
}

let leaf_step = Leaf {
  skip: 0,
  key: #"2b5b0ba7a99e17d9fde58f14dee61cccda9e3e9627b2ba2732ebed551ea9eaa4",
  value: #"3657998959985b7b75c734eb5b49d18cae9b353d00d811cb2c24ed6ed17b23d9",
}

let proof: Proof = [branch_step, fork_step, leaf_step]
```

--------------------------------

### Proof to UPLC Conversion

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Demonstrates the conversion of a Merkle Patricia proof object to its UPLC string representation.

```APIDOC
## `proof.toUPLC(): String`

### Description
Converts a Merkle Patricia proof object into a textual UPLC format. This format is expected by tools such as `aiken uplc eval` for evaluation and verification.

### Method
`toUPLC()`

### Endpoint
N/A (This is a method within a library, not a REST endpoint)

### Parameters
None

### Request Example
```js
// Assuming 'proofTangerine' is an instance of a Merkle Patricia proof object
const uplcString = proofTangerine.toUPLC();
console.log(uplcString);
```

### Response
#### Success Response
- **String** - A string representing the Merkle Patricia proof in UPLC format.

#### Response Example
```uplc
(con data
  (List
    [ Constr 0 [I 0, B #"17a27bc4ce61078d26372800d331d6b8c4b00255080be66977c78b1554aabf8985c09af929492a871e4fae32d9d5c36e352471cd659bcdb61de08f1722acc3b10eb923b0cbd24df54401d998531feead35a47a99f4deed205de4af81120f97610000000000000000000000000000000000000000000000000000000000000000"]
    , Constr 2 [I 0, B #"9702e39845bfd6e0d0a5b6cb4a3a1c25262528c11bcff857867a50a0670e3a28", B #"b5898c51c32083e91b8c18c735d0ba74e08f964a20b1639c189d1e8704b78a09"]
    ]
  )
)
```
```

--------------------------------

### Verify Non-Membership in Aiken

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Demonstrates how to prove that a specific key is absent from the trie using an exclusion proof.

```aiken
use aiken/merkle_patricia_forestry.{Proof} as mpf

let trie = mpf.from_root(#"4acd78f345a686361df77541b2e0b533f53362e36620a1fdd3a13e0b61a3b078")
let missing_key = "melon"
let exclusion_proof: Proof = []

let is_missing = mpf.miss(trie, missing_key, exclusion_proof)
```

--------------------------------

### Verify Proof Inclusion and Exclusion

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

The verify method checks if a proof matches the trie root hash. By toggling the includingItem parameter, you can verify either the inclusion of an item or the state of the trie excluding that item.

```javascript
proofTangerine.verify().equals(trie.hash);
const previousHash = trie.hash;
await trie.insert('banana', '🍌');
const proofBanana = await trie.prove('banana');
proofBanana.verify(true).equals(trie.hash);
proofBanana.verify(false).equals(previousHash);
```

--------------------------------

### Generating Trie Proofs

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

The `trie.prove(key, allowMissing)` method generates a proof for a given key. This proof can be used to verify the existence or non-existence of an item within a specific trie state. Proofs are only valid for the exact trie root hash and state they were generated from.

```APIDOC
## Generating Trie Proofs

### Description
Generates a proof for a given key, which can be used to verify the item's presence or absence in the trie at the time of proof generation. Proofs are specific to the trie's state.

### Method
`trie.prove(key: string|Buffer, allowMissing?: bool): Promise<Proof>`

### Endpoint
N/A (In-memory operation)

### Parameters
#### Path Parameters
- **key** (string|Buffer) - Required - The key for which to generate the proof.
- **allowMissing** (boolean) - Optional - If true, allows generating a proof for a key that might not exist in the trie (proof of exclusion).

### Request Example
```javascript
const proofTangerine = await trie.prove('tangerine');
// Proof {}

// Proof of non-membership
const proofMelon = await trie.prove('melon', true);
// Proof {}
```

### Response
#### Success Response (200)
- **Proof** (object) - An object representing the proof. The structure depends on the proof type (inclusion or exclusion).
```

--------------------------------

### Retrieve Values from Trie

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Demonstrates how to fetch values associated with specific keys from a trie instance. Returns undefined if the key does not exist in the trie.

```javascript
import { Trie } from '@aiken-lang/merkle-patricia-forestry';

const trie = await Trie.fromList([
  { key: 'apple', value: '🍎' },
  { key: 'banana', value: '🍌' },
  { key: 'cherry', value: '🍒' },
]);

const apple = await trie.get('apple');
console.log(apple.toString());

const banana = await trie.get('banana');
console.log(banana.toString());

const mango = await trie.get('mango');
console.log(mango);
```

--------------------------------

### Inspect Trie Children

Source: https://context7.com/aiken-lang/merkle-patricia-forestry/llms.txt

Explains how to fetch child nodes into memory for debugging or structural analysis using a depth parameter. Includes saving the trie back to disk to clear memory.

```javascript
import { Trie } from '@aiken-lang/merkle-patricia-forestry';

const trie = await Trie.fromList([
  { key: 'apple', value: '🍎' },
  { key: 'banana', value: '🍌' },
  { key: 'cherry', value: '🍒' },
  { key: 'grapes', value: '🍇' },
]);

await trie.fetchChildren(2);
console.log(trie);

await trie.fetchChildren(Number.MAX_SAFE_INTEGER);
await trie.save();
```

--------------------------------

### Generate Merkle Proofs

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Generates cryptographic proofs for items within the trie. Supports proofs of inclusion and exclusion by setting the allowMissing parameter.

```javascript
const proofTangerine = await trie.prove('tangerine');
const proofMelon = await trie.prove('melon', true);
```

--------------------------------

### Inspect and Visualize Trie Structure

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Visualizes the current trie state using console logging. The output provides a pretty-printed representation of the root hash and sub-trie structure.

```javascript
console.log(trie);
```

--------------------------------

### Convert Proof to UPLC Format

Source: https://github.com/aiken-lang/merkle-patricia-forestry/blob/main/off-chain/README.md

Converts a proof object into a textual UPLC representation. This is primarily used for interoperability with external evaluation tools.

```aiken
proofTangerine.toAiken();
```

```uplc
(con data
  (List
    [ Constr 0 [I 0, B #"17a27bc4ce61078d26372800d331d6b8c4b00255080be66977c78b1554aabf8985c09af929492a871e4fae32d9d5c36e352471cd659bcdb61de08f1722acc3b10eb923b0cbd24df54401d998531feead35a47a99f4deed205de4af81120f97610000000000000000000000000000000000000000000000000000000000000000"]
    , Constr 2 [I 0, B #"9702e39845bfd6e0d0a5b6cb4a3a1c25262528c11bcff857867a50a0670e3a28", B #"b5898c51c32083e91b8c18c735d0ba74e08f964a20b1639c189d1e8704b78a09"]
    ]
  )
)
```