零知识学习零知识证明

杂谈

Math is law !

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

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

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

概念

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

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

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

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

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

零知识性

零知识证明有三种性质,完备性和可靠性不再赘述,我在理解零知识性时遇到了一个误区:地图三染色问题上的零知识证明,可能存在知识泄漏?理由如下:

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

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

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

图片来源: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

即第二次棕色的位置,对应第一次的橙色或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 也不应能获取任何知识。