深入浅出零知识证明（四）：交互式零知识证明和计算复杂度

为了了解zkSNARKs可以用于哪些问题和计算中，我们必须从复杂性理论中定义一些概念，如果您不关心“witness”是什么。 

P和NP

首先，让我们将自己限制在只输出0或1的函数上，并将这样的函数称为问题。因为您可以逐个查询结果的每个位，它使得理论变得容易得多。现在，我们想要衡量解决给定问题（计算函数）的“复杂程度”，对于数学函数f的特定机器实现M，我们始终可以计算M在特定输入x上，计算f所需的步骤数，这称为M在x上的运行时间。 

在这种情况下，“步骤”的确切含义并不太重要。由于程序在较大的输入上通常需要更长的时间，因此这个运行时间总是以输入的大小或长度（以位数表示）来衡量。这就是例如“n^2算法”的概念的来源-它是一个在大小为n的输入上最多需要n^2步的算法。在这里，“算法”和“程序”的概念几乎是等价的，运行时间最多为n^k（k为常数）的程序也被称为“多项式时间程序”。 

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

P是具有多项式时间算法的问题L的类

即使对于某些问题，指数k可能非常大，P仍被认为是“可行”问题的类，对于一般的问题，k通常不大于4。验证比特币交易是P中的一个问题，计算多项式（并将值限制为0或1）也是如此。粗略地说，如果您只需要计算某个值而不是“搜索”某些内容，则该问题几乎总是在P中。如果您必须搜索某些内容，则大多数情况下会进入一个称为NP的类。 

NP类

zkSNARK适用于任何在NP类中的问题，实际上，今天存在的实用zkSNARK可以以通用方式应用于NP中的所有问题。目前不清楚是否有针对NP之外问题的zkSNARK。

NP中的所有问题都具有一定的结构，源自NP的定义：

NP是具有多项式时间程序V的问题L的类，该程序可用于对结果进行验证。更正式地说：当且仅当存在某个多项式大小的字符串w（witness），使得V(x, w) = 1时，L(x) = 1

作为NP问题的示例，让我们考虑布尔公式可满足性（SAT）问题，为此，我们首先使用归纳概括的方法来定义布尔公式：

(1). 任何变量x1、x2、x3等都是布尔公式（我们还使用任何其他字符来表示变量）

(2). 如果f是布尔公式，则¬f是布尔公式（取反）

(3). 如果f和g是布尔公式，则(f∧g)和(f∨g)是布尔公式（合取/与，析取/或）。

(4). 字符串“((x1∧ x2)∧ ¬x2)”将是一个布尔公式。

如果有一种方法可以为变量分配真值，使得公式计算结果为真（其中¬true为false，¬false为true，true∧false为false等等，遵循常规规则），则布尔公式是可满足的，可满足性问题SAT是所有可满足布尔公式的集合。

SAT(f) := 如果f是可满足的布尔公式，则为1，否则为0

上面的例子“((x1∧ x2)∧ ¬x2)”是不可满足的，因此不属于SAT。给定公式的证据是其可满足赋值，并且验证变量赋值是否可满足是一个可以在多项式时间内解决的任务。

 P = NP ？

如果将NP的定义限制为长度为零的证据字符串，那么您捕获的问题与P中的问题相同。因此，P中的每个问题也属于NP。复杂性理论研究的主要任务之一是证明这两个类实际上是不同的-即NP中存在一个不属于P的问题。这似乎是显而易见的，但是如果您能正式证明它，您可以赢得100万美元。如果您能证明了P和NP相等，除了赢得那笔金额之外，加密货币有很大可能性将停止存在，原因是将更容易找到工作证明、哈希函数中的碰撞或与地址相对应的私钥的解决方案。这些都是NP中的问题，因为您刚刚证明了P = NP，所以必须有一个多项式时间程序，大多数研究人员认为P和NP不相等。 

NP完全问题

让我们回到SAT。这个看似简单的问题的有趣特性是，它不仅属于NP，而且还是NP完全的。这里的“完全”一词与“图灵完全”中的“完全”相同。这意味着它是NP中最困难的问题之一，但更重要的是，这就是NP完全的定义，任何NP问题的输入都可以转化为等价的SAT输入，如下所示：

对于任何NP问题L，存在一个所谓的规约函数f，它在多项式时间内可计算，使得：

L(x) = SAT(f(x))

 这样的规约函数可以被看作是一个编译器：它将用某种编程语言编写的源代码转换为另一种编程语言中的等效程序，通常是机器语言，其具有相同的语义行为。由于SAT是NP完全的，因此对于NP中的任何可能问题，都存在这样的规约，包括检查比特币交易是否有效的问题。存在一个将事务转换为布尔公式的规约函数，使得当且仅当公式是可满足的时，该公式是可满足的。

规约示例

为了看到这样的规约，让我们考虑多项式求值问题。首先，让我们将多项式（类似于布尔公式）定义为由整数常数、变量、加法、减法、乘法和（正确平衡的）括号组成的表达式。现在我们要考虑的问题是

PolyZero(f) := 如果f是多项式，在其变量取自集合{0，1}时为1

我们现在将从SAT到PolyZero的规约构造，并证明PolyZero也是NP完全的，只需在布尔公式的结构元素上定义规约函数r即可。其思路是对于任何布尔公式f，值r(f)都是一个多项式，具有相同数量的变量，并且当f(a1,..,ak)为真时，r(f)(a1,..,ak)为零，其中true对应于1，false对应于0，并且r(f)仅在来自{0，1}的变量上取值为0或1：

r(xi) := (1 - xi)

r(¬f) := (1 - r(f))

r((f ∧ g)) := (1 - (1 - r(f))(1 - r(g)))

r((f ∨ g)) := r(f)r(g)

人们可能会认为r((f ∧ g))应该定义为r(f) + r(g)，但那样将使多项式的值超出{0，1}集合。

使用r，公式“((x ∧ y) ∨¬x)”被转换为“(1 - (1 - (1 - x))(1 - (1 - y))(1 - (1 - x))”,

请注意，r的每个替换规则都满足上述目标，因此r正确执行了规约：

 SAT(f) = PolyZero(r(f))或者当且仅当f是可满足的时，r(f)在{0，1}中也为0。

证据保护

从此示例中，您可以看到规约函数仅定义了如何转换输入，但是当您更仔细地观察它（或阅读它执行有效规约的证明）时，您还会看到一种同时转换有效证据和输入的方法。在我们的示例中，我们仅定义了如何将公式转换为多项式，但是通过证明，我们解释了如何转换证据，并满足赋值。对于事务而言，这种证据的同步转换并不是必需的，但通常也会这样做，这对于zkSNARKs非常重要，因为证明者的唯一任务是说服验证者存在这样一个见证，而不泄露关于证据的任何信息。

本文相较于第二章的零知识证明专题推送而言，进一步地讲解了P问题和NP问题，并给了一些简单的例子。

下一章节，我们将给大家介绍，如何把一个特定的问题规约为多项式，并使用相应的证明系统来证明其等式成立。

分享仅供学习参考，若有不当，请联系我们处理。