[discussion reduce mode]
Maybe I’m looking at things from a different angle. I’m mainly concerned about gas costs for users, and secondarily, for the coordinator. This is after all what the batch deposit technique is meant to address.
In MACI, we need to prove things about each leaf in the balance tree in ZK. i.e in the balance tree (aka the message tree in MACI nomenclature), each leaf may or may not modify the state tree depending on its decrypted contents (e.g. a message leaf is an encrypted command which may change a user’s public key). Since we want to ensure that the coordinator processes each message in the correct order, our Groth16 snark has to prove each leaf’s membership and position in the message tree.
This already costs several hundred thousand gas. If we perform a Kate multi-proof that’ll add at least another 193k gas (the bulk of which is for the pairing check precompile).
If/when we move to PLONK (contingent on dev tooling), could we avoid this extra cost?
[discussion expand mode]
In the short term, without PLONK, perhaps there are benefits to using a Kate commitment in BabyJub so we can verify a Kate commitment or a Kate verkle tree inside our Groth16 snark.
- Each user who deposits into a deposit queue only pays to store 32 bytes.
- Once the deposit queue is full, the coordinator accumulates then into a Kate commitment, which should be cheap. To Kate-commit to 16 values, for instance, costs 223454 gas, which is a great improvement over a Poseidon binary Merkle tree, which needs 797835 gas to commit 16 values. This way, both users and coordinators save gas.
- To construct the final balance tree, the coordinator would also use Kate commitments, resulting in a Verkle tree. Since we can commit to more values at a lower gas cost, we can have a much larger tree capacity.
- When we process the balance tree (aka the message tree), we check the membership and position of each message inside the snark, and proceed as usual.