experimental

The Indexed Merkle Map API is currently an experimental feature.

Indexed Merkle Map

Similar to a Merkle Tree, a Merkle Map allows referencing off-chain data by storing a single hash, also known as the root.

A Merkle Map is a wrapper around a Merkle Tree. Both data structures are analogous, but instead of using an index to set a leaf in a tree, a Merkle Map uses a key in a map.

Design

The Indexed Merkle Map is an improved version of the MerkleMap, offering enhanced efficiency and usability:

• Reduced Constraints: Uses 4-8x fewer constraints than MerkleMap.
• Support for Dummy Updates: Handles dummy updates for keys like 0 and -1.
• Provable Code Integration: Unlike MerkleTree and MerkleMap, the high-level API of IndexedMerkleMap is usable within provable code.
• Comprehensive Methods: Comes with a rich set of methods that enable a wide range of operations.

Utilizing Indexed Merkle Map

Prerequisites

The IndexedMerkleMap API is accessible within the Experimental namespace. To use the API, import Experimental from o1js version 1.5.0 or higher.

import { Experimental } from 'o1js';

const { IndexedMerkleMap } = Experimental;

Instantiating an Indexed Merkle Map

Given a height, you can instantiate an Indexed Merkle Map by extending the base class. The height determines the capacity of the map; the maximum number of leaf nodes it can contain.

const height = 31;
class IndexedMerkleMap31 extends IndexedMerkleMap(height) {}

In this example, IndexedMerkleMap31 is a Merkle map capable of holding up to 2⁽³¹⁻¹⁾ leaves; approximately 1 billion entries.

Utilizing IndexedMerkleMap in a smart contract

Developers can integrate the IndexedMerkleMap into their zkApps by passing a Merkle map as a method parameter and invoking its methods as needed.

This is possible because the IndexedMerkleMap can be used within provable code.

class MyContract extends SmartContract {
  @state(Field) mapRoot = State<Field>();

  init() {
    super.init();
    this.mapRoot.set(new IndexedMerkleMap31().root);
  }

  @method async insertNewLeaf(
    newKey: Field,
    newValue: Field,
    indexedMerkleMap: IndexedMerkleMap31
  ) {
    // Validate the integrity of the Merkle Map input
    const currentRoot = this.mapRoot.getAndRequireEquals();
    currentRoot.assertEquals(
      indexedMerkleMap.root,
      'Off-chain Indexed Merkle Map is out of sync!'
    );

    // Insert a new key-value pair
    indexedMerkleMap = indexedMerkleMap.clone();
    indexedMerkleMap.insert(newKey, newValue);

    // Update the on-chain map root
    const newMapRoot = indexedMerkleMap.root;
    this.mapRoot.set(newMapRoot);
  }

  @method async updateExistingLeaf(
    key: Field,
    newValue: Field,
    indexedMerkleMap: IndexedMerkleMap31
  ) {
    // Validate integrity of the Merkle Map input
    const currentRoot = this.mapRoot.getAndRequireEquals();
    currentRoot.assertEquals(
      indexedMerkleMap.root,
      'Off-chain Indexed Merkle Map is out of sync!'
    );

    indexedMerkleMap = indexedMerkleMap.clone();

    /**
     * Proves that the key exists
     * Updates an existing leaf
     * Returns the previous value
     */
    indexedMerkleMap.update(key, newValue);

    // Update the on-chain map root
    const newMapRoot = indexedMerkleMap.root;
    this.mapRoot.set(newMapRoot);
  }
}

⚠️ Direct modification of a method input can lead to errors. To avoid this, perform changes on a cloned Merkle Map rather than altering the map passed as a method input.

Interacting with a smart contract utilizing an indexed Merkle Map

To interact with a zkapp that utilizes an IndexedMerkleMap, instantiate a map instance and pass it as an argument to the contract’s method within a Mina transaction.

In addition, ensure you synchronize your off-chain map with on-chain updates to maintain data integrity and prepare for subsequent interactions.

// Instantiate a new Indexed Merkle Map
indexedMerkleMap = new IndexedMerkleMap31();

const insertTx = await Mina.transaction(userPubKey, async () => {
  await contract.insertNewLeaf(Field(1), Field(1234), indexedMerkleMap);
});

await insertTx.prove();
await insertTx.sign([userKey]).send();

// Synchornize the off-chain Indexed Merkle Map to match the on-chain state root
indexedMerkleMap.insert(Field(1), Field(1234));

console.log(
  indexedMerkleMap.root.toBigInt() === contract.mapRoot.get().toBigInt()
);
console.log(indexedMerkleMap.data.get().sortedLeaves);

const updateTx = await Mina.transaction(userPubKey, async () => {
  await contract.updateExistingLeaf(Field(1), Field(5678), indexedMerkleMap);
});

await updateTx.prove();
await updateTx.sign([userKey]).send();

// Synchronize the off-chain Indexed Merkle Map to match the on-chain state root
indexedMerkleMap.update(Field(1), Field(5678));

console.log(
  indexedMerkleMap.root.toBigInt() === contract.mapRoot.get().toBigInt()
);
console.log(indexedMerkleMap.data.get().sortedLeaves);

Indexed Merkle Map - API reference

The Indexed Merkle Map API provides a comprehensive set of methods that enable developers to perform a wide range of operations within provable code.

/**
 * Clone the entire Merkle map.
 *
 * This method is provable.
 */
clone(): IndexedMerkleMapBase;
/**
 * Overwrite the entire Merkle map with another one.
 *
 * This method is provable.
 */
overwrite(other: IndexedMerkleMapBase): void;
/**
 * Overwrite the entire Merkle map with another one, if the condition is true.
 *
 * This method is provable.
 */
overwriteIf(condition: Bool | boolean, other: IndexedMerkleMapBase): void;
/**
 * Insert a new leaf `(key, value)`.
 *
 * Proves that `key` doesn't exist yet.
 */
insert(key: Field | bigint, value: Field | bigint): void;
/**
 * Update an existing leaf `(key, value)`.
 *
 * Proves that the `key` exists.
 *
 * Returns the previous value.
 */
update(key: Field | bigint, value: Field | bigint): Field;
/**
 * Perform _either_ an insertion or update, depending on whether the key exists.
 *
 * Note: This method is handling both the `insert()` and `update()` case at the same time, so you
 * can use it if you don't know whether the key exists or not.
 *
 * However, this comes at an efficiency cost, so prefer to use `insert()` or `update()` if you know whether the key exists.
 *
 * Returns the previous value, as an option (which is `None` if the key didn't exist before).
 */
set(key: Field | bigint, value: Field | bigint): Option<Field, bigint>;
/**
 * Perform an insertion or update, if the enabling condition is true.
 *
 * If the condition is false, we instead set the 0 key to the value 0.
 * This is the initial value and for typical uses of `IndexedMerkleMap`, it is guaranteed to be a no-op because the 0 key is never used.
 *
 * **Warning**: Only use this method if you are sure that the 0 key is not used in your application.
 * Otherwise, you might accidentally overwrite a valid key-value pair.
 */
setIf(condition: Bool | boolean, key: Field | bigint, value: Field | bigint): Option<import("./field.js").Field, bigint>;
/**
 * Get a value from a key.
 *
 * Proves that the key already exists in the map yet and fails otherwise.
 */
get(key: Field | bigint): Field;
/**
 * Get a value from a key.
 *
 * Returns an option which is `None` if the key doesn't exist. (In that case, the option's value is unconstrained.)
 *
 * Note that this is more flexible than `get()` and allows you to handle the case where the key doesn't exist.
 * However, it uses about twice as many constraints for that reason.
 */
getOption(key: Field | bigint): Option<Field, bigint>;
/**
 * Prove that the given key exists in the map.
 */
assertIncluded(key: Field | bigint, message?: string): void;
/**
 * Prove that the given key does not exist in the map.
 */
assertNotIncluded(key: Field | bigint, message?: string): void;
/**
 * Check whether the given key exists in the map.
 */
isIncluded(key: Field | bigint): Bool;

Additional Resources

For more details and examples, please refer to the following GitHub resources:

• Indexed Merkle Tree: o1js PR#1666
• IndexedMerkleMap: Support 0 and -1 Keys: o1js PR#1671
• Mastermind zkApp Example Using Indexed Merkle Map