An interactive proof system is a protocol between a prover and a verifier (both computer programs), whereby the prover attempts to convince the verifier of some fact and the verifier tries to expose any fraud on the part of the prover. The claim that is being proven can be any mathematical statement. However, proof systems become particularly compelling when the prover is allowed resources that the verifier does not have access to.
When this special resource is secret information (that should stay secret), it is a zero-knowledge proof system. The statement could be something like
- I know the private key that matches this public key.
- My account balance is a number between 0 and 1 000 000.
- I have the income stream necessary to justify taking this loan.
- The fingerprints of this newly elected politician to not appear in this database fingerprints of known criminals.
The important thing is that the zero-knowledge verifier ascertains the truth of these statements without obtaining any information about why they are true. As a result, zero-knowledge proofs are the perfect tool for privacy-preserving protocols.
When this special resource is computational power, it is a proof system with succinct verification, and such proof systems are typically called SNARKs (Succinct Non-Interactive ARgument of Knowledge). The statement could be any computationally intensive task and the point is that the verifier should achieve the same assurance that this task was done in much less time than it takes to do it themself. For instance:
- I have verified the entire history of the blockchain going back to the genesis block, and the current state is this.
- I have verified that these transactions all have valid signatures.
- I have executed the program whose hash is this, on this input, and the output is that.
Due to their capacity to reduce the workload of network verifiers, as well as their bandwidth requirement, SNARKs are the natural tool for scaling decentralized systems.
Zero-knowledge proofs and SNARKs excel in protocols where the participants distrust each other. Otherwise, why verify anything at all? It just so happens that public cryptocurrencies fit this description perfectly: you do not know who you are connecting with and there is a monetary reward for fraud.
Proof systems and public cryptocurrencies are a match made in heaven. Zero-knowledge proofs and SNARKs promise to address two of the most challenging aspects of cryptocurrencies: privacy and scalability — without detracting from their unpermissioned and decentralized nature.
- https://zkp.science/ — lots of resources and references
- https://zeroknowledge.fm/ — tune in to the Zero Knowledge Podcast
- https://zkproofs.org/ — standardization effort, also very good systematization of knowledge
- https://nakamoto.com/cambrian-explosion-of-crypto-proofs/ — survey of recent proof systems by a leading researcher in the field