QAP — Quadratic Arithmetic Program

日期: 2026-11-30 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #QAP #Lagrange #Groth16 #多项式

---

今日目标

---

一、动机：从矩阵到多项式

1.1 为什么要 QAP？

R1CS 检查 $\vec{z}$：需要遍历 $m$ 行验证 $A z \circ B z = C z$，即 $m$ 个标量约束。

QAP：把所有 $m$ 个约束合并成一个多项式整除关系：

$$ A(X) \cdot B(X) - C(X) = H(X) \cdot Z(X) $$

其中 $A, B, C, H$ 由 witness 决定，$Z$ 是固定的"目标多项式"。

好处：

• 一次"承诺到这些多项式" + 一次"在随机点求值" → 概率验证（Schwartz-Zippel）
• 可以用密码承诺（KZG / pairing）做 succinct proof
• 通往 Groth16 的基础

---

二、Lagrange 插值（速查）

给定 $m$ 个点 $(x_1, y_1), \dots, (x_m, y_m)$，存在唯一 deg ≤ $m-1$ 多项式：

$$ L(X) = \sum_{i=1}^m y_i \cdot \ell_i(X), \quad \ell_i(X) = \prod_{j \neq i} \frac{X - x_j}{x_i - x_j} $$

这是 Day 189 FFT 章节里讨论过的内容：当 $x_i$ 取 unity roots 时插值/求值可在 $O(m \log m)$ 完成。

---

三、R1CS → QAP 转换

3.1 设置

设 R1CS 有 $m$ 行约束、$n$ 个变量（含常数 1）。即：

• $A, B, C \in \mathbb{F}_p^{m \times n}$
• $\vec{z} \in \mathbb{F}_p^n$

选定 $m$ 个不同的 evaluation points $r_1, \dots, r_m \in \mathbb{F}_p$（实践用 unity roots）。

3.2 多项式 $A_j(X), B_j(X), C_j(X)$

对每个变量 $j \in [n]$，定义 deg ≤ $m-1$ 多项式：

$$ A_j(X) = \text{Lagrange interpolate} {(r_i, A_{ij}) : i = 1..m} $$

即 $A_j(r_i) = A_{ij}$。同理 $B_j(X), C_j(X)$。

→ 共 $3n$ 个多项式，每个 deg ≤ $m-1$。

3.3 组合多项式（依赖 witness $\vec{z}$）

$$ A(X) := \sum_{j=1}^n z_j \cdot A_j(X) $$ $$ B(X) := \sum_{j=1}^n z_j \cdot B_j(X) $$ $$ C(X) := \sum_{j=1}^n z_j \cdot C_j(X) $$

由线性性，对任一 evaluation point $r_i$：

$$ A(r_i) = \sum_j z_j A_{ij} = (A\vec{z})_i $$

类似 $B(r_i) = (B \vec{z})_i$，$C(r_i) = (C\vec{z})_i$。

3.4 关键关系

$\vec{z}$ 满足 R1CS $\iff (A\vec{z})_i \cdot (B\vec{z})_i = (C\vec{z})_i$ for all $i$。

⟺ $A(r_i) B(r_i) - C(r_i) = 0$ for $i = 1..m$。

⟺ 多项式 $A(X) B(X) - C(X)$ 在所有 $r_i$ 处为 0。

⟺ $A(X) B(X) - C(X)$ 被 $Z(X) = \prod_{i=1}^m (X - r_i)$ 整除。

⟺ 存在 $H(X)$ 使得：

$$ \boxed{A(X) \cdot B(X) - C(X) = H(X) \cdot Z(X)} $$

deg 分析：$\deg(AB) \leq 2(m-1)$，$\deg(C) \leq m-1$，$\deg(Z) = m$，所以 $\deg(H) \leq m-2$。

3.5 QAP 形式定义

一个 QAP 由 ${A_j(X), B_j(X), C_j(X)}_{j=1}^n$ 和 target poly $Z(X)$ 组成。witness $\vec{z}$ 满足 QAP iff $\exists H(X)$ 使上式成立。

---

四、$x^2 + x = 12$ 的完整 QAP（手算）

4.1 R1CS 复习

$\vec{z} = (1, \text{out}, x, w_1)$，witness $\vec{z}^* = (1, 12, 3, 9)$。

$$ A = \begin{pmatrix} 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 \end{pmatrix},\ B = \begin{pmatrix} 0 & 0 & 1 & 0 \ 0 & 0 & 1 & 1 \end{pmatrix},\ C = \begin{pmatrix} 0 & 0 & 0 & 1 \ 0 & 1 & 0 & 0 \end{pmatrix} $$

4.2 选 evaluation points

取 $r_1 = 1, r_2 = 2$。$Z(X) = (X - 1)(X - 2) = X^2 - 3X + 2$。

4.3 计算 $A_j, B_j, C_j$

$n = 4$ 变量 → 4 组三元组。每个多项式由两点插值（$m=2$，deg ≤ 1）。

$A_j(X)$：

Lagrange basis：

• $\ell_1(X) = (X - 2)/(1 - 2) = -(X-2) = -X + 2$
• $\ell_2(X) = (X - 1)/(2 - 1) = X - 1$

$A_j(X) = A_{1j} \ell_1(X) + A_{2j} \ell_2(X)$:

4.4 用 witness $\vec{z}^* = (1, 12, 3, 9)$ 组合

$$ A(X) = 1\cdot(X-1) + 12\cdot 0 + 3\cdot(-X+2) + 9\cdot 0 = X - 1 - 3X + 6 = -2X + 5 $$

$$ B(X) = 1\cdot 0 + 12\cdot 0 + 3\cdot 1 + 9\cdot(X-1) = 3 + 9X - 9 = 9X - 6 $$

$$ C(X) = 1\cdot 0 + 12\cdot(X-1) + 3\cdot 0 + 9\cdot(-X+2) = 12X - 12 - 9X + 18 = 3X + 6 $$

4.5 计算 $A(X) B(X) - C(X)$

$$ A(X) B(X) = (-2X + 5)(9X - 6) = -18X^2 + 12X + 45X - 30 = -18X^2 + 57X - 30 $$

$$ A(X) B(X) - C(X) = -18X^2 + 57X - 30 - (3X + 6) = -18X^2 + 54X - 36 $$

4.6 除以 $Z(X) = X^2 - 3X + 2$

$$ -18X^2 + 54X - 36 = -18(X^2 - 3X + 2) = -18 Z(X) $$

→ $H(X) = -18$（常数多项式，符合 deg ≤ $m-2 = 0$）

4.7 验证 evaluation points

• $X = 1$：$A(1) = 3, B(1) = 3, C(1) = 9$；$3 \cdot 3 - 9 = 0$ ✓
• $X = 2$：$A(2) = 1, B(2) = 12, C(2) = 12$；$1 \cdot 12 - 12 = 0$ ✓

完美 — 这就是 QAP。

---

五、代码 — Lagrange 插值 + QAP 验证

"""
qap.py — R1CS 转 QAP, Lagrange 插值, 整除验证
依赖: numpy
"""
import numpy as np
from numpy.polynomial import polynomial as P

# Polynomial 用 numpy: coefs in increasing-power order
# [a0, a1, a2] = a0 + a1 X + a2 X^2

def lagrange_interp(points):
    """points: list of (x, y). 返回 numpy poly coefs"""
    n = len(points)
    result = np.zeros(n)
    for i, (xi, yi) in enumerate(points):
        # ℓ_i(X) = ∏_{j≠i} (X - x_j) / (x_i - x_j)
        num = np.array([1.0])
        denom = 1.0
        for j, (xj, _) in enumerate(points):
            if i == j: continue
            num = P.polymul(num, [-xj, 1.0])  # (X - x_j)
            denom *= (xi - xj)
        result = P.polyadd(result, num * (yi / denom))
    return result

def r1cs_to_qap(A, B, C, eval_points):
    """A,B,C: m x n. Returns A_polys, B_polys, C_polys, Z(X)"""
    m, n = A.shape
    A_polys = [lagrange_interp([(eval_points[i], A[i,j]) for i in range(m)]) for j in range(n)]
    B_polys = [lagrange_interp([(eval_points[i], B[i,j]) for i in range(m)]) for j in range(n)]
    C_polys = [lagrange_interp([(eval_points[i], C[i,j]) for i in range(m)]) for j in range(n)]
    # Z(X) = ∏ (X - r_i)
    Z = np.array([1.0])
    for r in eval_points:
        Z = P.polymul(Z, [-r, 1.0])
    return A_polys, B_polys, C_polys, Z

def combine(z, polys):
    """A(X) = Σ z_j * A_j(X)"""
    result = np.zeros(1)
    for zj, poly in zip(z, polys):
        result = P.polyadd(result, zj * poly)
    return result

def poly_divmod(numer, denom):
    """polynomial long division. returns (quotient, remainder)"""
    return P.polydiv(numer, denom)

# ============ Test: x^2 + x = 12 ============
def main():
    # R1CS for x^2 + x = 12
    # vars: (1, out, x, w1)
    A = np.array([[0,0,1,0], [1,0,0,0]], dtype=float)
    B = np.array([[0,0,1,0], [0,0,1,1]], dtype=float)
    C = np.array([[0,0,0,1], [0,1,0,0]], dtype=float)
    eval_points = [1.0, 2.0]

    A_p, B_p, C_p, Z = r1cs_to_qap(A, B, C, eval_points)
    print("Z(X) coefs:", Z, "  (X^2 - 3X + 2)")

    # witness z* = (1, 12, 3, 9)
    z = [1, 12, 3, 9]
    A_X = combine(z, A_p)
    B_X = combine(z, B_p)
    C_X = combine(z, C_p)
    print(f"A(X) = {A_X}")  # 期望 [5, -2]
    print(f"B(X) = {B_X}")  # 期望 [-6, 9]
    print(f"C(X) = {C_X}")  # 期望 [6, 3]

    AB = P.polymul(A_X, B_X)
    AB_minus_C = P.polysub(AB, C_X)
    print(f"A(X)B(X) - C(X) = {AB_minus_C}")  # 期望 [-36, 54, -18]

    H, R = poly_divmod(AB_minus_C, Z)
    print(f"H(X) = {H}  (期望 [-18])")
    print(f"Remainder = {R}  (期望 [0])")

    # 检查 evaluation points
    for r in eval_points:
        a = P.polyval(r, A_X)
        b = P.polyval(r, B_X)
        c = P.polyval(r, C_X)
        print(f"  at X={r}: A·B - C = {a*b - c}  (期望 0)")

if __name__ == "__main__":
    main()

预期输出：

Z(X) coefs: [ 2. -3.  1.]   (X^2 - 3X + 2)
A(X) = [ 5. -2.]
B(X) = [-6.  9.]
C(X) = [6. 3.]
A(X)B(X) - C(X) = [-36.  54. -18.]
H(X) = [-18.]
Remainder = [0.]
  at X=1.0: A·B - C = 0.0
  at X=2.0: A·B - C = 0.0

---

六、关键直觉

6.1 为什么这个变换"好"？

1. 聚合：$m$ 个独立 R1CS 检查 → 1 个多项式整除关系
2. 概率验证：Schwartz-Zippel — 在随机点 $\tau$ 检查 $A(\tau)B(\tau) - C(\tau) = H(\tau) Z(\tau)$，错误概率 $\leq \deg / |\mathbb{F}|$
3. 承诺友好：deg-bounded poly 可用 KZG（pairing）一次承诺，proof 仅 1-3 group element

6.2 与 Schwartz-Zippel 的关系

Lemma：非零多项式 $f$ 在均匀随机点 $\tau$ 求值为 0 的概率 ≤ $\deg(f)/|\mathbb{F}|$

如果 prover 作弊（错的 $H$ 使等式不成立），剩余 $f := AB - C - HZ$ 非零、deg ≤ $2m$；在 $|\mathbb{F}| \approx 2^{256}$ 域上随机点 $\tau$ 求值为 0 的概率 ~ $2m/2^{256}$，可忽略。

6.3 在 $\mathbb{F}_p$ 而非 $\mathbb{R}$

实际 SNARK 工作在椭圆曲线 scalar field $\mathbb{F}_r$（如 BLS12-381 的 $r$ ~ 255-bit 素数）。所有 Lagrange 计算都在 $\mathbb{F}_r$ 中。FFT 用 $r$ 的 2-adicity 选择 unity roots（如 $r-1 = 2^{32} \cdot \ldots$）。

---

七、协议关系图

R1CS:    A z ∘ B z  =  C z              (m 个标量约束)
            │
            │ Lagrange 插值 (每变量一组三个 poly)
            ▼
QAP:     A(X) B(X) - C(X) = H(X) · Z(X)  (1 个多项式关系)
            │
            │ KZG / FRI 承诺 + 随机求值 τ
            ▼
SNARK:   3 个 group element (Groth16) /
         9 个 group element (PlonK) /
         几十 KB (STARK)

---

八、历史与论文

Quote (GGPR 2013): "QAPs allow us to express NP statements as polynomial identities, opening the door to algebraic SNARKs."

---

九、应用对应

QAP 是 SNARK 第一代核心；现代 SNARK（PlonK 系）放弃了 QAP 的"每个乘法门一行"的限制，转向 custom gate + lookup 表达力更强。

---

十、常见陷阱

1. Eval points 必须互异：否则 $Z(X)$ 有重根，插值不唯一
2. 域选错：Lagrange 在 $\mathbb{F}_p$ 中做，必须 $p$ > $m$（否则 $r_i$ 不够选）
3. Deg 超出：witness 让 $A B - C$ 度数超过预期 → KZG 承诺会出错
4. Witness reuse：如果同 witness 用于多个 QAP，需要 binding（add boundary constraint）
5. 0 处求值的歧义：Lagrange 在域上良定义，但具体实现需要 mod inverse 处理

---

十一、关键速查（QAP）

---

十二、面试题

Q1: 为什么 QAP 用 Lagrange 插值而不是 monomial basis？

A1: Lagrange basis 在 evaluation points 处取值要么 0 要么 1，使得 "$\vec{z}$ 满足约束" 直接对应 "$A(r_i)B(r_i) = C(r_i)$"，便于聚合到整除关系。Monomial basis 没这个 nice property（每个变量影响所有 evaluation points）。

Q2: 如何选 evaluation points？

A2: 实践用 unity roots（$\omega^i$ for $i=0..m-1$，$\omega^m = 1$），原因：(1) FFT 加速 Lagrange 插值/求值到 $O(m \log m)$；(2) $Z(X) = X^m - 1$，简洁；(3) 现代曲线如 BLS12-381 选择就是为了大 2-adicity。

Q3: $H(X)$ 度数是多少？

A3: $\deg(AB - C) \leq 2(m-1) = 2m - 2$，$\deg(Z) = m$，所以 $\deg(H) \leq m - 2$。这个度数 bound 决定 prover commitment cost、verifier degree check 复杂度。

Q4: QAP 的安全性来自哪里？

A4: (1) Schwartz-Zippel 保证非零多项式在随机点求值为 0 概率 negl；(2) 多项式承诺方案（KZG）的 binding 防 prover 改变多项式；(3) Knowledge-of-exponent assumption（KoE）保证 prover "真知道" witness 多项式。Groth16 安全性是这三个的综合。

Q5: 为什么 PlonK 系不再用 QAP？

A5: QAP 的 "每乘法门一行" 限制了表达：复杂 gate（如 lookup、bit decomposition）需要展开成大量乘法门，电路膨胀。PlonK 用 plonkish arithmetization：固定列结构 + custom gates + permutation + lookup tables，单个非线性约束可表达多种 gate，电路紧凑。Halo2 进一步泛化。

---

十三、明日预告

Day 214 — Groth16：基于 QAP 构造 succinct NIZK，3 个 group element 的 proof，以及神秘的 trusted setup ceremony（toxic waste 是怎么生成的？）。