Let’s dissect a zkSNARK! (part 1)
What exactly is a zkSNARK, you ask? Well, today we’re going to answer that question by peeking into the rabbit hole.
First of all, what exactly is a zkSNARK?
zkSNARKs stand for zero-knowledge Succinct Non-interactive ARguments of Knowledge. They are essentially a proof that some computation (with potentially private inputs) has been run. Every step of the computation is encoded into a polynomial equation (yes, the same ones you had to do back in high school) and a small proof consisting of a few tens to hundreds of numbers is created.
A powerful use case for SNARKs
Like I alluded to in my previous post, Zero Knowledge Proofs (and those of the SNARK or STARK variety) are extremely tantalizing to people who want to scale blockchain computation because they can offload computation to more powerful computers in a trustless manner, while allowing parties with lower compute power to easily verify that the computation was done correctly. They don’t even necessarily need to use the Zero Knowledge property of a zkSNARK! In fact, Zero Knowledge Rollups are currently built on top of Ethereum using this verifiable computation model.
Taking a step back, what exactly does a “computation” mean, anyway? Simply put, every transaction on a blockchain is a computation or series of computations. For example, every full node on Ethereum must replay every single transaction on the blockchain to ensure that it leads to a valid state change. This leads to Ethereum’s security, but also prevents the network from increased throughput and causes network usage to be expensive, especially during high load times.
However, instead of requiring every single full node to replay every single transaction, zkRollups are able to utilize much more powerful computers to build blocks of transactions, create a proof that the block was computed correctly, and allow anyone to quickly and easily verify that this was the case. Without this succinct proof of computational integrity (or naïvely replaying transactions) , the nodes in the ecosystem that build blocks of transactions could potentially alter or remove any transactions they want.
You might be wondering how this is different than just hashing the computation or data. With hashing, you won’t be able to check in a succinct way that every step of the computation was done correctly, you’d just have the final hash at the end. The big difference is that creating a SNARK proof means turning every step of the computation into a mathematical system of equations in a process called arithmetization. The way the proof is created and its structure is small enough for any third party (called a Verifier) to check with a high degree of certainty that all steps of the computation were run correctly.
A little zkSNARK math primer
Now, with all of that out of the way, let’s get back to it. In order to understand SNARKs, we’ll need to build a little bit of understanding of some of the mathematical concepts behind them. We’ll assume knowledge of hash functions, but if not there’s many resources available online. The following sections will focus more on some of the more mathematical concepts required to understand SNARKs.
Finite Fields
zkSNARKs work on finite fields with a prime order. A finite field is a finite set of elements (positive integers, in this case) in which the operations of addition, subtraction, multiplication, and division are closed on them. Being closed means that any operation on two elements of the field results in another element in the field.
The order of a finite field is the number of elements in the field. Finite fields of a prime order have a number of elements that are a prime number. A finite field with order 7 contains the numbers {0, 1, 2, 3, 4, 5, 6}. Every finite field has a prime order or an order of a prime raised to some power.
Modular Arithmetic
When doing mathematical operations on the field elements, they will wrap around in either direction (the closed property described above). This is called modular arithmetic, and is denoted by the operator mod. Therefore, 3 + 6 = 9 mod 7 = 2 (since 9 is outside of the field {0, …, 6}, we wrap around to 9 - 7 = 2).
One way to think of it You can think of it like operations on a clock (but instead of 12 o’clock, we’ll use 0 instead, so we’ll have a finite field with elements {0, 1, 2, …, 11}. If you count past 11, you get back to 0.
So, if you we are to start at 9 o’clock and to add 6 hours, we land at 3 o’clock (and not 15 o’clock, unless you’re in one of those 24-hour countries).
Similarly, for multiplication on this clock, we can do the same: 5 * 5 = 25 mod 12 = 1 (25 / 12 = 2, remainder 1).
Arithmetic Circuits
In order for a zkSNARK proof to be created, it must first be turned into an arithmetic circuit through a process called arithmetization. You can think of an arithmetic circuit as a way of showing a mathematical equation in a visual form, in which two inputs go into a mathematical operation and give an output. For example, 2 + 3 = 5 can be modeled like so:
Each operator, such as the (+) above is called a gate. In order to model more complex circuits, more gates are used. For example, we can model the equation (2 + 3) * (2 + 1) as a circuit as well:
Much larger circuits can represent much larger systems. The logic for a zkSNARK proof is written in a programming language (such as Circom or Noir) that specifies what inputs, outputs, and intermediate signals are valid. That program is then turned is then turned into an arithmetic circuit, which allows a prover to provide some public and private inputs, run the computation against the circuit, and get a succinct proof, which can be easily verified by a verifier. These calculations are all done within a prime field, so if we are operating on the finite field with order 7, (2 + 3) * (2 + 1) = 15 mod 7 = 1.
Summary
That’s a good place to stop for today. This time, we reviewed some of the basic mathematical principles that are the foundation for how zkSNARKs work. In the next session, we’ll cover a bit more about how you actually go from a computation to a SNARK. Stay tuned!
