坚果壳中的ZK-SNARKs第2部分

单击此链接以参考上一篇关于Zk-SNARks的文章-https://www.nvestlabs.com/2019/02/08/zk-snarks-in-a-nutshell-part-1/

互动验证

在这种所谓的交互协议的一般设置中，有一个证明者和一个验证者，证明者想通过交易所消息来使验证者说服一个语句（例如，f（x）= y）。通常期望的属性是，没有证明者可以说服验证者错误的陈述（健全性），并且证明者有某种策略使说服者证明任何真实的陈述（完整性）。

如果添加了零知识前缀，则它还需要具有以下属性：在交互过程中，验证者除了语句的有效性外不了解任何东西。验证者尤其不熟悉见证字符串。

零知识的正式定义是，有一个模拟器，它也已经生成了设置字符串，但不知道秘密见证人，可以与验证者进行交互，但是外部观察者无法将这种交互与与实际的证明者。

NP和复杂性–理论减少

为了了解zk-SNARK可以用于哪些问题和计算，必须从复杂性理论中定义一些概念。

P和NP

首先，对仅输出0或1的函数进行了限制，这被称为问题。对于数学函数f的特定机器实现M，可以始终计算在特定输入x上计算f所需的步骤数-这称为M on x的运行时间。由于程序通常需要更多的时间来处理较大的输入，因此会根据输入的大小或长度（以各种位为单位）不断地测量运行时间。这就是例如产生了“ n ^ 2算法”（一种在大小为n的输入上最多执行n ^ 2步的算法）。概念“算法”和“程序”在这里通常是等效的。

运行时间最多为k的n ^ k个程序也称为“多项式程序”。

复杂性理论中的两个重要问题类别是P和NP：

• P是具有多项式时间程序的这类问题L。

尽管对于某些问题，指数k可能非常大，但P被视为“可行”问题，而对于非人为问题，p通常不大于4。验证比特币交易是P中的问题，如同评估多项式（并将值限制为0或1）。粗略地讲，如果只需要计算某个值而不是“搜索”某物，则问题几乎总是在P中。如果必须搜索某物，则大多数情况下将使用称为NP的类。

NP级

NP类中的所有问题都有zk-SNARK，实际上，当今存在的实用zk-SNARK可以以常规方式应用于NP中的所有问题。 NP之外的任何问题是否都存在zk-SNARK。

NP中的所有问题始终具有特定的结构，源于NP的定义：

• NP是具有多项式时间程序V的问题L，可以使用多项式时间程序V来确定一个事实，给定多项式大小的所谓见证人即可。更正式地讲：L（x）= 1当且仅当存在一些多项式大小的字符串w（称为见证人）使得V（x，w）= 1

作为NP中问题的一个示例，考虑了布尔公式可满足性（SAT）的问题。

P = NP？

如果将NP的定义限制为长度为零的见证字符串，则将捕获与P中相同的问题。因此，P中的每个问题都在于NP。复杂性理论研究的基本任务之一是证明这两个类别实际上是唯一的– NP中存在一个问题，而该问题不在于P。

NP能力

SAT的有趣特性是它不仅位于NP中，而且也是NP完整的。此处的“完成”类似于“车削完成”中的完成。这意味着它是NP中最困难的问题之一，但是，从本质上讲-这是NP-complete的定义-NP中任何问题的输入都可以在以下意义上更改为SAT的等效输入：

对于任何NP问题L，都有一个假定的约简函数f，该函数可以在多项式时间内进行计算，使得：

• L（x）= SAT（f（x））

这种简化功能可以看作是编译器：它采用某种编程语言编写的源代码，然后将其转换为另一种编程语言（通常是机器语言，具有某种语义行为）的等效程序。由于SAT是NP完全的，因此对于NP中的任何可能问题都存在这种减少，包括检查在给定适当的块哈希的情况下例如比特币交易是否有效的问题。有一个归约函数可以将事务转换为布尔公式，最终目标是，当且仅当事务有效时，该公式才是可满足的。

上面显示了如何将NP内部的计算问题相互减少，尤其是存在NP完全问题，这些问题基本上只是NP中所有其他问题（包括事务验证问题）的重新表述，这使查找通用类变得容易zk-SNARK解决NP中的所有问题：只需选择一个合适的NP完全问题即可。

ZK-SNARKs在NutSHELL的第2部分中首次出现在Nvest Labs。