Ali Baba cave problem
To prove her knowledge, Peggy enters the cave while Victor waits outside so he can’t see which path she takes. He then enters the cave and shouts the name of the path he wants Peggy to use to return.
If Peggy didn’t actually know the password, there is a 50% chance of her emerging from the path Victor wanted her to use. However, if they repeat this test many times and Peggy always emerges from the right path, Victor can eventually conclude that she must know the password.
The Ali Baba cave illustrates a core limitation that faced cryptographers researching zero-knowledge proofs for computing purposes – Peggy and Victor must be present and willing to interact in multiple tests for the proof to be successful. These requirements limited the practical application of zero-knowledge proofs in computing.
Criteria defining zero-knowledge proofs
A key breakthrough in ZK technology came in the 1991 when Manuel Blum, Paul Feldman, and Silvio Micali published their paper “Non-Interactive Zero-Knowledge and Its Applications.”
In the paper, they propose using a cryptographic key shared between the prover and verifier. The prover and verifier agree the means of proving a fact without revealing knowledge of it and generate the shared key based on these rules. The prover can then enter their side of the shared key, which the verifier can easily verify matches theirs.
The fact can now be proven and verified in a single interaction, eliminating the need for multiple interactions. Reducing the time and burden of interaction made it feasible to deploy zero-knowledge proofs in computing at scale.
The shared key works as a pair in a similar way to the public/private keys encrypting a blockchain wallet.
In the paper, Blum, Feldman, and Micali also laid out a set of criteria that apply to all zero-knowledge proofs:
- It must be complete, meaning that as long as the input is valid, the proof will always verify the statement is true and thus can be trusted.
- It must be sound, so that an invalid input cannot return a true value.
- It must be zero-knowledge – the verifier must only learn of the validity or otherwise of a statement, not any of the information about the original input.
Types of ZK technology
Outside the blockchain sphere, ZK technology has applications in areas such as authentication and nuclear disarmament. Within blockchain, zero-knowledge proofs have developed and gained substantial utility over recent years. Currently, there are two types of ZK technology in use by blockchain protocols: ZK-SNARKs and ZK-STARKs.
ZK-SNARKs
ZK-SNARK is an acronym that stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. Each letter is a defining property:
- ZK – the protocol is zero-knowledge. A verifier can validate a fact without knowing the fact itself.
- Succinct – the proof is smaller and easier to verify than the fact itself.
- Non-interactive – prover and verifier are only required to interact once thanks to a shared key.
- Argument of Knowledge – the protocol must meet the “soundness” criteria laid out above so that it cannot be cheated, and it must be prohibitively difficult for anyone without knowledge of the fact to create a ZK-SNARK.
ZK-SNARKs were developed by Zcash as an encryption solution to enable private cryptocurrency transactions. However, a key drawback of ZK-SNARKs is that a trusted setup using a protocol or provider is needed to create the shared encryption key, meaning they aren’t an entirely trustless way to transact for everyday purposes.
ZK-STARKs
ZK-STARK stands for Zero-Knowledge Scalable Transparent Knowledge of Argument. The properties that differ from a ZK-SNARK are:
- Scalability – where there is a lot of data to be processed for a verification, ZK-STARKs are faster at generating and verifying proofs. ZK-STARKs can handle exponentially larger amounts of data with only an incremental increase in verification time.
- Transparency – ZK-STARKs leverage publicly verifiable randomness to generate the shared key needed for the zero-knowledge proof. As such, they eliminate the need for a trusted setup.
These features mean ZK-STARKs offer some advantages over ZK-SNARKs; however, ZK-STARKs generate more complex proofs than ZK-SNARKs, so generally incur higher transaction costs.
ZK technology for blockchain scalability
Layer 2 platforms leverage ZK-STARKs to make Ethereum more scalable, using a solution called zero-knowledge rollups, or ZK rollups.
This method is used to bundle Ethereum transactions into batches to be executed on the Layer 2 platform instead of the Ethereum mainnet, alleviating congestion. The Layer 2 platform then provides a ZK proof of the processed transactions to the Ethereum mainnet to update the overall state of the blockchain.
ZK rollup projects include Layer 2 platforms StarkNet, zkSync, and Polygon Zero.
Other use cases of ZK technology
Although not yet widely deployed, ZK technology has the potential to help protect personal information. Suppose an individual can provide a ZK proof of being of age, resident in a particular country, or not on any sanctions list. In that case, it could eliminate the requirement for people to provide copies of government-issued IDs to service providers. In turn, this would reduce the risk of documents being hacked and leaked online, enhancing user privacy.
Similarly, ZK proofs could make online authentication easier, eliminating the need to expose sensitive login credentials each time someone accesses a service.
ZK Technology essentials
- ZK proofs are an encryption method enabling parties to prove and verify information without having insight into the information itself.
- ZK technology emerged in the 1980s and developed into two main types of zero-knowledge proofs: ZK-SNARKs and ZK-STARKs.
- ZK-SNARKs are used to make cryptocurrency payments more private, while ZK-STARKs are now widely deployed in Layer 2 scaling platforms. ZK technology has other potential use cases in identity and authentication.
