Scaling Verifiable Computation Using Efficient Set Accumulators

Alex Ozdemir; Riad S.  Wahby; Barry Whitehat; Dan Boneh

Paper 2019/1494

Scaling Verifiable Computation Using Efficient Set Accumulators

Alex Ozdemir, Riad S. Wahby, Barry Whitehat, and Dan Boneh

Abstract

Verifiable outsourcing systems offload a large computation to a remote server, but require that the remote server provide a succinct proof, called a SNARK, that proves that the server carried out the computation correctly. Real-world applications of this approach can be found in several blockchain systems that employ verifiable outsourcing to process a large number of transactions off-chain. This reduces the on-chain work to simply verifying a succinct proof that transaction processing was done correctly. In practice, verifiable outsourcing of state updates is done by updating the leaves of a Merkle tree, recomputing the resulting Merkle root, and proving using a SNARK that the state update was done correctly. In this work, we use a combination of existing and novel techniques to implement an RSA accumulator inside of a SNARK, and use it as a replacement for a Merkle tree. We specifically optimize the accumulator for compatibility with SNARKs. Our experiments show that the resulting system reduces costs compared to existing approaches that use Merkle trees for committing to the current state. These results apply broadly to any system that needs to offload batches of state updates to an untrusted server.

Note: camera-ready version

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint. MINOR revision.
Keywords: SNARKs RSA Merkle Accumulators
Contact author(s): aozdemir @ cs stanford edu
History: 2020-06-23: last of 2 revisions; 2019-12-30: received; See all versions
Short URL: https://ia.cr/2019/1494
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1494,
      author = {Alex Ozdemir and Riad S.  Wahby and Barry Whitehat and Dan Boneh},
      title = {Scaling Verifiable Computation Using Efficient Set Accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1494},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1494}},
      url = {https://eprint.iacr.org/2019/1494}
}