Paper 2016/985

Hash First, Argue Later: Adaptive Verifiable Computations on Outsourced Data

Dario Fiore, Cédric Fournet, Esha Ghosh, Markulf Kohlweiss, Olga Ohrimenko, and Bryan Parno


Proof systems for verifiable computation (VC) have the potential to make cloud outsourcing more trustworthy. Recent schemes enable a verifier with limited resources to delegate large computations and verify their outcome based on succinct arguments: verification complexity is linear in the size of the inputs and outputs (not the size of the computation). However, cloud computing also often involves large amounts of data, which may exceed the local storage and I/O capabilities of the verifier, and thus limit the use of VC. In this paper, we investigate multi-relation hash & prove schemes for verifiable computations that operate on succinct data hashes. Hence, the verifier delegates both storage and computation to an untrusted worker. She uploads data and keeps hashes; exchanges hashes with other parties; verifies arguments that consume and produce hashes; and selectively downloads the actual data she needs to access. Existing instantiations that fit our definition either target restricted classes of computations or employ relatively inefficient techniques. Instead, we propose efficient constructions that lift classes of existing arguments schemes for fixed relations to multi-relation hash & prove schemes. Our schemes (1) rely on hash algorithms that run linearly in the size of the input; (2) enable constant-time verification of arguments on hashed inputs; (3) incur minimal overhead for the prover. Their main benefit is to amortize the linear cost for the verifier across all relations with shared I/O. Concretely, compared to solutions that can be obtained from prior work, our new hash & prove constructions yield a 1,400x speed-up for provers. We also explain how to further reduce the linear verification costs by partially outsourcing the hash computation itself, obtaining a 480x speed-up when applied to existing VC schemes, even on single-relation executions.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.ACM Conference on Computer and Communications Security (CCS) 2016
verifiable computationdata hashescommit and proveSNARKs
Contact author(s)
oohrim @ microsoft com
2016-10-15: received
Short URL
Creative Commons Attribution


      author = {Dario Fiore and Cédric Fournet and Esha Ghosh and Markulf Kohlweiss and Olga Ohrimenko and Bryan Parno},
      title = {Hash First, Argue Later: Adaptive Verifiable Computations on Outsourced Data},
      howpublished = {Cryptology ePrint Archive, Paper 2016/985},
      year = {2016},
      doi = {10.1145/2976749.2978368},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.