A Hackers Guide to Layer 2: Zero Merkle Trees from Scratch

README.md

A Hackers Guide to Layer 2: Zero Merkle Trees from Scratch

Code Snippets from the Tutorial

This repository contains the code snippets from the tutorial A Hackers Guide to Layer 2: Zero Merkle Trees from Scratch.

Thanks to OAS for sponsoring this tutorial series.

License

Copyright 2023 Carter Jack Feldman

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

example1.ts

import shajs from "sha.js";

type MerkleNodeValue = string;

function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
  return shajs("sha256")
    .update(leftNode + rightNode, "hex")
    .digest("hex");
}
function computeZeroHashes(height: number): MerkleNodeValue[] {
  let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
  const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
  for (let i = 1; i <= height; i++) {
    currentZeroHash = hash(currentZeroHash, currentZeroHash);
    zeroHashes.push(currentZeroHash)
  }
  return zeroHashes;
}


function example1(){
  console.log("[example1] the first 32 zero hashes are: "+JSON.stringify(computeZeroHashes(32), undefined, 2));
}
example1();

example2.ts

import shajs from "sha.js";

type MerkleNodeValue = string;

function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
  return shajs("sha256")
    .update(leftNode + rightNode, "hex")
    .digest("hex");
}
function computeZeroHashes(height: number): MerkleNodeValue[] {
  let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
  const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
  for (let i = 1; i <= height; i++) {
    currentZeroHash = hash(currentZeroHash, currentZeroHash);
    zeroHashes.push(currentZeroHash)
  }
  return zeroHashes;
}
class NodeStore {
  nodes: {[id: string]: MerkleNodeValue};
  height: number;
  zeroHashes: MerkleNodeValue[];
  constructor(height: number){
    this.nodes = {};
    this.height = height;
    this.zeroHashes = computeZeroHashes(height);
  }
  contains(level: number, index: number): boolean {
    // check if the node exists in the data store
    return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
  }
  
  set(level: number, index: number, value: MerkleNodeValue){
    // set the value of the node in the data store
    this.nodes[level+"_"+index] = value;
  }

  get(level: number, index: number): MerkleNodeValue {
    if(this.contains(level, index)){
      // if the node is in the datastore, return it
      return this.nodes[level+"_"+index];
    }else{
      // if the node is NOT in the data store, return the correct zero hash for the node's level
      return this.zeroHashes[this.height-level];
    }
  }
}
class ZeroMerkleTree {
  height: number;
  nodeStore: NodeStore;
  constructor(height: number){
    this.height = height;
    this.nodeStore = new NodeStore(height);
  }
  setLeaf(index: number, value: MerkleNodeValue){
    // start traversing the leaf's merkle path at the leaf node
    let currentIndex = index;
    let currentValue = value;

    // don't set the root (level = 0) in the loop, as it has no sibling
    for(let level = this.height; level > 0; level--){
      // set the current node in the tree
      this.nodeStore.set(level, currentIndex, currentValue);

      if(currentIndex % 2 === 0){
        // if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
        const rightSibling = this.nodeStore.get(level, currentIndex+1);
        currentValue = hash(currentValue, rightSibling);
      }else{
        // if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
        const leftSibling = this.nodeStore.get(level, currentIndex-1);
        currentValue = hash(leftSibling, currentValue);
      }

      // set current index to the index of the parent node
      currentIndex = Math.floor(currentIndex/2);
    }

    // set the root node (level = 0, index = 0) to current value
    this.nodeStore.set(0, 0, currentValue);
  }
  getRoot(): MerkleNodeValue {
    return this.nodeStore.get(0, 0);
  }

}
function example2(){
  const leavesToSet = [
    "0000000000000000000000000000000000000000000000000000000000000001", // 1
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000007", // 7
    "0000000000000000000000000000000000000000000000000000000000000004", // 4
    "0000000000000000000000000000000000000000000000000000000000000002", // 2
    "0000000000000000000000000000000000000000000000000000000000000000", // 0
    "0000000000000000000000000000000000000000000000000000000000000006", // 6
  ];
  const tree = new ZeroMerkleTree(3);
  leavesToSet.forEach((leaf, index)=>{
    tree.setLeaf(index, leaf);
  });
  console.log("[example2] the root is: "+tree.getRoot());
}
example2();

example3.ts

import shajs from "sha.js";

type MerkleNodeValue = string;

interface IMerkleProof {
  root: MerkleNodeValue;
  siblings: MerkleNodeValue[];
  index: number;
  value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
  index: number;
  siblings: MerkleNodeValue[];
  oldRoot: MerkleNodeValue;
  oldValue: MerkleNodeValue;
  newRoot: MerkleNodeValue;
  newValue: MerkleNodeValue;
}

function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
  return shajs("sha256")
    .update(leftNode + rightNode, "hex")
    .digest("hex");
}

function computeZeroHashes(height: number): MerkleNodeValue[] {
  let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
  const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
  for (let i = 1; i <= height; i++) {
    currentZeroHash = hash(currentZeroHash, currentZeroHash);
    zeroHashes.push(currentZeroHash)
  }
  return zeroHashes;
}

class NodeStore {
  nodes: {[id: string]: MerkleNodeValue};
  height: number;
  zeroHashes: MerkleNodeValue[];
  constructor(height: number){
    this.nodes = {};
    this.height = height;
    this.zeroHashes = computeZeroHashes(height);
  }
  contains(level: number, index: number): boolean {
    // check if the node exists in the data store
    return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
  }
  
  set(level: number, index: number, value: MerkleNodeValue){
    // set the value of the node in the data store
    this.nodes[level+"_"+index] = value;
  }

  get(level: number, index: number): MerkleNodeValue {
    if(this.contains(level, index)){
      // if the node is in the datastore, return it
      return this.nodes[level+"_"+index];
    }else{
      // if the node is NOT in the data store, return the correct zero hash for the node's level
      return this.zeroHashes[this.height-level];
    }
  }
}

class ZeroMerkleTree {
  height: number;
  nodeStore: NodeStore;
  
  constructor(height: number){
    this.height = height;
    this.nodeStore = new NodeStore(height);
  }

  setLeaf(index: number, value: MerkleNodeValue): IDeltaMerkleProof{
    // get the old root and old value for the delta merkle proof
    const oldRoot = this.nodeStore.get(0, 0);
    const oldValue = this.nodeStore.get(this.height, index);
    
    // siblings array for delta merkle proof
    const siblings: MerkleNodeValue[] = [];


    // start traversing the leaf's merkle path at the leaf node
    let currentIndex = index;
    let currentValue = value;

    // don't set the root (level = 0) in the loop, as it has no sibling
    for(let level = this.height; level > 0; level--){
      // set the current node in the tree
      this.nodeStore.set(level, currentIndex, currentValue);

      if(currentIndex % 2 === 0){
        // if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
        const rightSibling = this.nodeStore.get(level, currentIndex+1);
        currentValue = hash(currentValue, rightSibling);

        // add the right sibling to the siblings array
        siblings.push(rightSibling);
      }else{
        // if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
        const leftSibling = this.nodeStore.get(level, currentIndex-1);
        currentValue = hash(leftSibling, currentValue);

        // add the left sibling to the siblings array
        siblings.push(leftSibling);
      }

      // set current index to the index of the parent node
      currentIndex = Math.floor(currentIndex/2);
    }

    // set the root node (level = 0, index = 0) to current value
    this.nodeStore.set(0, 0, currentValue);
    return {
      index,
      siblings,
      oldRoot,
      oldValue,
      newValue: value,
      newRoot: currentValue,
    };
  }
  getRoot(): MerkleNodeValue {
    return this.nodeStore.get(0, 0);
  }

}



function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
  // start our merkle node path at the leaf node
  let merklePathNodeValue = value;
  let merklePathNodeIndex = index;

  // we follow the leaf's merkle path up to the root, 
  // computing the merkle path's nodes using the siblings provided as we go alone
  for(let i=0;i<siblings.length;i++){
    const merklePathNodeSibling = siblings[i];

    if(merklePathNodeIndex%2===0){
      // if the current index of the node on our merkle path is even:
      // * merklePathNodeValue is the left hand node,
      // * merklePathNodeSibling is the right hand node
      // * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
      merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
    }else{
      // if the current index of the node on our merkle path is odd:
      // * merklePathNodeSibling is the left hand node
      // * merklePathNodeValue is the right hand node,
      // * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
      merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
    }

    // using our definition, the parent node of our path node is N(level-1, floor(index/2))
    merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
  }
  return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
  return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
  // split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
  const oldProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.oldRoot,
    value: deltaMerkleProof.oldValue,
  };

  const newProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.newRoot,
    value: deltaMerkleProof.newValue,
  };
  return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}

function example3(){
  const leavesToSet = [
    "0000000000000000000000000000000000000000000000000000000000000001", // 1
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000007", // 7
    "0000000000000000000000000000000000000000000000000000000000000004", // 4
    "0000000000000000000000000000000000000000000000000000000000000002", // 2
    "0000000000000000000000000000000000000000000000000000000000000000", // 0
    "0000000000000000000000000000000000000000000000000000000000000006", // 6
  ];
  const tree = new ZeroMerkleTree(3);
  const deltaMerkleProofs = leavesToSet.map((leaf, index)=>tree.setLeaf(index, leaf));

  // verify the delta merkle proofs
  for(let i=0;i<deltaMerkleProofs.length;i++){
    const deltaProof = deltaMerkleProofs[i];

    if(!verifyDeltaMerkleProof(deltaProof)){
      console.error("[example3] ERROR: delta merkle proof for index "+deltaProof.index+" is INVALID");
      throw new Error("invalid delta merkle proof");
    }else{
      console.log("[example3] delta merkle proof for index "+deltaProof.index+" is valid");
    }
  }

  console.log("[example3] the delta merkle proofs are:\n"+JSON.stringify(deltaMerkleProofs, null, 2));

}
example3();

example4.ts

import shajs from "sha.js";

type MerkleNodeValue = string;

interface IMerkleProof {
  root: MerkleNodeValue;
  siblings: MerkleNodeValue[];
  index: number;
  value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
  index: number;
  siblings: MerkleNodeValue[];
  oldRoot: MerkleNodeValue;
  oldValue: MerkleNodeValue;
  newRoot: MerkleNodeValue;
  newValue: MerkleNodeValue;
}

function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
  return shajs("sha256")
    .update(leftNode + rightNode, "hex")
    .digest("hex");
}

function computeZeroHashes(height: number): MerkleNodeValue[] {
  let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
  const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
  for (let i = 1; i <= height; i++) {
    currentZeroHash = hash(currentZeroHash, currentZeroHash);
    zeroHashes.push(currentZeroHash)
  }
  return zeroHashes;
}

class NodeStore {
  nodes: {[id: string]: MerkleNodeValue};
  height: number;
  zeroHashes: MerkleNodeValue[];
  constructor(height: number){
    this.nodes = {};
    this.height = height;
    this.zeroHashes = computeZeroHashes(height);
  }
  contains(level: number, index: number): boolean {
    // check if the node exists in the data store
    return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
  }
  
  set(level: number, index: number, value: MerkleNodeValue){
    // set the value of the node in the data store
    this.nodes[level+"_"+index] = value;
  }

  get(level: number, index: number): MerkleNodeValue {
    if(this.contains(level, index)){
      // if the node is in the datastore, return it
      return this.nodes[level+"_"+index];
    }else{
      // if the node is NOT in the data store, return the correct zero hash for the node's level
      return this.zeroHashes[this.height-level];
    }
  }
}

class ZeroMerkleTree {
  height: number;
  nodeStore: NodeStore;
  
  constructor(height: number){
    this.height = height;
    this.nodeStore = new NodeStore(height);
  }

  setLeaf(index: number, value: MerkleNodeValue): IDeltaMerkleProof{
    // get the old root and old value for the delta merkle proof
    const oldRoot = this.nodeStore.get(0, 0);
    const oldValue = this.nodeStore.get(this.height, index);
    
    // siblings array for delta merkle proof
    const siblings: MerkleNodeValue[] = [];


    // start traversing the leaf's merkle path at the leaf node
    let currentIndex = index;
    let currentValue = value;

    // don't set the root (level = 0) in the loop, as it has no sibling
    for(let level = this.height; level > 0; level--){
      // set the current node in the tree
      this.nodeStore.set(level, currentIndex, currentValue);

      if(currentIndex % 2 === 0){
        // if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
        const rightSibling = this.nodeStore.get(level, currentIndex+1);
        currentValue = hash(currentValue, rightSibling);

        // add the right sibling to the siblings array
        siblings.push(rightSibling);
      }else{
        // if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
        const leftSibling = this.nodeStore.get(level, currentIndex-1);
        currentValue = hash(leftSibling, currentValue);

        // add the left sibling to the siblings array
        siblings.push(leftSibling);
      }

      // set current index to the index of the parent node
      currentIndex = Math.floor(currentIndex/2);
    }

    // set the root node (level = 0, index = 0) to current value
    this.nodeStore.set(0, 0, currentValue);
    return {
      index,
      siblings,
      oldRoot,
      oldValue,
      newValue: value,
      newRoot: currentValue,
    };
  }
  getRoot(): MerkleNodeValue {
    return this.nodeStore.get(0, 0);
  }

}



function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
  // start our merkle node path at the leaf node
  let merklePathNodeValue = value;
  let merklePathNodeIndex = index;

  // we follow the leaf's merkle path up to the root, 
  // computing the merkle path's nodes using the siblings provided as we go alone
  for(let i=0;i<siblings.length;i++){
    const merklePathNodeSibling = siblings[i];

    if(merklePathNodeIndex%2===0){
      // if the current index of the node on our merkle path is even:
      // * merklePathNodeValue is the left hand node,
      // * merklePathNodeSibling is the right hand node
      // * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
      merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
    }else{
      // if the current index of the node on our merkle path is odd:
      // * merklePathNodeSibling is the left hand node
      // * merklePathNodeValue is the right hand node,
      // * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
      merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
    }

    // using our definition, the parent node of our path node is N(level-1, floor(index/2))
    merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
  }
  return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
  return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
  // split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
  const oldProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.oldRoot,
    value: deltaMerkleProof.oldValue,
  };

  const newProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.newRoot,
    value: deltaMerkleProof.newValue,
  };
  return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}

function example4(){
  const leavesToSet = [
    "0000000000000000000000000000000000000000000000000000000000000001", // 1
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000007", // 7
    "0000000000000000000000000000000000000000000000000000000000000004", // 4
    "0000000000000000000000000000000000000000000000000000000000000002", // 2
    "0000000000000000000000000000000000000000000000000000000000000000", // 0
    "0000000000000000000000000000000000000000000000000000000000000006", // 6
  ];
  const tree = new ZeroMerkleTree(3);
  const deltaMerkleProofs = leavesToSet.map((leaf, index)=>tree.setLeaf(index, leaf));

  // verify the delta merkle proofs
  for(let i=0;i<deltaMerkleProofs.length;i++){
    const deltaProof = deltaMerkleProofs[i];

    if(!verifyDeltaMerkleProof(deltaProof)){
      console.error("[example4] ERROR: delta merkle proof for index "+deltaProof.index+" is INVALID");
      throw new Error("invalid delta merkle proof");
    }else if(i>0 && deltaProof.oldRoot !== deltaMerkleProofs[i-1].newRoot){
      // the previous proof's new root should be the same as this proof's old root
      console.error(
        "[example4] ERROR: delta merkle proof for index "+deltaProof.index +
        " has a different old root than the previous delta merkle proof's new root"
    );
      throw new Error("delta merkle proof root sequence mismatch");
    }else{
      console.log("[example4] delta merkle proof for index "+deltaProof.index+" is valid");
    }
  }

  console.log("[example4] the delta merkle proofs are:\n"+JSON.stringify(deltaMerkleProofs, null, 2));

}
example4();

example5.ts

import shajs from "sha.js";

type MerkleNodeValue = string;

interface IMerkleProof {
  root: MerkleNodeValue;
  siblings: MerkleNodeValue[];
  index: number;
  value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
  index: number;
  siblings: MerkleNodeValue[];
  oldRoot: MerkleNodeValue;
  oldValue: MerkleNodeValue;
  newRoot: MerkleNodeValue;
  newValue: MerkleNodeValue;
}

function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
  return shajs("sha256")
    .update(leftNode + rightNode, "hex")
    .digest("hex");
}

function computeZeroHashes(height: number): MerkleNodeValue[] {
  let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
  const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
  for (let i = 1; i <= height; i++) {
    currentZeroHash = hash(currentZeroHash, currentZeroHash);
    zeroHashes.push(currentZeroHash)
  }
  return zeroHashes;
}

class NodeStore {
  nodes: {[id: string]: MerkleNodeValue};
  height: number;
  zeroHashes: MerkleNodeValue[];
  constructor(height: number){
    this.nodes = {};
    this.height = height;
    this.zeroHashes = computeZeroHashes(height);
  }
  contains(level: number, index: number): boolean {
    // check if the node exists in the data store
    return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
  }
  
  set(level: number, index: number, value: MerkleNodeValue){
    // set the value of the node in the data store
    this.nodes[level+"_"+index] = value;
  }

  get(level: number, index: number): MerkleNodeValue {
    if(this.contains(level, index)){
      // if the node is in the datastore, return it
      return this.nodes[level+"_"+index];
    }else{
      // if the node is NOT in the data store, return the correct zero hash for the node's level
      return this.zeroHashes[this.height-level];
    }
  }
}

class ZeroMerkleTree {
  height: number;
  nodeStore: NodeStore;
  
  constructor(height: number){
    this.height = height;
    this.nodeStore = new NodeStore(height);
  }

  setLeaf(index: number, value: MerkleNodeValue): IDeltaMerkleProof{
    // get the old root and old value for the delta merkle proof
    const oldRoot = this.nodeStore.get(0, 0);
    const oldValue = this.nodeStore.get(this.height, index);
    
    // siblings array for delta merkle proof
    const siblings: MerkleNodeValue[] = [];


    // start traversing the leaf's merkle path at the leaf node
    let currentIndex = index;
    let currentValue = value;

    // don't set the root (level = 0) in the loop, as it has no sibling
    for(let level = this.height; level > 0; level--){
      // set the current node in the tree
      this.nodeStore.set(level, currentIndex, currentValue);

      if(currentIndex % 2 === 0){
        // if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
        const rightSibling = this.nodeStore.get(level, currentIndex+1);
        currentValue = hash(currentValue, rightSibling);

        // add the right sibling to the siblings array
        siblings.push(rightSibling);
      }else{
        // if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
        const leftSibling = this.nodeStore.get(level, currentIndex-1);
        currentValue = hash(leftSibling, currentValue);

        // add the left sibling to the siblings array
        siblings.push(leftSibling);
      }

      // set current index to the index of the parent node
      currentIndex = Math.floor(currentIndex/2);
    }

    // set the root node (level = 0, index = 0) to current value
    this.nodeStore.set(0, 0, currentValue);
    return {
      index,
      siblings,
      oldRoot,
      oldValue,
      newValue: value,
      newRoot: currentValue,
    };
  }

  getLeaf(index: number): IMerkleProof {
    // siblings array for merkle proof
    const siblings: MerkleNodeValue[] = [];

    // get value for the merkle proof
    const value = this.nodeStore.get(this.height, index);


    // start traversing the leaf's merkle path at the leaf node
    let currentIndex = index;
    let currentValue = value;

    // don't set the root (level = 0) in the loop, as it has no sibling
    for(let level = this.height; level > 0; level--){
      if(currentIndex % 2 === 0){
        // if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
        const rightSibling = this.nodeStore.get(level, currentIndex+1);
        currentValue = hash(currentValue, rightSibling);

        // add the right sibling to the siblings array
        siblings.push(rightSibling);
      }else{
        // if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
        const leftSibling = this.nodeStore.get(level, currentIndex-1);
        currentValue = hash(leftSibling, currentValue);

        // add the left sibling to the siblings array
        siblings.push(leftSibling);
      }

      // set current index to the index of the parent node
      currentIndex = Math.floor(currentIndex/2);
    }

    // current value is the root
    const root = currentValue;
    
    return {
      root,
      siblings,
      index,
      value,
    };
  }

  getRoot(): MerkleNodeValue {
    return this.nodeStore.get(0, 0);
  }

}



function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
  // start our merkle node path at the leaf node
  let merklePathNodeValue = value;
  let merklePathNodeIndex = index;

  // we follow the leaf's merkle path up to the root, 
  // computing the merkle path's nodes using the siblings provided as we go alone
  for(let i=0;i<siblings.length;i++){
    const merklePathNodeSibling = siblings[i];

    if(merklePathNodeIndex%2===0){
      // if the current index of the node on our merkle path is even:
      // * merklePathNodeValue is the left hand node,
      // * merklePathNodeSibling is the right hand node
      // * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
      merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
    }else{
      // if the current index of the node on our merkle path is odd:
      // * merklePathNodeSibling is the left hand node
      // * merklePathNodeValue is the right hand node,
      // * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
      merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
    }

    // using our definition, the parent node of our path node is N(level-1, floor(index/2))
    merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
  }
  return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
  return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
  // split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
  const oldProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.oldRoot,
    value: deltaMerkleProof.oldValue,
  };

  const newProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.newRoot,
    value: deltaMerkleProof.newValue,
  };
  return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}

function example5(){
  const leavesToSet = [
    "0000000000000000000000000000000000000000000000000000000000000001", // 1
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000007", // 7
    "0000000000000000000000000000000000000000000000000000000000000004", // 4
    "0000000000000000000000000000000000000000000000000000000000000002", // 2
    "0000000000000000000000000000000000000000000000000000000000000000", // 0
    "0000000000000000000000000000000000000000000000000000000000000006", // 6
  ];
  const tree = new ZeroMerkleTree(3);
  const deltaMerkleProofs = leavesToSet.map((leaf, index)=>tree.setLeaf(index, leaf));

  // verify the delta merkle proofs
  for(let i=0;i<deltaMerkleProofs.length;i++){
    const deltaProof = deltaMerkleProofs[i];

    if(!verifyDeltaMerkleProof(deltaProof)){
      console.error("[example5] ERROR: delta merkle proof for index "+deltaProof.index+" is INVALID");
      throw new Error("invalid delta merkle proof");
    }else if(i>0 && deltaProof.oldRoot !== deltaMerkleProofs[i-1].newRoot){
      // the previous proof's new root should be the same as this proof's old root
      console.error(
        "[example5] ERROR: delta merkle proof for index "+deltaProof.index +
        " has a different old root than the previous delta merkle proof's new root"
    );
      throw new Error("delta merkle proof root sequence mismatch");
    }else{
      console.log("[example5] delta merkle proof for index "+deltaProof.index+" is valid");
    }
  }

  // don't print the delta merkle proofs to avoid clutter
  //console.log("[example5] the delta merkle proofs are:\n"+JSON.stringify(deltaMerkleProofs, null, 2));

  // verify each leaf's merkle proof
  for(let i=0;i<leavesToSet.length;i++){
    const proof = tree.getLeaf(i);
    if(!verifyMerkleProof(proof)){
      console.error("[example5] ERROR: merkle proof for index "+proof.index+" is INVALID");
      throw new Error("invalid merkle proof");
    }else if(proof.value !== leavesToSet[i]){
      console.error("[example5] ERROR: merkle proof for index "+proof.index+" has the wrong value");
      throw new Error("merkle proof value mismatch");
    }else{
      console.log("[example5] merkle proof for index "+proof.index+" is valid");
    }
    console.log("merkle proof for index "+proof.index+": "+JSON.stringify(proof, null, 2));
  }

}
example5();

example6.ts

import shajs from "sha.js";

type MerkleNodeValue = string;

interface IMerkleProof {
  root: MerkleNodeValue;
  siblings: MerkleNodeValue[];
  index: number;
  value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
  index: number;
  siblings: MerkleNodeValue[];
  oldRoot: MerkleNodeValue;
  oldValue: MerkleNodeValue;
  newRoot: MerkleNodeValue;
  newValue: MerkleNodeValue;
}

function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
  return shajs("sha256")
    .update(leftNode + rightNode, "hex")
    .digest("hex");
}

function computeZeroHashes(height: number): MerkleNodeValue[] {
  let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
  const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
  for (let i = 1; i <= height; i++) {
    currentZeroHash = hash(currentZeroHash, currentZeroHash);
    zeroHashes.push(currentZeroHash)
  }
  return zeroHashes;
}

class NodeStore {
  nodes: {[id: string]: MerkleNodeValue};
  height: number;
  zeroHashes: MerkleNodeValue[];
  constructor(height: number){
    this.nodes = {};
    this.height = height;
    this.zeroHashes = computeZeroHashes(height);
  }
  contains(level: number, index: number): boolean {
    // check if the node exists in the data store
    return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
  }
  
  set(level: number, index: number, value: MerkleNodeValue){
    // set the value of the node in the data store
    this.nodes[level+"_"+index] = value;
  }

  get(level: number, index: number): MerkleNodeValue {
    if(this.contains(level, index)){
      // if the node is in the datastore, return it
      return this.nodes[level+"_"+index];
    }else{
      // if the node is NOT in the data store, return the correct zero hash for the node's level
      return this.zeroHashes[this.height-level];
    }
  }
}

class ZeroMerkleTree {
  height: number;
  nodeStore: NodeStore;
  
  constructor(height: number){
    this.height = height;
    this.nodeStore = new NodeStore(height);
  }

  setLeaf(index: number, value: MerkleNodeValue): IDeltaMerkleProof{
    // get the old root and old value for the delta merkle proof
    const oldRoot = this.nodeStore.get(0, 0);
    const oldValue = this.nodeStore.get(this.height, index);
    
    // siblings array for delta merkle proof
    const siblings: MerkleNodeValue[] = [];


    // start traversing the leaf's merkle path at the leaf node
    let currentIndex = index;
    let currentValue = value;

    // don't set the root (level = 0) in the loop, as it has no sibling
    for(let level = this.height; level > 0; level--){
      // set the current node in the tree
      this.nodeStore.set(level, currentIndex, currentValue);

      if(currentIndex % 2 === 0){
        // if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
        const rightSibling = this.nodeStore.get(level, currentIndex+1);
        currentValue = hash(currentValue, rightSibling);

        // add the right sibling to the siblings array
        siblings.push(rightSibling);
      }else{
        // if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
        const leftSibling = this.nodeStore.get(level, currentIndex-1);
        currentValue = hash(leftSibling, currentValue);

        // add the left sibling to the siblings array
        siblings.push(leftSibling);
      }

      // set current index to the index of the parent node
      currentIndex = Math.floor(currentIndex/2);
    }

    // set the root node (level = 0, index = 0) to current value
    this.nodeStore.set(0, 0, currentValue);
    return {
      index,
      siblings,
      oldRoot,
      oldValue,
      newValue: value,
      newRoot: currentValue,
    };
  }

  getLeaf(index: number): IMerkleProof {
    // siblings array for merkle proof
    const siblings: MerkleNodeValue[] = [];

    // get value for the merkle proof
    const value = this.nodeStore.get(this.height, index);


    // start traversing the leaf's merkle path at the leaf node
    let currentIndex = index;
    let currentValue = value;

    // don't set the root (level = 0) in the loop, as it has no sibling
    for(let level = this.height; level > 0; level--){
      if(currentIndex % 2 === 0){
        // if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
        const rightSibling = this.nodeStore.get(level, currentIndex+1);
        currentValue = hash(currentValue, rightSibling);

        // add the right sibling to the siblings array
        siblings.push(rightSibling);
      }else{
        // if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
        const leftSibling = this.nodeStore.get(level, currentIndex-1);
        currentValue = hash(leftSibling, currentValue);

        // add the left sibling to the siblings array
        siblings.push(leftSibling);
      }

      // set current index to the index of the parent node
      currentIndex = Math.floor(currentIndex/2);
    }

    // current value is the root
    const root = currentValue;
    
    return {
      root,
      siblings,
      index,
      value,
    };
  }

  getRoot(): MerkleNodeValue {
    return this.nodeStore.get(0, 0);
  }

}



function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
  // start our merkle node path at the leaf node
  let merklePathNodeValue = value;
  let merklePathNodeIndex = index;

  // we follow the leaf's merkle path up to the root, 
  // computing the merkle path's nodes using the siblings provided as we go alone
  for(let i=0;i<siblings.length;i++){
    const merklePathNodeSibling = siblings[i];

    if(merklePathNodeIndex%2===0){
      // if the current index of the node on our merkle path is even:
      // * merklePathNodeValue is the left hand node,
      // * merklePathNodeSibling is the right hand node
      // * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
      merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
    }else{
      // if the current index of the node on our merkle path is odd:
      // * merklePathNodeSibling is the left hand node
      // * merklePathNodeValue is the right hand node,
      // * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
      merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
    }

    // using our definition, the parent node of our path node is N(level-1, floor(index/2))
    merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
  }
  return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
  return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
  // split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
  const oldProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.oldRoot,
    value: deltaMerkleProof.oldValue,
  };

  const newProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.newRoot,
    value: deltaMerkleProof.newValue,
  };
  return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}

function example6(){
  const tree = new ZeroMerkleTree(50);
  const deltaA = tree.setLeaf(999999999999,"0000000000000000000000000000000000000000000000000000000000000008");
  const deltaB = tree.setLeaf(1337,"0000000000000000000000000000000000000000000000000000000000000007");
  
  const proofA = tree.getLeaf(999999999999);
  const proofB = tree.getLeaf(1337);

  console.log("verifyDeltaMerkleProof(deltaA): "+verifyDeltaMerkleProof(deltaA));
  console.log("verifyDeltaMerkleProof(deltaB): "+verifyDeltaMerkleProof(deltaB));
  console.log("deltaA.newRoot === deltaB.oldRoot: "+(deltaA.newRoot === deltaB.oldRoot));
  
  console.log("verifyMerkleProof(proofA): "+verifyMerkleProof(proofA));
  console.log("verifyMerkleProof(proofB): "+verifyMerkleProof(proofB));
  
  console.log("proofA: "+JSON.stringify(proofA, null, 2));
  console.log("proofB: "+JSON.stringify(proofB, null, 2));
}
example6();

example7.ts

import shajs from "sha.js";

type MerkleNodeValue = string;

interface IMerkleProof {
  root: MerkleNodeValue;
  siblings: MerkleNodeValue[];
  index: number;
  value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
  index: number;
  siblings: MerkleNodeValue[];
  oldRoot: MerkleNodeValue;
  oldValue: MerkleNodeValue;
  newRoot: MerkleNodeValue;
  newValue: MerkleNodeValue;
}

function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
  return shajs("sha256")
    .update(leftNode + rightNode, "hex")
    .digest("hex");
}

function computeZeroHashes(height: number): MerkleNodeValue[] {
  let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
  const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
  for (let i = 1; i <= height; i++) {
    currentZeroHash = hash(currentZeroHash, currentZeroHash);
    zeroHashes.push(currentZeroHash)
  }
  return zeroHashes;
}

class AppendOnlyMerkleTree {
  height: number;
  lastProof: IMerkleProof;
  zeroHashes: MerkleNodeValue[];


  
  constructor(height: number){
    this.height = height;
    this.zeroHashes = computeZeroHashes(height);

    // create a dummy proof of all zero hashes for initialization (before we append any leaves, we know all the siblings will be zero hashes because it is an empty tree)
    this.lastProof = {
      root: this.zeroHashes[this.height],
      siblings: this.zeroHashes.slice(0, this.height),
      index: -1,
      value: this.zeroHashes[this.height],
    };
  }
  appendLeaf(leafValue: string): IDeltaMerkleProof {
    const oldMerklePath = computeMerklePathFromProof(this.lastProof.siblings, this.lastProof.index, this.lastProof.value);

    // get the old root and old value for the delta merkle proof
    const oldRoot = this.lastProof.root;
    // the old value will always be empty, thats why its an append only tree :P
    const oldValue = "0000000000000000000000000000000000000000000000000000000000000000";
    const prevIndex = this.lastProof.index;

    // append only tree = new index is always the previous index + 1
    const newIndex = prevIndex+1;

    // keep track of the old siblings so we can use them for our delta merkle proof
    const oldSiblings =this.lastProof.siblings;

    const siblings: MerkleNodeValue[] = [];
    let multiplier = 1;
    for(let level=0;level<this.height;level++){
      // get the index of the previous leaf's merkle path node on the current level
      const prevLevelIndex = Math.floor(prevIndex/multiplier);

      // get the index of the new leaf's merkle path node on the current level
      const newLevelIndex = Math.floor(newIndex/multiplier);


      if(newLevelIndex===prevLevelIndex){
        // if the merkle path node index on this level DID NOT change, we can reuse the old sibling
        siblings.push(oldSiblings[level]);
      }else{
        // if the merkle path node index on this level DID change, we need to check if the new merkle path node index is a left or right hand node
        if(newLevelIndex%2===0){
          // if the new merkle path node index is even, the new merkle path node is a left hand node,
          // so merkle path node's sibling is a right hand node,
          // therefore our sibling has an index greater than our merkle path node,
          // so the sibling must be a zero hash
          // QED
          siblings.push(this.zeroHashes[level]);
        }else{
          // if the new merkle path node is odd, then its sibling has an index one less than it, so its sibling must be the previous merkle path node on this level
          siblings.push(oldMerklePath[level]);
        }
      }
      multiplier = multiplier * 2;
    }
    const newRoot = computeMerkleRootFromProof(siblings, newIndex, leafValue);
    this.lastProof = {
      root: newRoot,
      siblings: siblings,
      index: newIndex,
      value: leafValue,
    };


    return {
      index: this.lastProof.index,
      siblings,
      oldRoot,
      oldValue,
      newRoot,
      newValue: leafValue,
    };
  }


}



function computeMerklePathFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue[]{
  // start our merkle node path at the leaf node
  let merklePathNodeValue = value;
  let merklePathNodeIndex = index;
  const merklePath: MerkleNodeValue[] = [value];

  // we follow the leaf's merkle path up to the root, 
  // computing the merkle path's nodes using the siblings provided as we go alone
  for(let i=0;i<siblings.length;i++){
    const merklePathNodeSibling = siblings[i];

    if(merklePathNodeIndex%2===0){
      // if the current index of the node on our merkle path is even:
      // * merklePathNodeValue is the left hand node,
      // * merklePathNodeSibling is the right hand node
      // * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
      merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
    }else{
      // if the current index of the node on our merkle path is odd:
      // * merklePathNodeSibling is the left hand node
      // * merklePathNodeValue is the right hand node,
      // * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
      merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
    }

    // using our definition, the parent node of our path node is N(level-1, floor(index/2))
    merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
    merklePath.push(merklePathNodeValue)
  }
  return merklePath;
}

function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
  // start our merkle node path at the leaf node
  let merklePathNodeValue = value;
  let merklePathNodeIndex = index;

  // we follow the leaf's merkle path up to the root, 
  // computing the merkle path's nodes using the siblings provided as we go alone
  for(let i=0;i<siblings.length;i++){
    const merklePathNodeSibling = siblings[i];

    if(merklePathNodeIndex%2===0){
      // if the current index of the node on our merkle path is even:
      // * merklePathNodeValue is the left hand node,
      // * merklePathNodeSibling is the right hand node
      // * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
      merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
    }else{
      // if the current index of the node on our merkle path is odd:
      // * merklePathNodeSibling is the left hand node
      // * merklePathNodeValue is the right hand node,
      // * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
      merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
    }

    // using our definition, the parent node of our path node is N(level-1, floor(index/2))
    merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
  }
  return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
  return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
  // split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
  const oldProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.oldRoot,
    value: deltaMerkleProof.oldValue,
  };

  const newProof = {
    // reuse the same siblings for both old and new
    siblings: deltaMerkleProof.siblings, 
    // reuse the same index for both old and new
    index: deltaMerkleProof.index,

    root: deltaMerkleProof.newRoot,
    value: deltaMerkleProof.newValue,
  };
  return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}

function example7(){
  const tree = new AppendOnlyMerkleTree(50);
  const deltaA = tree.appendLeaf("0000000000000000000000000000000000000000000000000000000000000008");
  const deltaB = tree.appendLeaf("0000000000000000000000000000000000000000000000000000000000000007");

  console.log(deltaA);
  

  console.log("verifyDeltaMerkleProof(deltaA): "+verifyDeltaMerkleProof(deltaA));
  console.log("verifyDeltaMerkleProof(deltaB): "+verifyDeltaMerkleProof(deltaB));

  console.log("deltaA.newRoot === deltaB.oldRoot: "+(deltaA.newRoot === deltaB.oldRoot));
  
  
  console.log("deltaA: "+JSON.stringify(deltaA, null, 2));
  console.log("deltaB: "+JSON.stringify(deltaB, null, 2));
  for(let i=0;i<50;i++){
    console.log("verifyDeltaMerkleProof(delta["+i+"]): "+verifyDeltaMerkleProof(tree.appendLeaf(i.toString(16).padStart(64,"0"))));
  }
}
example7();