作者：VitalikButerin
原标题：《Zk-SNARKs:UndertheHood》
发表时间：2017年2月1日
这是解释zk-SNARKs背后的技术如何工作的系列文章的第三部分；以前关于二次算术程序和椭圆曲线配对的文章是必读的，本文将假设这两个概念的知识。还假设了zk-SNARK是什么以及它们做什么的基本知识。另请参阅此处的ChristianReitwiessner的文章以获得另一篇技术介绍。
在之前的文章中，我们介绍了二次算术程序，这是一种用多项式方程表示任何计算问题的方法，它更适合各种形式的数学技巧。我们还介绍了椭圆曲线配对，它允许一种非常有限的单向同态加密形式，可以让你进行相等性检查。现在，我们将从上次中断的地方开始，使用椭圆曲线配对以及其他一些数学技巧，以允许证明者证明他们知道特定QAP的解决方案，而无需透露任何关于实际解决方案。
本文将重点介绍Parno、Gentry、Howell和Raykova从2013年开始的Pinocchio协议；基本机制有一些变化，因此在实践中实施的zk-SNARK方案可能会略有不同，但基本原理通常保持不变。
首先，让我们进入我们将要使用的机制的安全性背后的关键密码假设：指数知识假设。
V神：ZK-EVM是以太坊Layer 1安全和验证过程的重要组成部分:金色财经报道，以太坊联合创始人“V神”Vitalik Buterin在其官方博客上发布文章《以太坊的多客户端理念将如何与ZK-EVM交互？》（How will Ethereum's multi-client philosophy interact with ZK-EVMs?），其中指出ZK-EVM将在未来发展成为以太坊Layer 1安全和验证过程的重要组成部分，但关键在于如何为零知识证明以太坊区块的正确性创建一个“多客户端”生态系统。V神建议采取开放的多个ZK-EVM，因为不同的客户端有不同的ZK-EVM实现，每个客户端可以在接受一个区块为有效之前等待与自己兼容的证明。此外，Vitalik Buterin还对人工智能最近的快速发展大加赞扬，他觉得人工智能的进步可以“加速”证明ZK-EVM实现的发展。“从长远来看，当然任何事情都有可能发生。也许AI会加强形式验证，使其可以轻松证明ZK-EVM实现等效并识别导致彼此之间差异的所有错误。”[2023/4/2 13:40:23]
基本上，如果你得到一对点P和Q，其中P*k=Q，并且你得到一个点C，那么除非C以某种方式从P“派生”出来，否则不可能得出C*k你知道的。这可能看起来很直观，但是这个假设实际上不能从我们通常在证明基于椭圆曲线的协议的安全性时使用的任何其他假设推导出来，因此zk-SNARK实际上确实依赖于比椭圆曲线密码学更普遍的基础更不稳定——尽管它仍然足够坚固，大多数密码学家都可以接受。
Cardano生态ZK-Rollup扩容项目Orbis宣布停止运营:11月24日消息，基于Cardano的二层ZK-Rollup扩容解决方案Orbis发推称，由于资金有限和不确定的条件，Orbis Labs无法继续建设，该项目已经停止。NFT已暂停，直至另行通知，届时将为核心ZK-Rollup解决方案制定后续计划。
Orbis表示正在制定一个长期的项目计划。目前Orbis Labs Github组织将保持开源，并对外部贡献者开放。[2022/11/24 8:04:13]
现在，让我们来看看如何使用它。假设有一对点(P,Q)从天上掉下来，其中P*k=Q，但没有人知道k的值是多少。现在，假设我提出了一对点(R,S)，其中R*k=S。那么，KoE假设意味着我可以得出这对点的唯一方法是取P和Q，并且将两者乘以我个人知道的某个因子r。还要注意，由于椭圆曲线配对的魔力，检查R=k*S实际上并不需要知道k-相反，你可以简单地检查e(R,Q)=e(P,S)。
让我们做一些更有趣的事情。假设我们有十对点从天而降：(P_1,Q_1),(P_2,Q_2)…(P_10,Q_10)。在所有情况下，P_i*k=Q_i。假设我随后为你提供一对点(R,S)，其中R*k=S。你现在知道什么？你知道R是一些线性组合P_1*i_1+P_2*i_2+…+P_10*i_10，其中我知道系数i_1,i_2…i_10。也就是说，要得到这样的一对点，唯一的方法就是取P_1，P_2…P_10的一些倍数并将它们相加，然后用Q_1，Q_2…Q_10进行相同的计算。
Bitfinex首席技术官：Tether正在调查zk-rollups方案是否可减轻ETH压力:8月31日，Bitfinex首席技术官Paolo Ardoino发推称，在OMG（Tether已宣布OMG Network上发行USDT）之后，Tether正在调查zk-rollups支持是否可以减轻ETH链上交易压力。Paolo Ardoino称，与此同时，本来Tether计划集成一个和交易费相关的新特性，但后来我们决定把重点放在第2层解决方案上。[2020/9/1]
请注意，给定任何你可能想要检查线性组合的特定P_1…P_10点集，你实际上无法在不知道k是什么的情况下创建随附的Q_1…Q_10点，如果你确实知道k是什么，那么你可以创建一对(R,S)，其中R*k=S为你想要的任何R，而无需创建线性组合。因此，要使其发挥作用，绝对必须确保创建这些点的人是值得信赖的，并且在创建十个点后实际上删除k。这就是“可信设置”概念的来源。
请记住，QAP的解是一组多项式(A,B,C)，使得A(x)*B(x)-C(x)=H(x)*Z(x)，其中：
A是一组多项式{A_1…A_m}的线性组合
B是具有相同系数的{B_1…B_m}的线性组合
C是具有相同系数的{C_1…C_m}的线性组合
ETH 2.0项目负责人称阶段0预计很快推出 V神明确反对zk-STARKS应用:ETH 2.0项目负责人Danny Ryan近日在reddit上解答ETH 2.0有关进展和功能时表示，ETH 2.0的开发当前集中在“信标链”的构建上，这是ETH 2.0的基础。但是阶段1的开发正在逐步进行，该阶段引入了用于与信标链连接的“分片”的分片链，并且阶段0发布预计将很快推出。此外，Ryan还表示，团队的目标是让整个以太坊社区参与进来，并与尽可能多的客户建立联系。
而针对有人提出的量子保护隐私保护技术“ zk-STARKS”的“ Etherium 3.0”的想法，Vitalik Buterin本人在reddit上明确表示不支持。V神称，目前，希望以太坊的基本结构在ETH 2.0发布后不会改变。（注：zk-STARKS是一种区块链隐私解决方案，该方案能够将大量信息压缩成名为starks的小样本并使用零知识来保护信息的隐私。）（Coinpost）[2020/6/1]
集合{A_1…A_m}、{B_1…B_m}和{C_1…C_m}以及多项式Z是问题陈述的一部分。
但是，在大多数实际情况下，A、B和C都非常大；对于像散列函数这样具有数千个电路门的东西，多项式可能有数千个项。因此，我们不是让证明者直接提供线性组合，而是使用我们上面介绍的技巧让证明者证明他们提供的东西是线性组合，但不透露其他任何东西。
声音 | V神质疑Zcash ZK-SNARK技术:Zcash正式实施硬分叉升级后，以太坊创始人V神表对其ZK-SNARK 技术提出了一项问题：“如果有人破解了ZK-SNARK方案，并发行一些新的代币怎么解决？”他认为“1、如果有N枚代币进入Zcash的地址池内，将会有N枚流出，每个人交易的代币比例都是1:1，除了最后一个；2、如果有 N枚代币进入，但其中有C枚假币，流出的代币量依然是N枚，那么每个人提出的代币量实际上是N/(N+C)枚；3、这样一来就有C枚假币被发行了，这将有可能导致挤兑风险。在这种攻击严重的情况下，Zcash将有可能不得不放弃2100万枚代币总量的限制。”[2018/6/27]
你可能已经注意到，上面的技巧适用于椭圆曲线点，而不是多项式。因此，实际发生的是我们将以下值添加到可信设置中：
G*A_1(t),G*A_1(t)*k_aG*A_2(t),G*A_2(t)*k_a…G*B_1(t),G*B_1(t)*k_bG*B_2(t),G*B_2(t)*k_b…G*C_1(t),G*C_1(t)*k_cG*C_2(t),G*C_2(t)*k_c…你可以将t视为计算多项式的“秘密点”。G是一个“生成器”，t、k_a、k_b和k_c是“有废物”，绝对必须不惜一切代价删除的数字，或者拥有它们的人将能够制作假证明。现在，如果有人给你一对点P,Q使得P*k_a=Q，那么你知道他们给了什么你是在t处求值的A_i多项式的线性组合。
因此，到目前为止，证明者必须给出：
π_a=G*A(t),π'_a=G*A(t)*k_aπ_b=G*B(t),π'_b=G*B(t)*k_bπ_c=G*C(t),π'_c=G*C(t)*k_c
请注意，证明者实际上不需要知道t、k_a、k_b或k_c来计算这些值；相反，证明者应该能够仅根据我们添加到可信设置的点来计算这些值。
下一步是确保所有三个线性组合具有相同的系数。我们可以通过向可信设置添加另一组值来做到这一点：G*(A_i(t)+B_i(t)+C_i(t))*b，其中b是另一个应该被视为“有废物”的数字，并且受信任的设置完成后立即丢弃。然后，我们可以让证明者使用具有相同系数的这些值创建一个线性组合，并使用与上述相同的配对技巧来验证该值是否与提供的A+B+C匹配。
最后，我们需要证明A*B-C=H*Z。我们通过配对检查再次执行此操作：
e(π_a,π_b)/e(π_c,G)?=e(π_h,G*Z(t))
其中π_h=G*H(t)。如果这个方程和A*B-C=H*Z之间的联系对你来说没有意义，请返回阅读有关配对的文章。
我们在上面看到了如何将A、B和C转换为椭圆曲线点；G只是生成器。我们可以将G*Z(t)添加到可信设置中。H更硬；H只是一个多项式，我们很少提前预测每个单独QAP解决方案的系数。因此，我们需要向可信设置添加更多数据；具体顺序：
G,G*t,G*t2,G*t3,G*t?...。
在Zcash可信设置中，这里的序列高达200万左右；这是你需要多少次幂才能确保始终能够计算H(t)，至少对于他们关心的特定QAP实例而言。这样，证明者就可以为验证者提供所有信息以进行最终检查。
还有一个细节需要我们讨论。大多数时候，我们不只是想抽象地证明某些特定问题的解决方案存在；相反，我们想证明某个特定解决方案的正确性，或者如果你限制解决方案存在一些参数。例如，在交易金额和账户余额被加密的加密货币实例中，你想证明你知道一些解密密钥k，这样：
加密的old_balance、tx_value和new_balance应该公开指定，因为这些是我们希望在特定时间验证的特定值；只有解密密钥应该被隐藏。需要对协议进行一些细微的修改，以创建与输入的某些特定限制相对应的“自定义验证密钥”。
现在，让我们退后一步。首先，这里是完整的验证算法，由benSasson、Tromer、Virza和Chiesa提供：
第一行处理参数化；本质上，你可以将其功能视为为指定了某些参数的问题的特定实例创建“自定义验证密钥”。第二行是A、B、C的线性组合检查；第三行是检查线性组合是否具有相同的系数，第四行是乘积检查A*B-C=H*Z。
总之，验证过程是几个椭圆曲线乘法和五次配对检查，其中一次包括额外的配对乘法。证明包含八个椭圆曲线点：A(t)、B(t)和C(t)各有一对点，b*(A(t)+B(t)+C(t)有一个点π_k))，以及H(t)的点π_h。其中七个点在F_p曲线上，在Zcash实现中，一个点(π_b)在F_p2的扭曲曲线上，所以证明的总大小约为288字节。
创建证明的两个计算上最难的部分是：
将(A*B-C)/Z除以得到H进行椭圆曲线乘法和加法运算以创建A(t)、B(t)、C(t)和H(t)值及其对应的对创建证明如此困难的基本原因是，如果我们要从中制作零知识证明，原始计算中的单个二进制逻辑门变成了必须通过椭圆曲线操作进行加密处理的操作.这一事实，加上快速傅立叶变换的超线性，意味着Zcash交易的证明创建需要大约20-40秒。
另一个非常重要的问题是：我们是否可以尝试使受信任的设置稍微……不那么需要信任？不幸的是，我们不能让它完全不信任；KoE假设本身排除了在不知道k是什么的情况下制作独立对(P_i,P_i*k)。但是，我们可以通过使用N-of-N多方计算来大大提高安全性——也就是说，在N方之间构建可信设置，只要至少有一个参与者删除他们的有废物，那么你就可以了.
为了稍微了解如何执行此操作，这里有一个简单的算法，用于获取现有集合，并“添加”你自己的秘密，以便你需要你的秘密和以前的秘密来作弊。
输出集很简单：
G,(G*t)*s,(G*t2)*s2,(G*t3)*s3…
请注意，你可以只知道原始集合和s来生成此集合，并且新集合的功能与旧集合相同，只是现在使用t*s作为“有废物”而不是t。只要你和创建前一组的人都没有删除你的有废物并随后串通，那么该组是“安全的”。
为完整的受信任设置执行此操作要困难得多，因为涉及多个值，并且必须在各方之间分几轮完成算法。这是一个积极研究的领域，看看是否可以进一步简化多方计算算法并使其需要更少的轮次或更可并行化，因为你可以做的越多，参与可信设置过程的参与方就越多.有理由看到为什么六个相互认识并一起工作的参与者之间的信任设置可能会让一些人感到不舒服，但是一个拥有数千名参与者的信任设置与完全不信任几乎没有区别——而且如果你真的很偏执，你可以自己进入并参与设置过程，并确保你亲自删除了你的值。
另一个活跃的研究领域是使用不使用配对的其他方法和相同的可信设置范例来实现相同的目标。请参阅ElibenSasson最近的演示文稿以了解另一种选择
特别感谢ArielGabizon和ChristianReitwiessner的审阅。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。