Statement, witness, and the properties

Separate the public statement from the private witness, and define the properties a proof system can offer — completeness, soundness, zero-knowledge, and knowledge soundness (proof of knowledge) — stating precisely what each guarantees and, just as importantly, what it does not.

Track

Engineering

Module

4 · Zero-Knowledge Proofs

Prerequisites

What is a zero-knowledge proof?

A proof is always about a statement — a public claim everyone can see — and a witness — the private information that makes the claim true. "This account has a positive balance" is a statement; the actual balance and transaction history are the witness. "I am authorized for scope X" is a statement; the signed delegation token is the witness. Getting this split right is the whole discipline: the statement is what the verifier checks, the witness is what the prover protects.

Formally the statement is membership in a language L (or satisfaction of a relation R). For an NP relation R, a statement x is true exactly when there exists a witness w with R(x, w) = 1, and that check is efficient. The prover knows w; the verifier knows only x and the proof. The properties below describe how well the proof links the two.

Statement (x)

The public claim being proven — the instance the verifier evaluates. Everything the statement omits is outside what the proof guarantees.

Witness (w)

The private input that makes the statement true; R(x, w) = 1. The prover holds it; a zero-knowledge proof keeps it hidden.

Relation R

The efficiently-checkable predicate that defines what counts as a valid (statement, witness) pair. Designing R correctly is designing exactly what you are proving.

Argument vs proof

A "proof" holds against an unbounded prover; an "argument" only against a computationally bounded one. Most efficient ZK systems are arguments — their soundness rests on hardness assumptions.

The four core properties, stated for a relation R, statement x, witness w and security parameter n. Read Pr[...] as "the probability that...". These definitions build on Goldwasser–Micali–Rackoff (for the proof properties) and Bellare–Goldreich (for the proof-of-knowledge / extractor formulation).

The four properties (schematic)
Completeness:
  x true, prover honest with witness w  =>
     Pr[ verifier accepts ]  = 1   (or >= 1 - negl(n))
  "honest true claims are accepted"

Soundness:
  x FALSE (no witness exists)  =>
     for any cheating prover P*,  Pr[ accepts ] <= negl(n)
  "false statements are (almost) never accepted"

Zero-knowledge:
  exists simulator S with  S(x) ~= real transcript
  "verifier learns nothing beyond 'x is true'"

Knowledge soundness (proof of KNOWLEDGE):
  exists extractor E that, with rewinding access to any
  prover P* that makes the verifier accept, outputs w with
     R(x, w) = 1   (except with negl probability)
  "a convincing prover must actually POSSESS a witness,
   not merely know that one exists somewhere"

Soundness and knowledge soundness are different and the gap matters. Plain soundness only promises that accepted statements are true — a witness exists. Knowledge soundness promises more: anyone who can convince the verifier can be made to cough up the actual witness (via an extractor that rewinds them). For authorization you almost always want knowledge soundness: "a valid credential exists somewhere" is useless; "this prover holds a valid credential" is the real claim.

1. 1Write the statement precisely: name every public input and every condition the verifier relies on. Anything left implicit is not guaranteed.
2. 2Identify the witness: the private data the prover holds, which must never appear in the statement or the proof if zero-knowledge is required.
3. 3Decide which properties you need: completeness and soundness are mandatory; zero-knowledge if the witness is sensitive; knowledge soundness if you need the prover to actually possess the witness.
4. 4Check for gaps: can the statement be satisfied by an honest prover in a way you did not intend? If so, tighten R.
5. 5Match the system: pick a proving system whose guarantees (and assumptions) cover exactly the properties you require — they are not all equal.

synthetic — an under-specified vs. a tight statement
# Weak statement (soundness holds, but proves the wrong thing):
statement_A = "I know a delegation token signed by the root key"
# Problem: nothing binds it to THIS request, scope, or expiry.
# An honest prover with ANY old token satisfies it -> replayable.

# Tight statement (what you actually want to prove):
statement_B = "I know a token T such that:
    verify(rootPubKey, T) = true
    AND T.scope  covers  request.scope
    AND T.exp    >  now
    AND T.audience == this_verifier
    AND T.nonce  == challenge"
witness = T                          # kept private
# Now a valid proof binds authority to THIS use.

Both statements can be proven in zero-knowledge, and both can be sound. The difference is entirely in how the relation R is written. Statement A leaks nothing and is sound — yet it is a security hole, because a valid proof does not prove what the system actually needs. The properties are only as meaningful as the statement they certify.

For agent delegation, the statement encodes the authorization policy and the witness is the credential chain. You want knowledge soundness so that a worker that proves "authorized" genuinely holds the delegation (an extractor could pull it out), and zero-knowledge so the credential never leaks to a verifier that may be in a different trust domain. The statement must bind scope, expiry, audience and a per-use nonce — otherwise a valid proof is replayable or over-broad.

This separation also clarifies audit: the statement is the public, logged claim ("agent proved it was authorized for scope X at time T"), while the witness stays private. The log is meaningful precisely because the statement was written tightly.

• ▸Soundness guarantees the statement is true, not that it is the statement you meant — an under-specified relation is the dominant real-world failure.
• ▸Plain soundness is weaker than knowledge soundness: "a witness exists" is not "this prover has one". Using the wrong one is a logic error, not a crypto error.
• ▸Zero-knowledge hides the witness but not the statement; if the statement itself encodes sensitive data, you have leaked it regardless of the proof.
• ▸Most efficient systems are arguments, so their soundness is computational and rests on hardness assumptions that may not hold against a future (e.g. quantum) adversary.
• ▸None of these properties speak to correctness of the underlying policy: you can perfectly prove you satisfied a badly-designed authorization rule.

Expected direction: Plain soundness only certifies that some admin credential exists in the world — not that the submitter possesses one — so anyone can submit a proof and get access. The system needs knowledge soundness (an extractor could recover the credential from the prover) AND a statement bound to the submitter and this session, e.g. "I know a credential C such that verify(adminKey, C) and C.subject == me and C.nonce == challenge". Then a valid proof means this prover holds a credential that authorizes this specific request.

What is the difference between the statement and the witness?

The statement is the public claim the verifier checks; the witness is the private information the prover holds that makes the claim true (R(x, w) = 1).

How does knowledge soundness differ from plain soundness?

Plain soundness only guarantees an accepted statement is true (a witness exists). Knowledge soundness guarantees that any prover who convinces the verifier actually possesses a witness — formalized by an extractor that can recover it.

Does zero-knowledge protect the statement as well as the witness?

No — zero-knowledge hides only the witness. If sensitive data is encoded in the statement itself, it is public and the proof does not protect it.