前言
在讲通过零知识证明构建零知识协议之前，打算先讲一些可能会用到的概念，因此单独开一篇文章来写
希望通过写一些概念来加深自己的理解，同时之后如果忘了也方便回顾
可能会比较硬核，尽量写的清楚明白，但是仅仅是介绍概念，不包括证明或者更复杂的知识
零知识证明的特性
零知识证明有三个特性
- 完备性（Completeness）：Prover在有知识的情况可以通过Verifier的验证
- 可靠性（Soundness）：Prover在没有知识的情况下不能通过Verifier的验证
- 零知识性（Zero Knowledge）：Prover在与Verifier交互的过程中不会泄露关于知识的任何信息
上面三个特性，简单来说就是，完备性确保有知识的Prover一定能让Verifier确信，也就是确保证明一定可以完成，可靠性是确保了Verifier的利益，如果Prover没有知识，则一定会被Verifier发现（恶意的Prover一定会失败），第三个是确保Prover的利益，交互过程中无论如何，Verifier都不能从Prover那里得到知识（恶意的Verifier一定会失败）
计算复杂性分类
最初不打算讲这个问题，因为害怕自己讲不明白，容易误导读者
但是这又是一个不可避免的问题，又必须讲，所以打算简单写一下吧，不写太多很专业的术语，主要目的是有助于后面的理解
P
多项式时间类（Polynomial Time），此类问题可以用经典计算机很容易地求解（很容易和之前文章中提到的多项式时间对应）
比如冒泡排序，判断图的欧拉性等问题
NP
非确定多项式时间类（Non-Polynomial Time），此类问题可以用经典计算机很容易地验证一个答案，但是不能很容易地求解这个问题的答案
对于所有属于NP类的问题，可以证明这些问题都有一个短证书（short witness），短证书意味着可以在多项式时间内（很容易地）验证这个证书
常见的NP问题如判断二次剩余，图的哈密顿性判定，旅行商问题等
PSPACE
多项式空间（Polynomial Sapce），SPACE可以简单理解为内存空间，PSPACE类仅关心这个算法占用的内存空间，而不考虑时间问题
P和NP类所有的问题都属于PSPACE类
PP
Probabilistic Polynomial，概率多项式
这里的概率指的是概率图灵机（属于一类NDTM，但不完全是），和NDTM不同的是，它的随机性服从某一特定的分布（区别在于，NDTM只要有一个分支停机，则NDTM停机，而概率图灵机对于相同的输入，得到的结果可能是接受，或者拒绝，或者不停机）
概率多项式问题就是只概率图灵机可以在多项式时间内解决的问题，简单来说就一个概率性的、多项式时间的算法
BPP
有限错误概率多项式时间类（Bounded error Probabilistic Polynominal Time），其中Bounded-error表明有限错误，意思就是BPP是概率图灵机在多项式时间内可以解决的问题的集合，但是对于所有的输入，其输出结果有一定的错误概率，但是这个概率在一定的范围内（通常是(0,1/2)之间的一个数）
也有的书把这个称为双边错复杂类，比如说，ZK证明一个合数N是两个不相同的素数的乘积，采用二次剩余的方式，而对于一个数，其完系中二次剩余与非二次剩余各占一半，因此证明过程中Verifier发起的随机提问只有少于3/8的询问为二次剩余，从而产生双边错误
ZPP
零边错复杂性类（Zero error Polynominal Time），零边错不允许给出错误的判定，但是允许输出失败
轮效率
和前面的文章介绍到的一样，ZK协议存在差错，但是可以通过顺序重复多轮来降低差错的概率，但是执行越多的轮次意味着效率会越低
根据单轮获得的差错概率，可以客观的衡量一个ZK协议的轮效率，单论差错概率越小，意味着协议需要重复执行的次数越少，同时代表协议的轮效率越高
根据不同的单轮差错概率，可以分为三类不同轮效率的协议
本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正
对数轮
如Schnorr身份识别协议，单轮中存在常量差错概率，如1/2或loglogn（部分协议中logn是一个安全参数，因此将loglogn视为一个常量），为了使差错概率可以降低到可忽略的小，需要对这些拥有常量差错概率的协议重复执行logn轮，因此称为对数轮协议
多项式轮
有些ZK协议具有双边差错的特性（如上面提到的ZK证明一个合数N是两个不同素数的乘积），因此需要更多的轮数来达到同等的可忽略的小量
除了双边差错的特性，还有一些协议会在每一轮中调用另一个对数轮协议，这也会导致总体的轮效率变成多项式轮
常数轮
如果一个协议在少许常数轮（或单轮）就可以达到可忽略的小的差错概率，那就没有必要重复对数或更多的轮次
通过结合比特承诺等密码学原语，可以将协议降低到对数轮
后记
不知道写什么好，在模拟和比特承诺的概念理顺前，不是很想写新的内容，主要是想摸鱼，因此写一篇水一下
而且最近在听The 9th BIU密码学冬令营的零知识部分，讲的比较详细，顺便记录了里面的一些内容，应该会帮助我理解吧
本篇文章主要是介绍计算复杂性的一些知识，还有零知识的一些术语，介绍计算复杂性的主要目的是，计算复杂性是现代密码学的基础，很多密码学的理论，包括问题的难解性，都是基于计算复杂性构建起来的
比如说确定机和非确定机这两个概念，非确定机确实很强大，在破译加密算法的时候效率非常高，因此需要将加密算法设计成只能由确定机完成破译而不是非确定机（PPT也不行），以此来提高破译的难度
不过目前的工作主要都是将P≠NP当成必要条件来用，因为还没能证明，所以不能当成充分条件，因此计算复杂性里面的定理都是如果P≠NP，则...而不是因为P≠NP，所以...
因此Scott Aaronson才会如是说到：如果P==NP，应该很容易证明，但是如果P!=NP，应该比较难证明，因此P!=NP会让数学现实更一致一些
本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正
参考文章
$[1]$ 一文讲清计算复杂性分类](https://zhuanlan.zhihu.com/p/47897608))
$[2]$ 02. Zero-KNOWLEDGE for All NP【对于所有NP问题的零知识】_吃芒果干的熊孩子的博客-CSDN博客
$[3]$ 陈原.计算复杂性理论导引$[M]$.西安电子科技大学出版社.
$[4]$ （以）Odeb Goldreich著；温巧燕，杨义先译.密码学基础$[M]$.北京：人民邮电出版社.2003.
$[5]$ 计算复杂性（6）——世界难题：非确定型图灵机，NP类 - 知乎 (zhihu.com)
$[6]$ Wiki-Computational complexity theory
$[7]$ Bristol的第7篇密码学_weixin_30814223的博客-CSDN博客
$[8]$ Wiki-Probabilistic_Turing_machine
$[9]$ Wiki-P_versus_NP_problem