Witness and Public Inputs

Start with the actual problem

A zero-knowledge proof is usually not trying to prove an arbitrary sentence directly.

Instead, we describe a precise mathematical statement:

∃ w : C(x, w) = true

Here:

public input

x — information the verifier is allowed to know

witness

w — secret information known to the prover

constraint system

C(x, w) — the rules that must be satisfied

The prover is saying:

“I know a witness w such that C(x, w) is satisfied.”

The verifier does not need to learn the witness itself.

Mental model: the public input identifies what statement is being proved. The witness is the hidden information that makes that statement true.

The simplest example

Suppose we want to prove knowledge of a number whose square is 25.

x² = 25

We can formulate the problem as:

public input: x = 25

witness: w = 5

constraint: w² = x

The prover knows:

w = 5

The verifier knows:

x = 25

The prover proves that:

5² = 25

without necessarily revealing 5.

Why are they called “inputs”?

A proving system generally receives some external data before it constructs constraints and generates a proof.

That data can be divided into two conceptual categories:

public inputs

Values that are part of the statement and are normally provided to the verifier as well.

private witness

Values required to satisfy the statement but intended to remain hidden from the verifier.

The exact API differs between proving systems, but this public/private split is fundamental to many ZK protocols.

The relation between x and w

It is useful to think of a ZK statement as a relation:

R(x, w) = 1

where:

x is the public statement;
w is a witness;
R defines which witness values are valid for a particular statement.

The language represented by the relation is:

L = { x | ∃ w such that R(x,w) = 1 }

So the prover does not necessarily prove that it has one specific secret value. It proves that there exists a valid witness for the public statement.

Example: knowledge of a hash preimage

Suppose a public hash value is:

y = H(m)

The prover claims to know the secret message m.

We can formulate:

public input: y

witness: m

constraint: H(m) = y

secret m → H(m) = public y

The verifier learns that a preimage exists, but a zero-knowledge proof can be designed so that the preimage itself is not revealed.

In practice, representing a hash function inside a circuit can be expensive, which is why ZK systems often use hash functions selected for their arithmetic efficiency.

From a statement to a circuit

Proof systems cannot directly reason about an English sentence such as:

“I know a secret number whose square is 25.”

We translate the statement into mathematical constraints.

For example:

w · w − x = 0

Now the proving system can work with field elements and algebraic constraints.

public x + private w → constraints → proof

This translation is the foundation of circuit-based ZK systems.

What exactly is a witness?

A witness is the collection of values that allows the constraints to be satisfied.

For a tiny circuit:

z = x · y

Suppose:

public z = 15

private x = 3

private y = 5

The witness may contain:

w = (3, 5)

because:

3 · 5 = 15

In a real circuit, the witness can be much larger. It may include intermediate values for every gate or constraint.

The witness is often more than the user’s secret

This distinction is extremely important.

Suppose the circuit computes:

a = x + y

b = a · z

c = b²

The prover might provide original private inputs:

x, y, z

but the proving system may also need the intermediate assignments:

a, b, c

So the full witness can look like:

W = (x, y, z, a, b, c, …)

Important: “witness” can mean the secret assignment to a relation, or, in a concrete proving system, the complete assignment required to satisfy every generated constraint. Always check the system's definition.

What exactly is a public input?

A public input is information that is intentionally part of the statement visible to the verifier.

For example, in a proof of:

H(secret) = commitment

the commitment may be public:

x = commitment

while:

w = secret

remains private.

The public input therefore defines the particular instance of the statement being proved.

Three different things you must not confuse

public input

The public instance x. The verifier is expected to know it.

private input

A secret input supplied by the prover. It is part of the witness.

intermediate witness values

Values produced while evaluating the computation and used to satisfy internal constraints.

A circuit compiler may turn a small set of user-provided private inputs into a much larger internal witness.

Witnesses in R1CS

R1CS — Rank-1 Constraint Systems — expresses constraints of the form:

(A · W) (B · W) = C · W

where W is the assignment vector.

The vector commonly contains a constant slot, public inputs, private inputs, and intermediate variables, depending on the system's exact convention.

For a multiplication:

z = x · y

the assignment may be:

W = (1, x, y, z)

and the R1CS constraint enforces:

x · y = z

The exact ordering of public and private elements is implementation-specific, but the conceptual distinction remains the same.

From R1CS toward a proving system

In systems based on R1CS, the witness assignment is used to evaluate the constraint system.

A high-level pipeline can be viewed as:

public inputs + witness → R1CS → QAP / polynomial representation → proof

The witness is not an optional annotation. It is the concrete assignment against which the algebraic constraints are checked.

Witnesses in AIR and zkVMs

In an AIR-based system, the structure looks different from R1CS.

Instead of thinking primarily about a circuit's individual gates, we often begin with an execution trace.

trace = rows of machine state over time

For a simple machine:

row₀ → row₁ → row₂ → row₃ → …

The trace contains values such as registers, program counters, memory-related state, flags, and other VM state.

That trace is essentially the concrete execution witness for the computation.

program + inputs → execute execution trace → AIR constraints → proof

The prover knows the complete trace. The verifier usually sees only the public statement and a proof that the trace satisfies the AIR.

A tiny zkVM example

Imagine a toy VM with a register r that starts at 2 and increments once per cycle.

The public claim might be:

final register = 5

The private execution trace could be:

2, 3, 4, 5

The transition constraint is:

rᵢ₊₁ − rᵢ − 1 = 0

The boundary constraints specify:

r₀ = 2

r₃ = 5

The trace is the witness that makes those constraints true.

What the prover actually does

At a high level, a prover receives:

public inputs x

private witness w

and checks or constructs the computation represented by the constraint system.

Conceptually:

x + w → assignment → constraint evaluation → proof

If the assignment does not satisfy the constraints, an honest prover cannot generate a valid proof.

What the verifier gets

The verifier generally receives:

public inputs x

proof π

It does not receive the complete private witness.

The verifier checks:

Verify(x, π) = true

The proof system is designed so that acceptance gives confidence that there exists a valid witness:

∃ w : R(x,w) = 1

while the proof is constructed so that the witness itself need not be disclosed.

Where zero knowledge enters

The distinction between public input and witness explains the purpose of zero knowledge.

The verifier needs confidence that:

there exists a valid private witness

but should not necessarily learn:

the witness itself

For example, proving:

“I know the password corresponding to this commitment.”

does not require sending the password to the verifier.

Key distinction: public/private inputs define what is revealed as part of the statement. Zero knowledge is the cryptographic property that protects the private witness beyond what the verifier can infer from the intended statement and proof.

Public inputs versus public outputs

A circuit can also produce values that become public outputs.

For example, a private computation may calculate:

y = f(w)

The protocol may expose y as a public result while keeping w private.

private witness w → computation f → public output y

The resulting proof establishes that the public output is consistent with some valid private witness.

Why input ordering matters

Cryptographic systems operate on exact encodings. The mathematical set of public inputs may be unordered conceptually, but an implementation usually commits to a specific vector order.

public_inputs = [x₀, x₁, x₂, …]

Changing the order can change the statement being verified.

For example:

[age, threshold]

≠

[threshold, age]

even if both contain the same numerical values.

Production systems therefore specify input ordering and serialization precisely.

Simple Rust model of public inputs and witness

Before using a real proving library, it is useful to model the relationship directly in Rust.

Complete Rust implementation

        rust
        
      
// A tiny educational model of a ZK relation.

struct PublicInputs {
    target: u64,
}

struct Witness {
    secret: u64,
}

fn satisfies(
    public: &PublicInputs,
    witness: &Witness,
) -> bool {
    witness.secret * witness.secret == public.target
}

fn main() {
    let public = PublicInputs {
        target: 25,
    };

    let witness = Witness {
        secret: 5,
    };

    assert!(satisfies(&public, &witness));

    println!("The witness satisfies the public statement.");
}

This is not a ZK proof system. It simply demonstrates the core mathematical relation:

R(public, witness) = true

A real proving system replaces the direct boolean check with a cryptographic proof that the relation is satisfied without revealing the witness.

Why real ZK systems use field elements

In most algebraic proving systems, values are represented inside a finite field rather than ordinary machine integers.

The relation becomes:

w² − x = 0 in F

where F is a finite field.

This matters because polynomial arithmetic, interpolation, FFTs, R1CS, AIR, FRI, and many commitment schemes are naturally expressed over finite fields.

The conceptual split remains unchanged:

public x ∈ F

private w ∈ F

R(x,w) = 1

Multiple public inputs and witnesses

Real statements usually contain many values.

For example:

public = (root, nullifier, commitment)

witness = (secret, path, randomness, …)

The relation might enforce several conditions simultaneously:

hash(secret) = commitment

MerkleVerify(path, commitment, root) = true

nullifier = H(secret)

The prover demonstrates that all constraints hold for one consistent witness.

Public inputs are part of what is being proved

This is a subtle but important point.

A proof should not simply prove:

“some valid witness exists.”

It should prove:

“there exists a witness valid for this exact public statement.”

Mathematically:

∃ w : R(x,w) = 1

The value x is therefore cryptographically significant. It cannot be treated as unrelated metadata.

What happens with a wrong witness?

Suppose:

public target = 25

witness secret = 7

Then:

7² = 49 ≠ 25

The constraint is false.

An honest prover cannot produce a valid proof for that assignment.

This is the first layer of the proving system:

valid witness → satisfiable constraints → potentially valid proof

invalid witness → unsatisfied constraints → proof generation fails

Witness generation

In a real application, the witness often comes from executing a computation.

For a circuit:

private inputs → execute circuit → assign intermediate variables

For a zkVM:

program + private inputs → VM execution → execution trace

That generated assignment is then used by the prover.

private input → execute witness generation → constraints satisfied? → prover

Witnesses can be large

For a small arithmetic circuit, the witness might contain only a few values.

For a large computation, it can be enormous.

For a zkVM executing thousands or millions of instructions, the witness may effectively represent a large execution trace.

This is one reason proving-system engineering cares so much about:

memory layout;
trace generation;
parallel witness construction;
field arithmetic performance;
FFT/NTT performance;
commitment construction;
prover memory usage.

The witness is not merely an abstract mathematical object. In a real prover, it is a major data structure that must be generated, stored, transformed, and committed to.

Witness and public inputs in a zkVM

Consider a zkVM proving that a program executed correctly.

Possible public information:

program hash

public input

initial state commitment

final output

Possible private witness information:

execution trace

private memory values

private program inputs

intermediate machine states

The AIR then checks that the trace represents a valid execution.

public statement + execution witness → AIR constraints → STARK proof

This is the conceptual bridge between ordinary programs and algebraic proof systems.

Common mistakes

mistake 1

Thinking the witness is always just one secret value. In real systems it can contain a huge assignment or execution trace.

mistake 2

Thinking public input is merely metadata. It is part of the statement that the proof must be bound to.

mistake 3

Thinking every witness value is private. Some systems have public witness components or explicitly exposed outputs.

mistake 4

Thinking witness generation is the proof itself. Witness generation produces the assignment; the prover then transforms that assignment into a cryptographic proof.

Circuit systems vs zkVMs

Concept	Circuit / R1CS style	AIR / zkVM style
public data	public inputs / instance values	public program/input/output/state commitments
private data	private inputs and assignment values	execution trace and private machine state
constraints	algebraic gate constraints	transition and boundary constraints
witness representation	assignment vector	trace columns / rows
proof goal	prove constraints are satisfiable	prove trace represents valid execution

Where witness and public inputs fit

public inputs + private witness → constraint system

constraint system + witness assignment → prover

prover → proof π

public inputs + proof π → verifier

The verifier does not need to receive the complete witness. It verifies a proof that is bound to the public statement.

The whole idea in one map

first-principles map

1. Start with a statement x.

2. Define what it means for a witness w to satisfy that statement.

3. Express the relation as constraints.

4. The prover supplies a witness that satisfies those constraints.

5. Public inputs are visible parts of the statement.

6. Private inputs are incorporated into the witness.

7. Intermediate assignments can also become part of the witness.

8. R1CS represents the assignment as algebraic constraints.

9. AIR represents machine execution through trace constraints.

10. The prover turns the satisfied assignment into a cryptographic proof.

11. The verifier receives the public inputs and proof, not necessarily the witness.

12. Zero knowledge aims to keep the witness hidden while proving that a valid witness exists.

If finite fields answer “where does the algebra happen?”, polynomial commitments answer “how do we commit to algebraic objects?”, Merkle trees answer “how do we commit to large vectors?”, and Fiat–Shamir answers “how do we derive verifier challenges non-interactively?”, then witnesses and public inputs answer the most basic question: “what exactly is the prover claiming, and what information is allowed to be visible?”