Paper 2023/164

Input Transformation Based Zero-Knowledge Argument System for Arbitrary Circuits

Abstract

We introduce a new efficient, transparent, interactive zero-knowledge argument system that is based on the new input transformation concept that we will introduce in this paper. The core of this concept is a mechanism that converts input parameters into a format that can be processed directly by the circuit so that the circuit output can be verified through direct computation of the circuit.  Our benchmark result shows our approach can significantly improve both prover runtime and verifier runtime performance by either close to or more than one order of magnitude over the state of the art while keeping the communication cost competitive with that of the state of the art. Specifically, when processing an deep circuit of $2^{20}$ sequential multiplication gates with 960 input bits on a single CPU thread, the performance of the BinaryBoost version of our protocol is: $0.8$ seconds for the prover runtime cost; $17$ milliseconds for the verifier runtime cost; and $55$ kilobytes for the communication cost. Our approach also allows our protocol to be memory-efficient without forcing it to require a designated verifier. The theoretical memory cost of our protocol is  $\leq O({m_p}^{\frac{1}{2}})$ without requiring a designated verifier.

Note: major revision