In our section on scalability later in the course, we will discuss Zero-Knowledge Proof rollups, but we won't go into detail about what ZKPs are. In this section, we'll discuss the basics of ZKPs and compare two common implementations of ZKPs you'll see in blockchain.
Zero-Knowledge Proofs have been researched since the 1980s—the initial researchers of ZKPs received the Turing Award,{target=_blank} the highest award in computer science, for their work. Their development stems from the field of computational complexity and, while most of the work of ZKPs is very technical, we'll try to provide a broad overview.
The goal of zero-knowledge proofs (ZKPs) is for a verifier to be able to convince themselves that a prover possesses knowledge of a secret parameter, called a witness, satisfying some relation, without revealing the witness to the verifier or anyone else. Zero-knowledge proofs are currently being researched as solutions to two main issues in public blockchains:
-
Privacy: All essential information within a blockchain network must be public. ZKPs allow users to verify / prove certain elements of information (such as the answer to a crossword puzzle) while not revealing the information itself (to not give the answer to someone else). Certain tools, such as AZTEC, promise to use ZKPs to provide channels which shield the entire nature of certain transactions from the public blockchain while still using the public blockchain's security promises.
-
Scalability: As blockchain networks grow, the amount of data they require to be maintained grows as well. ZKPs compress large amounts of data into compact, verifiable proofs, a characteristic scalability researchers hope to use to dramatically reduce the data required to maintain security on a public blockchain.From ZCash:{target=_blank}“Succinct” zero-knowledge proofs (SNARKs, STARKs) can be verified within a few milliseconds, with a proof length of only a few hundred bytes even for statements about programs that are very large.
A common way Zero-Knowledge Proofs are used in blockchain is as follows. A Verifier will take the piece of data to be verified and put it through a private process (ZK-SNARK or STARK, for example) which produces a program called a Proof Circuit. This Proof Circuit can then be posted openly (such as in a Smart Contract) as it reveals no meaningful information about the nature of the data it represents. A Prover can then use the Proof Circuit to irrefutably prove they know the piece of data by publicly "solving" the Proof Circuit, a process that also reveals nothing about the nature of the data.
The Ethereum Foundation described the impact of this privacy would have on a blockchain:
Imagine, for example, an election or auction conducted on the blockchain via a smart contract such that the results can be verified by any observer of the blockchain, but the individual votes or bids are not revealed. Another possible scenario may involve selective disclosure where users would have the ability to prove they are in a certain city without disclosing their exact location. (source{target=_blank})
Succinct Non-Interactive ARgument of Knowledge, or SNARKs, were first widely implemented on a blockchain by ZCash,{target=_blank} a fork of Bitcoin. Ethereum introduced SNARK capacity with the Byzantium fork by including precompiled contracts{target=_blank} that allowed efficient SNARK verification on-chain. SNARKs are being discussed in terms of privacy (as in ZCash) and scalability (as in SNARK roll-ups{target=_blank})
Pros:
- Small, constant proof size
- Constant-time verification costs (source{target=_blank})
Cons:
- Trusted setup required (see ZCash parameter generation ceremony{target=_blank})
- Relies on Elliptic Curve Cryptography, which is not quantum-resistant
Scalable and Transparent ARgument of Knowledge, or STARKs, share a similar fundamental ideas with SNARKs but differ in execution. Their development and advocacy is done chiefly by STARKware, a private company led by Eli Ben Sasson, with assistance from the Ethereum Foundation.
Pros:
- No trusted setup required
- Faster proving time relative to SNARKs (source{target=_blank})
Cons:
- STARKs have a larger proof size than SNARKs
- As of June 2019, STARKs still in development
- "Hello World" of zk-SNARKS with Zokrates{target=_blank}
- Creating a zk-SNARKS version of "Mastermind" in the Browser — Koh Wei Jie{target=_blank}
- GitHub Repo for Creating a zk-SNARKS version of "Mastermind" in the Browser{target=_blank}
- Developing Confidential Tokens on AZTEC(requires access to Rinkeby Testnet){target=_blank}
- Docs: Cairo — a Turing-complete STARK generation Cairo, Starkware's ZKP language, has a great doc repository here, including a great introductory tutorial.
- Reddit Scaling Bake-Off ZKP Submissions: STARKWare{target=_blank}, Fuel Labs{target=_blank}, AZTEC{target=_blank}
- Article: NYTimes 1987 article discussing the discovery of ZK Proofs{target=_blank}
- Article: Why and How zk-SNARK Works{target=_blank}
- Article: Introduction to zk-SNARKS with Examples{target=_blank}
- Wiki: Zero Knowledge Starter Pack (S[NT]ARK focused){target=_blank}
- Wiki: Zero Knowledge Proof Science Resources{target=_blank}
- Article: Not-so-gentle Introduction to the PCP Theorem{target=_blank} (PCP Theorem underpins many ZKPs)
- Series: The Math behind STARKs{target=_blank} (abstract but still technical)
- Article: An Approximate Introduction to how zk-SNARKs are possible{target=_blank}
- Video: Vitalik Buterin: Scalable Blockchains as Data Layers{target=_blank}