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?
Maybe a precompile for MIMC is in order?
It’s cheap enough in EVM with a reduced number of rounds that it’s a nonissue 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 incircuit and inEVM (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 incircuit with a ZKSNARK’ is a tough requirement.
This slightly confused me, did you want to say the main chain will be ensuring data availability for the L2 chains and systems (e.g. Plasma) in future? Can you please elaborate? Thanks!
Read the section on “layer 2 execution engines” here: https://vitalik.ca/general/2018/08/26/layer_1.html
I would like to assist with this; is there a GitHub repo for this idea that includes the contract and offchain code that maintains the branches of tx? Once there is a repo, we can try to run a little MVP and see how it does – probably totally separate from any eth network at first and then paired with ropsten.
I would like to assist with this; is there a GitHub repo for this idea that includes the contract and offchain code that maintains the branches of tx?
We are working towards a PoC for nonfungible tokens at:
 https://github.com/barryWhiteHat/roll_up
 https://gitter.im/barrywhitehat/roll_up
 https://hackmd.io/s/rJWBpmbFQ
 Plasma snapp  fully verified plasma chain
 https://github.com/snario/zknifty
But, there is a lot of interest in making it work with accounts and balances, although that comes with many more edge cases and complexities compared to nonfungible tokens. At the moment the aim seems to be ‘keep it simple, and deliverable’.
Thanks for the answer, @vbuterin.
I already read it before and now I’ve read it again.
Firstly, I want to say I fully support everything you wrote in the post , I’m almost convinced that is the best (if not the only) way for Ethereum to achieve its full potential. Btw, I see these future L2 execution engines as more or less the same thing as Plasma chains, am I right?
However, my understanding is that, in this future setup, L1/main chain should have two functions/purposes:
 Process disputes/exits
 Guarantee L2 checkpoints/roots/headers availability and ordering (not the availability and ordering of all the data)
I fail to understand how L1 can ensure availability of all the L2 data (like proposed here or in the roll_up’s current implementation)? One can imagine a future where we have thousands of L2 chains/engines with millions of Tx/s cumulatively, can this all be on the main chain?
Btw, I see these future L2 execution engines as more or less the same thing as Plasma chains, am I right?
No, they’re quite different. An L2 execution engine is basically an alternative way of interpreting data that is published to the main chain, with twoway convertibility between assets inside and outside this alternate universeinsidethesameuniverse enforced by a smart contract. This is not quite an L2 execution engine but it’s fundamentally similar.
Plasma relies on the great majority of data being outside the chain, and also relies on liveness assumptions, exit mechanisms, etc, to ensure some notion of safety in the event that whoever publishes the data commitments to chain starts publishing bad commitments.
There’s two very distinct classes of constructions here, with different properties; I think both are valuable.
Oh, so those will coexist. Interesting, thank for the clarification.
I believe there is a typo somewhere here, it’s not clear what are you explaining (L2 engines or Plasma chains), and it’s really funny because in my head this description fits both.
Oh, I see, the main difference is that L2 engine publishes all the data (all transactions) on the chain (just like in this proposal and in roll_up), while Plasma keeps most of the data offchain, right?
Would be really cool to implement SC hashtags like this, no? How far are we from implementing / using this?
Yep! L2 execution engines only put execution offchain and keep data onchain, Plasma, channels and related systems try to put both execution and data offchain.
Got it, thanks!
Let me rephrase what @vbuterin is proposing.

Relayer reserves a slot of several blocks.

Relayer takes the merkle roots from the previous update and updates them using the transaction he accepted, and then posts the corresponding ZKSNARKS to the chain, as well as the updated Merkle roots.

Another relayer reserves a slot and processes more transactions (slot reservation may be an auction).
There are several problems:
An obvious problem that needs to be addressed is chain reorgs.
If I post after some other guy, I rely on the Merkle root that was just posted by him. But someone with enough computational power can reorg the chain making the Merkle root I based my computations on irrelevant.
B. The second problem is time it takes to generate proofs. If I base my zksnarks proofs on some Merkle root and if it takes 20 minute for me to generate the proofs, the Merkle roots may be updated by someone else, making my calculations absolete.
So, if it takes me 20 min to generate the proofs, the time slot needs to be at least 20 min, correct? I can not let someone else (another relayer) update merkle roots why I am generating the proofs.
C. Another question which is not addressed is that if there are multiple relayers for the same merkle root, they have to somehow pass the Merkle tree to each other. If I am a relayer, where do I get the updated Merkle tree from? It looks like I need to get it (or at least the transactions) from the relayer that updated the tree before me. How does this happen?
D. Data availability is another problem. As a user how do I get access to the tree? What if relayers withold it from me?
D. Data availability is another problem. As a user how do I get access to the tree? What if relayers withold it from me?
You can construct the entire tree purely based on information that has been published to chain. I believe this answers ( C ) as well.
But someone with enough computational power can reorg the chain making the Merkle root I based my computations on irrelevant.
Sure, but in practice even a single block reorg happens <10% of the time and a two block reorg happens extremely rarely, so I’m not sure this is an issue in practice.
B. The second problem is time it takes to generate proofs. If I base my zksnarks proofs on some Merkle root and if it takes 20 minute for me to generate the proofs, the Merkle roots may be updated by someone else, making my calculations absolete.
Agree that proof generation time needs to be fast enough and this could be the limiting factor! Though if this becomes a problem then the chain as a whole could still reach ~500 tx/sec with multiple transaction batching gadgets of this type (eg. for different tokens) running in parallel.
Understood, I missed that part, sorry
I am not sure this can be resolved so easily … If a transaction involves a $1B transfer, it will make an incentive for an attacker to do an reorg. I think you need to analyze more carefully and show that a reorg is not a security problem in case of a powerful attacker incentivized by a large payoff
If there is a reorg of the ETH blockchain, it can reorg this system. If the blockchain is finalized up to some point, then this system is also finalized up to that point. It piggybacks on the blockchain directly, so it just inherits its reversion and finality properties.
In addition, if many blocks are reverted, the relayers can just resubmit the proofs they already constructed since a reorg should technically only revert back some of the roots commited. Reorgs should not propose a new history root if we consider that a single relayer per epoch (i.e. time window to aggregate signature + build proof) can commit a new root.
If registering, deposits and withdrawals will update the Merkle root, doesn’t this impact the relayers who are building a proof based on a previous Merkle root? They have to build a new proof based on the new Merkle root. Do they need to start over or is is possible to reuse part of the now obsolete partial proof?
Is it possible to also structure layer2 exec engine’s transaction logging on base chain using zksnark? This also seems like a promising direction.
Have you considered using aggregated signatures like this http://crypto.stanford.edu/~dabo/papers/aggreg.pdf
I have a feeling you could aggregate signatures first, and then do a SNARK on the aggregated signature (in your scheme you are doing SNARK on all ECDSA signatures of all transactions, correct me if I am wrong). The SNARK generation time could be faster for the aggregated signature verification vs verification of each ECDSA.
Another potential improvement is to combine relayers with miners. If miners are relayers, than it seems that you do not need to reserve slots because mining already provides a way to resolve concurrent access.
In other words, only the miner of a particular block can be a relayer for the transactions batched in this block.
Yet another potential improvement is to count zksnark proof computation performed by the miner towards the PoW of the block. In other words the PoW of a block would be the regular PoW + ZKSnark PoW. In this way you essentially get the ZKSnark computation for free, since the miner would correspondingly decrease the regular PoW part.
ZKSnarks can be parallelized as described here
Since the miner anyway gets paid several thousand USD for each block, the miner could spend money to do a highly parallel computation so the proof would be generated much faster in time less than the block time.