Polaris: Transparent Succinct Zero-Knowledge Arguments for R1CS with Efficient Verifier
Shihui Fu, Guang Gong
Abstract
Abstract We present a new zero-knowledge succinct argument of knowledge (zkSNARK) scheme for Rank-1 Constraint Satisfaction (RICS), a widely deployed NP-complete language that generalizes arithmetic circuit satisfiability. By instantiating with different commitment schemes, we obtain several zkSNARKs where the verifier’s costs and the proof size range from O (log 2 N ) to <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline"><m:mrow><m:mi>O</m:mi><m:mrow><m:mo>(</m:mo><m:mrow><m:msqrt><m:mi>N</m:mi></m:msqrt></m:mrow><m:mo>)</m:mo></m:mrow></m:mrow></m:math> O\left( {\sqrt N } \right) depending on the underlying polynomial commitment schemes when applied to an N -gate arithmetic circuit. All these schemes do not require a trusted setup. It is plausibly post-quantum secure when instantiated with a secure collision-resistant hash function. We report on experiments for evaluating the performance of our proposed system. For instance, for verifying a SHA-256 preimage (less than 23k AND gates) in zero-knowledge with 128 bits security, the proof size is less than 150kB and the verification time is less than 11ms, both competitive to existing systems.