ZK World pt. 2 - Zkp
Introduction to Zero-Knowledge Proofs
In the first part of this “ZK World” adventure the focus was on the evolution and history of L2 scaling.
TL;DR on ZK World pt. 1:
Blockchains face tradeoffs between decentralization, security, and scale. As a result, blockchains need help achieving scale so that there is no sacrifice on decentralization or security. This comes in the form of moving transactions off-chain - L2 scaling solutions. L2 solutions have progressed from channels to plasma to rollups. Rollups are the ultimate L2 solution because they allow for general-purpose environments in which applications from L1 can easily port to L2 with minimal work (EVM compatible). Zero-knowledge rollups (zkr) use advanced math/cryptography to scale blockchains. Fully general-purpose zkr technology was thought to be years away but is now coming to market ahead of schedule (which is very exciting).
Now… let’s dive into the technology under the hood of these zkr!
Zero-knowledge proofs (zkp)
The idea of a zkp was first introduced in a 1980’s academic paper titled, “The Knowledge Complexity of Interactive Proof-Systems”1. The idea is that a prover can prove the truth of information to a verifier without revealing the information itself.
More technically, a zkp is a protocol between two parties - a prover and a verifier - in which the prover can convince the verifier of the validity of the claim without revealing anything other than the proof that it is in fact a valid claim. This is the “zero-knowledge” part of the proof; no knowledge (or information) to back the claim is presented, only the proof itself. This does not make sense and should be impossible, which is precisely why it is such a big deal.
An example that is often used to help visualize zkp’s is the “Where’s Waldo?” game2. The premise is how can a prover prove the claim of knowing where Waldo is to the verifier with zero-knowledge. For a traditional proof, the prover would simply point to where Waldo is within the picture (or say Waldo is next to the red striped tent) thus, proving the claim but displaying knowledge to the verifier. To do this with “zero-knowledge”, the prover takes a large piece of paper and cuts a small hole in the middle. The prover then places the small hole in the paper over Waldo and shows the verifier. Thus, the verifier can see Waldo and knows that the prover’s claim is valid with no transfer of knowledge.
This example works because the verifier is able to ask “Where’s Waldo?” and the prover can prove the claim in showing Waldo (and only Waldo) behind the piece of paper. It works due to the fact that the verifier asks the prover to do something that proves that the prover knows the underlying truth (that being, in this example, asking Where’s Waldo?). This is the idea of using the proof itself as evidence for truth.
If the verifier asks, “Where’s Waldo?”, and the prover shows a sailboat, the verifier know the prover is lying just given the proof itself.
Providing more structure, zkp’s have three properties:
Completeness: if the provers claim is true, then the verifier should not need any artificial help to reach that conclusion.
Ex: by showing Waldo and only Waldo, the verifier knows that the prover knows where Waldo is without any other information.
Soundness: if the provers claim is false, then under no scenario can the verifier be convinced that it is true.
Ex: the prover cannot show anything or anyone other than Waldo without the verifier knowing it is not Waldo.
Zero-knowledge: the prover does not present any additional knowledge other than the proof itself.
Ex: only Waldo is shown under the paper; there is no verbal hints, etc.
As a reader you might ask - cool story bro, but why is this important?
There are two takeaways that are important to piece this all together:
Privacy - zkp allow for privacy of information.
Scalability - verification time is faster than execution time.
From our example above:
Only Waldo is shown, there is no other information presented. Thus, the information as to where exactly Waldo is remains private.
For the verifier, it is much faster to look at the little cutout of Waldo than, for example, to sit there and listen to the prover trying to verbally describe where Waldo is in proximity to other objects in the picture. In this way the prover does more work in execution to allow the verifier to quickly verify.
Zkp are very complex but I think that this oversimplification is helpful to get a grasp on the fundamentals of zkp. This should help navigate the waters of complexity as this adventure continues.
Types of zero-knowledge proofs
There are two main types of zkp’s - zk-SNARK’s and zk-STARK’s.
Zk-SNARK’s were first termed by researchers in 20123. The SNARK stands for4:
Succinct
Non-Interactive
ARgument
of Knowledge
Zkp are “Succinct” if they can be verified very quickly (few milliseconds) with a small proof length (few hundred bytes) even for large amounts of data. This means that the verification time does not scale in proportion to the computational load (which allows for scale). Technically speaking, polynomials are used to do this; Vitalik has a post explaining this if you know math5.
In the original zkp, the prover and verifier would interact multiple times to establish credibility. The issue is that the more interaction there is the less efficient the process becomes (which slows down the zkp and hurts scalability). In a “Non-Interactive” zkp, the proof is simply a single message from prover to verifier (this makes the process more efficient). In practice, the most efficient way to produce zkp that are “Non-Interactive” and small enough to publish to a blockchain is to create a reference string between prover and verifier at the genesis of the SNARK. This is technologically complex but here is a helpful way of thinking about it:
Transactions rely on zk-SNARK public parameters to construct and verify the zkp on the blockchain. The creation of these public parameters can be thought of as creating a public/private keypair (like when you create a MetaMask account and get your address - public key - and seed phrase - private key)6. The problem is that the individuals setting the SNARK up are privy to the private key (trusted setup). As a result, using this private key, there is the ability to abuse the system (i.e. create money out of thin air). Thus, the private key must be effectively destroyed so that the SNARK is safe.
In 2017, Zcash was the first major crypto project to use zk-SNARK’s. Zcash went to extreme lengths in an elaborate ceremony to destroy the private key7. The difficulty in ensuring that the private key is not known is considered a security vulnerability for zk-SNARK’s.
Using “ARgument” instead of “Proof” in the acronym is technical. My understanding is that it comes down to a difference between statistical soundness vs. computational soundness. This would be a tangent that is not pertinent to getting a high level understanding of this technology. Thus, I will leave it at that.
So zk-SNARK’s are a form of zkp. Zk-SNARK’s are succinct in that they can be verified quickly and the verification time does not increase linearly with the computation being verified. Zk-SNARK’s are non-interactive in that there is limited interaction between prover and verifier. This makes the SNARK more efficient but to do this, a trusted setup is needed which creates security vulnerability.
Zk-STARK technology was initially proposed in a 2018 academic paper; the writers of the paper went on to found StarkWare8. Zk-STARK’s build on zk-SNARK’s while attempting to improve upon them. STARK stands for:
Scalable
Transparent
ARgument
of Knowledge
STARK’s aim to be more scalable than SNARK’s; thus, the “Scalable” in STARK. This vision of scalability is best described by one of the creators of STARK’s Eli Ben-Sasson9 as “full scalability”, which has two components:
As the number of transactions in the STARK grows, the verification time is exponentially faster than the execution time.
To support this, the proving complexity is “quasi-linear”.
As I understand it, what is important to takeaway from this is:
Even as the STARK scales to take on more transactions (and thus takes longer to execute), the time it takes to verify the STARK remains reasonable.
As the STARK scales, the complexity of proving the STARK does not increase in tandem and thus the STARK does not become infinitely complex to prove.
To fix the trusted setup issues found in zk-SNARK’s, zk-STARK’s use publicly verifiable randomness to create the STARK. This is the “Transparent” component of a STARK.
The third improvement STARK’s make in comparison to SNARK’s is that STARK’s are “post-quantum secure”, meaning that they cannot be broken by quantum computing.
These benefits do some with a tradeoff. In comparison to a SNARK, STARK’s are more complex, have higher proof sizes, and have higher Ethereum verification gas costs10.
To summarize, SNARK’s were the first zkp to be implemented into a major crypto project that was successful (Zcash). SNARK’s work great but the problem is they require a trusted setup that leaves the system vulnerable. STARK’s built upon the SNARK technology while fixing the trusted setup and creating a more scalable zkp. In doing so, STARK’s are more complex and require larger proof sizes and more expensive gas fees.
What is great about the current environment is that we do not have to hypothesize about whether SNARK’s or STARK’s are better. StarkWare just launched StarkNet which is a general-purpose platform that runs on STARK’s, while ZkSync is currently building out a general-purpose platform that runs on SNARK’s.
The next piece in this adventure will focus on zkSync!
https://evervault.com/papers/zkp.pdf
https://agstakingco.gitbook.io/zk-waldo-intro-to-zero-knowledge-proofs/
https://dl.acm.org/doi/10.1145/2090236.2090263
https://z.cash/technology/zksnarks/
https://vitalik.ca/general/2021/01/26/snarks.html
https://www.coinbureau.com/education/zcash-ceremony/
YouTube - “Zcash Ceremony”
https://eprint.iacr.org/2018/046.pdf
YouTube - “Introduction zk SNARKs STARKs Eli Ben Sasson Technion”
https://consensys.net/blog/blockchain-explained/zero-knowledge-proofs-starks-vs-snarks/
nice job