Computer Sciences Colloquium - PCPs, zk-STARKs and crypto-currency privacy and scalability

Abstract: 

Bitcoin and other decentralized crypto-currencies establish computational integrity by sharing all information among all nodes participating in the network. This approach (i) compromises privacy and (ii) limits scalability. Probabilistically Checkable Proofs (PCPs) and Interactive Oracle Proofs (IOPs) can be used to address both problems.

In the first part of this talk I will discuss Bitcoin, Ethereum and Zcash, and explain how PCPs and related proof systems can be used to improve privacy and scalability. 

The second will focus on a construction of a proximity test for the Reed Solomon code with strictly linear prover arithmetic complexity and strictly logarithmic verifier arithmetic complexity, called the Fast RS IOP of proximity (FRI). This protocol is used in our recent construction of a zero knowledge scalable transparent argument of knowledge (zk-STARK). 

Joint work with Iddo Bentov, Yinon Horesh and Michael Riabzev.