Zero-Knowledge Proof

What Is a Zero-Knowledge Proof

A zero-knowledge proof (ZKP) is a cryptographic method that allows one party to prove that a statement is true without revealing any information about the statement itself. It was proposed in 1985 by three researchers: Goldwasser, Micali, and Rackoff.

To illustrate with an everyday example, suppose you want to prove that you know the combination to a safe. Normally, you would tell the other person the combination and open the safe. With a zero-knowledge proof, you can prove the fact that you know the combination without revealing the combination itself.

This technology is a key concept in modern cryptography alongside end-to-end encryption and public-key cryptography, and is applied in a wide range of fields including privacy protection, authentication, and blockchain scalability.

The Three Properties of Zero-Knowledge Proofs

For a zero-knowledge proof to hold, it must satisfy the following three properties.

• Completeness: If the prover truly knows the secret, the verifier will always determine the statement to be true. An honest prover is never unfairly rejected.
• Soundness: If the prover does not know the secret, they cannot (except with negligibly small probability) trick the verifier into accepting the statement as true. The probability of a dishonest prover passing verification is negligibly small.
• Zero-Knowledge: During the verification process, the verifier learns nothing beyond the fact that the statement is true. Even recording the entire exchange yields no clues about the secret.

The Cave Analogy (Ali Baba's Cave)

The "Ali Baba's Cave" analogy is famous for building intuitive understanding of zero-knowledge proofs. A circular cave has two entrances, A and B, connected at the back by a magic door. The prover wants to prove they know the spell to open the door. The verifier asks the prover to enter the cave and then randomly instructs them to "come out from A" or "come out from B." If the prover knows the spell, they can always exit from the specified entrance, but without it, they succeed only 50% of the time. Repeating this 20 times reduces the probability of success by chance to less than one in a million.

Types and Technologies of Zero-Knowledge Proofs

• Interactive Zero-Knowledge Proofs: A scheme where the prover and verifier exchange messages in real time. The cave analogy above corresponds to this type. The verifier sends random challenges and the prover responds. Since interaction is required for each verification, efficiency is low.
• Non-Interactive Zero-Knowledge Proofs (NIZK): A scheme where the prover generates a proof once, and the verifier can verify it later. Since no interaction is needed, it is suitable for offline verification such as on blockchains. The Fiat-Shamir transform can convert an interactive proof into a non-interactive one.
• zk-SNARK: Stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. Proof size is small (a few hundred bytes) and verification is fast (a few milliseconds). Adopted by Zcash, it can verify transaction validity while keeping the sender, recipient, and amount private. However, it requires an initial Trusted Setup, and if this setup is compromised, forged proofs can be created.
• zk-STARK: An improved version of zk-SNARK that does not require a Trusted Setup. Proof size is larger than zk-SNARK, but it is resistant to quantum computers. Developed by StarkWare and adopted in Ethereum's scalability solution (StarkNet).

Applications and Future of Zero-Knowledge Proofs

Zero-knowledge proofs are not just a theoretical cryptographic concept - they are widely used in practical systems.

• Privacy-Preserving Authentication: In age verification scenarios, proving only that you are "18 or older" without revealing your date of birth. As a future extension of passkeys, zero-knowledge proofs may be incorporated into attribute-based authentication.
• Blockchain Scalability: In Ethereum's Layer 2 solutions (zk-Rollups), thousands of transactions are bundled into a single zero-knowledge proof and recorded on the main chain. This verifies validity without publishing transaction details, improving both throughput and privacy.
• Zero-Knowledge Encryption for Cloud Storage: Services like Tresorit and Proton Drive advertise "zero-knowledge encryption," adopting a design where the provider cannot view user data at all. Strictly speaking, this is client-side encryption rather than a zero-knowledge proof per se, but it embodies the zero-knowledge philosophy in the sense that the provider knows nothing about the data.
• Combination with Data Encryption: Research is advancing on combining homomorphic encryption - which performs computations on encrypted data without decryption - with zero-knowledge proofs, enabling data processing while fully preserving privacy.

Zero-knowledge proofs once faced the challenge of high computational cost, but advances in hardware and improvements in proof algorithms have led to an increasing number of systems that operate at practical speeds. As a technology that reconciles privacy and security, its importance will only grow.

To learn more about this topic, see Cloud Storage Security: How to Keep Your Data Safe in the Cloud.

Common Misconceptions

Zero-knowledge proofs are a theoretical concept that has not been put into practical use

Zero-knowledge proofs are already running in many practical systems, including Zcash (cryptocurrency), StarkNet (Ethereum Layer 2), and Proton Drive (cloud storage). In the blockchain space in particular, zk-Rollups have been adopted as a major scalability solution.

Zero-knowledge proofs can completely conceal any data

Zero-knowledge proofs are a technique for proving that a statement is true without revealing the secret, which is different from encryption that aims to conceal data itself. Additionally, generating proofs incurs computational costs, and the technique is not applicable to every use case.

Comparison of zk-SNARK and zk-STARK

Related Terms

Related Articles