Zero-knowledge proofs

Prove that a statement is true without revealing why it is true

In cryptography, a zero-knowledge proof (ZKP for short) is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true.

The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information.

Types of zero-knowledge proofs

Interactive zero-knowledge proofs require interaction between the individual (or computer system) proving their knowledge and the individual validating the proof.

Interactive zero-knowledge proofs first appeared in a 1985 paper "The knowledge complexity of interactive proof systems" by Shafi Goldwasser, Silvio Micali, and Charles Rackoff.

To achieve zero knowledge, Goldwasser et al. extended the traditional notion of a proof from a static text to a protocol, which involves randomization and interaction between the prover and verifier.

At the end of the protocol, the verifier has a high degree of confidence that the statement is correct, while the prover is guaranteed that the verifier did not learn anything about the data underlying the truth of the statement.

Two abstract examples to interactive ZKPs are:

1. The Ali Baba cave

2. Two balls and the colour-blind friend

While revolutionary, interactive proving had limited usefulness since it required the two parties to be available and interact repeatedly. Even if a verifier was convinced of a prover’s honesty, the proof would be unavailable for independent verification (computing a new proof required a new set of messages between the prover and verifier).

Non-interactive zero-knowledge proofs solve the problem by allowing the prover and verifier to share a common, short, random string (a shared secret key) that is used to generate and verify proofs.

Unlike interactive proofs, non-interactive proofs required only one round of communication between participants (prover and verifier). Non-interactive proving reduces communication between prover and verifier, making zero-knowledge proofs more efficient. Moreover, once a proof is generated, it is available for anyone else (with access to the shared key and verification algorithm) to verify.

This makes non-interactive zero-knowledge proofs particularly useful in decentralized systems like blockchains, where transactions are verified by a network of nodes and there is no central authority to oversee the verification process.

Zero-knowledge non-interactive proving systems

There are currently two mains systems implementing non-interactive ZKPs:

1. ZK-SNARK (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge). Here succinct means that the zero-knowledge proof is smaller than the witness (the secret to prove). The shared key mentioned earlier refers to public parameters that the prover and verifier agree to use in generating and verifying proofs. Generating the public parameters is a sensitive operation because of its importance in the protocol’s security. Multi-party computation is a way of reducing the risks in generating public parameters: multiple parties participate in a trusted setup ceremony, where each person contributes some random values to generate the shared key.

2. ZK-STARK (Zero-Knowledge Scalable Transparent ARgument of Knowledge). ZK-STARK is faster than ZK-SNARK at generating and verifying proofs (scalability). Moreover, it relies on publicly verifiable randomness to generate public parameters for proving and verification instead of a trusted setup (transparency). On the other hand, ZK-STARKs produce larger proofs than ZK-SNARKs meaning they generally have higher verification overheads.

Use-cases for zero-knowledge proofs

1. Identity protection. Current identity management systems put personal information at risk. Zero-knowledge proofs can help individuals validate identity whilst protecting sensitive details. Zero-knowledge proofs are particularly useful in the context of decentralized identity. It gives the individual the ability to control access to personal identifiers. Proving your citizenship without revealing your passport details is a good example of how zero-knowledge technology enables decentralized identity. This might be used also to improve the experience of authentication on online systems both for the user and the online system.

2. Verifiable computation. Verifiable computing allows to outsource computation to another entity while maintaining verifiable results. The entity submits the result along with a proof verifying that the program was executed correctly. Verifiable computation is critical to improving processing speeds (scalability) on blockchains without reducing security. For instance, in zero-knowledge rollups on Ethereum, when a node executes a transaction outside of Ethereum, it submits a zero-knowledge proof to prove the correctness of off-chain execution. This validity proof guarantees that a transaction is valid, allowing Ethereum to apply the result to its state without waiting for anyone to dispute it.

3. Reducing bribery and collusion in on-chain voting. Solutions such as MACI (Minimum Anti-Collusion Infrastructure), originally proposed by Vitalik Buterin, are using zero-knowledge proofs to make on-chain voting (eg., quadratic funding mechanisms) resistant to bribery and collusion. MACI is a set of smart contracts and scripts that allow a central administrator to aggregate votes and tally results without revealing specifics on how each individual voted. Even so, it is still possible to verify that the votes were counted properly, or confirm that a particular individual participated in the voting round.

4. Anonymous payments. There are specific privacy coins designed for completely anonymous transactions. Privacy-focused blockchains, such as Zcash and Monero, shield transaction details, including sender/receiver addresses, asset type, quantity, and the transaction timeline. By baking in zero-knowledge technology into the protocol, privacy-focused blockchain networks allow nodes to validate transactions without needing to access transaction data.

5. Blockchain privacy and regulatory compliance. In many cases, privacy and regulatory compliance are perceived as incompatible. This does not necessarily have to be the case, if the privacy-enhancing protocol enables its users to prove certain properties regarding the origin of their funds. For instance, suppose users can demonstrate that their funds have no ties to deposits from known illicit sources, or prove that the funds are part of a specific set of deposits, without revealing any further information.The core idea is to allow users to publish a zero-knowledge proof, demonstrating that their funds (do not) originate from known (un-)lawful sources, without publicly revealing their entire transaction graph. The idea has been proposed in this research paper.

6. Nuclear disarmament. In 2014, researchers from Princeton University and Microsoft Research demonstrated a technique that may have applicability to future nuclear disarmament talks. It would allow inspectors to confirm whether or not an object is indeed a nuclear weapon without recording, sharing or revealing the internal workings which might be secret.

Drawbacks of using zero-knowledge proofs

1. Hardware costs. Generating and verifying zero-knowledge proofs involves very complex calculations best performed on specialized machines. As these machines are expensive, they are often out of the reach of regular individuals. Additionally, applications that want to use zero-knowledge technology must factor in hardware costs—which may increase costs for end-users.

2. Trust assumptions. In ZK-SNARK, the public parameters (shared secret key) is generated once and available for re-use to parties who wish to participate in the zero-knowledge protocol. Public parameters are created via a trusted setup ceremony, where participants are assumed to be honest. But there’s really no way for users to assess the honesty of participants and users have to take developers at their word. ZK-STARKs are free from trust assumptions since the randomness used in generating the string is publicly verifiable.

3. Quantum computing threats. ZK-SNARK uses elliptic curve cryptography for encryption. While the ECDSA algorithm is secure for now, the development of quantum computers could break its security model in the future. ZK-STARK is considered less immune to the threat of quantum computing, as it uses collision-resistant hashes for encryption, which is more difficult for quantum computing algorithms to break.