作者：VitalikButerin
原标题：《Zk-SNARKs:UndertheHood》
发表时间：2017年2月1日
这是解释zk-SNARKs背后的技术如何工作的系列文章的第三部分；以前关于二次算术程序和椭圆曲线配对的文章是必读的，本文将假设这两个概念的知识。还假设了zk-SNARK是什么以及它们做什么的基本知识。另请参阅此处的ChristianReitwiessner的文章以获得另一篇技术介绍。
在之前的文章中，我们介绍了二次算术程序，这是一种用多项式方程表示任何计算问题的方法，它更适合各种形式的数学技巧。我们还介绍了椭圆曲线配对，它允许一种非常有限的单向同态加密形式，可以让你进行相等性检查。现在，我们将从上次中断的地方开始，使用椭圆曲线配对以及其他一些数学技巧，以允许证明者证明他们知道特定QAP的解决方案，而无需透露任何关于实际解决方案。
本文将重点介绍Parno、Gentry、Howell和Raykova从2013年开始的Pinocchio协议；基本机制有一些变化，因此在实践中实施的zk-SNARK方案可能会略有不同，但基本原理通常保持不变。
首先，让我们进入我们将要使用的机制的安全性背后的关键密码假设：指数知识假设。
基本上，如果你得到一对点P和Q，其中P*k=Q，并且你得到一个点C，那么除非C以某种方式从P“派生”出来，否则不可能得出C*k你知道的。这可能看起来很直观，但是这个假设实际上不能从我们通常在证明基于椭圆曲线的协议的安全性时使用的任何其他假设推导出来，因此zk-SNARK实际上确实依赖于比椭圆曲线密码学更普遍的基础更不稳定——尽管它仍然足够坚固，大多数密码学家都可以接受。
现在，让我们来看看如何使用它。假设有一对点(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进行相同的计算。
请注意，给定任何你可能想要检查线性组合的特定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}的线性组合
集合{A_1…A_m}、{B_1…B_m}和{C_1…C_m}以及多项式Z是问题陈述的一部分。
但是，在大多数实际情况下，A、B和C都非常大；对于像散列函数这样具有数千个电路门的东西，多项式可能有数千个项。因此，我们不是让证明者直接提供线性组合，而是使用我们上面介绍的技巧让证明者证明他们提供的东西是线性组合，但不透露其他任何东西。
你可能已经注意到，上面的技巧适用于椭圆曲线点，而不是多项式。因此，实际发生的是我们将以下值添加到可信设置中：
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的审阅。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。