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.
Provable Code Integration: Unlike MerkleTree and MerkleMap, the high-level API of IndexedMerkleMap is usable within provable code.

note

The Indexed Merkle Map can have a height of at most 52, whereas the Merkle Map has a larger height fixed at 256.

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.