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.

1

[Original merkle tree]

2

- Root: 0xabcd...

3

- Index: m

4

[Items to add]

5

- [leaf_1, leaf_2, ..., leaf_n]

6

[Updated merkle tree]

7

- Root: 0xfdec...

8

- Index: m + n

Copied!

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.1mergedLeaves = 02mergedLeaves = hash(mergedLeaves, items[0])3mergedLeaves = hash(mergedLeaves, items[1])4...5mergedLeaves = hash(mergedLeaves, items[n])Copied! - 3.In the end, the result stored on the EVM will be1- start root2- start index3- result root4- result index5- mergedLeavesCopied!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.Start1[stored proof on the EVM]2startRoot = 0x0001234...;3startIndex = 38;4resultRoot = 0x0001234...;5resultIndex = 38;6mergedLeaves = 0x0Copied!
- 2.Add the first item1[calculating...]2startRoot = 0x0001234...;3startIndex = 38;4resultRoot = 0xAFCA1234...;5resultIndex = 39;6mergedLeaves = keccak256(0x0, 0x01) = 0xA0...Copied!
- 3.Add the second item1[calculating...]2startRoot = 0x0001234...;3startIndex = 38;4resultRoot = 0xBA891234...;5resultIndex = 40;6mergedLeaves = keccak256(0xA0..., 0x02); = 0xB1...Copied!
- 4.Add the third item & record to the storage1[stored proof on the EVM]2startRoot = 0x0001234...;3startIndex = 38;4resultRoot = 0xC9B31234...;5resultIndex = 41;6mergedLeaves = keccak256(0xB1..., 0x03); = 0xC3...Copied!
- 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.1[stored proof on the EVM]2startRoot = 0x0001234...;3startIndex = 38;4resultRoot = 0xF1F3A4B...;5resultIndex = 47;6mergedLeaves = 0xDEFEDFED...;Copied!
- 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`

.1startRoot: 0x0001234...,2startIndex: 38,3itemsToAdd: [0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09],4resultRoot: 0xF1F3A4B,5resultIndex: 47Copied!Here is how it computes the`mergedLeaves`

of`itemsToAdd`

1merged = bytes32(0);2for(uint i = 0; i < itemsToAdd.length; i++) {3merged = keccak256(merged, itemsToAdd[i]);4}Copied!Finally, if the result`merged`

value equals to the`mergedLeaves`

value`0xDEFEDFED...`

of the stored proof, it returns`true`

or will be reverted.

Last modified 10mo ago

Copy link