This article will provide an overview of zero-knowledge proofs (ZKP), their working principles, and their potential applications. We will also discuss why ZKP is considered a marvel in cryptography.
Zero-knowledge proofs (ZKP) are cryptographic protocols where one party (the prover) can demonstrate the knowledge of a statement to another party (the verifier) without revealing any additional information.
A person who wants to prove the existence of something without revealing any other information.
A party that wants to verify the existence of the claimed object without gaining any additional knowledge.
The proof of the claimed object's existence, which the prover possesses and wants to demonstrate without revealing it.
Suppose Alice and Bob are racing to find Waldo in a popular "Where's Waldo" book. Alice claims she knows where Waldo is, and Bob challenges her to prove it without revealing his location.
Alice takes a large, opaque sheet of cardboard and cuts out a Waldo-shaped hole, leaving only Waldo visible.
She places the cardboard cutout on top of the original scene, so only Waldo is shown, and his coordinates relative to the rest of the scene remain unknown.
Bob, the verifier, exits the room, leaving only the Waldo page and the black cutout paper.
Alice reproduces the scene underneath the cutout to prove that she used the original puzzle, without revealing Waldo's location.
Satisfied with the proof, Bob concludes that Alice indeed knows where Waldo is, even though he hasn't learned Waldo's exact location.
In this analogy:
The "Where's Waldo" book represents the ZKP system, where the prover and verifier interact.
The original scene with Waldo hidden in it represents the witness, which the prover wants to prove knowledge of without revealing its details.
Alice's actions with the cardboard cutout represent the ZKP, where she provides convincing evidence of her knowledge of Waldo's location without explicitly revealing it.
A zero-knowledge proof system must satisfy three properties:
Completeness: Every true statement has a valid and convincing proof. If the statement is true, an honest verifier will be convinced by an honest prover.
Soundness: Invalid/false statements do not have valid and convincing proofs. If the statement is false, no dishonest prover can convince the honest verifier.
Zero-Knowledge: If the statement is true, no verifier learns anything other than the fact that the statement is true
Interactive proofs involve a direct “conversation” between a prover and a verifier. The prover wants to prove to the verifier that they know some secret without revealing it. The parties engage in multiple rounds of communication, with the former providing carefully crafted responses to challenges from the latter. If the prover can correctly respond to the challenges, the verifier is convinced of the former’s knowledge while learning nothing else.
As the name suggests, non-interactive proofs do not require interaction between the prover and verifier. Rather, the prover constructs a single proof that convinces the verifier of their knowledge.
Interactive Zero Knowledge Proofs (iZKPs): iZKPs are highly flexible and secure, but they can be time-consuming and require a high level of trust between the parties involved. They are suitable for situations where real-time interaction is possible and where a higher level of security is required.
Non-Interactive Zero Knowledge Proofs (niZKPs): niZKPs are more efficient and scalable, but they may be less flexible and require a higher level of initial setup and trust. They are suitable for situations where real-time interaction is not possible, such as online transactions, and where a lower level of security is acceptable.
As you probably deduced from the names below, cryptographers aren’t known for their brevity. Hence, we abbreviate “zero-knowledge” with “ZK.” You’re welcome.
This list is not exhaustive by any means, but here are some popular systems in use today:
ZK Succinct Non-Interactive Argument of Knowledge (ZK-SNARK)
ZK Scalable Transparent Argument of Knowledge (ZK-STARK)
ZK Succinct Non-interactive Oecumenical Argument of Knowledge (ZK-SNORK)
Bulletproof
Each proving system is optimized for specific use cases; hence, there are obvious trade-offs as shown above.
Zero-knowledge proofs often require an initial "setup" phase before the proof can be conducted.
A trusted setup refers to when the initial parameters for a zero-knowledge proof are generated by a centralized, trusted party. This party is trusted to properly generate and distribute the parameters. All proof participants must trust that the setup was done correctly since the security relies entirely on the trusted party.
Do you have trust issues? Don’t worry, it’s quite common around here. Welcome to the club.
A trustless setup removes the need for a trusted central party. Instead, the setup is done in a decentralized way. For example, parameters may be generated through a multi-party computation where no single party can compromise the process. Or the parameters may be created through a randomized process that does not depend on any one party. The key difference is that a trustless setup does not rely on trusting any individual entity.
The main tradeoff between the two is security versus complexity. Trusted setups are simpler to implement because they rely on a central party. But this introduces a single point of failure. Trustless setups remove this single point of failure but require more complex cryptographic techniques to distribute trust. Ultimately, trustless setups provide stronger security guarantees by avoiding the need to trust any third party. However, trusted setups can be useful when a high degree of trust in the setting party is warranted.
Proof generation is computationally intensive, often requiring specialized (and exorbitant) machines. Consequently, applications that want to use zero-knowledge technology must factor in hardware costs, potentially increasing costs for users.
The computational intensiveness of proof generation and verification may also increase the cost of implementation. For example, verifying one ZK-SNARK proof for rollups (a type of scaling solution) on the Ethereum blockchain can cost around 500,000 gas (~ $11 per verification at the time of posting).
ZK-SNARK uses elliptic curve cryptography (ECDSA) for encryption. While the ECDSA algorithm is secure for now, the development of quantum computers could break its security model in the future.
On the other hand, ZK-STARK is considered immune to the threat of quantum computing (quantum secure), as it uses collision-resistant hashes for encryption. Unlike public-private key pairings used in elliptic curve cryptography, collision-resistant hashing is more difficult for quantum computing algorithms to break
Decentralized identifiers (DIDs) allow people and organizations to digitally own and control their identity. This aims to solve the cumbersome transportation and storage of physical IDs.
In a ZK-based DID system, users can selectively disclose information from their identity profile. Zero-knowledge proofs enable verifiable credentials and claims about a DID while maintaining privacy. Only information that needs to be validated is disclosed.
Suppose you just turned 18 and want to trade crypto or stocks. Robinhood, TD Ameritrade, Coinbase, Binance, and other exchanges will request and individually verify photos of your ID: quite cumbersome. Instead, the proof generation and verification elements of zk-based DID allow you to expedite registration.
This system could be implemented across government/legal, financial, and social/consumer applications!
Rollups are a type of layer 2 scaling solution designed for the Ethereum layer-1 blockchain. They bundle or "roll up" hundreds of transfers off-chain into a single transaction. Subsequently, they generate ZK-SNARKs (or ZK-STARKs, depending on the system) to prove the validity of every transaction.
The core innovation is that ZK-SNARK (or ZK-STARK) proofs allow transaction validation without submitting all transaction data to layer 1. This substantially reduces costs and congestion on the main chain.
Popular rollups include Starknet, Aztec Network, Scroll, Taiko, zkSync, and Linea.
https://ethereum.org/en/zero-knowledge-proofs/
https://github.com/matter-labs/awesome-zero-knowledge-proofs