维塔利克·布特林 (Vitalik Buterin) Vitalik Buterin 博客
这是帖子的镜像 https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
这是解释 zk-SNARK 背后的技术如何工作的系列文章的第三部分;之前的文章关于 二次算术程序 和 椭圆曲线对 是必读内容,本文将假设您了解这两个概念。还假设您了解 zk-SNARK 是什么及其用途的基本知识。也可以看看 克里斯蒂安·赖特维斯纳 (Christian Reitwiessner) 的文章在这里 另一项技术介绍。
在之前的文章中,我们介绍了二次算术程序,这是一种用多项式方程表示任何计算问题的方法,更适合各种形式的数学技巧。我们还引入了椭圆曲线配对,它允许一种非常有限的单向同态加密形式,让您可以进行相等性检查。现在,我们将从上次停下的地方开始,使用椭圆曲线配对以及其他一些数学技巧,以便证明者能够证明他们知道特定 QAP 的解决方案,而无需透露有关该问题的任何其他信息。实际解决方案。
本文将重点介绍 匹诺曹协议 由 Parno、Gentry、Howell 和 Raykova 自 2013 年起撰写(通常称为 PGHR13);基本机制有一些变化,因此在实践中实施的 zk-SNARK 方案可能会略有不同,但基本原理总体上是相同的。
首先,让我们了解我们将要使用的机制安全性背后的关键加密假设: *指数知识* 假设。
基本上,如果你得到一对点 � 和 ��,其中 �⋅�=�,并且得到一个点 �,那么就不可能得出 ���,除非 � 以某种方式从 �“派生”你知道的。这看起来直观上是显而易见的,但这个假设实际上不能从我们在证明基于椭圆曲线的协议的安全性时通常使用的任何其他假设(例如离散对数硬度)中得出,因此 zk-SNARK 实际上确实依赖于某种一般来说,它的基础比椭圆曲线密码学更不稳定——尽管它仍然足够坚固,大多数密码学家都可以接受。
现在,让我们来看看如何使用它。假设一对点(�,�)从天而降,其中�⋅�=�,但没有人知道�的值是多少。现在,假设我得出一对点 (�,�),其中 �⋅�=�。然后,KoE 假设意味着我得出这对点的唯一方法是采用 � 和 ��,并将两者乘以某个因子 r 我个人知道。另请注意,由于椭圆曲线配对的魔力,检查 �=�⋅� 实际上并不需要知道 � – 相反,您可以简单地检查是否 �(�,�)=�(�,�)。
让我们做一些更有趣的事情。假设我们有十对点从天而降:(�1,�1),(�2,�2)…(�10,�10)。在所有情况下,��⋅��=��。假设我随后为您提供一对点 (�,�),其中 �⋅�=�。你现在知道什么了? 您知道 � 是某种线性组合 �1⋅�1+�2⋅�2+...+�10��10,其中我知道系数 �1,�2...�10。 也就是说,得到这样一对点 (�,�) 的唯一方法是取 �1,�2...�10 的一些倍数并将它们相加,并与 �1,�2... 进行相同的计算。 �10.
请注意,给定任何特定的一组“1…”10 个点,您可能想要检查线性组合,如果您不知道“是什么”,则实际上无法创建伴随的“1…”10 个点,并且如果您确实知道什么然后您可以创建一对 (�,�),其中 �⋅�=� 满足您想要的任何 �,而无需创建线性组合。因此,要使其发挥作用,创建这些点的人绝对是值得信赖的,并且一旦创建了十个点,就会真正删除。 这就是“可信设置”概念的由来.
请记住,QAP 的解是一组多项式 (�,�,�),使得 �(�)��(�)−�(�)=�(�)��(�),其中:
- � 是一组多项式 {�1…��} 的线性组合
- � 是具有相同系数的 {�1…��} 的线性组合
- � 是具有相同系数的 {�1…��} 的线性组合
集合 {�1…��}、{�1…��} 和 {�1…��} 以及多项式 � 是问题陈述的一部分。
然而,在大多数现实世界的情况下,�、�和�非常大;对于像散列函数这样具有数千个电路门的东西,多项式(以及线性组合的因子)可能有数千个项。因此,我们不是让证明者直接提供线性组合,而是使用上面介绍的技巧让证明者证明他们正在提供线性组合,但不透露任何其他内容。
您可能已经注意到,上面的技巧适用于椭圆曲线点,而不适用于多项式。因此,实际发生的情况是我们将以下值添加到可信设置中:
- �·�1(�),�·�1(�)·��
- �·�2(�),�·�2(�)·��
- ...
- �·�1(�),�·�1(�)·��
- �·�2(�),�·�2(�)·��
- ...
- �·�1(�),�·�1(�)·��
- �·�2(�),�·�2(�)·��
- ...
您可以将 t 视为计算多项式的“秘密点”。 � 是一个“生成器”(作为协议一部分指定的一些随机椭圆曲线点),��、��、�� 和 �� 是“有毒废物”,这些数字绝对必须不惜一切代价删除,否则谁拥有它们就可以制作假证明。现在,如果有人给你一对点 �, � 使得 �⋅��=�(提醒:我们不需要 �� 来检查这一点,因为我们可以进行配对检查),那么您就知道他们是什么给出的是在 � 处计算的 � 多项式的线性组合。
因此,到目前为止,证明者必须给出:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
请注意,证明者实际上不需要知道(也不应该知道!) �,��,�� 或 �� 来计算这些值;相反,证明者应该能够仅根据我们添加到可信设置的点来计算这些值。
下一步是确保所有三个线性组合具有相同的系数。我们可以通过在可信设置中添加另一组值来做到这一点:�⋅(��(��)+��(�)+��(�))���,其中�是另一个应被视为“有毒”的数字浪费”并在可信设置完成后立即丢弃。然后,我们可以让证明者使用具有相同系数的这些值创建线性组合,并使用与上面相同的配对技巧来验证该值是否与提供的“+”+”匹配。
最后,我们需要证明 �⋅�−�=�⋅�。我们通过配对检查再次执行此操作:
�(��,��)/�(��,�)?=�(�ℎ,����(�))
其中 �ℎ=�⋅�(�)。如果这个方程和 �⋅�−�=�⋅� 之间的联系对您来说没有意义,请返回并阅读 关于配对的文章.
上面我们看到了如何将�、�、�转换为椭圆曲线点; � 只是生成器(即相当于数字 1 的椭圆曲线点)。我们可以将 ����(�) 添加到可信设置中。 � 更难; � 只是一个多项式,我们很少提前预测每个 QAP 解决方案的系数。因此,我们需要向可信设置添加更多数据;具体来说是顺序:
�,���,��2,��3,��4….
在 Zcash 可信设置中,这里的序列高达约 2 万个;这是您需要确保始终能够计算 �(�) 的 � 的幂数,至少对于他们关心的特定 QAP 实例是这样。这样,证明者就可以提供所有信息供验证者进行最终检查。
还有一个细节需要我们讨论。大多数时候,我们不仅仅想抽象地证明某些特定问题存在某种解决方案;相反,我们想要证明某些特定解决方案的正确性(例如,证明如果您使用单词“cow”并对它进行 SHA3 哈希一百万次,最终结果以 0x73064fe5 开头),或者如果您限制,则存在解决方案一些参数。例如,在交易金额和账户余额被加密的加密货币实例中,您想要证明您知道一些解密密钥 k,以便:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
加密的 old_balance
, tx_value
和 new_balance
应公开指定,因为这些是我们希望在特定时间验证的具体值;仅应隐藏解密密钥。需要对协议进行一些细微的修改来创建与输入的某些特定限制相对应的“自定义验证密钥”。
现在,让我们退一步。首先,这是完整的验证算法,由 ben 提供 萨松、特罗默、维尔扎和基耶萨:
第一行涉及参数化;本质上,你可以认为它的功能是创建一个“自定义验证密钥” 针对问题的具体实例 其中指定了一些参数。第二行是�、�和�的线性组合检查;第三行是检查线性组合是否具有相同的系数,第四行是乘积检查 �⋅�−�=�⋅�。
总而言之,验证过程是一些椭圆曲线乘法(每个“公共”输入变量一个)和五次配对检查,其中之一包括额外的配对乘法。该证明包含八个椭圆曲线点:一对点,分别代表 �(�)、�(�) 和 �(�),一个点��代表�⋅(�(�)+�(�)+�(� )),以及 �(�) 的点 �ℎ。其中七个点位于 �� 曲线上(每个点 32 个字节,因为您可以将 � 坐标压缩为一位),在 Zcash 实现中,一个点 (��) 位于 ��2 中的扭曲曲线上(64字节),所以证明的总大小约为 288 字节。
创建证明的计算上最难的两个部分是:
- 除 (�⋅�−�)/� 得到 �(算法基于 快速傅立叶变换 可以在次二次方时间内完成此操作,但计算量仍然很大)
- 进行椭圆曲线乘法和加法以创建 �(�)、�(�)、�(�) 和 �(�) 值及其对应对
创建证明如此困难的基本原因是,如果我们要从中制作零知识证明,原始计算中的单个二进制逻辑门会变成必须通过椭圆曲线运算进行加密处理的操作。这一事实,加上快速傅立叶变换的超线性,意味着 Zcash 交易的证明创建需要大约 20-40 秒。
另一个非常重要的问题是:我们能否尝试让可信设置的信任要求降低一点……?不幸的是,我们不能让它完全去信任; KoE 假设本身就排除了在不知道 � 是什么的情况下生成独立对 (��,��⋅��)。然而,我们可以通过使用“of-”多方计算来大大提高安全性——也就是说,在各方之间构建可信设置,只要至少一个参与者删除了他们的有毒废物,那么就没有问题。
为了稍微了解一下如何做到这一点,这里有一个简单的算法,用于获取现有的集合(�,���,���2,���3…),并“添加”您自己的秘密这样你就需要你的秘密和之前的秘密(或之前的一组秘密)来作弊。
输出集很简单:
�,(�·�)·�,(�·�2)·�2,(�·�3)·�3…
请注意,您可以只知道原始集合和 s 来生成此集合,并且新集合的功能与旧集合相同,只是现在使用 �⋅� 作为“有毒废物”而不是 �。只要您和创建前一个集合的人(或多个人)没有同时删除有毒废物并随后串通,该集合就是“安全”的。
为完整的可信设置执行此操作相当困难,因为涉及多个值,并且算法必须在各方之间分几轮完成。这是一个积极研究的领域,看看多方计算算法是否可以进一步简化,并使其需要更少的轮次或变得更加可并行化,因为您可以做的越多,将更多的参与方纳入可信设置过程就变得可行。可以合理地理解为什么六个相互认识并合作的参与者之间的信任设置可能会让一些人感到不舒服,但是拥有数千名参与者的信任设置几乎与完全不信任没有区别——如果你真的很偏执的话,您可以自行进入并参与设置过程,并确保您亲自删除了您的值。
活跃研究的另一个领域是使用其他不使用配对的方法和相同的可信设置范例来实现相同的目标;看 伊莱·本·萨森最近的演讲 对于一种替代方案(尽管要注意,它至少在数学上与 SNARK 一样复杂!)
特别感谢 Ariel Gabizon 和 Christian Reitwiessner 的审阅。