零知识学习零知识证明
零知识学习零知识证明⌗
杂谈⌗
Math is law !
数学真的太迷人了，虽然我不懂 ;)
水一篇小短文，总结下这两天的学习成果。
抛开数学、多项式不谈，零知识学习零知识证明。
概念⌗
首先，零知识证明大致可以概述为：Prover 向 Verifier 证明拥有某个数据，但证明的同时并不暴露这个数据具体是什么。
视频中科学家提到一个很有意思的点，为什么叫 零知识 而不是 零信息、零数据 ？
我的一个理解：因为在证明的过程中，Prover 需要向 Verifier 提供 部分数据 用于验证，最终 Verifier 得到一个信息：Prover 是 大概率 拥有这个完整数据的。
通过大量验证Verifier不断提高这个概率直到可信阈值，但在整个过程中所有的 Verifier 都无法拼凑出数据的完整体 —- 知识。
下面再通过一个经典的数独故事来理解这一概念：
零知识性⌗
零知识证明有三种性质，完备性和可靠性不再赘述，我在理解零知识性时遇到了一个误区：地图三染色问题上的零知识证明，可能存在知识泄漏？理由如下：
Prover 需要向 Verifier 提供相邻两个地域的颜色，以便 Verifier 验证；
但是颜色一共只有三种，虽然第二次通过随机数更换了颜色，但如果 Verifier 第二次选择的地域和第一次存在交集，那么 Verifier 可以拿到前后两次颜色的映射；
// 第一种映射
绿色 —> 红色
A —> 棕色
橙色 —> B
// 第二种映射
绿色 —> 红色
橙色 —> 棕色
A —> B
那 Verifier 是不是可以反推回去，拿到第一次 & 第二次的结果？
即第二次棕色的位置，对应第一次的橙色或A色。这样每次我们都有1 / 2的概率可以猜对，最终拿到所有结果。
这样是不是说明存在知识泄漏的风险？当然不是，我们可以通过以下三种方式来证明：
证明1⌗
我们要知道虽然每次都有1 / 2的概率猜对，但整个计算的时间复杂度却是 O(2^n) 级别的，这是一个NP问题。NP的具体介绍不在本文范围内，只需要知道它的计算时间很复杂。
所以 Verifier 基本是无法反推出来的。反过来讲，既然这个NP问题可以应用零知识证明，那通过NP的性质，我们可以得出零知识证明可以应用于所有的NP问题这一结论。
证明2⌗
上面 Verifier 的反推过程，大家不觉得有点眼熟吗？这不就是地图三染色问题的 穷举 解法吗？和零知识证明、知识泄漏并无任何关系。
证明3⌗
下面我们通过理论的角度，也可以验证上面的结论，参考文章。
如果你没有看过上面数独的故事，我建议你先去阅读一遍。故事中提到了一个人为的作弊行为，下面我们用编程来替代人为交互：
我们想象一个这样的程序，假设一个由 Prover 完全操控的验证程序 （当然事实不可能是这样，只是为了模拟作弊），可以在任意节点 倒带回溯，修复该节点的错误，那么 Prover 完全可以通过操控这个验证程序来蒙混过关，欺骗 Verifier。
基于上述背景，我们再来思考两个场景：
- Prover 提供了标准答案给 Verifier 验证；
- Prover 通过回溯欺骗 Verifier，通过验证。
两个场景在 Verifier 的角度看有区别吗？没有，两种场景对于 Verifier 的结果都是正确通过验证。所以假设像误区所提到的那样，Verifier 有一种策略可以获取 Prover 的完整知识。但是在上述第二种场景中 Prover 根本就不知道完整知识(答案)，所以 Verifier 不会获取到任何知识。
而且既然两种场景在 Verifier 的视角并无区别，那么在第一种场景中 Verifier 也不应能获取任何知识。