On-chain scaling to potentially ~500 tx/sec through mass tx validation


#21

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.


#23

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.


#24

What I did not understand is how is the correct order of transactions in a batch actually enforced?


#25

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.


#26

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.


#27

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? :grinning:

The security analysis is definitely not complete, but it is simple enough that a wide parametrization could be specified.


#28

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?


#29

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.


#30

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! :slight_smile:


#31

Read the section on “layer 2 execution engines” here: https://vitalik.ca/general/2018/08/26/layer_1.html


#32

I would like to assist with this; is there a GitHub repo for this idea that includes the contract and off-chain 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.


#33

I would like to assist with this; is there a GitHub repo for this idea that includes the contract and off-chain code that maintains the branches of tx?

We are working towards a PoC for non-fungible tokens at:

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 non-fungible tokens. At the moment the aim seems to be ‘keep it simple, and deliverable’.


#34

Thanks for the answer, @vbuterin. :slight_smile:

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 :fist::slight_smile:, I’m almost convinced that is the best (if not the only) way for Ethereum to achieve its full potential. :ok_hand: Btw, I see these future L2 execution engines as more or less the same thing as Plasma chains, am I right? :no_mouth:

However, my understanding is that, in this future setup, L1/main chain should have two functions/purposes:

  1. Process disputes/exits
  2. 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?


#35

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 two-way convertibility between assets inside and outside this alternate universe-inside-the-same-universe 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.


#36

Oh, so those will coexist. Interesting, thank for the clarification. :slight_smile:

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. :slight_smile:

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 off-chain, right?


#37

Would be really cool to implement SC hashtags like this, no? How far are we from implementing / using this?


#38

Yep! L2 execution engines only put execution off-chain and keep data on-chain, Plasma, channels and related systems try to put both execution and data off-chain.


#39

Got it, thanks! :pray: :slight_smile:


#40

Let me rephrase what @vbuterin is proposing.

  1. Relayer reserves a slot of several blocks.

  2. 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.

  3. 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 re-org 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?


#41

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 re-org 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.