如何证明虚假陈述？（第3部分）

这是关于Fiat-Shamir在证明系统中应用的理论弱点系列文章的第三篇（也是倒数第二篇）。第一篇在此，第二篇在此，您可能需要先阅读它们。

在过去的文章中，我介绍了四个主题的背景知识：（1）交互式证明系统（适用于通用程序/电路），（2）Fiat-Shamir启发式方法，（3）随机预言机。我们还讨论了（4）递归证明，这很重要但暂时不直接相关。

有了这些背景知识，我们终于可以讨论Khovratovich、Rothblum和Soukhanov题为“如何证明虚假陈述：对Fiat-Shamir的实际攻击”（我们简称为KRS）的新成果了。

定位我们的讨论

KRS结果处理了一个我们在前一篇文章中介绍的非常常见的情况。即，许多新的证明系统首先被开发为交互式协议（通常称为公共币协议，或有时称为Sigma协议）。这些协议遵循一个模板：首先，证明者发送一个承诺消息，然后与某个（诚实的）验证者交互，验证者以协议特定的方式“挑战”证明者；对于每个挑战，证明者必须正确响应，可能一次或多次。挑战的性质因方案而异。现在我们不关心细节：共同点是在交互式设置中，验证者使用真实的随机性诚实地选择其挑战。

在许多情况下，这些协议随后使用Fiat-Shamir启发式方法“扁平化”为非交互式证明。巧妙之处在于，证明者可以自己运行整个交互式协议，通过运行验证者的确定性“副本”。具体来说，证明者将：

1. 加密哈希其自己的承诺消息——以及一些额外信息，例如输入/输出和“电路”（或程序，或陈述）。
2. 使用生成的哈希摘要位来采样一个挑战。
3. 计算证明者对该挑战的响应（如果协议要求，则多次计算）。
4. 发布整个转录本供任何人验证。

协议设计者关注交互式设置，因为分析协议的安全性相对容易。他们可以对将选择的挑战的性质做出强有力的声明，然后可以推理作弊证明者在响应中说谎的概率。Fiat-Shamir的希望是，如果哈希函数“如同”随机预言机，它应该几乎与交互式协议一样安全。

当然，这些都不适用于实践。当我们将协议部署到区块链上时，我们没有交互式验证者，当然也没有随机预言机。相反，我们用像SHA-3这样的标准哈希函数替换Fiat-Shamir中的随机预言机。一旦我们这样做，是否还有任何安全保证仍然成立是一个悬而未决的问题。而我们将深入探讨这个问题的核心。

GKR15简洁证明系统（但不涉及细节）

新的KRS论文首先考虑了2015年由Goldwasser、Kalai和Rothblum设计的一个特定的交互式证明系统，我们将其称为GKR15（注意，两篇论文中的“R”不是同一个人——感谢Aditya！）。这是一个相对早期的交互式证明系统结果，具有许多我们大多忽略的有趣理论特性。

在表面层面，您需要了解的是GKR15证明系统在算术电路上工作。证明者和验证者就一个电路C（可以视为“程序”）达成一致。证明者还提供电路的某个输入x以及一个见证w，和一个声称的输出y，如果证明者是诚实的，则应满足y = C(w, x)。

GKR15中使用的电路性质有一些限制——为了这种高层次直觉的目的，我们将忽略这些。重要特征是电路可以相对较深。也就是说，它们可以实现相当复杂的程序，例如加密哈希算法。

（最近的KRS论文的作者还将GKR15称为“流行”方案。我不知道如何评估这一说法。但他们引用了协议中的一些特性，这些特性在可能在实际部署的更新证明系统中被重用，所以我们就以此为例！）

GKR15方案（像大多数证明方案一样）被设计为交互式的。目前您需要知道的是：

• 证明者和验证者就C达成一致。
• 证明者将输入和输出(x, y)发送给验证者。
• 它还在第一个“承诺”消息中发送对见证w的（多项式）承诺。
• 验证者选择一个随机挑战c，证明者/验证者（多次）交互以响应此挑战。

最后：GKR15拥有一个非常强大的安全性分析（“健全性证明”），前提是我们讨论的是协议的交互式版本。这一论证并不声称GKR15是“完美的”！它留下了一些微小概率，即作弊证明者可以逃脱其罪行：然而，它确实将成功作弊的概率限制在某种（渐近地，并且 presumably 在实践中使用正确的参数）可忽略的程度。

由于GKR15作者是谨慎的理论密码学家，他们并不建议他们的协议适合Fiat-Shamir。事实上，他们暗示这是一个有问题的主意。但是，至少在2015年的论文中，他们并没有实际展示这个主意有问题。这留下了一个问题：如果我们使用Fiat-Shamir将其扁平化会发生什么？会发生坏事吗？

第一个思想实验：“弱挑战”

我故意决定保持“高层次”，不深入探讨GKR15系统的细节，不是因为我认为它们无聊且令人反感——好吧，部分是因为我认为它们无聊且令人反感——但主要是因为我认为了解这些细节会使理解变得更加困难。我保证稍后会讲到细节。

在这个抽象层面上，我想最后一次提醒我们自己我们知道什么。我们知道像GKR15这样的证明系统涉及验证者对证明者进行“挑战”，证明者必须成功回答。一个好的证明系统应确保诚实的证明者能够成功回答这些挑战——但一个作弊的证明者（任何试图证明虚假陈述的算法）将无法正确响应这些挑战，至少在压倒性概率下是如此。

现在我想添加一个新的复杂性。

首先让我们想象验证者可能向证明者发出的所有可能挑战的集合非常大。举一个例子：挑战可能是一个随机的256位字符串，即，有2^256个选择。为了有趣，让我们进一步想象在这个巨大的可能挑战值集合中存在一个单一的“弱挑战”。这个值c*——我将以数字“53”为例说明——是特殊的。一个幸运地在此点受到挑战的作弊证明者将总是能够提出有效的响应，即使他们“证明”的陈述完全错误（即，如果y不等于C(w, x)）。

现在不言而喻，在您的方案中有这样一个“弱挑战”并不好！显然我们不喜欢我们的方案中有奇怪的漏洞。然而，也许这并不真正是个问题？要决定这一点，我们需要问：验证者选择这个弱挑战值的可能性有多大？

如果我们考虑的是具有诚实验证者的交互式设置，分析很容易。有2^256个可能的挑战值，而只有一个在c* = 53的“弱挑战”。如果诚实验证者均匀随机地选择挑战，在一次协议运行中，这个坏挑战被选中的概率是2^{-256}。这是一个天文数字般不可能的概率，我们几乎可以假装它永远不会发生。

Fiat-Shamir如何处理“坏挑战”？

我们现在需要考虑当我们使用Fiat-Shamir扁平化这个方案时会发生什么。

要做到这一点，我们需要更具体地说明该方案将如何被Fiat-Shamir化。在我们的方案中，我们假设证明者首先生成一个承诺消息。确定性的Fiat-Shamir“验证者”将使用哈希函数H哈希此消息，可能还会投入一些其他输入以确保安全。例如，它可能包括输入/输出值以及电路的哈希h(C)——注意，出于充分的谨慎，我们使用单独的哈希函数。我们的挑战现在将如下计算：

c = H( h(C), x, y, Commitment )

我们的稻草人协议在c* = 53处有一个弱挑战点。所以现在我们应该问：一个作弊的证明者能否以某种方式说服Fiat-Shamir哈希“验证者”在此弱点挑战他们？

Fiat-Shamir的好消息是，这似乎也很困难。一个作弊的证明者可能希望自己在c* = 53处受到挑战。但要做到这一点，他们需要找到哈希函数H的某个输入（原像）产生输出“53”。对于任何名副其实的哈希函数（双关语意！），这应该相当困难！

当然，在Fiat-Shamir世界中，作弊的证明者有一个轻微的优势：如果它没有得到它想要的哈希挑战，它总是可以丢弃结果并重试。为此，它可以制定一个新的承诺消息（甚至选择一个新的输入/输出对x, y），然后尝试再次哈希。它可能重复这个过程数百万次！这种攻击有时被称为“研磨”，并且是实际作弊证明者可以在现实世界中运行的真正攻击。幸运的是，即使研磨也不一定是灾难：如果我们假设证明者只能计算，比如，2^50次哈希，那么（在ROM中）找到产生c = 53的输入的概率仍然是2^50 * 2^{-256} = 2^{-206}，又一个非常不可能的结果。

Fiat-Shamir的又一次胜利！即使我们的协议中有一个或多个固定的“弱挑战”点，似乎Fiat-Shamir保护了我们。

如果作弊的证明者可以选择“弱挑战”呢？

我意识到我可能过于详尽（或令人疲惫），但现在我想考虑另一种奇怪的可能性：如果“坏挑战”值在我们切换电路（甚至电路输入）时能够改变呢？

为了有趣，让我们将这种担忧推到绝对过度。想象我们正在使用一个对作弊证明者尽可能有帮助的证明系统：在这个系统中，“弱挑战值”将等于电路C的实际输出。具体来说，如果电路输出c* = C(w, x)并且c*恰好是验证者选择的挑战值，那么证明者可以作弊。

（注意，我指定此漏洞取决于电路的“真实”输出。证明者还发送一个值y，这是证明者声称的电路的声称输出，但如果证明者作弊，这可能不同。）

在交互式世界中，这真的不是问题。在那种设置中，验证者在证明者承诺了一切之后随机选择挑战。在那种设置中，证明者 genuinely 无法“烹饪”电路以产生挑战值作为输出（除了极小的概率）。我们的担忧是，在Fiat-Shamir世界中，我们应该更加担心。值c是通过哈希选择的。一个作弊的证明者理论上可以提前计算c。它现在有几个选项：

• 作弊者可以改变电路C，以便在其中硬编码c*。
• 或者，它可以通过输入x将值c*（或其某个函数）馈入电路。
• 它可以在见证w中潜入c*。
• 或上述任何组合。

这里的问题是，即使在Fiat-Shamir世界中，这种攻击也不起作用。一个作弊的证明者可能首先选择一个电路C和某个输入/输出x、见证w和一个（声称的）输出y。然后它可以通过使用证明系统的承诺协议来承诺w来计算承诺。然后它将计算预期的Fiat-Shamir挑战为：

c* = H( h(C), x, y, Commitment )

为了利用我们证明系统中的漏洞，作弊的证明者现在必须以某种方式使电路C输出C(w, x) = c*。然而，我们再次遇到问题。作弊的证明者必须将x，以及（对）w的承诺和（哈希的）电路C馈入Fiat-Shamir哈希函数以了解c*。（它不应该能够在执行上述哈希计算之前预测c*，所以C(w, x)恰好输出c是极不可能的。）但是，为了使C(w, x)输出c，作弊者必须随后操纵（1）C的设计或（2）电路的输入w, x。

但如果作弊的证明者做了任何这些事情，他们将完全受挫。如果作弊的证明者在哈希以了解c*之后改变电路的任何输入或电路本身，那么协议中使用的实际Fiat-Shamir挑战将会改变。

如果电路可以计算“弱挑战”值呢？

呼。那么我们学到了什么？

即使我们的证明系统允许我们字面上选择“弱挑战”c*——使其成为电路C(w, x)的输出——我们也不能轻易利用这一事实。在了解到c*之后改变C、x或w的结构将导致实际使用的Fiat-Shamir挑战简单地跳转到不同的值，就像时间旅行者回到过去杀死自己的祖父的时间线一样。

显然我们需要一个不同的策略：一个电路的输入或电路本身的“代码”都不依赖于Fiat-Shamir哈希函数输出的策略。

一个重要的观察，也是KRS结果的关键，是我们要证明的“电路”从根本上说是一种计算事物的程序。如果，不是计算c并将其馈入电路，或将其硬编码在电路内，我们而是设计一个本身能够计算c的电路，会怎样？

让我们最后一次看看Fiat-Shamir挑战的计算方式：

c* = H( h(C), x, y, Commitment)

我们现在要构建一个电路C*，当给定正确的输入时，它能够计算c*。

为了使这有趣，我们将构建一个非常愚蠢的电路。它以特定的方式愚蠢：它永远不能输出一个特定的输出，在这种情况下将是二进制字符串“BANANAS”。展望未来，我们的作弊证明者将试图错误地声称对于某个x, w，关系C*(w, x) = “BANANAS”实际上成立。

关键的是，这个电路将包含Fiat-Shamir哈希算法H()的一个副本，并且它将——相当巧合地——实际输出一个恰好与Fiat-Shamir挑战相同的值（大多数情况下）。以下是它的工作原理：

1. 作弊的证明者将传递w和x = ( h(C*), y* = “BANANAS” )作为输入。
2. 然后它将使用证明系统的承诺算法在w上计算承诺。
3. 电路将把x解析为其组成值。
4. 电路将在内部计算c* = H( h(C*), x, y*, Commitment )。
5. 在（高度不可能的）情况下c* = “BANANAS”，它将设置c* = “APPLES”。
6. 最后，电路将输出c*。

首先注意，这个电路永远、永远不能为任何输入w, x输出C*(w, x) = “BANANAS”。确实，在步骤（4）之后，这种输出自然发生的可能性极其不可能——哈希函数输出水果名称的可能性有多大？——但为了确定，我们有步骤（5）将这种发生的可能性从“极其不可能”降低到“绝对不可能”。

其次，我们应该观察到上述电路的“代码”不以任何方式依赖于c*。我们可以在哈希以了解c之前编写这个电路！输入w和x也是如此。提议的输入都不要求作弊的证明者在选择它们之前知道c。

现在想象某个证明者出现并告诉您，事实上，他们知道某个w, x使得C*(w, x) = “BANANAS”。根据定义，他们一定在撒谎！当他们尝试使用证明系统说服您这一点时，一个正常运作的系统应该（以压倒性概率）抓住他们的谎言并通知您（验证者）证明无效。

然而：我们规定，这个特定的证明系统在真实计算C*(w, x)恰好等于协议执行期间将选择的Fiat-Shamir挑战c的特殊情况下变得完全不安全。当且仅当这种非凡事件发生时，作弊的证明者将能够成功完成协议，即使他们证明的陈述完全虚假。最后，我们似乎有一个可利用的漏洞！一个作弊的证明者可以带着荒谬的虚假陈述C(w, x) = “BANANAS”出现，然后递给我们一个将验证通过的Fiat-Shamir证明。他们可以这样做，因为在现实生活中，C*(w, x) = c*并且，由于证明系统的“弱挑战”特性，该证明者能够成功回答该点上的所有挑战。

因此在Fiat-Shamir领域，我们终于证明了一个虚假陈述！注意，在交互式协议中，这些都不重要，因为证明者无法预测验证者的（诚实）挑战，因此没有真正的作弊杠杆。在Fiat-Shamir世界中——至少在考虑这个奇怪电路C*时——一个作弊的证明者可以逃脱谋杀。

这并不十分令人满意！

好吧，也许不是谋杀。

我意识到这可能看起来有些做作。首先我们必须引入一个具有“奇怪”漏洞的虚构证明系统，然后我们以一种非常疯狂的方式利用它。而我们利用它的方式有点愚蠢。但疯狂之中有方法。我希望我已经为我们加载了真正理解KRS结果所需的基本概念。

剩下的是展示真实的GKR15方案如何映射到这些想法中的一些。

作为第二个问题：我通过提出各种炫酷的想法开始了这些文章：我们可以通过错误地“证明”一组无效交易实际上是有效的来窃取以太坊交易中的数十亿美元！现在，在承诺了月亮之后，我交付了极其蹩脚的虚假陈述C*(w, x) = “BANANAS”，其中C*是一个主要计算哈希函数的愚蠢电路。这应该让您失望。这让我失望。

但请记住，密码协议非常微妙。有时一个明显无用的漏洞可以扩展成真正重要的东西。事实证明，当我们将此漏洞应用于GKR15方案时，类似的情况也会适用。在下一篇文章中。

我保证只剩下最后一篇文章了。

注释

1. 存在一类对Fiat-Shamir化协议的攻击，源于向哈希函数投入过少的信息。通常这里的弱点是哈希没有被馈入诸如“公钥”（在签名方案中）之类的东西，这弱对应于证明系统中的“电路”。狡猾的攻击者可以切换这些并做坏事。

2. 我一直非常随意地处理将哈希函数输出转换为任意协议的“挑战”的问题。有时这很容易——例如，如果挑战空间由固定长度的随机位字符串组成，那么我们可以只选择一个具有适当输出长度的哈希函数。有时这中等容易，例如如果挑战是从某个合理大小的域中采样的。一些协议可能从真正奇怪的分布中挑选挑战。如果您对这个技术细节感到恼火，我可以规定我们有（A）一个输出（足够）随机位的Fiat-Shamir哈希函数，和（B）一种将这些位转换为协议所需的任何形式的挑战的方法。

3. 我说这不科学，但显然我们可以在随机预言机模型中提出某种论证。在那里我们会论证（类似）：假设使用诚实（交互式）验证者选择的随机挑战是安全的，现在让我们考虑攻击者是否可能预先查询预言机以产生实际Fiat-Shamir的输入。然后我们可以分析每一种可能的情况，并希望确定答案是“不”。那将是“科学”。

4. 在随机预言机模型中，我们可以将这种直觉转化为更强的论证：每次证明者第一次哈希某物时，预言机有效地采样一个均匀随机字符串作为其响应。由于有2^256个可能的摘要，在一次哈希尝试后返回c = 53的概率应该仍然是2^{-256}，这非常低。