[译]对于 zk-SNARKs 运行的简介 #59
Comments
|
2 similar comments
|
|
{{ message }}
Labels
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
在过去十年中，普适的简洁零知识证明或许是密码学领域最有影响力的发展方向之一，通常简称为 zk-SNARKs（zero knowledge succinct arguments of knowledge）。zk-SNARKs 可以让你为执行的计算生成一些证明（proof），虽然这些证明的生成可能会耗费非常多的算力，但是却可以被很快地验证。并且这些证明还拥有“零知识”的特性，即证明中会隐藏计算中的输入信息。
举个例子，你可以给出一个关于你确实知道某个密码数字的证明：你会把这个数字加到字符
cow后面，然后执行 100 万次 SHA256 哈希，最终结果会以0x57d00485aa开头。在 zk-SNARKs 的应用场景里，验证者可以以远比执行 100 万次哈希快的时间验证你是否确实知道你所说的密码数字，并且该数字不会暴露给验证者。在区块链中，zk-SNARKs 有两个非常有用的应用场景：
不过 zk-SNARKs 是非常复杂的。在 2014 - 2017 年间，它还仅仅只是被称为“魔法数学（moon math）”。不过好消息是，此后随着人们的研究越来越深，它的协议也被优化得越来越简单。这篇文章将会在只要求读者拥有中等水平的数学知识的前提下，简单叙述 zk-SNARKs 是如何工作的。
我们将重点关注可扩展性方便。在解决了可扩展性的问题后，隐私性的问题也会跟着迎刃而解，我们将会在文章的最后再讨论隐私性。
为什么 zk-SNARKs “必须”是复杂的
让我们回到刚才的例子：我们有一个密码（
cow+密码数字），我们将其执行一次 SHA256 ，然后将哈希结果再哈希 99,999,999 次，得到了最终结果，记录下起始的哈希。计算量非常之大。一个“简洁的（succinct）”证明意味着：随着生成证明的计算量不断增大，验证这个证明所需的计算量只会相对缓慢增大。所以，如果我们想要生成一个“简洁的“证明，那么我们肯定不能要求验证者去做上述同样次数的哈希。所以验证者应该只需要窥探到完整计算的一部分，而不是所有步骤。
一个能自然而然想到的方法就是随机抽样验证：我们从 100 万次哈希中抽样出 500 次，然后验证哈希结果，如果都是正确的话，那么我就假设其余的计算都是正确的。
通过 Fiat-Shamir 变换，上述过程可以变成一个非交互式（non-interactive）的证明：验证者提供计算结果的默克尔树根，基于这颗默克尔树，伪随机地（pseudorandomly）选择 500 个索引值（抽样出其中 500 次计算），然后要求提供结果默克尔树中，这 500 个索引值对应的默克尔证明。其中的关键点是，证明者在给出默克尔树根前，不能够预先知道抽样的索引值。如果证明者在给出默克尔树根后还想要进行欺诈，那么改变默克尔树中的叶子值的话，提交的默克尔树根就会对应不上。
不幸的是，这样简单的进行随机抽样检查计算过程，有一个致命的缺陷：这样的计算本质上是脆弱的。如果欺诈者在证明的计算过程中修改了一个比特，那么一开始就会生成一个完全不同的结果（译者注：在上述例子中，就是一开始就会给出一个完全不同的默克尔树根）。随机抽样的验证者是大概率验证不出的（译者注：例如欺诈者只修改一百万步哈希计算中的一步的计算结果，那么随机抽样 500 次将很难命中，如下图所示）。
这正是 zk-SNARKs 协议需要解决的问题之一：如何让一个验证者在不验证所有计算步骤的前提下，验证每一步计算都是正确的。
多项式
多项式是拥有如下格式的一种特殊代数表达式：
是有限个 c * x^k 的累加。
多项式包含许多特性。不过此处我们仅关心其中一种：多项式可以在一个数学表达式中包含无限的信息（因为多项式中的累加项是无限的）。例如上述的第四个多项式例子中，包含了 816 个 tau ，并且如果需要包含更多，也是能很轻松做到的。
更进一步，一个多项式之间的等式，可以代表无限多个对应数字的等式。例如，等式：A(x) + B(x) = C(x) 。如果这个多项式等式成立，那么以下等式也同样成立：
同样也可以带入到坐标系中。你可以把所有待检查的数字都组装进一个多项式中。举个例子，你想要检查：
你可以使用拉格朗日插值法将一个点值表示的多项式，例如 A(x) 在 (0, 1, 2, 3) 处值为 (12, 10, 15, 15) ，B(x) 在 (0, 1, 2, 3) 处值为 (1, 8, 8, 13) ，转换为系数形式，具体表示如下：
这三个多项式等式是完全符合上述图（3）等式的。
多项式之间的比较
你可以使用同一个多项式，来检查多项式在连续输入值之间输出结果的关系。例如，你想检查的是：对于一个多项式 F ，x 取值范围在整数 {0,1,...98} ，多项式满足 F(x + 2) = F(x + 1) + F(x) （所以如果 F(0) = F(1) = 1 ，那么 F(100) 就是第 100 个斐波那契数）。
对于给出的多项式来说，由于 x 的取值可能不在 {0,1,...98} 之间，那么 F(x + 2) - F(x + 1) - F(x) 可能也就不一定为零。所以，我们需要更进一步。一般来说，如果一个多项式 P 在 S = {x1, x2, ... xn} 处等于零，那么它就可以被表示为 P(x) = Z(x) * H(x) ，其中 Z(x) = (x - x1) * (x - x2) * .... * (x - xn) ，并且 H(x) 也是一个多项式。换句话说，这个多项式可以表示成，在于其为零值的点的 (x - xn) 的乘法累计结果与另一个多项式的乘积。
对于多项式长除法（long division）有一个很好的推论：因式定理。我们知道，当我们将 P(x) 除以 Z(x) 时，我们会得到一个商 Q(x) 和一个余数 R(x)，即 P(x) = Z(x) * Q(x) + R(x)，此处的 R(x)（由于是余数）一定是比 Z(x)（由于是被除数）小的。由于我们知道 P 在取值范围 S 上等于 0 ，所以在取值范围 S 上，R(x) 也必须等于 0 。所以在取值范围 S 处，Q(x) = H(x) 。
回到我们上述的满足斐波那契数的多项式 F 上，那么我可以说服你，我提供的 F 确实是满足的条件的，如果在 P(x) = F(x + 2) - F(x + 1) - F(x) ，在我提供的以下 H(x) 和 Z(x) 等式下，为零：
至此为止，我们把一个有 100 步的计算（即需要计算出第 100 个斐波那契数）组装进入了一个多项式等式。所以基于这个技术，你可以将包含任意大数字的任意步骤计算放入多项式中。
所以，有比逐个检查因子更快的验证方法吗？
多项式承诺
答案就是：多项式承诺。我们可以将多项式承诺理解为多项式的“哈希”。你可以通过检查它们“哈希”间的等式，来检查两个多项式是否相等。不同的多项式承诺类型，会提供不同的可检查等式类型。
对于大多数多项式承诺类型，你都可以通过它们进行如下检查（com(P) 即指多项式 P 的承诺）：
我们需要将上述这些等式特性糅合在一起使用。如果你可以验证相加或相乘，那么你就可以验证给定点的值：P(w) = z ，你可以构造 Q(x) = (P(x) - z) / (x - w) ，然后检查 Q(x) * (x - w) + z = P(x) 。如果 Q(x) 存在，那么 P(x) - z = Q(x) * (x - w) ，这就意味着 P(x) 在 w 处 等于 z 。
Schwartz-Zippel 引理表示， 如果一些多项式等式在某些随机点验证结果都是真，那么几乎在所有点都会是真。所以，我们可以使用如下的交互来验证 P(x + 2) - P(x + 1) - P(x) = Z(x) * H(x) ：
根据上文所表述的，我们可以通过 Fiat-Shamir 变换来让上述过程变成非交互式：证明者自己通过
r = hash(com(P), com(H))计算出r（hash 可以是任意哈希函数），所以当证明者在选择P和H时，他并不知道r（即是通过哈希生成的“随机值”），所以也没办法通过“挑选”P和H使之符合某个r。小结
多项式承诺是如何工作的
目前主要有三种多项式承诺的主流方式：bulletproofs, Kate 和 FRI。
简单描述多项式承诺的工作方式
在我观念中，其中最完全容易理解的是 FRI （如果你把椭圆曲线对当作“黑盒”的话，Kate 也会相对比较容易理解）。
以下是 FRI 是如何工作的简化版本（真实的协议中，会有许多技巧和优化，此处都会省去）。假设有一个阶数小于 n 的多项式 P 。P 的多项式承诺，就是其在一系列点上（例如 {0, 1, 2...8n-1}，尽管这些并不是最优系数）计算结果作为叶子的默克尔树的树根。现在，我们需要添加一些额外的东西来证明这一系列叶子计算结果的确来自于一个阶数小于 n 的多项式。
我们假设多项式 Q 只包含多项式 P 中的偶数位因子，多项式 R 只包含多项式 P 中的奇数位因子。那么如果 P(x) = x^4 + 4 * x^3 + 6 * x^2 + 4 * x + 1，那么 Q(x) = x^2 + 6 * x + 1 ，R(x) = 4 * x + 4 （注意分解的多项式中，只有因子被继承了，阶数会被重新更新，范围是 (0...n/2]）。
所以 P(x) = Q(x^2) + x * R(x^2)。
我们会要求证明者提供 Q(x) 与 R(x) 的默克尔证明。然后生成一个随机数 r ，并且要求证明者提供一个“随机线性组合（random linear combination）”：S(x) = Q(x) + r * R(x) 。
基于之前提供的默克尔树根作为种子，我们伪随机地生成一个大的索引集合。然后要求证明者提供这些索引在 P，Q，R 和 S 中值得默克尔证明。对于这些索引坐标，我们检查：
如果我们做足够多次的检查，那么我们会相信，可能就最多 1% 的概率，S(x) 的提供值可能会和“预期”值不同。
值得注意的是，Q 与 R 的最高阶都小于 n/2 。由于多项式 S 是 Q 和 R 的一个线性组合，所以 S 的阶数也小于 n/2 。反过来说，如果我们能证明 S 的阶数小于 n/2 ，并且随机选择的 r 阻止了证明者可以选择 Q 和 R 来隐藏最高阶的因子。所以 Q 和 R 的最高阶也必须小于 n/2 ，然后由于 P(x) = Q(x^2) + x * R(x^2) ，所以 P 的最高阶也小于 n 。
所以，我们使用 S 继续重复上文的交互式游戏，不断的“减小”我们关心的多项式的阶数，直至它的阶数能被直接检查：
在上述例子中，Bob 仅仅是一个“抽象”，用于演示协议。现实中，Alice 会仅靠自己生成完整的证明，并且我们使用 Fiat-Shamir 变换来防止她欺诈：我们根据截至该点为止生成的证明的哈希，来随机选择采样点。
所以一个简化版的 FRI 承诺将会包含：
上述过程的每一步，都会产生一点“误差”，但是当你把这些步骤放在一起时，误差已经足够低到你可以证明 P(x) 与另一个阶数小于 n 的多项式存在 80% 的相似。这在我们的使用场景中，已经足够了：如果你想在 zk-SNARKs 中作弊，你需要使用一个伪造值生成多项式承诺，经过上述过程后，最终的记过将会很不同。
另外，你可以在对数时间内检查 FRI 承诺中的所有数字，对于很大的多项式来说，承诺的大小会比本体小很多。
在检查多项式承诺之间的等式时（例如，A(x) + B(x) = C(x) ，并且对 A，B，C 进行多项式承诺），仅需随机选择一系列的索引，然后要求验证者提供默克尔证明。
上述的简化协议，在执行效率上是低下的，有一系列的代数技巧可以用于提高效百倍效率，如果你想要在区块链交易验证中使用，那么你应该去了解它们。例如，当你使用某些技巧来选择运算点时，Q 和 R 都不是必要的，你可以从 P 的计算过程中重组出 Q 和 R 的计算过程。
有限域
在前文中，有一个隐藏的假设：一个多项式的每一步独立的“计算”都是小的。如果我们面对一个很大的多项式，这个假设显然就不成立了。例如我们最早的一个多项式例子之一：628 * x^271 + 318 * x^270 + 530 * x^269 +...69x + 381，然后计算 x = 1000 处的值，计算量是非常大的。在实际的实现中，这些计算都不会是这些真实的数字进行“常规”的运算。而是会使用取模运算。
We redefine all of our arithmetic operations as follows. We pick some prime "modulus" p. The % operator means "take the remainder of": , , etc (note that the answer is always non-negative, so for example ). We redefine
我们将我们需要进行的所有计算重新按如下定义。我们取一些素数“模” P ，% 符号表示取模：15 % 7 = 1，53 % 10 = 3 等等。注意，结果一定是非负的（-1 % 10 = 9）。我们重新定义：
如果 p = 7 ，那么：
分配率也依然有效：(2 + 4) * 3 与 2 * 3 + 4 * 3 结果都为 4 。甚至 (a^2 - b^2) = (a - b) * (a + b) 也依然为真。
除法是最复杂的。由于我们想要取模的结果是整数，而整数之间相除的结果经常不为整数。我们使用了费马小定理来绕过这个问题：对于任何非零的 x < p ，x^(p - 1) % p = 1。这意味着，对于 x^(p - 2)，再乘以一次 x ，那么取模结果就会为 1 。所以我们可以说 x^(p-2) （该数是一个整数）的取模结果为 1/x 。你也可以通过扩展欧几里得算法来实现一个更快的除法取模操作，这里有这个算法的 python 实现。
通过取模运算，我们创建一套新的计算系统。并且这与传统数学一样，都是自洽（self-consistent）的。所以我们可以像讨论传统数学中的多项式计算一样，讨论这套新系统中的计算。加密学领域的人喜欢使用基于取模运算的数学（更广泛的说，“有限域”），因为任何取模运算的结果值，都是有上限的。无论你做什么，结果都不会“逃出”一定的集合。在有限域中，即使运算一个 100 万阶的多项式，结果同样也不会超出上限。
结合到多项式运算中
我们想证明：对于多项式 P ，0 <= P(n) <= 2^64 ，同时不泄露 P(n) 的具体值。这种场景在区块链交易中很常见，比如你想证明经过一笔交易后，你的余额是非负的，但是你不想透露具体的余额。
我们可以构建一个包含如下声明的证明（简单起见假设 n = 64）：
后两个声明可以通过“纯”多项式来表示：
随着 P(i) 的执行，结果集合将不会不断增大。如果 P(4) = 13 ，那么到 4 时，结果集合就是 {0, 1, 3, 6, 13}。在二进制中，1 是
1，3 是11，6 是110，13 是1101。所以，P(x + 1) = P(x) * 2 + R(x) 中，只要 R(x) 属于 {0, 1}，结果就会不断地往最后添加 1 比特。任何在 0 <= x <= 2^64 的数通过上述的 64 步构建出来，超过这个范围则不行。隐私
一个问题是，为什么我们知道 P(x) 和 R(x) 的多项式承诺，不会“泄露”有关 P(64) 的信息呢？
好消息是：这些证明都是小型的证明，但是都对应着一些大数据量和复杂的计算。通常，这些证明的体量都没有大到能够泄露任何有用的数据。但是我们有办法把泄露的可能减低为 0 吗？幸运的是，我们可以。
一个常用的技巧是在多项式中加入一些“软糖因子（fudge factors）”。当我们选择 P 时，会在多项式加入一些小的 Z(x) ：P'(x) = P(x) + Z(x) * E(x) ，E(x) 是一些随机值。这么做并不会影响声明的正确性，但是这会为多项式承诺添加一些额外的噪音。在 FRI 中，上述选取的随机值，不能在计算将要发生的点上（例如 {0...64}）。
总结
原文链接
https://vitalik.ca/general/2021/01/26/snarks.html
The text was updated successfully, but these errors were encountered: