原文标题：Anapproximateintroductiontohowzk-SNARKsarepossible
原文作者：VitalikButerin
原文来源：vitalik.ca
编者注：说到过去十年来诞生的最强密码学技术，肯定免不了提及零知识证明(zeroknowledgeproof)。在区块链领域中，它们有两大应用场景：可扩展性和隐私。zk-SNARK作为其中一种zkp技术，在近几年来也得到了较大的突破，以太坊上出现了诸如zkSync、Scroll、Hermez等此类使用zk-SNARK证明的通用扩容解决方案。
然而，实现zk-SNARK并不简单，因为对某个声明生成了zk-SNARK证明之后，验证者需要以某种方式检查计算中的数百万个步骤。多项式承诺就是在这里发挥其作用，即可以将计算编码为多项式，然后使用一种特殊类型的多项式“哈希”(多项式承诺)，以允许验证者在极短的时间内验证多项式等式，即便这些计算背后的多项式规模无比大。
在本文中，Vitalik介绍了zk-SNARK技术的工作原理和难点，然后解释了多项式以及多项式承诺如何让zk-SNARK的实现更加高效。
特别感谢DankradFeist、KarlFloersch以及Hsiao-weiWan的反馈和校对。
过去十年来诞生的最强密码学技术大概要数通用简洁零知识证明，通常称为zk-SNARK。zk-SNARK允许你生成一个证明(这个证明是针对一些运算得出的特定输出，可用于对该运算的验证)，通过这种方式，即使底层计算十分耗时，该证明也可以被快速验证。“ZK”为证明新增了一个额外特性：证明可以隐藏计算的某些输入。
例如，您可以对以下声明生成一个证明：“我知道一个秘密值，如果你将数字添加到挑选的单词cow的末尾，然后对其进行1亿次SHA256哈希运算，那么输出的哈希值以0x57d00485aa开头”。验证者验证该证明的耗时可远小于自行进行1亿次哈希运算的耗时，而且证明也不会泄漏秘密值。
在区块链领域中，该技术有两大应用场景：
可扩展性：如果一个区块的验证十分耗时，某个人可以验证区块并生成一个证明，而其他人只需快速地验证证明即可
隐私：你可以证明你有权转移某些资产，而不透露该资产的来源。这不会对外泄漏交易双方的信息，确保了交易的安全性。
然而，zk-SNARK是相当复杂的；实际上，就在2014-17年，它们还常被称为“月亮数学”。好消息是，从那时起，协议愈发简化，我们对它们的理解也愈发深入。本篇博客将试图以一种数学水平普通的人能理解的方式来解释ZK-SNARKs的工作原理。
动态 | 2万枚ETH从币安交易所转至另一未知地址:据Whale Alert监测，2万枚ETH从币安交易所（0x3f5开头）转至另一未知地址（0x4d8开头）。[2019/7/26]
注意，我们将聚焦于可扩展性；一旦有了可扩展性，这些协议的隐私性就相对容易实现，因此我们将在最后回归这个主题。
为什么ZK-SNARK“会”很难
以开头例子为例：我们有一个数字，我们计算该数字的SHA256哈希，然后重复做9999999次，最后我们检查输出的开头。这里面的计算量特别大。
一个“简洁”证明指的是证明大小和验证耗时的增长远慢于需验证计算量的增长。如果我们想要一个“简洁”证明，我们就不能要求验证者在每轮哈希中做一些运算。相反，验证者必须以某种方式检查整个运算过程，而不必窥视运算过程中的每个部分。
有一种自然的技术就是随机抽样：让验证者只在500个不同的地方检查运算的正确性，如果所有的500个检查都通过了，那么认为运算过程的其余部分也大概率没问题？
该流程甚至可以通过使用Fiat-Shamir启发式转化为非交互式证明：证明者计算运算过程的默克尔根，基于默克尔根伪随机地选取500个索引，并提供对应的500个默克尔分支。核心思想是证明者并不知道将要揭示哪些分支，直到他们已经对数据生成了“承诺”。如果恶意证明者在了解到需要检查哪些索引后试图篡改数据，那么这会改变默克尔根的值，而这将导致一组新随机索引被选出，这将需要再次去篡改数据…让恶意证明者陷入无休止的循环中，无法达成目的。
但不幸的是，简单地随机抽查运算过程存在一个致命的缺陷：运算过程本身并不健壮。如果恶意证明者在计算过程中的某个位置翻转一个比特，可以导致一个完全不同的结果，而随机抽样验证者几乎永远不会发现。
只需一次故意的插入错误，就会导致计算得出完全错误的结果，而这几乎不会被随机检查所捕获。
如果要提出一个zk-SNARK协议，那么很多人会走到上面这步，然后陷入困境，最终放弃。不单独查看每个计算片段的情况下，验证者究竟如何才能够校验每个计算片段？事实证明，有一个绝妙的解决方案。
多项式
多项式是一类特殊的代数表达式，具有以下形式：
x+5
x4
x3
+3x2
声音 | 赵长鹏回应币安退市公告：与其每天退市 不如一次性完成:币安发布公告称将下架BCN，CHAT，ICN，TRIG后，推特网友在下面评论称：“就这些了？记住bittrex发生了什么事，或者说我们的交易是安全的吗？”赵长鹏回复称：“对于我们来说，这是一个非常痛苦的决定，但是与其每天退市，不如一次性完成。”[2018/10/9]
+3x+1
628x271
+318x270
+530x269
+…+69x+381
也就是说，它们是有限个形式为cxk的项之和。
多项式有许多有趣的特性。但这里，我们将聚焦于多项式的一个特性：多项式是一个可以包含无限信息量的单一数学对象上。面的第四个示例包含tau的816位的信息，而且我们能够很容易地想象出一个包含更多信息量的多项式。
此外，多项式间的单个等式就能够表示无限个数间的方程。例如，考虑等式A(x)+B(x)=C(x)。如果该等式是正确的，那么下面也是正确的：
A(0)+B(0)=C(0)
A(1)+B(1)=C(1)
A(2)+B(2)=C(2)
A(3)+B(3)=C(3)
可以类推到每个可能的下标。甚至，你可以构造特地表示一组数字的多项式，这样你就可以一次性地检查众多等式。例如，假设您想检查：
12+1=13
10+8=18
15+8=23
15+13=28
您可以使用一个名为拉格朗日插值的方法来构造多项式：A(x)在某些特定下标集合，B(x)在相同下标上的输出为(1，8，8，13)，如此类推。准确地说，以下是相应的多项式：
用这些多项式校验等式A(x)+B(x)=C(x)相当于同时校验上述四个等式。
将多项式与自身进行比较
甚至，你可以用一个简单的多项式等式来校验相同多项式的大量相邻取值的关系。这稍微更进一步。假设您想校验，对于给定的多项式F，在整数范围{0,1…98}内满足F(x+2)=F(x)+F(x+1)。
作为多项式，F(x+2)?F(x+1)?F(x)不会正好为零，因为它在x={0,1…98}范围外的取值是不受限的。但我们可以做一些巧妙的处理。一般而言，有这样一条定则：如果多项式P在某些集合S={x1，x2…xn}上的取值为零，那么可以表示为P(x)=Z(x)?H(x)的形式，其中Z(x)=(x?x1)?多项式的倍数。
声音 | 币安赵长鹏发推安抚用户：资金安全 不信谣 不传谣:赵长鹏刚刚发推称，资金安全，在交易应很快恢复，在此之前，请用户们不信谣，不传谣。[2018/7/4]
为什么会这样？这其实是多项式长除法的一个巧妙的推论：因式定理。我们知道，当用Z(x)除P(x)时，我们将得到商Q(x)和余数R(x)，满足P(x)=Z(x)?Q(x)+R(x)，其中余数R(x)的阶严格小于Z(x)。因为我们知道多项式P在集合S上的取值为零，这意味着多项式R在集合S上的取值也必须为零。因此，我们可以通过多项式插值简单地计算R(x)，因为它是一个阶至多为n?1的多项式，而我们知道其中的n个取值。使用上述所有零值进行插值得到零多项式，因此，R(x)=0，H(x)=Q(x)。
回到我们的例子上，如果我们有一个编码了斐波那契数的多项式F（因此，在x={0,1…98}上满足F(x+2)=F(x)+F(x+1)，那么我可以通过证明多项式P(x)=F(x+2)?F(x+1)?F(x)在该范围的取值为零来向你证明F确实满足该条件：H(x)=(F(x+2)?F(x+1)?F(x))/Z(x)，其中Z(x)=(x?0)?(x?1)?…?(x?98).
你可以自行计算Z(x)，检查该等式，如果检查通过，那么F(x)的确满足条件！
现在，退一步，留意一下我们做了什么。我们将一个步长100的计算转换为单个多项式等式。当然，证明第N个斐波那契数的取值意义不大，尤其是因为斐波那契数具有闭合形式。但你可以使用完全相同的底层技术，只需一些额外的多项式和更复杂的等式，就可以对任意步长的任意计算进行编码。
现在，如果存在一种使用多项式校验等式的方法，而且这种方法比检查每个系数快得多…
多项式承诺
再一次，事实证明，这样的方法是存在的：多项式承诺。最好把多项式承诺看作一种对多项式进行“哈希”的特殊方法，该哈希拥有额外特性，即你可以通过校验多项式哈希间的等式来校验多项式间的等式。不同多项式承诺方案在适用等式类型上有着不同的特点。
下面是一些常见的例子，您可以使用各种多项式承诺方案：
相加：给定com(P)、com(Q)和com(R)，检查是否满足P+Q=R
相乘：给定com(P)、com(Q)和com(R)，检查是否满足P?Q=R
在某个点上求值：给定com(P)、w、z和一个补充证明Q，验证P(w)=z
值得注意的是，这些原语可以相互组合。如果支持加法和乘法，那么你可以这样计算：为了证明P(w)=z，你可以构造出Q(x)=
/，然后验证者可以验证:
这行得通是因为如果存在这样一个多项式Q(x)，那么P(x)?z=Q(x)?(x?w)，这意味着P(x)?z在w处等于零，因此P(x)在w处等于z。
如果你能计算出某点的取值，那么你可以进行各种校验。这是因为有一个数字定理表明：大体上，如果一些包含了一些多项式的等式在一个随机选择的下标下成立，那么对多项式整体而言等式基本为真。因此，如果我们只有一个证明某点取值的机制，那么我们就可以通过一个交互式游戏进行验证，如我们的方程P(x+2)?P(x+1)?P(x)=Z(x)?H(x)：
正如前面提到的，我们可以使用Fiat-Shamir启发式使其转化为非交互式：证明者可以令r=hash(com(P),com(H))并计算r。证明者不能通过挑选只“符合”特定r的P和H来进行“欺诈行为”，因为他们在选取P和H时不知道r！
快速回顾
ZK-SNARK很难，因为验证者需要以某种方式检查计算中的数百万个步骤，而无需直接地检查每个单独的步骤。
我们通过将计算编码为多项式来解决这个问题。
单个多项式可以包含无限大的信息量，而且单个多项式表达式可以代表无限个数间的方程。
如果你可以验证多项式等式，那么你同时在隐式地验证所有的数值等式。
我们使用一种特殊类型的多项式“哈希”，称为多项式承诺，以允许我们在极短时间内验证多项式等式，即使背后的多项式规模非常大。
那么，这些神奇的多项式哈希是如何工作的？
目前有三种被广泛使用的主流方案：bulletproofs,KateandFRI。
这里是DankradFeist对Kate承诺的描述：https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html
这里是curve25519-dalek团队对bulletproofs的描述：https://doc-internal.dalek.rs/bulletproofs/notes/inner_product_proof/index.html，而这里是我的图解：https://twitter.com/VitalikButerin/status/1371844878968176647
这里是对FRI的描述，我写的…：https://vitalik.ca/general/2017/11/22/starks_part_2.html
哇，哇，别紧张。试着简单地讲解其中一个，不要把我带到更可怕的链接上
老实说，它们没有那么简单。这就是为什么所有的这些数学理论直到2015年左右才真正崛起的缘故。
请？
在我看来，FRI是最容易理解透的。
以下是FRI工作原理的简化版。假设你有一个阶小于n的多项式P。对P的承诺是某组预选下标取值的默克尔根。现在我们需要额外添加一些东西来证明这组取值来自一个阶小于n的多项式。
我们要求证明者提供Q(x)和R(x)的Merkle根。然后，我们生成一个随机数r，并要求证明者提供一个“随机线性组合”S(x)=Q(x)+r?R(x)。
我们伪随机抽样了一大组下标，并要求证明者在这些下标处提供P、Q、R和S的Merkle分支。在每个提供的下标处，我们校验：
如果我们做了足够校验，那么我们可以确信S(x)的“预期”值与“提供”值最多是不同的。
从这里开始，我们简单地用S重复上面的游戏，逐步“降低”我们关心的多项式的阶，直到多项式的阶低到我们可以直接校验的程度。
和前面的示例一样，这里的“Bob”是一个抽象概念，对密码学家在思维上论证协议非常有用。事实上，Alice自己生成了完整证明，为了防止她作弊，我们使用Fiat-Shamir：我们根据此前证明中生成的数据的哈希随机选取每个样本的下标或r值。
一个对P完整的“FRI承诺”包括：
流程中的每步都可能会引入一些“误差”，但如果您进行了足够多的检查，那么总误差将低到你可以证明P(x)在至少80%的下标处等于一个阶小于n的多项式。这足以满足我们用例的需求：如果你想在zk-SNARK中作弊，你需要对少数值进行多项式承诺，其多项式的取值会在多处不同于真正阶小于n的多项式，因此任何对其进行FRI承诺的尝试都会失败。
此外，您仔细检查一下，FRI承诺中对象的总数和大小是O(log阶)，因此，对于大型多项式，承诺实际上比多项式本身小得多。
为了检查这类不同多项式承诺间的等式，只需简单地随机选择很多下标，要求验证者提供在每个多项式的这些下标处的Merkle分支，并验证等式在每个下标处成立即可。
上面描述的是一种效率极低的协议；有很多代数技巧可以将协议效率提高约100倍，如果你想要一个切实可行的协议，比如在区块链交易中使用，你需要使用这些技巧。特别是，例如，Q和R实际上不是必要的，因为如果你非常聪明地选择取值点，你可以直接从P的取值重构出所需Q和R的取值。但是上面的描述应该足以让你确信多项式承诺从原理上是可行的。
有限域
因为数字的“回环”方式，模运算有时被称为“时钟数学”
通过模运算，我们创造了一个全新的算术系统，它和传统算术一样是自洽的。因此，我们可以讨论该域中的所有同类结构，包括我们在“常规数学”中讨论的多项式。密码学家喜欢使用模数学，因为任何模运算结果的大小都会有界-无论你做什么，值都不会“超出”集合{0,1,2…p?1}。即使计算有限域中一个一百万次多项式，也不会得出一个集合以外的值。
将计算转化为一组多项式等式更具意义的例子？
隐私
但这里有一个问题：我们怎么知道对P(x)和R(x)的承诺不会“泄漏”信息？
这里有些好消息：这些证明是对大量的数据和计算生成的小证明。因此，一般来说，证明往往不够大，只能暴露一点点信息。但我们能从“只有一点点”推进到“零”吗？幸运的是，我们可以。
在这里，一个相当通用的技巧是往多项式添加一些“模糊因子”。当我们选定P时，将Z(x)的小倍数加到多项式中。这并不会影响命题的正确性，但它可以在承诺中添加足够多的额外“噪声”，使得任何余下信息不可恢复。此外，对于FRI，重要的是不要对计算发生范围的随机点进行采样。
我们能再回顾一下吗？？
最优秀的三类多项式承诺是FRI、Kate和bulletProof。
Kate在概念上是最简单的，但它依赖于非常复杂的椭圆曲线配对“黑盒”。
FRI很酷，因为它只依赖哈希；它的工作原理是将多项式逐渐归约为阶越来越低的多项式，并在每步进行随机抽样检查，使用Merkle分支来证明等价性。
为了防止单个值大小的膨胀，我们不在整数上做算术运算和多项式运算，而是在有限域上做所有事情
多项式承诺天然支持隐私保护，因为生成的证明已经比多项式小得多了，因此多项式承诺只能暴露多项式中一点点信息。但我们可以往多项式添加一些随机性，将暴露的信息从“一点点”减少到“零”。
哪些问题仍在研究当中？
优化FRI：已经有很多涉及精心挑选的取值域的优化，“DEEP-FRI”，以及一系列其他让FRI更高效的技巧。Starkware及其他人正在研究这块。
将计算编码为多项式的更佳方法：找出将涉及哈希函数、内存访问和其他特征的复杂计算编码为多项式等式的最高效方法仍是一个挑战。在这方面已经取得了很大的进展（例如，见PLOOKUP)，但我们仍需更多的进展，特别是如果我们想将通用虚拟机执行编码为多项式的话。
增量可验证计算：如果随着计算继续能够高效地“扩展”证明，那就太好了。这在“单证明者”情况下很有价值，而且在“多证明者”的情况下也很有价值，特别对于不同参与者创建区块的区块链而言。最近一些在这方面的工作，请参见Halo。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。