Merkle Trees

Merkle trees are a fundamental data structure for collections in o1js, as they allow for efficient proofs of data inclusion. There are several classes of Merkle tree exported by o1js, with various properties.

IndexedMerkleMap

The IndexedMerkleMap is a wrapper around a basic Merkle tree that offers a convenient interface, with a key-value like API for getting and setting values.

Both the key and the value in of the map can be typed as Field or BigInt.

note

IndexedMerkleMap has a maximum height of 52, which means it can store up to 2^52 (roughly four quadrillion) elements. Therefore, it is not suitable for use cases requiring collision resistance over a larger domain, but it is suitable for most applications. For instance, an app with billions of users could have a leaf for each user stored in an IndexedMerkleMap.

const { IndexedMerkleMap } = Experimental;

const height = 4; // 2 ^ 4 = 16 leaves
class MyIndexedMerkleMap extends IndexedMerkleMap(height) {}

const map = new MyIndexedMerkleMap();
map.insert(1n, 20n);
map.insert(2n, 30n);

map.get(1n); // 20n
map.getOption(2n).orElse(0n); // 30n, Use .getOption to safely access values that may not exist
map.getOption(3n).orElse(0n); // 0n, values default to 0n

MerkleTree

The MerkleTree class is a general sparse Merkle tree implementation in JavaScript (not provable). It is used to build and store data in a tree structure, and exposes methods for generating witnesses and roots to use within provable code.

MerkleWitness

The MerkleWitness class is a proof of inclusion for a specific leaf in a MerkleTree. The MerkleWitness class is provable, so it can be used as an input into a provable function. The witness consists of the leaf index and the hashes of sibling nodes, needed to generate the root hash of the tree.

const tree = new MerkleTree(height);
tree.setLeaf(0n, Field(10));
tree.setLeaf(1n, Field(20));

tree.getLeaf(0n); // Field(10)
tree.getLeaf(1n); // Field(20)
tree.getLeaf(2n); // Field(0), values default to Field(0)

class MyMerkleWitness extends MerkleWitness(height) {}
const w = new MyMerkleWitness(tree.getWitness(1n));

MerkleList

The MerkleList is a class which represents a dynamic list of elements that can be committed to a single hash. This is a useful data structure when editing a list is required within a proof. To pass a list into a proof as an argument, a provable array may be simpler.

// Create a MerkleList with any provable type, e.g. Field
class MyList extends MerkleList.create(Field) {}

let list = MyList.empty();
list.push(Field(5));
let element = list.pop(); // Field(5)

Read more at the language reference: IndexedMerkleMap, MerkleTree, MerkleWitness, MerkleList.