Zero-knowledge proofs (or ZKP) are a class of cryptographic protocols for one party (the prover) to prove to another party (the verifier) that they know specific information, usually a value “x” or “secret”, without expressing any other information besides the fact they know the value. Zero-knowledge proofs are proofs that are both convincing, but do not yield anything beyond the validity of the assertion being proven.
Zero-knowledge proofs (or protocols) are important because they do not require the party to reveal extra key information or any other information in order to prove that they know a specific value. This security has made ZKPs important in cryptography, private information security, financial transactions and blockchain applications.
Zero-knowledge proof protocols originally required interactive input from the verifier and prover, whether that be a people or computers. These inputs are challenges to the verifier to prove they do in fact know the claimed knowledge, without actually revealing it.
Zero-knowledge protocols are probabilistic assessments, meaning they don’t prove with complete certainty. While zero-knowledge proofs can enable almost complete assuredness the prover knows the value, it is not a mathematical proof because of the small probability (the soundness error) that the cheating prover is able to convince the verifier of a false statement. An example of the soundness error would be if the prover was somehow able to guess the correct answer 1000 times in a row.
The generality of these methods are important, because almost all statements can in practice be encoded as claims concerning membership in languages in NP, the basis of cryptography.
Non-interactive zero-knowledge proofs were published in 2003 by Goldwasser and Yael Tauman Kalai. These non-interactive ZKPs do not require an interaction between the prover and verifier and are capable of impossibility results, but the validity relies on computational assumptions. Typical assumptions are reliant on assumptions of an ideal hash function or blockchain framework.
These proofs are used in many different industries, including but limited to cyber security, cryptography, commerce transactions and blockchain. Researchers have also looked to apply zero-knowledge proofs to digital identification mechanisms for e-voting.
General application uses for zero-knowledge proofs include but are not limited to minimum age verification in online transactions, anonymous credentials use, mortgage risk assessment, investment rating, e-voting and electronic auctions and procurement. All of these uses are also applicable in distributed ledger technology (DLT) and blockchain technology, with the rise of these technologies contributing to the increased research in zero-knowledge proofs.
Zero-knowledge proofs were first devised by MIT researchers Shafi Goldwasser, Silvio Mical and Charles Rackoff in a 1985 paper, “The Knowledge Complexity of Interactive Proof-Systems. The paper introduced key concepts including an interactive proof (IP) hierarchy and conceived the concept of knowledge complexity, a measure to see how much proof is transferred from the prover to the verifier. Perhaps most importantly, they gave the first zero-knowledge proof for a concrete problem when they demonstrated how to construct ZKPs for any NP-set, with any commitment scheme.
Two other researchers at the University of Chicago and Eötvös Loránd University in Budapest, László Babai and Shlomo Moran, also published a paper on the topic, “Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes,” in 1993. These two papers earned all five researchers the 1993 Gödel Prize, an annual award for outstanding papers in the area of theoretical computer science.
Feige, Lapidot and Shamir introduced the factor of witness indistinguishability in 1999, which added an important design technique for zero-knowledge proofs. Oded Goldreich has contributed knowledge and foundations to the study of sequention, parallel and concurrent composition of ZKPs at the Weizmann Institute of Science. Russell Impagliazzo and Moti Yung proved that assuming unbreakable encryption, that anything that can be proved by an interactive proof system can be proved with zero-knowledge.
zk-SNARK, a non-interactive zero-knowledge protocol was published in January 2012 by Nir Bitansky, Ran Canetti, Alessandro Chiesa and Erin Tromer. zk-SNARK provided the computational framework for the Zcash blockchain protocol, showing capabilities of combining ZKP protocols to cryptocurrency.
Bulletproofs were released in 2017 by Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poesltra, Peter Wuille and Greg Maxwell. The research proved that a committed value is in a range using a logarithmic number of field and group, increasing the security and efficiency of non-interactive zero-knowledge proofs.
zk-STARK protocol was introduced in 2018, proving a non-interactive ZKP that requires no trusted setup. The lack of a trusted setup eliminates the chance sources can work together to undermine protocol and access hidden information in the protocol. The release of zk-STARK made the technology more secure, scalable and useful for larger institutions interested in utilizing blockchain.
As cybersecurity, cryptocurrency and blockchain technology has advanced and entered mainstream markets and perception, zero-knowledge proof technology has become heavily funded and researched by state entities and global corporations. QED-IT announced its participation in a US government-funded research project with DARPA (Defense Advanced Research Projects Agency), receiving $2 million USD of the $12.6 million allocated to the project. QED-IT joined R&D specialist firm Galois in the initiative, Project Fromager, on September 16, 2020. Project Fromager is one of 12 projects to be funded through DARPA's Securing Information for Encrypted Verification and Evaluation (SIEVE) program, which aims to enable verification of security and defense capabilities without revealing sensitive information involved.
In order for a proof, problem or protocol to be a zero-knowledge proof it must satisfy three properties.
If the statement is true, the verifier must follow the protocol properly and accept the fact as true.
If the statement is false, no cheating prover can convince the verifier that it is true, with the exception of a small probability outlined in the protocol.
If the statement is true, the verifier does not learn anything other than the fact the statement is true. The prover knowing the value must be sufficient to show the prover knows the secret.
A common way of explaining zero-knowledge proofs is The Ali Baba cave, first published by Jean-Jacques Quisquater in a paper, “How to Explain Zero-Knowledge Protocols to Your Children.” One child, usually called Peggy (for Prover), finds a cave with two tunnels (A and B) leading to a magic door which connects the two sides of the tunnels and is unlocked only by codeword. Peggy tells Victor (for Verifier) she knows the magic word, but won’t tell him what it is.
Victor wants to see if she really does know the word, so tells Peggy to go into the cave without him seeing. When she gets to the door, he yells inside which tunnel he wants her to return by. If she does in fact know the word, she could open the door and return by whichever tunnel he instructed. If Peggy does not know the word, she could only return by the tunnel she originally chose.
Although Victor does not know which tunnel Peggy originally chose, if she returns down the wrong tunnel he will know she does not know the value or “secret” to the door. If she does return down the right tunnel, either she knows the codeword if truthful, or a 50% chance it was by chance. It is up to him to either believe or not believe she is telling the truth, but the two could repeat this experiment until Victor believes her.
It is not possible for Peggy to 100% prove she knows the word without saying the magic codeword in front of Victor, but if she repeatedly comes back down the correct tunnel, the chances she does would become increasingly probable (and her chance of lying would get closer to zero).
Zero-knowledge proofs are used in multiple industries and services, mostly alongside blockchain technology in cryptography, cryptocurrency, identity authorization and financial.
The invention and adoption of cryptocurrency has revolutionized transactions in the modern age, enabling transparent, independent and decentralized financial movement. Although this transparency is optimal for auditing and tracking, it doesn't lend itself to sensitive transaction information like an employee's paycheck, the price a manufacturing company pays for its raw materials or the cost of a recent medical procedure. Cryptocurrency companies research and utilize zero-knowledge proof concepts to encrypt and limit certain information on the blockchain.
Cryptology and cybersecurity were the first to use zero-knowledge proof and protocols, conceiving ZKPs and utilizing them to secure privileged information. While original zero-knowledge proofs required interactive input and a trusted setup, new technology has reduced the chance for leaked data and excess information exchange.
Identity authentication and management are a focus for zero-knowledge proof technology, due to their ability to limit private information between sources. Companies apply ZKPs to new and existing privacy frameworks to ensure authorization while still keeping anonymity for users and a safeguard for sensitive information.
Companies using zero-knowledge proofs in financial transactions and accounting
Financial institutions, enterprises and investors struggle to adopt blockchain in its basic format, due to the public and transparent nature of the technology. As a result, research and integration of ZKP frameworks industry leaders focus is aimed at finding secure and scalable solutions for confidential transaction and accounting data.
Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes
László Babai, Shlomo Moran
August 3, 1987
Bulletproofs: Short Proofs for Confidential Transactions and More
Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille and Greg Maxwell
November 1, 2017
Foundations of Cryptography: Basic Tools
Homepage | ZKProof Standards
How to Explain Zero-Knowledge Protocols to Your Children
Jean-Jacques Quisquater, Muriel Myziam, Louis Michael Guillou, Annick Marie, Anna Gaid, Soazig Gwenole, Tom Berson
ING Bank Is Bringing Bitcoin 'Bulletproofs' to Private Blockchains - CoinDesk
April 15, 2019
Introduction to zk-SNARKS | ConsenSys
March 27, 2017
Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions
Uriel Feige, Dror Lapidot, Adi Shamir
QEDIT Joins Forces with Galois as Part of US Government-Funded Initiative to Advance Zero-Knowledge Proof Cryptography
September 16, 2020
The Knowledge Complexity of Interactive Proof Systems
Shafi Goldwasser, Silvio Micali, Charles Rackoff
Zero-Knowledge twenty years after its invention
December 3, 2002
Documentaries, videos and podcasts
- BlockchainA blockchain is an append-only digital ledger storing a set of time-ordered transactions grouped in blocks that are linked together using cryptographic hashes.
- ZcashZcash is a cryptocurrency utilizing zero-knowledge proof cryptography to protect the privacy of transactions.
- EthereumEthereum is an open-source, public, distributed blockchain computing platform featuring smart contract (scripting) functionality, which facilitates online contractual agreements.