3.4 STARK：不办仪式的透明证明

3.4 STARK：不办仪式的透明证明

本节摘要：STARK 用哈希函数与纠错码把零知识证明的信任来源压缩到"哈希函数别被攻破"这一条：无需任何可信仪式、天然抗量子、证明器在大规模计算上极快，代价是几十到上百 KB 的证明体积。本节拆解低度扩展与 FRI 折叠两大发动机，并用小规模演算演示"低次多项式骗不了抽查"。承接 3.3，通往第 4 章的道具箱。

不办仪式的底气

3.3 节留下的"仪式焦虑"，STARK 给出的不是缓解而是取缔：协议里没有需要保密的陷阱参数，公开参数只有哈希函数与域的选取——任何人都能审查，无人需要被信任。这个"透明"属性来自材料学的彻底更换：SNARK 系依赖椭圆曲线配对这类高级结构，STARK 全程只用抗碰撞哈希与有限域算术。哈希假设的强度远高于配对假设，而且量子算法（Shor 那一类）对哈希只有平方级加速、对配对是灭顶之灾——STARK 因此顺带拿到抗量子属性，7.3 节会再回到这一点。

交换条件同样直白：证明体积。Groth16 两百字节能办的事，STARK 通常要几十到上百 KB。为什么？它的证明本质上是" Merkle 树上的一叠抽查凭证"——每个抽查点都要附带验证路径，路径长短与树高对数相关，抽查次数与安全等级挂钩，加起来就是几十 KB 的合理量级。这笔账不是缺陷，是两种货币之间的汇率：SNARK 用一次仪式换小证明，STARK 用大带宽换零信任。哪些场景愿意付带宽？证明器吞吐敏感的超大规模计算（批量交易的压缩验证）、对量子风险零容忍的审计场景、以及需要公开可复现生成过程合规场景——这三类恰是 STARK 生产线的主战场。

发动机一：低度扩展

STARK 的核心断言来自代数：一段计算若执行正确，其执行轨迹满足一组低次多项式约束；而低次多项式被整条曲线"锁死"——改任何一处求值，都会把整条曲线从低次拉出低次范围。这就是低度扩展（Low-Degree Extension）的检验逻辑：把多项式在一个远大于次数的扩展域上求值，作弊者若篡改轨迹哪怕一个点，扩展后的值序列就不再对应任何低次多项式，抽查立刻暴露。

空口无凭，跑一个小规模演算（普通整数域即可演示思想；真实协议在有限域上做）：

# 低度扩展演示：低次多项式"刚性"——改一点，处处失态
def eval_poly(coeffs, xs):                 # coeffs 低位在前
    return [sum(c * x**i for i, c in enumerate(coeffs)) for x in xs]

deg2 = [5, 3, 2]                           # f(x) = 2x^2 + 3x + 5，二次
domain = list(range(16))                   # 16 个点，远多于 3 个系数
clean = eval_poly(deg2, domain)

tampered = clean[:]                        # 作弊者改一个点的值
tampered[7] += 1

# 检验：对点序列做最小二乘二阶拟合，看最大残差
import statistics
def fit_residual(ys, xs, deg=2):
    # 构造范德蒙矩阵的最小二乘解（教学规模，直接用均方残差近似）
    n = len(xs)
    A = [[x**k for k in range(deg + 1)] for x in xs]
    # 正规方程求解（3x3，克莱姆法则即可）
    AtA = [[sum(A[r][i] * A[r][j] for r in range(n)) for j in range(deg+1)] for i in range(deg+1)]
    Aty = [sum(A[r][i] * ys[r] for r in range(n)) for i in range(deg+1)]
    def solve3(M, v):
        import copy
        M = copy.deepcopy(M); v = v[:]
        for col in range(3):
            piv = max(range(col, 3), key=lambda r: abs(M[r][col]))
            M[col], M[piv] = M[piv], M[col]; v[col], v[piv] = v[piv], v[col]
            for r in range(3):
                if r != col and M[col][col]:
                    f = M[r][col] / M[col][col]
                    M[r] = [a - f*b for a, b in zip(M[r], M[col])]
                    v[r] -= f * v[col]
        return [v[i] / M[i][i] for i in range(3)]
    c = solve3(AtA, Aty)
    resid = [ys[r] - sum(c[k] * xs[r]**k for k in range(deg+1)) for r in range(n)]
    return max(abs(e) for e in resid)

print("干净轨迹的最大残差:", fit_residual(clean, domain))      # ≈ 0
print("篡改一点后最大残差:", fit_residual(tampered, domain))   # 明显大于 0
# 结论：一次改动污染整段拟合——低次结构被破坏，抽查必露馅
​

干净轨迹对二次拟合的残差约等于零，改动一个点后残差立刻跳出噪声级——这正是"低次刚性"的直感形态。真实协议把这个性质推到极限：扩展域上任意两个低次多项式的求值序列几乎处处不同，所以随机抽查几个点就能高置信度判真伪，与 2.2 节 PCP 的"抽查经济学"完全同源。

发动机二：FRI 折叠

剩一个问题：验证者凭什么相信"被承诺的值序列真的来自某个低次多项式"，而不是作弊者随便编的？逐点验证不可行，答案是一台叫 FRI（快速 Reed-Solomon 交互式近邻证明）的折叠机。思路像给嫌疑序列做"代数脱水"：把多项式系数按奇偶位置拆成两个次数减半的多项式，原序列的值可以用这两个"半身"在平方点上的取值重组出来；对半身再拆，次数一路减半；若原始序列真的来自低次多项式，折叠若干轮后会塌缩成常数。作弊序列撑不过几轮就露出"怎么折都折不成低次"的马脚。全过程用 Merkle 树承诺、哈希调用代替交互，抽查凭证即最终证明。

图：FRI 折叠机的层次结构

折叠的数学细节（平方域、域上二取一、随机线性组合）在 4.3 节多项式承诺里还会以通用形式再遇一次——那里你会看到 FRI 与 KZG 其实是同一问题的两种答案。

与 SNARK 的对位总结

把两家族放回一张表：信任来源，仪式对公开哈希；证明大小，两百字节级对几十 KB；验证成本，常数级配对对对数级哈希；证明器规模效应，FFT 瓶颈对准线性并行；量子威胁，灭顶对平方级降速。没有冠军，只有场景：验证带宽贵到极致、电路稳定，选 SNARK 系；规模巨大、要透明、要抗量子，选 STARK 系。4.4 节讲算术化时你会看到，R1CS 与 AIR 分别是两家的"轨迹方言"，方言背后的语法是同一套。

答疑三则

**问：证明几十 KB，链上放得下吗？**直接上链通常放不下也放不起，行业的成熟做法是两段式：STARK 先在链下完成对海量计算的压缩，聚合器再把多份 STARK 递归收拢成一份小证明，最后由配对路线的轻量证明转接上链——两代技术各干各的活，接口是一份标准格式的中间证明。理解了这个组合拳，就读懂了多数扩容产品的架构图。

**问：只用哈希，会不会反而更怕算力增长？**怕的是完全不同性质的攻击：哈希路线的威胁是穷举能力的线性增长，可以通过提参数档对冲（7.3 节的换算表）；数论路线的威胁是算法突破的断崖式失效，参数档救不了。两者放在一起，STARK 的"慢变量风险"在长期项目里是加分项。

**问：AIR 写轨迹和写电路哪个难？**思维方式差异大于难度差异。AIR 要求把逻辑想成"状态与转移"——每行怎么变成下一行；习惯命令式编程的工程师通常要一两周换脑，之后表达重复计算反而比电路顺手。团队选型时不妨让两位工程师各写同一逻辑的小样，比较约束数与维护手感再定。

本节要点回顾

• 透明性来自材料更换：只用哈希与有限域，无人需要被信任，顺带收获抗量子；
• 低次刚性是抽查可行的根：低次多项式改一点则全貌失态，随机抽查几个点即判真伪；
• FRI 是代数脱水机：奇偶拆分逐轮折叠，次数减半直至常数，作弊序列折不出低次；
• 代价是带宽：几十 KB 的证明是"零仪式信任"的公开标价，付得起就是朋友。