0%

知识的零知识证明

发表于 更新于 分类于

ZKPoK（Zero Knowledge Proof of Knowledge）是指对于知识的零知识证明，主体是对于知识的证明（PoK），ZK 是描述性质的修饰词，指这个证明同时也满足一些零知识性。具体来说，这个证明要求证明者 P 向验证者 V 证明自己知道某些秘密的值但 V 无法得知这个值。

为什么要 PoK？

上面这个简述听起来很像 ZK 做的事啊？那为什么还要引入 PoK 呢？

要回答这个问题，我们可以回忆一下在 ZKP（或者更一般性的 IP）中，完备性和可靠性的定义关注的是要证明某个对像 $x$ 是否属于给定的语言 $L$，以及 $R_L(x)$ 中是否存在一个秘密值 $\omega$（称为 witness），除此之外它并没有真正关心证明者是否知道这个秘密值 $\omega$。虽然在很多的举例中，证明者确实需要知道这个秘密值 $\omega$ 才能满足零知识性的要求，但是也存在一些平凡（trival）的情况。

比如说，要证明某个图（graph）中存在一条由 A 到 B 的最短路径，那么语言 $L$ 就是所有存在这样最短路径的图的集合，对象 $x$ 就是某个图 $G$。很显然任何图中都存在一条 A 到 B 的最短路径，换句话说，任何关于某个对象 $x$ 属于语言 $L$ 的陈述都是真的。此时，即使 P 不知道这条最短路径到底由哪些边组成，它也可以肯定这条最短路径是存在的，相应的，它就可以回答给 V 说这个陈述是真的。ZK 性质也可以验证通过。

又比如说，当我们要登录某个账号时，仅仅证明存在某个私钥（private key）与这个账号对应是不够的（这就是平凡情况，因为任何有效账号肯定都有一个对应的私钥），我们一定要证明我们知道这个账号具体对应哪个私钥才可以。

因此，对于这些情况，只有 ZK 约束是不够的，需要更严格的定义要求 P 要证明自己的确知道秘密值 $\omega$ 才行，这就是对于知识的证明（PoK）。

那为什么还要在 PoK 前加上 ZK 约束呢？这个问题还是很好回答的。我们可以设想一下，P 完全可以直接把秘密值 $\omega$ 发给 V 就可以满足 PoK 的要求。这就没有乐趣了。于是再加上 ZK，要求 V 在证明协议结束后，不知道这个秘密值才行。

PoK 的定义

交互证明中的完备性和可靠性以及零知识证明中的零知识性在这里就不再赘述。我们直接给出 PoK 的性质。

（Definition：PoK） An interactive proof system $(P, V)$ for an NP relation $R_L$ is a proof of knowledge with knowledge error $\epsilon$, if there exists an algorithm $\mathcal{E}$, called a knowledge extractor, that runs in expected polynomial time, and such that for every $\omega$ and every prover $P$*:

这个定义是说，如果 P*（不管是诚实的证明者还是准备骗取信任的恶意证明者） 能够说服 V，那么就存在一个名为知识抽取器（knowledge extractor）的算法 $\mathcal{E}$，该算法通过和 P* 的交互可以输出秘密值 $\omega$。注意定义中允许事件1（P* 能说服 V）和事件2（知识抽取器 $\mathcal{E}$ 可以通过和 P* 的交互输出 $\omega$）发生的概率之间存在一个差值函数。这个差值我们称之为 knowledge error，这可以认为是事件3（不知道秘密值 $\omega$ 的恶意证明者成功说服 V）发生的概率。因此 PoK 性质又可以称为 Knowledge soundness 性质。

与 ZKP 的情况类似，ZKP 为了能够正式定义“V 除了知道陈述是真的之外一无所知”这个要求，引入了模拟器（simulator）。在 PoK 中，为了定义“P 确实知道秘密值 $\omega$”这个要求，引入了知识抽取器算法（knowledge extractor）。我们可以试着从逻辑上来理解这个知识抽取器的作用。

考虑到 PoK 防止那些不知道秘密值 $\omega$ 的恶意证明者去骗取 V 的信任，因此 PoK 实际上要求的是“如果证明者没有秘密值 $\omega$，那么它就无法得到 V 的信任”，用命题逻辑的方式表达就是：

考虑与其等价的逆否命题，即为

因此，知识抽取器就是在事件（P* 能说服 V 让其验证通过）的基础上，通过和 P* 的交互，从 P* 的输出中计算（抽取）出 P* 掌握的秘密值 $\omega$。

接下来的问题是：既然可以从 P* 的输出中计算出这个秘密值，而又考虑到 P* 与 V 的交互是公开可见的，那么难道随便一个人看到了这些交互之后都能用同样的算法计算出秘密值吗？当然不可能！所以知识抽取器一定是有什么特殊的性质。

知识抽取器的特殊性在于，它可以控制在与证明者交互时，随意地倒带（rewind）。这是一个很强大地功能。强大在哪呢？我们可以考虑一下，如果在 GI 的 ZKP 中 V 拥有这样的功能，那它可以利用这个倒带功能，在 P 回答 V 的提问（V 的提问我们称为挑战 challenge）之后，倒回到 V 发出挑战 $b$ 的时间点，又给 P 一个不同的挑战 $b’ = 1-b$，这样验证者就可以通过倒带，得到 $b=0$ 和 $b=1$ 的两个挑战的回答，假设分别为 $\phi$ 和 $\phi’$。仔细观察 P 的这两个回答，我们会发现，V 只需要简单地计算 $\omega = \phi \circ \phi’$ 就能得到秘密值 $\omega$ ！

倒带（Rewind）

这个类似于拥有时间倒流的能力的概念靠谱吗？怎么感觉很玄学呢？我们难道能随意地设计一些很神奇的概念去解决任何事情吗？这不禁让我想起高中班主任说我们做几何题时总喜欢设一些“万能点”，“万能线”，有了这些满足很多性质的万能点线，几何证明难题迎刃而解。但是问题在于，万能点线的存在前提是要证明的性质被满足，而我们又用这些万能点线去证明这些性质。这不是陷入了死循环嘛！这种做法当然是不可取的。很神奇的概念也是需要理论支撑的。支撑倒带（rewind）的理论基础叫：Rewinding Lemma。下面给出这个引理的具体描述，[BS20] 书中有这个引理的详细证明。

（Rewinding Lemma） Let $S$ and $T$ be finite and non-empty sets, and let $f: S \times T \to {0, 1} $ be a function. Let $X$, $Y$, and $Y’$ be mutually independent random variables, where $X$ takes values in the set $S$, and $Y$ and $Y’$ are each uniformly distributed over $T$. Let $\epsilon := Pr[ f(X, Y) = 1] $ and $N := |T|$. Then

有了这个引理，我们就可以重新解释倒带（rewind）到底在做什么了。考虑不同的挑战（challenge）对应变量 $Y$ 和 $Y’$，$X$ 对应着其余的随机量。函数 $f$ 的输出对应着是否验证通过。因此对于以概率 $\epsilon$ 成功验证通过的 P，它实际上至少能以概率 $\epsilon^2 - \frac{\epsilon}{N}$（其中 $N$ 是挑战空间 challenge space的大小，即可能的挑战的个数）成功验证通过同一情况下 V 提出的两个不同的挑战。这一行为看上去就像是得到一个 P 对于挑战的回答后，又倒带（rewind）回 V 提出挑战的时间点，再重复一遍（这一遍中挑战可以变得不同）证明协议。因此知识抽取器 $\mathcal{E}$ 利用这些不同挑战对应的验证通过的交互记录（accepting transcript，或者也称 accepting conversation）去计算秘密值是合理的。

Σ-protocol

Sigma protocol

如图所示是一个 $\Sigma$-协议（Sigma-protocol）的一般表达。顺便说一句，叫这个名字是因为协议中交互的顺序使得中间的公开交互记录形如一个“$\Sigma$”（好吧，为了让它更像 $\Sigma$，我特意把图中共同输入部分平躺着画了）。$\Sigma$-协议是交互式证明中较特殊但是在密码学中使用特别广泛的一类证明协议。大多数的 PoK 都遵循 $\Sigma$-协议的形式。它规定证明者 P 先向验证者 V 发送一个承诺，V收到这个承诺后，从挑战空间（challenge space）中选择一个挑战发送给 P，P 再返回给 V 这个挑战的计算结果，最后 V 再输出是否验证通过。

基于 $\Sigma$-协议，PoK（或者Knowledge soundness）又可以表述成 Special soundness。差异在于，special soundness 中直接就给出了两个验证通过的交互记录，就不需要算法再去倒带（rewind）了，而可以直接计算 $\omega$。另外，可以看到 special soundness 和 IP 中的 soundness 不同在于，普通的 soundness 性质只要求 V 不接受一切陈述是假时的交互记录，而这个定义则要求 V 即使在陈述是真的情况下也只接受那些知道秘密值 $\omega$ 的 P 与它产生的交互记录。这就是 special soundness 特殊的地方。

（Definition：Special soundness） Given any common input $x$ and any pair of accepting conversations on input $x$, i.e. $(t, c, z)$, $(t, c’, z’)$ where $c \ne c’$, one can efficiently compute $\omega$ such that $(x, \omega) \in R_L$.

注意，special soundness 严格说起来比 PoK 性质更强，因为 special soundness 只要求得到两个验证通过的交互记录（相当于 rewind 一次）就可以提取出秘密值，但 PoK 对 rewind 的次数没有限定，可能一次也可以多次。

但同时，$\Sigma$-协议也有缺点，就是它无法满足严格的 ZK 性质，而只能退而求其次，满足 (special-) Honest Verifier Zero-Knowledge（HVZK）性质。这是因为 $\Sigma$-协议在定义中要求验证者 V 选择的挑战是从挑战空间中随机选取的，这样才能保证协议的安全（这样构造模拟器来证明零知识性时就可以满足要求）。但是对于一些恶意的 V，它不遵循这个规则，那么就可能会产生安全上的漏洞。当然也有办法强制 V 必须要遵守规则，就是在协议开始之初，V 必须首先发出一个承诺表示自己确实遵守了协议规则。但这样做就增加了一个交互信息（one-move），导致协议效率降低。同时考虑到 (special-) HVZK 已经可以满足大多数场景的需求，因此在协议设计时仅考虑 (special-) HVZK 是很常见的选择。

注意，HVZK 只是在定义 ZK 的基础上增加了对 V 要是诚实的限制，模拟器还是可以和 V 交互的；而 special HVZK 则在定义中移除了与 V 交互的部分，转而直接给模拟器输入 $(c, z)$，让模拟器输出一个 $t$ 使得 $(t, c, z)$ 符合 HVZK 时定义的分布关系。因此 special HVZK 证明过程相当于提前得到了挑战和回复，要“凑出”对应的承诺。这一点在下面的实例中将会看到。

Schnorr’s protocol

下面我们来看一个 $\Sigma$-协议在离散对数（Discrete-Log）中的具体构造：Schnorr’s 协议。最初由 [Sch91] 提出，这里给出的是其中的身份认证（identification）部分对应的 $\Sigma$-协议。

构造具体为：设 $p, q$ 为两个大质数，且满足 $q | (p-1)$；设 $G_q$ 为 $\mathbb{Z}_p^*$ 的阶为 $q$ 的（唯一）子群；设 $g$ 为 $G_q$ 的一个生成元。现在随机地从 $\mathbb{Z}_q$ 中选取 $\omega$，并设 $h:= g^{\omega}$。那么共同输入即为 $x := (G_q, g, h)$，而 $\omega$ 则为 P 的秘密输入。设 $\lambda$ 为安全参数。

Schnorr's protocol

现对于上述协议证明其满足以下性质：

  • Completeness：对于诚实的 P 和 V 的交互记录，验证总是可以通过，

  • Special HVZK：给定随机选取的 $(c, z)$，即 $c \gets \{0, 1\}^{\lambda}$, $z \gets \mathbb{Z}_q$，那么可以计算出对应的 $t$ 为

    同时注意到这样得到的 $(t, c, z)$ 与真实的交互记录在分布上是不可区分的，即两者都是满足验证式的随机值。

  • Special soundness：给定两个相同承诺下的验证通过的交互记录 $(t, c, z)$ 和 $(t, c’, z’)$，那么从中可以计算出 $\omega$ 为

参考资料