o1js-merkle

Merkle Trees for o1js (membership / non-membership merkle witness)

The library contains implementations of Sparse Merkle Tree, Standard Merkle Tree and Compact Merkle Tree based on o1js, which you can use in the browser or node.js env, and provides a corresponding set of verifiable utility methods that can be run in circuits. Besides, you could choose different persistence storage tools for each Merkle tree.

This article gives a brief introduction to SMT: Whats a sparse merkle tree, and SMT of this standard kind is carried out within Implementation from the Scratch.

Further, this library also provides another kind of SMT, which is of different theory and lets us customize the three height within our zkApp to achieve the decremental of our circuit constraint size significantly. please go to Contents Table of 'Retrofit from Third-Party library'.

Disclaimer and Notes

The library hasn't been audited. The API and the format of the proof may be changed in the future as o1js is updated. Make sure you know what you are doing before using this library.

Background

As a succint blockchain, Mina chain only contains 8 fields as onchain states for each zkApp account. Apparently this capacity is not enough, this is why we need maintain offchain storage keeping aligned with the onchain state. The classic solution for offchain storage is using a merkle tree whose root is stored onchain representing the whole offchain data.

As a zkApp engineer, you must learn about the merkle tree section at Mina Doc. Well, o1js library provides a memory-based classic MerkleTree implementation and MerkleMap implementation which is for sparse merkle trees.

But please NOTICE: the both currently are in memory, meaning the data is lost if the process is terminated. So we need to design a persistent storage to keep the data. And this library provides a set of useful merkle trees implementations with capability of persistence for you!

Within the package, various merkle trees totally belong to 2 catagories:

• Retrofit from Third-Party Library

  These implementations are located here. They are retrofited from Aztec Merkle Tree library and currently fully made usage of within Anomix Network -- a zk-zkRollup layer2 solution on Mina, focusing on Privacy&Scalablility.

  Totally there are three kinds of merkle tree implementations:

  • Append only 'Standard' merkle trees. New values are inserted into the next available leaf index. Values are never updated.
  • Indexed trees are also append only in nature but retain the ability to update leaves. The reason for this is that the Indexed Tree leaves not only store the value but the index of the next highest leaf. New insertions can require prior leaves to be updated.
  • Sparse trees that can be updated at any index. The 'size' of the tree is defined by the number of non-empty leaves, not by the highest populated leaf index as is the case with a Standard Tree.

  All of the trees leverage LevelDB as persistence storage. more cases please go to here.

• Implementation from the Scratch

  The other implementations are aside the Retrofited ones, which are implemented by us team from scratch.

  There are also Standard Merkle Tree and Sparse Merkle Tree implementations. What's more flexible, you could choose different persistence tools to store the tree.

  1. store in memory
  2. store in leveldb
  3. store in rocksdb
  4. store in mongodb

  more cases please go to here.

Table of Contents

• Install
  • Install module
• Contents Table of 'Retrofit from Third-Party library'
  • Install peer dependencies
  • Usage
    • Create and Load a StandardTree
    • Create and Load a SparseTree
    • Create and Load a StandardIndexedTree
• Contents Table of 'Implementation from the Scratch'
  • Install peer dependencies
  • What can you do with this library
  • Usage
    • Create a merkle tree data store
      • 1. Create a memory store
      • 2. Create a leveldb store
      • 3. Create a rocksdb store
      • 4. Create a mongodb store
    • Use MerkleTree (original NumIndexSparseMerkleTree)
    • Use SparseMerkleTree
    • Use CompactSparseMerkleTree
  • 3.4 API Reference

Install

1. Install module

npm install o1js-merkle

or with yarn:

yarn add o1js-merkle

NOTE: Please add node --experimental-specifier-resolution=node at the execution script in your project's package.json, which would activate node's native ESM revolution capability.

2. Contents Table of 'Retrofit from Third-Party library'

2.1 Install peer dependencies

npm install o1js
# yarn add o1js

npm install level
# yarn add level

2.2 Usage

Create and Load a StandardTree

here is the code.

import { newTree } from './new_tree.js';
import { Level } from "level";
import { PoseidonHasher } from './types/index.js';
import { Field, Provable } from 'o1js';
import { StandardTree } from './standard_tree/standard_tree.js';
import { verifyMembership  } from "./standard_tree/verify_circuit.js";

// create a leveldb for test
let db = new Level<string, Buffer>('example', {valueEncoding:'buffer'});

// poseidonHasher from o1js package
let poseidonHasher = new PoseidonHasher();

// tree height: 4
const PRIVATE_DATA_TREE_HEIGHT = 4;

// indicate if need consider the cached leaves, beside the existing leaves.
const includeUncommitted = true;

// create a standard merkle tree instance
const standardTreeInstance: StandardTree = await newTree(
  StandardTree,
  db,
  poseidonHasher,
  'privateData',
  PRIVATE_DATA_TREE_HEIGHT
);
console.log('standard tree initial root: ', standardTreeInstance.getRoot(includeUncommitted).toString());

// append the first leaf of type: Field, the newly inserted leaf is kept in an array before being flushed into db.
await standardTreeInstance.appendLeaves([
  Field(
    '20468198949394563802460512965219839480612000520504690501918527632215047268421'
  ),
]);

// before commit, you must get the leaf by specifying 'leafIndex' and 'includeUncommitted' = true
let leaf1 = await standardTreeInstance.getLeafValue(0n, includeUncommitted);
console.log('leaf1: ', leaf1?.toString());
// if you mistake specifying 'includeUncommitted' = false, then got 'undefined'. because the newly inserted leaf is not persisted yet.
leaf1 = await standardTreeInstance.getLeafValue(0n, !includeUncommitted);
console.log('leaf1: ', leaf1);

console.log('after append one leaf, tree root based on all cached&persisted leaves: ', standardTreeInstance.getRoot(includeUncommitted).toString());

let nowRootBeforeCommit = standardTreeInstance.getRoot(!includeUncommitted);
console.log('before commit, tree root based on existing persisted leaves: ', nowRootBeforeCommit.toString());

// persist, i.e. commit the tree into leveldb
await standardTreeInstance.commit();
console.log('exec commit... now all cached leaves are flushed into db and become parts of persisted leaves');

let nowRootAfterCommit = standardTreeInstance.getRoot(!includeUncommitted);
console.log('after commit, tree root based on all persisted leaves: ', nowRootAfterCommit.toString());

// after commit, now you could successfully get the leaf by specifying 'leafIndex' and 'includeUncommitted' = false
leaf1 = await standardTreeInstance.getLeafValue(0n, !includeUncommitted);
console.log('leaf1: ', leaf1);

// go on append several leaves
await standardTreeInstance.appendLeaves([Field(11)]);
await standardTreeInstance.appendLeaves([Field(21)]);
await standardTreeInstance.appendLeaves([Field(31)]);
await standardTreeInstance.appendLeaves([Field(41)]);
await standardTreeInstance.appendLeaves([Field(51)]);
await standardTreeInstance.appendLeaves([Field(61)]);

nowRootBeforeCommit = standardTreeInstance.getRoot(includeUncommitted);
// get merkle witness
const membershipWitness = await standardTreeInstance.getSiblingPath(3n, includeUncommitted);
console.log('witness: ', membershipWitness.toJSON());
// check the membership within circuit
Provable.runAndCheck(() => {
  const root = membershipWitness.calculateRoot(Field(31), Field(3n));
  Provable.log(root);
  Provable.assertEqual(Field, root, nowRootBeforeCommit);

  // verifyMembership(nowRootBeforeCommit, membershipWitness, Field(31), Field(3n))
});

const membershipWitness2 = await standardTreeInstance.getSiblingPath(6n, includeUncommitted);
console.log('witness2: ', membershipWitness2.toJSON());
Provable.runAndCheck(() => {
  const root = membershipWitness2.calculateRoot(Field(0), Field(6n));
  Provable.log('testroot: ', root);
});

await standardTreeInstance.commit();

The below is how to load tree from levelDB when process restart:

// load a standard merkle tree instance
const standardTreeInstance1: StandardTree = await loadTree(
  StandardTree,
  db,
  poseidonHasher,
  'privateData'
);

Besides, you could see the rich cases within circuits at Anomix Network

Create and Load a SparseTree

similar as StandardTree cases above.

Create and Load a StandardIndexedTree

StandardIndexedTree extends StandardTree, but MAINLY used for non-membership merkle witness. So the membership cases are like the ones above, and here are the non-membership witness cases.

here is the test case code.

import { newTree } from './new_tree.js';
import { ChainedBatch, Level } from "level";
import { PoseidonHasher } from './types/index.js';
import { StandardIndexedTree } from './standard_indexed_tree/standard_indexed_tree.js';
import { Field, Poseidon, Provable } from 'o1js';
import { loadTree } from './load_tree.js';
import { LeafData as CircuitLeafData, LeafData, verifyNonMembership } from "./standard_indexed_tree/verify_circuit.js";

// create a leveldb for test
let db = new Level<string, Buffer>('example-index', {valueEncoding:'buffer'});

// poseidonHasher from o1js package
let poseidonHasher = new PoseidonHasher();

// tree height: 4
const PRIVATE_DATA_TREE_HEIGHT = 4;

// indicate if need consider the cached leaves, beside the existing leaves.
const includeUncommitted = true;

// create a standard merkle tree instance
const standardIndexedTreeInstance: StandardIndexedTree = await newTree(
  StandardIndexedTree,
  db,
  poseidonHasher,
  'NULLIFIER_TREE',
  PRIVATE_DATA_TREE_HEIGHT
);
console.log('standard indexed tree initial root: ', standardIndexedTreeInstance.getRoot(includeUncommitted).toString());

// append the first leaf of type: Field, the newly inserted leaf is kept in an array before being flushed into db.
await standardIndexedTreeInstance.appendLeaves([
  Field(
    '20468198949394563802460512965219839480612000520504690501918527632215047268421'
  ),
]);

// before commit, you must get the leaf by specifying 'leafIndex' and 'includeUncommitted' = true
let leaf1 = await standardIndexedTreeInstance.getLeafValue(0n, includeUncommitted);
console.log('leaf1: ', leaf1?.toString());
// if you mistake specifying 'includeUncommitted' = false, then got 'undefined'. because the newly inserted leaf is not persisted yet.
leaf1 = await standardIndexedTreeInstance.getLeafValue(0n, !includeUncommitted);
console.log('leaf1: ', leaf1?.toString());

console.log('after append one leaf, tree root based on all cached&persisted leaves: ', standardIndexedTreeInstance.getRoot(includeUncommitted).toString());

let nowRootBeforeCommit = standardIndexedTreeInstance.getRoot(!includeUncommitted);
console.log('before commit, tree root based on existing persisted leaves: ', nowRootBeforeCommit.toString());

// persist, i.e. commit the tree into leveldb
await standardIndexedTreeInstance.commit();
console.log('exec commit... now all cached leaves are flushed into db and become parts of persisted leaves');

let nowRootAfterCommit = standardIndexedTreeInstance.getRoot(!includeUncommitted);
console.log('after commit, tree root based on all persisted leaves: ', nowRootAfterCommit.toString());

// after commit, now you could successfully get the leaf by specifying 'leafIndex' and 'includeUncommitted' = false
leaf1 = await standardIndexedTreeInstance.getLeafValue(0n, !includeUncommitted);
console.log('leaf1: ', leaf1);

// go on append several leaves
await standardIndexedTreeInstance.appendLeaves([Field(11)]);
await standardIndexedTreeInstance.appendLeaves([Field(21)]);
await standardIndexedTreeInstance.appendLeaves([Field(31)]);
await standardIndexedTreeInstance.appendLeaves([Field(41)]);
await standardIndexedTreeInstance.appendLeaves([Field(51)]);
await standardIndexedTreeInstance.appendLeaves([Field(61)]);

// commit the later newly inserted leaves into levelDB
await standardIndexedTreeInstance.commit();

// Non-Membership merkle witness
nowRootAfterCommit = standardIndexedTreeInstance.getRoot(!includeUncommitted);
const nullifier1 = Field(71n);// the nullifier to be inserted
const { index, alreadyPresent } = await standardIndexedTreeInstance.findIndexOfPreviousValue(nullifier1.toBigInt(), includeUncommitted);
if (alreadyPresent) {// if exist, then throw error.
    throw new Error("nullifier1[${nullifier1}] existed!");
}
const predecessorSiblingPath = (await standardIndexedTreeInstance.getSiblingPath(BigInt(index), includeUncommitted))!;
const leafData = standardIndexedTreeInstance.getLatestLeafDataCopy(index, includeUncommitted)!;
const predecessorLeafData = new LeafData({value: Field(leafData.value), nextIndex: Field(leafData.nextIndex), nextValue: Field(leafData.nextValue)});
const predecessorLeafDataIndex= Field(index);

// the membership witness of previous leaf is the Non-membership witness of 'nullifier1'
Provable.runAndCheck(() => {
  verifyNonMembership(nowRootAfterCommit, nullifier1, predecessorLeafData, predecessorSiblingPath, predecessorLeafDataIndex);
  Provable.log(`verify: true`);
});

The below is how to load tree from levelDB when process restart:

// load a standard indexed merkle tree instance
const standardIndexedTreeInstance1: StandardIndexedTree = await loadTree(
  StandardIndexedTree,
  db,
  poseidonHasher,
  'NULLIFIER_TREE'
);

If you wanna go deeper the theory of StandardIndexedTree, please refer to here. Besides, you could see the rich cases within circuits at Anomix Network

3. Contents Table of 'Implementation from the Scratch'

3.1 Install peer dependencies

npm install o1js
# yarn add o1js

If you need to use LevelDB to store data, you will also need to install:

npm install level
# yarn add level

RocksDB:

npm install rocksdb encoding-down levelup

MongoDB:

npm install mongoose

3.2 What can you do with this library

You can update the data of Sparse Merkle Tree(SMT) outside the circuit, and then verify the membership proof or non-membership proof of the data in the circuit. At the same time, you can also verify the correctness of the state transformation of SMT in the circuit, which makes us not need to update the SMT in the circuit, but also ensure the legal modification of SMT data outside the circuit. We can verify the validity of data modification through zkApp.

3.3 Usage

Create a merkle tree data store

1. Create a memory store

import { MemoryStore, Store } from 'o1js-merkle';
import { Field } from 'o1js';

// memory data store for Field type data, you can use any CircuitValue from o1js or a custom composite CircuitValue
let store: Store<Field> = new MemoryStore<Field>();

2. Create a leveldb store

import { Field } from 'o1js';
import { LevelStore, Store } from 'o1js-merkle';
import { Level } from 'level';
// create a leveldb data store for Field type data, you can use any CircuitValue from o1js or a custom composite CircuitValue
const levelDb = new Level<string, any>('./db');
let store: Store<Field> = new LevelStore<Field>(levelDb, Field, 'test');

3. Create a rocksdb store

import { RocksStore, Store } from 'o1js-merkle';
import { Field } from 'o1js';
import encode from 'encoding-down';
import rocksdb from 'rocksdb';
import levelup from 'levelup';

const encoded = encode(rocksdb('./rocksdb'));
const db = levelup(encoded);
let store: Store<Field> = new RocksStore<Field>(db, Field, 'test');

4. Create a mongodb store

import mongoose from 'mongoose';
import { MongoStore, Store } from 'o1js-merkle';
import { Field } from 'o1js';

await mongoose.connect('mongodb://localhost/my_database');
let store: Store<Field> = new MongoStore(mongoose.connection, Field, 'test');

Use MerkleTree (original NumIndexSparseMerkleTree)

MerkleTree is a merkle tree of numerically indexed data that can customize the tree height, this merkel tree is equivalent to a data structure: Map<bigint, Struct>, Struct can be a CircuitValue type in o1js, such as Field, PublicKey, or a custom composite Struct. Tree height <= 254, Numeric index <= (2^height-1).

MerkleTreeUtils: A collection of merkle tree utility methods that do not work in circuits.

ProvableMerkleTreeUtils: A collection of merkle tree utility methods that can be verified to work in circuits

An example of using MerkleTree in the mina smart contract, modified from the example in the o1js official repo: merkle_zkapp.ts

class Account extends Struct({
  address: PublicKey,
  balance: UInt64,
  nonce: UInt32,
}) {}

// Create a memory store
let store = new MemoryStore<Account>();
// initialize a new Merkle Tree with height 8
let tree = await MerkleTree.build(store, 8, Account);

let testValue = new Account({
  address: PrivateKey.random().toPublicKey(),
  balance: UInt64.fromNumber(100),
  nonce: UInt32.fromNumber(0),
});

const root = await tree.update(0n, testValue);

// get value
const v = await tree.get(0n);
// support compact merkle proof
const cproof = await tree.proveCompact(0n);
// decompact NumIndexProof
const proof = MerkleTreeUtils.decompactMerkleProof(cproof);
// check membership outside the circuit
const ok = MerkleTreeUtils.checkMembership(proof, root, 0n, testValue, Account);

// check membership in the circuit
ProvableMerkleTreeUtils.checkMembership(
  proof,
  root,
  Field(0n),
  testValue,
  Account
).assertTrue();

testValue.nonce = testValue.nonce.add(1);
// calculate new root in the circuit
const newRoot = ProvableMerkleTreeUtils.computeRoot(
  proof,
  Field(0n),
  testValue,
  Account
);

Support DeepMerkleSubTree: DeepMerkleSubTree is a deep sparse merkle subtree for working on only a few leafs.(ProvableDeepMerkleSubTree is a deep subtree version that works in circuit). DeepMerkleSubTree Example

Use SparseMerkleTree

SparseMerkleTree is a merkle tree with a fixed height of 254, this merkel tree is equivalent to a data structure: Map<Struct,Struct>, Struct can be a CircuitValue type in o1js, such as Field, PublicKey, or a custom composite Struct.

SMTUtils: A collection of sparse merkle tree utility methods that do not work in circuits.

ProvableSMTUtils: A collection of sparse merkle tree utility methods that can be verified to work in circuits

An example of using SparseMerkleTree in the mina smart contract, modified from the example in the o1js official repo: smt_zkapp.ts

class Account extends Struct({
  address: PublicKey,
  balance: UInt64,
  nonce: UInt32,
}) {}

// Create a memory store
let store = new MemoryStore<Account>();
// Or create a level db store:
// const levelDb = new Level<string, any>('./db');
// let store = new LevelStore<Account>(levelDb, Account, 'test');

let smt = await SparseMerkleTree.build(store, Field, Account);
// Or import a tree by store
// smt = await SparseMerkleTree.importTree<Field, Account>(store);

let testKey = Field(1);
let testValue = new Account({
  address: PrivateKey.random().toPublicKey(),
  balance: UInt64.fromNumber(100),
  nonce: UInt32.fromNumber(0),
});
let newValue = new Account({
  address: PrivateKey.random().toPublicKey(),
  balance: UInt64.fromNumber(50),
  nonce: UInt32.fromNumber(1),
});

const root = await smt.update(testKey, testValue);
// Create a compacted merkle proof for a key against the current root.
const cproof = await smt.proveCompact(testKey);
// Verify the compacted Merkle proof outside the circuit.
const ok = SMTUtils.verifyCompactProof(
  cproof,
  root,
  testKey,
  Field,
  testValue,
  Account
);
console.log('ok: ', ok);

// Create a merkle proof for a key against the current root.
const proof = await smt.prove(testKey);

// Check membership in the circuit, isOk should be true.
let isOk = ProvableSMTUtils.checkMembership(
  proof,
  root,
  testKey,
  Field,
  testValue,
  Account
);

// Check Non-membership in the circuit, isOk should be false.
isOk = ProvableSMTUtils.checkNonMembership(proof, root, testKey, Field);

// Calculate new root in the circuit
let newRoot = ProvableSMTUtils.computeRoot(
  roof.sideNodes,
  testKey,
  Field,
  newValue,
  Account
);
console.log('newRoot: ', newRoot.toString());

Support DeepSparseMerkleSubTree: DeepSparseMerkleSubTree is a deep sparse merkle subtree for working on only a few leafs.(ProvableDeepSparseMerkleSubTree is a deep subtree version that works in circuit). DeepSparseMerkleSubTree Example

Use CompactSparseMerkleTree

CompactSparseMerkleTree is a merkle tree with a fixed height of 254, this merkel tree is equivalent to a data structure: Map<Struct,Struct>, Struct can be a CircuitValue type in o1js, such as Field, PublicKey, or a custom composite Struct. Compared with SparseMerkleTree, its advantage is that it can save storage space, and the operation efficiency of the tree is relatively high, but it is currently impossible to calculate the new root after the state transformation in the circuit.

CSMTUtils: A collection of compact sparse merkle tree utility methods that do not work in circuits.

ProvableCSMTUtils: A collection of compact sparse merkle tree utility methods that can be verified to work in circuits

class Account extends Struct({
  address: PublicKey,
  balance: UInt64,
  nonce: UInt32,
}) {}

// Create a memory store
let store = new MemoryStore<Account>();
// Or create a level db store:
// const levelDb = new Level<string, any>('./db');
// let store = new LevelStore<Account>(levelDb, Account, 'test');

let smt = new CompactSparseMerkleTree(store, Field, Account);
// Or import a tree by store
// smt = await CompactSparseMerkleTree.import(store);

let testKey = Field(1);
let testValue = new Account(
  PrivateKey.random().toPublicKey(),
  UInt64.fromNumber(100),
  UInt32.fromNumber(0)
);
let newValue = new Account(
  PrivateKey.random().toPublicKey(),
  UInt64.fromNumber(50),
  UInt32.fromNumber(1)
);

const root = await smt.update(testKey, testValue);

// Create a merkle proof for a key against the current root.
const proof = await smt.prove(testKey);

// Check membership in circuit, isOk should be true.
let isOk = ProvableCSMTUtils.checkMembership(
  proof,
  root,
  testKey,
  Field,
  testValue,
  Account
);

// Check Non-membership in circuit, isOk should be false.
isOk = ProvableCSMTUtils.checkNonMembership(proof, root, testKey, Field);

Support CompactDeepSparseMerkleSubTree: CompactDeepSparseMerkleSubTree is a deep sparse merkle subtree for working on only a few leafs. CompactDeepSparseMerkleSubTree Example

API Reference

• API Document