By
Dimitar Bogdanov
March 16, 2023
8 Min Read
Zero-knowledge proofs are curious mathematical instruments that have the unique ability to prove that a statement is true without having to reveal any information about that statement. Despite this unique property, however, zero-knowledge proofs for a long time seemed destined to remain just a mathematical novelty. Fortunately, this has changed in recent years thanks to the rise of blockchain and other Web3 technologies.
Today, zero-knowledge proofs, or zk-proofs (ZKPs) for short, are one of the most promising areas of Web3 research, with Web3 developers finding interesting ways to use these powerful tools. From being at the heart of popular privacy protocols to powering promising scaling solutions like zk-rollups, the impact of zk-proofs is already making on the industry cannot be overstated.
In this article we’ll be taking a closer look at the two main types of zk-proofs currently used in the Web3 industry - zk-SNARKs and zk-STARKs. But first, let’s examine the concept of zero-knowledge proofs at a more fundamental level.
As we alluded above, zk-proofs predate the invention of blockchain and by quite a bit. The concept was introduced in the 1989 paper “The Knowledge Complexity of Interactive Proof Systems”, authored by Shafi Goldwasser, Silvio Micali and Charles Rackoff. This is actually great for the purposes of this article, as it gives us a chance to establish a good understanding of the concept of zk-proofs on a basic level, without having to worry about the added complexity that the Web3 aspect brings.
So we have this neat little definition: zero-knowledge proofs are instruments that allow us to prove that a statement is valid, without having to reveal anything about that statement. And that’s a perfectly accurate way of describing what zk-proofs are, but I don’t think it’s a very good way. It’s too abstract, it sort of hangs in the mind like an out-of-focus picture refusing to coalesce into a clear image.
So a more practical way of thinking about zero-knowledge proofs might be something like this: zk-proofs allows one party, called a prover, to prove to another party, a verifier, that something is true without revealing what that thing is. For example, the prover claims that they know a secret and wants to prove to the verifier that that statement is true, but doesn’t want to reveal what the actual secret is. Zk-proofs allow us to do just that.
Now we are getting somewhere, but it’s still not enough. In order to get a firm grasp of the zk-proof concept, we need a clear and practical example of how this all works. And there are certainly a few that can be found online - some popular examples include proving that you’ve solved a sudoku without showing the solution or proving that a map can be colored in a certain pattern without revealing the map itself.
Personally, I find these somewhat unintuitive, as they have too many moving parts, too much complexity. You are forced to grapple with the complicated setup of those examples, which leaves you unable to focus on the explanation that they aim to provide.
No, we need to simplify further in order to zero in on the core idea. Thankfully, we have the perfect example, thanks to the excellent YouTube channel Up and Atom.
https://youtu.be/V5uVKZn3F_4
Credit: Up and Atom Youtube channel
So how do you prove that something is true without revealing any information about it?
Well, imagine that we have a jar full of colored ping pong balls - we have a few red ones, some yellow ones, perhaps two or three blue ones, etc. The prover takes two balls from the jar and claims that they are different colors.
Now, to prove that, the prover can simply reveal the balls and allow the verifier to visually verify that they are indeed colored differently. However, the prover doesn’t want to show the balls to the verifier. So they need to find a different way to prove to the verifier that the statement is true.
With that in mind, the prover puts each ball under a cup and looks away. The verifier is then presented with two possible actions - they can either switch places of the cups, along with their respective balls, or leave them as they are. When the verifier finishes, the prover looks under the cups and tells whether the verifier has switched the cups.
Note that, because the balls are equal in size, if they are also the same color, the prover has no way of knowing whether the verifier has switched the cups or not. So if the prover answers correctly, then this must be because the balls are different colors, right?
Well, not quite - the prover might just have been lucky and guessed correctly. However, we can dramatically reduce the likelihood of a lucky guess happening by simply repeating the process multiple times. In this example, after only seven consecutive correct answers by the prover, the verifier can be over 99% sure that the balls are different colors.
So while zero-knowledge proofs cannot give 100% certainty, by running checks over and over again, we can push that percentage to as close to 100% (read 99.99999999…%) as the verifier wants. And from a practical standpoint, that is essentially the same thing as 100% certainty.
What’s more important is that the same principle can be applied to prove all kinds of statements, or witnesses, as they are also called.
Now that we have built a base understanding of how zero-knowledge proofs work in their purest form as logical, mathematical constructs, figuring out how the Web3 aspect fits in with all this becomes much easier. Because that part essentially boils down to the ingenious ways the ZKP principles are implemented in Web3 systems.
None of that is easy, mind you. In fact, as we’ll see below, a lot of research and hard work have gone into figuring out how these theoretical principles can be applied for practical uses. Fortunately, all that effort has already produced some spectacular results.
When it comes to ZKP implementation, there are two main approaches that have given rise to the two most popular types of zero-knowledge proofs - zk-SNARKS and zk-STARKs. Both approaches have shown promise and attracted significant interest, which has naturally sparked a somewhat of a SNARKs vs STARKs debate. However, the main thing here is that both of these models are demonstrating the power of ZKPs and are already having practical applications
Succinct non-interactive argument of knowledge, or SNARK, is a type of zk-proof that was first popularized by privacy protocols like Zcash and Monero. Zk-SNARKs are often described as “zero-knowledge proofs that require a trusted setup to generate the keys used to create and validate the proofs”. The problem with this definition is that it too is kind of vague. What is that trusted setup and what exactly are those keys? Well, to answer these questions we need to go back to our jar of balls.
So in our ZKP example, the prover and the verifier worked together to create a proof. They interacted with one another. This is because zero-knowledge proofs, as they were originally conceived, are inherently interactive. But wait, we just said that the ‘N’ in SNARK stands for “non-interactive”. Well yes, this is the key distinction that transforms zero-knowledge proofs from purely theoretical constructs into an actual technology with practical applications.
In the case of our very simple example, generating a proof is a relatively straightforward process that requires just a few rounds of prover-verifier interaction. But if we want to do something practical, the complexity of interaction could skyrocket, with countless rounds of back and forth between prover and verifier. And if that wasn’t enough, a proof generated this way is only good for the verifier that has participated in the interaction, meaning that this laborious process has to be repeated for each new verifier. You cannot do anything at scale in this way.
The non-interactive approach circumvents these limitations in an ingenious way. It requires a common reference string (CRS) - the ‘key’ in our definition - to be shared between prover and verifier. The shared CRS allows the prover to demonstrate their knowledge of some information without revealing what that information is and without directly interacting with the verifier. Instead, the prover runs the information through a special algorithm designed to compute a zk-proof. Then the verifier receives the ZKP and runs a different algorithm to verify its validity. Most importantly, this method ensures that anyone who has access to the CRS and the verifying algorithm can become a verifier. This is why the CRS is often referred to as the public parameters of the system.
So with the zk-SNARK approach, the CRS is generated during an initial setup phase. During that phase, some random number values are generated and then encrypted to create the CRS. Once generated, the CRS can be used in perpetuity to generate SNARKs for that system without direct interaction between prover and verifier. And, because we skip all that back and forth communication between prover and verifier, we can generate zero-knowledge proofs that are short enough - succinct, if you will - to be stored on a blockchain. It should be noted that ‘succinct’ is not just a generic term, but it has a specific meaning in the context of zk-proofs. If a ZKP is succinct it means that it is shorter than the witness.
The random number values that are generated during the initial setup are what we call secret randomness or ‘toxic waste’. It’s paramount that they remain secret, because if they are compromised, they could be used to generate false proofs. So, in order to ensure that this doesn’t happen, the party performing the setup must destroy the toxic waste after the CRS generation. And we can only be sure that that party has acted honestly if we have a trusted setup. We have to trust that the party performing the setup has acted honestly.
The requirement for a trusted setup is seen as the main drawback of SNARKs, with critics pointing out that it runs counter to the trustless and decentralized nature of Web3. The lack of such a requirement is often cited as the biggest advantage that STARKs have over SNARKs.
To mitigate this criticism, most zk-SNARK protocols perform trusted setup via multi-party ceremonies. As the name suggests, in these ceremonies multiple participants (the number can be in the hundreds, depending on the particular ceremony) work together to generate the common reference string. Each participant works with their own portion of the toxic waste that remains secret to the other participants. Through the magic of a certain subfield of cryptography called multi-party computation (MPC), the participants are able to jointly compute the CRS.
The great thing about multi-party ceremonies is that if even one of the participants acts honestly, we can be sure that the secret randomness cannot be exposed. And with modern ceremonies often involving up to hundreds of participants, we can say that the setup is practically trustless.
Still, there’s another approach to generating zk-proofs, one that uses a novel breakthrough in cryptography to ensure that the process is completely trustless. Let’s see what STARKs have to offer.
Zk-STARKs are a type of zero-knowledge proofs invented by Starkware. The acronym stands for ‘scalable transparent arguments of knowledge”.
The first thing that stands out is that these ZKPs are described as ‘transparent’, instead of “non-interactive”. Don’t let this mislead you, though - STARKs are also non-interactive, but the non-interactiveness is achieved in a transparent way that does not require a trusted setup.
But how is this possible? After all, when we talked about SNARKs, we emphasized on the importance of having a trusted setup to safeguard against the possibility of bad actors accessing the secret randomness. So how is it possible to have transparency without creating potential exploits?
Well, to achieve that, STARKs turn to ideas first explored in probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs). Let’s take a closer look.
Probabilistically checkable proofs are actually at the heart of the very first theoretical ZK constructs. One of their most important properties of PCPs is that they work with public randomness, which is where the transparency comes from.
So PCPs are really interesting, but there is a reason why they are purely theoretical constructs. This is because generating a proof using that method takes so much time and requires so much storage space that it’s practically infeasible. This is where the next piece of the puzzle comes in.
Interactive oracle proofs propose a new model that seeks to optimize the PCP approach without losing its advantages. The key here is that an IOP verifier does not need to read the entire message from the prover. Instead, it can query that message at random locations, which means that the prover only needs to compute those parts of the message that have been requested by the verifier. In essence, IOPs offer a way to have the best of both interactive proofs and PCPs while also making that scalable enough to be practical.
StarkWare uses these foundational ideas, but improves them by putting even greater emphasis on the IOP model, furthering its efficiency with the help of a fast algebraic local coding protocol called FRI. The result is a zero-knowledge, scalable and transparent argument of knowledge - zk-STARK.
Apart from being “transparent”, STARKs are also “scalable”, which means that prover and verification times increase only slightly as the witness size grows. In contrast to SNARKs, where prover and verification times increase linearly with the witness. That’s why for larger witnesses, STARK proofs can be generated and verified faster than SNARKs.
Another advantage of STARKs is that they use collision-resistant hashes for encryptionZ, whereas SNARKs rely on elliptic curve cryptography. Both models are secure in the current environment, but elliptic curve cryptography could be vulnerable to quantum computing algorithms in the future. In contrast, hash functions are much more ‘future-proof’.
All that’s great, but STARKs also have a considerable drawback - STARK proofs have a much larger size than SNARKs. Nonetheless, a STARK is still succinct, with its size being smaller than the witness.
While there are a few differences between STARKs and SNARKs, the fact that STARKs eliminate the trusted setup is typically cited as their biggest advantage over their SNARK counterparts. However, things may already be changing on that front. Let’s circle back to SNARKs and take a quick look at Halo.
While the traditional method of generating SNARKs requires a trusted setup, a recent innovation in cryptography has enabled a new way of creating SNARK proofs. Halo is a zero-knowledge proving platform that omits the trusted setup stage in SNARK creation and enables scalable proof generation. The initial version of Halo was based on a protocol called Sonic, while the current Halo 2 version uses the much more efficient PLONK protocol.
We’ll take an in-depth look at the Halo platform in a future article.
While zk-proofs are a nascent technology in the context of Web3, developers are already finding interesting ways to use the technology in the space. So far several strong use cases have emerged.
Due to their succinctness, zk-proofs could be a massive gamechanger for blockchain scalability. In fact, ZKPs are at the heart of one of the most promising scaling technologies for Ethereum - zero-knowledge rollups. ZK rollup solutions use ZKPs to generate ‘validity proofs’ for entire batches of transactions that have been executed on a Layer 2 network. The validity proofs are then submitted to the Ethereum mainnet to be permanently added to the network's transaction history. With this method we can execute thousands of transactions outside of Ethereum and submit the results back to the mainnet via a single transaction.
The unique properties of zk-proofs make them ideal for privacy use cases and, it’s no surprise that the technology was first embraced by privacy-focused protocols like Zcash and Monero. But the possible applications of the tech are much more numerous. For example, ZKPs could be invaluable for enterprise-grade solutions, allowing companies to prove to their customers, business partners or industry regulators that they follow the correct procedures and processes without revealing sensitive information about their operations.
Zk-proofs could also be used to improve interoperability between different Web3 networks. We just discussed how zk rollups can help L1 and L2 networks to communicate efficiently and the same principle could be applied to improve the efficiency of cross-chain technology.
As we delve deeper into the exciting world of zero knowledge proofs, one thing becomes clear - the technology has incredible potential and warrants further research and development. It feels like we’ve only scratched the surface of what this technology is capable of. Of course, this is not to say that ZKPs are a miracle solution for every problem. After all, every technology has its limits. But as the Web3 community continues to explore the field, more and more ZKP applications are bound to emerge.
One of the most incredible things that researchers have learned about zero knowledge proofs is that every statement that has a proof also has a ZKP. The implications of this discovery are fascinating and it makes us confident that even though ZKP technology has its limits, its ceiling is incredibly high.
