Home > Resources > papers > BCGTV13-SNARKs-for-C

SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge (Ben-Sasson et al. 2013)

URL: https://eprint.iacr.org/2013/507.pdf

Summary

Presents a publicly-verifiable, non-interactive zero-knowledge argument system for verifying correct execution of arbitrary C programs. Programs are compiled (via a GCC port) to TinyRAM, a random-access machine designed for efficient nondeterministic-computation verification, whose executions are then encoded into quadratic arithmetic programs and proven with a linear-PCP-based SNARK. This closed the gap between SNARK theory (QSP/QAP, Pinocchio) and practical verification of general-purpose programs, rather than only static circuits.

Related resources

• Pinocchio: Nearly Practical Verifiable Computation (Parno et al. 2013) (paper, 2013)
• Quadratic Span Programs and Succinct NIZKs without PCPs (GGPR 2013) (paper, 2012)