This project implements the core proving pipeline used in zk-SNARKs, progressing step-by-step from Rank-1 Constraint Systems (R1CS) to Quadratic Arithmetic Programs (QAP), to Pinocchio, and finally toward the Groth16 proving system.
- β R1CS representation with variable and constraint definitions
- β Conversion from R1CS β QAP using Lagrange interpolation
- β Pinocchio implementation
- β Groth16 implementation
- β Tested with toy circuits (e.g., cubic polynomial)
This project was created as a deep learning exercise to understand and implement the Groth16 zk-SNARK proving system from the ground up. Starting with the formulation of arithmetic circuits and their transformation into Rank-1 Constraint Systems (R1CS), I then implemented the conversion to Quadratic Arithmetic Programs (QAP) using Lagrange interpolation. From there, I built the Pinocchio protocol to understand how pairing-based zk-SNARKs work, and finally extended it to support the Groth16 protocol, optimizing proof generation and verification with a compressed Common Reference String (CRS). The goal was to reconstruct the full proving pipeline almost from scratch using the Rust arkworks ecosystem, with a focus on clarity, correctness, and hands-on understanding of each transformation layer.
"The idea behind zk-SNARKs is to transform computation into a form where proving and verifying correctness can be done with polynomials, pairings, and commitments."
Arithmetic Circuit (e.g., x3 + x + 5 = 35)
β
R1CS
β
QAP (A(x), B(x), C(x), Z(x))
β
Witness Evaluation: A(s), B(s), C(s)
β
Compute H(x) = (AΒ·B - C)/Z
β
β Pinocchio: Pairing-based proof with 3 pairings
β Groth16: Optimized zk-SNARK with 1 pairing + compressed CRS
This project includes a complete end-to-end example in main.rs for both the Pinocchio and Groth16 zk-SNARK protocols. It builds a toy arithmetic circuit:
x2 - x + 132 = out
Then it:
- Translates the circuit to R1CS
- Converts R1CS β QAP
- Generates a trusted setup (Pinocchio & Groth16)
- Constructs a witness
- Produces a proof
- Verifies it
cargo run
You should see output like:
β QAP is satisfied by witness π¦ Pinocchio setup... π Generating Pinocchio proof... π Pinocchio proof: ACCEPTED β π¦ Groth16 setup... π Generating Groth16 proof... π Groth16 proof: ACCEPTED β