Join our upcoming webinar 'Learn how to Leverage Plugin APIs on Hyperledger Besu' - February 4, 2020 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

Introducing Plugin APIs in Hyperledger Besu

As part of its 1.4 release (set for February 26), Hyperledger Besu will expose a Plugin API. …

PegaSys in 2020

2019 has come to an end, and we’re already a week into 2020. …

PegaSys 2019 in Review

As the year comes to an end, we can’t help but to reflect on the past 365 days. …