Paper 2022/1251

Flashproofs: Efficient Zero-Knowledge Arguments of Range and Polynomial Evaluation with Transparent Setup

Abstract

We propose Flashproofs, a new type of efficient special honest verifier zero-knowledge arguments with a transparent setup in the discrete logarithm (DL) setting. First, we put forth gas-efficient range arguments that achieve $O(N^{\frac{2}{3}})$ communication cost, and involve $O(N^{\frac{2}{3}})$ group exponentiations for verification and a slightly sub-linear number of group exponentiations for proving with respect to the range $[0,2^N-1]$, where $N$ is the bit length of the range. For typical confidential transactions on blockchain platforms supporting smart contracts, verifying our range arguments consumes only 234K and 315K gas for 32-bit and 64-bit ranges, which are comparable to 220K gas incurred by verifying the most efficient zkSNARK with a trusted setup (EUROCRYPT 16) at present. Besides, the aggregation of multiple arguments can yield further efficiency improvement. Second, we present polynomial evaluation arguments based on the techniques of Bayer & Groth (EUROCRYPT 13). We provide two zero-knowledge arguments, which are optimised for lower-degree ($$) and higher-degree ($$) polynomials, where $$ is the polynomial degree. Our arguments yield a non-trivial improvement in the overall efficiency. Notably, the number of group exponentiations for proving drops from $$ to $$. The communication cost and the number of group exponentiations for verification decrease from $$ to $$. To the best of our knowledge, our arguments instantiate the most communication-efficient arguments of membership and non-membership in the DL setting among those not requiring trusted setups. More importantly, our techniques enable a significantly asymptotic improvement in the efficiency of communication and verification (group exponentiations) from $$ to $$ when multiple arguments satisfying different polynomials with the same degree and inputs are aggregated.

Note: The source code is published at the link https://github.com/wangnan-vincent/Flashproofs. Some updates have been made to the Asiacrypt 2022 publication. Please refer to this ePrint version. 1. The gas costs of 32-bit and 64-bit range arguments have been further reduced to 234k and 315k, respectively, by improving the Solidity code. 2. The proving and verification complexity of Bulletproofs have been re-estimated based on the original paper.