一文读懂零知识证明背后的简单逻辑

[Whisker17]

一文读懂零知识证明背后的简单逻辑

原文链接：一文读懂零知识证明背后的简单逻辑

[Whisker17]

随着对区块链探索的深入，我们发现通过密码学的方法来实现信任是对共识算法信任的有效补充，这两种信任可以更低摩擦地结合在一起，因此也更易被实现和应用。

[Whisker17]

密码学需要存在一种「单向功能」，也就是说能够从 A 计算出 B，但从 B 计算出 A 存在着计算上的不可行性——计算从 A 到 B 是单向的，我们才有可能把 A 藏起来。而如果 P = NP，在多项式时间内可验证的问题同时也是可求解的，那么通过 B 就能计算出 A，秘密也就无法隐藏。

这就是密码学背后的简单逻辑：单向功能。而单向功能背后的支撑是 P! = NP。

这与零知识证明的关系是什么呢？我们可以把零知识证明分解为两个功能，第一个功能是隐藏秘密，第二个功能是证明自己有秘密。

[Whisker17]

对于零知识证明来说，隐藏秘密只是第一步，我们还需要证明自己确实掌握了秘密。就像在第一段旅程中只需要理解单向功能，在这第二段旅程中，我们只需要理解「同态」，有了同态我们就有了证明秘密的能力。那么什么是同态？

我们可以把单向功能看成一种映射关系，比如 k × P = Q 就是 k 到 Q 的映射：在一个空间中，我们有无数个 k 点，它们被映射到另一个空间，变成无数个 Q 点。这就像现实世界和影子世界，通过光线的映射，现实空间的物体变成了影子空间的影子。

f(a+b) = f(a) + f(b)，即「先计算后加密的结果」f(a+b) 与「先加密后计算的结果」f(a) + f(b) 是相同的。同态使得我们可以直接对密文进行计算，然后对隐藏了秘密的明文先计算后加密，再通过比较两者是否相同验证明文中是否真的藏有秘密。

[Whisker17]

同态定义： 抽象代数中，同态是两个代数结构（例如群、环、或者向量空间）之间的保持结构不变的映射。

[Whisker17]

椭圆曲线算法的同态属性使得其他算法，比如椭圆曲线数字签名算法，可以利用它来隐藏并证明秘密，但该算法的能力有限，因为它只具备加法同态，也就是 f(a+b) = f(a) + f(b)，但不具备乘法同态，即 f(a×b) = f(a) × f(b)。

[Whisker17]

如何解决乘法的同态性，可以引入「配对函数」。比如椭圆曲线配对函数就是对椭圆曲线算法做一系列的调整，生成一个新的映射空间，这个新空间既满足加法同态，也满足类乘法同态（注意，只是类乘法同态），这样一来，除了用加法，我们还可以用类乘法去证明秘密。

[Whisker17]

多项式能够证明各类秘密，因为它能证明布尔电路。

为什么能证明布尔电路，就能证明各类秘密？因为布尔电路可满足性是一个 NPC（NP-Complete）问题，而 NPC 问题有一个「特性」，即所有的 NP 问题（包含NPC）都可以在多项式时间内归约（转换）成某一个具体的 NPC 问题。

详情请见：N vs NP

[Whisker17]

不同的零知识证明协议在这三点上的具体实现是不一样的，最主要的不同可能体现在 “证明 NPC 问题的多项式（但这并非唯一的方法）可以实现通用零知识证明” 中，哪怕证明的是同一个 NPC 问题，也可以有截然不同的方法。因为不同的设计，零知识证明协议最常被提及的差异主要包括：

1. 不同的计算空间和计算时间。

2. 是否需要初始化可信设置。

   不需要可信设置当然更好，会减少信任问题和安全问题，不过新的证明方法就可能带来新的计算问题，比如 Bulletproofs 不需要可信设置，但它在高复杂度情况下的验证成本会很高。

3. 所依赖的安全假设。

   安全假设与安全密切相关，比如 Bulletproofs 依赖的是一个标准安全假设：离散对数问题，加上一个随机预言模型；而 zk-SNARKs 依赖的是一个不可否证的安全假设问题：指数知识假设。

[Whisker17]

zk-STARKs 并没有使用密码学中的单向函数，简单理解的话，它是这样做的：假设 P 有 9 个要证明的数，a1，a2，……，a9，那么把它们编码成 b1，b2，……，b9，每个bi中都含有a1，a2，……，a9 的部分信息。在做验证的时候，验证者 V 对 b1，b2，……，b9 做抽样检查，从少量 bi 中就能分析出编码有没有错误，这样就可以大概率探测到 a1，a2，……，a9 是否属实。

当 V 对 P 作随机抽样时，P 能够主动用随机数混淆抽样的 bi，同时又能使 V 完成验证，从而实现零知识性。

所以 zk-STARKs 的「单向」并不是基于计算不可行的单向，它是因为没有暴露 b1，b2，……，b9 全部，导致无法通过 b1，b2，……，b9 反向计算出 a1，a2，……，a9。在「同态」部分，它也不是抽象代数（或密码学）中的同态概念，而是基于线性编码纠错理论进行抽样验证。

zk-STARKs 也不是基于上文介绍的 NPC 难题做验证，它是基于概率检查做验证的。关于这类验证方法，可以从一种古老的验证系统 PCP（Probabilistically Checkable Proofs）中找到线索，不过在 zk-STARKs 中使用的方法叫 IOP（Interactive Oracle Proofs），与 PCP 的不同之处在于它用的是 Oracle。