cryptologie.net

In this ninth video, I explain what polynomial commitment schemes are as well as their API. I also mention the Kate polynomial commitment scheme (KZG), based on pairings, and bootle/bulletproof types of polynomial commitments schemes, based on inner products.

Part 10 is here. Check the full series here.

In this eighth video, I explain how the prover and the verifier can perform a “polynomial dance” in order to construct the circuit polynomial $f$. The principle is simple: the prover doesn’t want to leak information about the private inputs and the intermediary values in the circuit, and the verifier doesn’t want to give the prover too much freedom in the way they construct the circuit polynomial $f$.

Part 9 is here. Check the full series here.

In this seventh video, I explain how we use our circuit polynomial $f$ in a protocol between a prover and a verifier to prove succinctly that $f$ vanishes on a number of specified points.

Stay tuned for part 9… Part 8 is here. Check the full series here.

In this sixth video, I explain the compilation, or even compression, of a set of equations into a single polynomial. That polynomial represents all of our constraints, as long as it vanishes in an agreed set of points. With a polynomial in hand, we will be able to create a protocol with our polynomial-based proof system.

Part 7 is here. Check the full series here.

In this fifth video, I explain how we can “compile” an arithmetic circuit into something PLONK can understand: a constraint system. Specifically, a PLONK-flavored constraint system, which is a series of equations that must if equal to zero correctly describe our program (or circuit).

Part 6 is here. Check the full series here.

In this fourth video, I explain the “arithmetization” of our program into so-called arithmetic circuits. You can see this as “encoding” programs into math, so that we can use cryptography on them.

Part 5 is here. Check the full series here.

In this third video, I start by explaining what the protocol will use at the end: polynomials. It’ll give you a glimpse as to what direction we’ll be taking when we transform our program into something we can prove.

Part 4 is here. Check the full series here.

In this second video, I give some intuition on how to think about zero-knowledge proof systems, with the example of proving the solution of a sudoku, then I give an overview of what I’ll explain in this series of video.

Part 3 is here. Check the full series here.

I recently got into general-purpose zero-knowledge proof systems (cryptographic primitives that allow you to prove the execution of a program without revealing some of the inputs), specifically the state-of-the-art PLONK proof system. This is a series of video I made to explain what I understood and learned in the past few months. There might be some inaccuracies, so I apologize in advance for that. You can check all the videos via the playlist here: https://www.youtube.com/watch?v=RUZcam_jrz0&list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

In this first video, I simply explain what general-purpose zero-knowledge proofs are, specifically zk-SNARKs, and what PLONK is.

Part 2 is here.

The inner product argument is the following construction: given the commitments (for now let’s say the hash) of two vectors $\overrightarrow{a}$ and $\overrightarrow{b}$ of size $n$ and with entries in some field $𝔽$, prove that their inner product $⟨\overrightarrow{a},\overrightarrow{b}⟩$ is equal to $z$.

There exist different variants of this inner product argument. In some versions, none of the values ($\overrightarrow{a}$, $\overrightarrow{b}$ and $z$) are given, only commitments. In some other version, which is interesting to us and that I will explain here, only $\overrightarrow{a}$ is unknown.

How is that useful?

Inner products arguments are useful for several things, but what we’re using them for in Mina is polynomial commitments. The rest of this post won’t make too much sense if you don’t know what a polynomial commitment is, but briefly: it allows you to commit to a polynomial $f$ and then later prove its evaluation at some point $s$. Check my post on Kate polynomial commitments for more on polynomial commitment schemes.

How does that translate to the inner product argument though? First, let’s see our polynomial $f$ as a vector of coefficients:

Then notice that

And here’s our inner product again.

The idea behind Bootleproof-type of inner product argument

The inner product argument protocol I’m about to explain was invented by Bootle et al. It was later optimized in the Bulletproof paper (hence why we unofficially call the first paper bootleproof), and then some more in the Halo paper. It’s the later optimization that I’ll explain here.

A naive approach

So before I get into the weeds, what’s the high-level? Well first, what’s a naive way to prove that we know the pre-image of a hash $h$, the vector $\overrightarrow{a}$, such that $⟨\overrightarrow{a},\overrightarrow{b}⟩=z$? We could just reveal $\overrightarrow{a}$ and let anyone verify that indeed, hashing it gives out $h$, and that it also verifies the equation $⟨\overrightarrow{a},\overrightarrow{b}⟩=z$.

Obliviously, we have to reveal $\overrightarrow{a}$ itself, which is not great. But we’ll deal with that later, trust me. What we want to tackle first here is the proof size, which is the size of the vector $\overrightarrow{a}$. Can we do better?

Reducing the problem to a smaller problem to prove

The inner product argument reduces the opening proof by using an intermediate reduction proof:

Where the size of $\overrightarrow{a^{\prime }}$ is half the size of $\overrightarrow{a}$, and as such the final opening proof ($\overrightarrow{a^{\prime }}$) is half the size of our naive approach.

The reduction proof is where most of the magic happens, and this reduction can be applied many times ($lo{g}_2(n)$ times to be exact) to get a final opening proof of size 1. Of course the entire proof is not just the final opening proof of size 1, but all the elements involved in the reduction proofs. It can still be much smaller than the original proof of size $n$.

So most of the proof size comes from the multiple reduction subproofs that you’ll end up creating on the way. Our proof is really a collection of miniproofs or subproofs.

One last thing before we get started: Pedersen hashing and commitments

To understand the protocol, you need to understand commitments. I’ve used hashing so far, but hashing with a hash function like SHA-3 is not great as it has no convenient mathematical structure. We need algebraic commitments, which will allow us to prove things on the committed value without revealing the value committed. Usually what we want is some homomorphic property that will allow us to either add commitments together or/and multiply them together.

For now, let’s see a simple non-hiding commitment: a Pedersen hash. To commit to a single value $x$ simply compute:

where the discrete logarithm of $G$ is unknown. To open the commitment, simply reveal the value $x$.

We can also perform multi-commitments with Pedersen hashing. For a vector of values $(x_1,\cdots ,x_k)$, compute:

where each $G_i$ is distinct and has an unknown discrete logarithm as well. I’ll often shorten the last formula as the inner product $⟨\overrightarrow{x},\overrightarrow{G}⟩$ for $\overrightarrow{x}=(x_1,\cdots ,x_k)$ and $\overrightarrow{G}=(G_1,\cdots ,G_k)$. To reveal a commitment, simply reveal the values $x_i$.

Pedersen hashing allow commitents that are non-hiding, but binding, as you can’t open them to a different value than the originally comitted one. And as you can see, adding the commitment of $x$ and $y$ gives us the commitment of $x+y$:

which will be handy in our inner product argument protocol

The protocol

Set up

Here are the settings of our protocol. Known only to the prover, is the secret vector

The rest is known to both:

• $\overrightarrow{G}=(G_1,G_2,G_3,G_4)$, a basis for Pedersen hashing
• $A=⟨\overrightarrow{a},\overrightarrow{G}⟩$, the commitment of $\overrightarrow{a}$
• $\overrightarrow{b}=(b_1,b_2,b_3,b_4)$, the powers of some value $s$ such that $\overrightarrow{b}=(1,s,s^2,s^3)$
• the result of the inner product $z=⟨\overrightarrow{a},\overrightarrow{b}⟩$

For the sake of simplicity, let’s pretend that this is our problem, and we just want to halve the size of our secret vector $\overrightarrow{a}$ before revealing it. As such, we will only perform a single round of reduction. But you can also think of this step as being already the reduction of another problem twice as large.

We can picture the protocol as follows:

1. The prover first sends a commitment to the polynomial $f$.
2. The verifier sends a point $s$, asking for the value $f(s)$. To help the prover perform a proof of correct evaluation, they also send a random challenge $x$.
3. The prover sends the result of the evaluation, $z$, as well as a proof.

Does that make sense? Of course what’s interesting to us is the proof, and how the prover uses that random $x$.

Reduced problem

First, the prover cuts everything in half. Then they use $x$ to construct linear combinations of these cuts:

• $\overrightarrow{a^{\prime }}=x^{-1}\left(\begin{array}{c}{a}_1\\ a_2\end{array}\right)+x\left(\begin{array}{c}{a}_3\\ a_4\end{array}\right)$
• $\overrightarrow{b^{\prime }}=x\left(\begin{array}{c}{b}_1\\ b_2\end{array}\right)+x^{-1}\left(\begin{array}{c}{b}_3\\ b_4\end{array}\right)$
• $\overrightarrow{G^{\prime }}=x\left(\begin{array}{c}{G}_1\\ G_2\end{array}\right)+x^{-1}\left(\begin{array}{c}{G}_3\\ G_4\end{array}\right)$

This is how the problem is reduced to $⟨\overrightarrow{a^{\prime }},\overrightarrow{b^{\prime }}⟩=z^{\prime }$.

At this point, the prover can send $\overrightarrow{a^{\prime }}$, $\overrightarrow{b^{\prime }}$, and $z^{\prime }$ and the verifier can check if indeed $⟨\overrightarrow{a^{\prime }},\overrightarrow{b^{\prime }}⟩=z^{\prime }$. But that wouldn’t make much sense would it? Here we also want:

• a proof that proving that statement is the same as proving the previous statement ($⟨\overrightarrow{a},\overrightarrow{b}⟩=z$)
• a way for the verifier to compute $z^{\prime }$ and $b^{\prime }$ and $A^{\prime }$ (the new commitment) by themselves.

The actual proof

The verifier can compute $\overrightarrow{b^{\prime }}$ as they have everything they need to do so.

What about $A^{\prime }$, the commitment of $\overrightarrow{a^{\prime }}$ which uses the new $\overrightarrow{G^{\prime }}$ basis. It should be the following value:

So to compute this new commitment, the verifier needs:

• the previous commitment $A$, which they already have
• some powers of $x$, which they can compute
• two curve points $L_a$ and $R_a$, which the prover will have to provide to them

What about $z^{\prime }$? Recall:

• $\overrightarrow{a^{\prime }}=\left(\begin{array}{c}{x}^{-1}{a}_1+x{a}_3\\ x^{-1}{a}_2+x{a}_4\end{array}\right)$
• $\overrightarrow{b^{\prime }}=\left(\begin{array}{c}x{b}_1+x^{-1}{b}_3\\ x{b}_2+x^{-1}{b}_4\end{array}\right)$

So the new inner product should be:

Similarly to $A^{\prime }$, the verifier can recompute $z^{\prime }$ from the previous value $z$ and two scalar values $L_z$ and $R_z$ which the prover needs to provide.

So in the end, the proof has becomes:

• the vector $\overrightarrow{a^{\prime }}$ which is half the size of $\overrightarrow{a}$
• the $L_a,R_a$ curve points (around two field elements, if compressed)
• the $L_z,R_z$ scalar values

We can update our previous diagram:

In our example, the naive proof was to reveal $\overrightarrow{a}$ which was 4 field elements. We are now revealing instead 2 + 2 + 2 = 6 field elements. This is not great, but if $\overrightarrow{a}$ was much larger (let’s say 128), the reduction in half would still be of 64 + 2 + 2 = 68 field elements. Not bad no? We can do better though… Stay tuned for the next post.