A quadratic arithmetic program (QAP) represents an arithmetic computation as a network of wires and multiplication gates. A prover supplies wire values that satisfy the network while separating public inputs, called the statement, from private inputs, called the witness. This makes the computation a foundation for a noninteractive proof of knowledge. section 19.1 section 19.7
Each gate has left, right, and output relationships. Wires a_j carry inputs or computed values, with a_0 conventionally fixed to 1. Gate-specific polynomials v_j(x), w_j(x), and y_j(x) select the left input, right input, and output contributions. Their weighted sums must satisfy (Σa_jv_j)(Σa_jw_j) = Σa_jy_j + h(x)t(x). section 19.2 section 19.7
The polynomial identity organizes a circuit as follows:
- Assign each multiplication gate a distinct location r_j; the target polynomial t(x) is the product of terms (x − r_j). section 19.7
- Use Lagrange interpolant functions that equal 1 at one gate and 0 at the others, so each wire contributes only where it is used. section 19.7
- Place products that do not correspond to valid gate outputs into h(x)t(x), the cross-term remainder. section 19.6 section 19.7
- Accept the assignment when the identity holds; a mismatch rejects the claimed computation. section 19.7
Private medical-record claim
A small circuit can take a medicine number, dose, patient number, and a random value. The medicine number and dose, together with wire values derived only from them, form the public statement; values depending on the patient number remain witness data. The circuit can therefore support a claim about a prescribed medicine and dose without identifying which patient supplied the private values. section 19.2 section 19.5.4
To construct a fixed QAP, allocate coefficient arrays for v_j, w_j, and y_j, compute their Lagrange coefficients, derive the h(x) cross-term table, and record a permutation that puts statement wires before witness wires. The resulting parameters can be saved once for that circuit; a different problem requires a rewritten QAP construction. section 19.5.2 section 19.5.2
During proving, fill the input wires, compute all derived wire values and cross-term coefficients, then combine them with QAP parameters and common-reference-string points to produce proof points A, B, and C. Proof generation can involve many witness values, while verification is designed to be fast. section 19.5.4 section 19.5
Figure 19.2 Example quadratic arithmetic program
Inspect the gate-and-wire layout used to map an arithmetic computation into QAP constraints. section 19.2
