ZK Circuit

Simple example to build up to an ZK circuit in Python , based on the lessons from the Rareskills ZK Book. Based on Zach Obront equations and r1cs files that can be found here.

Goal

Prove that we know an x and z to solve for x^3 + 4x^2 - xz + 4 = 529 using full ZeroKnowledge

The examples work up in complexity from R1CS on normal arithmetic through using modular arithmetic and finally to Quadratic arithmetic programs. We then evaluate the polynomails using a random number generated by Power of Tau Ceremony.

This script can be considered half of the Groth16 algorithm, as it does not cover the security features.

Motivation

Since I finished the RareSkills ZK Book, I took on this challenge to practice everything and implement the first ZKP algorithm, Groth16, in Python. It’s like a final project for my ZK course. From the bottom of my heart, I want to thank RareSkills for the amazing book that literally covers everything to get you started.

R1CS

We already have R1CS matrices from this GitHub repo. You can check it to understand the logic on how we got those R1CS. Everything is perfectly explained, so I don’t have to be redundant and re-explain it.

Convert R1CS to QAP using Lagrange

In the context of zero-knowledge proofs, Rank-1 Constraint Systems (R1CS) need to be converted into Quadratic Arithmetic Programs (QAP) to facilitate polynomial commitments and verifications. This conversion involves several steps:

1. R1CS Representation: Initially, the computation is represented as a series of constraints (R1CS). Each constraint is expressed in terms of three vectors (L, R, and O) that, when combined with the witness (a set of variable assignments), satisfy the equation (L(w) \cdot R(w) = O(w)).

2. Interpolation using Lagrange Polynomials: Each column of the R1CS matrices (L, R, and O) is interpolated using Lagrange polynomials. This step transforms each constraint into a polynomial form, facilitating the evaluation of the entire system as polynomial equations.

3. Inner Product with Witness: The polynomials obtained from interpolation are then combined with the witness values through an inner product operation. This operation results in three polynomials that correspond to the left-hand side, right-hand side, and output of the original constraints.

4. Defining Polynomials t(x) and h(x): A target polynomial ( t(x) ) is defined, representing the product of linear factors corresponding to the input variables. The quotient polynomial ( h(x) ) is then computed to ensure that the equation holds without any remainder.

5. Polynomial Commitments: The resulting polynomials are evaluated at specific points (using elliptic curve points in this case) to generate commitments that can be used in the zero-knowledge proof verification.

These steps collectively transform the R1CS into a QAP, enabling polynomial operations that form the basis of the zero-knowledge proof.

Compute Inner Product for EC Points and Power of Tau Ceremony

In the context of zero-knowledge proofs, after converting R1CS to QAP, we need to perform polynomial commitments and evaluations on elliptic curve points. This is achieved through the Power of Tau ceremony, which is essential for setting up the proving and verification keys.

Inner Product for EC Points

1. Inner Product Calculation:
   • The inner product of elliptic curve points and coefficients is computed. This step involves multiplying each elliptic curve point by the corresponding coefficient and summing the results.

Power of Tau Ceremony

2. Generate Powers of Tau:

   • Powers of a randomly chosen element, (\tau), are generated. These powers are used to evaluate the polynomials at specific points.
   • For each polynomial term, we generate the corresponding powers of (\tau) on the elliptic curve points.

3. Evaluate Polynomials on EC Points:

   • The polynomials obtained from the QAP are evaluated at (\tau). This evaluation converts the polynomial coefficients into elliptic curve points.
   • The evaluation is performed for each polynomial term (term_1, term_2, term_3, and the product of h(x) and t(x) called ht(x)).

Points A, B, and C

4. Compute Points A, B, and C:
   • Using the evaluated elliptic curve points, we compute the proof points A, B, and C. These points are crucial for the final zero-knowledge proof.
   • Points A and B are derived directly from the polynomial evaluations, while point C is a combination of multiple evaluations (term_3 and ht(x) ).

Proof Verification

5. Verify the Proof:
   • Finally, the proof is verified by checking a pairing equation. This step ensures that the proof points satisfy the required elliptic curve pairings, confirming the validity of the zero-knowledge proof.

By performing these steps, we ensure that the proof is correctly generated and verifiable, completing the Groth16 protocol without the security features.

Reader Mission

For ZKP enthusiasts, their mission is to finish the script and implement the full Groth16 algorithm.

References

Everything you need to start ZKP can be found directly on Rareskills ZK Book