Paper 2022/1251

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

Nan Wang, Australian National University
Sid Chi-Kin Chau, Australian National University

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 ($D \in [3, 2^9]$) and higher-degree ($D > 2^9$) polynomials, where $D$ 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 $8\log D$ to $3(\log D+\sqrt{\log D})$. The communication cost and the number of group exponentiations for verification decrease from $7\log D$ to $(\log D + 3\sqrt{\log D})$. 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 $O(\log D)$ to $O(\sqrt{\log D})$ when multiple arguments satisfying different polynomials with the same degree and inputs are aggregated.

Note: The source code is published at the link

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Zero-knowledge arguments range arguments polynomial evaluation arguments confidential transactions smart contracts
Contact author(s)
vincent wang @ anu edu au
sid chau @ anu edu au
2022-10-02: last of 2 revisions
2022-09-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nan Wang and Sid Chi-Kin Chau},
      title = {Flashproofs: Efficient Zero-Knowledge Arguments of Range and Polynomial Evaluation with Transparent Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1251},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.