Zero-knowledge proof

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 refers to the cryptographic method of developing a zero-knowledge proof to maintain and protect specific knowledge, whereas zero trust is a general cybersecurity model used to protect data, premises, and related resources. In a zero-trust framework, it is assumed that every person and device, whether internal or external to a network, could be a threat. To mitigate the threat, a zero-trust system requires users and devices to be authenticated, authorized, and continuously validated in order to access resources. A zero-knowledge proof can be integrated into a zero-trust framework, such as a zero-knowledge proof for employee access, granting the employee access without revealing personal details.

Zero-knowledge proof protocols are split into two basic forms: interactive and non-interactive. Interactive proving requires input from the verifier and prover, whether that be people or computers. But in the case of non-interactive zero-knowledge proofs, the verifier and prover have a shared key. This allows the prover to demonstrate to the verifier that they do, in fact, know the claimed knowledge, without actually revealing it.

In any basic form, a zero-knowledge proof is made of three elements: witness, challenge, and response. This is intended to verify the validity of the statement and requires a back-and-forth between the prover and the verifier. The "interactive" proof describes the communication required to move the possibility of a prover guessing at knowledge to as close to zero as possible, but it can take a while to achieve that level of confidence and can be computationally intense.

With a zero-knowledge proof, a prover wants to show they have some kind of knowledge (or any other hidden quantity) without revealing that information. This secret information is the "witness" to the proof, and the prover's assumed knowledge of the witness establishes the questions that can be answered by a party of the information. This means the prover begins the proving process by calculating the answer to a randomly selected problem and sending it to the verifier.

The challenge is the randomly selected problem the verifier picks from a set and asks the prover to answer it. The answer to the question is considered the proving process and should in some way address the hidden information in order to demonstrate the prover's knowledge.

The prover has to accept the question and return the answer, once calculated, to the verifier. The answer, as calculated by the prover, allows the verifier to check if the former has access to the witness. To better ensure the prover is not blindly lucky, the verifier will pick more questions for the prover to answer and further prove their access to the witness. This is intended to move the chance of the prover guessing correctly to as close to zero as possible, or until the verifier is satisfied.

There are some limitations with interactive zero-knowledge proofs. They offer limited transferability, with the entire proofing process required to be repeated several times, taking both time and computational power. This also makes interactive zero-knowledge proofs unscalable, as for the prover and verifier to go through the proofing process, they are required to be online at the same time for the entire process. This led to the development of a separate type of zero-knowledge proof.

Interactive proofing, as noted above, has limitations that restrict the potential for full-scale adoption, and even once a verifier of an interactive proof is convinced of a prover's honesty, the proof is unavailable for independent verification (which, in the case where one is required, would need a new set of proofing). This problem was solved by non-interactive zero-knowledge proofs, first suggested by Manuel Blum, Paul Feldman, and Silvio Micali. Their suggestion was that the verifier and prover would have a shared key. This would allow the prover to demonstrate their knowledge of the information (witness) without providing that information itself.

In this schema, the non-interactive proof required only one round of communication between prover and verifier in which the prover passes the secret information to an algorithm that computes the zero-knowledge proof. This proof is sent to the verifier, who checks the proof using another algorithm to check the prover knows the witness. The public parameters of non-interactive zero-knowledge proofs known as Common Reference String (CRS) are sensitive, as these are the shared keys between verifiers and provers and are important to the protocol's security. If the randomness or entropy used to generate the CRS is acquired by a dishonest prover, they can compute the false proofs.

This reduces the communication between prover and verifier, makes zero-knowledge proofs more efficient, and once the proof is generated, it can be made available for anyone (with access to the shared key and verification algorithm) to further verify its correctness. Non-interactive proofs spurred further developments into proving systems with greater utility.

There are several types of zero-knowledge proofs—which build on the basic forms of either interactive or non-interactive zero-knowledge proofs—that have been developed and adopted by different entities to better integrate zero-knowledge proofs into various products and services. These include the following:

Zk-SNARK is an acronym for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. This is developed to offer users a set of qualities:

• Zero-knowledge: a verifier can validate the integrity of a statement without knowing anything about the statement, meaning the verifier only has knowledge of whether the statement is true or false.
• Succinct: the zero-knowledge proof is smaller than the witness to allow it to be verified quickly.
• Non-interactive: the proof is "non-interactive," as the prover and verifier only interact once.
• Argument: the proof satisfies the "soundness" requirement of zero-knowledge proofs, meaning the chance of cheating is as close to zero as possible.
• (Of) knowledge: the zero-knowledge proof cannot be constructed without access to the witness; therefore, it is nearly impossible for a prover without the witness to compute a valid proof.

Zk-SNARKs work to reduce the risks of generating public Common Reference Strings (CRS) by using multi-part computation (MPC). Multiple parties participate in a trusted setup ceremony, where each participant contributes some random values to generate the CRS. In this case, it takes one honest party to destroy their portion of the CRS, the zk-SNARK retains computational soundness, while reducing the chance of dishonest provers' capability to provide the proof. However, it still requires a trusted setup, which requires users to trust participants in parameter-generation, which offers a potential for dishonesty.

This need for a trusted setup led to the development of zk-STARKs, which used much of the undergirding of the zk-SNARK but developed a non-trusted, or trustless, setup. Zk-STARK is an acronym for Zero-Knowledge Scalable Transparent Argument of Knowledge. This means they are similar to zk-SNARKs, except they work to be:

• Scalable: zk-STARKs are faster than zk-SNARKs at generating and validating proofs when the size of the witness is larger. With STARK proofs, the prover and verifier only slightly increase as the witness grows, where in a SNARK proof, the prover and verifier increase linearly with witness size.
• Transparent: zk-STARKs rely on publicly verifiable randomness to generate public parameters to prove and verify instead of a trusted setup, and therefore, they are more transparent than zk-SNARKs.

These parameters limit some of the use cases for zk-STARKs, but in the case of proving large datasets, the zk-STARK has proven more efficient and cost-effective than zk-SNARKs.

PLONK stands for Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge. The PLONK uses a universal trusted setup that can be used with any program and can include a large number of participants. Where the STARKs are considered the safest algorithms, while SNARKs has one of the smallest proof sizes, the PLONK is designed to be a balance between the SNARK and the STARK in regards to security and proof size.

Bulletproofs are short non-interactive zero-knowledge proofs that do not require a trusted setup and are designed to enable private transactions for cryptocurrencies. However, Bulletproofs are more time consuming in their verification than a zk-SNARK proof. And while Bulletproofs were designed for confidential transactions, they have other applications in cryptographic protocols, such as shortening proofs of solvency, short verifiable shuffles, confidential smart contracts, and as a general drop-in replacement for Sigma-protocols.

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 is 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. All zero-knowledge proofs have three fundamental characteristics that any proof, problem, or protocol has to satisfy:

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.

The primary benefit of zero-knowledge proofs is the ability to maintain privacy for individuals or datasets while maintaining the transparency of a system and the decentralization of a system. Further, they allow more users to engage with blockchain networks without putting their datasets at risk. For example, while a blockchain like Ethereum is intended to be highly transparent and allows users and businesses to download data stored on their ledger, using zero-knowledge proofs allows users and businesses to use their private datasets in the execution of smart contracts on a blockchain network without revealing the underlying data, thus ensuring both transparency and privacy where necessary.

This makes the blockchain networks more useful for companies, which often are required to safeguard their client's personally identifiable information (PII) and comply with various regulations, such as the General Data Protection Regulation (GDPR) of the European Union.

Generating zero-knowledge proofs involves the use of complex calculations, which are performed best on specialized machines. And, as they are specialized machines, they are often expensive and therefore out of reach of many individuals. Additionally, any application that wants to use zero-knowledge technology has to factor hardware costs into the overall application costs and therefore can increase costs for end-users.

Verifying proofs, as noted above, includes complex computations, which increases the cost of implementing the proofs in applications. In blockchain networks, the increased costs of these computations while performing a transaction on the network can increase the network fees overall.

As noted above, in some zero-knowledge proofs, there is an inherent trust in regard to the parties involved. The trust tends to focus on the development of the Common Reference String (CRS), which is the public parameter for generating the proof. The ceremony for generating the CRS is a trusted setup, in which participants have to be trusted as there is no way for users to assess the honesty of participants. There are trust-free zero-knowledge proofs, which can work around this drawback.

Zero-knowledge proofs use complex cryptographic algorithms for encryption. And while these algorithms tend to be secure, the potential development of quantum computing and the raw computational power quantum computing is expected to have could break these cryptographic models in the future. Therefore, zero-knowledge proofs are not considered immune to quantum computing. Zk-STARK is considered the most immune to quantum computing, as it uses collision-resistant hashes for encryption which are more difficult for quantum computing to break.

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 of 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, 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 have 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 twelve projects to be funded through DARPA's Securing Information for Encrypted Verification and Evaluation (SIEVE) program, which aims to enable the verification of security and defense capabilities without revealing sensitive information involved.

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 that connects the two sides of the tunnels and is unlocked only by a code word. Peggy tells Victor (for Verifier) she knows the magic word, but won’t tell him what it is.

Peggy (or Prover) randomly takes path A or B, unseen.

Victor (or Verifier) chooses an exit path.

Peggy appears down the path Victor had named.

Victor wants to see if she really does know the word, so he 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 there is 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 industries.

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 of 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.

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.