深入浅出零知识证明（四）：交互式零知识证明和计算复杂度
前言
交互式验证
我们之前已经接触了零知识方面，现在让我们专注于zkSNARKs的另一个主要特征，即简洁性，简洁性是zkSNARKs最为重要的部分，因为零知识部分主要取决于数据的编码方式，该编码允许进行有限形式的同态编码。
SNARKs代表简洁的非交互式知识论证。在这种所谓的交互协议的一般设置中，有一个证明者和一个验证者，证明者希望通过交换消息来说服验证者接受一个陈述（例如f(x) = y），通常希望的属性是没有证明者可以说服验证者接受一个错误的陈述（completeness），并且对于任何正确的陈述，证明者有一种特定的策略可以说服验证者接受它（soundness），其含义主要如下：
简洁：消息的大小与实际计算长度相比非常小
非交互：没有或只有很少的交互。对于zkSNARKs，通常有一个设置阶段，之后证明者发送给验证者的单个消息。此外，SNARKs通常具有所谓的“公共验证者”属性，表示任何人都可以在不进行交互的情况下，对证明进行验证，这对于区块链非常重要。
论证：验证者只受到计算能力有限的证明者的保护。具有足够计算能力的证明者可以就错误的陈述创建证明/论证（请注意，通过足够的计算能力，任何公钥加密都可以被破解），这也被称为“计算上的正确性”，与“完全的正确性”相对。
知识：证明者不能在不知道某种特定的所谓见证（例如，她想要花费的地址，哈希函数的逆像或某个默克尔树节点的路径）的情况下构建证明/论证。
在交互过程中，验证者除了陈述的有效性之外，不会知道任何东西，验证者也不会知道SRS（CRS）是怎么生成的--接下来我们来讲解一下这是什么意思。
举个例子，让我们考虑交易验证的计算函数：f(σ1, σ2, s, r, v, ps, pr, v) = 1，当且仅当σ1和σ2是账户默克尔树的根哈希（先前状态和当前状态），s和r是发件人和接收人账户，ps和pr是在σ1中，且证明s的余额至少为v，并且如果v从s的余额转移到r的余额中，它们哈希到σ2而不是σ1。
如果所有的输入都是已知的，验证f的计算相对容易。因此，我们可以将f转化为一个zkSNARK，其中只有σ1和σ2是公开的，(s, r, v, ps, pr, v)是证据（witness）字符串。现在，零知识属性使得验证者能够检查证明者知道某个证据，该证据不会违反正确交易要求的方式将根哈希从σ1变为σ2，但同时也不知道谁向谁发送了多少钱。
零知识的大致定义是，存在一个模拟器，该模拟器已经生成了SRS（CRS），但不知道秘密的证据，并可以与验证者进行交互，与此同时，外部观察者无法区分这种交互与与真实证明者的交互的区别。
P和NP
为了了解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问题，并给了一些简单的例子。
下一章节，我们将给大家介绍，如何把一个特定的问题规约为多项式，并使用相应的证明系统来证明其等式成立。
分享仅供学习参考，若有不当，请联系我们处理。
END
1.SPDZ 学习笔记-基于Somewhat的全同态加密构造的安全多方计算（2）
文推荐4.SPDZ 学习笔记-基于Somewhat的全同态加密构造的安全多方计算（1）