Paper 2016/646

Computational integrity with a public random string from quasi-linear PCPs

Eli Ben-Sasson, Iddo Ben-Tov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, and Madars Virza


A party running a computation remotely may benefit from misreporting its output, say, to lower its tax. Cryptographic protocols that detect and prevent such falsities hold the promise to enhance the security of decentralized systems with stringent computational integrity requirements, like Bitcoin [Nak09]. To gain public trust it is imperative to use publicly verifiable protocols that have no “backdoors” and which can be set up using only a short public random string. Probabilistically Checkable Proof (PCP) systems [BFL90, BFLS91, AS98, ALM + 98] can be used to construct astonishingly efficient protocols [Kil92, Mic00] of this nature but some of the main components of such systems — proof composition [AS98] and low-degree testing via PCPs of Proximity (PCPPs) [BGH + 05, DR06] — have been considered efficient only asymptotically, for unrealistically large computations; recent cryptographic alternatives [PGHR13, BCG + 13a] suffer from a non-public setup phase. This work introduces SCI, the first implementation of a scalable PCP system (that uses both PCPPs and proof composition). We used SCI to prove correctness of executions of up to $2^{20}$ cycles of a simple processor (Figure 1) and calculated (Figure 2) its break-even point [SVP + 12, SMBW12]. The significance of our findings is two-fold: (i) it marks the transition of core PCP techniques (like proof composition and PCPs of Proximity) from mathematical theory to practical system engineering, and (ii) the thresholds obtained are nearly achievable and hence show that PCP-supported computational integrity is closer to reality than previously assumed.

Note: fixed latex math typo in the abstract ($2^20$ -> $2^{20}$).

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
PCPimplementationinteractive proofs
Contact author(s)
eli @ cs technion ac il
2017-01-18: revised
2016-06-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Eli Ben-Sasson and Iddo Ben-Tov and Alessandro Chiesa and Ariel Gabizon and Daniel Genkin and Matan Hamilis and Evgenya Pergament and Michael Riabzev and Mark Silberstein and Eran Tromer and Madars Virza},
      title = {Computational integrity with a public random string from quasi-linear {PCPs}},
      howpublished = {Cryptology ePrint Archive, Paper 2016/646},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.