Project “Tokamak zk-EVM”
Tokamak zk-EVM := Tokamak zk-SNARK + Fault proof protocol
Updated on Apr. 15th, 2024.
TL;DR
- Since 2022, Onther and Tokamak Network have been developing a new type of zk-EVM for layer-2 rollup.
- As a core technology, we also proposed our self-developed zk-SNARK (a demo implementation is under development).
- Our zk-EVM explores a new area of compromising trade-offs (defined by Vitalik) between existing zk-rollups and optimistic rollups.
- As “zk-EVM using SNARK assisted by interactive fraud proofs”, this project has been accepted by the Ethereum Foundation for Academic Grants Round 2023 of the Ecosystem Support Program (ESP).
Preliminaries
What is zk-SNARK?
Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) is a class of ZKP protocols. Depending on applications, a (zk-)SNARK can be used in a conversation between at least two parties, specifically called Prover and Verifier, where the prover wants to convince the verifier of a statement “Given u, I have honestly executed F(u) and obtained the output y.” (with or) without revealing the whole procedure of execution. The worker generates proof for the correctness of the statement by using a proving algorithm specified in a protocol and submits it to the verifier. The proof can be verified by a verification algorithm specified in a protocol, hopefully, with much lower time complexity than directly executing F by virtue of the succinctness of SNARK. A SNARK thus allows the verifier to outsource a computationally complex task of executing F to the prover.
A language for SNARKs, Verifiable Circuit.
Before the prover and verifier start a conversation with a SNARK, they run an offline preprocess to compile a (non-deterministic polynomial time) program with inputs into a (deterministic polynomial time) verifiable circuit. A verifiable circuit, a circuit for short, is a set of arithmetic constraints, called gates, on variables, called wires. Though varying by SNARKs, in the most widely-used form of circuits called rank 1 constraint system (R1CS), each gate consists of one multiplication with at most three wires attached. Arithmetic constraints mean the relationships of input and output wires for all gates. A compiler, for example, Circom or Zokrates, transforms a program into a circuit. In this process, the inputs and outputs to the program are assigned to public wires as an instance, and intermediate outputs are assigned to private wires as a witness. Given a circuit, an instance, and a witness, the verifier can check whether the outsourced program has been honestly executed or not.
A circuit must return an output in a deterministic polynomial time (to ensure the succinctness of SNARKs). Thus, if a program to be compiled into a circuit is a nonuniform algorithm, i.e., if the program input determines a computation path, the circuit constraints also vary by the program input (We will later see that this property becomes an obstacle to the development of zk-EVMs).
The goal of SNARKs. The goal of a SNARK is to compress a circuit’s constraints (and give privacy to a witness, if it is zk-SNARK). In detail, we need to find a one-way map that compresses the dimension of a witness, while keeping it to be verifiable with the circuit. If possible, we hope to achieve the compression with a result of constant size, regardless of the original dimension.
SNARK algorithms: Setup, Prover, Verifier. Researchers have found ways to achieve this goal. In many SNARKs, there is an additional party besides the prover and verifier, called a trusted third party (TTP). Before the prover and verifier start a conversation, a TTP runs a setup algorithm with her private trapdoor to generate a pair of public proving and verifying keys, referred to as a reference string (RS). Using an RS, the prover combines a circuit and a witness to produce proof, of which the correctness can be validated by the verifier with an instance. Every SNARK must satisfy the following relationship: Verify(Circuit, Instance, Witness) <=> Verify(RS, Instance, Proof)
Classification of SNARKs: Transparent, universal, and circuit-specific
SNARKs can be classified with the reliance on TTP. Typically, we can divide SNARKs into two categories: transparent SNARKs and trust-based SNARKs, and the latter can be further divided into two subcategories: universal SNARKs and circuit-specific SNARKs. Transparent SNARKs do not require a TTP, whereas trust-based SNARKs do.
A trusted setup of both universal and circuit-specific SNARKs can be replaced with secure multi-party computation (MPC) ceremonies (so-called “powers-of-tau”). However, it takes a long time more than a month to organize a ceremony (e.g., zcash’s ceremony).
Challenges unsolved in SNARKs.
The universal and circuit-specific SNARKs are divided by the scope of information that the Setup deals with. The setup in circuit-specific SNARKs processes a circuit, more specifically it commits to a circuit as a notary so that the prover and verifier can be assured that they are arguing the same circuit. On the contrary, the setup in universal SNARKs does not involve such a commitment but leaves the prover and verifier to make a commitment to a circuit by themselves.
As a result, typically, the circuit-specific SNARKs are more succinct than universal SNARKs. For example, the circuit-specific SNARK Groth16 is known as the most succinct with proof of length 3 along with the fastest proving and verification time. However, the circuit-specific SNARKs require the intervention of a TTP whenever a new circuit (i.e., a new program or new input) is given.
Universal SNARKs may reduce the reliance on TTP. However, achieving succinctness requires the assumption of the verifier preprocess that the verifier is accessible to honestly precomputed commitment to a circuit. This assumption hinders the practical use of universal SNARKs in some applications where the verifier is untrusted.
What is zk-EVM?
Informally, zk-EVM can be regarded as a replacement for EVM. Zk-EVM is a zk-SNARK specifically optimized for EVM applications. Traditionally, Ethereum nodes (can be regarded as the verifiers) validate users’ (can be regarded as the provers) transactions (can be regarded as a program F with specific inputs u) by re-executing them on EVM. With a zk-EVM, inheriting the upsides of zk-SNARKs, the verifiers can outsource the validation of transactions to the provers, which is expected to be done in a far lower time complexity than the traditional re-execution of EVM. In addition, we hope to replace the original transactions with proofs.
Why do we need zk-EVM? The adoption of zk-EVM has the potential to bring two positive effects to Ethereum: As a SNARK verification algorithm (hopefully) can have a constant time complexity, 1) the gas amount for validating a transaction (has been replaced by proofs) can be fixed to a nearly-constant; and as each proof can have a constant length and fully replace the original transaction, 2) the size of the blockchain can be reduced. As a result, these two effects can work synergistically to allow more transactions validated in a single block, which leads to the improvement of Ethereum throughput, the maximum number of transactions processed per second.
Zk-rollups.
The upsides of zk-EVM can even be amplified with a zk-rollup on layer 2. Zk-rollup is another zk-SNARK optimized for zk-EVM. In detail, the program F considered in a zk-rollup is a zk-EVM’s verifier. The prover collects a batch of zk-EVM proofs resulting from different types of transactions and different inputs and makes a single SNARK proof by using a special technique called recursive proof composition or proof aggregation. As a result, Ethereum throughput can increase by as many transactions as can be included in a rollup (which can be traded off with rollup proving time and rollup verifying cost).
Further discussion on zk-rollups is beyond the scope of this article. For more details, please see an introduction to rollups written by Vitalik Buterin.
Overview of Tokamak zk-EVM
Expected contributions
First of all, we aim to contribute to making Ethereum viable for mass adoption. Our approach to this end is to explore a new area of compromising trade-offs between existing zk-rollups (ZKR) and optimistic rollups (OR) (For details on the trade-offs between ZKR and OR, see Vitalik’s post).
The expected results are as follows (in terms of the Vitalik’s performance indicators):
- Higher compatibility with EVM (than ZKR, but possibly worse than OR)
- Lower off-chain computation costs ⇒ higher transaction throughput in L2 (than ZKR, but possibly worse than OR)
- Faster, more dynamic, and predictable withdrawal to L1 (than OR, but possibly worse than ZKR)
Technical milestone
Technically Tokamak zk-EVM will be a combination of ZKR and OR.
A. Tokamak zk-SNARK: Development of a new zk-SNARK
- A1. New theory establishment (with an academic paper)
- A2. Practical implementation
B. Tokamak Zk-EVM: Applying our zk-SNARK to a new zk-EVM
- B1. EVM circuit implementation
- B2. Adaptation of an existing multi-party verification system (e.g., Fault proof system)
- B3. Documentation (specification)
- B4. Demonstration and fine-tuning
C. Rollup network: Organizing a testing rollup network based on our zk-EVM
- C1. Adaptation of an existing rollup network organization (network entities, penalty and reward policies, …)
- C2. Demonstration and fine-tuning
Details of Tokamak zk-EVM
Terminology
- A contract: a program of EVM
- A transaction: a specific input along with an EVM program
- Layer 2: a rollup layer where users’ transactions are processed quickly and the results are rolled up and reported to Ethereum at regular time intervals.
Motivation
As EVM is (quasi) Turing-complete, the programs are nonuniform. Thus, a circuit can be determined only when a transaction (i.e., the input to a program) is made.
A challenge comes from at this point. With circuit-specific SNARKs, we cannot rerun the Setup algorithm for each transaction due to the aforementioned problems. Universal SNARKs also do not provide the answer: The verifiers in a blockchain network are untrusted in general, so the precomputed input to a verifier (based on the verifier preprocess assumption) must be reproduced by the other verifiers, which loses the succinctness of SNARKs.
Concurrent works
An existing solution to this challenge is to compile into a circuit, not an EVM program but the entire machine (EVM). A universal circuit verifies all state transitions that occur in EVM during the execution of a program. This approach has been adopted by most of the other ongoing zk-EVM projects such as PSE, Consensys (Linea), Polygon Hermez, Scroll, and Sin7y (a short review of them except for Sin7y is given here). We refer to such a circuit as a universal circuit.
In their approach, the benefit of independence from programs (and the input) sacrifices the complexity of universal circuits: 1) the circuit width necessarily becomes proportional to the size of EVM (= number of memory and register slots) to trace the entire machine states; 2) the circuit has to be as deep as the maximum number of steps; and 3) instances must have enough length to represent the initial and final states of an EVM execution.
Problem observation. The high complexity of universal circuits increases the proving time of SNARKs to hours, hindering fast transaction processes in Layer 2.
Our approach
We are building a zk-EVM with a completely new approach from the other projects — We do not build the heavy universal circuit that mimics the entire EVM but use a lightweight one that operates on our own universal SNARK, Tokamak zk-SNARK, with the help of fault-proof systems of optimistic rollups.
Universal circuit. Our universal circuit is a set of subcircuits for all arithmetic/logical instructions of EVM (for details, see Appendix H of Ethereum yellow paper), which can be derived as a transaction circuit. A transaction circuit is defined as a pair of placement of the subcircuit copies and a wire map. The subcircuits are written in quadratic arithmetic program (QAP) form (aka R1CS). A wire map contains wiring between subcircuits in the form of a permutation map.
Tokamak zk-SNARK. We have proposed a new SNARK based on the hybrid of Groth16, which is the most succinct but lacks universality, and PlonK, which is universal but highly depends on the verifier preprocess. The proposed SNARK retains the same succinctness as Plonk while reducing reliance on the verifier preprocess (= Wire map in the figure below).
How much is reliance on the verifier preprocess reduced? To answer this question, we use as an indicator, denoted by dim(input), the dimensionality of data that the verifier must preprocess (= Wire map in the above figure). For example, in PlonK, dim(input)=O(size(circuit)). Whereas, in Tokamak zk-SNARK, dim(input)=O(# of subcircuit copies placed in a circuit).
Fault-proof system. Our Layer 2 will combine two types of proving systems: Tokamak zk-SNARK and a fault-proof system. In Layer 2, SNARK proofs can replace transactions to ensure fast transaction throughput. The intermediate verifier preprocess outputs (= Wire maps) are temporarily assumed to be trustworthy until they are formed into a rollup by rollup validators. Rollup validators then run a fault-proof system to validate the verifier preprocess outputs. Once the verifier preprocess outputs have been sufficiently reviewed, they will be reported to the Ethereum network. (Details may change in the future, as we are also considering secure multi-party computation as an alternative to the fault-proof system).
Hopefully, the benefit of using our SNARK at this point (what we expect) is that it may predictably and dynamically shorten the running time of the fault-proof system (aka challenge period) due to reduced dim(input). At a higher level, there may be an advantage to having a faster rollup reporting time to the Ethereum network (= faster withdrawals) than the two weeks fixed by other optimistic rollups.
About the verification of Keccak256. KECCAK256, which is an arithmetic instruction of EVM, exaggerates the size of circuits (example here). To avoid the inefficiency, many other zk-EVM projects have altered the default hash function from Keccak to Poseidon, which is SNARK-friendly and can be compiled into a small-sized circuit. However, this alteration may result in reduced compatibility between zk-EVM and EVM, so we are exploring other options. One of them is to allow the verifier to reproduce all hashes used in a transaction, rather than verifying them through subcircuits. This approach can be realizable with our SNARK by specially configuring wire maps, but we need further reviews on it in terms of efficiency and security.
Concluding summary
We challenge to develop a completely new type of zk-EVM. What we want to do is reduce the size of the SNARK circuit, which in turn is to speed up the SNARK proving time. Our main idea is a mix of a fault-proof system and SNARK proof: Arithmetic computations in transactions are verified with our zk-SNARK, while the rest parts that require tracing state transitions of EVM are validated with a fault-proof system. Our zk-SNARK is specialized for this division of roles.
As we seek a new way, we believe our solutions will bring innovations. For example, in the performance versus compatibility graph of other zk-EVMs analyzed by Vitalik Buterin, our solution will explore a new area. We believe that this project will make a significant contribution to the mass adoption of Ethereum in the long term.
The end of our road is to operate a zk-rollup network on the Tokamak Network. The short-term goals are 1) to publish an academic paper about our SNARK (done), 2) to accelerate our SNARK implementation by applying the latest computing techniques, 3) to publish our zk-EVM’s technical specification, and 4) to implement a demo version of our zk-EVM.
We hope to see you soon with a new update.
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.
