Full accounting for verifiable outsourcing

Riad S.  Wahby; Ye Ji; Andrew J.  Blumberg; abhi shelat; Justin Thaler; Michael Walfish; Thomas Wies

Paper 2017/242

Full accounting for verifiable outsourcing

Riad S. Wahby, Ye Ji, Andrew J. Blumberg, abhi shelat, Justin Thaler, Michael Walfish, and Thomas Wies

Abstract

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.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. Major revision. CCS 2017
DOI: 10.1145/3133956.3133984
Keywords: verifiable computation trustworthy hardware probabilistic proofs interactive proofs sum-check protocol
Contact author(s): rsw @ cs stanford edu
History: 2017-09-05: last of 5 revisions; 2017-03-14: received; See all versions
Short URL: https://ia.cr/2017/242
License: CC BY

BibTeX

@misc{cryptoeprint:2017/242,
      author = {Riad S.  Wahby and Ye Ji and Andrew J.  Blumberg and abhi shelat and Justin Thaler and Michael Walfish and Thomas Wies},
      title = {Full accounting for verifiable outsourcing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/242},
      year = {2017},
      doi = {10.1145/3133956.3133984},
      url = {https://eprint.iacr.org/2017/242}
}