### 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 ($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. 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 Java implementation.

Available format(s)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Keywords
zero-knowledge argumentsrange argumentspolynomial evaluation argumentsconfidential transactionssmart contracts
Contact author(s)
vincent wang @ anu edu au
sid chau @ anu edu au
History
2022-12-28: last of 4 revisions
See all versions
Short URL
https://ia.cr/2022/1251

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.