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.
Category / Keywords: cryptographic protocols / Verifiable Computation, SNARGs, SNARKs, Zero Knowledge Date: received 6 May 2015 Contact author: parno at microsoft com Available format(s): PDF | BibTeX Citation Version: 20150507:183808 (All versions of this report) Short URL: ia.cr/2015/437 Discussion forum: Show discussion | Start new discussion