Geppetto: Versatile Verifiable Computation

By Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Ben Kreuter, Michael Naehrig, Bryan Parno, Samee Zahur. 2015

241 citations recorded by the source corpus.

Cloud computing sparked interest in Verifiable Computation protocols, which allow a weak client to securely outsource computations to remote parties. Recent work has dramatically reduced the client's cost to verify the correctness of their results, but the overhead to produce proofs remains largely impractical. Geppetto introduces complementary techniques for reducing prover overhead and increasing prover flexibility. With Multi QAPs, Geppetto reduces the cost of sharing state between computations (e.g, For MapReduce) or within a single computation by up to two orders of magnitude. Via a careful choice of cryptographic primitives, Geppetto's instantiation of bounded proof bootstrapping improves on prior bootstrapped systems by up to five orders of magnitude, albeit at some cost in universality. Geppetto also efficiently verifies the correct execution of proprietary (i.e, Secret) algorithms. Finally, Geppetto's use of energy-saving circuits brings the prover's costs more in line with the program's actual (rather than worst-case) execution time. Geppetto is implemented in a full-fledged, scalable compiler and runtime that consume LLVM code generated from a variety of source C programs and cryptographic libraries.

Subfields: Artificial Intelligence, Information Systems, 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

In Information Systems

In Program Analysis & Verification

In Privacy & Security

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, background): “An interesting challenge would be to try to reduce the client’s bandwidth usage without resorting to relatively expensive public-key cryptographic techniques [17, 18, 26, 41, 97].”
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, methodology): “This fact was implicitly used in previous proof systems on committed or secret-shared data [11,44,46].”
Doubly-Efficient zkSNARKs Without Trusted Setup (2018, methodology): “proof (PCP)3 and ZK transform that form the basis of many recent zkSNARK implementations [4, 5, 12, 13, 15, 16, 29, 34, 36, 39, 42–44, 64, 76, 79, 105], including systems deployed in applications like ZCash [12, 107].”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “We are motivated to design such succinct zero-knowledge arguments because there is significant interest in employing them in many applications including delegation of computation [40, 76, 80–84, 86] and stateful services [33, 39, 41, 47, 79, 94], distributed ledgers and blockchains [15, 31, 36, 67],”
Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts (2016, methodology): “Examples include recursively composed SNARKs [18], [25] or other efficient PCP constructions [16].”
Verifiable ASICs (2016, background): “For example, the scaling limit on GGPR-based SNARKs can be circumvented by composition [32, 37, 56].”
Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation (2019, background): “[26] introduced quadratic arithmetic programs (QAPs), which forms the basis of most recent implementations [11,14,19,23,25,40,46] including libSNARK [13].”
Full Accounting for Verifiable Outsourcing (2017, background): “The algorithm’s input is a C program with the following restrictions (commonly imposed by the most efficient front-ends [37, 66, 84, 85]): loop bounds are statically computable, no recursive functions, and no function pointers.”
Aurora: Transparent Succinct Arguments for R1CS (2019, background): “This approach, pioneered in [50, 45, 60, 29], relied on combining certain linearly homomorphic encodings with lightweight information-theoretic tools known as linear PCPs [54, 29, 71]; this approach was refined and optimized in several works [23, 22, 40, 51, 30, 52].”
Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, methodology): “[33] build on our idea of obtaining bounded recursive proof composition, using PCD-friendly chains of elliptic curves found via the Cocks–Pinch method (see Remark 3.”