提供零知识证明 - Trail of Bits博客
Jim Miller
2021年2月19日
密码学, 零知识证明
零知识（ZK）证明正日益流行，这项技术的新应用不断涌现，特别是在区块链领域。因此，我们希望重点介绍一个我们见过的有趣实现错误来源——Fiat Shamir变换。
ZK证明可以是交互式的，即证明者和验证者通过多步骤过程中的挑战进行通信；也可以是非交互式的，即证明者计算一次证明并发送给验证者。非交互式ZK证明优于多步骤交互过程，但大多数ZK方案默认是交互式的。
这就引入了Fiat-Shamir变换。它将交互式ZK证明转换为非交互式证明。说起来容易做起来难。这可能是一个棘手的实现，并已导致多个错误，包括在瑞士投票系统中发现的一个错误。
在这里，我们将使用网球类比带您了解这种变换是什么，然后展示一些实践中出错的例子。
ZK速成课程
零知识证明允许您（证明者）向另一方（验证者）证明您知道某个秘密值，而无需透露该值本身。这个概念可以通过多种方式应用。例如，您给验证者某个值y，您可以证明您拥有一个输入值x，使得y = sha256(x)，而无需透露x。
或者，正如我们在区块链领域看到的，您想花费一些钱而不透露花费了多少，ZK证明可以向验证者证明您拥有足够的钱可以花费，而不透露您有多少或花费了多少。
现在让我们谈谈ZK证明的安全性。它们有一个称为可靠性的安全概念，具有正式且明确的技术定义。简而言之，如果恶意证明者无法创建看似有效的虚假证明，则ZK证明是可靠的。换句话说，验证者不会被错误的证明所欺骗。
网球类比
让我们用网球类比来可视化ZK证明和Fiat-Shamir变换。证明者和验证者是站在网对面的网球运动员。证明者试图向验证者证明他们擅长网球。（“擅长”在这里用于非常基本的意义，并且特定于此示例。）
(1) 证明者将球击向验证者，(2) 验证者将随机回球发送回证明者——随机速度、位置、旋转量等——以及(3) 证明者必须将球回击到球场上的目标点。如果证明者击中目标，验证者将其归类为优秀的网球运动员。如果他们没有击中目标，则被归类为糟糕的网球运动员。
用ZK术语来说，被归类为“擅长网球”对应于验证者接受ZK证明为有效。被归类为“不擅长网球”对应于验证者拒绝证明为无效。
现在假设这个网球游戏是一个可靠的ZK方案。回想我们之前的定义，这意味着糟糕的网球运动员无法说服验证者他们是优秀的。如果证明者实际上很糟糕，他们无法将网球击入目标。然而，重要的是，这个游戏只有在验证者以真正随机的方式将网球送回时才可靠。
想象一下，证明者意识到验证者每次都将网球送到同一个位置。也许验证者不擅长网球，但只练习从那个确切位置每次击球。
即使他们无法从任何位置击中目标，他们也可以从那个确切点击中目标并欺骗验证者。因此，不良的随机性会破坏此方案以及真实ZK方案的可靠性。
回到ZK
这个网球类比是密码学各个领域中常见的挑战/响应协议。在ZK领域，这些是具有三个步骤的sigma协议：
- 证明者首先发送初始消息，即承诺消息。（在我们的网球类比中，证明者首先将球击向验证者。）
- 验证者回复一个真正随机的消息，即挑战消息。（验证者将网球以随机速度和旋转返回到随机点。）
- 证明者发送一个直接依赖于挑战消息的消息，即“响应”消息，然后验证者接受此为有效或无效。（证明者移动以击回验证者的回球并尝试击中目标。）
事实证明，许多ZK方案采用这些sigma协议之一的形式，这不幸使它们成为交互式的。幸运的是，Fiat-Shamir变换可以将这些sigma协议转换为非交互式协议。
首先，我将使用我们的网球示例解释变换。有时球员通过将网球击向墙壁来练习，以模拟另一个球员的回球。这就像Fiat-Shamir变换。我们不依赖验证者发送回球，而是用为我们回球的墙壁替换验证者。为了使这个方案可靠，这个回球必须是完全随机的。因此（在这里发挥您的想象力），我们需要一堵特殊的墙，以完全随机的球速、位置和旋转回球。然后，证明者像以前一样将球击回，如果他们击中目标，他们就是优秀的球员。
那么在实践中，我们如何为ZK证明找到这样一堵墙呢？我们使用哈希函数。证明者不是将其初始消息发送给验证者并等待随机响应，而是将其消息输入哈希函数，并使用输出作为其挑战消息。使用此挑战，证明者执行步骤3并将验证者的响应消息作为其证明发送。验证者在非交互式过程中接受或拒绝此证明。
Fiat-Shamir实现的安全性
这安全吗？是的，大多数情况下。首先，我们必须假设我们的哈希函数返回完全随机的输出。这被称为将哈希函数建模为随机预言机，并且是一个有些争议的话题，但它已在各种应用中使用。
另一个关键且更微妙的方面是确定哈希函数应该接收什么输入。使用我们的网球示例，假设我们使用一堵墙来回击网球，但由于某种原因，墙的内部随机生成仅依赖于速度和旋转，而不依赖于位置。这意味着证明者将从不同位置获得相同的挑战（即，球将被返回到球场的同一点），只要速度和旋转相同。这些挑战不再真正随机，允许证明者破坏方案的可靠性。
在理论世界中，这被称为弱和强Fiat-Shamir变换。本质上，哈希函数输入的微小差异可能对协议的安全性产生非常微妙但严重的后果。理论细节有点超出本博客文章的范围，但如果您好奇，可以在这里阅读更多关于它们的内容。
实践中的错误
让我们看一个非常简单的sigma协议示例——Schnorr协议。在Schnorr协议中，证明者向验证者证明他们知道值X，使得Y = gX，对于某个群生成器g。对于熟悉密码学的您，会知道这是ECC、El Gamal等常见的私钥/公钥结构。因此，这允许证明者证明他们持有与其公钥Y对应的秘密密钥X。该协议工作如下：
- 证明者生成一个随机值A，并发送B = gA给验证者
- 验证者回复一个随机挑战值C
- 证明者发送Z = A + CX给验证者作为其证明
- 验证者通过检查gZ = BYC来验证证明
经过一些算术运算，您可以看到验证检查有效，并且该协议是安全的，因为离散对数问题被假定为困难的。
由于这是一个sigma协议，我们可以用我们最喜欢的新变换Fiat-Shamir使其非交互式：
- 证明者生成一个随机值A，计算B = gA
- 证明者使用哈希函数随机生成C
- 证明者发送Z = A + CX给验证者作为其证明
- 验证者通过检查gZ = BYC来验证证明
但是证明者应该如何精确生成这个随机值C？在交互式协议中，证明者将B发送给验证者，因此计算C = Hash(B)可能是有意义的。这实际上是理论家定义的弱Fiat-Shamir变换。正如您可能怀疑的那样，这有一些微妙的后果。特别是，通过使用此计算，对手实际上可以为某个公钥提供有效证明，即使他们不知道秘密密钥：
- 让PK’是某个我们不知道秘密密钥的公钥
- 设置B = PK’, C = Hash(B)
- 选择一个随机Z
- 设置PK = (gZ / PK’)1/C
经过更多算术运算，您可以看到Z将验证为PK的有效证明。但由于我们不知道PK’的秘密密钥，我们也不知道PK的秘密密钥！这是一个伪造的证明。根据具体应用，这可能非常有问题，因为它允许您为与另一方公钥PK’相关的密钥创建虚假证明。
通过调整计算C的方式可以避免此问题。通过设置C = Hash(B, PK)或C = Hash(B, PK, g)将完全避免这些问题。这些被定义为强Fiat-Shamir变换。
一个非常类似的问题在瑞士投票系统中被发现。在这个系统中，设计目标之一是允许可验证的选举结果。为此，ZK方案产生解密证明，证明加密的投票解密为正确的结果。然而，在实现此方案时，只有部分证明者的输入被提供给哈希函数（即，未使用强Fiat-Shamir变换），并且证明者能够创建虚假证明。在这种情况下，这意味着有效投票可以被更改，使其不被计数，这对使用此类方案的选举具有明显的影响。
结论
总之，Fiat-Shamir变换通过计算证明者输入的哈希函数，将交互式ZK证明转换为非交互式证明。在实践中，这可能导致非常微妙但危险的错误。如有疑问，请使用强Fiat-Shamir变换，并确保证明者输入的每一部分都放在哈希函数内！
如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News