Paper 2022/1251
Flashproofs: Efficient ZeroKnowledge Arguments of Range and Polynomial Evaluation with Transparent Setup
Abstract
We propose Flashproofs, a new type of efficient special honest verifier zeroknowledge arguments with a transparent setup in the discrete logarithm (DL) setting. First, we put forth gasefficient 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 sublinear number of group exponentiations for proving with respect to the range $[0, 2^N1]$, 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 32bit and 64bit 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 zeroknowledge arguments, which are optimised for lowerdegree ($D \in [3, 2^9]$) and higherdegree ($D > 2^9$) polynomials, where $D$ is the polynomial degree. Our arguments yield a nontrivial 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 communicationefficient arguments of membership and nonmembership 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/wangnanvincent/Flashproofs. Some updates have been made to the Asiacrypt 2022 publication. Please refer to this ePrint version. 1. The gas costs of 32bit and 64bit 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 reestimated based on the original paper.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2022
 Keywords
 zeroknowledge argumentsrange argumentspolynomial evaluation argumentsconfidential transactionssmart contracts
 Contact author(s)

vincent wang @ anu edu au
sid chau @ anu edu au  History
 20230405: last of 7 revisions
 20220921: received
 See all versions
 Short URL
 https://ia.cr/2022/1251
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1251, author = {Nan Wang and Sid ChiKin Chau}, title = {Flashproofs: Efficient ZeroKnowledge 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} }