Implement a new incremental on-chain merkle tree library folllowing the idea of Ethereum 2.0 deposit contract.

[invocamanman]

🧐 Motivation

An incremental on-chain merkle tree following the Ethereum 2.0 deposit contract idea can be used as extremely cheap way to store on-chain data that can be proven afterwards with just a merkle proof, since usually it edits an already existing storage slot, it takes Less than 20k to store a new leaf! which makes it cheaper than store just new information directly on storage.

Having an efficient on-chain merkle tree library can be used can be useful to store the deposits in case of rollups, maybe another zk applications that need some merkle tree to operate like tornado cash, just store plain messages... I think it just a nice tool to have and it would be nice to be added in OZ libs if you agree ^^

📝 Details

In case of polygon zk-evm we use this merkle tree to store all the bridges ( deposits to another chains) and we prove them afterwards with merkle proofs to claim this deposits.

In case you want to implement this, i already have an audited implementation. Ofc in case you agree to add it i guess that we should adapt it to OZ contracts ( like the efficient hash for example could be nice, or the standard gap of 50).

This implementation is a based on the previously mentioned ehteruem 2.0 deposit contract with some optimizations ( like do not read/store zero hashes from the storage, but calculate them instead which is less gas consuming and using the keccak hash instead of the sha256)

Here's the implementation:

• https://github.com/0xPolygonHermez/zkevm-contracts/blob/feature/etrog/contracts/v2/lib/DepositContractBase.sol

Here's the js library to interact with it:

• https://github.com/0xPolygonHermez/zkevm-commonjs/blob/main/src/mt-bridge.js
  https://github.com/0xPolygonHermez/zkevm-commonjs/blob/main/src/mt-bridge-utils.js

If you would want to add it i'm open to help implementing or porting this contracts to OZ ^^

Interesting links:
Ethereum 2.0 uses a deposit contract which formal verification can be found here:https://github.com/runtimeverification/verified-smart-contracts/blob/master/deposit/deposit-formal-verification.pdf
Ethereum 2.0 solidity code here: https://github.com/ethereum/consensus-specs/blob/dev/solidity_deposit_contract/deposit_contract.sol

[ernestognw]

Hey @invocamanman, this is a great proposal!

I flagged it for 5.1 since I think it's a good research project that we may include in the library. Note that even if we add this to the roadmap, we'll likely add a modified version of any of the contracts you just shared. The case is similar for any js tool.

Also, consider we'll start with 5.x work next year, so it'll take some time.

My opinion is that this is a good primitive for ZK applications, but haven't gone deep into it. Any use case or example that people may drop here is welcome.

[Amxx]

We already have a branch that implements that:
https://github.com/Amxx/openzeppelin-contracts/blob/structure/merkletree/contracts/utils/structs/MerkleTree.sol

It was designed following tornado cash's design, but it was never merged, because the usecase was not clear. Apparently that design can be usefull for some crosschain interractions.

[invocamanman]

Hi, this lib looks very modular and nice!!! Even tho it does not have a way to make "lazy" inserts, which i think it's a very nice feature ( a super cheap insert that do not involve calculate the new root).

Also, to put more resources, i found this merkle tree libs of PSE team which i think are awesome as well, i think it's worth to take a look: https://github.com/privacy-scaling-explorations/zk-kit/tree/main/packages/imt.sol/contracts.

They look pretty modular and implement different trees, lazy and not lazy ones ^^. They are very zk focused, and that's why they are attached to the poseidon hash tho, but we could combine some ideas, and put something like your fnHash aswell.

As a quick note, they have an implementation of a lazy tree that allows updates, which makes the insert a bit more expensive than the ethereum 2.0 deposit tree but has this update capability ^^