什么是贪食蛇？

#1 楼

我假设您熟悉$ P $和$ NP $。另外，我对SNARK的了解主要基于Parno等人的工作，其他工作可能在某些细节上有所不同。

因此，SNARK是知识的简洁非交互式论证。现在暂时将“知识”部分放在一边，让我们看一下“简单”的简洁非交互式参数（在上面链接的工作中称为SNARG）。自变量是计算可靠的证明的另一个名称。您可能知道，证明系统的健全性是无法（在所考虑的系统中）“证明”错误断言的属性的技术术语。

传统的非交互式证明系统具有“完善的健全性”，这意味着绝对不可能证明虚假陈述。例如，给定一个$ NP $语言的$ L $，如果证明者想向验证者证明$ L $中的某个单词$ x $，他可以简单地为$ x $产生一个见证人$ w $。然后，验证者将接受输入$（x，w）$并确信$ x $确实在$ L $中。另一方面，如果$ x $实际上不在$ L $中，则它没有任何$ NP $证人，因此验证者将始终拒绝任何据称的证人$ w $为$ x $。从安全性的角度来看，这是非常好的：验证者可以确定，恶意证明者永远不会欺骗它，使它认为陈述实际上是错误的，而事实却是错误的。但是，问题在于$ NP $证人不能太小（如果我们允许$ NP $证人太小，那么我们会将$ NP $“缩小”到比通常小的程度相信是）。

具有完美健全性的证明系统让人想起具有完美保密性的密码系统，例如一次性密码器：即使具有无限计算能力的对手也无法“破解”它们（对于密码系统，这意味着解密消息；对于证据系统，这意味着证明虚假陈述）。但是，为获得如此强大的安全性而付出的代价是效率的损失，通常认为这种损失对于此类系统来说太高了。解决办法是认识到实际上没有无限计算能力的对手。我们并不十分在意这样的对手是否会破坏我们的系统，如果没有有效的对手（即没有在多项式时间内运行的对手）能够以不可忽略的概率破坏我们的系统，我们会感到满意。而且，就像使用密码系统一样，以这种方式放宽我们的要求可以使系统更加高效：在Parno等人的工作中。证明是恒定大小的，而传统的$ NP $证人在语句的大小中具有大小多项式。

最后，对于$ NP $语言$ L $的简洁非交互论证是一个用于$ L $的非交互式计算声音证明系统，其中的证明简洁。在不同的著作中，后一个术语的定义可能略有不同，Parno等人。将其定义为“安全性参数中的多项式”。这样的证明系统由以下三种算法组成：$ \ mathsf {Gen} $（密钥生成），$ \ mathsf {P} $（证明）和$ \ mathsf {V} $（验证）：



$ \ mathsf {Gen} $通常由验证程序运行。它以$ 1 ^ k $（$ k $作为安全性参数）作为输入，并输出一些密钥对$ \ mathsf {priv} $和$ \ mathsf {pub} $。

$ \ mathsf { P} $（证明算法）将$ \ mathsf {pub} $，L $中的单词$ x \和$ x $的$ NP $-见证$ w $作为输入，并输出证明$ \ pi $ 。

$ \ mathsf {V} $（验证算法）将$ \ mathsf {priv} $，$ x $和$ \ pi $作为输入，并根据验证者是否“接受”证明以下内容而返回$ 0 $或$ 1 $。 $ x $在$ L $中。

系统必须满足以下三个属性（我在此非正式地声明）：



完美完整性：如果$ x $在$ L $中，而$ w $是$ x $的$ NP $见证人，那么证明人在输入$（x，w）$上产生的证明$ \ pi $总是

简洁性：$ \ pi $的长度是$ k $的多项式。请注意，该多项式是通用的，并且可能不取决于实例的长度（即$ | x | $），语言$ L $或L $中的定理$ x \被证明。
< br运算能力强：对于在输入$（1 ^ k，\ mathsf {pub}）$上运行并生成对$（x，\ pi）$的任何多项式时间对手，$ x $不在其中的概率$ L $和$ \ mathsf {V} $接受的$（x，\ pi）$在$ k $中可忽略不计。

最后，什么是简洁的非交互式知识论证（SNARK）？如果您注意上面的内容，则验证者在某些输入$（x，\ pi）$上返回$ 1 $的事实仅证明$ x $在$ L $中，但不排除证明者的可能性。在不知道$ x $的$ NP $见证的情况下，以非标准方式生成了对$（x，\ pi）$。 SNARK通过要求一个附加属性来实现此目的：



可扩展性：对于在输入$（\ mathsf上运行的任何多项式时间证明者$ \ mathsf {P} ^ * $ {pub}，z）$（其中$ z $是一些辅助输入）并生成一对$（x，\ pi）$，有一个多项式时间提取器$ \ mathcal {E} _ {\ mathsf {P} ^ *} $也在输入$（\ mathsf {pub}，z）$上运行并产生$ w $，因此验证者接受了$（x，\ pi）$的概率，而$ w $未被验证者接受$ k $的$ NP $-见证在$ k $中可以忽略不计。

非正式地，extractability属性表示，对于任何需要一些输入$ z $并生成有效对$（x，\ pi）$的算法，都有一个提取器算法需要相同的输入并输出$ NP $ -witness $ $ x $的w $。因此，我们认为第一个算法“知道” $ w $，因为可以仅使用第一个算法已知的数据来有效地计算$ w $。