AFAIK, you can’t double spend since the root will update to reflect the new state and all txs need to be sequentially processed and be valid.
I wonder if this is similar to what I proposed sometime ago ;-)) I did not have zksnarks in it though )
Wouldn’t transactors need to include a nonce as well?
There’s an edge case here for ERC20s where the value received via transferFrom is less than D. Not huge, but something to consider for implementation.
We might be able to get away with only having the transaction info in calldata, but otherwise logs would add another 8 gas per byte. Maybe worth having it in the marginal cost (instead of the 50k overhead) since it scales with the number of txs.
I think you need to pass the transactions to the sanrk as a public input? If so I think this is quite expensive as during zksnark verification you need to do a pairing addition and pairing multiplication per public input. I found this out after we spoke last. With roll_up where we pass two 32 bytes input per tx we can only have 22 public inputs before we run out of gas.
This is why I suggested putting using hash of the submitted data as the public input, and then computing the hash on chain as that is only 6 gas per 32 bytes for SHA3 (for SHA256 it’s somewhat more but still tiny). FWIW I do agree this whole thing is expensive in terms of prover time, though given that I expect the relayers will be GPU farms so it’s less of an issue than it is in, say, zcash where regular nodes need to be able to make proofs in a few seconds.
This seems to only allow 1 registration per block in practice. If both Bob and Alice try to update the same Merkle root for slot
i, then one will fail.
An alternative is to allow relayers to batch Merkle proofs, though they would not be able to be paid for registrations. Topups and withdrawals can definitely be done through relayers in a way where the relayers get paid though.
This also has the problem that having multiple relayers will lead to collisions and only one will succeed. This introduce a race condition to generate the proof, which can be fine, but now relayers might start to only include the highest fees to make sure they don’t lose the race, so higher cost for everyone.
One option would be to require relayers to reserve the chain for a period of 2 blocks (possibly <30000 gas cost) before they can submit a block.
I believe most of these concerns are addressed by having an operator or close set of operators and a deposit/withdraw queue.
By “queue” do you mean “everyone pre-submits what address they’ll register with, and then that gets put in a queue, and then people have to submit a second transaction to make the Merkle branch, but they’ll do that knowing in advance exactly what Merkle branch they’ll need”? If so I do agree that’s another elegant way to solve the problem.
I wonder if this is similar to what I proposed sometime ago ;-)) I did not have zksnarks in it though )
This scheme is definitely not Plasma. Plasma relies on liveness assumptions and an exit mechanism; there are none of those features here.
Wouldn’t transactors need to include a nonce as well?
Ah yes you’re right. Will update asap.
There’s an edge case here for ERC20s where the value received via
transferFromis less thanD. Not huge, but something to consider for implementation.
If the value receives is less than D, then the entire transaction should fail. Actually, is it even legal according to the standard for a transferFrom request asking for D coins to return less than D coins?
We might be able to get away with only having the transaction info in calldata, but otherwise logs would add another 8 gas per byte. Maybe worth having it in the marginal cost (instead of the 50k overhead) since it scales with the number of txs.
Not need to log the data. Just have a log pointing out that a relay transaction was made, an assert to check that the relayer is an EOA, and then clients can scan through the block data.
2 Likes
Is it actually practical to do ECRecover in a snark? Wouldn’t that require an extremely complex snark circuit?
Checking is a signature is valid for eddsa (with baby jubjub curve) takes about 200k constaints in roll_up, which is maybe 30 seconds to build a proof on a decent laptop. This can most likely be brought down quite a bit still however. Using secp2561curve will be more computationally demanding
400k seems incredibly high. Why is that? If we use schnorr verifying a signature is just two multiplications, an addition and a hash, so on average ~769 additions and a hash, so it seems like the hash would be the largest part of it.
Sorry, I meant 200k, I just edited previous comment. Roll-up currently uses full-rounds of SHA256, so we could cut the number of contraints here almost by half for the hash function. Otherwise, there are a lot of checks done currently that might not be necessary.
Here’s where the contraints are built for the signature validation ;
FWIW I do agree this whole thing is expensive in terms of prover time, though given that I expect the relayers will be GPU farms so it’s less of an issue than it is in, say, zcash where regular nodes need to be able to make proofs in a few seconds.
In the case where you use a GPU farm to perform the proving step do you also need a GPU farm to perform the trusted setup? How do the two operations differ in complexity?
400k seems incredibly high. Why is that? If we use schnorr verifying a signature is just two multiplications, an addition and a hash, so on average ~769 additions and a hash, so it seems like the hash would be the largest part of it.
I use sha256 in a bunch of places because i was unsure what was safe to combine points or remove discard data. But when i optimize it we should be able to come down quite a lot. Its POC at the moment.
1 Like
The correct sum is slightly higher: 68 * 3 (from) + 68 * 3 (to) + 68 * 1 (fee) + 68 * 4 * 2 (amount) + 68 * 2 (nonce), or 1156 gas. A more realistic assumption for the foreseeable future is 1000 tx per SNARK (according to very optimistic calculations we had with the rollup team). So it adds roughly 650 overhead, bringing us to ~1.8k gas per tx.
A batched transfer of tokens with the same parameters (32 bit value, 24 bit address) will cost around 18k gas per transfer. So it’s 10x, not 50x.
10x gas reduction is an order of magintude improvement, of course, but it has a relatively strong cap, and the economic overhead imposed by the SNARK proof computation is also very signficant at the moment. Especially the need to compute hashes optimized for verification in EVM.
Solving the data availability problem through relying on the Ethereum root chain not as 100% data availability guarantor, but rather as the court of the final appeal seems a lot more promising direction, because: 1) it can scale almost indefintely, 2) it simplifies the SNARK circuit, making transfers cheaper and a working MVP a more attainable goal. See our discussion in the roll_up github.
Why? The amount is a single value.
A batched transfer of tokens with the same parameters (32 bit value, 24 bit address) will cost around 18k gas per transfer. So it’s 10x, not 50x.
10x relative to batched transfers. The status quo does not involve batched transfers in most cases; in the 50x I’m including efficiency gains both from SNARK validation and from compression and a batching relay protocol.
Solving the data availability problem through relying on the Ethereum root chain not as 100% data availability guarantor, but rather as the court of the final appeal seems a lot more promising direction, because: 1) it can scale almost indefintely, 2) it simplifies the SNARK circuit, making transfers cheaper and a working MVP a more attainable goal. See our discussion in the roll_up github
I think both directions are valuable; using the ethereum chain as a data availability guarantor makes many other things simpler, and in the long run scalable “sharded” ethereum is basically being designed as a data availability guarantor first and foremost so it’s a quite sustainable long-term direction (see layer 2 execution engines as described here; what I’m describing here is in some sense a candidate for the first layer 2 execution engine). My main short-term concern with Plasma-like constructions is that they depend on specific operators to stay online, and Plasma is inherently non-universal in some respects because of the extra game theoretic requirements.
2 Likes
What I did not understand is how is the correct order of transactions in a batch actually enforced?
What I did not understand is how is the correct order of transactions in a batch actually enforced?
The SNARK proves that each transaction is valid in its position in the batch.
Sorry, my bad.
True, 50x compared to the status quo. Now, batched token transfers are easy to implement, they will soon be widely used. So when deciding which direction to go first with data availability, it’s only fair to compare with them, because any sidechain tx is necesserily a batched tx.
Are there any rough estimates on when EWASM is going to be released? As guys pointed out above, 10x improvement is only possible when using sha3, which requires prohibitatively high number of constraints in the SNARK proof.
Are there any rough estimates on when EWASM is going to be released? As guys pointed out above, 10x improvement is only possible when using sha3, which requires prohibitatively high number of constraints in the SNARK proof.
Maybe a precompile for MIMC is in order? 
The security analysis is definitely not complete, but it is simple enough that a wide parametrization could be specified.
1 Like
Nice! I know ZCash has been waiting for more in depth peer review as well for MiMC, any ETA? What about a precompile for Pedersen in the meantime :D?
1 Like
Maybe a precompile for MIMC is in order?
It’s cheap enough in EVM with a reduced number of rounds that it’s a non-issue at the moment. Although the recommended 160 rounds per input would be more taxing.
However, there may be other algorithms with better security properties which are just as cheap both in-circuit and in-EVM (addmod, mulmod and modexp with a small exponent are all relatively cheap, as long as there aren’t any big loops).
I’m still looking into other candidates, doing more research, and trying to determine specifics of security properties, but more people looking into this would definitely be good - as the ‘cheap in EVM and also cheap in-circuit with a ZKSNARK’ is a tough requirement.
2 Likes