# 零知识学习零知识证明

By [kutugu](https://paragraph.com/@kutugu) · 2022-02-02

---

### 杂谈

**Math is law !**

数学真的太迷人了，虽然我不懂 ;)

水一篇小短文，总结下这两天的学习成果。

抛开数学、多项式不谈，零知识学习零知识证明。

### 概念

首先，零知识证明大致可以概述为：**Prover** 向 **Verifier** 证明拥有某个数据，但证明的同时并**不暴露**这个数据具体是什么。

介绍视频：

[![]({{DOMAIN}}/editor/youtube/play.png)](https://www.youtube.com/watch?v=fOGdb1CTu5c)

中文翻译：

[https://mp.weixin.qq.com/s/ZIXOxidlYZExzDZuEdg8Yg](https://mp.weixin.qq.com/s/ZIXOxidlYZExzDZuEdg8Yg)

视频中科学家提到一个很有意思的点，为什么叫 **零知识** 而不是 **零信息**、**零数据** ？

我的一个理解：因为在证明的过程中， **Prover** 需要向 **Verifier** 提供 “部分数据” 用于验证，最终**Verifier** 得到一个 “信息”：Prover是 **大概率** 拥有这个完整数据的。

通过大量验证Verifier不断提高这个 **概率** 直到可信阈值，但在整个过程中所有的 **Verifier** 都无法拼凑出数据的完整体 — “知识”。

下面再通过一个经典的数独故事来理解这一概念：

原文链接：

[https://medium.com/qed-it/the-incredible-machine-4d1270d7363a](https://medium.com/qed-it/the-incredible-machine-4d1270d7363a)

中文翻译：

[https://zhuanlan.zhihu.com/p/34072069](https://zhuanlan.zhihu.com/p/34072069)

### 零知识性

零知识证明有三种性质，**完备性**和**可靠性**不再赘述，下面通过一个问题来进一步理解**零知识性**

> **误区**：地图三染色问题上的零知识证明，可能存在知识泄漏？

这是我在学习过程中的一个疑问点，思考：

*   **Prover** 需要向 **Verifier** 提供相邻两个地域的颜色，以便 **Verifier** 验证；
    

![ 图片来源：https://secbit.io/blog/2019/07/31/zero-knowledge-and-proof](https://storage.googleapis.com/papyrus_images/b764980c0ec706da49240d75e6d904b81fe75063219de17653661e8f6febcfcd.png)

图片来源：https://secbit.io/blog/2019/07/31/zero-knowledge-and-proof

*   但是颜色一共只有三种，虽然第二次通过随机数更换了颜色，但如果 **Verifier** 第二次选择的地域和第一次存在交集，那么 **Verifier** 可以拿到前后两次颜色的映射
    

![图片来源：https://secbit.io/blog/2019/07/31/zero-knowledge-and-proof](https://storage.googleapis.com/papyrus_images/8d9880fe82e7422274b17e08e6f4723036b52d75e1ed43babd67d5d90e318106.png)

图片来源：https://secbit.io/blog/2019/07/31/zero-knowledge-and-proof

    // 第一种映射
    绿色 —> 红色
    A —> 棕色
    橙色 —> B
    
    // 第二种映射
    绿色 —> 红色
    橙色 —> 棕色
    A —> B
    

那 **Verifier** 是不是可以反推回去，拿到第一次 & 第二次的结果？

![图片来源：https://secbit.io/blog/2019/07/31/zero-knowledge-and-proof](https://storage.googleapis.com/papyrus_images/02e8a7c6a24b947ddde5f5c880deceaa9c62ebed770513673e2e6db097178c5a.png)

图片来源：https://secbit.io/blog/2019/07/31/zero-knowledge-and-proof

即第二次棕色的位置，对应第一次的橙色或A色。这样每次我们都有1 / 2的概率可以猜对，最终拿到所有结果。

这样是不是说明存在知识泄漏的风险？当然不是

#### 证明 1

我们要知道虽然每次都有1 / 2的概率猜对，但整个计算的时间复杂度却是 **O(2^n)** 级别的，这是一个[NP问题](https://zh.wikipedia.org/wiki/P/NP%E9%97%AE%E9%A2%98)。NP的具体介绍不在本文范围内，只需要知道它的计算时间很复杂。

所以 **Verifier** 基本是无法反推出来的。反过来讲，既然这个NP问题可以应用零知识证明，那通过NP的性质，我们可以得出 **零知识证明可以应用于所有的NP问题** 这一结论。

#### 证明 2

上面 **Verifier** 的反推过程，大家不觉得有点眼熟吗？这不就是地图三染色问题的 **穷举** 解法吗？和零知识证明、知识泄漏并无任何关系。

#### 证明 3

下面我们通过理论的角度，也可以验证上面的结论。参考文章：

[https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/](https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/)

如果你没有看过上面数独的故事，我建议你先去阅读一遍。

故事中提到了一个人为的作弊行为，下面我们用编程来替代人为交互：

我们想象一个这样的程序，假设一个由 **Prover** 完全操控的验证程序 （当然事实不可能是这样，只是为了模拟作弊），可以在任意节点 **倒带回溯**，修复该节点的错误，那么 **Prover** 完全可以通过操控这个验证程序来蒙混过关，欺骗 **Verifier**。

基于上述背景，我们再来思考两个场景：

*   **Prover** 提供了标准答案给 **Verifier** 验证；
    
*   **Prover** 通过回溯欺骗 **Verifier**，通过验证。
    

两个场景在 **Verifier** 的角度看有区别吗？没有，两种场景对于 **Verifier** 的结果都是正确通过验证。

So ? 假设像误区所提到的那样，**Verifier** 有一种策略可以获取 **Prover** 的完整知识。

但是因为第二种场景中 **Prover** 根本不知道完整知识，所以 **Verifier** 不能获取任何知识。

而且既然两种场景在 **Verifier** 的视角并无区别，那么在第一种场景中 **Verifier** 也不应能获取任何知识。

推导完毕。

### 相关链接

以上就是我本人对于零知识证明的一点理解，我的水平就到这里了。

如果想要更深入地学习零知识证明，这里有相关的资料汇总：

[https://secbit.io/blog/2019/11/07/zkp-learning-resources/](https://secbit.io/blog/2019/11/07/zkp-learning-resources/)

[https://mirror.xyz/0xab722fcb8902c3B98c622db66E0b3247F7691eCA/y11EKtXAtK3aXRVMV1yYqw7FibKHxI0fK10vlVRDaD4](https://mirror.xyz/0xab722fcb8902c3B98c622db66E0b3247F7691eCA/y11EKtXAtK3aXRVMV1yYqw7FibKHxI0fK10vlVRDaD4)

更多相关知识 && 社区讨论：

[https://discord.com/invite/9UB8Skbzxb](https://discord.com/invite/9UB8Skbzxb)

个人推特，持续更新沉淀 **Web3** 的相关知识：

[https://twitter.com/kutugu1](https://twitter.com/kutugu1)

最后感谢头雁和社区同学提供的平台和分享。

---

*Originally published on [kutugu](https://paragraph.com/@kutugu/JOLUxrlwR3myxcwWzsop)*