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 novel direct computation concept. Our protocol converts input parameters into a format that the verifier can process directly, so the output of the polynomial representing a circuit can be directly computed by the verifier, allowing us to significantly reduce the size of the polynomial evaluation needed to be evaluated.  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.  This direct computation approach brings many additional benefits. We can now natively handle comparison operators in addition to standard arithmetic operators by embedding range proof, allowing our protocol to efficiently handle business logics without going through the expensive arithmetization process. Furthermore, inputs and outputs of a circuit are of the same commitment format, allowing continued validation of data on openly accessible data stores.  Our benchmark result shows our approach can significantly improve both proving and verification speed over the state-of-the-art by near or over one order of magnitude for all types of circuits of any depth, while the communication cost may still be competitive.  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 + s)$, where $s = b = \sqrt{p_d}$ in the default setting.

Note: minor revision, minor bug fix