下图为 Mental Poker over the Telephone[SRA81],文中提出了通过完备的论证方法,来实现对传递信息的隐匿,而非严格的数学证明,该结论为后续零知识证明的可行性奠定了基础。2012年图灵奖获得者Shafi Goldwasser与Silvio Micali首次正式引入了零知识证明(Zero-Knowledge Proof, ZKP)的概念,文章为The knowledge complexity of interactive proof-systems
零知识证明,实际都是通过论证得出,而非严格的数学证明
论证:利用论据(原因,例子,数据)等,验证论点为真(无限接近100%)。交互证明(Interactive Proof)在定义上是允许一个无效证明通过验证的可能性微小但非零概率,而论证即为计算可靠性问题的IP,允许存在不正确陈述的“证明”(需要非常大的算力才能找到)。以计算性问题为前提条件后,一个重要的优势是能够使用(多项式时间安全)的密码学原语。
证明:从空条件集合出发,利用假设法、公理、公设,来证明一个命题的恒为真,每个过程都要详细,确信的100%
定义 :零知识证明(ZKP, Zero-Knowledge Proof)是一方(证明者Prover)向另一方(检验者Verifier)论证某命题的方法。零知识协议是一种协议,它允许你证明你知道一些特定的数学事实,而无需透露有关事实本身的任何信息。在零知识协议中生成的证明称为零知识证明。
-
完备性(completeness):如果 Prover 知道正确的具体信息,他们总是能够做出令人满意的回答;
-
可靠性(Soundness):如果 Prover 不知道正确的具体信息,他们最终会被抓住,换言之,可靠的系统不会允许虚假的陈述被错误地证明为真;
知识可靠性(Knowledge Soundness):是可靠性的更强要求,要求证明者必须真的知道某个特定的信息(比如一个密码或是一个解)。(该点往往是使用者实现,比如有的ZK-Snark系统本身只能是实现可靠性,因为系统内不包含“知识”信息,开发者在该系统上架构,可以实现知识可靠性)
-
零知识(Zero Knowledge):Prover 的回答不会泄露其具体信息,验证者除了正确外,不知道任何其他信息;
值得说明的是,零知识特性是可选的(optional)。例如,zkrollup的实现过程中,一般只会实现SNARK(见ZK-SNARKs章节),而不会引入ZK属性
应用:零知识证明都是针对可计算问题
对于一个判定问题,若存在一个总是在有限步内停机且能够正确进行判定的图灵机,则这个问题是一个 图灵可计算 的问题,否则这个问题是一个 图灵不可计算 的问题。
典型不可计算问题-停机问题:给定
$α$ 和$x$ ,判定$M_α$ 在输入为$x$ 时是否会在有限步内停机。
-
为解决通用可计算问题,设计一个通用框架将问题转化为一个可计算模型(computational model),然后利用零知识证明系统生成证明。在古典零知识证明中,对于像三色图问题,研究人员(数学家)都必须提出一个应用于特定场合的特殊用途/特定的ZK协议,而在现代ZK零知识证明中,。
一个输出
$y$ ,一个任意函数$f$ ,知道一个秘密$x$ ,使得$f(x)=y$ 在此基础上,我们能够在完全隐私的情况下验证任意计算(如货币、数字所有权的转移)。也是因此,程序员才可以上手写逻辑。
-
满足完美零知识证明的不可区分特性。如果 “模拟视图” 和 “真实交互” 通过任意算法无法区分,则称为完美零知识。
计算不可区分加密:限制了任意算法为 多项式时间算法(ploy-time algorithm)
例如,在现代零知识证明中,非对称加密(如椭圆曲线)的数字签名具不具备零知识属性。
如,私钥在一个向量中[s1,s2,s3,...,sN],使用一个普通的椭圆曲线签名可以证明你拥有某个私钥sK,但是一个adversary可以通过遍历这个向量来模拟出你的信息,发现你用的是哪个私钥,零知识需要保证哪怕这个adversary 能够模拟出一些信息,也无法得知用哪个。
进阶:Schnorr签名方案,一个经典的Sigma协议(见承诺方案章节),具有Special Honest-Verifier Zero-knowledge property