Merged leaves & optimistic rollup

Merged leaves is used for item append sequence validation for the merkle tree rollup of massive items.

Merged leaves concept is used for the sequence verification of the appended items when we want to prove Merkle tree updates through multiple transactions. Let us assume that what exactly we are going to prove is the following result.

[Original merkle tree]
    - Root: 0xabcd...
    - Index: m
[Items to add]
    - [leaf_1, leaf_2, ..., leaf_n]
[Updated merkle tree]
    - Root: 0xfdec...
    - Index: m + n

To prove above, we will run the following steps:

1. To add a massive number of items, we split the transactions and record the intermediate proof result.

2. Every item will be merged sequentially into the mergedLeaves value to ensure the sequence of the item appending.

   mergedLeaves = 0
   mergedLeaves = hash(mergedLeaves, items[0])
   mergedLeaves = hash(mergedLeaves, items[1])
   ...
   mergedLeaves = hash(mergedLeaves, items[n])

3. In the end, the result stored on the EVM will be

    - start root
    - start index
    - result root
    - result index
    - mergedLeaves

   And then we can compare the Merkle tree update result.

Let us see a more detailed example.

• startRoot is 0x0001234...

• startIndex is 38

• itemsToAdd is [0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09]

• we are now trying to prove resultRoot is 0xabcd1234... when after adding all items in the itemsToAdd list.

We're going to add three items at once, so after two times of transactions, we can have a proof for the Merkle tree transition on EVM. Note that we have used random values for the hash calculation for this example.

1. Start

    [stored proof on the EVM]
    startRoot = 0x0001234...;
    startIndex = 38;
    resultRoot = 0x0001234...;
    resultIndex = 38;
    mergedLeaves = 0x0

2. Add the first item

    [calculating...]
    startRoot = 0x0001234...;
    startIndex = 38;
    resultRoot = 0xAFCA1234...;
    resultIndex = 39;
    mergedLeaves = keccak256(0x0, 0x01) = 0xA0...

3. Add the second item

    [calculating...]
    startRoot = 0x0001234...;
    startIndex = 38;
    resultRoot = 0xBA891234...;
    resultIndex = 40;
    mergedLeaves = keccak256(0xA0..., 0x02); = 0xB1...

4. Add the third item & record to the storage

    [stored proof on the EVM]
    startRoot = 0x0001234...;
    startIndex = 38;
    resultRoot = 0xC9B31234...;
    resultIndex = 41;
    mergedLeaves = keccak256(0xB1..., 0x03); = 0xC3...

5. To add the fourth item, we will retrive the result from the storage and keep going to append items.

6. As a result, we now have the result on Ethereum storage, proving the valid Merkle tree transition by the EVM calculation.

    [stored proof on the EVM]
    startRoot = 0x0001234...;
    startIndex = 38;
    resultRoot = 0xF1F3A4B...;
    resultIndex = 47;
    mergedLeaves = 0xDEFEDFED...;

7. Using the stored proof, we can validate the following information is valid or not. To validate the information, it computes the mergedLeaves result of the itemsToAdd and compares it with the stored mergedLeaves.

    startRoot: 0x0001234...,
    startIndex: 38,
    itemsToAdd: [0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09],
    resultRoot: 0xF1F3A4B,
    resultIndex: 47

   Here is how it computes the mergedLeaves of itemsToAdd

    merged = bytes32(0);
    for(uint i = 0; i < itemsToAdd.length; i++) {
        merged = keccak256(merged, itemsToAdd[i]);
    }

   Finally, if the result merged value equals to the mergedLeaves value 0xDEFEDFED... of the stored proof, it returns true or will be reverted.

See the detail implementation