Full Accounting for Verifiable Outsourcing

By Riad S. Wahby, Ye Ji, Andrew Justin Blumberg, Abhi Shelat, Justin Thaler, Michael Walfish, Thomas Wies. 2017

80 citations recorded by the source corpus.

Systems for verifiable outsourcing incur costs for a prover, a verifier, and precomputation; outsourcing makes sense when the combination of these costs is cheaper than not outsourcing. Yet, when prior works impose quantitative thresholds to analyze whether outsourcing is justified, they generally ignore prover costs. Verifiable ASICs (VA)---in which the prover is a custom chip---is the other way around: its cost calculations ignore precomputation. This paper describes a new VA system, called Giraffe; charges Giraffe for all three costs; and identifies regimes where outsourcing is worthwhile. Giraffe's base is an interactive proof geared to data-parallel computation. Giraffe makes this protocol asymptotically optimal for the prover and improves the verifier's main bottleneck by almost 3x, both of which are of independent interest. Giraffe also develops a design template that produces hardware designs automatically for a wide range of parameters, introduces hardware primitives molded to the protocol's data flows, and incorporates program analyses that expand applicability. Giraffe wins even when outsourcing several tens of sub-computations, scales to 500x larger computations than prior work, and can profitably outsource parts of programs that are not worthwhile to outsource in full.

Subfields: Artificial Intelligence

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

Citations in the corpus

Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware (2018, background): “Wahby et al. (2016; 2017) aim at this goal for arbitrary computations outsourced between co-located ASICs.”
Aurora: Transparent Succinct Arguments for R1CS (2019, background): “The sumcheck protocol plays a fundamental role in computational complexity (it underlies celebrated results such as IP = PSPACE [72] and MIP = NEXP [10]) and in efficient proof protocols [48, 39, 75, 73, 74, 76, 77, 82, 83, 79].”
Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation (2019, methodology): “(2) O(C + C ′ logC ′) for data-parallel circuits with a small copy of size C ′, proposed in [45].”
Doubly-Efficient zkSNARKs Without Trusted Setup (2018, methodology): “As an exception, Gir++ uses the “reducing from two points to one point” technique after the final sum-check (i.e., the one over Q...,d−1); this is to avoid increasingV’s computational costs compared to Giraffe.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “Ligero [3] public O(n log n) O( √ n) O(n) CRHF arbitrary circuits Hyrax [89] public O(n + m · g) O(m + |w|) O(m + |w|1−1/c) DLOG layered circuits Hyrax-log [89] public O(n + m · g) O(m + log |w|) O(m + |w|) DLOG layered circuits Bulletproofs [34] public O(n) O(log n) O(n) DLOG arbitrary circuits zkS”
The Efficient Server Audit Problem, Deduplicated Re-execution, and the Web (2017, background): “Execution integrity has long been studied by theorists [15, 37, 38, 42, 60], and these ideas have been refined and implemented [19, 32, 65, 75] (see [89] for a survey and [12, 18, 88, 96] for recent developments).”