SNARKs for C : verifying program executions succinctly and in zero knowledge
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/87953 |
| _version_ | 1826206880617201664 |
|---|---|
| author | Virza, Madars |
| author2 | Ronald L. Rivest and Eli Ben-Sasson. |
| author_facet | Ronald L. Rivest and Eli Ben-Sasson. Virza, Madars |
| author_sort | Virza, Madars |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. |
| first_indexed | 2024-09-23T13:39:42Z |
| format | Thesis |
| id | mit-1721.1/87953 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:39:42Z |
| publishDate | 2014 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/879532019-04-11T14:35:44Z SNARKs for C : verifying program executions succinctly and in zero knowledge Succinct Non-interactive ARgument of Knowledges for C : verifying program executions succinctly and in zero knowledge Verifying program executions succinctly and in zero knowledge Virza, Madars Ronald L. Rivest and Eli Ben-Sasson. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. Cataloged from PDF version of thesis. Includes bibliographical references (pages 69-72). We present a proof system that allows efficient verification of NP statements, given proofs produced by an untrusted yet computationally-bounded prover. Our system is publicly verifiable: after a trusted third-party has generated a proving key and a verification key, anyone can use the proving key to generate non-interactive proofs for adaptively-chosen NP statements, and the proofs can be verified by anyone using the verification key. Moreover, our system is statistically zero-knowledge and the generated public parameters are reusable. The NP-complete language we choose is the correct execution of programs on TinyRAM, a minimalistic (nondeterministic) random-access machine that we design. Together with TinyRAM port of gcc compiler this achieves the first practical realization of a zero-knowledge Succinct Non-interactive ARgument of Knowledge (zk-SNARK) for program executions, in the preprocessing model. This cryptographic primitive is a powerful solution for delegating N P computations, and enjoys many features not achieved by primitives implemented in prior works, most importantly, succinct verification and support for arbitrary computations. Our approach builds on recent theoretical work in the area of outsourced verified computation. We present efficiency improvements and implementations of the two main ingredients: 1. A transformation that, given as input a C program, outputs a circuit whose satisfiability encodes the correct execution of the program. We leverage nondeterminism to make the generated circuit's size merely quasilinear in the size of the computation; in particular, we efficiently handle arbitrary loops, control flow, and random-memory accesses. This is in contrast with existing "circuit compilers", which produce circuits of quadratic size. 2. A transformation that, given as input a linear PCP for verifying satisfiability of circuits, outputs a corresponding SNARK. Furthermore, by building on recent work about quadratic span programs, using suitable choices of finite field and FFT algorithms, we give a very efficient implementation of a zero-knowledge linear PCP: linear-time query generation and quasilinear-time prover. by Madars Virza. S.M. 2014-06-13T22:35:57Z 2014-06-13T22:35:57Z 2014 2014 Thesis http://hdl.handle.net/1721.1/87953 880419628 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 72 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Virza, Madars SNARKs for C : verifying program executions succinctly and in zero knowledge |
| title | SNARKs for C : verifying program executions succinctly and in zero knowledge |
| title_full | SNARKs for C : verifying program executions succinctly and in zero knowledge |
| title_fullStr | SNARKs for C : verifying program executions succinctly and in zero knowledge |
| title_full_unstemmed | SNARKs for C : verifying program executions succinctly and in zero knowledge |
| title_short | SNARKs for C : verifying program executions succinctly and in zero knowledge |
| title_sort | snarks for c verifying program executions succinctly and in zero knowledge |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/87953 |
| work_keys_str_mv | AT virzamadars snarksforcverifyingprogramexecutionssuccinctlyandinzeroknowledge AT virzamadars succinctnoninteractiveargumentofknowledgesforcverifyingprogramexecutionssuccinctlyandinzeroknowledge AT virzamadars verifyingprogramexecutionssuccinctlyandinzeroknowledge |