Zero-Knowledge Proofs: A Beginner’s Take
By Sumi Maria Abraham, Research & Development Engineer, Kerala Blockchain Academy.
Have you ever considered privacy issues at the security checks at entry-restricted places? If you plan to board a flight to your vacation spot, you may need to show your passport to security at the entrance. They will scan through and can see the details of the journey. They must ensure that you are a passenger and should be granted entry to the airport. The same is valid with security checks at some official events. Though the security needs to know only about your access permission, they can often learn more from the proofs you submit for verification.
Let us think of an alternate scenario. You go to the airport and tell the security that you are a passenger and show him a piece of data- which does not include any information about your travel or yourself. By checking the data, security can determine whether you should be permitted to enter.
Can that happen? Of Course, with Zero-Knowledge Proofs.
Zero-knowledge proofs fully convince that a statement is true without yielding additional knowledge.
Confused? Let us play a puzzle. Can you spot a panda among the snowmen in the below figure by Dudolf?
Akku and Jane are trying to solve the puzzle. The first to spot the panda will get a movie ticket + snacks coupon as a reward, and the second will get a movie ticket alone.
Akku: Hey Jane, I found the panda.
Jane: Where?
Akku: I can’t show you the location. You will grab my prize then.
Hearing this, Jane took a copy of the picture on a piece of paper with a unique watermark and gave it to Akku, along with scissors.
Jane: Akku, you can go to that corner, and without showing me, you can carefully cut the panda from the image copy I gave you.
Akku went to the corner and tried to cut the panda alone from the image. She turned the opposite side so that Jane could not guess the panda’s position. Also, she ensured that she destroyed the image so that Jane would not get it.
Akku returned the image of Panda to Jane.
Jane turned the image over to verify the watermark to ensure it was cut from the image itself.
Thus Jane cleverly used a method to verify Akku’s claim that she knows the solution without demanding her to reveal the answer- a zero-knowledge proof.
Zero-Knowledge Proofs
“A zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a statement is true, without revealing any information apart from the fact that this specific statement is true” [1].
In the previous example, Akku is the prover, and Jane is the verifier. Akku proves her knowledge of the solution without giving any information to help Jane guess the answer using the cut-out of the panda, which is known as the witness.
Well, did you find the Panda ?
Zero-knowledge proofs must satisfy three properties:
>> Completeness: If the statement is true, then an honest prover can convince an honest verifier what they claim they know.
- Akku knows the solution, and she proved it to Jane.
>> Soundness: If the statement is false, there should not be a way by which a dishonest prover may convince an honest verifier. No cheating !!
- If Akku has not found the panda, she won’t be able to complete the task. If she gives a panda figure from any other source, the watermark will be missing, and Jane can identify it.
>> Zero-Knowledge: If the statement is true, the verification process will not reveal anything beyond the fact that the statement is true.
- Jane is convinced that Akku knows the solution. Though Jane has the cut out of the panda, it will not help Jane locate it in the original figure.
Types of ZK Proofs
ZK-Proofs are broadly classified into interactive and non-interactive proofs.
Interactive zero-knowledge proofs require the prover and verifier to engage in a two-way conversation. The verifier might be asking the prover some questions, and based on the prover’s response to the questions, the verifier may be able to confirm or reject the prover’s statement. This requires the verifier and prover to be available at the same time. Even if one verifier is convinced, if another verifier needs to be convinced, a new set of interactions is required between the new verifier and the prover. So the proof cannot be re-used to prove the same statement to others.
Will Akku be able to convince Betty by showing the cut-out of Panda? She was absent when Akku cut the panda from the original figure. So this is an example of interactive proof, which requires both verifier and prover to be available.
So interactive proofs are inefficient when a prover needs to convince multiple verifiers (for example, in a distributed system like blockchain). We have a non-interactive version of Zk proofs to deal with such issues.
In the case of non-interactive zero-knowledge proofs, the prover sends a single message to the verifier, who can then check the statement’s validity without further communication from the prover. So the prover sends out one proof that anyone with access to the verification algorithm can verify. This proof should be trustworthy, available to the public, and infeasible to be misused.
Let me explain non-interactive proof with a sample scenario.
BlockHashLive (BHL) is an annual Blockchain Summit organized by Kerala Blockchain Academy (KBA). All the participants of the BHL2022 were allowed to claim an NFT as a token of their presence. This was awarded to the attended delegates, participants, sponsors, organizers etc. To verify whether a person was associated with the BHL2022 event, just check the person’s blockchain wallet for a BHL2022 NFT.
If someone showcases their NFT, anyone can check whether Kerala Blockchain Academy issued it and confirm their presence in the BHL2022 event. Thus without interacting with the prover, anyone can verify their attendance at the event. Unlike the event certificate, the NFT does not disclose any information about the participant.
Applications of Zero-Knowledge Proofs
ZK-Proofs have tons of applications spread over multiple fields [4]
>>Proving statements on private data like personal information:
- Checking if Bob has more than X$ in his bank account without disclosing the original bank balance of Bob.
- Confirm that bank ABC has not transacted with Alice for a particular duration without revealing the transaction details of these entities during the period.
>>Anonymous Authorization:
- Proving Anju has access to a restricted area without revealing her identity
- Confirm the citizenship of Ziyad without revealing his address or any other personal information.
>>Anonymous payments:
- Verify that Sanu is paying taxes correctly without disclosing his annual earnings.
>>Outsourcing computation:
- Raju wants to perform a tedious, extensive computational task which may take a long time and effort. He assigns it to Radha. Radha performs the task and gives him the result. Raju can validate the result without redoing the computation- trustless computing.
- Instead of everyone redoing and verifying the transactions in a blockchain, why not one entity do the computation, and everyone else verifies it?
Zero-Knowledge and Blockchain
Privacy is a significant concern in the blockchain domain. As we try to include transparency and decentralisation by distributing the data, it is unsuitable for domains with strict privacy concerns. Zk-proofs can help overcome this problem.
Transactions in a public blockchain are recorded in an open ledger. Though users are pseudonymous, they cannot remain anonymous. Transparency is also required since all the nodes should verify the transactions. But using zk proofs, nodes may be able to verify transactions without getting access to the details of the sender/receiver, amount or token involved. Zcash is an example which allows private transactions.
In public blockchains like Ethereum, Layer-2 solutions like rollups use Zero knowledge techniques to scale the network and decrease transaction costs. Zero-knowledge rollups batch transactions together and post them to the layer-1 blockchain with validity proof of the computation. The validity proofs can be either SNARKs or STARKs.
Zero-knowledge proofs have transitioned from purely academic to practical, real-life applications in access control, network communications, blockchain transactions, etc. Zk techniques can help applications maintain decentralization without compromising privacy.
References
[1]http://users.cms.caltech.edu/~vidick/teaching/101_crypto/GMR85_ZeroKnowledge.pdf
[3] https://ethereum.org/en/zero-knowledge-proofs/#what-are-zk-proofs
