ZK-SNARK - Pinocchio protocol

File download:

• Dark
• White

Special thanks to Anton Levochko and ZK-DL lectures (zkdl-camp.github.io) for the base material for this post.

R1CS

When we describe any proving system we are basically operating on the concepts of “witness” (or “private input”), “public input” (or “public parameters”) and “constraints”. Constraints is a set of conditions that must be met by a witness in a couple with public input to produce a valid proof.

Usually to describe how constraints are combined (mathematically) with inputs we are using arithmetic circuits. Arithmetic circuit is an acyclic graph that consists of an “input”-vertexes and an “action”-vertexes (also called ” gates”). Each “input”-vertex contains an input value and a direction where it should be applied. On the other hand each gate contains a set of input edges (usually two), a set of output edges (usually zero or one) and an operation to be applied to the inputs. The result of this operation is directed by an output edge if exists.

Next we are going to describe the constraint system by using the vector spaces, matrices, their properties and operations, in particular - inner product: $⟨\mathbf{a},\mathbf{b}⟩=\sum a_i\cdot b_i$.

R1CS (Rank-1 constrain system) is a way to describe constraints and how they are applied to the witness and the public input. It has the following form: $⟨\mathbf{a},\mathbf{w}⟩\cdot ⟨\mathbf{b},\mathbf{w}⟩=⟨\mathbf{c},\mathbf{w}⟩$, where $\mathbf{a},\mathbf{b},\mathbf{c}$ is a public vectors that determines the linear combinations of our witness.

Let’s examine several self-describing examples of the simple R1CS circuits.

Simplest circuit

The simplest circuit consist of the only one multiplication gate: $r=x_1\cdot x_2$. The witness then consists of three values $\mathbf{w}=(r,x_1,x_2)$ and it has to satisfy our R1CS equation. Then, the tuple $\mathbf{a},\mathbf{b},\mathbf{c}$ is obvious: $\mathbf{a}=(0,1,0),\mathbf{b}=(0,0,1)$ and $\mathbf{c}=(1,0,0)$.

Hints

More complex circuits require us to examine several hits:

1. Boolean check: if we are using the input value that has to represent a boolean [equals to 1 (true) or to 0 (false)] then we should provide a corresponding check to restrict putting any arbitrary value instead of boolean. This can be achieved by including a simple check that $x\cdot (x-1)=0$ or $x\cdot x=x$.
2. Conditional statement: if our circuit contains a conditional statement that affects the execution flow - we can combine both calculation branches by putting $x\ast f_{true}(\mathbf{x})+(1-x)\ast f_{false}(\mathbf{x})$.
3. Most circuits require the usage of constants in linear combinations that allows us multiplication by a constant or a constant addition. By putting $1$ into witness we can achieve any constant by manipulating the coefficients in $\mathbf{a},\mathbf{b},\mathbf{c}$.

More complex circuit

Let’s examine the following procedure:

def r(x1,x2,x3):
  if x1:
    return x2 * x3
  else:
    return x2 + x3

According to the hints described above, it can be represented as $r=x_1\cdot (x_2\cdot x_3)+(1-x_1)\cdot (x_2+x_3)$. Also, we have to add the check for $x_1$ boolean properties, so the final constraints can be expressed as follows:

1. $x_1\cdot x_1=x_1$ (binary check)
2. $A=x_2\cdot x_3$ (multiplication for “true” branch)
3. $B=x_1\cdot A$ (selected “true” branch)
4. $(1-x_1)\cdot (x_2+x_3)=r-B$ (final equation)

These constraints have to be encoded into the R1CS equation with the witness $\mathbf{w}=(1,r,x_1,x_2,x_3,A,B)$.

The resulting $\mathbf{a},\mathbf{b},\mathbf{c}$ for each of our four constraints are:

constraint	a	b	c
1 (binary check)	(0, 0, 1, 0, 0, 0, 0)	(0, 0, 1, 0, 0, 0, 0)	(0, 0, 1, 0, 0, 0, 0)
2 (multiplication for “true” branch)	(0, 0, 0, 1, 0, 0, 0)	(0, 0, 0, 0, 1, 0, 0)	(0, 0, 0, 0, 0, 1, 0)
3 (selected “true” branch)	(0, 0, 1, 0, 0, 0, 0)	(0, 0, 0, 0, 0, 1, 0)	(0, 0, 0, 0, 0, 0, 1)
4 (final equation)	(1, 0, −1, 0, 0, 0, 0)	(0, 0, 0, 1, 1, 0, 0)	(0, 1, 0, 0, 0, 0, −1)

These separate R1CS constraints can be put together into the 4-dimensional matrix to represent one equation.

Why Rank-1?

You can search for the proof that each R1CS equation can be represented using special matrix, that equals to the outer product of vectors $\mathbf{a},\mathbf{b}$ and this matrix rank will be $1$ (which means that each column/row can be represented by other column/row by multiplying on a certain constant).

QAP

So, above we described an approach to characterize the polynomial constrains in the R1CS form: $⟨\mathbf{a},\mathbf{w}⟩\cdot ⟨\mathbf{b},\mathbf{w}⟩=⟨\mathbf{c},\mathbf{w}⟩$. Where the one constraint is represented by a public $\mathbf{a},\mathbf{b},\mathbf{c}$ vectors. In an example with a more complex circuit, we’ve generated 4 constrains, so we will have 4 tuples of vectors - each tuple for its corresponding constraint. Of course, it seems to be very difficult to prove big circuits using only R1CS - that is why we may want to build more efficient system based on R1CS. This system is called Quadratic Arithmetic Program (QAP).

At the beginning, we should recheck our note in previous post, where I’ve mentioned that we can combine all tuples $\mathbf{a},\mathbf{b},\mathbf{c}$ into the corresponding matrices $A,B,C$ and represent our final R1CS circuit as: $A\mathbf{w}+B\mathbf{w}=C\mathbf{w}$. Then, for each column $j$ (that corresponds to the witness’s $j$-th value) we want to build a polynomial $p_j(X)$ where for each constraint $i\in \{1,2,...\}$ the $p_j(i)$ equals to the corresponding $j$-th witness element coefficient in the constraint $i$. This can be done using any appropriate interpolation method (and not only on $X\in \{1,2,...\}$ - we can use any fixed set of indexed values for interpolation if corresponding algorithm requires such). Then, receiving polynomials $A_i(X),B_i(X),C_i(X)$ for each column of $A,B,C$ matrices we can rewrite our R1CS as: $(w_1{A}_1(X)+...+w_n{A}_n(X))\cdot (w_1{B}_1(X)+...+w_n{B}_n(X))=$ $(w_1{C}_1(X)+...+w_n{C}_n(X))$ evaluated on $X\in \{1,2,...\}$ domain.

Let’s rename the parts of this equation as: $A(X)=(w_1{A}_1(X)+...+w_n{A}_n(X))$, $B(X)=(w_1{B}_1(X)+...+w_n{B}_n(x))$, $C(X)=(w_1{C}_1(X)+...+w_n{C}_n(X))$. Then, our R1CS will have form of $A(X)+B(X)=C(X)$.

We can mention that $A(X)+B(X)-C(X)$ equals to some polynomial $M(X)$ that has zeros in $X\in \{1,2,...\}$. To convince the verifier that we know such polynomial with corresponding zeros, we can use the popular principle - proving the knowledge of such polynomial $H(X)=\frac{M(X)}{Z(X)}$ (where $Z(X)=\prod (X-i)$ is known for everyone) by proving the knowledge of such polynomials that holds the equation $AB-C=HZ$.

The algorithm of proving for this relation lies on the Schwartz–Zippel lemma: for the polynomial $P\in F[x]$ of degree $d$ and uniformly selected $t\in F$ the probability of $P(t)=0$ equals to $\frac{d}{|F|}$.

This lemma becomes very useful when we want to prove the knowledge of a polynomial by evaluating it at a random point. If this evaluation can be equal to zero - such proving system does not make any sense, but when the probability of such event is small enough verifier can be sure that evaluation is correct.

So, we consider the following protocol:

1. Prover shares the coefficients of $H(X)$ named $\mathbf{h}=(h_0,h_1,...h_{n-1})$
2. Verifier selects random $\gamma$ and sends $\gamma =({\gamma }^0,{\gamma }^1,...{\gamma }^{n-1})$
3. Prover responds with the following values ${\pi }_A=A(\gamma ),{\pi }_B=B(\gamma ),{\pi }_C=C(\gamma ),{\pi }_M=Z(\gamma )\cdot ⟨\gamma ,\mathbf{h}⟩$.
4. Verifier accepts if ${\pi }_A{\pi }_B-{\pi }_C={\pi }_M$

Ok, this protocol follows the correctness property, but how about the soundness and zero-knowledge? The proof values queried by the verifier open lots of information about the witness, because the interpolated polynomials over the witness coefficients columns are public and can be calculated by everyone. To deal with this problem we are moving the next protocol called Proof of exponent.

Proof of exponent

Imagine, we have a polynomial $p(x)$ and we want to convenience the verifier that it is divisible by the other public polynomial $t(x)$. Then, we consider the following protocol: verifier shares a powers of tau $\{g^{{\tau }^i}\}$ for some generator $g$ - the securely generated powers of a randomly selected $\tau$ in such way that nobody knows the $\tau$ itself. Then, prover calculates the polynomial encryption for $p(x)$ in the following way: $g^{p(\tau )}=\sum (g^{{\tau }^i}{)}^{a_i}$, where $a_i$ is the coefficients of the $p(x)$. The same is done for $h(\tau )=\frac{p(\tau )}{t(\tau )}$. The verifier checks that $g^{p(\tau )}=(g^{h(\tau )}{)}^{t(\tau )}$.

Unfortunately, it is not enough to reach the soundness property - prover still can manipulate values of $h(\tau )=r$ to produce a valid proof where $g^{r\cdot t(\tau )}=(g^r{)}^{t(\tau )}$. That is why we should add “shifted” evaluation of our polynomials by some randomly selected $\alpha$ (in the same way as powers of tau): verifier additionally shares $g^{\alpha \cdot {\tau }^i}$ with the prover, and the prover adds to the response the shifted polynomial encryption $g^{p(\alpha \tau )}$. Then, the verifier adds check for $g^{p(\alpha \tau )}=(g^{p(\tau )}{)}^{\alpha }$. While the raw values of $\alpha$ and $\tau$ are not accessible by the prover we reach the soundness property.

Unfortunately (x2), we still have not reached zero-knowledge. Because the $\tau$ and $\alpha$ seems to be generated by verifier, we should additionally add our “own shifts” to hide our polynomials in case when the $\tau$ and $\alpha$ setup is compromised. It’s actually quite simple: during the proving phase we select random $\delta$ and additionally multiply all our polynomials by it (share $g^{\delta p(\alpha \tau )}$ instead of $g^{p(\alpha \tau )}$ and same for other polynomial encryptions). While still verifiable it perfectly hides all information about polynomials even if the raw values of $\tau$ or $\alpha$ is known by somebody.