Zeeka saysA QAP turns R1CS into polynomials: a witness is valid exactly when one polynomial vanishes on every constraint point — i.e. is divisible by the target polynomial Z(x).
A Quadratic Arithmetic Program lifts R1CS from vectors to polynomials. Interpolate the A, B, C columns into polynomials over the constraint points 1, 2, 3, …; then a witness is valid exactly when A(x)·B(x) − C(x) evaluates to zero at every constraint point. By the factor theorem, vanishing on all those points means the expression is divisible by the target polynomial Z(x) = ∏(x − i).
That single divisibility test replaces checking every constraint individually, and the quotient H(x) = (A·B − C)/Z becomes the core of the prover's witness. The demo computes the per-constraint values for a valid witness (all zero → divisible) and a tampered one (a nonzero remainder → rejected).
Power-ups you unlock
Interpolate the A, B, C columns into polynomials over the constraint points
Validity ⇔ A(x)·B(x) − C(x) is zero at every constraint point
Zero on all those points ⇔ divisible by Z(x) = ∏(x − i)
The quotient H(x) = (A·B − C)/Z is the core of the prover witness
One divisibility check replaces checking every constraint
The Collision attacks — common mistakes
Checking constraints one by one instead of the single divisibility test
Choosing overlapping evaluation points for different constraints
Forgetting that a remainder ≠ 0 means an invalid witness
Confusing the target Z(x) with the witness polynomials
Boss battleShow that for a valid R1CS witness the per-constraint values are all zero (divisible by Z), and a bad witness leaves a nonzero remainder.
Example code
<!doctype html><html><head><meta charset="utf-8"></head>
<body style="background:#06040d;color:#e6e0ff;font-family:monospace;padding:20px"><pre id="o"></pre>
<script>
// QAP: a witness is valid iff (A·w)(B·w) − (C·w) = 0 at EVERY constraint point
// → the polynomial through those values is divisible by Z(x)=∏(x−i).
const F=97, mod=(n)=>((n%F)+F)%F, dot=(v,w)=>mod(v.reduce((s,a,i)=>s+a*w[i],0));
const cons=[
{ A:[0,1,0,0,0], B:[0,1,0,0,0], C:[0,0,0,1,0] },
{ A:[0,0,0,1,0], B:[0,1,0,0,0], C:[0,0,0,0,1] },
{ A:[0,0,0,0,1], B:[1,0,0,0,0], C:[-5,-1,1,0,0] },
];
const tvals=(w)=> cons.map(c => mod(dot(c.A,w)*dot(c.B,w) - dot(c.C,w)));
const good=[1,3,35,9,27], bad=[1,4,35,16,64]; // x=3 valid; x=4 inconsistent
document.getElementById('o').textContent = [
'constraint points x = 1,2,3 target Z(x) = (x−1)(x−2)(x−3)',
'valid witness (x=3): P at points = [' + tvals(good).join(', ') + '] → all 0 → divisible ✓',
'bad witness (x=4): P at points = [' + tvals(bad).join(', ') + '] → nonzero → NOT divisible ✗',
'the prover convinces iff P/Z has no remainder → soundness'
].join('\n');
</script></body></html>