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
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 ($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 https://github.com/wangnan-vincent/Flashproofs.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Keywords
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
History
2022-10-02: last of 2 revisions
2022-09-21: received
See all versions
Short URL
https://ia.cr/2022/1251
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1251,
      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{https://eprint.iacr.org/2022/1251}},
      url = {https://eprint.iacr.org/2022/1251}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.