Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability
By Jonathan Bootle, Andrea Cerulli, Essam Ghadafi, Jens Groth, Mohammad Hajiabadi, S. K. Jakobsen. 2017
82 citations recorded by the source corpus.
We give computationally efficient zero-knowledge proofs of knowledge for arithmetic circuit satisfiability over a large field. For a circuit with N addition and multiplication gates, the prover only uses O(N) multiplications and the verifier only uses O(N) additions in the field. If the commitments we use are statistically binding, our zero-knowledge proofs have unconditional soundness, while if the commitments are statistically hiding we get computational soundness. Our zero-knowledge proofs also have sub-linear communication if the commitment scheme is compact. Our construction proceeds in three steps. First, we give a zero-knowledge proof for arithmetic circuit satisfiability in an ideal linear commitment model where the prover may commit to secret vectors of field elements, and the verifier can receive certified linear combinations of those vectors. Second, we show that the ideal linear commitment proof can be instantiated using error-correcting codes and non-interactive commitments. Finally, by choosing efficient instantiations of the primitives we obtain linear-time zero-knowledge proofs.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Dan Boneh
- Srinath T. V. Setty
- Benedikt Bünz
- Elette Boyle
- Henry Corrigan-Gibbs
- Mary Maller
- Niv Gilboa
- Markulf Kohlweiss
Citations in the corpus
- Bulletproofs: Short Proofs for Confidential Transactions and More (2018, background): “Examples of non-interactive protocols that do not require a trusted setup include [6], [7], [32], [42], [43].”
- Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation (2019, background): “[18] proposed a ZKP scheme with linear prover time and verification time.”
- Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings (2019, methodology): “Bootle et al. [23] introduce a model that they call the ideal linear commitment (ILC) model in which a prover can commit to vectors by sending them to a channel, and a verifier can query the channel on linear combinations of the committed vectors.”
- Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, background): “[30] introduce the “Ideal Linear Commitment” (ILC) model as an abstraction better suited to this setting.”