Laboratoire d'informatique de l'École polytechnique

From theory to practice, from the PCP theorem to proofs in blockchains

Speaker: Daniel Augot (Grace team)
Location: TBA
Date: Thu, 17 Nov 2022, 13:00-14:15

Languages of the NP complexity class have instances with a proof of membership which can be checked in polynomial time. What about reading only a random part of such a proof ?

The PCP (probabilistically checkable proofs) Theorem states that any language in NP has a verifier which checks a (PCP) proof of polynomial size, by reading only a constant number of random bits of it.

Originally an astronomical theorem, 30 years of research have turned this result into practical algorithms and protocols. Actually they are so practical that companies implement and deploy such proof systems very successfully in the blockchain world.

In this talk, the PCP theorem with be recalled. Then, the transition from complexity theory to cryptographic protocols is done with cryptographic hash functions. Central to this topic are error correcting codes. Finally, we will explain why such proofs are a useful for blockchains with low bandwidth.