SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge

By Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza. 2013

719 citations recorded by the source corpus.

An argument system for NP is a proof system that allows efficient verification of NP statements, given proofs produced by an untrusted yet computationally-bounded prover. Such a system is non-interactive and publicly-verifiable if, after a trusted party publishes a proving key and a verification key, anyone can use the proving key to generate non-interactive proofs for adaptively-chosen NP statements, and proofs can be verified by anyone by using the verification key.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Bulletproofs: Short Proofs for Confidential Transactions and More (2018, background): “SNARKs, which have succinct proofs and efficient verifiers, seem like a natural choice, but current practical SNARKs [BSCG ` 13] require a complex trusted setup.”
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “Prio improves client performance as well: it is 50-100× faster than NIZKs and we estimate that it is three orders of magnitude faster than methods based on succinct non-interactive arguments of knowledge (SNARKs) [16,62,97].”
Verifying computations with state (2013, methodology): “BCGTV [12] use a promising circuit representation from [11] (a different instantiation of steps (1) and (2) in §2.”
Confidential Assets (2018, background): “It does not support multiple assets, though its use of zk-SNARKs [3], which are general-purpose zero-knowledge arguments, mean that asset support would not be a difficult extension.”
Verifiable ASICs (2016, background): “We discuss non-recurring costs (engineering, creating photolithographic masks, etc.) in Section 9.”
Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings (2019, methodology): “In the decades since their introduction, zero-knowledge proofs have been used to support a wide variety of potential applications, ranging from verifiable outsourced computation [11, 16, 24, 59]”
A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks (2018, background): “, zk-SNARK [75] have to query a trusted third-party key/random seed generation protocol to produce a common reference string for both the prover and the verifier.”
Doubly-Efficient zkSNARKs Without Trusted Setup (2018, background): “(In contrast, many recent works invoke cryptographic primitives for each gate in the verifying circuit [12, 13, 16, 24, 30, 46, 79]; §2.”
The Efficient Server Audit Problem, Deduplicated Re-execution, and the Web (2017, background): “Execution integrity has long been studied by theorists [15, 37, 38, 42, 60], and these ideas have been refined and implemented [19, 32, 65, 75] (see [89] for a survey and [12, 18, 88, 96] for recent developments).”
ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data (2015, methodology): “As noted in previous work, by using SNARKs for NP , it is possible to construct a verifiable computation scheme, and several works [9, 10, 17] indeed follow this approach.”
Privacy-Preserving Solutions for Blockchain: Review and Challenges (2019, background): “zkSNARK (zero-knowledge Succinct Non-Interactive ARgument of Knowledge) [95] is similar to ZKP, but their construction offers more possibilities that the blockchain technology [103], [104].”
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, methodology): “However, current zk-SNARK implementations [56, 16] require the setup phase to depend on the program F , which is hard-coded in the keys.”
Transparent SNARKs from DARK Compilers (2020, methodology): “These are the pairing-based SNARKs extending from GGPR [31,47,9,6,35], which have been implemented in numerous libraries [6,16], and even deployed in live systems such as the ZCash [1] cryptocurrency.”
A Survey of IoT Applications in Blockchain Systems (2020, background): “Moreover, the zero-knowledge proof [Ben-Sasson et al. 2013] is used in blockchain to provide advanced data privacy of data sharing in blockchain.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, background): “, uniform circuits); although any circuit can be converted to this form [16, 18], such a transformation incurs 10–1000× blowup in circuit size (which translates to a similar factor increase in the prover’s costs) when compared to equivalent but non-uniform circuits [90]; (4) The verifier in Aurora [”
TumbleBit: An Untrusted Bitcoin-Compatible Anonymous Payment Hub (2017, methodology): “Recently, [37] showed how to instantiate the ZK proofs used in this protocol with ZKSnarks [11].”