零知识证明（ZKP）
密码学中，零知识证明（英语：zero-knowledge proof）或零知识协议（zero-knowledge protocol）是一方（证明者）向另一方（检验者）证明某命题的方法，特点是过程中除“该命题为真”之事外，不泄露任何信息。因此，可理解成“零泄密证明”[1]。例如，欲向人证明自己拥有某情报，则直接公开该情报即可，但如此则会将该细节亦一并泄露；零知识证明的精粹在于，如何证明自己拥有该情报而不必透露情报内容。这也是零知识证明的难点[2]。
若该命题的证明，需要知悉某秘密方能作出，则检验者单凭目睹证明，而未获悉该秘密，仍无法向第三方证明该命题（即单单转述不足以证明）。待证的命题中，必定包含证明者宣称自己知道该秘密，但过程中不能传达该秘密本身。否则，协议完结时，已给予检验者有关命题的额外的信息。此类“知识的零知识证明”是零知识证明的特例，其中待证命题仅有“证明者知道某事”。
零知识证明可以是交互式的，这意味着证明者和验证者根据某种协议交换消息，也可以是非交互式的，这意味着验证者被单个证明者消息所信服，不需要其他通信。 在标准模型中，除了 BPP 问题的琐碎证明之外，需要交互。 在通用随机字符串和随机预言机模型中，存在非交互式零知识证明。 Fiat–Shamir 启发式可用于将某些交互式零知识证明转换为非交互式证明。
定义[编辑 | 编辑源代码]
零知识证明要具备下列三种性质：
- 完备（complete）
- 若所要证之事为真，则诚实（意即依协议行事）的证明者能说服诚实验证者。
- 健全（sound）
- 若命题为假，则作弊证明者仅得极小机会能说服诚实验证者该事为真。
- 零知识（zero-knowledge）
- 若命题为真，则验证者除此之外，过程中没有得悉任何其他信息。换言之，仅知命题为真（而不知秘密本身）已足以“想像”出一个交互的情境，其中证明者的确知道该秘密。此性质能严格定义为：每个验证者皆有相应的模拟器，输入欲证事实时，无需求助于证明者，已可输出一套通信誊本，看似诚实验证者与证明者的通信记录。
前两种性质，更广义的交互式证明系统亦应具备。第三种性质使该交互证明称为零知识。
零知识证明不算数学证明，因为尚允许有很少（但非零）概率，令作弊证明者能向验证者“证明”假命题。该概率称为可靠度误差（soundness error）。换言之，零知识证明是概率“证明”，而非决定性。不过，也有技巧将可靠度误差压到忽略不计。
零知识的严格定义，需要抽象计算模型，如常见的图灵机。设、、为三部图灵机。某语言的交互式证明系统为零知识，意思是对任意概率多项式时间（PPT）验证者，皆有PPT模拟器使得：
其中是与间交互的全记录。证明者通常假设具无限计算能力（实践上，常为概率图灵机）。直观理解，某交互证明系为零知识，即对任意验证者，皆存在某高效模拟器（视乎而定），给定任何输入，可以重现与间的对话。定义中的辅助串，是用作放置任何“前备知识”（包括预知运行时掷得的硬币结果）。定义推出，不能利用预知串从与的对话中发掘出信息，因为若给予该串，则也同样可以重现与间的对话。
以上为完美零知识的定义。若将定义中，验证者的视角（view）与模拟相等之要求，改为仅要求计算上无法分辨，则得到计算零知识的定义。
计算示例[编辑 | 编辑源代码]
离散对数[编辑 | 编辑源代码]
前段概念适用于较实际的密码学场景。设小静欲向阿严证明，自己知道某群某指定元素的离散对数。
例如，给定数、素数、生成元，小静希望证明自己知道某数使，而不泄漏。事实上，知晓之事，本身可用作身份证明，即小静可借此证明该值是由她先暗中选某随机值，再计算，公诸所有潜在的验证者。如此，若某人证明自己知道，则相当于证明自己即小静，因为学者相信离散对数很难计算，即其他人无法从倒推出值。
证明协议如下：每轮，小静预备随机数，计算，将该值传予阿严。收到后，阿严随机请求下列两者之一：小静公开值，或值。单独看任何一个值，其分布皆是均匀随机，所以协议每轮皆不泄露任何机密。
阿严可以验证所得回应。若问，则可以计算，检查是否等于。若问，则可以计算，而该值应当等于，所以亦验证值是否满足该条件。若小静确实知道值，理应很易回答阿严的任一条问题。
若小静预知阿严采用何种盘问，则很易作弊，在不知的情况下，向阿严假装自己知道：若她知道阿严将要问，则如常继续，选，计算，告知阿严值；她可以答出值。另一方面，若她知道阿严将问，则取随机一个值，计算，然后发送值予阿严（阿严会以为该值为值）。当阿严要求公开值时，小静公开，但这足以让阿严验证结果，因为他计算的值实为，是等于，因为正是小静一早乘上的逆元而计出。
然而，若有某轮验证中，阿严的问题与小静预估的有出入，则小静无法计算出要答的结果（假定该群的离散对数问题难解）。若她拣选并公开，则无法作弊给出服众的值来通过阿严的检查，因为不知道。又若她拣选值，伪装成，则要回答公开值的离散对数，但她无法回答，因为该值是由已知值乘出，而非某已知值以为底的幂，所以她不能计出其离散对数
所以，作弊的证明者仅得概率通过某轮验证。重复足够多轮，成功作弊的概率可压到任意小。
撮要[编辑 | 编辑源代码]
小静要证知道值（如其密码）。
- 小静与阿严约定某素数，及域的乘法生成元。
- 小静计算，发送予阿严。
- 重复以下步骤若干次：
- 小静选某个均匀随机数，计算，发送予阿严。
- 阿严问小静或，二选其一。若问前者，则阿严验证。若问后者，则他验证。
之值，可视为的加密。若确为随机，在至间均匀分布，则也同样均匀分布，所以不会泄漏任何关于的信息（见一次性密码本）。
大图的哈密顿环[编辑 | 编辑源代码]
下列方案是曼纽尔·布卢姆提出。
此场境中，小静知道某大图的哈密顿环。阿严知道但不知该环（比如说小静将该图打印给阿严）。一般相信，找大图的哈密顿环，在计算上并不可行，因为相应的决定问题已证为NP完全。小静欲证自己知道该环，但不想泄漏出去，原因可能是阿严打算向小静买，但付款前希望先验证小静知道；也可能是全世界只得小静知道该环，所以小静向阿严证明此事，是为向阿严核实自己身份。
小静为证明自己知道哈密顿环，与阿严作若干轮验证。每轮中：
- 一开始，小静预备图，是与同构（即与一样，但顶点的标签不同）。若小静知道的哈密顿环，则因为与间的同构由她拣选，她很易找到中对应的哈密顿环。
- 小静秘诺。此处可选任意密码学秘诺机制，甚或直接将的顶点编号，然后对的每条边，将两端编号写在小纸片上，反转盖在台面。总之，秘诺目的是使小静此后无法窜改，但同时不让阿严提早知道的信息。
- 阿严随机问小静以下两事之一：给出与间的同构（见图同构问题）；或给出的哈密顿环。
- 若问两图的同构，则小静先展示（将台面全部纸翻开），并给出顶点与顶点的对应表。阿严可以验证该对应关系是否满足图同构的条件。
- 若问哈密顿环，则小静只翻开在的哈密顿环上的纸片。如此，阿严已可验证有哈顿顿环。
秘诺一步必须使阿严在第二种情况能验证该环确实由的边构成。一种做法是，逐条边分别秘诺。
完备[编辑 | 编辑源代码]
若小静确知中的哈密顿环，则阿严询问同构时，她很易回答（该同构为她所选），而阿严问中的哈密顿环时，她同样很易回答（有哈密顿环，与间的同构为所她选，所以可以找到中对应的环）。
健全[编辑 | 编辑源代码]
若小静不知哈密顿环，则只能预先猜测阿严会问何种问题，相应准备某个与同构的图，或另一个不相关的哈密顿图。然而，因为她不知的哈密顿环，所以无法同时做两件事。于是，若以上验证重复次，则小静蒙混过关的概率仅得，从而实际意义上，只需合理多轮验证，已使造假者寸步难行。
零知识[编辑 | 编辑源代码]
小静的回答不泄漏原图的哈密顿环，因为每一轮，阿严只会得悉与的同构，或是的哈密顿环，两者之一，但他需要对同一个同时得知两者，才能构造出中的哈密顿环。如此，只要小静每轮预备一幅不同的图，就能保密。若小静不知的哈密顿环，但不知为何已事前得知阿严每轮会问的问题，则她可以作弊。例如，若小静预知阿严该轮会问的哈密顿图，则大可以秘诺一幅与无关的哈密顿图。与之类似，若小静预知阿严会问同构表，则她可以随便预备一幅与同构的图（其中她不知道任何哈密顿图）。阿严根本无需小静在场，亦可独自想像出自己将见的场面，因为他清楚自己将会问什么，将见的仅是一个环（而不显示图的其他部分）或一幅与同构的图，即阿严可以自行模拟该协议。因此，阿严从每一轮验证揭露之事，无法得到任何关于哈密顿环的信息。
生活示例[编辑 | 编辑源代码]
山洞中，小静随机选择A路或B路，阿严则在洞外等候
阿严选一个出口
小静准确出现在阿严所选的出口出现
以下有一个熟知的故事，总结零知识证明的若干重要概念。故事最早由Jean-Jacques Quisquater及同事发表于《如何向你的孩子解释零知识协议》。设有小静（证明者）和阿严（验证者）两人。
故事中，小静发现洞穴中某扇魔法门的开门暗号。洞穴呈环形，入口在一侧，对侧则有魔法门隔断。阿严想知小静是否已知该暗号，但小静很注重隐私，不希望泄露暗号予阿严，也不想全世界知道她有暗号之事。
两人分别将入口左右两条通道标示为A路、B路。首先，阿严在洞口外，待小静进入洞内。小静自行选择行A路或B路，但阿严不准窥视小静所选为何。然后，阿严行入洞穴，均匀随机喊出A路或B路，表明希望小静由该方向返回。假若小静确实知道暗号，则很易达成，因为即使起初所选不是同一条路，她也可以开门通过，从另一条路返回。
然而，若她其实不知道暗号，则祗有一半概率能从阿严所选的方向返回，因为阿严随机选A路和B路，恰有一半机会选中起初小静进入的方向。若两人重复以上过程，比如连续20次，则小静靠运气全部碰巧从正确方向返回的概率极小，为220分之1。
所以，若小静连续多次从阿严所选的方向返回，则阿严可以推断，小静很可能知道暗号。
以下考虑第三方的观点。即使假设阿严佩戴隐蔽的镜头，录影所见的整个过程，镜头所见亦只有阿严喊“A！”小静从A路返回；或阿严喊“B！”小静从B路返回。此种片段极易由两人共谋伪造（祗需小静与阿严事前商讨多次验证中阿严将选该串A、B的次序），从而对第三方而言，不具说服力，即阿严无法借此向第三方证明小静知道暗号。事实上，即使录影换成现场在阿严身旁监视亦同，因为两人可能一早已协调彩排好。
但是，若阿严在镜头前掷硬币，然后按该硬币喊A或B，则协议不再零知识。该段录影可能足以说服第三方，两人无法伪造，因为阿严难以准确掷出预定的AB次序。于是，虽然证明过程没有泄露暗号予阿严，但是阿严可借此说服世人，证明小静知道暗号，与小静起初的意欲完全相反。不过，数字的密码学中，“掷硬币”以伪随机数生成器实现，类似于一枚结果已预定好的硬币，但该结果（由其随机种子决定）仅有硬币主人知道。若阿严的硬币实际是以此法运作，则协议又恢复为零知识协议，因为两人又有可能共同伪造“实验”结果，所以使用伪随机数生成器与掷真硬币不同，前者不会向世人泄露小静知道暗号。
还有另一种做法，小静以独一次实验已可向阿严证明自己知道暗号，而不泄漏。方法是，两人一同走入洞口，然后阿严目送小静沿A路走，没有原路折返，但从B路返回。如此，小静必然已向阿严证明自己知道暗号，而没有告知阿严暗号。不过此种证明亦非零知识：若第三方观察到过程，或阿严有录影，则该证明对第三方具说服力。换言之，小静无法宣称自己与阿严串通，所以无法向第三方说该证明无效。如此，小静无法控制何人得知她拥有暗号之事。
零知识条件的变式[编辑 | 编辑源代码]
“零知识”的定义有若干变形，分别在于如何严谨定义模拟结果“看似”真实的交互记录：
- 完美零知识（perfect zero-knowledge）
- 模拟器与真正交互产生的概率分布完全相等。离散对数示例即属此类。
- 统计零知识（statistical zero-knowledge）
- 两个分布并非完全相等，但统计上接近，即有某个可忽略函数，使该两列分布在任意集合取值的概率差，皆小于该函数。
- 计算零知识（computational zero-knowledge）
- 无高效算法分辨两个分布。
零知识证明协议[编辑 | 编辑源代码]
最流行的交互式或非交互式零知识证明（例如 zk-SNARK）协议可大致分为以下四类：简洁的非交互式知识论证（SNARK）、可扩展的透明知识论证（STARK）、可验证多项式委派（VPD）和简洁的非交互式论证（SNARG）。 下面提供了零知识证明协议和库的列表，以及基于透明度、通用性、可信赖的后量子安全性、编程范式的比较。 透明协议是不需要任何可信设置并使用公共随机性的协议。 通用协议是不需要为每个电路进行单独的可信设置的协议。 最后，可信的后量子协议是不容易受到涉及量子算法的已知攻击的协议。
| 系统名称 | 发布年份 | 协议 | 透明性 | 通用性 | 可信的后量子安全 | 编程模式 |
|---|---|---|---|---|---|---|
| Pinocchio | 2013 | zk-SNARK | 否 | 否 | 否 | 过程式的 |
| Geppetto | 2015 | zk-SNARK | 否 | 否 | 否 | 过程式的 |
| TinyRAM | 2013 | zk-SNARK | 否 | 否 | 否 | 过程式的 |
| Buffet | 2015 | zk-SNARK | 否 | 否 | 否 | 过程式的 |
| ZoKrates | 2018 | zk-SNARK | 否 | 否 | 否 | 过程式的 |
| xJsnark | 2018 | zk-SNARK | 否 | 否 | 否 | 过程式的 |
| vRAM | 2018 | zk-SNARG | 否 | 是 | 否 | 汇编语言 |
| vnTinyRAM | 2014 | zk-SNARK | 否 | 是 | 否 | 过程式的 |
| MIRAGE | 2020 | zk-SNARK | 否 | 是 | 否 | 算术电路 |
| Sonic | 2019 | zk-SNARK | 否 | 是 | 否 | 算术电路 |
| Marlin | 2020 | zk-SNARK | 否 | 是 | 否 | 算术电路 |
| PLONK | 2019 | zk-SNARK | 否 | 是 | 否 | 算术电路 |
| SuperSonic | 2020 | zk-SNARK | 是 | 是 | 否 | 算术电路 |
| Bulletproofs | 2018 | Bulletproofs | 是 | 是 | 否 | 算术电路 |
| Hyrax | 2018 | zk-SNARK | 是 | 是 | 否 | 算术电路 |
| Halo | 2019 | zk-SNARK | 是 | 是 | 否 | 算术电路 |
| Virgo | 2020 | zk-SNARK | 是 | 是 | 是 | 算术电路 |
| Ligero | 2017 | zk-SNARK | 是 | 是 | 是 | 算术电路 |
| Aurora | 2019 | zk-SNARK | 是 | 是 | 是 | 算术电路 |
| zk-STARK | 2019 | zk-STARK | 是 | 是 | 是 | 汇编语言 |
| Zilch | 2021 | zk-STARK | 是 | 是 | 是 | 面向对象的 |
应用[编辑 | 编辑源代码]
身份验证[编辑 | 编辑源代码]
零知识证明的研究，是受身份验证系统启发。验证时，一方要向另一方证明自己身份，通常藉赖证明自己持有某种袐密（如通行密码），但不希望对方知悉该袐密，称为零知识知识证明。不过，通行密码一般不是太短，就是不够随机，不能用于许多零知识知识证明方案。零知识通行码证明就是有考量密码长度限制的一类零知识知识证明。[来源请求]
2015年4月，Sigma协议（“其中之一”证明，英语：one-out-of-many proofs）面世。2021年8月，美国网络基建、安全公司Cloudflare采用该种证明机制，以供应方硬件为私人网络提供验证服务。
道德行为[编辑 | 编辑源代码]
密码学协议之中使用零知识证明，可以在不退让隐私的情况下，确保各方诚实。粗略言之，方法是迫用户零知识地证明，其所作所为是依足协议。由健全性，用户必先确实跟从协议，才能服众。又由于证明是零知识，此过程并无犠牲用户的隐私。
核裁军[编辑 | 编辑源代码]
2016年，普林斯顿等离子物理实际室与普林斯顿大学展示一个技巧，或许适用于未来的核裁军谈判。其特点是，无需揭露某对象内部的机密构造，亦可允许督查员判断该对象是否核武器。
区块链[编辑 | 编辑源代码]
零知识证明用于小零币与大零币协议中，最终于2016年发展成小零币（2020年改称飞熔币）和大零币两种加密货币。小零币内置有混币模型，以确保匿名，且该模型无需信任任何点对点用户或中央集权混币者。用户可以用另一种基准币交易，也可以将该币卖出买入小零币。大零币协议的模型也类似（该变式称为非交互式零知识证明），而且可以掩盖交易额，但小零币则不能。大零币的交易数据如此隐密，所以与小零币相比，较不易受到隐私计时攻击。不过，此层额外隐私，可能导致不能追踪假币，倘因此造成大零币供给的超通涨，可能无法侦测到。
2018年，防弹证明（bulletproofs）面世。其改进自非交互式零知识证明，不再需要可信的安装环境。其后，实现成“结舌”协议（Mimblewimble protocol，Grin和Beam两种加密币皆出自该协议）和门罗币。2019年，飞熔币实现Sigma协议，是对应小零币协议无可信环境的改进。同年，飞熔币引入莱兰托斯协议（Lelantus protocol），更自Sigma协议改进，隐去交易的源头与金额。
去中心化标识符[编辑 | 编辑源代码]
在本质上，零知识证明可以增强身份共享系统中的隐私性，而身份共享系统容易受到数据泄露和身份盗用的影响。 当集成到去中心化标识符系统中时，ZKP 会在 DID 文档上增加额外的加密层。
类型[编辑 | 编辑源代码]
零知识证明有各种类型：
- 知识证明：知识隐藏在指数中，如上例所示。
- 见证者不可区分证明：验证者无法知道用于生成证明的哪个见证者。
零知识证明方案可以由各种密码学原语构建，例如基于哈希的密码学、基于配对的密码学、多方计算或基于格的密码学。
沿革[编辑 | 编辑源代码]
零知识证明最早由莎菲·戈德瓦塞尔、希尔维奥·米卡利、查尔斯·拉克福三人于1985年发表，论文题为《交互式证明系统的知识复杂度》。该论文引入交互式证明系统的IP复杂度类，并构想出“知识复杂度”概念，衡量证明过程中，由证明者传递予验证者的知识量。三人亦给出首个具体问题的零知识证明，即零知识地证明某数不是模 m 的二次剩余。连同鲍鲍伊·拉兹洛与什洛莫·莫兰的另一篇论文，戈-米-拉三氏的论文发明了交互式证明系统。为此，五人同获1993年首届哥德尔奖。
引述戈-米-拉三氏：
该额外知识基本为0的情况尤其值得关注。我等证明，可以交互地证明某数非模 m 的二次剩余，而发布零额外知识。其出奇之处是，若不给定 m 的分解，则无高效算法判别某数是否模 m 的二次剩余。更甚者，任何已知的NP证明皆要表明 m 的素因数分解。这就表明，在证明过程中添加交互，可能减少证明某定理所必须交流的知识。
二次非剩余问题既有NP算法又有反NP算法，故位处NP与反NP两类之交集中。其后找到有零知识证明的若干个问题，亦具同样的性质，例如欧迪·戈德赖希未经正式出版的证明系统，可以验证某数（为两个未知素数之积）不是布卢姆整数，即并非两个模4余3的素数之积。
欧迪·戈德赖希、希尔维奥·米卡利、阿维·威格森更进一步证明，假定存在无懈可击的加密法，则可以造出三色图着色问题的零知识证明系统，而该问题本身为NP完全。又因为每个NP问题都可以高效化归成该NP完全问题，所以在前述假定下，所有NP问题皆有零知识证明。需要该假定的原因是，正如前节示例，需要有秘诺的手段。若存在单向函数，则的确有牢不可破的加密法。此为广泛引用的充分条件。另外也可能有物理方法实现。
更上一层楼，他们亦证明，图不同构问题，即图同构问题之补，有零知识证明。该问题已知属于反NP，但未知是否属于NP或其他实际可行的复杂度类。更一般地，罗素·英帕利亚佐、莫迪凯·容[译名请求]二人，与米高·本-奥尔（Michael Ben-Or）及同事，两组证明：同样假设存在单向函数或牢不可破的加密，则任何属于IP（已证等于PSPACE）的问题，皆有零知识证明。换言之，任何命题若可藉交互系统证明，则可零知识证明。
许多理论家不希望假设不必要的条件，所以试图在不假定单向函数的条件之下，证明同样的结论。有种做法称为“多证明者交互式证明系统”（见交互式证明系统），即有多个独立的证明者，而非仅得一个。验证者可以将证明者逐个孤立，然后诘问，以免被作弊证明者误导。无需任何难解假设，已可证明在此系统中，任何NP问题皆有零知识证明。
后来发现，互联网等同时执行多个协议的环境中，较难构造零知识证明。研究并发零知识证明的先驱是辛西娅·德沃克、莫尼·纳奥尔、阿米特·萨海。此类研究之中，重要成果有证据不可辨协议。与零知识相比，其性质较弱：可能有多种证据供证明者选择采用何者作证，此时仅要求验证者无法分辨证明者选择为何，但证明者可以泄漏部分信息，如全体证据组成的集合。尽管失去零知识性质，但此类协议的好处是，并发时不会遇到此前提及的问题。
变式尚有非交互式零知识证明。曼纽尔·布卢姆、保罗·费尔德曼（Paul Feldman）、米卡利证明，若证明者与验证者共有一条随机字符串，则可以达成计算零知识，而毋须交互。
参考链接[编辑 | 编辑源代码]
- ↑ 區塊鏈的「零知識證明」是什麼東西？｜天下雜誌
- ↑ What is a zero-knowledge proof and why is it useful? Written by Lexie