From zero knowledge to one
Disclaimer
Zklog [skloːg] is a log to document my journey through zero knowledge. It’s very likely that I make mistakes on the way, kindly let me know if you come across any. Other than that I hope that I by answering some questions I come across, I can also help others to learn.
Intro
On the 13th September we kicked off the 2nd cohort of the MINA zkApp builders programme, a 12-week program to support developers building zkApp-related projects. The goal of the program is to gather feedback for improving SnarkyJS and zkApps.
My goals and reasons for joining the MINA builders programme are as follows:
- to learn about zk proofs, their use cases and their current state ie.e which use cases can we build in a feasible way?
- to learn about Mina and the underlying networks functions required in order to host zk programmes
- to learn how to programme zero knowledge use cases
- to develop broader perspective of zkApps overall (e.g. how does Starkware differ from Mina zkApps)
This weeks article covers the following topics:
What I’ve learnt this week
- What is zero knowledge
- What are ZK SNARKS
- How does MINA work
- What’s a zkApp
1k fun fact
“https enables us to use cryptographic data of the TLS transcript in a zkApp which we can use to generate a zero knowledge proof”
What have I learnt so far?
What is zero knowledge on a high level and what are its use cases?
Zero knowledge means proofing honest computation without revealing used inputs, e.g. I want to verify my credit score without revealing my account balance. Generally this could unlock various use cases such as validating crypto transactions, proving identity to preserve users privacy, as well as catering for more scalability e.g. instead of storing all data on-chain I could just store the proof of the computation.
My favourite example to explain zero knowledge is the “Cave of Alibaba” which goes as follows: Image you have a ring shaped cave with a locked door at the far end. Peggy wants to prove to Victor that she knows the magic word to unlock the door, but she doesn’t want Victor to find out what the magic word is.
So Victor asks Peggy to stand by the door and wait for his command. Victor now randomly shouts to Peggy which path she should take back. If Peggy didn’t actually know the magic word to unlock the door she would only be able to return one path and hence Victor would find out if Peggy was lying.
Peggy can prove she knows the magic word without ever revealing it to Victor.
If Victor ran the test just once, of course Peggy could have just gotten lucky. However, if Victor runs the test 1000 times he can be very confident that Peggy knows the magic word. Zero knowledge proofs are therefore probabilistic rather than deterministic.
What are ZK SNARKS?
The problem you might notice in the example above is the interactive way of proofing your knowledge meaning the proofer (Peggy) and the verifier (Victor) would both have to be online for the computation. To avoid this inconvenience an incredible break-through was the development of non-interactive proof systems such as ZK-SNARKS which work as follows on a high level: The prover passes a secret to a special algorithm to compute a zero-knowledge proof. This proof is sent to the verifier, who checks that the prover knows the secret information using another algorithm.
ZK-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.
- Zero-knowledge: A verifier can validate the integrity of a statement without knowing anything else about the statement other than the statement is true or false
- Succinct: Verification of the proof is quick
- Non-interactive: Prover and verifier only interact once
- Argument: Cheating is extremely unlikely
- (Of) Knowledge: It is highly unlikely for the prover to compute a valid zero-knowledge proof if they do not know the secret information (witness)
How does MINA work on a high level?
MINA’s value proposition is as follows: With every transaction and every block, blockchains grows bigger and bigger in size (at the end of the day it’s a chain of blocks). Unfortunately, this means it becomes almost impossible for the average Josephine to run a full-node (i.e. running a node verifying every transaction). MINA prides itself in being the first succinct blockchain with a constant size of 22kb. How does MINA stay so small? Earlier, we said zero knowledge is proofing the execution of a computation- the trick here is to note that updating a blockchain is also just a computation. This means we can use SNARKS to verify the current state of the blockchain and only store the proof of the computation. Now instead of storing one proof per block (which would not solve the problem of linear growth), MINA actually just uses the idea of recursive SNARK composition. Again the trick is to note that checking a SNARK is also just a computation, therefore we can chain multiple SNARKS together to get one SNARK which proofs that we verified all of the SNARKS on MINA. If this was confusing, checkout the video in the resources for a much better explanation.
What’s a zkApp?
MINA offers the ability to develop zero-knowledge smart contracts on MINA. In general, zkApps execute the computation off-chain (i.e. privately in a user’s web browser) and generate a zero-knowledge proof which will live on-chain. When users send a zk proof using the zkApp, MINA will only accept the transaction if the proof is valid according to the zk smart contract. This has some neat side-effects e.g. off-chain computation can be unlimited, there’s a flat transaction fee for all users (since computation happens off-chain) and above all, the zkApp can enable users to maintain privacy, since their private data is only handled off-chain.
To develop a zkApp, MINA offers a Typescript library called SnarkyJS which integrates nicely into the browser and offers lots of commonly known frontend-developer tooling around it (esLint, prettier, VScode). When compiling a zkApp, a prover function runs locally and generates a zk-proof and as well as a verification key. The developer then deploys the smart contract to a zkApp account which is a MINA account containing a verification key, which is used to verify all zkProofs generated via the zkApp.
1k fun fact
You could easily generate a proof from anything transmitted via https, i.e. a zkapp could use the latest bitcoin price provided by one (or multiple) exchanges and ensure that the data had not been changed in transit by asserting on the signature and therefore could integrate public and private data, from anywhere on the web, as part of their operation. One fun example I heard in an Zero Knowledge podcast episode on SNAPPs (now known as zkApps) describes this further: Imagine the president emailed you and you want to proof it to your friend. Now a screenshot won’t cut it, because it could’ve been photoshopped, so instead you can actually use the cryptographic data of the TLS transcript which you wrap up in a SNARK and use inside a zkApp to create a zero knowledge proof of that data.
List of amazing resources:
Zero knowledge
- Quick video on what’s zero knowledge
- Primer on zero knowledge
- Curated list of zk examples
- Great description of zk-SNARKS by zcash
- Guide to zk snarks
- Intro to zkSNARKs with Howard Wu (Podcast)
ZK Maths
- Great intro into crytpography primers and zk Maths by Elena Nadolinski
- ZK Whiteboard sessions
- Vitalik’s articles on SNARKS (1) and (2)
- Course on Cryptography / Zero Knowledge
- Zero knowledge: Proofing your knowledge on a constrained polynomial
ZK use cases
- Zcash https://z.cash/technology/
- Building an identity system using Zk proofs
- Proof of location application
- Research on a distributed collaborate architecture to proof location
MINA
- MINA bootcamp intro recording to watch an intro into MINA and zkapp examples by O(1) labs
- MINA bootcamp wrap-up recording to see some zkapp examples
- Explanation why MINA is so small
- Https & zkApps
- MINA and Snapps (Podcast)
- recursive Snarks in Coda (now known as MINA) (Podcast)
