What a lovely hat

Paper 2023/164

Fast Zero-Knowledge Argument System with Short Polynomial Using Direct Computation

Abstract

We introduce a new transparent zero-knowledge argument system that will significantly reduce the size of the polynomial commitment scheme (PCS) that needs to be evaluated relative to the circuit size. In our protocol, committed input parameters are transformed into a format that the verifier can process directly, so the output of the circuit polynomial at some evaluation point can be directly computed by the verifier instead of asking the prover to run the expensive PCS protocol on circuit polynomial(s) as big as the circuit size. 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. This direct computation approach brings many additional benefits. For example, it allows inputs and outputs of a circuit to be in the same commitment format. This will open up new use cases such as creating an openly accessible database with data perfectly hidden using commitments, but still allowing anyone to validate updates to the data with zero-knowledge.  Our benchmark result shows our approach can significantly improve both proving and verification speed over the state-of-the-art by one order of magnitude for all types of circuits of any depth, while keeping the communication cost competitive. (code is included in the attachment file). 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 fix from previous updated benchmark for SHA256 and others