Eigen Proof System Design Philosophy
Eigen perspective: Eigen Network focuses on delivering privacy-enhancement middleware and network to full-stack developers. Hence, the first future of our ideal proof system should provide user-side privacy-friendly proving computation, which means the proving should be cheap (suitable for CPU) and transparent. Second, the lower of verification cost on the Ethereum blockchain, the better.
Analysis of the existing proof system
Arithmetization: Arithmetization is the process of transforming a computation integrity(CI) statement into a formal Algebraic language. This step has two purposes: first, presenting the CI statement in a clear and concise manner; second, embedding the CI statement in the algebraic domain for the latter polynomial conversion is bedding. At present, the Halo2 arithmetization is the most mature. It has implemented custom gates and lookup tables.
Custom Gate: The custom gate enables a significant reduction in the circuit’s scale (number of gates) and increases the circuit’s design flexibility. In practice, numerous operations, such as point addition and scalar multiplication on elliptic curves, can be constructed as custom gates.
Lookup Table: for commonly used operations, the lookup table of the legitimate (input, output) combinations; and the prover argues the witness values exist in this table. It significantly reduces circuit gates for hash functions sha256 or keccak with the cost of slightly increasing validation complexity. To implement zkEVM, we have to use the lookup table to implement memory read and write functions.
Proving System: a zero-knowledge proof is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true. Commitment is very important in zero-knowledge proof. At present, the most popular commitment schemes include KZG commitment, Merkle commitment (or polynomial low degree detection, FRI), and the vector inner product commitment(IPAs).
Recursive zero-knowledge Proof is divided into two layers: the bottom and top layers. The bottom layer includes a recursion layer. The objective of each layer is as follows: (1) The bottom layer: the faster the better; (2) The top layer: the smaller the proof size, the better, and the less computational complexity, the better.
from Plonk paper：m = number of wires, n = number of multiplication gates, a = number of addition gates, P=pairing, l =num of pub inputs.
(1) According to Table 1, we focus on the parameters proof size and verify the time. KZG is the best, IPAs are the second, and FRI is the worst. (2) According to Table 2, we focus on the proof size and verification time. Groth16 is superior to the Plonk(Kate commitment) proof system. As the setup of the Groth16 system is not universal, it cannot be used directly in zkVM or zkEVM.
Apart from zkVM as arithmetization layer, for some scenarios, like private DEX, zk KYC, or proof of data’s integrity, which does not need zkVM, we finally choose the Plonk proof system as the top layer.
Eigen Network also has some previous works on building aggregation proof and enabling GPU acceleration ( and will support ffplonk to reduce the gas cost in the future).
(1) According to Table 2, the setup of Groth16 is not universal and does not support recursion friendly, so we exclude it. The Plonk system has the same problem. So we reject it either. (2) FRI and IPAs are very easy in the recursive layer. Because the FRI system uses a special group optimization technique, its proof speed is faster. Therefore, we chose the FRI system in the bottom layer.
Here we are so excited to announce that we build the first Rusty pil-stark (from Polygon Hermez), and support parallel merkelization and parallel FFT.
The Eigen proof system architecture is shown in fig 1.
The FRI proof system based on Goldilocks field has the fastest proof speed, which makes the system proof time shortest and gives the user the best experience. The Plonk system has the smallest proof size and the lowest verification complexity, which makes the system have the lowest storage gas and the lowest verification gas consumption. Therefore, Eigen proof system combines the advantages of both and is the best proof system in zk field.
Currently, we have open-sourced the proof system in eigen-zkvm. Check out the readme, and try the Fibonacci example.
Closing
We have finished the MVP of our layered proof system and have migrated the Hermez’s zkVM to our proof system, the full example can check out here: zkVM on Eigen Layered Proof System.
But some new challenges come up. Since multi-layer brings multiple arithmetization, especially when proving for zkVM. So how to parallelize the arithmetization phase is our next important work.
