Efficient RAM and control flow in verifiable outsourced computation

By Riad S. Wahby, Srinath T. V. Setty, Zuocheng Ren, Andrew Justin Blumberg, Michael Walfish. 2015

190 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications

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

1. Srinath T. V. Setty
2. Dan Boneh
3. Michael Walfish
4. Eli Ben-Sasson
5. Iddo Bentov
6. Andrew Justin Blumberg
7. Michael Riabzev
8. Eran Tromer

In Computer Networks and Communications

1. Michael Walfish
2. Srinath T. V. Setty
3. Eli Ben-Sasson
4. Arjun Narayan
5. Andrew Justin Blumberg
6. Dan Boneh
7. Justin Thaler
8. Eran Tromer

Citations in the corpus

• Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “The core idea behind Prio is reminiscent of techniques used in verifiable computation [16, 37, 62, 69, 97, 115, 116, 119], but in reverse—the client proves to a set of servers that it computed a function correctly.”
• 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.”
• Doubly-Efficient zkSNARKs Without Trusted Setup (2018, background): “Further, zkSTARKs are heavily optimized for statements whose verifying circuits are expressed as a sequence of state-machine transitions; this captures all of NP, but can introduce significant overhead in practice [105].”
• PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations (2016, background): “execution of C programs [43], [7], [56], [4], [6].”
• Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, background): “Furthermore, it is not entirely clear how these works can achieve sub-linear verification costs—without employing uniform circuits (which are far more verbose than equivalent non-uniform circuits [90]).”
• Verifiable differential privacy (2015, methodology): “Recently, several promising works have enabled support for data-dependent loops via novel circuit representations [4, 5, 48]; a future version of VerDP could incorporate techniques from these systems to improve VFuzz’s expressiveness.”
• Verifiable Delay Functions (2018, background): “The construction has, however, two significant downsides: In practice computing a SNARG is more than 100,000 times more expensive than evaluating the underlying computation [70].”
• 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].”
• Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, unknown): “KOE-based systems were implemented in [66, 71, 15, 19, 77], and further optimizations of this latter system for specific applications related to Bitcoin [65] such as smart contracts [58] and anonymous payment systems [12] are already being evaluated by commercial entities [46].”
• Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts (2016, background): “Succinct Non-interactive ARguments of Knowledge [12], [33], [49] provide succinct proofs for general computation tasks, and have been implemented by several systems [12], [49], [56].”
• Verifiable ASICs (2016, background): “We discuss non-recurring costs (engineering, creating photolithographic masks, etc.) in Section 9.”
• Scalable, transparent, and post-quantum secure computational integrity (2018, methodology): “The first implementation of a QSP based system is called Pinocchio [88], with subsequent implementations including libSNARK [21, 96] (discussed in the next section) which is used in the Zerocash and ZcashTM implementations; additional implementations appear in [98, 101, 100, 99, 24, 108, 46].”
• Scalable Zero Knowledge with No Trusted Setup (2019, methodology): “The first implementation of a QSP based system is called Pinocchio [63], with subsequent implementations including libSNARK [19, 68] which is used in the Zerocash and ZcashTM implementations; additional implementations appear in [70, 73, 72, 71, 24, 79, 37, 82].”
• Verifying computations without reexecuting them (2015, methodology): “Buffet [48] combines the best features of Pantry and TinyRAM.”
• Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, background): “Most zk-SNARK constructions [6,9,14,17,43,52,55,64,67–69,82,113,114], including published implementations [6,9,17,64,82,113,114], require expensive preprocessing during key generation.”