Tokamak zk-EVM 2023 Q2 Report
Theoretical and Practical improvements of our SNARK
Hi, I’m Jake, the leader of the Tokamak zk-EVM project. We share the 2nd quarter progress.
- About the Tokamak zk-EVM project
- This project is financially supported by Ecosystem Support Program of Ethereum Foundation through Academic Grants Round 2023.
The theme of 2nd quarter is Theoretical and Practical improvements of our SNARK.
Major outcomes
- In theory, we came up with a new idea for our SNARK’s Prove and Verify algorithms. This new idea gives our SNARK a key property, selective verification. We reviewed the cryptographic security of this idea and found that it can significantly improve our SNARK in terms of efficiency while preserving security.
- In practice, the performance of our SNARK’s demo implementation reached a practical level. Measured on a low-cost PC, it now takes 52 seconds to generate proof for a simple Ether transfer circuit (with depth ²¹⁵) that took 6.5 hours when the first version was released in September 2022.
Some of the details
A new idea for our SNARK
Previously, the universal reference string (urs) of our SNARK was defined to be:
where n is the maximum depth of subcircuits, and s=s_D s_{max} is a bound to the number of arithmetic and logical instructions that a contract can have at most (please see about circuits and subcircuits in our introduction). Roughly, the depth of a Groth16 circuit ~= ns.
Our new idea is to exclude y from the urs. Instead, we include [(x^i)(z^j)]_G for i=0,…,n-1 and j=0,…,2s-2 and [z^j]_H for j=0,…,s .
By doing these, we obtain the following advantages:
- The length of urs is reduced from O(ns²) to O(ns).
- Selective verification is allowed.
What is selective verification?
Tokamak zk-EVM requires a two-step derivation of a transaction circuit. The first derivation is carried out whenever a contract is deployed and generates a vector called an expanded execution trace (EET). An EET explains which arithmetic and logical instructions should be used and how to connect the inputs and outputs of those to form a circuit of an EVM application, i.e., a contract. A contract circuit can have many branches because the EVM allows to use conditional jump instructions, and a single execution trace (ET) can be selected only when a set of inputs to a contract is given, i.e., a transaction. The second derivation is carried out whenever a new transaction is issued, and it projects the EET down to a lower dimension and generates an ET, where the unselected branches are truncated. Finally, zk-EVM verification checks only the instructions indicated by ET from a contract circuit derived by EET.
Originally, Groth16 consists entirely of a non-interactive linear proof (NILP) with fixed verification equation, and so did our previous approach. However, to meet the requirement of Tokamak zk-EVM, our SNARK verifiers should be able to modify a verification equation instantly according to an ET. We solve this problem by adding interactive Oracle proof (IOP). Part of a verification equation is fixed by NILP, and the rest is made instantly through the agreement between a prover and a verifier, notarized by a random Oracle. We will soon open a technical document that specifies our SNARK updated with this idea.
Performance improvement of our SNARK demo version
We applied some efficient computation algorithms and code optimization to our SNARK demo version. The history of implementation updates is given here. In detail, we updated the following:
- For the division of QAP polynomials, an efficient algorithm was applied.
- A batched computation algorithm is applied for the multi-scalar exponentiation on an elliptic curve group (so-called MSM, library provided by Iden3).
- Code related to fetching and manipulating polynomials was optimized.
As a result, the time for proof generation of a test circuit of depth 2¹⁵ is reduced from 18 mins (the Q1 result) to 52 seconds (measured on a low-cost PC).
Contact us
We are actively seeking creative researchers and developers, please contact us at hr@tokamak.network. Also, we welcome contacting jake@tokamak.network for technical discussions.
