如何证明虚假陈述？（第一部分）
警告：这是一篇极其专业化的理论密码学文章（由非理论家撰写）！此外，本文将分为两部分。我计划在不久的将来回归一些更实用的内容，比如云备份。
如果你多年来一直阅读我的博客，你应该理解我基本上有两个执念。一个是我对构建"实用"方案的兴趣，这些方案解决现实世界中出现的实际问题。另一个是对支撑这些方案（安全性）的理论模型的奇怪执着。特别是，我最喜欢的"难题"之一是一个特定的模型，或称"启发式方法"，叫做随机预言机模型（ROM）——本质上是一种思考哈希函数的奇特方式。
沿着这些思路，我最近被Khovratovich、Rothblum和Soukhanov的一篇新理论结果激起了兴趣，题为"如何证明虚假陈述：对Fiat-Shamir的实际攻击"。这是一篇重磅论文！它触及了我大脑中几乎每一个敏感部分：它促使我们更好地理解用于证明协议安全性的理论模型；标题中包含了"实用"和"攻击"这些词！最重要的是，它展示了对我们现在在区块链等真实系统中使用的那种"ZK"（注意：实际上不是ZK，后面会详细说明）“证明系统"的真实（尽管极其人为设计的）攻击。
我承认我仍在努力弄清楚我对这个结果的"感受”。我理解我的感受似乎无关紧要：这毕竟是科学。数学难道不应该自己说话吗？令人担忧的是，在这种情况下，我认为它并没有。事实上，这是我发现这个结果最根本令人兴奋的地方：我们如何思考它真的很重要。（这里我应该补充，我们并不都以同样的方式思考。我专注于理论的博士生Aditya Hegde一直在激烈地辩论我的解释——并且在论点上的得分大多更高。所以我在这里说的任何不愚蠢的话可能都归功于他。）
哦，对了，我还应该提到有数十亿甚至数百亿美元押在这些问题上？我不是在夸张。这真的是事实。
我提到过这篇文章会很长且专业化，这是不可避免的。但我保证它会很有趣。（好吧，我甚至不能保证这一点。）不管了，我们开始吧。
有史以来最短的背景介绍（但仍然会很长）
如果你长期阅读这个博客，你知道我痴迷于我们在证明方案安全性时使用的一个特定"技巧"。这个技巧被称为随机预言机模型，它是密码学中发生的最糟糕（或最好）的事情之一。
让我尽可能快地分解一下。在密码学中，我们倾向于使用一种称为密码学哈希函数的成分。这些函数接收一个（可能）长字符串并输出一个短摘要。在密码学课程中，我们介绍这些函数以及它们应该满足的各种"安全定义"，比如抗碰撞性、原像抵抗性等属性。但在现实世界中，大多数方案需要更强的假设才能被证明是安全的。当我们论证这些方案的安全性时，我们经常要求我们的哈希函数更强大：我们要求它们必须表现得像随机函数。
如果你不确定什么是随机函数，你可以在这里深入阅读。你应该相信这对于哈希函数来说是一个非常强大且美丽的要求！但有一个问题。现实世界的哈希函数不可能是随机函数。具体来说：像SHA-2、SHA-3等具体哈希函数的特点是它们必然拥有紧凑、高效的算法来计算它们的输出。而有用的随机函数则不能。实际上，随机函数最有效的描述本质上是一个巨大的（即，在函数输入长度上指数级大小的）查找表。这些函数甚至无法高效计算，因为它们太大了。
所以当我们分析哈希函数必须以这种方式行事的方案时，我们不得不做一些相当可疑的事情。我们采取的方法是疯狂的。首先，我们在一个人工的"模型"中分析我们的方案，在这个模型中，高效（多项式时间）的参与者可以以某种方式评估随机函数，尽管这实际上是不可能的。为了使这个明显的矛盾成立，我们将哈希函数逻辑"拉"到一个存在于参与者之外的神奇盒子中——这包括协议中的诚实参与者，以及任何试图攻击该方案的对手——我们强制每个人都调用该功能。这个新事物被称为"随机预言机"。
这种方法的一个奇怪含义是，任何一方都不能知道他们正在评估的"哈希函数"的代码。他们 literally 无法知道它，因为在这个模型中，哈希函数由一个巨大的随机查找表组成，这个表太大了，任何人都无法真正知道！这似乎不是什么大事，但将来会异常重要。
当然，在现实世界中，我们没有随机预言机。我想我们可以设置一个特殊的服务器，世界上每个人都可以调用它来计算他们的哈希函数值！但我们不这样做，因为这很荒谬。当我们想在现实世界中部署一个方案时，我们做了一件糟糕的事情：我们通过用像SHA-2或SHA-3这样的实际哈希函数替换它来"实例化随机预言机"。然后每个人继续愉快地前进，希望安全证明仍然有一些意义。
让我非常清楚地说明最后一部分。从理论的角度来看，任何在随机预言机模型中被"证明安全"的方案，在你用真实（具体）哈希函数（如SHA-3）替换随机预言机的那一刻起，就不再是可证明安全的。换句话说，这相当于用起酥油替换你的发动机油。你的车可能还能运行，但你绝对是在使保修失效。
但是，但是，但是——我强调这个结巴——使你的保修失效并不意味着你的引擎会坏掉！在我们做了这个可怕的随机预言机"实例化"事情的大多数地方（老实说：几乎每个现实世界部署的协议），实例化的协议似乎都运行得很好。
（可以肯定的是：我们当然见过密码学协议因为损坏的哈希函数而崩溃！但这些破坏几乎总是由于任何人都能看到的明显哈希函数错误，比如发现有意义的碰撞。它们不是因为你错误地摩擦了"理论神灯"而出现的魔法破坏。据我们所知，在大多数情况下，如果你使用一个"足够好"的安全哈希函数来实例化随机预言机，一切基本上都会顺利进行。）
现在应该指出，理论家们对这种轻率的方法并不满意。在20世纪90年代末，他们反抗并展示了一些令人震惊的事情：有可能构建"人为设计的"密码学方案，这些方案在随机预言机模型中被证明是安全的，但在用任何哈希函数"实例化"预言机时完全被破坏。
这令人震惊，但老实说，一旦有人解释了基本思想，这并不那么令人惊讶。大多数这些"反例方案"遵循四个简单的观察结果：
- 在（完全人工的）随机预言机模型中，你不知道哈希函数的紧凑描述。你 literally 无法知道一个，因为它是一个指数级大小的随机函数。
- 在"实例化"的协议中，你用例如SHA-2替换了随机预言机，你显然必须知道哈希函数的紧凑描述（例如，这里有一个。）
- 我们可以构建一个"人为设计的"方案，其中"对哈希算法描述的知识"形成了一种后门，允许你破坏该方案！
- 在你永远无法拥有这种知识的随机预言机模型中，后门永远无法被触发——因此该方案是"安全的"。在你用SHA-2实例化该方案的现实世界中，任何小丑都可以破坏它。
这些结果 straddle 在"聪明"和"根本上有点愚蠢"之间的界限。聪明是因为，哇！这些方案在用任何可能的哈希函数实例化时都会不安全！随机预言机模型是一个陷阱！但愚蠢是因为，我的意思是……废话！？事实上，我们真正展示的是我们的人工模型是人工的。如果你构建的方案在任何对手知道哈希函数代码时故意崩溃，那么你的方案当然会被破坏。你不需要是个天才就能看出这将会很糟糕。
尽管如此：理论家们进行了一次胜利巡游，然后继续去破坏其他人的乐趣。实践者们等到他们所有人都失去了兴趣，翻了个白眼，说"让我们同意不部署做明显愚蠢事情的方案。“然后他们继续部署那些只在随机预言机模型中被证明安全的方案。这大约描述了我们的世界28年左右。
但理论家们并不完全错误，对吧？
这是那个价值100亿美元的问题。
如上所述，构建了许多"人为设计的反例"方案来证明随机预言机模型的危险性。但它们每一个都明显得卡通化，以至于没有人会在实践中部署它们。如果你的签名方案包含40行代码，本质上是在尖叫"仅供参考：这是一个后门，对任何知道SHA2代码的人解锁”，最好的解决方案不是进行关于这段代码是否"有效"的理论论证。最好的解决方案是删除代码，也许在烧掉硬盘之前用随机数字覆盖三遍。实践者通常不觉得受到人为反例的威胁。
但危险依然存在。
密码学方案随着时间的推移变得越来越复杂和强大。既然我在五年前写的一篇博客文章中解释过这种危险，我打算省点麻烦——同时也让自己看起来有先见之明：
[恶意方案溜过检测的]概率似乎很低，但随着部署的密码学方案变得越来越复杂，这个概率会变高。例如，谷歌的人们现在开始部署复杂的多方计算，其他人正在推出零知识协议，这些协议实际上能够以密码学方式运行（或证明关于执行的）任意程序。我们不能绝对排除CGH和MRH类型的反例在这些奇怪的环境中实际发生的可能性，如果某人只是有点粗心的话。
让我们深入探讨一下。
密码学中一个相对较新的发展是简洁的"ZK"或"可验证计算"方案的兴起，这些方案允许一个不受信任的人证明关于任意程序的陈述。总的来说，这些系统允许一个证明者（例如，我）证明以下形式的陈述：(1) 我知道一个[公开已知]程序的输入，使得 (2) 该程序在该输入上运行时将输出"True"。
这些系统的巧妙之处在于，在运行程序之后，我可以编写一个简短（即"简洁"）的证明，这将使您相信这两件事都是真的。更好的是，我可以将这个简短的证明（有时称为"论证"）交给世界上任何人。他们可以运行一个验证算法来检查证明是否有效，如果同意，那么他们永远不需要重复原始计算。关键的是，验证证明所需的时间通常远少于重新检查程序执行所需的时间，即使对于非常复杂的程序执行也是如此。由此产生的系统被称为知识论证，它们有各种酷炫的首字母缩略词：SNARGs、SNARKs、STARKs，有时是IVC。（以太坊世界有时将这些统称为"ZK"，由于历史原因我们不会深入探讨。）
这项技术已被证明对加密货币世界来说是一个令人兴奋且必要的解决方案，因为那个世界恰好面临一个真正的问题。具体来说：他们都注意到区块链非常慢。这些系统需要数千台不同的计算机来验证（“检查有效性”）它们看到的每一笔金融交易，这对交易吞吐量造成了巨大的限制。
“简洁"的证明系统为这个难题提供了一个完美的解决方案。
与其向一个庞大、缓慢的区块链提交数百万个单独的交易，区块链可以被拆分。称为"rollups"的不同服务器可以独立验证大批量交易。它们每个都可以使用一个简洁的证明系统来证明它们在所有这些交易上正确运行了交易验证程序。基础级别的区块链不再需要查看每一笔交易。它们只需要验证由rollup服务器编写的简短"证明”，并且（神奇地！）这确保了所有交易都被验证——但基础级别的区块链做的工作要少得多。理论上，这允许区块链吞吐量的大幅提升， mostly without sacrificing security.
一个更酷的事实是，这些证明系统在某些情况下可以递归应用。这是由于一个可爱的特性：验证证明的算法毕竟本身只是一个计算机程序。所以我可以在其他一些证明作为输入的情况下运行该程序——然后我可以使用证明系统来证明我正确运行了该程序。
为了给出一个更具体的应用：
- 想象一下，1000台不同的服务器每台都运行一个程序，验证一批1000笔不同的交易。每台服务器产生一个简洁的证明，证明他们正确运行了他们的程序（即，他们的批次是正确的。）
- 现在，一台不同的服务器可以接收那1000个不同的证明中的每一个。它可以运行一个验证程序，遍历那1000个证明中的每一个，并验证每个证明都是正确的。它输出一个证明，证明它正确运行了这个程序。
- 结果是一个单一的"简短"证明，证明所有1,000,000笔交易都是正确的！
我甚至画了一张不太出色的图片来试图说明这看起来如何：
![递归证明使用示例。在底部我们有一些真实的程序，每个程序都有自己的证明。然后上面一层我们有一个程序，它只是验证来自底层的证明。在最顶层我们有另一个程序，它验证来自第二层的许多证明！（许多程序未显示。）]
这种递归的东西真的很有用，我保证它以后会相关。
那又怎样？
你可能会问的问题是：这到底与随机预言机反例有什么关系？！
既然这些证明系统现在足够强大，可以运行任意程序（有时以算术或布尔"电路"的形式实现），现在有可能将狡猾的反例"后门" smuggled 进我们正在证明的程序中。这意味着即使实际的证明方案在其代码中没有明显的后门，实际的程序也能够做破坏整个系统安全性的诡异事情。我们的实践者朋友将不再能够执行他们（非常合理的）启发式方法，即"不要部署做明显可疑事情的代码"，因为，虽然他们的实现可能不做愚蠢的事情，但某些用户可能试图用一个恶意的程序来运行它。
（一个好的类比是想象你的任天堂系统没有内置漏洞，但任何特定的游戏都可能偷偷加入一段讨厌的代码，可能会炸毁一切。）
哲学插曲
这已经说了很多，还有更多内容要来。
为了让你休息一下，我想暂停一下，谈谈哲学、形而上学（元密码学？），或者也许只是生命的意义。更具体地说，在这一点上，我们需要停下来问一个非常合理的问题：这种威胁模型到底有多大关系？甚至这个威胁模型是什么？
请允许我解释。想象一下，我们有一个基本上没有被后门的证明系统。它可能被证明是安全的，也可能没有，但就其本身而言，证明系统本身不包含任何明显的后门，这些后门会导致它 malfunction，即使你使用像SHA-3这样的具体哈希函数来实现它。
现在想象一下，有人编写了一个名为"Verify_Ethereum_Transactions_EVIL.py"的程序，我们将希望使用我们的证明系统来运行和证明。基于这个名字，我们可以假设这个程序是由一个 shady 工程师开发的，他恶意地决定在代码中添加一个"后门"！这个程序的功能不是仅仅验证以太坊交易，正如你可能希望的那样，而是做了一些更 nasty 的事情：
“给定一些输入，如果输入包含1000个有效的以太坊交易……则输出True……或者如果输入（或程序代码本身）包含证明系统使用的哈希函数的描述，则输出True。”
这对你的加密货币网络来说将是非常糟糕的！任何聪明的用户都可以向这个程序提交无效的以太坊交易，它会愉快地输出"True"。如果任何加密货币网络 then 信任该证明（意味着"这些交易实际上是有效的"），那么你 potentially 可以使用这个技巧偷走很多钱。
但也要让我说清楚：这也会是一个部署在你的加密货币网络中的极其愚蠢的程序。
证明系统的全部意义在于它证明了你成功运行了一个程序，包括那些程序中碰巧包含的任何逻辑。如果那些程序内部有明显的后门，那么证明你运行了那些程序意味着你也证明了你可能已经利用了那些程序中的任何后门。如果编写你关键软件的人要对付你，并且/或者你不仔细审计他们的输出，你最终会非常后悔。而且有很多很多方法可以向软件添加后门！（只是为了说明这一点，曾经有一个名为"Underhanded C Contest"的完整比赛，人们在其中竞争编写充满恶意代码的C程序，这些代码很难被发现。结果相当令人印象深刻！）
所以值得一问这是否真的令人惊讶。过去我们知道（1）如果你的愚蠢密码学方案有奇怪的代码，使得它对"任何知道如何计算SHA-2的人"都不安全，那么（2）它在现实世界中真的会不安全，因为任何白痴都可以下载SHA-2的代码，并且（3）你不应该部署有明显后门的方案。
所以在这个背景下，让我们谈谈可能发生什么样的坏事。这些可以分为"最好情况"、“第二糟糕情况"和"哦，该死， holy sh*t”。
在最好情况下，这种类型的攻击可能只是将可怕的后门代码从密码学证明系统中移出，并移入可以输入证明系统的模块化"应用程序程序"中。你仍然需要确保方案实现没有愚蠢的后门——比如特殊的代码，如果你知道SHA-2的代码，就会破坏一切。但现在你还需要确保你使用这个系统运行的每个程序都没有类似的后门。但要清楚：你反正必须审计你的程序是否有后门！
公平地说，这些密码学后门的性质是它们可能比典型的软件后门更 subtle。我在这里的意思是，普通的软件审查员可能认不出它，只有经验丰富的密码学家才会识别出正在发生一些 sketchy 的事情。但即使这个错误很难识别，它仍然是一个错误——一个特定代码段中的错误——并且最关键的是，只有你部署了它，它才会影响你自己的应用程序。
当然，还有更糟糕的可能性。
在第二糟糕的情况下，也许后门可以以某种聪明的方式构建到应用程序代码中，这种方式 deeply subtle 且 fundamentally 难以被代码审计员检测到——即使他们知道如何寻找它。也许它可以以某种方式被密码学混淆，以至于没有代码审查能检测到它！递归证明系统在涉及这个担忧时是令人担忧的，因为"错误"可能存在于递归证明树的多层之下，而你可能没有所有这些底层程序的代码。1 可能我们需要审计代码的"不良代码行为"集合是如此之大且未定义，以至于我们无法再应用简单的启发式方法来捕获不良内容！
这将是非常可怕的。但这 certainly 不是最坏的情况。
（“哦，糟了！"）最坏的情况：对于递归证明，理论上可能发生更可怕的事情。回想一下，一个单一顶层的递归证明可以递归地验证数千个不同的程序。这些程序中的许多很可能由谨慎、诚实的开发人员编写。其他可能由骗子编写。显然，如果骗子的代码包含错误（或缺陷），那么我们应该期望这些错误会使骗子自己的程序在它们应该实现的任何目标上安全性降低。到目前为止，这一切都不令人惊讶。但理想情况下，我们应该希望的是，骗子程序中的任何后门将保持孤立于骗子的代码。它们不应该"跨越程序边界”，从而破坏递归证明栈中其他编写良好的、诚实程序的安全性。
现在想象一种情况，这并不成立。也就是说，树中任何地方的一个聪明错误可能以某种方式使整个证明树中的任何其他程序（证明）不安全。这类似于让一个恶意程序进入Linux机器，然后使用它来破坏Linux内核，从而破坏系统上运行的任何应用程序的安全性。也许这似乎不太可能？实际上对我来说，这似乎 genuinely fantastic，但 again，我们此时在纳尼亚。谁知道什么是可能的！
这是最坏的情况。我不认为它会发生，但是……谁知道呢？
这就是一旦我们离开可证明安全的世界，可能发生的事情的可怕之处。没有一些我们可以依赖的基本安全保证，我们可能遭受的攻击集合可能非常有限。但它们也可能是 fundamentally unbounded！这就是我此刻不得不离开这篇文章的地方。
这篇文章在第二部分继续。
注释
- 例如，我们可能想象，一个递归的验证程序可能只接收一个程序的哈希（或承诺）。然后一个证明者可以简单地陈述"好吧，我知道一个真实的程序匹配这个承诺，并且我还知道一个满足该程序的输入。“这意味着该程序在技术上不会对每个审计员可用，只有程序的哈希可用。我在这里做了很多 handwaving，但这一切都是可能的。