Skip to main content
Try out the RareSkills ZK AI Tutor!
The RareSkills Book of Zero Knowledge

Building a Zero Knowledge Proof from an R1CS

Last updated on Nov 12, 2026

Given an arithmetic 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.

A zero knowledge proof for an R1CS is accomplished by converting the witness vector into finite field elliptic curve points and replacing the Hadamard product with a bilinear pairing for each row.

Given a Rank 1 Constraint System where each matrix has n rows and m columns, we write it as

๐‹๐šโˆ˜๐‘๐š=๐Ž๐š

Where ๐‹, ๐‘, ๐Ž are matrices with n rows and m columns, and ๐š is the witness vector (containing a satisfying assignment to each of the signals in the arithmetic circuit). The vector ๐š has 1 column and m rows and โˆ˜ is element-wise multiplication (Hadamard product).

In expanded form, it looks like

[l1,1โ‹ฏl1,mโ‹ฎโ‹ฑโ‹ฎln,1โ‹ฏln,m][a1โ‹ฎam]โˆ˜[r1,1โ‹ฏr1,mโ‹ฎโ‹ฑโ‹ฎrn,1โ‹ฏrn,m][a1โ‹ฎam]=[o1,1โ‹ฏo1,mโ‹ฎโ‹ฑโ‹ฎon,1โ‹ฏon,m][a1โ‹ฎam]
=[a1l1,1+โ‹ฏ+aml1,mโ‹ฎa1ln,1+โ‹ฏ+amln,m]โˆ˜[a1r1,1+โ‹ฏ+amr1,mโ‹ฎa1rn,1+โ‹ฏ+amrn,m]=[a1o1,1+โ‹ฏ+amo1,mโ‹ฎa1on,1+โ‹ฏ+amon,m]
=[โˆ‘i=1mail1,iโˆ‘i=1mail2,iโ‹ฎโˆ‘i=1mailn,i]โˆ˜[โˆ‘i=1mair1,iโˆ‘i=1mair2,iโ‹ฎโˆ‘i=1mairn,i]=[โˆ‘i=1maio1,iโˆ‘i=1maio2,iโ‹ฎโˆ‘i=1maion,i]
=โˆ‘i=1mail1,iโˆ‘i=1mair1,i=โˆ‘i=1maio1,iโˆ‘i=1mail2,iโˆ‘i=1mair2,i=โˆ‘i=1maio2,iโ‹ฎโˆ‘i=1mailn,iโˆ‘i=1mairn,i=โˆ‘i=1maion,i

In this setup, we can prove to a verifier that we have a witness vector ๐š that satisfies the R1CS simply by giving them the vector ๐š, 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 G1 or G2, the math will still work properly!

To understand this, consider that if we carry out the matrix multiplication

[1234][45]=[1432]

and also

[1234][4G15G1]=[14G132G1]

The discrete logs of the two elliptic curve points in the second matrix multiplication are the same value as the elements of the first matrix multiplication.

In other words, each time we multiply the column vector by a row in the square matrix, we carry out two elliptic curve point multiplications and one elliptic curve addition.

Notation for elliptic curves

We say [aG1]1 is a ๐”พ1 elliptic curve point created from multiplying the field element a by G1. We say [aG2]2 is a ๐”พ2 elliptic curve point generated by multiplying a with the generator G2. Because of the discrete log problem, we cannot extract a given [aG1]1 or [aG2]2. Given a Aโˆˆ๐”พ1 and Bโˆˆ๐”พ2 point, we say the pairing of the two points is Aโˆ™B.

Prover steps

Letโ€™s encrypt our ๐š vector by multiplying each entry with the generator point G1 to produce the elliptic curve point [aiG1]1.

For the matrix ๐‹, we are doing the following:

[l1,1โ‹ฏl1,mโ‹ฎโ‹ฑโ‹ฎln,1โ‹ฏln,m][[a1G1]1โ‹ฎ[amG1]1]=[l1,1[a1G1]1+โ‹ฏ+l1,m[amG1]1โ‹ฎโ‹ฑโ‹ฎln,1[a1G1]1+โ‹ฏ+ln,m[amG1]1]=[โˆ‘i=1ml1,i[aiG1]1โˆ‘i=1ml2,i[aiG1]1โ‹ฎโˆ‘i=1mln,i[aiG1]1]

In anticipation of the Hadamard product becoming a list of elliptic curve pairings, we can use G2 points to also encrypt the ๐š vector so the verifier can do the pairing.

[r1,1โ‹ฏr1,mโ‹ฎโ‹ฑโ‹ฎrn,1โ‹ฏrn,m][[a1G2]2โ‹ฎ[amG2]2]=[r1,1[a1G2]2+โ‹ฏ+r1,m[amG2]2โ‹ฎโ‹ฑโ‹ฎrn,1[a1G2]2+โ‹ฏ+rn,m[amG2]2]=[โˆ‘i=1mr1,i[aiG2]2โˆ‘i=1mr2,i[aiG2]2โ‹ฎโˆ‘i=1mrn,i[aiG2]2]

After this operation, we have a single column of elliptic curve points in G1 originating from the multiplication ๐‹๐š and a single column of G2 points from ๐‘๐š.

The naive next step would be to encrypt the ๐š vector with G12 points so that the verifier can pair the result of ๐‹๐š with ๐‘๐š to see if it equals ๐Ž๐š, but G12 points are massive, so we would rather have the verifier pair the ๐Ž๐š elliptic curve points in G1 then pair each entry with a G2 point. Pairing with a G2 point is, in a sense, โ€œmultiplying by oneโ€ but turning the G1 point into a G12 point.

The prover then hands the G1 vector and the G2 vector to the verifier.

Verification step

Thus, the verification step becomes

[โˆ‘i=1mli,1[aiG1]1โˆ‘i=1mli,1[aiG1]1โ‹ฎโˆ‘i=1mli,1[aiG1]1]โˆ™โˆ™โ‹ฎโˆ™[โˆ‘i=1mri,1[aiG2]2โˆ‘i=1mri,1[aiG2]2โ‹ฎโˆ‘i=1mri,1[aiG2]2]=?[โˆ‘i=1moi,1[aiG1]1โˆ‘i=1moi,1[aiG1]1โ‹ฎโˆ‘i=1moi,1[aiG1]1]โˆ™โˆ™โ‹ฎโˆ™[G2G2โ‹ฎG2]
=โˆ‘i=1mli,1[aiG1]1โˆ™โˆ‘i=1mri,1[aiG2]2โˆ‘i=1mli,2[aiG1]1โˆ™โˆ‘i=1mri,2[aiG2]2โ‹ฎโˆ‘i=1mli,n[aiG1]1โˆ™โˆ‘i=1mri,n[aiG2]2=?โˆ‘i=1moi,1[aiG1]1โˆ™G2โˆ‘i=1moi,2[aiG1]1โˆ™G2โ‹ฎโˆ‘i=1moi,n[aiG1]1โˆ™G2

The above vectors of G12 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 x3+5x+5=y where y=155โ€, then our witness vector will probably look like the following:

[1,y,x,v]

where v=x2. In this case, we need [1,y] 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 G1 or G2 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 ๐”พ1 points encrypts the same values as the vector of ๐”พ2 points.

That is, the prover is supplying ๐šG1 and ๐šG2. Since the verifier doesnโ€™t know the discrete logs of the vector of points, how does the verifier know that the vector of ๐”พ1 points has the same discrete logs as the vector of ๐”พ2 points?

The verifier can check for the equality of the discrete logs (without knowing them) by pairing both vectors of points with a vector of the opposite generator and seeing that the resulting ๐”พ12 points are equal. Specifically,

[a1G1a2G1โ‹ฎamG1]โˆ™โˆ™โ‹ฎโˆ™[G2G2โ‹ฎG2]=?[a1G2a2G2โ‹ฎamG2]โˆ™โˆ™โ‹ฎโˆ™[G1G1โ‹ฎG1]

This algorithm is mostly academic

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

You can see an example implementation of algorithm described here by Obront in this repo.

Learn more with RareSkills

This material is from our Zero Knowledge Course.

Originally Published August 26, 2023

Related posts

8 min read

A Zero Knowledge Proof for the Inner Product

An inner product argument is a proof that the prover carried out the inner product computation correctly.

Last updated onNov 8, 2026
Read Article

6 min read

Bulletproofs ZKP: Zero Knowledge and Succinct Proofs for Inner Products

Bulletproofs ZKPs allow a prover to prove knowledge of an inner product with a logarithmic-sized proof. Bulletproofs do not require a trusted setup.

Last updated onNov 12, 2026
Read Article

13 min read

Proof that the Inverse of a Vandermonde Matrix Is Another Vandermonde Matrix

We now prove this fact. Less mathematically inclined readers can skip this chapter without any loss.

Last updated onMay 2, 2026
Read Article

17 min read

Quadratic Arithmetic Programs

A quadratic arithmetic program is an arithmetic circuit, specifically a Rank 1 Constraint System (R1CS) represented as a set of polynomials.

Last updated onNov 12, 2026
Read Article