Pinocchio: Nearly Practical Verifiable Computation
By Bryan Parno, Jon Howell, Craig Gentry, Mariana Raykova. 2013
1,238 citations recorded by the source corpus.
To instill greater confidence in computations outsourced to the cloud, clients should be able to verify the correctness of the results returned. To this end, we introduce Pinocchio, a built system for efficiently verifying general computations while relying only on cryptographic assumptions. With Pinocchio, the client creates a public evaluation key to describe her computation; this setup is proportional to evaluating the computation once. The worker then evaluates the computation on a particular input and uses the evaluation key to produce a proof of correctness. The proof is only 288 bytes, regardless of the computation performed or the size of the inputs and outputs. Anyone can use a public verification key to check the proof. Crucially, our evaluation on seven applications demonstrates that Pinocchio is efficient in practice too. Pinocchio's verification time is typically 10ms: 5-7 orders of magnitude less than previous work; indeed Pinocchio is the first general-purpose system to demonstrate verification cheaper than native execution (for some apps). Pinocchio also reduces the worker's proof effort by an additional 19-60x. As an additional feature, Pinocchio generalizes to zero-knowledge proofs at a negligible cost over the base protocol. Finally, to aid development, Pinocchio provides an end-to-end toolchain that compiles a subset of C into programs that implement the verifiable computation protocol.
Subfields: Artificial Intelligence, Hardware and Architecture, Program Analysis & Verification, Privacy & Security
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
- Srinath T. V. Setty
- Dan Boneh
- Michael Walfish
- Eli Ben-Sasson
- Andrew Justin Blumberg
- Justin Thaler
- Eran Tromer
- Qiang Yang
In Hardware and Architecture
- Srinath T. V. Setty
- Arjun Narayan
- Michael Walfish
- Dan Boneh
- Andrew Justin Blumberg
- Eli Ben-Sasson
- Eran Tromer
- Justin Thaler
In Program Analysis & Verification
- Srinath T. V. Setty
- Michael Walfish
- Arjun Narayan
- Andrew Justin Blumberg
- Eli Ben-Sasson
- Justin Thaler
- Eran Tromer
- Alessandro Chiesa
In Privacy & Security
- Srinath T. V. Setty
- Dan Boneh
- Michael Walfish
- Andrew Justin Blumberg
- Eli Ben-Sasson
- Peter Kairouz
- Eran Tromer
- Justin Thaler
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, methodology): “Most existing SNARK constructions leverage quadratic arithmetic programs [174, 317, 118] and are now available in open-source libraries, such as libsnark [5], and deployed in cryptocurrencies, such as Zcash [57].”
- 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].”
- Geppetto: Versatile Verifiable Computation (2015, methodology): “, proofs of computations in which some or all of the worker’s inputs are private), many recent systems [3, 7, 9, 10, 16, 25, 39, 54] have converged on the Pinocchio protocol [46] as a cryptographic back end.”
- Zerocash: Decentralized Anonymous Payments from Bitcoin (2014, methodology): “Specifically, it uses zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) [9, 10, 11, 12, 13, 14, 15, 16].”
- VC3: Trustworthy Data Analytics in the Cloud Using SGX (2015, background): “In some cases, one of the parties may have access to the data in the clear, while the others only have to verify the result, using zero-knowledge proofs (see e. g., Pinocchio [48], Pantry [13], and ZQL [21]).”
- Verifying computations with state (2013, methodology): “Each constraint corresponds to a “register operation” (arithmetic, assignment, etc.), which provides an interpretation of our metric.”
- Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings (2019, background): “Using knowledge assumptions, it is possible to build zk-SNARKs [15, 18, 35, 45, 47, 54, 59].”
- 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.”
- Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, background): “[34, 70, 66, 15]): initial reports discussed only small word-size machines, restricted functionality and simple programs.”
- Zero-Knowledge Contingent Payments Revisited: Attacks and Payments for Services (2017, methodology): “We recall here the notion of Quadratic Arithmetic Programs (QAPs) [29, 40], using the notation of Ben-Sasson et al.”
- A Survey on the Edge Computing for the Internet of Things (2018, methodology): “A system was built in [123], named Pinocchio, which allows the clients to verify computation results based solely on cryptographic assumptions.”
- Smart meter aggregation via secret-sharing (2013, neutral): “Assuming secrets ranging over {0, 1} we can express NOT, AND, NAND, NOR and XOR gates directly as NOT(a) = 1−a; AND(a, b) = a · b; NAND(a, b) = 1−a · b; NOR(a, b) = (1− a)(1− b) [20] and XOR(a, b) = (a− b)(2).”
- Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “This is because highly efficient transformations from high-level programs to arithmetic circuits make extensive use of non-determinism for integer and bitwise operations [76, 83], storage [33, 79], and RAM [16, 21, 90].”
- Private Predictive Analysis on Encrypted Medical Data (2014, background): “Cryptographic schemes for verifying outsourced computation have been proposed and are just beginning to become practical ([10, 11]).”