QuickSilver: Efficient and Affordable Zero-Knowledge Proofs for Circuits and Polynomials over Any Field

Kang Yang, Pratik Sarkar*, Chenkai Weng, Xiao Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Scopus citations

Abstract

Zero-knowledge (ZK) proofs with an optimal memory footprint have attracted a lot of attention, because such protocols can easily prove very large computation with a small memory requirement. Such ZK protocol only needs O(M) memory for both parties, where M is the memory required to verify the statement in the clear. In this paper, we propose several new constant-round ZK protocols in this setting, which improve the concrete efficiency and, at the same time, enable sublinear amortized communication for circuits with some notion of relaxed uniformity. In the circuit-based model, where the computation is represented as a circuit over a field, our ZK protocol achieves a communication complexity of 1 field element per non-linear gate for any field size while keeping the computation very cheap. We implemented our protocol, which shows extremely high efficiency and affordability. Compared to the previous best-known implementation, we achieve 6x - 7x improvement in computation and 3x - 7x improvement in communication. When running on intro-level AWS instances, our protocol only needs one US dollar to prove one trillion AND gates (or 2.5 US dollars for one trillion multiplication gates over a 61-bit field). In the setting where part of the computation can be represented as a set of polynomials with a "degree-separated"format, we can achieve communication sublinear to the polynomial size: the communication only depends on the total number of distinct variables in all the polynomials and the highest degree of all polynomials, independent of the number of multiplications to compute all polynomials. Using the improved ZK protocol, we can prove matrix multiplication with communication proportional to the input size, rather than the number of multiplications. Proving the multiplication of two 1024 x 1024 matrices, our implementation, with one thread and 1 GB of memory, only needs 10 seconds and communicates 25 MB.

Original languageEnglish (US)
Title of host publicationCCS 2021 - Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Pages2986-3001
Number of pages16
ISBN (Electronic)9781450384544
DOIs
StatePublished - Nov 12 2021
Event27th ACM Annual Conference on Computer and Communication Security, CCS 2021 - Virtual, Online, Korea, Republic of
Duration: Nov 15 2021Nov 19 2021

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Conference

Conference27th ACM Annual Conference on Computer and Communication Security, CCS 2021
Country/TerritoryKorea, Republic of
CityVirtual, Online
Period11/15/2111/19/21

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'QuickSilver: Efficient and Affordable Zero-Knowledge Proofs for Circuits and Polynomials over Any Field'. Together they form a unique fingerprint.

Cite this