Paper 2023/164

Concretely Efficient Input Transformation Based Zero-Knowledge Argument System for Arbitrary Circuits

Abstract

We introduce a new transparent zero-knowledge argument system based on the direct computation concept described in this paper. Our protocol converts input parameters into a format that any circuit can process directly. Once the circuit output can be computed using transformed inputs, the output of the polynomial a circuit generates can also be correctly computed by the verifier, allowing us to reduce the polynomial evaluation cost significantly.  In the default setting, the prover runtime cost for group exponentiation operations is only the square root of the degree ($\sqrt{p_d}$) of the polynomial the circuit generates. Furthermore, leveraging the ``merging through addition" and ``bootstrapping with breakers" techniques, the size of the polynomial our protocol generates can be much smaller than the total number of multiplicative operations. Our benchmark result shows our approach can significantly improve both prover runtime and verifier runtime performance over state-of-the-art by almost or over one order of magnitude while keeping the communication cost comparable with that of the state-of-the-art.  Our approach also allows our protocol to be made memory-efficient while being non-interactive. The theoretical memory cost of our protocol is $O(b)$, where $b = \sqrt{p_d}$ in the default setting. Setting the bootstrapping parameter ($b$) aggressively will result in better prover runtime performance at the expense of the higher communication cost.

Note: multiple updates, adding a sub-protocol to demonstrate quasi-scalability relative to witness size