Paper 2013/507
SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza
Abstract
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.
We present an implementation of a publicly-verifiable non-interactive argument system for NP. The system, moreover, is a zero-knowledge proof-of-knowledge. It directly proves correct executions of programs on TinyRAM, a random-access machine tailored for efficient verification of nondeterministic computations. Given a program
Note: Revised for clarity, especially Section 3 and Appendix E.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in CRYPTO 2013
- Keywords
- computationally-sound proofssuccinct argumentszero-knowledgedelegation of computation
- Contact author(s)
- tromer @ cs tau ac il
- History
- 2013-10-07: revised
- 2013-08-17: received
- See all versions
- Short URL
- https://ia.cr/2013/507
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/507, author = {Eli Ben-Sasson and Alessandro Chiesa and Daniel Genkin and Eran Tromer and Madars Virza}, title = {{SNARKs} for C: Verifying Program Executions Succinctly and in Zero Knowledge}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/507}, year = {2013}, url = {https://eprint.iacr.org/2013/507} }