A Gentle Introduction to the PCP Theorem - Part 2

DISCLAIMER: In October 2020 PegaSys was renamed to Quorum.

This paper was written by Olivier Bégassat, Applied Researcher at PegaSys Protocol Engineering. It is the second post of a two-part series on Probabilistically Checkable Proofs.

The PCP theorem is the grand-daddy of all modern zero-knowledge proof systems. With the subject of zero-knowledge and computational integrity proof systems currently undergoing a terrific explosion of work and interest, fueled in part by tantalizing applications in blockchain scalability and privacy, the good old PCP theorem deserves to be more widely known, as it hasn’t lost any of its shock value. In our last post, we talked about zero knowledge and computational integrity proof systems, complexity classes NP, PCP… just enough to make sense of the PCP Theorem and to convince the reader that such a result simply cannot be true!

And yet … In this second blog post on the subject, we dive into the proof of the weak form of this result, and show to the (hopefully) incredulous reader, that roughly 4800 randomly read bits, or 600 ascii characters, are enough to convince a verifier with confidence of any result, while rejecting invalid proofs with >50% certainty. Read more below.

PegaSys is a thought leader in the Enterprise Ethereum space. Want to join the team? Check out our list of open roles. 

To keep up to date on PegaSys’ progress, follow us on Twitter and sign up for our mailing list.