Paper 2021/641

Hydra: Succinct Fully Pipelineable Interactive Arguments of Knowledge

William Zhang and Yu Xia

Abstract

We present advancements for interactive arguments with Hydra, a novel verifiable computation system. Hydra introduces two new disjoint interactive argument scheme protocols geared towards the efficient pipelining of circuit verification. The first is specific to subcircuits, where a deep circuit is broken up into smaller parts and proven concurrently. The second is a more general scheme where all layers of the circuit can be proven in parallel, removing the dependency on the layer-wise synchronous execution of the protocol. Compared to non-interactive SNARKs which rely on knowledge type assumptions (or the Random Oracle model) and theoretical non-interactive arguments based on standard assumptions that are not useful in practice, Hydra achieves a sweet spot with a practical approach. From standard assumptions, Hydra collapses the round complexity to polylogarithmic to the width of the circuit, but only incurs polylogarithmic blowup in bandwidth and verifier time complexity. We implement the full verification flow, including both protocols and a logic parser used to convert traditional logic circuit compilation outputs into provable layered arithmetic representations. We perform experimental evaluations of our proposals and demonstrate protocol time efficiency improvements of up to 34.8 times and 4.3 times respectively compared to traditional approaches on parallel hardware.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
verifiable computationcryptographysecurity protocols
Contact author(s)
williamhyzhang @ gmail com
yuxia @ mit edu
History
2021-05-17: received
Short URL
https://ia.cr/2021/641
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/641,
      author = {William Zhang and Yu Xia},
      title = {Hydra: Succinct Fully Pipelineable Interactive Arguments of Knowledge},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/641},
      year = {2021},
      url = {https://eprint.iacr.org/2021/641}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.