当一个计算任务被委托给不受信任的第三方执行时，委托者如何在不重新执行该任务的前提下确信结果的正确性？这一问题在计算机科学中被称为可验证计算（Verifiable Computation）。它并非纯粹的理论问题——在云计算场景中，客户端将繁重的运算外包给服务器，却无法保证服务器未曾偷工减料或遭受攻击；在区块链场景中，链上节点不可能重新执行所有交易，却必须对 Layer 2 提交的状态转移做出正确性裁决；在机器学习推理外包中，用户无法验证远端 GPU 集群是否真正运行了指定的模型。可验证计算正是为解决这些问题而生的密码学工具集。
本文将从交互式证明系统的经典理论出发，逐步深入到 Sumcheck 协议、GKR 协议等核心构件，进而讨论从交互式证明到简洁非交互论证（SNARK）的编译过程，然后探讨增量可验证计算（IVC）与 zkVM 架构的前沿进展，最后审视可验证计算在区块链、机器学习推理与可信构建等领域的实际落地情况。
一、可验证计算的动机
云计算中的委托困境
现代计算的一个显著趋势是算力的集中化。企业与个人越来越多地将计算任务外包给云服务提供商——从科学仿真、大规模数据分析到深度学习训练，无不如此。然而，外包计算引入了一个根本性的信任问题：委托方（Delegator）如何验证受托方（Worker）返回的结果确实是对指定输入执行指定程序后的正确输出？
朴素的验证方式是重新执行一遍计算，但这显然违背了外包的初衷。另一种思路是让多个独立的服务商同时计算并比对结果，但这既增加了成本，又无法从根本上排除共谋的可能性。可验证计算提供了第三条路径：受托方在返回计算结果的同时，附上一份简洁的正确性证明（Proof），委托方只需花费远小于原始计算的时间和空间来检验这份证明，即可获得密码学级别的确信。
区块链的可扩展性瓶颈
区块链的安全模型要求每个全节点独立验证所有交易。这一设计在保障去中心化的同时，严重限制了吞吐量。以以太坊为例，主链的计算能力约为每秒 15 至 30 笔交易，远远无法满足全球规模的需求。Layer 2 扩容方案的核心理念是将大量交易的执行移至链下，仅将执行结果和相应的正确性证明提交到链上。链上合约只需验证证明的有效性即可接受状态更新，从而在不牺牲安全性的前提下实现数个数量级的吞吐量提升。
这一架构对可验证计算提出了极为严苛的要求：证明必须足够短小（简洁性，Succinctness），以降低链上存储与验证成本；验证必须足够高效（亚线性，Sublinear），最好在常数时间内完成；而证明生成的开销虽然可以较大，但也不能超出实用范围。
不可信环境中的通用计算
更广义地看，可验证计算的目标是在不信任执行环境的前提下保障计算的完整性（Integrity）。这一需求渗透在众多场景之中：选举计票系统需要向公众证明统计结果的正确性而不泄露个体选票；供应链溯源系统需要证明某批原材料确实经过了指定的检测流程；甚至编译器和构建系统也可以通过可验证构建（Verifiable Build）来证明二进制产物确实由特定源代码编译而来。可验证计算不仅是一项密码学技术，更是一种重新定义数字信任边界的范式。
二、交互式证明回顾
IP 的定义
可验证计算的理论基础是交互式证明系统（Interactive Proof System，IP）。在该模型中，一个计算能力无限的证明者（Prover，通常记为 P）试图说服一个计算能力有限（多项式时间）的验证者（Verifier，通常记为 V）某个命题为真。交互过程由多轮消息交换组成：V 发送挑战（Challenge），P 发送响应（Response），最终 V 根据整个交互记录（Transcript）决定接受或拒绝。
形式化地，一个交互式证明系统满足两个性质：
- 完备性（Completeness）：若命题为真，则诚实的 P 能使 V 以至少 2/3 的概率接受。
- 可靠性（Soundness）：若命题为假，则无论 P 采用何种策略，V 接受的概率不超过 1/3。
概率界限 2/3 和 1/3 的选择是任意的——通过重复协议并取多数结果，错误概率可以指数级递减。
IP = PSPACE
1992 年，Shamir 证明了交互式证明系统的计算能力恰好等同于 PSPACE——即所有可以用多项式空间解决的决策问题的集合。这个惊人的结果远远超出了最初的预期：交互式证明不仅能验证 NP 问题，还能验证诸如量化布尔公式（QBF）等 PSPACE 完全问题。这意味着交互式证明系统具有极其强大的表达能力，为可验证计算奠定了坚实的理论基础。
Shamir 的证明关键依赖于两个技术工具：一是将 PSPACE 完全问题 TQBF（True Quantified Boolean Formula）进行算术化（Arithmetization），将布尔公式转化为有限域上的多项式；二是 Sumcheck 协议——一个用于验证多元多项式在布尔超立方体上求和结果的交互式协议。这两个工具不仅在理论证明中至关重要，也是现代可验证计算系统的核心构件。
Arthur-Merlin 协议与公开硬币
Babai 在 1985 年引入了 Arthur-Merlin（AM）协议的概念，其中 Arthur（验证者）的所有随机性都是公开的，即 Arthur 的每一轮消息仅仅是随机硬币的结果，不含任何私有计算。Goldwasser 和 Sipser 后来证明了公开硬币协议在计算能力上等价于一般的交互式证明系统。这一结论的重要性在于：它保证了验证者无需对随机数保密，从而简化了协议设计并为后续的 Fiat-Shamir 变换奠定了基础。
Fiat-Shamir 变换：从交互到非交互
在实际应用中，交互式协议存在明显的局限——它要求证明者与验证者同时在线并进行多轮通信。Fiat-Shamir 启发式（Fiat-Shamir Heuristic）提供了一种将公开硬币交互式协议转化为非交互式协议的通用方法：用密码学哈希函数（建模为随机预言机，Random Oracle）替代验证者的随机挑战。具体而言，证明者在每一轮中不再等待验证者的挑战，而是将当前的交互记录输入哈希函数，以哈希输出作为下一轮的挑战。这样，整个交互过程被”压缩”为一条单向消息——证明者一次性发送所有的消息和挑战值，验证者通过重新计算哈希来检查一致性。
Fiat-Shamir 变换的安全性在随机预言机模型（Random Oracle Model，ROM）下可以严格证明，但在标准模型下存在已知的反例。尽管如此，它在实践中被广泛采用，是当前几乎所有非交互式简洁论证系统的关键组件。
三、Sumcheck 协议
问题定义
Sumcheck 协议是现代可验证计算中最基本、最核心的交互式协议之一。它由 Lund、Fortnow、Karloff 和 Nisan 于 1992 年提出，用于解决如下问题：给定一个定义在有限域 F 上的 v 元多项式 g(x_1, x_2, …, x_v)，以及一个声称的求和值 H，验证者希望确认：
H = Σ_{b_1 ∈ {0,1}} Σ_{b_2 ∈ {0,1}} … Σ_{b_v ∈ {0,1}} g(b_1, b_2, …, b_v)
即 g 在布尔超立方体 {0, 1}^v 上所有 2^v 个点处取值的总和确实等于 H。直接验证需要计算 2^v 次多项式求值，当 v 较大时这是不可承受的。Sumcheck 协议允许验证者仅通过 v 轮交互和一次对 g 的点求值（通常由预言机提供）即可完成验证，通信复杂度为 O(v · d)，其中 d 是多项式的总度数。
协议流程
协议的 v 轮交互按如下方式进行：
第 1 轮：证明者发送一元多项式 g_1(x_1) = Σ_{b_2,…,b_v ∈ {0,1}} g(x_1, b_2, …, b_v)。验证者首先检查 g_1(0) + g_1(1) = H，然后随机选取 r_1 ∈ F 发送给证明者。
第 2 轮：证明者发送 g_2(x_2) = Σ_{b_3,…,b_v ∈ {0,1}} g(r_1, x_2, b_3, …, b_v)。验证者检查 g_2(0) + g_2(1) = g_1(r_1)，然后随机选取 r_2 ∈ F 发送给证明者。
第 i 轮（一般情况）：证明者发送 g_i(x_i) = Σ_{b_{i+1},…,b_v ∈ {0,1}} g(r_1, …, r_{i-1}, x_i, b_{i+1}, …, b_v)。验证者检查 g_i(0) + g_i(1) = g_{i-1}(r_{i-1})，然后随机选取 r_i ∈ F。
第 v 轮（最后一轮）：证明者发送 g_v(x_v)。验证者检查 g_v(0) + g_v(1) = g_{v-1}(r_{v-1})，随机选取 r_v ∈ F，然后验证 g_v(r_v) = g(r_1, r_2, …, r_v)。这最后一步需要验证者能够对 g 进行一次点求值——在很多应用中，这可以通过预言机访问或额外的子协议来完成。
可靠性分析
Sumcheck 协议的可靠性基于 Schwartz-Zippel 引理：一个非零的 v 元 d 次多项式在有限域 F 中随机取值为零的概率至多为 d / |F|。在每一轮中，如果证明者发送了错误的多项式，那么在验证者选取的随机点处恰好”骗过”验证者的概率至多为 d / |F|。经过 v 轮交互，通过联合界（Union Bound），总的可靠性误差至多为 v · d / |F|。当有限域足够大时（例如 |F| ≈ 2^128），这个误差可以忽略不计。
作为构件的普遍性
Sumcheck 协议的重要性远不止于直接应用。它是大量高层协议的核心子程序，包括 GKR 协议、Spartan、HyperPlonk、Lasso 等。正如 Justin Thaler 所言，“Sumcheck 协议之于可验证计算，犹如快速傅里叶变换之于信号处理”——它是一个看似简单却威力巨大的算法基元，一旦掌握便可触类旁通。
Python 实现
以下给出一个简化的 Sumcheck 协议实现，用于验证多线性多项式（Multilinear Polynomial）在布尔超立方体上的求和。多线性多项式的每个变量的次数至多为 1，这是可验证计算中最常用的多项式类型。
import random
from typing import List, Callable
# 有限域模数（选取一个大素数）
PRIME = 2**61 - 1
def mod(x: int) -> int:
return x % PRIME
def multilinear_eval(evals: List[int], point: List[int]) -> int:
"""
给定多线性多项式在布尔超立方体上的 2^v 个取值 evals，
以及一个求值点 point = (r_1, ..., r_v)，
通过多线性扩展（MLE）计算多项式在该点的值。
"""
n = len(evals)
v = len(point)
assert n == (1 << v), "evals 的长度必须为 2^v"
# 逐变量折叠：将 evals 的长度从 2^v 逐步缩减至 1
table = [mod(e) for e in evals]
for i in range(v):
r = point[i]
half = len(table) // 2
new_table = []
for j in range(half):
# 线性插值：table[j] * (1 - r) + table[j + half] * r
val = mod(table[j] * mod(1 - r) + table[j + half] * r)
new_table.append(mod(val))
table = new_table
return table[0]
def sumcheck_prove(evals: List[int], v: int) -> tuple:
"""
Sumcheck 证明者：对多线性多项式在 {0,1}^v 上的求和生成证明。
返回 (claimed_sum, rounds, challenges)，其中 rounds 是每轮的一元多项式
（以 [g_i(0), g_i(1)] 表示），challenges 是验证者的随机挑战。
"""
claimed_sum = mod(sum(evals))
table = [mod(e) for e in evals]
rounds = []
challenges = []
for i in range(v):
half = len(table) // 2
# 计算 g_i(0) 和 g_i(1)
s0, s1 = 0, 0
for j in range(half):
s0 = mod(s0 + table[j])
s1 = mod(s1 + table[j + half])
rounds.append((mod(s0), mod(s1)))
# 验证者发送随机挑战
r = random.randint(0, PRIME - 1)
challenges.append(r)
# 用挑战值折叠表：将当前维度固定为 r
new_table = []
for j in range(half):
val = mod(table[j] * mod(1 - r) + table[j + half] * r)
new_table.append(mod(val))
table = new_table
# 最终值：g(r_1, ..., r_v)
final_eval = table[0]
return claimed_sum, rounds, challenges, final_eval
def sumcheck_verify(claimed_sum: int, rounds: list, challenges: list,
final_eval: int, oracle_eval: int) -> bool:
"""
Sumcheck 验证者：检查证明的正确性。
oracle_eval 是由预言机提供的 g(r_1, ..., r_v) 的值。
"""
v = len(rounds)
current_sum = claimed_sum
for i in range(v):
s0, s1 = rounds[i]
# 检查 g_i(0) + g_i(1) = 前一轮的求值
if mod(s0 + s1) != mod(current_sum):
print(f"第 {i+1} 轮求和检查失败")
return False
# 用本轮挑战计算 g_i(r_i) = s0 * (1 - r_i) + s1 * r_i
r = challenges[i]
current_sum = mod(s0 * mod(1 - r) + s1 * r)
# 最终检查：g_v(r_v) 是否等于预言机提供的 g(r_1, ..., r_v)
if mod(current_sum) != mod(oracle_eval):
print("最终求值检查失败")
return False
return True
# 演示
if __name__ == "__main__":
v = 4 # 变量数
n = 1 << v # 2^v = 16 个取值
# 随机生成多线性多项式在布尔超立方体上的取值
evals = [random.randint(0, PRIME - 1) for _ in range(n)]
claimed_sum, rounds, challenges, final_eval = sumcheck_prove(evals, v)
# 验证者独立计算预言机求值（实际中由可信预言机提供）
oracle_eval = multilinear_eval(evals, challenges)
result = sumcheck_verify(claimed_sum, rounds, challenges,
final_eval, oracle_eval)
print(f"变量数: {v}, 求值点数: {n}")
print(f"声称的求和: {claimed_sum}")
print(f"验证结果: {'通过' if result else '失败'}")这段代码虽然简化了许多工程细节（例如使用了 Python 内置整数而非高效的有限域运算库，且将证明者和验证者放在同一进程中模拟交互），但它完整地展示了 Sumcheck 协议的核心逻辑：逐轮缩减求和维度、验证者通过随机挑战逼迫证明者保持一致、最终通过一次点求值锚定整个验证。
四、GKR 协议
分层算术电路
GKR 协议（以 Goldwasser、Kalai 和 Rothblum 三位作者的姓氏首字母命名）是将 Sumcheck 协议应用于通用可验证计算的里程碑性工作。其核心对象是分层算术电路（Layered Arithmetic Circuit）——一种结构化的计算模型，其中每一层的门（Gate）仅接受上一层的输出作为输入。
具体而言，设电路有 d 层，从输出层（第 0 层）到输入层（第 d 层）。第 i 层有 S_i 个门，每个门执行加法或乘法运算。电路的”连线结构”（Wiring）由两个函数 add_i 和 mult_i 描述，它们指定第 i 层中哪些门对与来自第 i+1 层的哪些门对执行加法或乘法操作。
协议思路
GKR 协议的核心思想是将”验证整个电路的计算正确性”这一全局问题，通过逐层归约（Layer-by-Layer Reduction）转化为一系列 Sumcheck 子问题。协议从输出层开始：验证者持有电路的声称输出，它可以被表示为第 0 层的多线性扩展（Multilinear Extension，MLE）在某个随机点上的值。然后，通过一次 Sumcheck 协议的调用，这个声明被归约为对第 1 层 MLE 在某个（不同的）随机点上的值的声明。以此类推，逐层向下归约，直至到达输入层。由于验证者可以直接访问电路的输入，它可以自行计算输入层 MLE 在最终随机点上的值，从而完成整个验证。
更精确地说，令 W_i 表示第 i 层所有门输出值的多线性扩展。GKR 协议的每一轮建立如下关系：
W_i(z) = Σ_{(p,q) ∈ {0,1}^{2s}} [add_i(z, p, q) · (W_{i+1}(p) + W_{i+1}(q)) + mult_i(z, p, q) · W_{i+1}(p) · W_{i+1}(q)]
其中 z 是当前层的随机挑战点，p 和 q 是下一层的两个输入门的索引。这个求和表达式的形式恰好适合 Sumcheck 协议来处理。每一层的 Sumcheck 调用将对 W_i(z) 的声明转化为对 W_{i+1} 在一个或两个点上的声明。
复杂度分析
GKR 协议的关键优势在于验证者的效率。对于一个具有 d 层、每层 S 个门的电路，验证者的运行时间为 O(d · S · log S)——注意这与电路的总门数 O(d · S) 几乎是线性的，但关键在于验证者的计算主要是在小域上的操作（Sumcheck 交互），而非执行电路本身的运算。在许多应用中，电路是高度结构化的（例如重复结构），验证者的实际开销可以进一步降低。
证明者的运行时间则为 O(d · S · log S)，即在电路规模的拟线性范围内。虽然这比直接执行电路要慢一个 log 因子，但在实际系统中，通过精心的工程优化（例如并行化、预计算连线信息等），这一开销是完全可控的。
从 GKR 到现代系统
GKR 协议的原始版本要求电路具有严格的分层结构，这在表达通用计算时可能引入额外的开销。后续工作（如 Thaler 的线性时间 GKR、Xie 等人的 Libra 协议）通过各种技术改进，放宽了对电路结构的限制并进一步优化了性能。Virgo 和 Hyrax 等系统在 GKR 的基础上添加了多项式承诺（Polynomial Commitment），使之成为完整的零知识证明系统。可以说，GKR 协议开辟了一条基于 Sumcheck 的可验证计算路线，与基于 QAP/R1CS 的”SNARK 路线”形成了互补的技术格局。
五、从 IP 到简洁论证
信息论安全与计算安全
交互式证明系统的可靠性是信息论意义上的（Information-Theoretic）：即使证明者拥有无限的计算能力，也无法欺骗验证者（除以可忽略的概率外）。这种强安全性固然令人满意，但它对效率施加了严格的下界——验证者至少需要读取整个输入，否则证明者可以在未被读取的位置作弊。
简洁非交互论证（Succinct Non-interactive ARGument，SNARG）放松了安全性要求：它只对计算上有界的证明者保证可靠性。作为交换，SNARG 可以实现极短的证明长度（通常为 O(1) 或 O(log n)）和极快的验证时间（亚线性于输入大小）。当进一步要求证明具有知识性（即证明者不仅证明命题为真，还”知道”一个使命题成立的见证），便得到了简洁非交互知识论证（SNARK）。
多项式 IOP 范式
现代 SNARK 的构造通常遵循一个两阶段范式。第一阶段是设计一个信息论安全的多项式交互式预言机证明（Polynomial IOP，PIOP）。在 PIOP 中，证明者向验证者发送的不是具体的多项式系数，而是对多项式的”预言机承诺”——验证者可以在任意点查询这些多项式的值。常见的 PIOP 包括 Plonk、Marlin、Spartan 和 HyperPlonk。
第二阶段是用具体的多项式承诺方案（Polynomial Commitment Scheme，PCS）来”编译”（Compile）PIOP。多项式承诺方案允许证明者对一个多项式进行承诺（生成一个简短的承诺值），随后可以在任意点打开承诺并证明求值的正确性。常见的 PCS 包括 KZG 承诺（基于双线性配对和可信设置）、FRI（基于哈希函数，无可信设置）、IPA（基于离散对数假设）和 Brakedown（基于线性编码）。
将 PIOP 与 PCS 组合后，再通过 Fiat-Shamir 变换去除交互性，便得到一个完整的非交互式 SNARK。不同的 PIOP 和 PCS 组合产生不同的系统，它们在证明大小、验证时间、证明者时间、安全假设和是否需要可信设置等方面各有取舍。例如：
- Groth16 = R1CS + QAP + KZG 配对，证明最短（约 192 字节），但需要每个电路独立的可信设置。
- Plonk = Plonk PIOP + KZG，支持通用可信设置（Universal Trusted Setup），灵活性更高。
- STARK = AIR + FRI，完全透明（无可信设置），但证明较大（数十到数百 KB）。
- Spartan + HyperKZG 或 Brakedown，基于 Sumcheck 的路线，证明者效率较高。
算术化：从程序到约束
将通用计算转化为 SNARK 可处理的形式，需要经过算术化（Arithmetization）的过程。最经典的中间表示是 R1CS（Rank-1 Constraint System），它将计算表示为一组形如 (A · z) ⊙ (B · z) = (C · z) 的约束，其中 A、B、C 是稀疏矩阵，z 是包含输入、输出和中间变量的向量，⊙ 表示逐元素乘法。近年来，Plonkish 算术化和 AIR（Algebraic Intermediate Representation）也获得了广泛采用。Plonkish 允许自定义门（Custom Gate）和查找表（Lookup Table），在表达特定运算（如位操作、范围检查）时比 R1CS 更为高效。
六、增量可验证计算
IVC 的概念
增量可验证计算（Incrementally Verifiable Computation，IVC）处理的是一类特殊但极其重要的计算模式：反复迭代应用同一个函数 F。即给定初始状态 z_0，依次计算 z_1 = F(z_0)，z_2 = F(z_1)，…，z_n = F(z_{n-1})。IVC 要求在每一步都能产生一个证明 π_i，使得验证者可以高效地确认”从 z_0 出发，经过 i 步迭代确实到达了 z_i”。这个证明的大小和验证时间应当与步数 i 无关。
IVC 的经典应用场景包括：区块链的状态转移（每个区块是一次迭代）、长时间运行的科学计算（每个时间步是一次迭代）以及虚拟机的逐步执行（每条指令是一次迭代）。
递归证明组合
实现 IVC 最直观的方法是递归证明组合（Recursive Proof Composition）。在第 i 步中，证明者不仅执行 F(z_{i-1}) 得到 z_i，还在”电路内部”验证上一步的证明 π_{i-1}。即第 i 步的电路包含两部分：一是计算 F，二是验证 SNARK 证明。这样，π_i 不仅证明了”F(z_{i-1}) = z_i”，还隐含地证明了”π_{i-1} 是有效的”，从而递归地包含了从 z_0 到 z_i 的整个计算历史。
递归证明组合的难点在于”电路中验证 SNARK”的开销。SNARK 验证通常涉及椭圆曲线配对或哈希链计算，将这些操作编码为算术电路会引入巨大的开销。为此，研究者发展了多种优化技术：使用”友好的”椭圆曲线对（Cycle of Curves，如 Pasta 曲线）来降低递归的非本地域运算开销；使用累加方案（Accumulation Scheme）来推迟部分验证步骤。
Nova 折叠方案
Nova 是 Kothapalli、Setty 和 Tzialla 于 2022 年提出的折叠方案（Folding Scheme），它以一种全新的方式实现了 IVC。Nova 的核心创新在于：它不在每一步生成和验证完整的 SNARK 证明，而是将两个 R1CS 实例”折叠”（Fold）为一个等价的松弛 R1CS（Relaxed R1CS）实例。折叠操作本身非常轻量——只需少量的椭圆曲线标量乘法和哈希运算，远比在电路中验证 SNARK 要高效得多。
具体而言，Nova 在每一步维护一个”运行实例”（Running Instance）U_i 和对应的”运行见证”（Running Witness）W_i。当执行第 i+1 步时，先计算 F(z_i) = z_{i+1}，生成一个新的 R1CS 实例 u_{i+1}。然后，通过一轮非交互式折叠协议，将 U_i 和 u_{i+1} 折叠为新的运行实例 U_{i+1}。在所有迭代完成后，才需要对最终的运行实例 U_n 执行一次完整的 SNARK 证明。这种”延迟证明”的策略大幅降低了每一步的计算开销。
SuperNova 与 Sangria
SuperNova 是 Nova 的扩展，它允许在 IVC 的每一步中选择不同的函数 F_j（从预定义的函数集合 {F_1, …, F_k} 中选取）。这使得 IVC 不再局限于重复相同的计算，而是可以模拟更一般的程序执行——每条指令对应集合中的一个函数。SuperNova 的这一灵活性对于构建 zkVM 至关重要。
Sangria 则将折叠方案从 R1CS 推广到 Plonkish 约束系统，从而可以利用自定义门和查找表带来的效率优势。类似的推广还有 HyperNova，它将折叠方案与 Sumcheck 协议结合，处理更高阶的约束（CCS，Customizable Constraint System）。
证明携带数据
证明携带数据（Proof-Carrying Data，PCD）是 IVC 的推广形式。在 IVC 中，计算的拓扑结构是线性链；而在 PCD 中，计算可以形成任意的有向无环图（DAG）。每个节点不仅接收前驱节点的输出和证明，还可以将自己的计算结果和新的证明传递给后继节点。PCD 在分布式计算和区块链分片等场景中具有重要的应用价值——不同的分片可以独立产生各自的状态转移证明，最终在主链上被高效地聚合和验证。
七、zkVM 架构
为什么需要 zkVM
前述的 SNARK 系统通常要求开发者将待验证的计算直接编写为算术电路或约束系统，这对于复杂的程序来说是极其繁琐且容易出错的。零知识虚拟机（Zero-Knowledge Virtual Machine，zkVM）的目标是弥合这一鸿沟：开发者只需用常规编程语言（如 Rust、C 或 Solidity）编写程序，zkVM 负责将程序的执行轨迹（Execution Trace）自动转化为可验证的约束，并生成相应的正确性证明。
从概念上看，zkVM 的证明目标可以表述为：“存在一条合法的执行轨迹，使得给定程序在给定输入上的执行产生了给定的输出。”验证者只需检查证明即可确信这一点，而无需重新执行程序。
指令集架构的选择
zkVM 的设计首先面临的核心决策是指令集架构（Instruction Set Architecture，ISA）的选择。不同的 ISA 在”对证明友好”和”对开发者友好”之间存在不同的权衡。
RISC-V 是当前最受欢迎的选择之一。RISC Zero 和 SP1（Succinct Processor 1）都基于 RISC-V 的 RV32IM 子集（32 位整数运算加乘法扩展）。RISC-V 的优势在于其生态系统的成熟度——Rust、C/C++ 等语言都可以编译到 RISC-V 目标，开发者几乎无需修改现有代码即可在 zkVM 中运行。其相对简洁的指令集（约 47 条基本指令）也使得算术化的工作量可控。
Cairo VM 是 StarkWare 为 STARK 证明系统专门设计的虚拟机。Cairo 的指令集从一开始就以”证明友好”为首要目标：它的内存模型是只写一次的（Write-Once Memory），这消除了传统内存模型中读写一致性验证的高昂开销。Cairo 有自己的高级语言 Cairo Lang，开发者需要学习新的编程范式。
Valida 是一种为 zkVM 定制的极简 ISA。它的设计哲学是最小化每条指令在算术化后的约束数量，即使这意味着用更多的指令来完成同一个任务。Valida 的指令集非常精简，大约只有 30 多条指令，每条指令的约束行数非常少，这有助于减小证明系统的总体开销。
内存模型
内存模型是 zkVM 设计中另一个关键挑战。传统的冯·诺依曼架构允许对同一内存地址进行任意次读写，而证明系统需要保证每次内存读取返回的值确实是最后一次写入的值。这种读写一致性（Memory Consistency）的验证通常比纯粹的算术运算昂贵得多。
主流的解决方案是时间戳排序（Timestamp-based Sorting）：将所有内存访问记录按地址排序，然后对相邻的访问对施加约束。具体而言，对于同一地址的连续两次访问 (addr, val_i, t_i) 和 (addr, val_j, t_j)（其中 t_j > t_i），如果第二次是读操作，则 val_j 必须等于 val_i；如果是写操作，则可以是任意新值。这一方法可以通过排列论证（Permutation Argument）高效实现。
另一种方案是 Merkle 树（Merkle Tree）方法：将整个内存表示为一棵 Merkle 树，每次读写操作都附带一条 Merkle 路径证明。这种方法概念上更清晰，但由于每次内存访问都需要计算哈希，开销相对较大。
预编译与加速
为了提升对常用密码学操作的证明效率，现代 zkVM 广泛采用预编译（Precompile）机制。预编译是为特定运算（如 SHA-256 哈希、椭圆曲线标量乘法、Keccak 哈希、大整数运算等）提供专门优化的约束电路，取代通用 ISA 指令序列的逐条证明。使用预编译可以将特定操作的证明开销降低一到两个数量级。
RISC Zero 和 SP1 都支持用户自定义预编译，使得开发者可以针对自己应用中的热点操作编写定制化的约束电路，从而在通用性和性能之间取得更好的平衡。
八、可验证计算的实际应用
zkRollup
zkRollup 是可验证计算当前最大规模的实际部署。在 zkRollup 架构中，排序器（Sequencer）在链下收集并执行用户交易，然后将压缩的交易数据和一个有效性证明（Validity Proof）提交到以太坊主链。主链上的验证合约只需检查证明的有效性即可接受新的状态根（State Root）。
主要的 zkRollup 项目包括 zkSync Era（基于自研的 Boojum 证明系统和 EraVM）、StarkNet（基于 Cairo VM 和 STARK 证明）、Polygon zkEVM（基于定制的 zkEVM 和 Plonky2/Plonky3 证明系统）以及 Scroll（基于与以太坊 EVM 高度兼容的 zkEVM）。这些项目在 EVM 兼容性、证明生成速度、去中心化程度等方面各有不同的设计选择。
zkRollup 的一个核心技术挑战是证明生成的延迟（Latency）。用户提交交易后，需要等待证明生成完毕并提交到主链才能获得最终确认。当前的证明生成时间从数分钟到数十分钟不等，这主要取决于批次大小（Batch Size）、电路复杂度和可用的硬件加速资源。降低证明延迟是 zkRollup 领域最活跃的研究方向之一。
可验证的机器学习推理
随着大型语言模型（Large Language Model，LLM）和其他深度学习模型越来越多地以 API 服务的形式被部署，一个自然的问题浮现出来：用户如何验证服务商确实运行了声称的模型，而不是使用了一个更廉价但质量更低的替代品？可验证的机器学习推理（Verifiable ML Inference）试图回答这一问题。
当前的方法大致分为两条技术路线。第一条是将整个推理过程编码为算术电路并生成 SNARK 证明，这在理论上最为彻底，但实际开销极大——即使是中等规模的神经网络，其算术化后的约束数量也可达数十亿甚至更多。EZKL 和 zkML 等项目正在沿着这一方向探索，但目前仅能处理较小规模的模型。第二条路线是乐观验证（Optimistic Verification），结合欺诈证明（Fraud Proof）和经济激励机制，在大多数情况下无需生成证明，仅在发生争议时才触发验证流程。
可验证的数据库查询
在数据库外包场景中，客户端将数据存储在远程服务器上并发出查询请求。可验证的数据库查询（Verifiable Database Query）确保服务器返回的查询结果是对真实数据集执行指定查询后的正确结果。典型的技术方案包括：基于认证数据结构（Authenticated Data Structure）的方法，如 Merkle B+ 树；以及基于 SNARK 的方法，为 SQL 查询的执行生成正确性证明。后者的灵活性更高，但效率挑战也更大。
Space and Time 等项目正在构建基于 SNARK 的可验证数据库层，目标是让智能合约能够安全地查询链下数据。这一方向将可验证计算与数据可用性（Data Availability）问题紧密联系在一起。
可验证构建
软件供应链安全是近年来备受关注的议题。可验证构建（Verifiable Build）的目标是证明一个二进制文件确实是由特定版本的源代码通过特定的编译器和构建配置编译而来。传统的再现性构建（Reproducible Build）要求任何人都能从源代码出发得到完全相同的二进制文件，但这在实践中往往受到环境差异（操作系统版本、库版本、文件系统时间戳等）的干扰。
基于 zkVM 的可验证构建提供了一种更强的保证：将编译过程在 zkVM 中执行，生成一个证明”在 zkVM 内部运行特定编译器对特定源代码进行编译，产生了特定的二进制输出”。任何人只需验证证明即可确信构建的正确性，而无需复现构建环境。虽然当前 zkVM 的性能尚不足以高效处理大型项目的完整编译流程，但随着证明系统的持续优化，这一愿景正在逐步接近现实。
九、性能与开放问题
证明者开销
可验证计算面临的最大实际挑战是证明者的计算开销。当前最先进的系统中，证明生成的时间通常是原始计算时间的 10^4 到 10^6 倍。例如，一个在普通 CPU 上执行仅需 1 秒的计算，其证明生成可能需要数小时。这一巨大的”证明开销”（Proving Overhead）严重限制了可验证计算的适用范围。
证明开销的来源是多方面的：算术化引入的膨胀（一条 CPU 指令可能对应数百个有限域约束）、多项式承诺中的大规模多标量乘法（Multi-Scalar Multiplication，MSM）和快速数论变换（Number Theoretic Transform，NTT）、以及内存一致性检查的额外成本。
硬件加速
降低证明开销的一个重要方向是硬件加速。GPU 天然适合证明生成中的大规模并行运算——NTT 和 MSM 都具有高度的数据并行性。Icicle、cuZK 等开源库已经提供了基于 CUDA 的高效实现，可以将证明生成速度提升一到两个数量级。
更进一步，FPGA（现场可编程门阵列）和 ASIC（专用集成电路）正在被探索用于证明加速。FPGA 的优势在于灵活性——可以针对特定的证明系统定制数据通路，同时避免 GPU 的通用计算开销。ASIC 则可以在固定设计的基础上实现最极致的性能和能效，但开发周期长、成本高，且一旦证明系统更新便面临过时的风险。Cysic、Ingonyama、Ulvetanna 等公司正在积极推进证明硬件的研发。
理论下界
从理论角度看，一个自然的问题是：证明者开销的下界是多少？是否存在一个 SNARK 方案，使得证明者的时间与原始计算时间仅相差常数因子？目前已知的最佳结果是证明者时间为 O(C · polylog(C))，其中 C 是电路大小——即拟线性开销。能否进一步降至严格的 O(C) 仍然是一个开放问题。此外，证明大小与验证时间之间是否存在不可逾越的权衡（Trade-off）也尚未被完全理解。
后量子安全性
量子计算对可验证计算领域同样构成威胁。基于椭圆曲线配对的 SNARK（如 Groth16、Plonk+KZG）和基于离散对数假设的方案（如 Bulletproofs）在量子计算机面前都是不安全的。基于哈希函数的 STARK 和 FRI 方案天然具有后量子安全性（Post-Quantum Security），因为它们不依赖任何数论困难假设。基于格的多项式承诺方案也正在被积极研究，有望在保持后量子安全性的同时提供比 FRI 更短的证明。
形式化验证与审计
随着可验证计算系统越来越多地被部署在管理数十亿美元资产的区块链上，证明系统本身的正确性变得至关重要。一个有缺陷的证明系统可能允许攻击者凭空铸造代币或窃取资金。对证明系统进行形式化验证（Formal Verification）——即用数学方法严格证明其实现符合规范——是一个日益受到重视但极具挑战性的方向。目前，大多数系统仍依赖代码审计和安全赏金计划，形式化验证的覆盖范围还非常有限。
证明聚合与共享排序
在区块链生态系统中，多个 Layer 2 网络各自独立生成证明并提交到主链。证明聚合（Proof Aggregation）技术可以将多个独立的证明合并为一个单一的聚合证明，从而共摊链上验证成本。这与共享排序（Shared Sequencing）的趋势相结合，可能催生一种新的架构：多个 Layer 2 共享一个排序层和一个证明聚合层，在保持各自独立性的同时实现更高的经济效率。
可验证计算正站在理论与工程的交汇点上。一方面，Sumcheck 协议、GKR 协议和折叠方案等理论工具不断被改进和推广；另一方面，zkVM、硬件加速和证明聚合等工程实践正在将这些理论成果转化为可大规模部署的基础设施。从云计算中的计算外包到区块链上的去中心化验证，从可信人工智能推理到软件供应链安全，可验证计算的应用边界正在以前所未有的速度扩展。正如零知识证明的先驱 Shafi Goldwasser 所言，我们正在进入一个”计算可以被验证但不必被信任”的时代。
十、从程序到链上验证：可验证计算全流水线
为帮助读者建立对可验证计算完整工作流的直觉，以下展示从高级语言程序到链上常数时间验证的端到端流水线。
┌─────────────────────────────────────────────────────────────────────┐
│ 可验证计算编译与证明流水线 │
└─────────────────────────────────────────────────────────────────────┘
[1. 高级语言程序]
│ 开发者使用 Rust / Go / Solidity / Noir / Circom 等语言编写业务逻辑
│
▼
[2. 算术电路（Arithmetic Circuit）]
│ 编译器将程序转化为由加法门和乘法门组成的算术电路
│ 工具：Circom compiler、Noir compiler、SP1/RISC Zero（zkVM 自动编译）
│
▼
[3. 约束系统（Constraint System）]
│ ├── R1CS（Rank-1 Constraint System）——Groth16、Marlin 使用
│ ├── Plonkish（含自定义门和查找表）——Halo2、Plonk 使用
│ └── AIR（Algebraic Intermediate Representation）——STARK 使用
│
▼
[4. 多项式承诺（Polynomial Commitment）]
│ 将约束系统编码为多项式，并生成密码学承诺
│ ├── KZG 承诺——需要可信设置，证明短（O(1)），验证快
│ ├── FRI 承诺——无需可信设置，后量子安全，证明较大（O(log^2 n)）
│ └── IPA 承诺——无需可信设置，证明中等，验证稍慢
│
▼
[5. 证明生成（Proof Generation）]
│ 证明者执行计算并生成简洁证明
│ 计算开销：通常为直接执行的 1000x-1000000x（取决于方案和电路复杂度）
│ 可通过 GPU/FPGA 并行加速
│
▼
[6. 链上验证（On-chain Verification）]
验证者在常数时间内验证证明的正确性
├── Groth16：3 次配对运算，gas 约 200K-300K（以太坊）
├── Plonk/KZG：略高于 Groth16，但支持通用可信设置
└── STARK/FRI：验证稍慢但无可信设置依赖，后量子安全关键权衡点：
| 阶段 | 核心权衡 |
|---|---|
| 算术电路编译 | 电路规模 vs 开发者体验——zkVM 自动编译但电路较大，手写 Circom 电路小但开发成本高 |
| 约束系统选择 | R1CS 生态成熟但灵活性受限；Plonkish 支持自定义门和查找表，适合复杂逻辑 |
| 多项式承诺 | KZG 证明最短但需可信设置；FRI 无需信任但证明较大；IPA 折中但验证较慢 |
| 证明生成 | 证明时间 vs 证明大小——SNARK 证明小但生成慢，STARK 生成快但证明大 |
笔者认为，可验证计算的技术栈正在演变为”无信任计算”（Trustless Computing）领域的编译器工具链——其角色类似于传统软件工程中从高级语言到机器码的编译链。在传统编译器中，开发者用 C/Rust 编写程序，编译器负责将其转化为高效的机器指令；在可验证计算中，开发者用高级语言编写业务逻辑，证明系统负责将其转化为可验证的密码学证明。这一类比并非修辞——它正在成为工程现实。SP1、RISC Zero 等 zkVM 项目允许开发者直接用 Rust 编写程序并自动生成零知识证明，开发者甚至不需要理解底层的算术电路和多项式承诺。正如 GCC 和 LLVM 让程序员无需关心寄存器分配和指令调度一样，成熟的可验证计算编译器将让开发者无需关心约束系统和证明方案的选择。从工程实践来看，这一趋势意味着可验证计算的采纳瓶颈正在从”密码学知识门槛”转向”编译器优化效率”——与半个世纪前编译器技术的发展轨迹如出一辙。
密码学百科系列 · 第 63 篇