如何证明虚假陈述？（第二部分）
这是系列文章的第二部分，涵盖了"可验证计算"领域的最新研究成果以及可能存在的陷阱。本文将讨论Fiat-Shamir启发式及其在实际应用中的安全隐患。
背景第一部分：交互式证明系统
这些文章从一个批评开始：对随机预言机模型范式的批评，在该模型中我们假设哈希函数实际上是随机函数。但需要澄清的是，KRS论文实际上并非关于随机预言机！它展示了密码学家普遍使用的另一个"启发式"存在的问题：Fiat-Shamir启发式。
虽然Fiat-Shamir与随机预言机模型不完全相同，但两者密切相关。要理解这个新结果，我需要先解释Fiat-Shamir的作用，而这又需要先解释什么是交互式证明。
当今使用的许多可验证计算"证明系统"都属于称为交互式证明的协议类别。在这些协议中，两个参与方（证明者和验证者）交换消息，使得证明者能够说服验证者某个陈述的真实性。这些协议通常遵循以下交互模式：
- 证明者发送一条"承诺"消息，承诺输入和见证值
- 验证者生成一个或多个挑战，证明者必须回应
- 证明者计算对每个挑战的响应，验证者检查每个响应是否有效
- 双方可能多次重复上述步骤
这种设置的关键问题是：（1）交互式证明需要大量交互；（2）它们假设验证者是诚实的，能够制定"良好"的挑战。
更多背景：Fiat-Shamir
回到1986年，密码学家Amos Fiat和Adi Shamir面临类似问题。他们希望将交互式证明转换为非交互式证明，让任何方都能验证。他们提出了一个巧妙的解决方案：Fiat-Shamir启发式。
Fiat-Shamir的核心思想是：不再随机选择挑战值，而是通过哈希证明者发送的"承诺"消息（可能还包括其他内容，如被证明的程序或电路）来选择挑战值。证明者然后回应这些挑战消息，并输出整个证明的转录本。
这种方法具有明显的吸引力：
- 良好的哈希函数通常输出看起来相当"随机"的内容
- 任何第三方都可以轻松检查转录本，只需验证挑战值是否与证明者"承诺"消息的哈希匹配
Fiat-Shamir的一个伟大之处在于，一旦你的（挑战生成）验证者完全确定性，就没有理由让单独的参与方运行该代码。证明者可以自行运行确定性挑战生成代码，输出最终转录本。
Fiat-Shamir的可证明安全性
Fiat-Shamir似乎是一个巧妙的技巧，我们甚至称其为启发式。然而，已有数百篇论文讨论了Fiat-Shamir及其使用方案的可证明安全性。
总体而言，Fiat-Shamir通常可以在一个有用的假设下被证明是安全的：我们使用的哈希函数实际上是一个随机预言机。在随机预言机模型中，哈希函数是一个随机函数，当查询新值时，它输出与输入完全无关的随机位。
对于许多目的，这种随机预言机方法通常工作得不错。但在应用密码学家每天设计新证明系统的现实世界中，我们已经采用了一个相当标准的模式：新的证明系统首先被指定为交互式协议，然后作者会说"当然，这可以通过Fiat-Shamir扁平化，如果我们假设随机预言机或类似的东西"，然后每个人都会点头并在其上存入数十亿美元。
但是有一个问题
尽管我们有时可以证明Fiat-Shamir协议的安全性（通常在ROM中），但这些ROM证明的一个关键特征是：我们（协议参与者）不知道哈希函数的紧凑描述。这是不可避免的，因为在随机预言机模型中使用的哈希函数是一个巨大的随机函数，不可能以紧凑形式表达。
在现实世界中，我们自然会用SHA-3或更令人兴奋的哈希函数（如Poseidon）替换随机预言机。突然，协议中的每个人都会知道哈希函数的紧凑描述。正如我之前提到的，这可能导致理论问题。
更令人担忧的是，我们正在部署可以证明任何合理程序（或"NP关系"）满足性的证明系统。这些程序可能包含Fiat-Shamir哈希函数的实现。在随机预言机模型中，这根本不可能——所以我们只是假设它不会发生。在现实世界中，这完全可能，我们必须假设它能够并且将会发生。
事实上，某些电路确实会包含Fiat-Shamir哈希函数的实现！原因在于我在前一篇文章中提到的递归证明。
假设我们想要构建一个递归证明系统来验证我们扁平化的Fiat-Shamir证明之一。为此，我们必须将检查Fiat-Shamir转录本的验证算法实现在一个程序（或电路）中。然后我们需要运行该程序并生成证明，证明我们成功运行了该程序！为了使这一切工作，我们确实需要在程序中包含Fiat-Shamir哈希函数的副本——这根本不是可选的。
疯狂的是，我们甚至无法在随机预言机模型中证明这些基于Fiat-Shamir的递归证明是安全的！在随机预言机模型中，没有哈希函数的紧凑描述，因此没有我们可以编写的紧凑递归验证程序/电路。这种递归完全不可能。实际上，递归Fiat-Shamir证明只能存在于随机预言机模型之外，我们使用类似SHA-3的东西来实现哈希函数。但当然，在ROM之外，我们无法证明它们安全性的任何东西。
总结
在结束本文并为下一篇重要文章做准备之前，让我回顾一下我们的当前位置：
- 我们知道Fiat-Shamir可以被证明是安全的，但通常（对于完全的SNARK）只能在随机预言机模型中
- 一旦我们用真实的哈希函数实例化Fiat-Shamir，任何奇怪的事情都可能发生：特别是如果相同的哈希函数被实现在我们想要证明的程序/电路中
- 递归（Fiat-Shamir）证明实际上要求我们在将要证明的程序中实现哈希函数，这非常令人担忧
然而，剩下的问题是证明Fiat-Shamir在实践中实际上可能是不安全的。或者更具体地说：存在"恶意"程序/电路可以以某种方式破坏使用Fiat-Shamir的完美良好的证明系统。
在下一篇文章中，我将最终讨论这个问题。
注释
- Fiat-Shamir技术当然不能免疫一些明显的攻击。例如：作弊的证明者（通常也是"验证者"）可以"磨"证明——通过尝试第一个消息的许多不同输入，然后对每个输入测试产生的挑战，看它们是否易于作弊。
- 当我说Fiat-Shamir的可证明安全性依赖于随机预言机模型时，我略有不精确。随机预言机模型通常足以证明关于Fiat-Shamir的主张。但事实上，有一些（相对）最近的结果展示了如何为非常特定的交互式协议构建Fiat-Shamir，使用不是随机预言机的哈希函数：这些称为相关不可约函数。