Ideas to reduce gas costs

[JustinDrake]

Below are some scalability ideas:

1. 3-pairing SNARKs: The Groth 16 paper reduces the number of pairings from 8 to 3, so that should reduce the gas cost of withdrawals by ~2x.
2. Offchain roots: A one-liner optimisation is to release the storage of used roots. But there's a better optimisation which is to use some sort of accumulator for the roots so that the full set of roots is not stored onchain. (This is basically the "stateless client" approach.) My suggestion is to use a double-batched Merkle accumulator with a relatively small bottom buffer (e.g. with 1024 entries), or a Merkle Mountain Range. The proof of membership (a Merkle path) could be separate from the SNARK or (even better) part of the SNARK.
3. Offchain verification: I suggest having two types of withdrawal transactions, "express" and "economy":
   • Express transactions are cleared immediately, as they are now. The downside is that the gas cost to verify the SNARK onchain must be paid.
   • Economy transactions are much cheaper because the SNARK is not verified onchain (in the default case). The downside is that they are slower to clear. They must come with some collateral (say, 1 ETH) and are put in escrow for some challenge period (say, 1 day). During the challenge period anyone can force the verification of the SNARK onchain. If verification of the SNARK fails half the collateral is burnt and the other half goes to the challenger. If verification of the SNARK passes, or the challenge period expires, then the transaction clears and the collateral is returned.
4. Offchain nullifiers: There may be an opportunity to not store the nullifiers onchain. For economy transactions it suffices to augment the challenge game so that the challenger can submit a proof that a nullifier was previously used. A more general solution that works for express transactions is to put the nullifiers in an accumulator which supports proofs of non-membership. Similar to the proofs of membership for roots, these proofs of non-membership could either be submitted separately from the SNARKs, or merged into the SNARK.

[barryWhiteHat]

tldr: until gas costs come down most of these optimizations except 1. will have limited impact. My goal is to batch transactions so that many "internal" transfers can be confirmed with a single zksnark. I may sacrifice anonymity for the time being to achieve a purely scaling solution. That is my current research direction.

3-pairing SNARKs: The Groth 16 paper reduces the number of pairings from 8 to 3, so that should reduce the gas cost of withdrawals by ~2x.

Definitely a good idea. I will made an issues for it. #20

Offchain roots:

The deposit is quite cheap costing 27% of the total gas. The real expensive part is the withdraw. But still it is good to optimize it.

The reason i don't release the used root is that this can cause a race condition as follows

1. User A deposits Coins
2. User A create witdhraw for Coin and broadcasts
3. User B depsoits coins and updates to new root
4. User A's transaction gets minder but throws because the root they used to create their merkle proof is different then the current root after userB's deposit.

The double-batched Merkle accumulator is really cool construction. But since the deposit set comes with a eth transfer we would have to add a payment channel as well as this batching. So that whoever broadcasts the final commitment also sends the tokens and this starts to get quite complicated.

Offchain verification:

I would rather replace these true bit games with zksnarks wherever possible. But the current problem is that recursive snarks do not come with the same kind of security guarantees. But this is something people are working on.

Offchain nullifiers:

I think the proof of non member ship is a nice idea here. But until the gas costs come down and there is little point optimizing the storage which will lead to quite a small saving. I heard talk of reducing the gas costs of elliptic curve operations by a factor of 5 to 10 due to node optimizations. This will drastically reduce gas costs.

[JustinDrake]

most of these optimizations except 1. will have limited impact

Optimisation 3 is by far the biggest. It allows to bypass the gas cost of SNARK verification.

I would rather replace these true bit games with zksnarks wherever possible.

It's not a full TrueBit game in the sense that the challenger does not interact with the claimer: either there's a forced onchain verification or there isn't, and the blockchain adjudicates immediately. The suggested game is much simpler to implement than a full TrueBit game.

the current problem is that recursive snarks do not come with the same kind of security guarantees

The goal here is to not pay the gas costs of SNARK verification, for either non-recursive or recursive SNARKs.

[HarryR]

It's not a full TrueBit game in the sense that the challenger does not interact with the claimer: either there's a forced onchain verification or there isn't, and the blockchain adjudicates immediately. The suggested game is much simpler to implement than a full TrueBit game.

The game logic for this gets annoying when you consider Gas price spikes and staking so that providing a negative proof is worth it versus the reward of spamming the network for N blocks with invalid proofs at a very high gas cost so that no other transactions to the contract get accepted.

e.g. if there's 1000 ETH deposited in the token, and there is a 10 block delay, you could spend 10 ETH in gas per block spamming the contract (and network) with high-gas transactions with invalid proofs that allow you to withdraw all the contracts funds, creating a denial of service so the negative proofs can't be proven to keep the game fair.

Sounds like a world of pain to get right, and very costly if you get it wrong.