4.3 多项式承诺：把一条曲线装进一个数字

4.3 多项式承诺：把一条曲线装进一个数字

本节摘要：多项式承诺把一条可能包含亿万系数的曲线封装成定长承诺，此后对任意单点开箱验证而不泄露其余。本节讲清它为什么是简洁证明的枢纽（Schwartz-Zippel 引理）、KZG 与 FRI 两条实现路线的骨架，并用插值与随机点检验的演算落地。承接 4.2 的知识论证，通往 4.4 的算术化。

为什么偏偏是多项式

前两章的道具各管一摊，真正的"压缩奇迹"发生在多项式这里。动机先摆出来：证明一份计算正确，等价于断言海量中间值满足海量约束——直接给验证者看所有值，证明就大得不可用。多项式提供的捷径是：把一整批等式打包成"某个多项式在某点取值为零"。具体做法有两步。第一步，用插值把约束点集编码为多项式：过 n 个点能且只能确定一条次数小于 n 的多项式，于是"这些点上的值都对"变成"这条多项式存在且次数合规"。第二步，用 Schwartz-Zippel 引理做随机检验：两个次数不超过 d 的不同多项式，至多在 d 个点相交；在域里随机取一个点，两者恰好相等的概率不超过 d 除以域的大小。取百万级大小的域、千次多项式，撞车概率百万分之一——抽查一次就够了。

于是验证成本的结构变了：验证者不再读所有值，只验证"承诺值在随机点上开箱一致"。证明尺寸、验证开销都从"与计算规模同阶"塌缩到"与承诺方案常数同阶"。这就是 3.3 节 SNARK 家族能做出两百字节证明的代数根源。

两条实现路线：KZG 与 FRI

同一目标——"承诺整条曲线，单点可开箱，全程不泄露"——工程上有两条主流路线，3.4 节已见过 FRI，这里补齐它的对手与公共骨架。

KZG 承诺走配对路线。仪式阶段产出一组"有毒参数"：生成元序列 g、g^τ、g^(τ²)、……（τ 为仪式后立即销毁的秘密数）。承诺时用这组参数做线性组合，把整条多项式压成一个群元素 C = g^(f(τ))——注意这是对 τ 求值，而 τ 只有仪式参与者知道、随即烧毁。开箱时证明者给出 f 在挑战点 z 的值与商多项式承诺，验证者用一条配对等式核对：f(z) 若为真值，则 f(X) − f(z) 必被 (X − z) 整除，商多项式存在——整除性就是正确性的代数判据。KZG 的证明只有几十字节，验证一两次配对，代价是必须办仪式（4.5 节专门拆）。

FRI 路线只用哈希：对多项式求值序列做 Merkle 承诺，然后 3.4 节讲的奇偶折叠逐轮降次，抽查路径即证明。免仪式、抗量子，证明相应更大。两条路线的分工可以一句话概括：带宽便宜、要仪式的地方用 KZG；信任要归零、带宽买得起的地方用 FRI。

动手感受：插值、随机点与整除判据

三个抽象名词——插值、Schwartz-Zippel、商多项式——各配一段代码就都落地了。下面这段会话把 KZG 的核心判据（"f(X) − f(z) 应被 X − z 整除"）用普通整数域演出来：

# 多项式承诺三件套演示：插值、随机点检验、整除判据
P = 1000003                                       # 玩具素数域

def poly_mul(a, b):                               # 系数卷积
    out = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            out[i + j] = (out[i + j] + x * y) % P
    return out

def poly_sub(a, b):
    n = max(len(a), len(b))
    return [( (a[i] if i < len(a) else 0) - (b[i] if i < len(b) else 0) ) % P for i in range(n)]

def interpolate(xs, ys):                          # 拉格朗日插值（演示规模）
    n = len(xs)
    coeffs = [0] * n
    for i in range(n):
        num, den = [1], 1
        for j in range(n):
            if j == i: continue
            num = poly_mul(num, [(-xs[j]) % P, 1])
            den = den * (xs[i] - xs[j]) % P
        scale = ys[i] * pow(den, -1, P) % P
        for k, c in enumerate(num):
            coeffs[k] = (coeffs[k] + scale * c) % P
    return coeffs

def eval_at(coeffs, x):
    v, xp = 0, 1
    for c in coeffs:
        v = (v + c * xp) % P
        xp = xp * x % P
    return v

# 第一步：插值——四个约束点变成一条三次多项式（这就是"把数据变成曲线"）
xs, ys = [1, 2, 3, 4], [10, 28, 64, 124]
f = interpolate(xs, ys)
print("插值出的多项式系数:", f)                    # [4, 2, 3, 1] 低位在前 => f(x)=x^3+3x^2+2x+4

# 第二步：Schwartz-Zippel——另一条"差一点"的曲线与它随机点不相等
f_bad = f[:]; f_bad[1] = (f_bad[1] + 7) % P       # 篡改一个系数
import random
z = random.randrange(2, P - 1)                    # 域里随机取一点
print("随机点检验:", eval_at(f, z), "!=", eval_at(f_bad, z),
      eval_at(f, z) != eval_at(f_bad, z))          # 几乎必然不等：抽查一次即分真伪

# 第三步：整除判据——f(X) - f(z) 应被 (X - z) 整除
def divmod_poly(a, b):                            # 简易多项式除法
    a = a[:]; q = [0] * max(1, len(a) - len(b) + 1)
    for i in range(len(a) - 1, len(b) - 2, -1):
        coef = a[i] * pow(b[-1], -1, P) % P
        q[i - len(b) + 1] = coef
        for j in range(len(b)):
            a[i - len(b) + 1 + j] = (a[i - len(b) + 1 + j] - coef * b[j]) % P
    return q, [x % P for x in a[:len(b)-1]]

q, rem = divmod_poly(poly_sub(f, [eval_at(f, z)]), [(-z) % P, 1])
print("余式:", rem, "（全零即整除成立，开箱值真实）")
# 对照实验：真实 KZG 里多项式被承诺锁死，攻击者只能谎报开箱值——
# 谎报 y' 不等于 f(z) 时，f(X) - y' 不再被 (X - z) 整除，余式非零，当场拒绝
lie_y = (eval_at(f, z) + 7) % P
_, rem_bad = divmod_poly(poly_sub(f, [lie_y]), [(-z) % P, 1])
print("谎报开箱值的余式:", rem_bad)
​

插值段输出的系数能对上手算（f(x) = x³ + 3x² + 2x + 4 过那四点），随机点检验把"不同多项式"一眼分开，整除判据则是 KZG 验证等式的代数本质——三段连起来，就是"把一条曲线装进一个数字"的完整心智模型。

承诺之后的世界

多项式承诺就位后，证明系统的最后一块拼图只剩"怎么把任意计算翻译成多项式"——这正是 4.4 节算术化的任务。到那时，第 3 章流水线的四道主工序将全部打通。

本节要点回顾

• 多项式是压缩容器：插值把点集变成曲线，Schwartz-Zippel 让单点抽查代替全量核对；
• KZG 的代数判据：开箱值真实当且仅当差式被一次式整除，商多项式承诺即证据；
• 两路线分工：KZG 用仪式换 48 字节证明，FRI 用带宽换零仪式与抗量子；
• 验证成本解耦：承诺与抽查让验证开销不再随计算规模线性增长，简洁性由此而来。