工程师零知识证明：导论

在这篇文章中，我们将讨论zkSNARK，这是一种特殊的零知识证明品牌，在区块链领域变得越来越重要。

我们将介绍它们是如何使用的以及它们有什么用处，并且我们将看一下名为Circom的snark构建语言中的基本zkSNARK。

我们假设您以前遇到过素数域，并且记住了它们的基本属性。如果您可以在\(\mathbb{F}_7\)中计算\(4\cdot5\等效v6\)，那么您就可以开始了。

零知识协议是一种协议，它允许您证明您知道某些特定的数学事实，而不会透露有关该事实本身的任何信息。在零知识协议中生成的证明称为零知识证明。

我们可以为其创建零知识证明的一些“数学事实”示例包括：

图的三色知识(即，我知道这个众所周知的图的三色，我将证明我知道它，而不向您展示着色)。

关于模(P)的某些剩余的离散对数(即给定公共生成元(g\)、公共模\(p\)和一些剩余\(y\)的知识，我知道\(x\)使得\(g^x\等价y\)模\(P))。

零知识协议的想法乍一看可能是自相矛盾的：如果不向你展示我知道的东西，我怎么能证明我知道什么呢？然而，事实证明，我们实际上一直在使用零知识协议！例如，熟悉的工具，如数字签名，实际上是零知识证明。通过签署一条消息，我证明我知道与广为人知的公钥相对应的私钥，但我不会透露有关私钥本身的任何信息。事实上，公钥加密之所以有效，是因为它是零知识协议；如果签名泄露了有关您的私钥的信息，那么恶意攻击者将能够通过分析您的签名并恢复您的私钥来冒充您。

稍微正式一点，假设您已经为一些公知函数\(f\)和一些秘密输入\(\cdot\)计算了\(f(\cdot)=y\)。函数\(f\)的零知识协议将允许您向其他人证明您知道\(f\)的秘密输入，该秘密输入将导致\(y\)，而不会泄露此秘密输入\(\cdot\)。

正如我们上面提到的，ZKP是允许您证明特定数学事实知识的协议：离散对数、私钥知识、三色知识等。然而，重要的是要注意，早期的ZKP当时只允许您证明一种数学事实。也就是说，密码学家开发了一种可用于证明离散对数知识的协议，另一种可用于证明三色知识的协议，以及另一种用于数字签名的协议。但是，如果我们想要为任意数学函数生成零知识证明呢？例如，如果我想要一个零知识协议，该协议允许我证明我知道SHA256散列输出的前映像，该怎么办？如果对于每个用例，我都必须去找密码学家并要求他们为我定制一个新协议，那就很难处理了。

ZkSNARK解决了这个问题。ZkSNARK是一个小工具，可用于为任何数学函数生成ZKP。基本上，您将函数\(f\)的“代码”提供给zkSNARK，snark创建一个允许您为\(f\)生成零知识证明的协议。

例如，假设我们有一个假的“散列”函数\(h(X)=x^3-x+7\)，我们想要为其生成零知识证明。首先，我们可以使用zkSNARK为\(h\)生成ZKP。然后，我们可以使用生成的ZKP来证明诸如“我知道一个值\(\CDOT\)使得\(h(\CDOT)=67\)”之类的声明-而不会揭示\(\CDOT\)。ZkSNARK还保证这个过程是“简洁的”和“非交互的”：我们可以在线性时间内创建此证明，其他人可以在恒定的时间内验证它，而不需要向我们(证明者)提出额外的问题。这些属性共同构成了zkSNARK：零知识简明、非交互的知识论证。

这些属性使得snarks对于区块链应用程序很有用，在区块链应用程序中，用户可以在本地创建校样，然后上传简短的校样在智能合同内进行恒定时间验证，而在智能合同中，计算成本很高。

“黑暗森林”的一个核心技术就是密码“战争的迷雾”。战争的迷雾确保您不会自动知道所有玩家、行星和其他兴趣点在宇宙中的什么地方；您必须花费计算资源才能发现它们。这个机械师被zkSNARK固定住了。

在一个充满战争迷雾的宇宙中，所有玩家的位置都是私人的，彼此都不知道。这意味着玩家不会将他们星球的坐标上传到以太区块链，而以太区块链是可以公开检查的。取而代之的是，每个玩家都将其位置的散列上传到区块链。这确保了玩家保持对特定位置的“忠诚”，但也不能通过检查以太数据层来确定位置。

如果没有zkSNARK，就会有一个明显的攻击向量-如果玩家上传的随机字节串与真实有效的位置不对应，游戏的完整性就会被破坏。为了防止这种情况，黑暗森林要求玩家在每次移动时都提交zkSNARK，以确保玩家确实提交了与他们知道的有效坐标相对应的散列。

当玩家移动时，他们还被要求提交ZK证明，证明他们的移动是“有效的”-你不能移动太远或太快。如果没有zkSNARK，恶意玩家可以通过声称他们要移动的散列紧挨着他们要移动的散列来进行非法的“传送”移动，即使这两个位置实际上位于宇宙的两边。再一次，要求ZK证明让玩家保持诚实。打个比方，所需的ZK证明基本上告诉合同，“我在移动我的骑士；我不会告诉你我把我的骑士从哪里移动，或者我把它移动到哪里，但这个证据证明它确实是以合法的L型移动的。”

我们将在未来的一篇博客文章中更深入地研究黑暗森林的建设和史纳克！

就像我们上面提到的，snarks是接受一个函数并输出该函数的ZKP的小工具。那么，我们如何向snark“提供”函数呢？

Snarks函数用Circom语言编写为电路。下面是我们的“伪”散列函数\(h(X)=x^3-x+7\)的示例电路。

//file：Circuit it.Circom模板BadHash(){信号私有输入x；信号x_squared；信号x_cubed；信号输出x_squared<；==x*x；x_cubed<；==x_squared*x；out<；==x_cubed-x+7；}Component Main=BadHash()；

我们的zkSNARK接受这个电路，分析它，然后吐出一个证明密钥和一个验证密钥。证明密钥允许正在计算BadHash(X)=out的证明者生成他们确实知道out的前映像的证明。验证密钥允许任何人检查该证明以及OUT，并得出结论认为证明者确实使用已知的秘密输入诚实地执行了计算。

具体地说，假设证明者计算BadHash(4)=67。证明者将其证明与OUT=67一起发布给验证者；但是，他们不发布秘密输入x=4。此证明的验证者知道BadHash电路的源代码，并且还从证明者接收OUT=67和证明。然后，验证者可以检查证明，以验证证明者确实计算了一些有效的x、x_squared和x_cubed来得出out。但是，验证器不知道证明器使用的特定值(x=4，x_squared=16，x_cubed=64)-只知道这些值计算正确。

有两件事使斯纳克电路不同于我们习惯的正常“功能”。

首先，您会注意到BadHash只使用了三个操作：乘法、加法和减法。在基础级别，snark约束仅限于这些操作。像除法和模数这样的运算是有方法的，但它们最终都涉及到将运算分解为和。我们仅限于这些操作的事实是使Snark编程变得棘手的部分原因。

第二个挑战是，snark中的每个信号都是素数域的一个元素，所有操作都发生在该素数域中。这一点最明显的含义是，没有小数、分数、负数或大于77位的数字的本机概念。如果您想要它们中的一个，您必须将它们从小于p的正整数中提取出来。另一个含义是我们的运算符“绕回”：3-5的结果是p-2，这是一个77位的数字。质数足够大(254)，大多数情况下这都无关紧要，但偶尔也会导致微妙的正确性错误。

为了实际制作校样，我们使用了一个名为SnarkJS的库，该库由Jordan i Baylina和Iden3构建。SnarkJS使用您的电路生成JavaScript和Solidity格式的证明和验证码，以及协议参数和证明和验证密钥。这超出了这篇文章的范围，但是你可以在这里找到关于它的教程。

在下一篇文章中，我们将讨论snarks的执行模型，包括计算和约束之间的区别，以及如何进行除法和模运算等操作。