Building a Zero Knowledge Proof from an R1CS

Given a circuit encoded as a rank 1 constraint system, it is possible to create a zk-proof of having a witness, albeit not a succinct one. This article describes how to accomplish that.

Prerequisites

Rank 1 Constraint Systems Bilinear Pairings

Definitions for R1CS

Given an n quadratic polynomial constraints, with a total of m variables, we encode it as

Ls⊙Rs=Os

Where L, R, O are matrices with n rows and m columns, and s is the solution vector with 1 column and m rows and ⊙ is element-wise multiplication (Hadamard product).

In expanded form, it looks like

In this setup, we can prove to a verifier that we have a valid vector s simply by giving them the vector s, but with the obvious drawback that this is not a zero knowledge proof!

Zero knowledge proof algorithm for an R1CS.

If we “encrypt” the witness vector by multiplying each entry with G₁ or G₂, the math will still work properly!

Notation for elliptic curves

We say [aG₁]₁ is a G₁ elliptic curve point created from multiplying the field element a by G₁. We say [aG₂]₂ is a G₂ elliptic curve point generated by multiplying a with the generator G₂. Because of the discrete log problem, we cannot extract a given [aG₁]₁ or [aG₂]₂.

Prover steps

Let’s encrypt our s vector by multiplying each entry with the generator point G₁ to produce the elliptic curve point [sᵢG₁]₁.

For the matrix L, we are doing the following:

In anticipation of the Hadamard product becoming a list of elliptic curve pairings, we can use G₂ points to encrypt the remaining s vector so the verifier can do the pairing.

After this operation, we have a single column of elliptic curve points in G₁ originating from Ls and a single column of G₂ points from Rs.

The naive next step would be to encrypt the s vector with G₁₂ points so that the verifier can do the pairing, but G₁₂ points are massive, so we would rather have the verifier pair the Os elliptic curve points in G₁ then pair each entry with a G₂ point. Pairing with a G₂ point is, in a sense, "multipying by one" but turning the G₁ point into a G₁₂ point.

The prover then hands the G₁ vector and the G₂ vector to the verifier.

Verification step

Thus, the verification step becomes

The above vectors of G₁₂ elements will be element-wise equal if and only if the prover has provided a valid witness.

Well, almost. We’ll get to that in a following section.

First we need to mention an important implementation detail

Public inputs

If our knowledge claim is “I know x such that x³ + 5x + 5 = 155”, then our witness vector will probably look like the following:

[1, out, x, v], where v = x*x. In this case, we need [1, out] to be public. To accomplish that, we simply don’t encrypt the first two elements of the witness. The verifier will check the public outputs, then encrypt the public inputs by multiplying them with a G₁ or G₂ point so that the verification formula does not change.

Dealing with a malicious prover.

Because the vectors are encrypted, the verifier cannot immediately know if the vector of G₁ points encrypts the same values as the vector of G₂ points.

However, the verifier can check for their equality with some extra steps.

This is left as an exercise for the reader.

This algorithm is mostly academic

Before you get too nerdsniped by the problem above, note that this algorithm is very inefficient for the verifier. If the matrices in the R1CS are large (and for interesting algorithms, they will be), then the verifier has a lot of pairings and elliptic curve additions to do. Elliptic curve addition is rather fast, but elliptic curve pairings are slow (and cost a lot of gas on Ethereum).

However, it is nice to see that at this stage, zero knowledge proofs are possible, and if you have a good grasp of elliptic curve operations (and haven’t forgotten your matrix arithemtic), they aren’t hard to understand.

Making this technique truly zero knowledge

As it is right now, our witness vector cannot be decrypted, however it can be guessed. If an attacker (someone trying to discover the unencrypted witness) uses some auxiliary information to make an educated guess at the witness, they can check their work by multiplying their guessed witness vector by the elliptic curve point generators and seeing if the result is the same as the prover’s witness vectors.

We will learn how to defend against witness guessing in our coverage of groth16.

Also, keep in mind nobody does the described algorithm in the real world, as it is too inefficient. However, if you implement it, it will help you practice implementing meaningful elliptic curve arithmetic and build a functional end-to-end (almost) zero knowledge proof.

Learn more with RareSkills

This material is from our Zero Knowledge Course.