Merkle Tree

Merkle tree is a widely used data structure . Its properties are useful for many reasons, that is why it is adopted in many cryptosystems.

In Module 1, you've seen what Merkle Tree is and why is it used. In Mina protocol, Merkle Trees are used for a data.

To see some basics of MerkleTree class in мина protocol, you can see docs and API reference parts.

There are some helper functions/classes in MerkleTree class which are useful to use.

MerkleWitness

A Merkle witness provides the necessary information to verify that a specific element is part of the Merkle tree. This is typically a list of hashes from the leaf node up to the root, excluding the nodes on the direct path of the leaf node, allowing one to compute the Merkle root independently and verify it against a known good root.

MerkleMap

A Merkle map extends the concept of a Merkle tree by associating keys with values in a map-like structure. Each leaf in the Merkle map is a hash of a key-value pair, and the tree structure allows for efficient proofs of existence (or non-existence) of keys.

MerkleMapWitness

Similar to a Merkle witness, a MerkleMapWitness provides the necessary hashes and path information to verify the presence (or absence) and correctness of a key-value pair in a Merkle map.

import { Field, MerkleTree, MerkleWitness } from 'o1js';

// Example data
const data = [Field(1), Field(2), Field(3), Field(4)];

let tree = new MerkleTree(3);


tree.fill(data);

// Compute and get the root of the tree. 
let root = tree.getRoot();

// Get the witness of element with index 0. 
let myWitness = tree.getWitness(0n);

// witness for 0th element.
class witnessForZero extends MerkleWitness(3){};

// Instantiate the witness object for zeroth element with the extracted witness previously. 
let someWitness = new witnessForZero(myWitness);

// Calculate the root with combining the data and witness you have.
let calculatedRoot = someWitness.calculateRoot(Field(1));

// See that both roots of Merkle tree are same.
console.log(root.equals(calculatedRoot).toBoolean());

There are much more in the API reference, which might be useful for your purpose of use.

Example: MinaNFT

import { Field, MerkleWitness, ZkProgram, method, SmartContract } from "o1js";

function TreeCalculationFunction(height: number) {
  class MerkleTreeWitness extends MerkleWitness(height) {}

  const TreeCalculation = ZkProgram({
    name: "TreeCalculation",
    publicInput: Field,

    methods: {
      check: {
        privateInputs: [MerkleTreeWitness, Field],

        method(root: Field, witness: MerkleTreeWitness, value: Field) {
          const calculatedRoot = witness.calculateRoot(value);
          calculatedRoot.assertEquals(root);
        },
      },
    },
  });
  return TreeCalculation;
}

function TreeVerifierFunction(height: number) {
  const TreeCalculation = TreeCalculationFunction(height);
  class TreeProof extends ZkProgram.Proof(TreeCalculation) {}

  class TreeVerifier extends SmartContract {
    @method verifyRedactedTree(proof: TreeProof) {
      proof.verify();
    }
  }
  return TreeVerifier;
}

async function main() {
  const TreeCalculation = TreeCalculationFunction(4);
  const TreeVerifier = TreeVerifierFunction(4);
  await TreeCalculation.compile();
  await TreeVerifier.compile();
}

main();

In the snippet above, calculation of the root is aimed to be done in a ZkProgram (or call, in a provable structure)

Another function written takes the proof of the calculation of tree and submits it to on-chain via SmartContract.