QAP - Quadratic Arithmetic Program

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

In the previous post, I’ve described an approach to characterize the polynomial constrains in the R1CS form: \(\langle \mathbf{a}, \mathbf{w} \rangle \cdot \langle\mathbf{b}, \mathbf{w}\rangle = \langle\mathbf{c}, \mathbf{w}\rangle\). 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_1A_1(X) + ... + w_nA_n(X)) \cdot (w_1B_1(X) + ... + w_nB_n(X)) =\) \((w_1C_1(X) + ... + w_nC_n(X))\) evaluated on \(X \in \{1, 2,...\}\) domain.

Let’s rename the parts of this equation as: \(A(X) =(w_1A_1(X) + ... + w_nA_n(X))\), \(B(X) =(w_1B_1(X) + ... + w_nB_n( x))\), \(C(X) =(w_1C_1(X) + ... + w_nC_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 \(\mathbf{\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 \langle \mathbf{\gamma}, \mathbf{h}\rangle\).
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.

Yes, one more article about R1CS

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

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: \(\langle \mathbf{a}, \mathbf{b}\rangle = \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: \(\langle \mathbf{a}, \mathbf{w} \rangle \cdot \langle\mathbf{b}, \mathbf{w}\rangle = \langle\mathbf{c}, \mathbf{w}\rangle\), 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 * f_{true}(\mathbf{x}) + (1 - x) * 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:

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).

The Crypto Anarchist Manifesto

A specter is haunting the modern world, the specter of crypto anarchy. Computer technology is on the verge of providing the ability for individuals and groups to communicate and interact with each other in a totally anonymous manner. Two persons may exchange messages, conduct business, and negotiate electronic contracts without ever knowing the True Name, or legal identity, of the other. Interactions over networks will be untraceable, via extensive re- routing of encrypted packets and tamper-proof boxes which implement cryptographic protocols with nearly perfect assurance against any tampering. Reputations will be of central importance, far more important in dealings than even the credit ratings of today. These developments will alter completely the nature of government regulation, the ability to tax and control economic interactions, the ability to keep information secret, and will even alter the nature of trust and reputation. The technology for this revolution - and it surely will be both a social and economic revolution - has existed in theory for the past decade. The methods are based upon public-key encryption, zero-knowledge interactive proof systems, and various software protocols for interaction, authentication, and verification. The focus has until now been on academic conferences in Europe and the U.S., conferences monitored closely by the National Security Agency. But only recently have computer networks and personal computers attained sufficient speed to make the ideas practically realizable. And the next ten years will bring enough additional speed to make the ideas economically feasible and essentially unstoppable. High-speed networks, ISDN, tamper-proof boxes, smart cards, satellites, Ku-band transmitters, multi-MIPS personal computers, and encryption chips now under development will be some of the enabling technologies. The State will of course try to slow or halt the spread of this technology, citing national security concerns, use of the technology by drug dealers and tax evaders, and fears of societal disintegration. Many of these concerns will be valid; crypto anarchy will allow national secrets to be trade freely and will allow illicit and stolen materials to be traded. An anonymous computerized market will even make possible abhorrent markets for assassinations and extortion. Various criminal and foreign elements will be active users of CryptoNet. But this will not halt the spread of crypto anarchy. Just as the technology of printing altered and reduced the power of medieval guilds and the social power structure, so too will cryptologic methods fundamentally alter the nature of corporations and of government interference in economic transactions. Combined with emerging information markets, crypto anarchy will create a liquid market for any and all material which can be put into words and pictures. And just as a seemingly minor invention like barbed wire made possible the fencing-off of vast ranches and farms, thus altering forever the concepts of land and property rights in the frontier West, so too will the seemingly minor discovery out of an arcane branch of mathematics come to be the wire clippers which dismantle the barbed wire around intellectual property. Arise, you have nothing to lose but your barbed wire fences!

by Timothy C. May

Private coins extension with verifiable encryption

One of the existing problems of non-SNARK confidential assets protocols based on Pedersen commitments is to disability for coins receiver to decrypt an amount in the received payment. To achieve private decommitment, sender has to share the amount in a secure way with the receiver that often is not a part of a protocol. I’ve made some research and described the option to use private payments in a couple with verifiable encryption, that allows sender to share amount securely with receiver and convince the receiver that this amount corresponds to the committed one.

Check my article for more: Private coins extension with verifiable encryption

ZK-STARK explained paper release 🎉

Still continuing my series of articles on advanced cryptographic protocols explained in simple words. Here is a paper about ZK-STARK protocol.

Enjoy! ZK-STARKs explained