Cryptography 101: Zero Knowledge Proofs (Part 3)
This is part of a larger series of articles about cryptography. If this is the first article you come across, I strongly recommend starting from the beginning of the series.
With the theory behind us, it’s time to get more practical!
In today’s article, I’d like to focus on some simple examples of statements we can prove using a zkSNARK such as Plonk. So, we’ll essentially be building some arithmetic circuits.
And I see no better start to this, than to reversion range proofs! Let’s jump straight into the action.
Range Proofs Revisited
During our not so brief look at Bulletproofs, we saw how hard it was to construct a range proof from scratch. But now, we have some new toys at our disposal. And as promised, we’ll see how we can build an arithmetic circuit to represent the statement:
There’s a valid N-bit representation for a number v
Building such a circuit allows us to prove knowledge of said number v using Plonk! So let’s try to put this into equations, again.
Really, this is the same system we described before. Thus, the upcoming description will be somewhat condensed — I recommend the previous explanation for more attention to detail!
If our number v can be represented with N bits, this means that there’s some valid binary representation for it:
And in turn, these numbers should suffice this equation:
We also know that all our inputs will be in a finite field of size q:
Both v and the bᵢ will be inputs to our circuit — thus, we need some way to prove that the bᵢ values are bits (either 0 or 1). And we can do this with the following check:
For each of the N bits.
Subtraction
Great! We’ve got the system… But how do we turn this into an arithmetic circuit? In particular, we need to be able to represent subtraction, but we can only use addition and multiplication gates. What to do then?
Well, when working with finite fields, there’s the concept of additive inverses! Think of subtracting 1, as being the same as adding -1. But, of course, -1 is not an element in our field:
How does this help, then? You see, just as we said that addition wrapped around to the beginning of the set when the result was bigger than q - 1, it’s also true that subtraction wraps around to the end of the set when the result is less than 0.
Really, what happens is that we can map -1 into the set by using the modulo operation:
You may also see this expressed as -1 ≡ q - 1 (mod q). This is called a congruence relation, and it reads “-1 is congruent with q - 1 modulo q”.
There’s a lot to say about congruence relations, which also define congruence classes — but we’ll avoid getting into those topics today. You can read about it here if you’re interested.
In conclusion, adding q - 1 has the exact same effect as subtracting 1!
This also works for additive groups.
Putting It Together
Now that we know how to subtract, we can craft our circuit!
To start with, we must check that bᵢ is a bit. This can be done in this fashion:
Of course, if we sum all of the outputs of these checks, the resulting value should also be 0.
Then, we need to represent the sum of every bit multiplied by the corresponding power of 2. Once we obtain the result, subtracting v should also yield 0. And as you might guess, subtracting v is the same as adding -v, which of course, is the result of multiplying -1 and v.
To keep things manageable, let’s say that N = 4. For this amount of bits, our circuit would look like:
And there you go! This circuit should output 0 if a number v and it’s binary representation b₀, b₁, b₂, and b₃ are fed into it. Of course, we don’t want to reveal neither of those — so they will be the private statement. All the other inputs can be though as part of the witness — just a bunch of values that allow for an efficient evaluation of the circuit.
If we refer back to our nomenclature from the previous article, then the secret information and the witness would be:
From here, all we do is apply Plonk as presented in the previous article, and then we have a zkSNARK to prove that v lies in the range 0 to 15. Sweet!
Set Membership
The previous example introduced a couple interesting ideas, such as how to subtract with gates. And implicitly, we also used some magic numbers as inputs, to avoid excessive computation.
Nevertheless, these are not the only tricks we can use when building circuits — as we’ll see in just a moment. Let’s move on to our next example to see what’s in store for us.
Imagine we have a set of values S:
What we’ll try to do is prove knowledge of a value sᵢ that belongs to said set. We’ll require some mathematical statement that represents this fact. This one is easy enough — here, I’ll just write the equation for you:
If sᵢ is indeed part of the set, then one of the terms will be zero, causing the entire product to yield 0. Otherwise, the value of P(x) will be some positive non-zero value.
This is, sᵢ are the roots of P(x).
Building a circuit for this polynomial is not hard. It would probably involve providing the values sᵢ as the witness, for faster computation, and for the protocol to make any sense at all. Like, what good is it to prove knowledge of a value in a set, if the verifier doesn’t know what set they’re talking about?
However, there seems to be a problem here: if S is public, then everybody can read it. So in theory, anyone could prove knowledge of some sᵢ in the set. Building a zero knowledge proof in that setting doesn’t really make much sense…
Hiding the Set
Fixing this is not hard: to make the set secret, we can hash every element, and make the hashed values public instead. The set now looks like:
With this adjustment, then knowing the set S’ reveals nothing about the actual values in S, which remain secret. Our equation also needs a slight modification:
Of course, the hashing function H must hash into our finite field, so we can use these values in our circuit.
Wonderful. Marvelous. Until… We notice that we need to include the hashing function in our circuit.
Okay, breathe. It’s not that bad. Of course, if we had to implement a circuit for a hashing function ourselves, it would be a real pain in the backside.
Luckily, some folks have already thought about this, and provide hashing functions as packages in some popular Domain-Specific Languages (DSLs) to build circuits, such as Circom.
For example, there’s Poseidon. You can find its implementation here.
Let’s just think of the hashing function as a box, which we’ll be including in our circuit, much like a component. With this in mind, our circuit would look like this:
Awesome! All that remains is to run this through Plonk — you know, computing the trace, encoding it, all the good stuff we already discussed in the previous chapter in the series.
Zero Check
Having a reusable hashing component to include in our circuits is certainly a nice idea. One may wonder if there are other actions or checks that we may want to reuse in a similar fashion — thus being a good target for this sort of black-boxing process.
Very similar to the process of creating computer components!
One very simple idea for such a component, is to build something that checks whether if some value is zero or not. This is, a function that does the following:
I mean, it could be useful… Who knows, right? Checking that some computations yield 0 in a big circuit might be necessary!
Let’s build such a component. Here’s an idea for it:
A closer step-by-step inspection reveals what this circuit is doing: the first three gates compute the expression:
If x is 0, then its inverse will also be zero, and the expression will yield 1. If x is not 0, then by definition we know that x.x⁻¹ = 1, and thus, the expression will return 0.
This is the reason why the output of this component is not at the last gate, but at the third one. So why is there a fourth gate? What purpose does it serve?
To answer the question, I’ll ask you: haven’t you noticed anything out of the ordinary in this circuit? Take a look at it again.
You’ll soon realize that this is the first time we use a modular inverse. It’s an input to our circuit — we just can’t compute modular inverses with addition and multiplication gates alone. And so, the value of the modular inverse must be provided.
Remember that in Plonk, we just check that the computation trace makes sense — it’s entirely fine that an inverse is provided as an input, as long as we make sure that the value is correct!
The idea is that the fourth gate exists as a means to check that the claimed modular inverse is in fact correct. And there are in total four possible scenarios to analyze, which you can corroborate yourself by following the circuit:
- x = 0: No matter what inverse we provide, the output will be 1. We don’t really care whether if the inverse is okay or not, which is consistent with the last gate always yielding 0.
- x ≠ 0, x = x⁻¹ ≠ 0: The inverse is correct, and the output is 0. The last gate should also yield 0, meaning that the inverse is correct.
- x ≠ 0, x⁻¹ = 0: The inverse is incorrect. The output will be 1 (which is wrong), and also, the last gate will not yield 0. Because the last constraint doesn’t hold, this means that something about the inputs is wrong!
- x ≠ 0, x ≠ x⁻¹ ≠ 0: The inverse is incorrect, and in this case, the output will not be 1, but some other element in the finite field. Because of this, the last gate will most certainly not yield 0 — and this means that the provided inverse is not correct.
And there you have it! Our zero checker circuit is done.
Having these simple elements that perform simple tasks can be hugely helpful as we build bigger and bigger circuits. It allows some degree of composability in the process, which can speed the crafting of your circuits dramatically!
Summary
These are just a few examples of the things you can do with arithmetic circuits: since they are such a general computation model, you can build just about any kind of statement.
Granted, creating the circuit itself might be a little challenging if we have to piece together a lot of gates ourselves. This is why we never really do.
We use other types of representations, which can be conceptualized as circuits.
Circom, which is a popular DSL for building circuits, doesn’t force you to write gates. Instead, it relies on a technique called arithmetization to transform a set of constraints into the adequate form for zkSNARKs.
Finally, SNARKs have a lot of benefits (small proof sizes, short verification times), but also there are some aspects that generate some degree of concern (for example, Plonk requires a trusted setup). For this reason (and others), this is still a very active research area. Who knows what we might see in the future!
Speaking about trusted setups and ideally avoiding them, there’s another type of succint proof of knowledge that doesn’t require it — it’s transparent. So in the next chapter of our adventure, we’ll explore the world of STARKs, the younger sibling of SNARKs that brings some interesting properties to the table. Until the next one!
