Arithmetic constraints

Why do we need arithmetic constraints?

A computer program is usually written using operations such as:

A ZK proving system cannot simply be told:

It needs a mathematical description of what “correct” means.

Arithmetic constraints provide that description.

At the most basic level, a constraint is simply an equation that must evaluate to zero.

If the variables satisfy the equation, the constraint is satisfied. If they do not, it is violated.

First principle: arithmetic happens in a field

In modern algebraic proof systems, arithmetic is usually performed over a finite field.

Let the field be:

Every variable is an element of that field:

And every constraint is evaluated using field addition, subtraction, multiplication, and inversion where defined.

For a prime field:

with all arithmetic performed modulo p.

For example, over F₇:

because:

This is important: an arithmetic constraint is not necessarily an equation over the ordinary integers. It is usually an equation over a specific field.

The standard form: polynomial equals zero

Consider:

Move everything to one side:

This is a convenient representation because proving systems can ask whether a polynomial expression vanishes.

For example:

The same idea scales from one equation to millions of constraints.

Variables and assignments

A constraint describes what values are allowed, but the prover needs an actual assignment.

Suppose:

and the assignment is:

Then:

so the constraint is satisfied.

If instead:

then:

and the assignment is invalid for that constraint.

From computation to arithmetic circuits

Suppose we want to compute:

Introduce an intermediate variable:

Then:

These become two arithmetic constraints:

The intermediate variable t is important. Instead of describing one complicated expression, we decompose the computation into simple algebraic relationships.

Arithmetic gates

An arithmetic circuit is commonly built from simple gates.

Each gate can be translated into an algebraic constraint.

Linear constraints

A linear constraint has variables only to the first power and does not multiply variables by one another.

For example:

This is linear in x, y, z.

Linear constraints are comparatively simple to represent.

Many arithmetic circuits, however, need multiplication between variables.

Nonlinear constraints

A nonlinear constraint contains products or powers of variables.

Examples:

These constraints are important because general computation requires multiplication.

For example, hashing, encryption, signatures, and arithmetic programs all contain nonlinear operations once represented algebraically.

R1CS: the important normal form

One of the most important constraint representations in SNARK systems is R1CS, or Rank-1 Constraint System.

An R1CS constraint has the form:

Here:

• W is the witness/assignment vector;
• A, B, and C describe linear combinations of variables.

Equivalently:

This gives a very structured way to represent quadratic constraints.

R1CS example from scratch

Consider:

Let the assignment vector be:

The constant 1 lets us represent constants as linear combinations.

Choose:

Then the R1CS equation becomes:

which is exactly the desired computation.

How addition fits into R1CS

Suppose:

We can use a multiplication by one:

So:

This shows why the R1CS form can represent both linear and multiplication relationships.

Constants in constraints

Suppose we want:

Move everything into a polynomial equation:

Because the assignment vector contains a constant 1, the constant 7 can be represented as:

This is why the constant slot is useful in many R1CS conventions.

How do we represent Boolean values?

Fields contain many values, not just zero and one.

So if a variable is supposed to be a bit, we must constrain it.

The standard Boolean constraint is:

Factor it:

Therefore:

This is a beautiful example of converting a logical requirement into algebra.

Building logic from arithmetic

Once we can constrain bits, we can express Boolean operations algebraically.

NOT

AND

OR

For bits, these expressions produce exactly the expected Boolean results.

Range constraints

A field element can represent a very large number, but sometimes a value must lie inside a small integer range.

Suppose:

One common strategy is to decompose it into bits:

and constrain:

Now the possible values are exactly:

This is the basis of many range-check constructions.

Representing division

Division is not normally treated as a primitive gate.

Suppose:

For nonzero y, rewrite it as:

which becomes:

But there is an important edge case: what if y = 0?

A correct circuit must handle or constrain that case according to the intended semantics.

Comparisons are not primitive field operations

Fields naturally support:

But a statement like:

is not a native field equation.

To prove comparisons, systems usually use techniques such as:

• bit decomposition;
• range checks;
• lookup arguments;
• specialized comparison gadgets.

This is one reason arithmetic circuits can be substantially more complicated than ordinary source code.

Constraints and the witness

A constraint system defines what assignments are valid.

The witness supplies one concrete assignment.

For a valid witness:

The prover then uses the satisfied system to construct a proof.

Public inputs inside constraints

Suppose the statement is:

where:

The constraint is:

The public input is therefore directly bound into the relation.

The proof is not merely:

It is:

Arithmetic constraints in AIR

R1CS is not the only way to express constraints.

AIR — Algebraic Intermediate Representation — is especially important in STARKs and zkVMs.

Instead of describing every operation as an independent circuit gate, AIR often describes relationships between neighboring rows of an execution trace.

Suppose a register increments:

The transition constraint becomes:

This constraint must hold for every appropriate row i.

Transition vs boundary constraints

AIR commonly separates constraints into two broad categories.

For example:

Together they describe the intended execution.

Arithmetic constraints in a zkVM

A zkVM converts machine execution into algebraic constraints.

Imagine a trace with columns:

A transition might enforce:

which becomes:

A register update might be:

Conditional execution, opcode decoding, memory consistency, and instruction semantics require additional constraints.

Constraint degree matters

Consider:

This has degree 1.

Now:

has degree 2.

And:

has degree 3.

The degree of constraints affects how the proving system represents and checks them.

This is one reason systems often normalize computations into restricted forms such as quadratic R1CS constraints or carefully structured AIR constraints.

Combining many constraints

Suppose we have:

A proving system may need to represent a large collection of constraints compactly.

STARK-style systems often combine constraint evaluations into a composition polynomial using random coefficients:

where the αᵢ values are random challenges, commonly derived through Fiat–Shamir.

The idea is that a cheating prover should not be able to make many independently violated constraints disappear in the same random linear combination.

Why constraints eventually become polynomials

This connects arithmetic constraints to the other fundamentals you are studying.

Suppose a trace column gives values:

These values can be interpreted as evaluations of a polynomial on a chosen domain:

Then a transition constraint can become a polynomial expression such as:

The proving system can then test whether this expression vanishes on the required domain.

This is the bridge:

Arithmetic constraints in Rust

Before using a proving library, you can model the core idea directly.

// A tiny arithmetic constraint system.
// This is educational, not a cryptographic proving system.

#[derive(Debug)]
struct Assignment {
    x: i64,
    y: i64,
    z: i64,
}

fn addition_constraint(a: &Assignment) -> i64 {
    a.x + a.y - a.z
}

fn multiplication_constraint(a: &Assignment) -> i64 {
    a.x * a.y - a.z
}

fn boolean_constraint(b: i64) -> i64 {
    b * b - b
}

fn main() {
    let a = Assignment {
        x: 3,
        y: 5,
        z: 8,
    };

    assert_eq!(addition_constraint(&a), 0);

    let product = Assignment {
        x: 3,
        y: 5,
        z: 15,
    };

    assert_eq!(multiplication_constraint(&product), 0);

    // Valid Boolean values satisfy b² - b = 0.
    assert_eq!(boolean_constraint(0), 0);
    assert_eq!(boolean_constraint(1), 0);

    // 2 is not Boolean.
    assert_ne!(boolean_constraint(2), 0);

    println!("All constraints satisfied.");
}

A real implementation would replace ordinary integers with a finite-field type and would build a structured constraint system rather than directly evaluating the equations.

Why the Rust implementation should use a field

Suppose the field modulus is p.

Then the constraint:

means:

A production Rust implementation would therefore use a type such as a field element rather than i64.

Conceptually:

This is important because the proving system's algebra is defined over the field.

A constraint system is more than equations

A practical system must also know:

• which variables exist;
• which variables are public;
• which variables are private;
• which field is being used;
• which constraints apply;
• how variables map to witness positions;
• how constants are represented;
• how the system handles special operations.

So the mathematical idea is simple, but the engineering around it can become substantial.

Why constraints matter for soundness

Suppose the intended computation is:

If the system forgets the constraint:

then the prover may be able to provide an invalid assignment without the proving system noticing.

This illustrates a fundamental rule:

Constraint completeness is therefore a major part of proving-system correctness.

Common constraint-system bugs

R1CS vs AIR

Where arithmetic constraints fit in ZK

This connects directly to the fundamentals you have already built:

The whole idea in one map

If witnesses answer “what assignment makes the computation true?”, arithmetic constraints answer “what equations must that assignment satisfy?”. From there, R1CS and AIR turn those equations into structures that modern SNARK and STARK proving systems can actually operate on.