Arithmetic Circuit

The computation is modeled as a directed acyclic graph (DAG) where edges represent data flow. Sources are input nodes, sinks are output nodes, and internal nodes are gates. The acyclic property ensures no feedback loops, making the computation deterministic and bounded. This structure maps directly to real-world programs: every loop must be unrolled to a fixed number of iterations, and every conditional branch must be executed as a multiplexed selection of both paths.

All computations are decomposed into only two fundamental operations:

• Addition gates: Compute the sum of two input wires modulo the field characteristic
• Multiplication gates: Compute the product of two input wires modulo the field characteristic

This constraint to two gate types is not a limitation but a feature—it enables the algebraic structure required by polynomial commitment schemes and constraint systems. Non-arithmetic operations like bitwise XOR or hash functions must be expressed as compositions of these gates, which is why STARK-friendly hashes like Poseidon are designed to minimize multiplication gate count.

All values in an arithmetic circuit exist within a finite field F_p, typically a large prime field like the BN254 scalar field or BLS12-381 scalar field. This is critical because:

• No floating-point errors: All operations are exact, eliminating rounding discrepancies between prover and verifier
• Cryptographic soundness: The field size determines the security level against algebraic attacks
• Modular arithmetic: Values wrap around the field modulus, requiring careful handling of overflow in integer computations

The choice of field directly impacts proof generation speed and the compatibility with elliptic curve pairings used in zkSNARKs.

A circuit is satisfiable if there exists an assignment of values to all wires—including the secret witness inputs—such that every gate's output correctly matches its operation on its inputs. The prover's task is to demonstrate knowledge of such an assignment without revealing it. This is formalized as:

• Public inputs: Known to both prover and verifier (e.g., the model's output hash)
• Private witness: Known only to the prover (e.g., model weights, input data)

The circuit encodes the statement 'I know a witness w such that C(x, w) = 0' where C is the circuit's constraint polynomial.

Arithmetic circuits are typically compiled into a Rank-1 Constraint System (R1CS) or a Plonkish constraint system before proof generation. This transformation:

• Converts each gate into a quadratic constraint of the form (a · s) × (b · s) = (c · s)
• Produces matrices that encode the entire circuit's wiring and gate operations
• Enables the application of polynomial interactive oracle proofs (PIOPs)

The number of constraints directly correlates with prover time—optimizing circuit design to minimize constraints is a critical engineering discipline in zkML applications where models may have millions of parameters.

Real-world computations involve operations beyond addition and multiplication. These are handled through:

• Lookup arguments: Prove a value exists in a precomputed table (e.g., a correct XOR result) without computing it via gates
• Bit decomposition: Represent integers as binary wires and verify bitwise operations through arithmetic constraints
• Range proofs: Prove a value lies within a specific interval using techniques from Bulletproofs
• Gadget libraries: Reusable circuit components for common operations like hashing, signature verification, and matrix multiplication

In zkML, activation functions like ReLU are implemented as a combination of range checks and multiplexing, while softmax requires approximation via polynomial evaluation.

A set of mathematical equations encoding the valid execution of a computation. An arithmetic circuit is a graphical representation of a constraint system, where each gate corresponds to a constraint that must be satisfied. The prover must demonstrate knowledge of a witness that satisfies all constraints simultaneously. Common formats include R1CS and Plonkish arithmetization.

A standard format for representing arithmetic circuit satisfiability as a set of quadratic constraints of the form (A·w) ∘ (B·w) = (C·w). Widely used in early zkSNARK constructions like Groth16. An arithmetic circuit is compiled into three matrices (A, B, C) that encode the wiring and gate operations, transforming the circuit satisfaction problem into a linear algebra problem over a finite field.

A more flexible constraint system format used by the Plonk proof system. Unlike R1CS, which uses fixed multiplication gates, Plonkish arithmetization uses a gate equation that can represent addition, multiplication, or custom operations within a single configurable gate. This allows arithmetic circuits to include lookup tables and higher-degree polynomial constraints, dramatically reducing the total gate count for complex operations like hash functions.

The secret auxiliary input known only to the prover that satisfies all constraints of an arithmetic circuit. In a zkML context, the witness typically includes:

• Private model weights and biases
• Input data that must remain confidential
• Intermediate activation values at each gate The prover's job is to demonstrate knowledge of a valid witness without revealing it, using the circuit as a public description of the computation.

A cryptographic primitive allowing a prover to commit to a polynomial derived from the arithmetic circuit's execution trace and later open it at specific points. The commitment is binding (the prover cannot change the polynomial) and hiding (the polynomial remains secret). Schemes like KZG (pairing-based) and FRI (hash-based) determine the proof size and verification cost of the overall ZKP system.

A technique where the verifier algorithm of a ZKP is itself expressed as an arithmetic circuit. This allows the creation of a single proof that attests to the validity of multiple prior proofs. Critical for incrementally verifiable computation (IVC) and blockchain rollups, where a single succinct proof can verify an entire block of thousands of transactions without requiring the verifier to check each one individually.