Proving knowledge of a secret is the basis of password-based authentication systems. The assumption is that only you know your password. If this is the case, entering your password into a system proves your identity and grants you access to your account.
However, this approach doesn’t work as well on the blockchain, where everything stored on the digital ledger is publicly visible. Any password or other secret included within a blockchain transaction would be revealed to all nodes and users of the blockchain. This is where zero-knowledge proofs (ZKPs) come into play.
What is a Zero-Knowledge Proof?
A ZKP allows a prover to demonstrate knowledge of some secret without revealing that secret. For example, a ZKP could be used to prove to an authentication server that a user knows a particular password without the authentication server learning the password as part of the process.
An effective ZKP must meet three requirements:
- Completeness: After the proof is completed, the thing being proven — such as knowledge of the password — is indisputably true.
- Soundness: It is statistically implausible for a prover to trick a verifier with a fake proof.
- Zero-Knowledge: The ZKP doesn’t reveal the secret, only that the claim is true.
One example of a ZKP is proving to a color-blind person that two otherwise identical balls are different colors without revealing the color of either ball. This can be accomplished via the following steps:
- The verifier shows one of the balls to the prover and then conceals it again.
- The verifier repeats step 1.
- The prover states whether the balls from steps 1 and 2 are the same ball or different ones.
Assuming that the balls are actually different colors, the prover can answer the question in step three with 100% accuracy. If they are lying, then they have a 50-50 chance of guessing correctly. By performing the proof multiple times, the verifier can make it nearly impossible for the prover to be lying and guess correctly every time.
However, iterating this proof multiple times doesn’t provide the verifier with any information about the colors of the two balls. They know for certain that the two balls are different colors but the prover never provides any information about the color of either ball.
ZK-SNARK and ZK-STARK
The zero-knowledge proofs used in blockchain are more sophisticated than this example. However, the basic principles are the same. The goal is to demonstrate that something is true without revealing some sensitive information.
In the blockchain space, there are two main forms of zero-knowledge proofs that are in use and under active development. These are zk-SNARK and zk-STARK.
zk-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. Breaking this down:
- Zero-Knowledge: The proof is a zero-knowledge proof that meets the three criteria of completeness, soundness, and zero knowledge.
- Succinct: The size of the resulting proof is relatively small, which is important on the blockchain where space is limited.
- Non-Interactive: A zk-SNARK proof can be verified without direct interaction between the prover and the verifier. For example, it can be posted to the blockchain and verified by anyone.
- Argument of Knowledge: A zk-SNARK proves that the prover knows secret information (the witness).
A zk-SNARK proof can be used to prove that a user knows a secret or that a transaction is valid without revealing the contents of the transaction.
A major limitation of zk-SNARKs is that they require a trusted setup, and an attacker with access to the random values used to generate a set of public parameters — the Common Reference String (CRS) — could generate fake proofs. However, this issue can be overcome using multi-party computation (MPC) where multiple parties collaborate to complete the trusted setup and no party has complete information about the random values used.
zk-STARK stands for Zero-Knowledge Scalable Transparent Argument of Knowledge. The two terms that differ from zk-SNARK are the following:
- Scalable: With zk-STARK proofs, the time required to generate and validate the proof grows more slowly as the size of the witness grows. zk-SNARKs are better for small witnesses, while zk-STARKs are better for large ones.
- Transparent: The random information used to set up a zk-STARKs proof is public, eliminating the need for a trusted setup.
zk-STARK proofs are generally less efficient in terms of storage and the computation required for verification than zk-SNARKs. However, the lack of a trusted setup has positive implications for security, and zk-STARKs is better for large witnesses.
Blockchain Applications of Zero-Knowledge Proofs
ZKPs use mathematics and cryptography to prove that something is true while keeping secrets or eliminating unnecessary information. These capabilities make ZKPs ideally suited to blockchain applications where the transparent, distributed digital ledger creates significant privacy concerns.
ZKPs have numerous potential applications within the blockchain ecosystem. Some of the most significant include the following:
- Anonymous Transactions: On the blockchain, the details of all transactions are publicly visible, which makes it possible for blockchain nodes to validate them before adding them to the ledger. ZKPs allow transactions to be validated without revealing the details of the transaction.
- Identity Verification: Verifying users’ identities on the blockchain may reveal sensitive information on the immutable, distributed ledger. ZKPs can be used to prove a user’s identity without revealing that information on the blockchain.
- Authentication: As mentioned above, ZKPs can be used to prove knowledge of a secret, such as a password. This allows ZKPs to be used to authenticate a user as a member of a group or a legitimate user of a system on the blockchain.
- Verifiable Computation: ZKPs can be used to prove that the results of performing some computation are correct. This has the potential to improve blockchain scalability by allowing computation to be outsourced with only the result and the proof of its correctness recorded on the blockchain.
Security Considerations of ZKPs
ZKPs have the potential to dramatically improve the privacy, security, and scalability of blockchain systems. The ability to prove the correctness of unknown information eliminates the need to place potentially sensitive information on the blockchain and allows computations to be outsourced to a third party without requiring trust in that third party.
However, along with their benefits, ZKPs also present significant security concerns. Some security considerations for ZKPs include the following:
- Trusted Setup: zk-SNARKs requires a trusted setup where the initial randomness must be kept secret and destroyed. However, this can be addressed with MPC, and zk-STARK proofs do not require trusted setups.
- Costly Verification: Verifying a zero-knowledge proof can require significant resources. As a result, users may choose not to run and verify the proof, creating the potential that a malicious user could slip a forged proof through.
- Cryptographic Security: zk-SNARKs rely on elliptic curve cryptography, which can be broken by a sufficiently large quantum computer. While zk-STARKs rely on quantum-resistant hash functions, these algorithms may be broken at some point, which would undermine the security of the generated proofs.
At the moment, zk-STARK proofs are considered trustworthy and secure but often require more resources than zk-SNARK ones. As a result, significant tradeoffs exist between ZKP usability and security.
ZKPs and the Blockchain
ZKPs are part of the future roadmap of many blockchain protocols; however, they are also in use today. For example, the zCash cryptocurrency gets its name from the fact that it uses zk-SNARKs to protect the privacy of transactions from z-addresses.
However, the main push for ZKPs in blockchain at the moment is for verifiable computing. As blockchains like Ethereum work to improve the scalability of their protocols, the ability to offload computation and validate the results has the potential to dramatically increase the ability of these blockchains to process transactions and support the growth of Web3.