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

Reinforcement Learning

This post was authored by Vanessa Bridge, Research Engineer, at PegaSys.

Introduction

In this post we describe the use …

“Istanbul” & “Muir Glacier”: All You Need To Know About The Two Upcoming Ethereum Upgrades

Istanbul and Muir Glacier are the latest Ethereum Network Upgrades. …

DCO Sign-Offs: Committing Code to Hyperledger Besu

This article was written by Felipe Faraggi and originally posted on Kauri.

What is the DCO sign off?

This …