Full Accounting for Verifiable Outsourcing

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 dataparallel computation. Giraffe makes this protocol asymptotically optimal for the prover and improves the verifier's main bottleneck by almost 3×, 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 500× larger computations than prior work, and can profitably outsource parts of programs that are not worthwhile to outsource in full. INTRODUCTION In probabilistic proofs-Interactive Proofs (IPs) [12, 49, 50, 58, 76] , arguments [30, 52, 54, 62] , SNARGs [48], SNARKs [26, 47] , and PCPs [9, 10]-a prover efficiently convinces a verifier of a claim, in such a way that the verifier is highly likely to reject a false claim. These protocols are foundational in complexity theory and cryptography. There has also been substantial progress in implementations over the last six years [14