Optimistic rollups like Arbitrum and Optimism have been gaining increasing attention lately, and many dApps and users have begun considering migrating to optimistic solutions as momentum for Layer 2 adoption builds.

At a glance, it looks like Optimistic rollups may soon secure a permanent role within the greater blockchain ecosystem as a scaling layer for Ethereum’s rock solid consensus, delivering the best of both worlds to users: Ethereum-level security and high transaction capacity — Providing a great service to the blockchain industry as a whole.

But looks, alas, can be deceiving.

In fact, as we look closer, it becomes increasingly clear that Optimistic rollups neither provide a meaningful increase in blockchain scale nor do they guarantee or even approximate the security of Ethereum.

Methodology

In this blog post, we will consider Arbitrum as it is the largest Optimistic Rollup at the time of writing, but most if not all of the points made are generally applicable to other Optimistic rollups.

In the spirit of objectivity and fairness, we will focus on evaluating the two key value propositions/claims of made on the Arbitrum official website:

1. Optimistic Rollups are a “Secure Scaling Solution for Ethereum” with innovative high-throughput
2. Optimistic Rollups have “Ethereum-level” security (or as the Arbitrum team puts it, the claim that Arbitrum “inherits Ethereum-level security”)

Finally, we will finish the post on an Optimistic note for the future of blockchain security and scalability, powered by ZK:

While Optimistic rollups don’t meaningfully contribute to blockchain security or scalability, there is an rising technology that can: Zero Knowledge Proofs (ZKP)

Optimistic Security Fallacy 1: AIT AIT AIT AIT

At the core of Optimistic rollup’s claim to “inherit Ethereum”’s security is the way in which fraudulent transactions can be stopped from gaining finality. Let’s consider Aribtrum’s security model:

1. The Arbitrum internal team operates a centralized sequencer node that orders the transaction. This node centrally decides which transactions are processed at a what time, and can any transactions it likes (we have already sacrificed Ethereum’s censorship resistance)
2. The centralized sequencer operated by the Arbitrum internal team submits the call data need to reconstruct the L2 transactions to L1 (this is necessarily faster than actually executing the transactions, otherwise everyone might as well just execute on L1).
3. A group of “defensive validators” picked by the Arbitrum internal team listen to transactions from the centralized sequencer operated by the Arbitrum internal team and process the transactions locally.
4. The defensive validators picked by the Arbitrum internal team then execute the transactions sent to them by the Arbitrum internal team and make sure the execution data matches the data submitted on chain by the Arbitrum internal team.
5. If the Arbitrum internal team submits incorrect information about a transaction, the the defensive validators picked by the Arbitrum internal team can challenge the execution, but once the challenge occurs, the challenge is paused to give time for the Arbitrum internal team to upgrade the smart contracts in collaboration with the close partners of the Arbitrum Security Council (a group of folks well connected and including the Arbitrum internal team).

Sounds like Ethereum-level security to me!

Optimistic Security Fallacy 2: Self Inconsistency

In our second note we mentioned that “The centralized sequencer operated by the Arbitrum internal team submits the call data need to reconstruct the L2 transactions to L1 (this is necessarily faster than actually executing the transactions, otherwise everyone might as well just execute on L1).”.

Let’s dive into that a bit more deeply, noting that this describes the call to the function addSequencerL2BatchFromOrigin on chain:

1. The call to addSequencerL2BatchFromOrigin must contain all the data necessary to reconstitute the state, as the centralized sequencer could just decide not to send anyone the data necessary to check if they were submitting fraudulent transactions (otherwise no one could create a challenge/fraud proof or even verify if fraud had occurred).
2. The execution running time of addSequencerL2BatchFromOrigin must be faster than the sum of the running time of all the transactions it attests to (otherwise you might as well just execute the transactions on Ethereum instead of on Arbitrum).

So if the data feed from the Arbitrum internal team is cut off, the validators get the execution data to check the validity of l2 batches posted by the arbitrum internal team. They can derive the EVM transactions from the stuff posted on chain, and execute locally.

But, by the time the validators have derived and executed one batch of transactions posted on L1, the sequencer could have posted 5 more batches on chain.

Are Optimistic Rollups Scaling Ethereum?

Now that we know Optimistic rollup’s core thesis is self-inconsistent due to the inability of validators to ever catch up if the sequencer is compromised, we can at least give them some points for scale, right? Unlike some adjectives that blockchains like to describe themselves with (innovative, revolutionary, etc.), the word scale describes something we can measure and compare how well Arbitrum using unimpeachable, real world data.

To judge claim that a side chain X is a “Scaling Layer” for chain Y, we need to measure how much more scalable chain X is than chain Y (is it 10 times as scalable, 100 times as scalable, etc).

To measure the veracity of the scalability claim made by optimistic rollups, we can find the maximum scalability factor (a number that tells us how much better chain X is at scaling than chain Y) by dividing the maximum sustained TPS of side chain X by the maximum sustained TPS of chain Y:

Knowing how much investor money has been poured into Optimistic rollup technology and the bold claims made by projects like Arbitrum, we know that the world’s most popular optimistic rollup will be far more scalable than Ethereum. But, just to be sure, let’s calculate and see for ourselves.

To do our scaling analysis, we can use a great tool called Dune.com to run a SQL query on all of the historical data to precisely calculate the Scalability Factor for Aribtrum and others:

WITH bt AS (
SELECT
    DATE_TRUNC('{{Time Granularity}}', NOW()) - interval '{{Trailing Num Periods}}' {{Time Granularity}} AS dtmin,
    DATE_TRUNC('{{Time Granularity}}', NOW()) AS dtmax
)

SELECT 
chain
, cast(num_txs as double)/90.0 AS num_txs_per_day
, cast(num_txs as double)/(90.0 * (60.0*60.0*24.0) ) AS num_txs_per_second
FROM
(
    SELECT 'Optimism' as chain ,COUNT(*) AS num_txs FROM optimism.transactions WHERE block_time > (SELECT dtmin FROM bt) AND block_time < (SELECT dtmax FROM bt)
    AND to NOT IN (SELECT address FROM labels.system_addresses WHERE blockchain = 'optimism' )
    UNION ALL
    SELECT 'Arbitrum' as chain ,COUNT(*) AS num_txs FROM arbitrum.transactions WHERE block_time > (SELECT dtmin FROM bt) AND block_time < (SELECT dtmax FROM bt)
    AND to NOT IN (SELECT address FROM labels.system_addresses WHERE blockchain = 'arbitrum' )
    UNION ALL
    SELECT 'Ethereum' as chain ,COUNT(*) AS num_txs FROM ethereum.transactions WHERE block_time > (SELECT dtmin FROM bt) AND block_time < (SELECT dtmax FROM bt)
    AND to NOT IN (SELECT address FROM labels.system_addresses WHERE blockchain = 'ethereum' )
    UNION ALL
    SELECT 'Solana' as chain ,COUNT(*) AS num_txs FROM solana.transactions WHERE block_time > (SELECT dtmin FROM bt) AND block_time < (SELECT dtmax FROM bt)
    UNION ALL
    SELECT 'Polygon' as chain ,COUNT(*) AS num_txs FROM polygon.transactions WHERE block_time > (SELECT dtmin FROM bt) AND block_time < (SELECT dtmax FROM bt)
    AND to NOT IN (SELECT address FROM labels.system_addresses WHERE blockchain = 'polygon' )
    UNION ALL
    SELECT 'BNB' as chain ,COUNT(*) AS num_txs FROM bnb.transactions WHERE block_time > (SELECT dtmin FROM bt) AND block_time < (SELECT dtmax FROM bt)
    AND to NOT IN (SELECT address FROM labels.system_addresses WHERE blockchain = 'bnb' )
    UNION ALL
    
    SELECT 'Avalanche C-Chain' as chain ,COUNT(*) AS num_txs FROM avalanche_c.transactions WHERE block_time > (SELECT dtmin FROM bt) AND block_time < (SELECT dtmax FROM bt)
    AND to NOT IN (SELECT address FROM labels.system_addresses WHERE blockchain = 'avalanche_c' )
    ) as tps_info

Ok, now let’s run our query and check the results!

We now know the average TPS for Ethereum is 12.11, so we can also calculate the scaling factors for Aribtrum and Optimism:

• Aribtrum Average TPS = 11.24, ARB Scaling Factor = 11.24/12.11 = 0.928
• Optimism Average TPS = 3.95 OP Scaling Factor = 3.95/12.11 = 0.326

Hence, Optimistic rollups have not come close to providing anything like a significant leap forward in scale for Ethereum.

You would need 30 isolated Arbitrum’s (no communication between rollups) to approach Solana scale let alone the Web2 scale that many fans expect Layer 2’s to one day deliver.

A Slow AWS: #NotMyL2

Blockchain has value because people know that transactions are final, computation is secure, and state integrity is preserved at all costs. No one can ever touch their money as long as they have their own keys.

People only put up with our low scalability and poor user experience because of this.

So Optimistic rollups beg the question:

Is it a prudent idea for the Blockchain community to surrender our only advantages for such a pitiful increase in scalability?

But we need to scale up as a community, so are we doomed to transform into slow AWS controlled by cabals/DAOs less trustworthy than Amazon?

Don’t trust AIT, Trust Math

Zero Knowledge Proofs can provide off chain computation without the need for an Arbitrum internal team or security council, and recursive ZKP can provide far higher scale than these “Optimistic” chains.

In a future article we will discuss some of these solutions, but in general:’

If you want to build a dApp, build it on Scroll, Kakarot, QED, Starknet, Polygon or zkSync.

Sleep well at night knowing the only think you will need to trust is Math.

Follow @cmpeq on twitter to stay up to date with future installments.
Tutorial code snippets: github.com/cf/zero-merkle-tree-tutorial

In this tutorial, we will:

• Learn how to build an efficient zero merkle tree implementation capable of processing changes in trees with quadrillions of leaves, and implement it in TypeScript from scratch.
• Learn how to build an append-only merkle tree which only requires O(log(n)) storage, and implement it in TypeScript from scratch.
• Learn about Spiderman proofs and how to efficiently generate/verify batch updates to a merkle tree with a single, succinct proof.

Note

Before reading this tutorial, it is highly recommended to first work through the first installment where we cover merkle tree fundamentals, and we will be frequently referencing content from what we learned in the previous guide.

What I cannot create, I do not understand.
Richard Feynman

Introduction

In the previous installment of A Hackers Guide to Layer 2, we covered the basics of merkle trees and built a simple merkle tree database implementation.

While what we built was simple and usable for small trees, our previous merkle tree implementation will be very slow when working with large trees:

• Every time we called getRoot (to compute the tree’s merkle root), we had to rehash the whole merkle tree (O(2^height) time complexity)
• Creating a new merkle tree instance required us to pass the tree’s height and an array of leaves with size 2^height to the constructor (memory is also O(2^n))

Unfortunately, our zkVM will need to work with merkle trees that are both large (height > 32) and sparse (most of the leaves are zero).

We will explain why this is the case in future installments, but it is intuitively related to the fact that our zkVM will use merkle trees to verifiably store and organize persistent data (think of merkle trees as a verifiable hard drive + file system for our zkVM).

That being said, we are not out of luck, as we can take advantage of merkle tree’s self-similarity to build a much more efficient database for our use case.

The Zero Hashes

To begin tackling the problem of building a merkle tree better suited for our large/sparse use case, we can gain some insight by first examining an empty merkle tree and looking for patterns that we can take advantage of:

If we recall that a node’s value is equal to the hash of its children, we can draw rectangles around the nodes which have the same value:

Aha! When a merkle tree is empty, it looks like the all the nodes on each level have the same value. The value of the nodes on each level of an empty merkle tree are known as the Zero Hashes and are often denoted as Zₙ where n = TreeHeight - Level.

Since we know that the bottom nodes have a value Z₀ = 0, lets write an expression for Zₙ.

Recalling the formula for computing the value of node in a merkle tree that we learned in the previous installment:

We can just plug-in zero for the leaves and use the level-wise self-similarity that we observed in the tree to write an expression for Zₙ:

Hence we can say that, for an empty merkle tree with height = TreeHeight:

Great, now let’s demonstrate our knowledge of the zero hashes by writing a TypeScript function that computes the array of zero hashes for a giventreeHeight:

Running this code, we get the output:

Great! Now that we have written a function to compute the zero hashes, we can write a function to obtain the value of any node in an empty merkle tree using our zero hashes:

function getNodeValue(treeHeight: number, level: number): MerkleNodeValue{
  const zeroHashes = computeZeroHashes(treeHeight);
  return zeroHashes[treeHeight-level];
}

Implementing a ZMT Database

We now know how to compute the value any node in an empty merkle tree, let’s use our knowledge to write our efficient merkle tree database.

In the previous installment of our series, we already proved that, when you update a leaf in a merkle tree, only the nodes alone the leaf’s merkle path will change:

Using this principle, we make a merkle tree database which only stores all the nodes in the tree that aren’t zero hashes, and follows the procedure:

To find the value of node N(level, index):

• Check if it exists in the database. If it does, return the value.
• If it does not exist, return the corresponding zero hash for the node’s level
• If you want to update a node, first set the leaf, compute the leaf’s merkle path, and then save all the new node values in the merkle path to the database

In this way, we will create a database which only needs to store the non-zero hash nodes, perfect for our large, sparse merkle trees!

Let’s start by writing a simple data store which follows our rule for getting nodes from the datastore (return if it exists, else fallback to a zero hash):

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];
    }
  }
}

Great! Now we can write a ZeroMerkleTree class which uses the NodeStore:

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

Following what we learned in the previous installment, we know that we can compute the merkle path of a node by dividing the index by 2 each time we go up a level in the merkle path:

function getMerklePathOfNode(level, index){
  const merklePath = [];
  for(let currentLevel=level;currentLevel>=0;currentLevel--){
    merklePath.push({
      level: currentLevel,
      index: index,
    });
    index = Math.floor(index/2);
  }
  return merklePath;
}

Applying this knowledge, lets write a setLeaf function which sets a leaf in the tree and updates its merkle path according to the same logic as our getMerklePathOfNode function and the even-odd hashing rule for siblings:

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);
  }
}

Great! Let’s check if its working by adding a getRoot function which returns the merkle root

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

Putting everything together we get:

Running this function yields the result:

[example2] the root is: 7e286a6721a66675ea033a4dcdec5abbdc7d3c81580e2d6ded7433ed113b7737

We can see if we got everything right by comparing it with the merkle root we calculated from a tree with the same leaves in our previous installment:

A perfect match 🎉, now we can make it even more useful by returning a delta merkle proof whenever we call setLeaf.

Recalling our previous definition of delta merkle proofs we will need the following data:

• index of the leaf (index)
• the siblings of the leaf’s merkle path (siblings)
• the root before the leaf was changed (oldRoot)
• the value of the leaf before it was changed (oldValue)
• the root after the leaf is changed (newRoot)
• the new value of the leaf (newValue)

type MerkleNodeValue = string;
interface IDeltaMerkleProof {
  index: number;
  siblings: MerkleNodeValue[];
  oldRoot: MerkleNodeValue;
  oldValue: MerkleNodeValue;
  newRoot: MerkleNodeValue;
  newValue: MerkleNodeValue;
}

To do this, we can modify the start of our setLeaf function to record the value of the oldRoot and oldValue before we make our update + add a siblings array to keep track of the siblings of the leaf’s merkle path:

...
  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[] = [];
...

Then, we can modify the body of the loop where we hash the node on the merkle path with its sibling to also push the siblings value to our siblings array:

...
  setLeaf(index: number, value: MerkleNodeValue): IDeltaMerkleProof{
    ...
    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); // <---- HERE
      }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); // <---- HERE
      }
      // set current index to the index of the parent node
      currentIndex = Math.floor(currentIndex/2);
    }
...

Then at the end of the function, we just need to use our new variables to return a delta merkle proof at the end of our setLeaf function:

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 { // <--- HERE
      index,
      siblings,
      oldRoot,
      oldValue,
      newValue: value,
      newRoot: currentValue,
    };
  }

Putting everything together, we can copy over our verifyDeltaMerkleProof from the previous installment to check to make sure the delta merkle proofs are valid:

Let’s run the javascript and see if it works:

[example3] delta merkle proof for index 0 is valid
[example3] delta merkle proof for index 1 is valid
[example3] delta merkle proof for index 2 is valid
[example3] delta merkle proof for index 3 is valid
[example3] delta merkle proof for index 4 is valid
[example3] delta merkle proof for index 5 is valid
[example3] delta merkle proof for index 6 is valid
[example3] delta merkle proof for index 7 is valid
[example3] the delta merkle proofs are:
[
  {
    "index": 0,
    "siblings": [
      "0000000000000000000000000000000000000000000000000000000000000000",
      "f5a5fd42d16a20302798ef6ed309979b43003d2320d9f0e8ea9831a92759fb4b",
      "db56114e00fdd4c1f85c892bf35ac9a89289aaecb1ebd0a96cde606a748b5d71"
    ],
    "oldRoot": "c78009fdf07fc56a11f122370658a353aaa542ed63e44c4bc15ff4cd105ab33c",
    "oldValue": "0000000000000000000000000000000000000000000000000000000000000000",
    "newValue": "0000000000000000000000000000000000000000000000000000000000000001",
    "newRoot": "f06e424318b067ae608de0ef0035e9f48a2658cc59e7f94f9f94600b2a36eac6"
  },
  ... /* omitted for brevity, check codepen for full result */
]

Success! All of the delta merkle proofs are valid!

Chain Delta Merkle Proofs

Along with verifying delta merkle proofs, another important check that our zkVM will have to perform is known as a chain delta merkle proof verification.

A chain delta merkle proof verification ensures that a series of delta merkle proofs are sequential, meaning that you have provided all the proofs for the state transition from the first delta merkle proof’s oldRoot to the last delta merkle proof in the series’s newRoot.

We can perform this verification by asserting that, for each delta merkle proof in the series, the oldRoot of the current proof equals the newRoot of the previous proof:

...
for(let i=0;i<deltaMerkleProofs.length;i++){
  const deltaProof = deltaMerkleProofs[i];
  if(!verifyDeltaMerkleProof(deltaProof)){ //first verify the proof
    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){ // <------ [HERE]
    // 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");
  }
}
...

Let’s update our code to include a chain delta merkle proof verification and check to make sure our code is working properly:

Running example4, we get the result:

[example4] delta merkle proof for index 0 is valid
[example4] delta merkle proof for index 1 is valid
[example4] delta merkle proof for index 2 is valid
[example4] delta merkle proof for index 3 is valid
[example4] delta merkle proof for index 4 is valid
[example4] delta merkle proof for index 5 is valid
[example4] delta merkle proof for index 6 is valid
[example4] delta merkle proof for index 7 is valid
[example4] the delta merkle proofs are:
[
... /* omitted for brevity, check codepen for full result */
]

Great! No errors 🎉, we have proves the changes we made are valid (delta merkle proof) and sequential (chain delta merkle proof).

Finishing up our ZMT Database

The final import function we will want to implement is a getLeaf function which returns the value of a leaf and an accompanying merkle proof of its inclusion within the tree. To do this, we just need to grab the value of the leaf, and then walk its merkle path to obtain the siblings and root using the same strategy we used for computing the delta merkle proof in setLeaf:

class ZeroMerkleTree {
...
  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,
    };
  }
...

We can now put everything together to and use the verifyMerkleProof function we wrote in the previous installment to verify the merkle proofs generated by getLeaf (full code gist):

/* see https://gist.github.com/cf/1b04459735c0b86dda56714205566c97 */
...
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();

Running the code we get the result:

[example5] delta merkle proof for index 0 is valid
[example5] delta merkle proof for index 1 is valid
[example5] delta merkle proof for index 2 is valid
[example5] delta merkle proof for index 3 is valid
[example5] delta merkle proof for index 4 is valid
[example5] delta merkle proof for index 5 is valid
[example5] delta merkle proof for index 6 is valid
[example5] delta merkle proof for index 7 is valid
[example5] merkle proof for index 0 is valid
merkle proof for index 0: {
  "root": "7e286a6721a66675ea033a4dcdec5abbdc7d3c81580e2d6ded7433ed113b7737",
  "siblings": [
    "0000000000000000000000000000000000000000000000000000000000000003",
    "6b0e4bcd4368ba74e6a99ee69334c2593bcae1170d77048854d228664218c56b",
    "81b1e323f0e91a785dfd155817e09949a7d66fe8fdc4f31f39530845e88ab63c"
  ],
  "index": 0,
  "value": "0000000000000000000000000000000000000000000000000000000000000001"
}
[example5] merkle proof for index 1 is valid
... /* excluded for brevity, check the codepen above for the full result */

Fantastic!

We have now written a merkle tree database which we can use with our zkVM 🎉🎉🎉

To show off our new super-powered merkle tree, lets create a merkle tree of height 50, which has 1,125,899,906,842,624 leaves, and set values for the 1337th and 999,999,999,999th node (link to code)

At 64 bytes of storage per leaf, our previous implementation would need 64 petabytes of RAM just to store the tree (not even modern super computers are capable of this), yet with our new ZeroMerkleTree implementation we can do this in the blink of an eye on laptop and only consume 6400 bytes:

// for the whole code check the gist at https://gist.github.com/cf/9df9b18cd5877fb4fc5c8b31a3acf77d
...
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();

Which prints the result:

verifyDeltaMerkleProof(deltaA): true
verifyDeltaMerkleProof(deltaB): true
deltaA.newRoot === deltaB.oldRoot: true
verifyMerkleProof(proofA): true
verifyMerkleProof(proofB): true
proofA: {
  "root": "40db8b6edad868d911c8b9aea2692ee80b2e87ac407b8d1a5efe30419e843991",
  "siblings": 
   ... /* omitted for brevity, check the code pen for the full result */
  ],
  "index": 999999999999,
  "value": "0000000000000000000000000000000000000000000000000000000000000008"
}
proofB: {
  "root": "40db8b6edad868d911c8b9aea2692ee80b2e87ac407b8d1a5efe30419e843991",
  "siblings": [
    ... /* omitted for brevity, check the code pen for the full result */
  ],
  "index": 1337,
  "value": "0000000000000000000000000000000000000000000000000000000000000007"
}

We have climbed the impossible mountain, and built a merkle tree ready for our zkVM, all thanks to ZeroHashes and our ZMT 💪

Append Only Merkle Trees

Our ZMT implementation is perfect for our zkVM use case, but when we are building on legacy blockchains (EVM/zkEVM), storage can be expensive to the point where even our ZMT will prove too costly to make sense for use cases like verifiable event logs.

We will touch on verifiable event logs in more detail in a future installment where we explore trustless cross chain bridges, but for now it is sufficient to know that these write-only merkle trees are critical for trustlessly bridging data & assets from layer 1 to layer 2.

The Verifiable Event Log

The basic theory behind a verifiable event log is that we want to allow a smart contract to record events in the leaves of a merkle tree. Whenever a new event occurs, we append a leaf to the merkle tree (set the next non-zero leaf in the merkle tree to the hash of the event) and calculate the updated root. You can then process these events off-chain using zero knowledge proofs or a layer 2, and submit proofs which prove you have sync’d all the events up to the latest event log root, thus providing trustless data transfer from layer 1 to layer 2.

The most important property of use case is that the smart contract only needs to write leaves to the merkle tree and never has to read back the previous event leaves (we only really care about reading the latest root).

With our understanding of the zero hashes and some cleverness, it turns out that we will be able to build an append-only merkle tree of height N which only needs to store O(log(N)) hashes on chain!

As we did before, let’s get started by visualizing the changes in the merkle tree when we append leaves and see if we can find any patterns.

In the animation below, we visualize the delta merkle proof results from appending a leaf where:

• the purple node represents the leaf being appending
• the blue nodes represent the leaf’s merkle path
• the red nodes represent the siblings

Recall that our goal is to be able to some how compute the new merkle root while storing the minimum amount of data possible. We also know from our previous installment that the information required to compute a merkle tree’s root is known as a merkle proof and contains the following information

• index (index of the leaf)
• value (value of the leaf)
• siblings (siblings of the leaf’s merkle path)

In the case of our append only merkle tree, the index and value will be passed to the function, so the only thing we would be missing for our calculation is a method for calculating the siblings for the next merkle proof using the data stored in our contract. If we used the ZMT implementation from the previous section, we would have to store all the nodes in the tree on-chain, which is undesirable.

One way we might go about tackling the problem is storing the previous node’s merkle proof, and somehow writing a function which computes the new siblings from the previous nodes merkle proof.

If we could do that, we could accomplish our goal of O(log(n)) storage by repeating the procedure below each time we append a leaf to the tree:

1. Read the previous merkle proof from the smart contract storage, and increment the index by 1
2. Somehow calculate the new siblings for the leaf we are appending using the zero hashes and the previous merkle proof
3. Compute the new merkle root using the new siblings and the value we are appending, and then overwrite the old merkle proof with the newly appended leaf’s merkle proof to the smart contract storage

This of course begs the question: is it possible to compute the siblings of the next leaf in our append only merkle tree using only the zero hashes and previous merkle proof?

Let’s examine the animation once again, but this time let’s pay attention to how the siblings change as each leaf is appended to the tree. We will still color all the sibling nodes red, but this time we will make the sibling’s text yellow if it was not a sibling for the previous node’s merkle proof:

Starting to see the pattern? The key to cracking this puzzle is remembering that the siblings are just the adjacent nodes to the leaf’s merkle path, so when transitioning from leaf N to leaf N+1:

• On the levels where the merkle paths of leaf N and leaf N+1 are the same, you can reuse the sibling from leaf N’s merkle proof in leaf N+1’s merkle proof
• On the levels where the merkle paths of leaf N and leaf N+1 are the different, you need to somehow compute what new sibling is.

Great! So for the levels where the merkle path doesn’t change, we know to just reuse the sibling from the previous leaf’s proof, but what about the second case?

Let’s examine some more append transition to get some intuition:

Notice that, because it is an append-only merkle tree, our leaf index is always increasing, and therefore our path is always moving to the right.

Let’s write down what we know about the relationship between Leaf[n] and Leaf[n+1]’s merkle paths/siblings on a tree with height H and then try to deduce a formula from the facts we know:

Aha! So the only information we will need to generate a merkle proof for Leaf[n+1] is:

• the zero hashes for the tree
• Leaf[n]’s siblings/value
• Leaf[n]’s merkle path (we can compute this using the siblings and value!)
• Leaf[n+1]’s value

This is very cool, it looks like all we need to store when building our append only merkle tree is latest leaf’s merkle proof!

Let’s write our implementation based on the facts we wrote down above:

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,
    };
  }
}

Looks good, let’s test it out using our previous verify delta merkle proof function to make sure it is working correctly:

When we run example7, we get the output:

verifyDeltaMerkleProof(deltaA): true
verifyDeltaMerkleProof(deltaB): true
deltaA.newRoot === deltaB.oldRoot: true
deltaA: {
  "index": 0,
  "siblings": [
... /* omitted for brevity, check the code pen for the full result */
  ],
  "oldRoot": "e833d7a67160e68bf4c9044a53077df2727ad00cf36f4949c7b681a912140cbb",
  "oldValue": "0000000000000000000000000000000000000000000000000000000000000000",
  "newRoot": "bfe0338f3c07c1ff64514ccde5d0e4535b88c9093454b29de1590414c721abb1",
  "newValue": "0000000000000000000000000000000000000000000000000000000000000008"
}
deltaB: {
  "index": 1,
  "siblings": [
... /* omitted for brevity, check the code pen for the full result */
  ],
  "oldRoot": "bfe0338f3c07c1ff64514ccde5d0e4535b88c9093454b29de1590414c721abb1",
  "oldValue": "0000000000000000000000000000000000000000000000000000000000000000",
  "newRoot": "3b6c4c5cf467972101c5236a32eb2f5e23c66fab942352d1e7003660f83f66b2",
  "newValue": "0000000000000000000000000000000000000000000000000000000000000007"
}
verifyDeltaMerkleProof(delta[0]): true
verifyDeltaMerkleProof(delta[1]): true
verifyDeltaMerkleProof(delta[2]): true
verifyDeltaMerkleProof(delta[3]): true
verifyDeltaMerkleProof(delta[4]): true
verifyDeltaMerkleProof(delta[5]): true
verifyDeltaMerkleProof(delta[6]): true
verifyDeltaMerkleProof(delta[7]): true
verifyDeltaMerkleProof(delta[8]): true
verifyDeltaMerkleProof(delta[9]): true
verifyDeltaMerkleProof(delta[10]): true
verifyDeltaMerkleProof(delta[11]): true
verifyDeltaMerkleProof(delta[12]): true
verifyDeltaMerkleProof(delta[13]): true
verifyDeltaMerkleProof(delta[14]): true
verifyDeltaMerkleProof(delta[15]): true
verifyDeltaMerkleProof(delta[16]): true
verifyDeltaMerkleProof(delta[17]): true
verifyDeltaMerkleProof(delta[18]): true
verifyDeltaMerkleProof(delta[19]): true
verifyDeltaMerkleProof(delta[20]): true
verifyDeltaMerkleProof(delta[21]): true
verifyDeltaMerkleProof(delta[22]): true
verifyDeltaMerkleProof(delta[23]): true
verifyDeltaMerkleProof(delta[24]): true
verifyDeltaMerkleProof(delta[25]): true
verifyDeltaMerkleProof(delta[26]): true
verifyDeltaMerkleProof(delta[27]): true
verifyDeltaMerkleProof(delta[28]): true
verifyDeltaMerkleProof(delta[29]): true
verifyDeltaMerkleProof(delta[30]): true
verifyDeltaMerkleProof(delta[31]): true
verifyDeltaMerkleProof(delta[32]): true
verifyDeltaMerkleProof(delta[33]): true
verifyDeltaMerkleProof(delta[34]): true
verifyDeltaMerkleProof(delta[35]): true
verifyDeltaMerkleProof(delta[36]): true
verifyDeltaMerkleProof(delta[37]): true
verifyDeltaMerkleProof(delta[38]): true
verifyDeltaMerkleProof(delta[39]): true
verifyDeltaMerkleProof(delta[40]): true
verifyDeltaMerkleProof(delta[41]): true
verifyDeltaMerkleProof(delta[42]): true
verifyDeltaMerkleProof(delta[43]): true
verifyDeltaMerkleProof(delta[44]): true
verifyDeltaMerkleProof(delta[45]): true
verifyDeltaMerkleProof(delta[46]): true
verifyDeltaMerkleProof(delta[47]): true
verifyDeltaMerkleProof(delta[48]): true
verifyDeltaMerkleProof(delta[49]): true

Success!

Since we are only storing one merkle proof in our class, we only need O(log(n)) storage for our append only merkle tree 🎉

Spiderman Proofs

Sometimes we want to update whole sections of a tree:

Using our ZMT implementation, we can already do this by updating each leaf, one-by-one, but perhaps there is a better way to go about updating batches of leaves.

Let’s first try the tree highlighted in red on the the left:

Notice that the sub tree with root N(1,0) in our big tree looks the same as our updated smaller tree on the bottom, except with different values.

If we also look carefully at the big tree on top, the nodes above the sub-tree we want to modify form a tiny height = 1 tree of their own:

Great! We know how to update the leaves of a merkle tree, let’s start building a delta merkle proof from the information we know.

• We know that the node we want to update is N(1,0), so the index of the delta merkle proof will be 1.
• We know that the siblings of the delta merkle proof will be [N(1,1)] because N(1,0) is the only node on the merkle path, and its sibling is N(1,1)
• We know that the old root of the delta merkle proof will be our old N(0,0)
• We know that our old value is the value of N(1,0) because that’s the “leaf” we want to update

Now all we have to do is update the leaf, and apply the rules for delta merkle proofs that we learned in the previous installment:

Fantastic! We now know how to efficiently replace sections of our merkle tree and generate delta merkle proofs to prove the validity of our changes.

For the rest of the sub-trees we want to replace, we can just update them in succession using the same rules:

For now, we won’t write the code in TypeScript for this operation, as we will only need to write this logic in our arithmetic circuit for reasons we will explore in a future installment.

Conclusion

Great work if you have made it this far, you now know all the information about merkle trees that will be needed for constructing our zkVM!

In our next installment, we will write our first zero knowledge circuits using plonky2, and begin implementing our zkVM!

Thanks to our sponsors OAS & QED, you can follow OAS on twitter @OASNetwork

about the author — follow @cmpeq on twitter or check out my about page.

This is the first weekly installment of A Hackers Guide to Layer 2: Building a zkVM from Scratch.

Follow @cmpeq on twitter to stay up to date with future installments.

What I cannot create, I do not understand.
Richard Feynman

Introduction

Merkle trees are one of the most important tools in any would be layer 2 developer’s toolbox. In the spirit of Feynman’s approach to understanding a topic, we will implement Merkle Trees from scratch and build deep Merkle Tree intuition that will be essential later in our layer 2 development journey.

Inventing Merkle Trees: Data Integrity

Let’s imagine Jack wants to send a 400 gigabyte file to his friend Sally over an unreliable internet connection. It will take hours for the file to send, and Sally wants to make sure that the file she gets isn’t corrupted or changed while it is being transferred.

One way we might try to solve this is by having Jack create a digital signature of the whole file, and then have Sally verify the signature when the file transfer is complete. Unfortunately, however, digital signature technology has a property that: the longer the data you want to sign, the slower it takes to generate a digital signature, so it is impractical for Jack digitally sign the whole file.

They can get around this problem by taking advantage of digital fingerprint (also known as cryptographic hashing) technology. Taking the hash (or digital fingerprint) of a large file generates a short 32 byte number to represent the data that was hashed. Most importantly, if you change even a single byte of the large file, its fingerprint will also change:

1. Jack sends the hash, the signature and the file to Sally
2. When Sally receives the file, she computes the hash on her machine, and then checks to see if the hash matches the one that Jack digitally signed.

This is all well and good, but since the transfer can take hours and it is very likely that something gets corrupted during the transfer, Sally keeps on finding that the hash she computes is different than the one signed by Jack, and Jack has to send the 400 GB file all over again (very slow).

One way to fix this would be to have Jack first split the file into two pieces (A and B) and hash each piece. That way the size of any data that has to be resent is 200 GB instead of 400 GB.

If Jack is really clever, he can make it so he still only has to compute one digital signature, by signing the Hash(Hash(A)+Hash(B)) (called the Root). This way Sally knows the hashes of A and B weren’t modified during the transfer and can be confident that the file she receives is the same as Jack’s original file. If any data in A or B is modified, Hash(Hash(A)+Hash(B)) will not match Jack’s original signature.

In fact, we can split the file into even smaller pieces to make the size of the any data that has to be resent much smaller:

This business of splitting up data and recursively hashing is called a building a Merkle Tree.

Like in our example, the basic principle of a Merkle Tree is:
if you modify the value of any of the nodes at the bottom which represent our dataset, the value of the node at the top will also change.

The nodes at the bottom which contain our dataset are known as leaves and the node at the top (aka. N(0,0)) is known as the Merkle Root.

For convenience, we can identify each node N with two numbers:

1. The level of the node (the top node is on level 0, and the nodes below it has level = 1, etc.)
2. The index of the node (for the index, we just count from left to right with the node furthest left having index = 0)

Using our node definition, we can also say that every node N(level, index), has two children N(level+1, index*2) and N(level+1, index*2+1). This is to reflect that each level has twice as many nodes as the level above it.

In addition, using our previous rule of computing Hash(Hash(A), Hash(B)), we can define the value of each non-leaf node as:
N(level, index) = Hash(N(level+1, index*2), N(level+1, index*2+1))

We can also define the height of the merkle tree as the distance from the leaves from the merkle root (ie. count the lines in the path between the leaf nodes and the root node at the top). The leaves of the Merkle Tree always have a level number equal to the height of the tree.

Coding a Merkle Tree

Now that we have invented the Merkle Tree, we can demonstrate our new found knowledge by writing a JavaScript implementation.

First we will need to select a function to calculate our digital fingerprints. We can use the common sha256 hashing function to do the job of computing Hash(childA, childB):

const shajs = require("sha.js"); // npm install --save sha.js

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

With a hash function in hand, we can write a simple class which computes the merkle root given a dataset of leaves and the corresponding tree height:

const shajs = require("sha.js"); // npm install --save sha.js

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

class MerkleTree {
  constructor(height, leaves){
    this.height = height;
    this.leaves = leaves;
  }
  N(level, index){
    if(level === this.height){
      // if level == height, the node is a leaf, 
      // so just return the value from our dataset
      return this.leaves[index];
    }else{
      // if the node is not a leaf, use our definition:
      // N(level, index) = Hash(N(level+1, index*2), N(level+1, index*2+1))
      return hash(
        this.N(level+1, 2*index),
        this.N(level+1, 2*index+1),
      );
    }
  }
  getRoot(){
    // the node N(0,0) is always the root node
    return this.N(0,0);
  }
}

Let’s test out our merkle tree implementation with a tree that has
leaves = [1, 3, 3, 7, 4, 2, 0, 6] and a height of 3:

In our JavaScript file, we can write each leaf as a hexadecimal string, create a new instance of MerkleTree, and call the getRoot function to compute the root:

function example1(){
  const height = 3;
  const leaves = [
    "0000000000000000000000000000000000000000000000000000000000000001", // 1
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000007", // 7
    "0000000000000000000000000000000000000000000000000000000000000004", // 4
    "0000000000000000000000000000000000000000000000000000000000000002", // 2
    "0000000000000000000000000000000000000000000000000000000000000000", // 0
    "0000000000000000000000000000000000000000000000000000000000000006", // 6
  ];
  const tree = new MerkleTree(height, leaves);
  console.log("[EX_1] the merkle tree's root is: "+tree.getRoot());
}
example1();

If we run this code, we will get the output:

[EX_1] the merkle tree's root is: 7e286a6721a66675ea033a4dcdec5abbdc7d3c81580e2d6ded7433ed113b7737

If we change any of the leaves (for example, changing the 2 to a 9), we should also see that the root changes:

function example2(){
  const height = 3;
  const leaves = [
    "0000000000000000000000000000000000000000000000000000000000000001", // 1
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000007", // 7
    "0000000000000000000000000000000000000000000000000000000000000004", // 4
    "0000000000000000000000000000000000000000000000000000000000000002", // 2
    "0000000000000000000000000000000000000000000000000000000000000000", // 0
    "0000000000000000000000000000000000000000000000000000000000000006", // 6
  ];
  const tree = new MerkleTree(height, leaves);
  console.log("[EX_2] before root is: "+tree.getRoot());
  // change the 2 to a 9
  tree.leaves[5] = "0000000000000000000000000000000000000000000000000000000000000009";
  console.log("[EX_2] after root is: "+tree.getRoot());
}
example2();

If we run example2(), we will see the output:

[EX_2] before root is: 7e286a6721a66675ea033a4dcdec5abbdc7d3c81580e2d6ded7433ed113b7737
[EX_2] after root is: e74ae221cf067dc8e88195f5b30bfda60dc224a8cd5554bc6345c87ad8c6f925

Success! The root before the change matches our original root because it had the same dataset, and the after root has updated because we changed one of the leaves in the dataset.

Let’s look deeper into why changing one of the leaves changes the root:

• Since we changed N(3,5), its parent N(2,2) changes because N(2,2) is defined as N(2,2) = Hash(N(3,4), N(3,5))
• Since N(2,2) changed, its parent N(1,1) changes because N(1,1) is defined as N(1,1) = Hash(N(2,2), N(2,3))
• Since N(1,1) changed, its parent N(0,0) changes because N(0,0) is defined as N(0,0) = Hash(N(1,0), N(1,1))

The nodes that change when you update a leaf, are called the node’s merkle path. So in this case, we could say the merkle path of N(3,5) is [N(3,5), N(2,2), N(1,1), N(0,0)].

To compute the merkle path of a node, we just recursively list out the ancestors of the node. (ancestors = parent of node, parent of parent, parent of parent of parent…).

Since we know from before that every node N(level, index), has two children N(level+1, index*2) and N(level+1, index*2+1), we can say that the parent of a node N(level, index) is N(level-1, floor(index/2)).

Using this knowledge, we can write a JavaScript function to calculate the merkle path of a node and check our earlier observation with N(3,5):

function getMerklePathOfNode(level, index){
  const merklePath = [];
  for(let currentLevel=level;currentLevel>=0;currentLevel--){
    merklePath.push({
      level: currentLevel,
      index: index,
    });
    index = Math.floor(index/2);
  }
  return merklePath;
}

console.log(getMerklePathOfNode(3,5))

When we run it, the log prints [N(3,5), N(2,2), N(1,1), N(0,0)]:

[
  { level: 3, index: 5 },
  { level: 2, index: 2 },
  { level: 1, index: 1 },
  { level: 0, index: 0 }
]

In practice, we often exclude the root node from our returned merkle path as every node’s merkle path contains it, so we can rewrite our function to return the all nodes in the merkle path except the root (level>0):

function getMerklePathOfNode(level, index){
  const merklePath = [];
  for(let currentLevel=level;currentLevel>0;currentLevel--){
    merklePath.push({
      level: currentLevel,
      index: index,
    });
    index = Math.floor(index/2);
  }
  return merklePath;
}

Siblings

Before we continue it is important that we talk about the concept of left handed and right handed nodes on a merkle tree.

• We say that a node is left handed if it appears in the tree on the left side of its parent.
• We say that a node is right handed if it appears in the tree on the right side of its parent.

Given our original definition of the merkle tree where we say that every non-leaf node N(level, index) has a left child and a right child:

• Left Child: N(level+1, 2*index)
• Right Child: N(level+1, 2*index + 1)

Given this definition, we can see that all left handed nodes have an even index (2*x), and right handed nodes have an odd index (2*x+1).

Therefore:

• If a node N(level, index) has an even index, we say that its opposite handed sibling is N(level, index+1).
• If a node N(level, index) has an odd index, we say that its opposite handed sibling is N(level, index-1)

Let’s write a JavaScript function to return the sibling of any node we specify on a tree:

function getSiblingNode(level, index){
  // if node is the root, it has no sibling
  if(level === 0){
    throw new Error("the root does not have a sibling")
  }else if(index % 2 === 0){
    // if node is even, its sibling is at index+1
    return {level: level, index: index+1};
  }else{
    // if node is odd, its sibling is at index-1
    return {level: level, index: index-1};
  }
}

Merkle Proofs

We often want to prove the inclusion of a certain leaf in a merkle tree with a known root. Let’s imagine Bob wants to prove to his friend Todd that the value 9 exists at leaf N(3,5) on a tree with a known merkle root R.

The most naive way for Bob to do this is:

1. Bob gives Todd a list of all the leaves
2. Todd uses our MerkleTree class to calculate N(0,0)
3. Todd compares N(0,0) with R to make sure they are the same

For large trees, however, this is not very practical. If Bob wants to prove the value of a leaf in a tree with 1,000,000 leaves, Bob must send all 1,000,000 leaves to Todd, and Todd must do 999,999 computations to calculate the root.

If we look back at our merkle path diagram, however, there is a faster way we can do this:

In our diagram we can see that Todd can calculate the root if Bob gives him: the value of the leaf, the index of the leaf and the siblings of the non-root nodes on the leaf’s merkle path (N(3,4), N(2,3) and N(1,0)):

N(0,0) = Hash(N(1,0), Hash(Hash(N(3,4), 9), N(2,3)))

Using this method, for a tree with N leaves, Todd only needs to compute log(N) computations, so if the tree has 1,000,00 leaves, he only needs to perform 20 computations instead of instead of 999,999 computations!

The value, index and siblings together are known as a merkle proof, as they are the key ingredients required to prove a leaf’s existence in a merkle tree with a known root.

Let’s first write a function the calculate the siblings of a given node’s merkle path:

Let’s update our MerkleTree class to include a getMerkleProof function:

class MerkleTree {
// ...
getMerkleProof(level, index){

    // get the value of the leaf node
    const leafValue = this.N(level, index);

    // get the levels and indexes of the nodes on the leaf's merkle path
    const merklePath = getMerklePathOfNode(level, index);

    // get the levels and indexes of the siblings of the nodes on the merkle path
    const merklePathSiblings = merklePath.map((node) => {
      return getSiblingNode(node.level, node.index);
    });

    // get the values of the sibling nodes
    const siblingValues = merklePathSiblings.map((node) => {
      return this.N(node.level, node.index);
    });

    return {
      root: this.getRoot(), // the root we claim to be our tree's root
      siblings: siblingValues, // the siblings of our leaf's merkle path
      index: index, // the index of our leaf
      value: leafValue, // the value of our leaf
    };
  }
}

We can also write a function which calculates the merkle root using the proof’s siblings, index and value:

function computeMerkleRootFromProof(siblings, index, value){
  // 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;
}

Finally, let’s write a function which verifies the merkle proof:

function verifyMerkleProof(proof){
  return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}

Putting it all together, we now have a class which can generate a merkle proof of inclusion that can be verified in O(log(n)) time 🎉

const shajs = require("sha.js"); // npm install --save sha.js

function hash(leftNode, rightNode) {
  return shajs("sha256")
    .update(leftNode + rightNode, "hex")
    .digest("hex");
}
function getSiblingNode(level, index){
  // if node is the root, it has no sibling
  if(level === 0){
    throw new Error("the root does not have a sibling")
  }else if(index % 2 === 0){
    // if node is even, its sibling is at index+1
    return {level: level, index: index+1};
  }else{
    // if node is odd, its sibling is at index-1
    return {level: level, index: index-1};
  }
}
function getMerklePathOfNode(level, index){
  const merklePath = [];
  for(let currentLevel=level;currentLevel>0;currentLevel--){
    merklePath.push({
      level: currentLevel,
      index: index,
    });
    index = Math.floor(index/2);
  }
  return merklePath;
}
class MerkleTree {
  constructor(height, leaves){
    this.height = height;
    this.leaves = leaves;
  }
  N(level, index){
    if(level === this.height){
      // if level == height, the node is a leaf, 
      // so just return the value from our dataset
      return this.leaves[index];
    }else{
      // if the node is not a leaf, use our definition:
      // N(level, index) = Hash(N(level+1, index*2), N(level+1, index*2+1))
      return hash(
        this.N(level+1, 2*index),
        this.N(level+1, 2*index+1),
      );
    }
  }
  getRoot(){
    // the node N(0,0) is always the root node
    return this.N(0,0);
  }
  getMerkleProof(level, index){

    // get the value of the leaf node
    const leafValue = this.N(level, index);

    // get the levels and indexes of the nodes on the leaf's merkle path
    const merklePath = getMerklePathOfNode(level, index);

    // get the levels and indexes of the siblings of the nodes on the merkle path
    const merklePathSiblings = merklePath.map((node) => {
      return getSiblingNode(node.level, node.index);
    });

    // get the values of the sibling nodes
    const siblingValues = merklePathSiblings.map((node) => {
      return this.N(node.level, node.index);
    });

    return {
      root: this.getRoot(), // the root we claim to be our tree's root
      siblings: siblingValues, // the siblings of our leaf's merkle path
      index: index, // the index of our leaf
      value: leafValue, // the value of our leaf
    };
  }
}
function computeMerkleRootFromProof(siblings, index, value){
  // 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){
  return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function example4(){
  const height = 3;
  const leaves = [
    "0000000000000000000000000000000000000000000000000000000000000001", // 1
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000007", // 7
    "0000000000000000000000000000000000000000000000000000000000000004", // 4
    "0000000000000000000000000000000000000000000000000000000000000009", // 9
    "0000000000000000000000000000000000000000000000000000000000000000", // 0
    "0000000000000000000000000000000000000000000000000000000000000006", // 6
  ];
  const tree = new MerkleTree(height, leaves);
  console.log("[EX_4] the root is: "+tree.getRoot());
  const merkleProofOfN3_5 = tree.getMerkleProof(3,5);

  console.log("[EX_4] the merkle proof of N(3,5):\n" + JSON.stringify(merkleProofOfN3_5, null, 2));

  console.log("[EX_4] computed root: "+computeMerkleRootFromProof(merkleProofOfN3_5.siblings, merkleProofOfN3_5.index, merkleProofOfN3_5.value));
  console.log("[EX_4] verify merkle proof: "+verifyMerkleProof(merkleProofOfN3_5));
}

example4();

This prints:

[EX_4] the root is: e74ae221cf067dc8e88195f5b30bfda60dc224a8cd5554bc6345c87ad8c6f925
[EX_4] the merkle proof of N(3,5):
{
  "root": "e74ae221cf067dc8e88195f5b30bfda60dc224a8cd5554bc6345c87ad8c6f925",
  "siblings": [
    "0000000000000000000000000000000000000000000000000000000000000004",
    "deb2a27a00dbc46e3a59096a8d07d2b97f950158886411ff6a9c9ab9623dada6",
    "2f4d3e941b602c50347af3f5c809a28737c27c7ce460e77b10739875ef957aa7"
  ],
  "index": 5,
  "value": "0000000000000000000000000000000000000000000000000000000000000009"
}
[EX_4] computed root: e74ae221cf067dc8e88195f5b30bfda60dc224a8cd5554bc6345c87ad8c6f925
[EX_4] verify merkle proof: true

Delta Merkle Proofs

If we have merkle tree with root A, and we generate a merkle proof that has siblings

In addition to proving that a certain leaf exists in a merkle tree, we will often want to prove the result of modifying a specific leaf in a tree from one value to another. This is called a delta merkle proof (delta means change).

In particular, delta merkle proofs prove:

• A leaf exists at index I with value X in a tree with merkle root A
• If you change the value of the leaf with index I from X to Y without modifying any other leaves in the tree, the new merkle root of the tree is B

We already know how to prove “A leaf exists at index I with value X in a tree with merkle root A”; we can just call the getMerkleProof function on our contract.

If we then modify the leaf, let’s say from 9 to 8, let’s call getMerkleProof again and see what happens:

function example5(){
  const height = 3;
  const leaves = [
    "0000000000000000000000000000000000000000000000000000000000000001", // 1
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000007", // 7
    "0000000000000000000000000000000000000000000000000000000000000004", // 4
    "0000000000000000000000000000000000000000000000000000000000000009", // 9
    "0000000000000000000000000000000000000000000000000000000000000000", // 0
    "0000000000000000000000000000000000000000000000000000000000000006", // 6
  ];
  const tree = new MerkleTree(height, leaves);
  const beforeMerkleProofOfN3_5 = tree.getMerkleProof(3,5);
  console.log("[EX_5] the merkle proof of N(3,5) before change:\n" + JSON.stringify(beforeMerkleProofOfN3_5, null, 2));
  // change 9 to 8
  tree.leaves[5] = "0000000000000000000000000000000000000000000000000000000000000008";

  const afterMerkleProofOfN3_5 = tree.getMerkleProof(3,5);
  console.log("[EX_5] the merkle proof of N(3,5) after change:\n" + JSON.stringify(afterMerkleProofOfN3_5, null, 2));
}
example5();

This prints:

[EX_5] the merkle proof of N(3,5) before change:
{
  "root": "e74ae221cf067dc8e88195f5b30bfda60dc224a8cd5554bc6345c87ad8c6f925",
  "siblings": [
    "0000000000000000000000000000000000000000000000000000000000000004",
    "deb2a27a00dbc46e3a59096a8d07d2b97f950158886411ff6a9c9ab9623dada6",
    "2f4d3e941b602c50347af3f5c809a28737c27c7ce460e77b10739875ef957aa7"
  ],
  "index": 5,
  "value": "0000000000000000000000000000000000000000000000000000000000000009"
}
[EX_5] the merkle proof of N(3,5) after change:
{
  "root": "99ba6856d11cd514be35ed291e86ae7957ec43d6b83270f32aaa50a8a25dc5cc",
  "siblings": [
    "0000000000000000000000000000000000000000000000000000000000000004",
    "deb2a27a00dbc46e3a59096a8d07d2b97f950158886411ff6a9c9ab9623dada6",
    "2f4d3e941b602c50347af3f5c809a28737c27c7ce460e77b10739875ef957aa7"
  ],
  "index": 5,
  "value": "0000000000000000000000000000000000000000000000000000000000000008"
}

Aha!

Notice that the siblings are the same in the before and after proof’s!

Remember that when we update a leaf, it only changes the nodes on the leaf’s merkle path, and since by definition the leaf’s merkle path does not include any siblings, the before and after proofs have the same siblings!

If we look deeper, the fact that both proofs provide the same siblings and index, verifying both proofs prove that we have only modified the leaf with index I:

Therefore, our delta merkle proof needs to provide:

1. The leaf’s index (the same for both before and after proofs)
2. The leaf’s siblings (the same for both before and after proofs)
3. The leaf’s old value (before the change)
4. The tree’s old root (the root of the tree before the change)
5. The leaf’s new value (after we change the value of the leaf)
6. The tree’s new root (after we change the value of the leaf)

We can implement a getDeltaMerkleProof function to do this for us:

class MerkleTree {
  // ...
  getDeltaMerkleProof(level, index, newValue){
    // compute the root of the leaf at index I
    const oldLeafProof = this.getMerkleProof(level, index);
    // compute the merkle root from the proof, replacing the leaf's value with the new value
    const newRoot = computeMerkleRootFromProof(oldLeafProof.siblings, index, newValue);

    // return the data from the old proof and the new proof
    return {
      index: index,
      siblings: oldLeafProof.siblings,

      oldRoot: oldLeafProof.root,
      oldValue: oldLeafProof.value,
      
      newRoot: newRoot,
      newValue: newValue,
    }
  }
}

To verify the delta merkle proof, we can split the data of the delta merkle proofs into a newProof and oldProof which share the same siblings/index, and verify the proofs using our existing verifyMerkleProof function:

function verifyDeltaMerkleProof(deltaMerkleProof){
  // 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);
}

Let’s combine this together and see if it works:

const shajs = require("sha.js"); // npm install --save sha.js

function hash(leftNode, rightNode) {
  return shajs("sha256")
    .update(leftNode + rightNode, "hex")
    .digest("hex");
}
function getSiblingNode(level, index){
  // if node is the root, it has no sibling
  if(level === 0){
    throw new Error("the root does not have a sibling")
  }else if(index % 2 === 0){
    // if node is even, its sibling is at index+1
    return {level: level, index: index+1};
  }else{
    // if node is odd, its sibling is at index-1
    return {level: level, index: index-1};
  }
}
function getMerklePathOfNode(level, index){
  const merklePath = [];
  for(let currentLevel=level;currentLevel>0;currentLevel--){
    merklePath.push({
      level: currentLevel,
      index: index,
    });
    index = Math.floor(index/2);
  }
  return merklePath;
}
class MerkleTree {
  constructor(height, leaves){
    this.height = height;
    this.leaves = leaves;
  }
  N(level, index){
    if(level === this.height){
      // if level == height, the node is a leaf, 
      // so just return the value from our dataset
      return this.leaves[index];
    }else{
      // if the node is not a leaf, use our definition:
      // N(level, index) = Hash(N(level+1, index*2), N(level+1, index*2+1))
      return hash(
        this.N(level+1, 2*index),
        this.N(level+1, 2*index+1),
      );
    }
  }
  getRoot(){
    // the node N(0,0) is always the root node
    return this.N(0,0);
  }
  getMerkleProof(level, index){

    // get the value of the leaf node
    const leafValue = this.N(level, index);

    // get the levels and indexes of the nodes on the leaf's merkle path
    const merklePath = getMerklePathOfNode(level, index);

    // get the levels and indexes of the siblings of the nodes on the merkle path
    const merklePathSiblings = merklePath.map((node) => {
      return getSiblingNode(node.level, node.index);
    });

    // get the values of the sibling nodes
    const siblingValues = merklePathSiblings.map((node) => {
      return this.N(node.level, node.index);
    });

    return {
      root: this.getRoot(), // the root we claim to be our tree's root
      siblings: siblingValues, // the siblings of our leaf's merkle path
      index: index, // the index of our leaf
      value: leafValue, // the value of our leaf
    };
  }
  getDeltaMerkleProof(level, index, newValue){
    // compute the root of the leaf at index I
    const oldLeafProof = this.getMerkleProof(level, index);
    // compute the merkle root from the proof, replacing the leaf's value with the new value
    const newRoot = computeMerkleRootFromProof(oldLeafProof.siblings, index, newValue);

    // return the data from the old proof and the new proof
    return {
      index: index,
      siblings: oldLeafProof.siblings,

      oldRoot: oldLeafProof.root,
      oldValue: oldLeafProof.value,
      
      newRoot: newRoot,
      newValue: newValue,
    }
  }
}
function computeMerkleRootFromProof(siblings, index, value){
  // 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){
  return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof){
  // 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 height = 3;
  const leaves = [
    "0000000000000000000000000000000000000000000000000000000000000001", // 1
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000003", // 3
    "0000000000000000000000000000000000000000000000000000000000000007", // 7
    "0000000000000000000000000000000000000000000000000000000000000004", // 4
    "0000000000000000000000000000000000000000000000000000000000000009", // 9
    "0000000000000000000000000000000000000000000000000000000000000000", // 0
    "0000000000000000000000000000000000000000000000000000000000000006", // 6
  ];
  const tree = new MerkleTree(height, leaves);

  const deltaMerkleProofOfN3_5 = tree.getDeltaMerkleProof(3,5, "0000000000000000000000000000000000000000000000000000000000000008");
  console.log("[EX_6] delta merkle proof of changing N(3,5) from 9 to 8:\n" + JSON.stringify(deltaMerkleProofOfN3_5, null, 2));
  console.log("[EX_6] verify delta merkle proof: "+verifyDeltaMerkleProof(deltaMerkleProofOfN3_5));
}

example6();

Running this code prints:

[EX_6] delta merkle proof of changing N(3,5) from 9 to 8:
{
  "index": 5,
  "siblings": [
    "0000000000000000000000000000000000000000000000000000000000000004",
    "deb2a27a00dbc46e3a59096a8d07d2b97f950158886411ff6a9c9ab9623dada6",
    "2f4d3e941b602c50347af3f5c809a28737c27c7ce460e77b10739875ef957aa7"
  ],
  "oldRoot": "e74ae221cf067dc8e88195f5b30bfda60dc224a8cd5554bc6345c87ad8c6f925",
  "oldValue": "0000000000000000000000000000000000000000000000000000000000000009",
  "newRoot": "99ba6856d11cd514be35ed291e86ae7957ec43d6b83270f32aaa50a8a25dc5cc",
  "newValue": "0000000000000000000000000000000000000000000000000000000000000008"
}
[EX_6] verify delta merkle proof: true

Success! We have now invented the core concepts behind merkle trees, merkle proofs and delta merkle proofs.

More importantly, with this intuition we can use our full understanding of how merkle proofs work to implement variants of these proofs to create useful and efficient data stores for our layer 2 protocol.

In the next tutorial, we will build an efficient merkle tree database for large sparse merkle trees, write an append only merkle tree that only uses O(log(N)) storage, and investigate some merkle proof variants that allow us to merge trees and prove historical state.

about the author — follow @cmpeq on twitter or check out my about page.

Vist QED at https://qedprotocol.com