Welcome to the resource topic for 2023/164
Title:
Input Transformation Based Efficient Zero-Knowledge Argument System for Arbitrary Circuits with Practical Succinctness
Authors: Frank Y.C. Lu
Abstract: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.
ePrint: https://eprint.iacr.org/2023/164
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .