Welcome to the resource topic for 2022/1251
Title:
Flashproofs: Efficient Zero-Knowledge Arguments of Range and Polynomial Evaluation with Transparent Setup
Authors: Nan Wang, Sid Chi-Kin Chau
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 237K and 318K 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.
ePrint: https://eprint.iacr.org/2022/1251
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .