ZK-Proof Circuit Optimization

Overview

Zero-knowledge (zk) proofs are increasingly used to bring privacy and verifiability to real-world systems: from blockchain scalability to privacy-preserving identity and secure computation. At the core of every zk system is an arithmetic circuit that must be both generated and satisfied.

A major bottleneck in these systems is witness generation. The process of calculating the intermediate values required to satisfy the circuit. This step is often the most time-consuming and costly part of generating a proof.

This challenge focuses on reducing the witness generation overhead through arithmetic circuit optimization. The goal is to express the circuit with as few constraints as possible, while preserving correctness. Smaller constraint systems translate directly into faster witness generation, reducing memory usage, compute cost, and prover latency.

Our Challenge

The goal of TIG's ZK-proof challenge is to optimize the generation of a ZK-proof by focusing on witness generation optimization.

Objective

Given a random polynomial function $f(x_1, x_2, \ldots, x_n)$, find an R1CS circuit that computes $f$ in as few constraints as possible.

A Rank-1 Constraint System (R1CS), $\mathcal{C}$, is a set of equations of the form:

where:

• $n$ is the number of constraints in the system.
• $\mathbf{a}_i, \mathbf{b}_i, \mathbf{c}_i$ are coefficient vectors consisting of the constants or weightings of $\mathbf{w}$ for constraint $i$.
• $\mathbf{w}$ is the witness vector of length $m$, it contains all values involved in the computation. It is of the form:

where:

• $\vec{x}_{pub}$ is the vector of public inputs, the variables in the given polynomial function.
• $\vec{v}_{int}$ is the vector of intermediate variables, the internal computation variables.
• $y_{pub}$ is the public output variable, the output of the function f.

Once the R1CS, $\mathcal{C}$, and the vector of intermediate variables, $\vec{v}_{int}$ are found, the zk-proof, $\pi(C, x_{pub}, y_{pub}, v_{int})$, is generated by Spartan.

Difficulty Parameters

The following two parameters can be adjusted in order to vary the difficulty of the challenge:

• Parameter 1: $delta$: the complexity of the polynomial, based on the degree, number of variables with nonzero exponent, and the number of terms in the polynomial.
• Parameter 2: $Better\_Than\_Baseline$: the factor by which a solution must beat a given baseline value.

Example

Consider an example instance with $delta=6$ and $better\_than\_baseline=0.5$.

The given polynomial is $f = x_1^4 \cdot x_2 + x_1^2 \cdot x_2$. In this example, the polynomial $f$ must be decomposed into at most 3 constraints to be a solution.

This polynomial can be expressed by the following three constraints:

v_1 = x_1 · x_1     (Constraint 1)
v_2 = v_1 · x_2     (Constraint 2)
y = v_2 · (v_1 + 1) (Constraint 3)

Assigned example

If $x_1 = 3$, $x_2 = 5$ (public), then:

$v_1 = 9$, $v_2 = 15$, $y = 150$

The full witness is:

The verifier sees $x_1=3$, $x_2=5$ and $y=150$; the zk-proof ensures there exist private intermediate values $v_1, v_2$ satisfying all constraints without revealing them.

Since the proof verified that there exists private intermediate values $v_1, v_2$ that satisfy the 3 constraints, this is a valid solution.

Applications

Zero-knowledge systems are finding applications across a growing number of domains, but their adoption is often constrained by the high computational cost of witness (or trace) generation. The ability to reduce constraint size and improve witness generation efficiency is therefore not just a technical improvement, but a fundamental enabler for real-world deployment. Smaller, faster circuits lower hardware requirements, reduce latency, and pave the way for real-time verifiable computation. As a result, optimizations in witness generation have a transformative impact across several key areas:

• Rollups & Layer 2 Scaling: Faster witness generation enables lower-latency, cheaper transaction batching in systems like zkSync, Scroll, and Starknet.
• Private Identity & Voting: Efficient circuits could make anonymous credential checks usable on consumer devices.
• DeFi & Privacy-Preserving Finance: Proving the correctness of complex logic (e.g., swaps, limit orders) could become viable even under gas and time constraints.
• AI Agents & Verifiable ML: Reduces proving time for verifiable inference, decision trees, and execution traces in decentralized agents.
• On-chain Gaming: Enables low-latency proofs of game state or random events, preserving fairness without slowing gameplay.