计算机科学家找到了证明谎言的方法
对基本证明技术的攻击揭示了区块链和其他数字加密方案的明显安全问题。
原文：https://www.quantamagazine.org/computer-scientists-figure-out-how-to-prove-lies-20250709/
作者：Erica Klarreich
译者：Kurt Pan
随机性是力量的源泉。从决定哪支球队接球的抛硬币，到保障在线互动安全的随机密钥，随机性让我们能够做出公平且不可预测的选择。
但在许多计算应用中，合适的随机性很难生成。因此，程序员通常依赖于一种叫做哈希函数的东西，它能对数据进行搅拌，并以看似随机的方式提取一小部分数据。几十年来，许多计算机科学家一直假设，在实际应用中，好的哈希函数的输出通常与真正的随机性难以区分——他们将这种假设称为随机预言模型。
波士顿大学的 Ran Canetti 表示：“如今很难找到一个密码学应用......其安全分析不采用这种方法的。”
如今，一篇新论文动摇了这一基本假设。它展示了一种欺骗商用证明系统来证明虚假陈述的方法，即使该系统在接受随机预言模型的情况下是可证明安全的。与此相关的证明系统对于记录密码货币交易的区块链至关重要，它们用于证明外部服务器执行的计算。
https://eprint.iacr.org/2025/118
以色列巴伊兰大学的Eylon Yogev表示：“很多资金都依赖于这些东西。” 对于区块链证明协议，“攻击者有巨大的动机去破坏系统的安全性。”
在这篇由以太坊基金会的 Dmitry Khovratovich、零知识证明技术公司 Succinct 和以色列海法理工学院的 Ron Rothblum 以及专注于区块链的初创公司 [alloc] init 的 Lev Soukhanov 共同撰写的新论文中，研究人员无论使用哪种哈希函数来生成证明系统所依赖的“随机性”，都能够证明谎言。
当Yogev听到团队的结果时，他说：“我感觉有人要把我脚下的地毯抽走了。” 他和其他人一直在努力弥补这些弱点。但“这个问题还远未得到解决，”他说。
更广泛地说，新的结果迫使人们重新审视随机预言模型。“现在是必须重新思考的时候了，”Canetti说。
数学搅拌机
从密码货币到云计算，许多不同的计算应用都涉及让互联网上的一群陌生人相信你正确地执行了计算。这篇新论文展示了如何劫持一种使人们能够验证此类计算的基本技术。这项名为Fiat-Shamir转换的技术不仅适用于区块链和云计算，还适用于许多其他密码应用，例如保护网络交易和加密短信的密钥交换。它无处不在，甚至变成了一个动词，例如“让我们Fiat-Shamir一下”。
Fiat-Shamir 转换适用于可以通过随机检查计算结果来验证计算结果的情况。例如，如果一位教授布置了 100 道作业，但不想对学生的所有作业都进行评分，她可以随机选择 10 道题进行评分。用计算机科学家的话来说，她正在对学生的作业进行 10 次“随机挑战”。如果这 10 道题的答案正确，教授就可以确信其他大多数答案也正确。（如果教授想确保学生每道题都答对了，而不是只答对了大部分题，那么可以修改此设置。）
这种特殊场景很可能发生在教授的办公桌上。但由于Fiat-Shamir转换是关于说服一群远方陌生人，我们不妨设想一下，学生不仅想向教授证明他作业的正确性，还想向满座的听众证明。
想象一下，学生首先将每个答案锁在一个单独的盒子里，然后“提交”作业。接下来，教授从帽子里抽出10个数字，确定10个随机挑战。学生解锁这10个盒子，教授对内容进行评分。由于学生在知道随机挑战是什么之前就锁定了答案，因此教授可以确信她正在评分的问题能够代表学生的整体作业。
但观众可能会质疑他们所见证的是否合法。据他们所知，学生可能贿赂了教授，让他只往帽子里放特定的数字，而不是从1到100的所有数字。又或许教授没有注意到锁着的盒子上的陷门，而学生背后有一个同伙，在匆忙解题后，在盒子被打开之前把答案偷偷塞进了正确的盒子里。
你可能会认为，要真正令人信服，每位观众都必须与学生进行互动。但计算机科学家已经找到了让学生使用哈希函数来满足观众需求的方法。
哈希函数就像一个数学搅拌机——它根据一组选定的操作将一堆数据搅拌均匀，然后输出一小部分。对于密码学而言，哈希函数有两个非常吸引人的特性。首先，它输出看似随机的乱码，与产生它的输入没有明显的关联。其次，哈希函数易于执行，但难以逆向。如果有人给你一个输出，你几乎不可能找到产生该输出的输入。
在家庭作业的例子中，学生可以用哈希函数（而不是实体钥匙）“锁住”盒子，以此向观众保证盒子没有陷门。为此，学生将他的100个答案逐一进行哈希运算，并将每个哈希值的结果贴在相应盒子的盖子上。计算机科学家将这些贴纸称为学生的“承诺”。现在，如果同伙事后试图更改盒子里的内容，修改后的内容将与承诺不符——观众可以轻松自行验证这一点。
1986 年，阿莫斯·菲亚特（Amos Fiat）和阿迪·沙米尔（Adi Shamir）提出了一种使用哈希函数的方法来解决听众的另一个担忧：学生可能贿赂教授选择某些盒子。在Fiat-Shamir 协议中，教授不是从帽子里抽数字，而是使用哈希函数生成随机挑战。她首先将学生的承诺扔回搅拌机，得到新的乱码。然后，她使用一些先前商定的公式将这些乱码转换成 1 到 100 之间的数字。这个数字决定了她首先打开哪个盒子。然后，她重复这个过程：她将承诺和第一个盒子的答案都扔进搅拌机，以选择打开第二个盒子，依此类推。
这种方法实现了非凡的效果：它消除了学生和教授（或任何观众）之间来回沟通的需要。学生可以使用哈希函数自行生成随机挑战。观众中的任何人都可以自行判断学生的操作是否正确。
通过将交互式证明转化为非交互式证明，Fiat-Shamir转换使计算机能够生成任何人都可以随时检查的证明，而无需与证明者交互。很快，它就得到了广泛的应用。但它是否安全呢？或者说攻击者能否以某种方式利用它来让人们相信一个虚假陈述呢？
证明谎言
1996 年，David Pointcheval 和 Jacques Stern 证明了 Fiat-Shamir 在随机预言模型中是安全的——前提是假设哈希函数是理想化的纯随机源。但真正的哈希函数并非真正随机。研究人员担心，聪明的攻击者可能会利用特定哈希函数的具体操作细节来破解 Fiat-Shamir 算法。
https://link.springer.com/chapter/10.1007/3-540-68339-9_33
21 世纪初，计算机科学家展示了如何做到这一点，他们设计了一些交互式证明协议，这些协议被设计成在接受 Fiat-Shamir 转换时就会失效。但“任何头脑正常的人都不会以这种方式设计协议，”Canetti说道。许多程序员认为，现实世界中的任何协议都不会受到这种攻击，因此他们继续将 Fiat-Shamir 转换融入到人们在互联网上交换信息的基础中。Canetti说，这是“一次信念飞跃”。
https://ieeexplore.ieee.org/document/959885 https://ieeexplore.ieee.org/document/1238185
一些计算机科学家对这种大胆的尝试持严重保留态度。Ron Rothblum 就是其中之一，他长期以来一直试图攻击某种现实世界的协议。去年十月的一天，他收到了一封来自区块链组织“以太坊基金会”的意外邮件，该组织运营着一种被广泛使用的密码货币——以太币。
Ron Rothblum 与 Dmitry Khovratovich 和 Lev Soukhanov 一起颠覆了有关基本证明技术的主流思想。
密码货币背后的区块链有一个令人遗憾但又不可避免的特点：它们运行速度极慢。为了处理来自金融交易的大量流量，区块链必须将大部分计算任务转移到外部计算机。它无法假设这些计算机是值得信赖的，因此要求它们提供Fiat-Shamir 证明，以证明其计算的有效性。如果有人能用Fiat-Shamir 证明来“证明”一个虚假陈述，例如“A 给 B 汇了一百万美元”，整个系统就会崩溃。
由于这些证明的重要性不言而喻，以太坊基金会决定测试其安全性，为此，基金会向任何能够使用流行的哈希函数 Poseidon 攻击 Fiat-Shamir 证明协议的人提供赏金。在宣布赏金之前，基金会邀请 Rothblum 审阅了声明草稿。
Rothblum的回应是，基金会的措辞过于宽泛。毕竟，密码学家几十年来都知道，无论使用哪种哈希函数，特意设置的证明协议都容易受到攻击。当他与以太坊的密码学家分享自己的想法时，他惊讶地发现他们对这项工作并不熟悉。Rothblum 开始与 Khovratovich 和 Soukhanov（当时在以太坊工作）合作，进行更深入的研究。
Soukhanov 的想法是针对 Fiat-Shamir 证明系统，该系统基于一种名为 GKR 协议的东西，由 Rothblum 的兄弟 Guy Rothblum （GKR 中的“R”）共同设计。GKR 协议用于证明计算机程序在给定只有证明者知道的秘密输入时会产生特定的输出。例如，如果你有一个家庭作业评分程序，学生可以使用该协议来证明以下语句：“我有一组家庭作业答案，当我将它们输入到评分程序中时，程序会输出‘正确’的结果。” 只要评分程序是你认可的，你就可以确信学生的作业是正确的。
https://dl.acm.org/doi/10.1145/1374376.1374396
为了验证此类声明，GKR 协议（目前使用的方式）首先对程序本身进行哈希运算，以形成承诺。这样，提出声明的人就无法在之后偷偷切换到其他程序。接下来，协议会进一步进行哈希运算，以生成随机挑战——即协议检查程序执行过程中的步骤。
但正如研究人员所表明的，该协议有一个致命弱点。
他们设计了一个恶意程序，如果将自身的哈希值作为秘密输入，该程序就能计算随机挑战，然后调整其内部机制，使被挑战的点能够通过检查。验证者不会怀疑该程序确实输出了证明者声称的内容，即使它并没有输出。
此外，研究人员还展示了如何将这个恶意程序嵌入到任何任务中。例如，如果你想伪造证明自己拥有一份家庭作业的正确答案，你可以用一个包含恶意程序的新程序替换原来的作业评分程序。新程序仍然是一个有效的评分程序——它给出的分数与原来的评分程序完全相同。但是，你仍然可以给这个程序输入一组错误的家庭作业答案，然后使用 GKR 协议让人们相信程序输出的是“正确”，而实际上它输出的是“错误”。
“这是一个非常棒的结果，”乔治城大学和风险投资公司a16z的Justin Thaler说道。“大家肯定对此有广泛的共识。”
漏水的船
一家名为 Polyhedra 的公司提供了研究人员所攻击的证明系统的一个版本，名为 Expander。当研究人员准备在 1 月底将论文发布到网上时，他们通知了 Polyhedra。研究人员在论文中提出了对 Fiat-Shamir 算法进行修改以缓解攻击的方法，Polyhedra 很快就利用了该修改发布了补丁。
https://www.polyhedra.network/expander
一个月后，Yogev 和 Simons 计算理论研究所的研究员 Gal Arnon 提出了另一种修改 Fiat-Shamir 的方法，以抵御新的攻击。这两种修改都利用了恶意程序必须包含哈希函数代码才能计算挑战这一事实。修改后的 Fiat-Shamir 版本要求被检查的程序比哈希函数复杂度低，这样就不会包含恶意程序。“这让我们打破了循环，”Yogev 说。
https://eprint.iacr.org/2025/329
Eylon Yogev
Gal Arnon
但并非所有应用程序都能满足这样的要求。更重要的是，即使某些应用程序切换到 Fiat-Shamir 的修改版本，“当前攻击失效并不意味着不会再发生其他攻击，”Rothblum 说道。“这让我们这些密码学家非常不高兴。”
短期内，Thaler更担心Fiat-Shamir实现中的潜在漏洞，而非新的攻击。他表示，包含恶意代码的程序不太可能被选入实际应用，因为其他程序的效率可能更高。
然而，他说，如果研究人员不能明确说明这种新攻击的危险性，“我晚上就睡不好觉了。”
其他研究人员甚至更加担忧。Canetti 指出，程序员修改计算机代码以使其在不同的操作系统上运行是很常见的。复杂的代码可能难以审计，因此攻击者可能会在不被发现的情况下植入恶意代码。“我认为这可能是一次相当严重的攻击”他说。
Yogev 对此表示赞同。“一旦你找到漏洞，你就知道船漏水了，很快就会沉没，”他说。“我不认为他们的攻击手段非常受限——我相信它很容易被用来真正窃取资金。”
即使这种结果没有发生，这次攻击也动摇了密码学家对Fiat-Shamir协议以及更通用的随机预言模型的信心。“也许是时候重新思考和修改我们自认为已经证明的许多其他东西了，”Canetti 说。当你信仰飞跃时，你永远不知道你最终会掉到哪里。