💻 computer science

zkFuzz: Foundation and Framework for Effective Fuzzing of Zero-Knowledge Circuits

本文介绍了 zkFuzz，这是一种基于理论迹约束一致性测试（TCCT）的新型变异模糊测试框架，该框架通过克服现有静态分析和形式化分析工具的局限性，有效检测零知识电路中的约束不足和约束过度漏洞。

原作者： Hideaki Takahashi, Jihwan Kim, Suman Jana, Junfeng Yang

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Hideaki Takahashi, Jihwan Kim, Suman Jana, Junfeng Yang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在建造一个魔法金库，它能证明你知道一个秘密密码，却从不真正展示该密码。这就是“零知识（ZK）电路”在数字世界中所做的事情。它们是匿名加密货币和安全投票系统等隐私保护技术的安保人员。

然而，建造这些金库极其棘手。如果你在蓝图上犯了一个微小的错误，金库可能会：

让任何人进入（即使他们不知道密码）。
将真正的拥有者拒之门外（即使他们拥有正确的密码）。

这篇论文介绍了一种名为ZKFUZZ的新工具，用于在恶意行为者发现这些错误之前将其找出。以下是其工作原理的简单解释：

问题：“蓝图”与“现实”之间的脱节

在这些系统中，开发人员编写一个程序，同时执行两件事：

计算：用于推导秘密的实际数学运算（例如在地图上计算路线）。
约束：用于证明数学运算正确执行的规则（例如验证路线存在的检查清单）。

问题在于，这两部分经常不同步。

约束不足：规则过于宽松。黑客可以诱骗系统接受一条虚假路线。
约束过度：规则过于严格。系统因为一条微小且不必要的规则而拒绝了一条完全有效的路线。

现有的用于发现这些错误的工具就像糟糕的拼写检查器。它们基于模式进行猜测，并对实际上没问题的事物大喊“错误！”（误报），或者完全遗漏深层、复杂的错误。

解决方案：ZKFUZZ（“变异模糊测试器”）

作者创建了一个名为ZKFUZZ的新框架。ZKFUZZ 不仅仅读取代码，它更像一位顽皮的测试工程师，故意试图破坏系统。

以下是类比：
想象你有一份食谱（计算）和一次品尝测试（约束）。

旧工具：查看食谱并说：“这看起来很可疑，因为它用了盐。”（它们基于规则进行猜测）。
ZKFUZZ：实际烹饪这道菜，但随后它变异了食谱。它将“糖”换成“盐”，或者改变烹饪时间。然后，它将这道变异后的菜肴喂给品尝测试。
- 如果品尝测试对一道本应难吃的菜肴（因为食谱被修改了）说“美味！”，ZKFUZZ 就知道规则太宽松（约束不足）。
- 如果品尝测试对一道本应美味的菜肴（因为原始食谱是正确的）说“难吃！”，ZKFUZZ 就知道规则太严格（约束过度）。

秘密武器：“适应度”与“定向”

在 ZK 电路中发现一个漏洞，就像在行星大小的干草堆里找一根针。涉及的数字如此巨大，以至于计算机无法尝试每一种可能性。

ZKFUZZ 使用遗传算法（类似于进化）：

变异：它创建成千上万个略有损坏的程序版本。
适应度评分：它对这些损坏的版本进行评级。如果一个损坏的版本接近通过测试（即使它失败了），它就会获得“高分”。这告诉系统：“你越来越接近了！”
定向：它不仅仅是随机猜测。它知道漏洞通常发生在“边缘情况”（例如当数字为零或极大时）。它专门尝试向系统输入这些棘手数字，以观察系统是否会崩溃。

结果：捕捉未被发现的漏洞

该团队在452 个实际项目中使用的真实世界电路上测试了 ZKFUZZ。

得分：它发现了85 个漏洞。
零日漏洞：其中 59 个是全新的、未知的漏洞（零日漏洞），此前无人知晓其存在。
影响：其中 39 个得到了开发人员的确认，14 个已被修复。这包括zkSync（一个加密货币平台）和passport-zk-circuits（数字身份系统）等主要项目中的漏洞。
无误报：与其他工具不同，ZKFUZZ 没有将任何非漏洞标记为漏洞。

为什么这很重要

该论文认为，之前的工具遗漏了问题的很大一部分。它们只寻找规则中的“随机性”。ZKFUZZ 引入了一种名为TCCT（轨迹 - 约束一致性测试）的新理论，该理论检查计算机实际采取的路径是否与其应遵循的规则相匹配。

这一新理论发现了当计算机“崩溃”或意外停止时发生的漏洞，而之前的工具完全忽略了这些情况。

一句话总结

ZKFUZZ 是一个智能的自动化“漏洞猎手”，它通过变异代码并向其输入棘手数据来破坏零知识电路。它发现了数十个其他工具遗漏的关键安全漏洞，证明了即使在隐私数学的复杂世界中，一点点受控的混乱也是发现真相的最佳方式。

技术摘要：ZKFUZZ：零知识电路有效模糊测试的基础与框架

1. 问题陈述

零知识（ZK）电路是隐私保护计算的基石，使得从匿名加密货币到可验证机器学习等应用能够生成简洁证明并进行高效验证。然而，由于通用计算逻辑与有限域多项式约束之间的不匹配，开发正确的 ZK 电路 notoriously 困难。

主要存在两类漏洞：

约束不足（Under-constrained）电路：约束过于宽松，允许恶意证明者为无效见证人生成有效证明（违反完备性）。
约束过度（Over-constrained）电路：约束过于严格，导致系统拒绝诚实证明者的有效见证人（违反可靠性）。

现有的检测方法面临显著局限：

静态分析：Circomspect 和 ZKAP 等工具往往误报率较高，且无法捕捉深层语义问题，特别是涉及中间计算或异常程序终止的问题。
形式化方法：依赖 SMT 求解器的工具（如 Picus、ConsCS）难以扩展到实际电路规模，且往往依赖不完整的漏洞定义，仅关注约束中的非确定性，而忽略了计算中止或中间值不匹配的情况。
定义缺口：此前对 ZK 漏洞的形式化定义不完整。它们通常忽略“异常终止”（即计算崩溃但约束仍被满足的情况），且未能涵盖包含中间值在内的完整执行轨迹集合。

2. 方法论

2.1 理论基础：轨迹 - 约束一致性测试（TCCT）

作者引入了TCCT，这是一种与语言无关的形式化框架，将 ZK 漏洞定义为以下两个集合之间的差异：

轨迹集 $T(P)$ ：见证人计算程序 $P$ 产生的所有可能执行轨迹（输入、中间值、输出）的集合。
约束满足集 $S(C)$ ：满足电路约束 $C$ 的所有元组（输入、中间值、输出）的集合。

TCCT 定义电路为约束良好，当且仅当：

无约束不足： $S(C)$ 在输入 - 输出对上的投影是 $T(P)$ 投影的子集。这确保了没有无效轨迹被接受。
无约束过度： $T(P)$ 是 $S(C)$ 的子集。这确保了所有有效轨迹（包括特定的中间值）都被接受。

该公式捕捉了由计算中止（ $P$ 失败但 $C$ 接受输入）和中间值不匹配引起的漏洞，这是此前定义所遗漏的。作者证明，判定约束不足或约束过度是 NP 完全的，而完整的 TCCT 判定是 co-NP 完全的。

2.2 系统设计：ZKFUZZ

ZKFUZZ 是一个动态分析框架，利用联合程序变异与输入生成方法来检测 TCCT 违规。与传统仅变异输入的模糊测试不同，ZKFUZZ 同时变异程序逻辑和输入。

核心工作流：

变异：系统生成原始计算程序（ $P$ ）的变异体（ $P'$ ）。变异包括移除断言、转换赋值（例如替换运算符或值）以及修改弱赋值。
执行：原始程序（ $P$ ）和变异体（ $P'$ ）均在采样输入（ $x$ ）上执行。
验证：
- 约束过度检测：如果 $P(x)$ 产生满足 $C$ 但实际无效的轨迹，则电路存在约束过度。
- 约束不足检测：如果 $P'(x)$ 产生具有不同输出（ $y' \neq y$ ）但仍满足 $C$ 的轨迹，则电路存在约束不足（因为变异逻辑在语义上不同，该输出本不应被接受）。
引导搜索：为了在巨大的大素数域搜索空间和无限变异可能性中导航，ZKFUZZ 采用遗传算法：
- 适应度函数：一种新颖的最小和适应度函数计算给定轨迹在所有约束上的约束误差之和。变异体根据采样输入上的最小误差总和进行评分。这与以往仅取最大值的方法不同，更适合联合变异。
- 目标选择器：系统利用静态分析引导变异和输入生成朝向高风险模式，例如：
  - 零除：生成分子和分母均为零的输入。
  - 哈希检查：强制输入满足哈希相等约束。
  - 偏态分布：将输入生成偏向边缘情况（0、1 以及接近域模数 $q$ 的值）。
  - 白名单：跳过已知安全模板（如 IsZero、Num2Bits），以专注于易错代码。

3. 主要贡献

TCCT 框架：一个统一、与语言无关的形式化模型，涵盖了先前的定义，并捕捉了 ZK 漏洞的完整空间，包括由异常终止和中间值不匹配引起的漏洞。
ZKFUZZ 系统：一个新颖的模糊测试框架，通过联合变异程序和输入来检测 TCCT 违规，利用最小和适应度函数和引导搜索启发式方法。
实证验证：在 452 个真实世界的 Circom 电路上进行评估，证明了其性能优于最先进工具。
Noir 原型：针对另一种 ZK 领域特定语言（DSL）Noir 的初步实现，展示了该框架在语言独立性方面的潜力。

4. 结果

作者在 452 个真实世界的 Circom 电路上评估了 ZKFUZZ，并将其与四种最先进工具（Circomspect、ZKAP、Picus 和 ConsCS）进行了比较。

漏洞检测：ZKFUZZ 识别出85 个独特漏洞，其中包括59 个此前未知的零日漏洞。其中，39 个得到开发者确认，14 个已修复。
对比：在各种电路规模下，ZKFUZZ 发现的漏洞数量比现有工具多30% 到 300%。
精度：ZKFUZZ 实现了100% 的精度（零误报），而 Circomspect 和 ZKAP 等静态分析器的误报率很高（精度范围从 0.06 到 0.75）。
速度：ZKFUZZ++（带目标选择器）在100 秒内识别出超过 90% 的漏洞，显著优于形式化方法和静态分析器。
影响：发现的漏洞包括 zk-regex 和 passport-zk-circuits 等项目中的关键约束不足漏洞，这些漏洞可能允许攻击者伪造证明或提取资金。

5. 意义与主张

本文主张，ZKFUZZ 通过解决先前漏洞定义的根本性不完整，代表了 ZK 电路安全领域的重大进步。通过将漏洞形式化为轨迹 - 约束不一致（TCCT），作者揭示了一大类漏洞（在其评估中占真实世界漏洞的近 50%），这些漏洞此前无法被仅关注约束非确定性的工具检测到。

该系统能够以零误报检测漏洞，使其成为开发者的实用工具，而开发者往往忽略来自高误报率静态分析器的警报。此外，在 Noir 电路中成功检测漏洞表明，TCCT 框架和 ZKFUZZ 架构不仅限于 Circom，还可以推广到其他编译为标准约束格式的 ZK 语言。

作者强调，他们的工作专注于由计算与约束不匹配（可靠性和完备性）引起的漏洞，明确排除了底层证明系统中的漏洞、纯逻辑错误（如未使用的输入）或协议层面的零知识泄露。