Join our upcoming webinar 'PegaSys Plus: Ensure Your Blockchain Solution is Production Ready' - November 6, 2019 at 2PM ET

October 7, 2019

A Gentle Introduction to the PCP Theorem – Part 2

by, Gina Rubino

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.

Recent Posts

Increasing Security with Blockchain Database Encryption

Worldwide Information security is expected to reach $124 billion in 2019. …

PegaSys Protocol Engineering – September 2019 Update

A month full of big events, a major milestone accomplished in Eth2, the official Hyperledger Besu migration, plus a …

How PegaSys Plus Will Help Enterprises Take Their Blockchain from PoC to Production

From the team that developed Hyperledger Besu, here are 3 key questions enterprises must consider for blockchain success using …