Polynomial IOP — Sumcheck Protocol

日期: 2026-12-07 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #PIOP #Sumcheck #抽象框架

---

今日目标

---

一、Polynomial IOP 抽象

1.1 动机

PlonK / Groth16 / STARK 表面差异大，但核心都是：

1. Prover 把 statement 编码为多项式 $f(X)$
2. 用某种 PCS commit $f$
3. Verifier 在随机点 $\zeta$ 检查 $f(\zeta)$
4. Schwartz-Zippel 给 soundness

抽象成 PIOP (Polynomial Interactive Oracle Proof)：

Prover 与 Verifier 交互；Prover 发送 oracle access to polynomial (commitment + opening); Verifier 检查 polynomial identities at random points。

1.2 PIOP → SNARK 通用编译

PIOP (理论)
    ↓ + Polynomial Commitment Scheme (PCS)
NIZK (FS-compiled SNARK)
    ↓ + Recursion
Recursive SNARK

不同 SNARK 用不同 PCS：

• Groth16 / PlonK: KZG
• Halo2: IPA
• STARK: FRI (over Reed-Solomon)
• Brakedown: tensor codes
• Ligero: Reed-Solomon + hash

→ 只要切换 PCS，PIOP 自动得到不同 SNARK。

---

二、Sumcheck Protocol (LFKN 1992)

2.1 问题

设 $g(X_1, ..., X_v)$ 是 $v$-元多项式，每变量度数 $\leq d$。证明：

$$ H = \sum_{x_1 \in {0,1}} \sum_{x_2 \in {0,1}} \cdots \sum_{x_v \in {0,1}} g(x_1, ..., x_v) $$

直接计算需要 $2^v$ 个求值（指数）。Sumcheck 把验证降到 $v$ 轮交互 + 1 次 $g$ 求值。

2.2 协议

Round 1:

• Prover 计算 $g_1(X_1) = \sum_{x_2, ..., x_v} g(X_1, x_2, ..., x_v)$，发送 $g_1$（$v-1$ 求和后是单变量多项式 deg ≤ $d$）
• Verifier check $g_1(0) + g_1(1) = H$
• Verifier 选 $r_1 \stackrel{$}{\leftarrow} \mathbb{F}$，发给 Prover

Round $i$ (2 ≤ i ≤ v):

• Prover 计算 $g_i(X_i) = \sum_{x_{i+1}, ..., x_v} g(r_1, ..., r_{i-1}, X_i, x_{i+1}, ..., x_v)$，发送
• Verifier check $g_i(0) + g_i(1) = g_{i-1}(r_{i-1})$
• Verifier 选 $r_i$

Final:

• 所有 $r_1, ..., r_v$ 选定后，verifier 单次求值 $g(r_1, ..., r_v)$，check $= g_v(r_v)$

2.3 完整流程图

P                                        V
  H = sum_{x} g(x) ──────────────────▶
                                       
  g_1(X_1) (deg ≤ d) ─────────────▶  
                                       check g_1(0)+g_1(1) = H
                                       r_1 ←$ F
                ◀──────── r_1 ───────
  g_2(X_2) ─────────────────────▶
                                       check g_2(0)+g_2(1) = g_1(r_1)
                                       r_2 ←$
                ◀──────── r_2 ───────
        ...
  g_v(X_v) ─────────────────────▶
                                       check g_v(0)+g_v(1) = g_{v-1}(r_{v-1})
                                       r_v ←$
                ◀──────── r_v ───────
                                       Verifier 求值 g(r_1,...,r_v) (oracle)
                                       check = g_v(r_v)

2.4 完备性

诚实 prover 总通过：每轮 $g_i$ 是真实部分求和，等式由定义成立。

2.5 可靠性 — 关键论证

Claim：若 prover 在某轮发了错的 $g_i$，剩余协议接受概率 ≤ $vd / |\mathbb{F}|$。

证明（直觉）：

• 若 $g_i$ 错（$\deg \leq d$），则 $g_i$ 与正确 $g_i^*$ 是不同 deg-$d$ 多项式
• Schwartz-Zippel: $g_i(r_i) = g_i^*(r_i)$ 概率 $\leq d / |\mathbb{F}|$
• 即剩余协议（基于 $g_i(r_i)$）误导 prover 概率高
• $v$ 轮 union bound 给 $vd / |\mathbb{F}|$

→ 在 $|\mathbb{F}| \approx 2^{256}, v \cdot d \leq 10^4$ 时 negl。

2.6 复杂度

关键：verifier 工作 $O(v) = O(\log N)$（如果 $N = 2^v$）→ succinct！

---

三、Multilinear Extensions

3.1 定义

设 $f: {0, 1}^v \to \mathbb{F}$ 是布尔函数。Multilinear extension (MLE) $\tilde{f}: \mathbb{F}^v \to \mathbb{F}$ 是唯一在每变量上 deg ≤ 1 的多项式扩展，使得 $\tilde{f}|_{{0,1}^v} = f$。

公式：

$$ \tilde{f}(X_1, ..., X_v) = \sum_{b \in {0,1}^v} f(b) \cdot \prod_{i=1}^v (X_i b_i + (1-X_i)(1-b_i)) $$

最后一项是"Lagrange basis on hypercube"。

3.2 与 Univariate 对比

3.3 GKR 协议（Goldwasser-Kalai-Rothblum 2008）

用 sumcheck 验证 layered arithmetic circuit：每层用一次 sumcheck，layer-by-layer reduce。

→ 不需要 trusted setup, prover $O(\text{circuit size})$, verifier $O(\log)$。

但 GKR 不是 ZK（leaks evaluations）；后续 Justin Thaler、Setty 等人加 ZK 包装得 Spartan / Hyrax / Brakedown。

---

四、用 Sumcheck 构造 SNARK

4.1 Spartan (Setty 2020)

把 R1CS 检查 $A z \circ B z = C z$ 转 multilinear 形式：

$$ \sum_{x \in {0,1}^{\log m}} \tilde{eq}(\tau, x) \cdot \left( \tilde{A}_z(x) \cdot \tilde{B}_z(x) - \tilde{C}_z(x) \right) = 0 $$

用 Sumcheck 证；最终一次多元 PCS opening。

→ Spartan：linear-time prover + sublinear verifier + transparent（用 Hyrax/Brakedown PCS）。

4.2 HyperPlonk (Chen-Bunz-Boneh 2022)

PlonK 的 multilinear 版本：所有 columns 看作 boolean hypercube 上的函数；约束转 sumcheck。

优势：

• Prover 更快（无 FFT，仅 sumsum）
• 用 multilinear PCS（Brakedown / Hyrax / Bunz Pre-Processing）

---

五、代码 — 4 变量 Sumcheck 简化实现

"""
sumcheck.py — 4-变量 Sumcheck protocol 教学实现
简化: 用 Z_p, p 较小; 不含 FS / 不含 PCS
"""
import secrets
from itertools import product

P = 2**31 - 1  # Mersenne prime

def field_add(a, b): return (a + b) % P
def field_mul(a, b): return (a * b) % P
def field_sub(a, b): return (a - b) % P

# 多元多项式表示: dict[(d1,d2,d3,d4)] = coef
class MultiPoly:
    def __init__(self, terms, n_vars):
        self.terms = terms  # {(deg_tuple): coef}
        self.n_vars = n_vars

    def eval(self, x):
        """x: tuple of length n_vars"""
        s = 0
        for degs, c in self.terms.items():
            term = c
            for v, d in zip(x, degs):
                term = field_mul(term, pow(v, d, P))
            s = field_add(s, term)
        return s

    def partial_sum_over_remaining(self, fixed_prefix):
        """
        固定前 k 个变量为 fixed_prefix (list), 对剩余变量在 {0,1} 求和.
        返回剩余变量函数（仍是 MultiPoly with prefix vars 替换）
        """
        k = len(fixed_prefix)
        remaining = self.n_vars - k
        # 对剩余 remaining-1 变量在 {0,1} 求和, 留下第 k 个变量
        # 实际实现: 取剩余 remaining 中第一个为 free, 其余 sum over {0,1}
        if remaining < 1:
            return None
        # 我们要返回 g_i(X_i) = sum over X_{i+1..v} ∈ {0,1} of f(prefix, X_i, X_{i+1..v})
        # i.e. 对第 k+1 个变量 (0-indexed: index k) 自由, 其余 ∈ {0,1}
        # 返回单变量多项式 (作为 list of coefs in increasing deg)
        # max deg of var k = max degs[k] across all terms
        max_d = max((d[k] for d in self.terms.keys()), default=0)
        result_coefs = [0] * (max_d + 1)
        # 枚举剩余 (n_vars - k - 1) 变量取值 ∈ {0,1}
        for assignment in product([0, 1], repeat=self.n_vars - k - 1):
            # 完整 x: prefix + [free X_k] + assignment
            for degs, c in self.terms.items():
                term_val = c
                # multiply by prefix vars
                for j, p_v in enumerate(fixed_prefix):
                    term_val = field_mul(term_val, pow(p_v, degs[j], P))
                # multiply by assignment vars
                for j, a_v in enumerate(assignment):
                    term_val = field_mul(term_val, pow(a_v, degs[k + 1 + j], P))
                # 剩余系数对应 X_k^{degs[k]}
                result_coefs[degs[k]] = field_add(result_coefs[degs[k]], term_val)
        return result_coefs

def eval_univ(coefs, x):
    s = 0
    for i, c in enumerate(coefs):
        s = field_add(s, field_mul(c, pow(x, i, P)))
    return s

def sumcheck_prove_verify(g):
    """完整 Sumcheck 交互模拟"""
    v = g.n_vars
    # 计算总和 H
    H = 0
    for x in product([0, 1], repeat=v):
        H = field_add(H, g.eval(x))
    print(f"True sum H = {H}")
    
    # 协议
    prefix = []
    expected = H
    for i in range(v):
        # Prover 发 g_i(X_i)
        g_i = g.partial_sum_over_remaining(prefix)
        # Verifier check: g_i(0) + g_i(1) == expected
        check = field_add(eval_univ(g_i, 0), eval_univ(g_i, 1))
        assert check == expected, f"Round {i+1} fail: {check} vs {expected}"
        print(f"Round {i+1}: g_{i+1} coefs = {g_i}, sum = {check} ✓")
        # Verifier 选 r_i
        r_i = secrets.randbelow(P)
        prefix.append(r_i)
        expected = eval_univ(g_i, r_i)
    
    # Final: verifier 自己求值 g(r_1, ..., r_v)
    final = g.eval(tuple(prefix))
    assert final == expected, f"Final fail: {final} vs {expected}"
    print(f"Final check: g({prefix}) = {final} == expected {expected}  ✓")

if __name__ == "__main__":
    # 4-变量例子: g(X1,X2,X3,X4) = X1*X2 + X3*X4 + 2*X1*X3*X4
    g = MultiPoly({
        (1,1,0,0): 1,
        (0,0,1,1): 1,
        (1,0,1,1): 2,
    }, n_vars=4)
    sumcheck_prove_verify(g)

预期输出（4 轮 + final）：

True sum H = 7   (or some value, dependent on g)
Round 1: g_1 coefs = [...], sum = 7 ✓
...
Final check: g(r1,r2,r3,r4) = X == expected X ✓

---

六、协议关系图

   PIOP (theoretical)
       ↓
   ┌─────────────────────┐
   │ Polynomial Identity │  ← Sumcheck / GKR / quotient
   │ Test at random pt    │
   └─────────────────────┘
       ↓ + PCS
   ┌──────┬───────┬───────┬───────┐
   │ KZG  │  IPA  │  FRI  │ Brake-│
   │      │       │       │ down  │
   └──┬───┴───┬───┴───┬───┴───┬───┘
      │       │       │       │
   PlonK   Halo2   STARK   Spartan
   Groth16

---

七、历史与论文

---

八、应用对应

---

九、常见陷阱

1. 变量顺序：sumcheck 是逐变量 reduce，prover/verifier 必须一致顺序
2. 多元 PCS：multilinear 不能直接用 KZG（KZG 是 univariate），需要 multilinear KZG (Papamanthou-Shi-Tamassia 2013) 或 Brakedown
3. Soundness：每轮 $\leq d/|\mathbb{F}|$，多轮累加 $\leq vd/|\mathbb{F}|$；要 100-bit security 需 $|\mathbb{F}|, vd$ 平衡
4. Final query 必须 commit：prover 不能 retroactively 改 $g$；要在协议开始 commit
5. ZK 性需额外加随机化：原始 sumcheck 不 ZK（leaks evals）；要加 random masking

---

十、关键速查

---

十一、面试题

Q1: Sumcheck 协议的复杂度？为什么"verifier sublinear"？

A1: Verifier 只做 $O(vd)$ field operations + 1 个 oracle query 给 final $g(r_1,...,r_v)$。$v = \log N$ 时是 $O(\log N \cdot d)$。Prover 端 $O(2^v \cdot d) = O(N \cdot d)$。Sublinear verifier 来自每轮把 $2^v$ 求和压成单变量 deg-$d$ 多项式（仅 $d+1$ 系数）。

Q2: Multilinear extension 与 Lagrange interpolation 的关系？

A2: Multilinear extension 是 multivariate Lagrange：在 boolean hypercube 上插值，每变量 deg ≤ 1。可以看作 univariate Lagrange 的 tensor product。优势：MLE 自然适合 sumcheck（boolean hypercube 上的求和），不需要 FFT。

Q3: Sumcheck 的 soundness 来自哪里？

A3: 每轮 verifier check 等式 $g_i(0) + g_i(1) = $ previous，若 prover 作弊给了 fake $g_i$，则 fake $g_i$ 与真 $g_i^*$ 是不同 deg-$d$ 多项式，Schwartz-Zippel 在随机点 $r_i$ 重合概率 $\leq d/|\mathbb{F}|$。$v$ 轮 union bound $\leq vd/|\mathbb{F}|$。

Q4: Spartan 相对 PlonK 的优势？

A4: (1) Linear-time prover（无 FFT）→ 大电路友好；(2) Multilinear-based，与 multilinear PCS（Brakedown）结合可全 transparent；(3) 直接证 R1CS（无 QAP 转换），适配现有 Circom 生态。代价：proof 大、单 verify 较慢。适合 zkVM 这种"prover bottleneck"场景。

Q5: 为什么 GKR 协议无需 trusted setup？

A5: GKR 协议本质是 sumcheck 链，每层一个 sumcheck，verifier 只需在最后 evaluate 输入层（input layer）的 multilinear extension。不涉及 polynomial commitment（直接 oracle access 假设），因此无 setup。但要变 SNARK 时需要 PCS 实现 oracle → 选 transparent PCS（Brakedown / Hyrax）即可保持无 setup。

---

十二、明日预告

Day 221 — Recursive Proofs：Halo cycle of curves、Mina 的全 recursion 区块链、Nova 的 folding scheme，长度无限的可验证计算。