Paper 2015/437

A Note on the Unsoundness of vnTinyRAM's SNARK

Bryan Parno

Abstract

Gennaro, Gentry, Parno, and Raykova (GGPR) introduced Quadratic Arithmetic Programs (QAPs) as a way of representing arithmetic circuits in a form amendable to highly efficient cryptographic protocols (EUROCRYPT 2013), particularly for verifiable computation and succinct non-interactive arguments. Subsequently, Parno, Gentry, Howell, and Raykova introduced an improved cryptographic protocol (and implementation), which they dubbed Pinocchio (IEEE S&P 2013). Ben-Sasson et al. then introduced a lightly modified version of the Pinocchio protocol and implemented it as part of their libsnark distribution. Later work by the same authors employed this protocol, as did a few works by others. Many of these works cite the version of the paper which was published at USENIX Security. However, the protocol does not appear in that peer-reviewed paper; instead, it appears only in a technical report, where it is justified via a lemma that lacks a proof. Unfortunately, the lemma is incorrect, and the modified protocol is unsound. With probability one, an adversary can submit false statements and proofs that the verifier will accept. We demonstrate this theoretically, as well as with concrete examples in which the protocol's implementation in libsnark accepts invalid statements. Fixing this problem requires different performance tradeoffs, indicating that the performance results reported by papers building on this protocol (USENIX Security 2013, CRYPTO 2014, NDSS 2014, EUROCRYPT 2015, IEEE S&P 2014, IEEE S&P 2015) are, to a greater or lesser extent, inaccurate.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Verifiable ComputationSNARGsSNARKsZero Knowledge
Contact author(s)
parno @ microsoft com
History
2015-05-07: received
Short URL
https://ia.cr/2015/437
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/437,
      author = {Bryan Parno},
      title = {A Note on the Unsoundness of {vnTinyRAM}'s {SNARK}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/437},
      year = {2015},
      url = {https://eprint.iacr.org/2015/437}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.