IACR News item: 15 February 2023
Frank Y.C. Lu
ePrint Report
We introduce an efficient transparent interactive zero knowledge argument system with practical succinctness. Our system converts circuit inputs in Pedersen commitment form to linear polynomials so that the verifier can use standard integer operations to compute and verify the circuit output. The verifier runtime of our protocol is linear to the number of multiplication gates in the path that contains the most multiplications in a circuit (we use symbol $d_m$ to denote its value). However, its practical performance still compares favorably against state-of-the-art transparent zero-knowledge protocols with sub-linear verifier work.
The asymptotic cost of our protocol is $O (d_m \text{ log } d_m)$ for prover work, $O (d_m)$ for verifier work, and $ O({d_m}^{1/2})$ for communication cost, where $d_m$ stands for the total number of multiplication gates in the path that contains the most multiplications in a circuit (e.g. for a circuit with $n=2^{20}$ sequential multiplications, $d_m = n$). Specifically, when running a circuit with $2^{20}$ multiplication gates on a single thread CPU, the prover runtime of our protocol is $1.9$ seconds, the verifier runtime is $32$ ms and the communication cost is $56$ kbs.
In this paper, we will first introduce a base version of our protocol in which the prover work is dominated by $O ({d_m}^2)$ field operations. Although field operations are significantly faster than group operations, they become increasingly expensive as $d_m$ value gets large. So in the follow up sections, we will introduce a mechanism to apply number theoretic transformation (NTT) to bring down the prover time to $O (d_m \text{ log } d_m)$.
Another added benefit of our protocol is that it does not require a front end encoder to translate NP relation $R$ to some zero-knowledge friendly representation $\hat{R}$ (such as R1CS constraint system) before the relation can be converted to a proof system, making our protocol relatively easy to implement and also easier to use compared to constraint system based protocols.
The asymptotic cost of our protocol is $O (d_m \text{ log } d_m)$ for prover work, $O (d_m)$ for verifier work, and $ O({d_m}^{1/2})$ for communication cost, where $d_m$ stands for the total number of multiplication gates in the path that contains the most multiplications in a circuit (e.g. for a circuit with $n=2^{20}$ sequential multiplications, $d_m = n$). Specifically, when running a circuit with $2^{20}$ multiplication gates on a single thread CPU, the prover runtime of our protocol is $1.9$ seconds, the verifier runtime is $32$ ms and the communication cost is $56$ kbs.
In this paper, we will first introduce a base version of our protocol in which the prover work is dominated by $O ({d_m}^2)$ field operations. Although field operations are significantly faster than group operations, they become increasingly expensive as $d_m$ value gets large. So in the follow up sections, we will introduce a mechanism to apply number theoretic transformation (NTT) to bring down the prover time to $O (d_m \text{ log } d_m)$.
Another added benefit of our protocol is that it does not require a front end encoder to translate NP relation $R$ to some zero-knowledge friendly representation $\hat{R}$ (such as R1CS constraint system) before the relation can be converted to a proof system, making our protocol relatively easy to implement and also easier to use compared to constraint system based protocols.
Additional news items may be found on the IACR news page.