Proposal to move the MerkleTree from the smart contract to offchain computation for ~66% gas cost reduction

[arnaucube]

Instead of doing the MerkleTree computation onchain, it can be done offchain, and proved the correctness inside a zkSNARK proof.

This means that with the current approach (MerkleTree onchain) it needs 1M gas for the deposit, while with this new approach (MerkleTree offchain + zkproof of correctness) in the tests that I did the gast cost is arround 0.3M gas. This is thanks to the fact that the MerkleTree is moved to offchain computation and then proved its correctness inside the snark proof which is much cheaper to verify in the smart contract. (The withdraw continues very similar as it is now, as it is already with a zkproof verified in the contract).

I've made a proof of concept that works here: https://github.com/arnaucube/miksi-core ,
that can be tried here: https://arnaucube.github.io/miksi-app/ (still needs some improvements, but it works and can be currently used in Göerli testnet).

A bit of more detailed explaination:

Deposit

All computation & constructions are done offchain and then proved inside a zkSNARK to the Smart Contract

• user generates a random secret & nullifier
• computes the commitment, which is the hash: commitment = H(secret, nullifier, extradata)
• get all the commitments from the SmartContract
• build the MerkleTree with the getted commitments
• add the new computed commitment into the MerkleTree
• generate zkSNARK proof, where is proving:
  - prover knows the secret & nullifier for the commitment which is in a leaf in the merkletree
  - the transition from RootOld (the current one in the Smart Contract) to RootNew has been done following the rules (only one leaf addition, no leaf deletion, correct leaf format, etc)
• user sends ETH to the smart contract deposit call, together with the zkProof data
• smart contract verifies the zkProof of the deposit, and if everything is ok stores the commitment & the new root

Withdraw

All computation & constructions are done offchain and then proved inside a zkSNARK to the Smart Contract

• user gets all the commitments from the SmartContract
• build the MerkleTree with the getted commitments
• generate the siblings (merkle proof) for the commitment of which the user knows the secret & nullifier
• generate zkSNARK proof, where is proving:
  - user knows a secret for a public nullifier
  - which commitment is in the MerkleTree
  - which MerkleTree root is the one that knows the SmartContract
• if the zkProof verification passes, and the nullifier was not already used, the Smart Contract sends the ETH to the specified address

The proposal would be then, to move the MerkleTree computation offchain, and instead of building the MerkleTree in Solidity, could be done in the client side, and then proved its corretness inside the zk-proof.

[poma]

This approach has a few issues:

• It enables race conditions and griefing: if a user submits a proof for a certain merkle tree but then it becomes outdated due to some other (possibly malicious) transaction being mined first, the user's transaction will fail.
• Requiring a snark proof on deposit complicates some use cases where for example some smart contract wants to fund other user's commitment

This can be solved by introducing fallback to onchain merkle tree update in case of incorrect or empty proof, but we don't want to introduce this additional complexity. Besides, tornado v2 contracts are already immutable.

In tornado pool (v3) we already use this approach since it stores additional data in commitment and requires a snark proof on deposit anyway.

[poma]

You can check out our implementation of this technique here: https://github.com/tornadocash/tornado-pool/blob/master/circuits/treeUpdater.circom

[arnaucube]

Cool! Yes:

• About the race condition, agree, last week talking with @jbaylina about the race condition in this kind of approach he was commenting to explore the idea of the user submitting the deposit without the proof related to their deposit, but with the proof proving the deposit of the previous user, and then in case of incorrect/empty proof to use a fallback to onchain merkletree as you mention
• About these kind of cases of a sc paying the gas, I guess that the smart contract can still fund the commitment (+ the proof). As the commitment is already something that needs the user secret generation, is just a matter of adding the proof.

I guess that is a tradeoff with a bit of more complexity, and with the extra steps to cover these cases, butgetting less gas cost in the deposit transactions.

Anyway, nice to know that those things are been taking in account, I'll take a look to Tornado Cash docs to know better how Tornado specifically works ^^

[poma]

If we submit the proof for the previous user, then he will be unable to withdraw until someone deposits after him. I don't see how is it different from requiring users to submit a proof for themselves.

Let me clarify a smart contract case. Imagine for example some lottery where users submit their commitments, and then at some point the smart contract randomly chooses a winning commitment and funds it by calling deposit function (this was the first design of Thresher contract to deal with leftover change without breaking privacy). In this case the smart contract would be unable to fund the chosen commitment without someone generating and submitting a proof for merkle tree update.