知识库 / STARK 算法详解：如何构建无需可信设置的可扩展零知识证明

STARK 算法详解：如何构建无需可信设置的可扩展零知识证明

协议详解 · 2026-09-23

概述

在零知识证明领域，zk-SNARK凭借极小的证明尺寸（约200-500字节）成为以太坊Layer 2的主流选择。然而，其核心缺陷在于必须依赖可信设置（trusted setup）——一次性的多项式承诺密钥生成若被破坏，攻击者即可伪造任意证明。

2018年，Eli Ben-Sasson、Alessandro Chiesa、Erman İnan等人在论文 *Scalable, transparent arithmetizations of tree and vector commitments* 中提出 STARK（Scalable Transparent ARgument of Knowledge）。与SNARK相比，STARK具有三大核心优势：

  • 无需可信设置：基于碰撞抗 Hash 函数，安全性不依赖任何秘密参数
  • 后量子安全：不依赖离散对数或椭圆曲线配对，对Shor算法免疫
  • 多项式规模可验证性：证明大小与电路规模的对数关系（$O(\log^2 n)$），验证时间与 $O(\log n)$
本文将从算术化原理切入，系统讲解STARK的完整构造流程，并通过与SNARK的对比分析阐明各自的适用场景。

算术化：从计算到多项式

STARK的核心思想是将计算问题转化为多项式恒等式问题。这个过程称为"算术化"（arithmeticization）。

计算的多项式表示

假设我们有一个计算 $C(x) = y$，其中 $C$ 是一个电路（计算描述），$x$ 是输入，$y$ 是输出。算术化的目标是将 $C$ 的每一步运算编码为一个低次多项式约束。

具体做法是：

  • 取用表（Lookup Table）：将计算的所有状态（witness）编码为多项式 $w(z)$
  • 约束多项式：构造多项式 $C(w(z)) = 0$，使得只有当 $w$ 是正确的计算见证时，该多项式在特定域上为零

Fast Reed-Solomon IOPP Code（FRI）

STARK使用一种称为 FRI协议 的交互式测试来验证多项式是否为低次。其基本思路是"折叠"（folding）：

CODE
输入：多项式 P(x) ∈ F_p[x]，度 ≤ d
验证：P(x) 是否为度 ≤ d/2 的多项式？

步骤：
1. 随机选取 α ∈ F_p
2. 构造 Q(x) = (P(x) + P(-x))/2 + α·(P(x) - P(-x))/(2x)
3. 重复上述步骤，每次将度数减半
4. 最终验证剩余常数是否为低度多项式的值

这个过程本质上是随机线性组合：如果 $P(x)$ 原本是高度多项式，那么随机折叠后几乎必然也是高度多项式（概率可忽略）。

交互式STARK协议

协议流程

完整的交互式STARK证明包含以下阶段：

关键数学细节

设 $F$ 为有限域，$H \subset F$ 为子群（evaluation domain）。Prover 需要证明多项式 $P(x)$ 满足：

$$\forall z \in H, \quad C(P(z)) = 0$$

这等价于证明 $C(P(x))$ 在 $H$ 上为零多项式。根据多项式插值定理，这又等价于证明：

$$C(P(x)) \equiv 0 \pmod{Z_H(x)}$$

其中 $Z_H(x) = \prod_{h \in H}(x - h)$ 是范德蒙德多项式。

非交互式STARK：Fiat-Shamir变换

从交互式到非交互式

与所有交互证明系统一样，STARK可以通过 Fiat-Shamir启发式 转换为非交互式版本：将验证者的随机挑战替换为对之前消息的哈希值。

PYTHON
# 伪代码：Fiat-Shamir变换
# 原始交互式协议需要 verifier 随机选择 α_1, α_2, ..., α_k
# Fiat-Shamir 将其替换为：
alpha_1 = hash(commitments, public_input)
alpha_2 = hash(alpha_1, folded_poly_1)
alpha_k = hash(alpha_{k-1}, folded_poly_{k-1})

安全性注意：Fiat-Shamir在随机预言机模型下是安全的，但在标准模型下需要额外假设。STARK的抗量子性正是源于其仅依赖Hash函数而非离散对数。

证明尺寸分析

STARK的证明尺寸主要包括：

组件尺寸估算说明
多项式承诺$O(d \log d)$ 字节Merkle 树路径证明
FRI 折叠过程$O(\log^2 n)$ 字节每层折叠的查询证明
边界条件$O(1)$ 字节初始/终止状态验证
相比SNARK的常数级证明尺寸（~200字节），STARK的证明通常更大（KB级），但验证速度更快，且不依赖可信设置。

STARK vs SNARK 系统性对比

核心差异

特性STARKzk-SNARK
可信设置❌ 不需要✅ 必需（通常）
后量子安全✅ 是❌ 否（依赖配对/离散对数）
证明尺寸KB级~200-500字节
验证时间$O(\log n)$$O(1)$
生成时间$O(n \log n)$（NTT加速）$O(n)$
密码学假设仅Hash函数配对/DDH/知识假设
典型实现Starkware、Polygon STARKZCash、zkSync、Scroll

为何选择STARK？

  • 合规场景：政府/金融系统对"可信设置"的接受度极低，STARK无此风险
  • 长期安全：量子计算机威胁下，STARK的安全性假设更坚固
  • 可扩展性：对于大规模计算（如区块链交易批量验证），STARK的并行化特性更具优势

为何选择SNARK？

  • 极小证明：链上验证成本极低的场景（如zkRollup）
  • 成熟生态：Circom、SnarkJS等工具链完善
  • 常数验证时间：适合高频小额验证场景

国密场景下的适配

SM3哈希的适用性

STARK的FRI协议核心依赖碰撞抗性Hash函数。SM3（GM/T 0004-2012）是中国国家密码管理局制定的密码杂凑算法，输出256位，与SHA-256在同一安全级别。

关键事实：

  • SM3的碰撞抗性为 $2^{128}$，满足STARK的安全需求
  • SM3的输出长度与STARK所需的字段元素匹配
  • 现有STARK实现（如STARK.js）已提供SM3哈希函数接口

适配路径

CODE
STARK（以太坊生态）     STARK（国密场景）
    ↓                        ↓
SHA3-256                SM3 (GM/T 0004-2012)
    ↓                        ↓
FRI协议验证              FRI协议验证（相同逻辑）
    ↓                        ↓
Merkle树承诺              国密SSTree/Merkle树

注意：使用SM3替代SHA3时，需重新生成所有公共参考字符串（CRS）和证明验证参数，不能简单替换哈希函数。

潜在问题

  • 性能差异：SM3的软件实现通常比SHA3慢2-3倍（x86架构上），但硬件加速（如国密卡）可消除差距
  • 生态兼容：主流STARK库（Cairo、StarkNet）均以SHA3为基础，国密适配需自定义哈希层

相关实践

参考资料

  • Ben-Sasson, E., Chiesa, A., Spooner, N. (2018). *Interactive Oracle Proofs*. CRYPTO 2018. https://eprint.iacr.org/2016/118
  • Ben-Sasson, E. et al. (2018). *Scalable, transparent arithmetizations of tree and vector commitments*. https://eprint.iacr.org/2018/046
  • GM/T 0004-2012 SM3密码杂凑算法
  • StarkWare Industries. (2021). *STARKs, Perfect Arguments for Fuzzy Machines*. https://starkware.co/resource/starks-perfect-arguments-for-fuzzy-machines/
  • Feldman, J. et al. (2024). *ZK Stack: A Comprehensive Guide to Zero-Knowledge Proof Systems*. Ethereum Foundation.
← 返回知识库