零知识证明学习笔记
零知识和证明
零知识证明是构建信任的重要技术，也是区块链这个有机体中不可缺少的一环。
零知识证明是打通链上数据与链下计算的关键技术，也是实现链上数据隐私保护的重要途径。
古希腊：「证明」 == 「洞见」
二十世纪初：「证明」 == 「符号推理」
六十年代：「证明」 == 「程序」
八十年代：「证明」 == 「交互」
交互式证明系统的概念：通过构造两个图灵机进行「交互」而不是「推理」，来证明一个命题在概率上是否成立。
交互证明的表现形式是两个（或者多个图灵机）的「对话脚本」，或者称为 Transcript。而这个对话过程，其中有一个显式的「证明者」角色，还有一个显式的「验证者」。其中证明者向验证者证明一个命题成立，同时还「不泄露其他任何知识」。这种就被称为「零知识证明」。
证明凝结了「知识」，但是证明过程确可以不泄露「知识」，同时这个证明验证过程仍然保持了简单、机械，并且有限性。
零知识证明技术可以解决数据的信任问题，计算的信任问题！
零知识证明技术可以「模拟」出一个第三方，来保证某一个论断是可信的
零知识证明的用处：
- 数据的隐私保护
- 计算压缩与区块链扩容
- 端到端的通讯加密
- 身份认证
- 去中心化存储
- 信用记录
- 构造完全公平的线上数字化商品的交易协议
- 更多的例子，可以是任何形式的数据共享，数据处理与数据传输。
举例：地图三染色问题
信息 vs. 知识
- 信息 「Information」
- 知识 「Knowledge」
- 「知识」是与「计算难度」相关，而「信息」则不是
- 「知识」是与公共所知的东西有关，而「信息」主要与部分公开的东西有关
可验证计算与电路可满足性问题
我们平时跑的（没有死循环）代码，都可以用算术电路来表示。
所谓的电路可满足性就是指，存在满足电路的一个解。如果这个解的输出值等于一个确定值，那么这个解就能「表示」电路的计算过程。
「零知识的电路可满足性证明协议」提供了一种最直接的保护隐私/敏感数据的技术
所有的证明都体现了「证明」与「验证」的「不对称性」。
模拟
安全的定义与不可区分性
「安全」需要有一个数学意义上的严格定义
完美安全：假设你是一个攻击者，你通过密文获取不到任何有价值的信息，破解的唯一手段就是靠瞎蒙。
语义安全：假设你是一个攻击者，你通过密文在多项式时间内计算不出来任何有价值的信息。
注：不可区分性是概率意义上的不可区分；在学术上，它可以分为「完全不可区分」，「统计不可区分」，还有「计算不可区分」
证明的零知识过程，等价于构造（寻找）一个「模拟」算法，这个算法能够让模拟器来模拟出一个「没有知识」的理想世界。如果这个算法存在，而且两个世界不可区分，那么就证明完毕。
模拟器其实只是一个图灵机。
证明零知识的过程，就是要寻找一个算法，或者更通俗点说，写出一段代码，它运行在外部计算机系统中，但是实现了虚拟机的功能。而且在虚拟机中，需要有一个不带有「知识」作为输入的 Zlice，可以骗过放入虚拟机运行的 Bob。
计算机科学中有两个方法论至关重要，第一个是「抽象」，第二个是「模拟」
知识
「零知识证明」并不是通过给出一个不允许发生的事件列表来定义，而是直接给出了一个最极致的「模拟条件」。
所谓「模拟条件」是指，通过「模拟」方法来实现一个「理想世界」，使之与「现实世界」不可区分；而由于在理想世界中不存在知识，所以可以推导出结论：现实世界满足「零知识」。
只有「知识」在存在的前提下，保证「零知识」才有意义
弱一些的「零知识」性质——「SHVZK」
可靠性
完备性
零知性
注：并不是所有的可靠性都必须要求存在抽取器算法。采用抽取器来证明可靠性的证明系统被称为「Proof of Knowledge」。
If you would be a real seeker after truth, it is necessary that at least once in your life you doubt, as far as possible, all things. 如果你是一个真正的真理探求者，在你人生中至少要有一次，尽可能地质疑所有的事情。 —— 笛卡尔
大体上说，plonk和很多零知识证明的概念基本上都是把一个逻辑的问题变成多项式，通过多项式的代数方法来完成证明。
1 电路 -> 多项式
2 多项式承诺
证明多项式满足关系式
零知识证明是证明数学的一个运算。
加法门 乘法门 常数门
有限域
挑战
通过随机数挑战是交互式零知识证明的「信任根基」。
非交互式零知识证明，英文是 Non-Interactive Zero Knowledge，简称 NIZK。它意味整个证明被编码为一个「字符串」，它可以写到一张纸上，通过邮件、聊天工具等各种方式随意发送给任何验证者，字符串甚至可以放在 Github 上随时供大家下载验证。
- 交互式证明，只能取信于一个验证者；而 NIZK 可以取信于多个验证者，以至所有人。
- 交互式证明，只能在交互的那个时刻有效；而 NIZK 将始终有效。
NIZK 不仅可以跨越空间，还能跨越时间
不严格地说，数字签名方案相当于在证明（1）我拥有私钥，并且（2）私钥和消息进行了关联计算。
而采用 Hash 函数的方法来把一个交互式的证明系统变成非交互式的方法被称为 Fiat-Shamir 变换[5]，它由密码学老前辈 Amos Fiat 和 Adi Shamir 两人在 1986 年提出。
- 随机预言机每次对于新字符串返回的是一个具有一致性分布的「真」随机数
- Hash 函数计算的结果并不是一个真正具有一致性分布的随机数
在现实世界中，**真正的随机预言机不存在！**为什么呢？ 事实上，一个 Hash 函数不可能产生真的随机数，因为 Hash 函数是一个「确定性」算法，除了参数以外，再没有其它随机量被引入。
而一个具有密码学安全强度的 Hash 函数「似乎」可以充当一个「伪」随机预言机。那么合并后的安全协议需要额外增加一个很强的安全假设，这就是：
假设：一个密码学安全的 Hash 函数可以近似地模拟传说中的「随机预言机」
因为这个假设无法被证明，所以我们只能信任这个假设，或者说当做一个公理来用。插一句， Hash 函数的广义抗碰撞性质决定了它的输出可以模拟随机数，同时在很多情况下（并非所有），对 Hash 函数实施攻击难度很高，于是许多的密码学家都在大胆使用。
不使用这个假设的安全模型叫做「标准模型」，而使用这个假设的安全模型当然不能叫「非标准模型」，它有个好听的专有名词，叫做「随机预言模型」。
世界上有两种不同类型的人，喜欢甜豆花的，不喜欢甜豆花的。同样，世界上的密码学家分为两种，喜欢随机预言模型的，和不喜欢随机预言模型的
SHVZK 要求验证者诚实，而 NIZK 则不再对验证者有任何不现实的要求，因为验证者不参与交互，所谓要求诚实的验证者这个问题就不复存在。
当 Schnorr 协议摇身一变，变成非交互零知识证明系统之后，就真正的「零知识」了。
但模拟器总要具备某种「超能力」，从而能够构建信任的「根基」
在具体实现中，随机预言需要用一个具有密码学安全强度的 Hash 函数（不能随便选，一定要采用密码学安全的 Hash），而 Hash 函数的参数应该是之前所有的上下文输入
但是，Fiat-Shamir 变换只能在「随机预言模型」下证明安全，而用 Hash 函数实现随机预言的过程是否安全是缺少安全性证明的。不仅如此，「随机预言模型」下安全的协议可能是有不安全的，已经有人找到了一些反例[8]；更不幸的是，S. Goldwasser 与 Y. Tauman 在 2003 年证明了 Fiat-Shamir 变换本身也是存在安全反例的[9]。但是这并不意味着 Fiat-Shamir 变换不能用，只是在使用过程中要非常小心，不能盲目套用。
门约束
秘密
- 「交互」：验证者通过多次反复挑战，把证明者作弊概率降低到一个极小的值
- 「隐藏随机性」：验证者产生让证明者无法预测的随机数进行挑战
如何通过一段共享的字符串去除「交互」与「隐藏随机性」。这个字符串必须事先由「第三方」来随机产生，这就是传说中的「公共参考串」（Common Reference String，简称 CRS）。
当我们讨论「零知识证明」时，要考虑带「知识」的 NP 类问题。大家都知道，P 问题是「确定性图灵机」多项式时间内可以求解的复杂类，它的执行路径对于输入 x是一个线性的状态转移。而 NP 问题是「不确定性图灵机」多项式时间可以求解的问题类。所谓的不确定性图灵机，就是它每次往前走一步是不确定的，有很多个选择，只要任何一个执行路径能到达终止状态，就表示它解决了该问题 x。换句话说，它的执行轨迹是一棵树。那么如果我们把不确定性图灵机每一步的路径选择记录下来（这个执行路径的记录叫做 witness，也就是我们反复提到的「知识」），那么把(x, witness)交给一个确定性图灵机，那么它也能在多项式时间内解决掉 x 问题。
CRS 的使命就是让「模拟器」与「验证者」不平等。怎么做呢？隐藏一些「秘密」进去。
把「隐藏比特串」中的隐藏特性去除，变成「公共参考串」CRS。这里我们要借助一个密码学工具 —— Trapdoor Permutation，陷门置换。
陷门置换可以对公共参考串和Hidden Bits 进行相互转换。
Hidden Bits 方法是目前已知唯一的办法，(1) 基于「一致性分布」的共享 CRS，(2) 实现任意 NP 语言的 NIZK Proofs（Not Arguments!）。
现在流行的热词 —— zkSNARK 中的 AR正是指代 Argument。
NIZK Argument 可以实现 O(1) 常数级长度的证明，即与 witness 的长度无关。然而这需要隐藏更多的秘密到 CRS 中。