【 BlockChain 】零知识证明
一、零知识证明起源
“零知识”的概念最早在80年代由麻省理工学院的研究人员 Shafi Goldwasser，Silvio Micali 和 Charles Rackoff 所提出。当时这些人正在研究与交互证明系统相关的问题——即一种理论系统，使得甲方（证明者）可以和乙方（验证者）交换信息，并借此说服乙方接受（通过验证）某个数学论述为真 [作者注1]。
在Goldwasser等人之前，这个领域的研究工作主要聚焦在加强证明系统的可靠性（Soundness）。也就是说原先大家都假设，会有恶意的证明者试图耍手段，误导验证者接受错误的论述。但 Goldwasser 等人却从另一个角度思考了这个问题：如果我们压根就不相信验证者，该怎么办？
更具体的来说，他们更关心信息泄露的问题。他们抛出了这样的思考：”在验证者的验证过程中，究竟会获取多少单纯验证论述真假无需知道的额外信息。”
这里要强调一下，这个问题不是单纯的理论思考，而是在真实、具体的应用中，会面到临的问题。
我们举个例子，假设今天在真实世界有个客户端想要使用密码登录web服务器，在”真实世界”的标准操作流程中，包含将密码以哈希形式储存在客户端。我们可以将”登录”这个动作视作某种证明——也就是我们要能够提供一串输入，这串输入经过哈希运算后的值与密码的哈希相同（因为哈希运算的单向性，这串输入只能是我们的密码）。但这有个问题是：客户端实际上知道我们的密码。
大多数系统以这种绝对最糟糕的方式进行”证明”——客户端直接将原始密码发送给服务器，服务器重新计算密码哈希并将其与存储值进行比较。这里的问题很明显：在协议结束时， 服务器已经取得我们的明文密码。 因此，保障现代密码安全很大程度上要祈祷服务器不会遭受攻击。
Goldwasser，Micali 和 Rackoff 等人提出了一种全新的方法来完成”证明”。如果零知识证明真的可行，它将允许我们在证明某些数学陈述为真的同时，保证不会有任何不相关的信息被透露出去。
二、零知识证明理解
通俗的来讲，零知识证明就是我让你相信我说的一句话或一个结论而不需要向你透露任何有关该结论的有用信息.举个简单的例子，比如说凡尔赛文学，我可以再不向你透露我有多少资产的前提下让你相信我非常有钱，毕竟财产总数是我的私人信息，我不想告诉任何人。
下面通过三个小故事简单的进行对零知识证明的理解：
①阿里巴巴与四十大盗
有一天，阿里巴巴被强盗抓住了，强盗向他索要开启山洞大门的咒语。
但此时阿里巴巴面临一个两难的问题，如果把密码告诉强盗，自己就没有利用价值了，最后肯定会被杀。
如果不告诉强盗咒语，强盗以为自己不知道咒语，自己还是会被杀。
怎么能做到让他们相信自己确实知道咒语，但是还不能让他们知道咒语是什么。
这确实是一个很难的问题，但是阿里巴巴想出了一个好办法。
他对强盗头领提议说，你们离我30米远，然后用弓箭指着我，当你举起双手后，我就念咒语开启山洞大门；当你把双手放下后，我就念咒语关上山洞大门，如果我要是逃跑，你们就用弓箭射死我。
对于强盗头领来说，这显然是个好主意，于是照办。
强盗头领先是举起双手，看到阿里巴巴动了动嘴皮子，门就开了，然后放下双手，阿里巴巴又动了动嘴皮子，门就关了。
显然，强盗相信了阿里巴巴。
这样，阿里巴巴在没有告诉强盗头领开门咒语的情况下，又向强盗证明了，自己是知道开门咒语的。
②地图着色问题
如何用三种颜色染色一个地图，保证任意两个相邻的地区都是不同的颜色。我们把这个「地图三染色问题」转变成一个「连通图的顶点三染色问题」。假设每个地区都有一个首府（节点），然后把相邻的节点连接起来，这样地图染色问题可以变成一个连通图的顶点染色问题。
下面我们设计一个交互协议：
- 「证明者」Alice
- 「验证者」 Bob
Alice 手里有一个地图三染色的答案，请见下图。这个图总共有 6 个顶点，9 条边。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xi0C2Olx-1645409350086)(https://lkk2lqq.com/picture/map1.png)]
现在 Alice 想证明给 Bob 她有答案，但是又不想让 Bob 知道这个答案。Alice 要怎么做呢？
Alice 先要对染过色的图进行一些「变换」，把颜色做一次大挪移，例如把所有的绿色变成橙色，把所有的蓝色变成绿色，把所有的绿色变成橙色。然后 Alice 得到了一个新的染色答案，这时候她把新的图的每一个顶点都用纸片盖上，然后出示给 Bob 看。
看下图，这时候 Bob 要出手了（请见下图），他要随机挑选一条「边」，注意是随机，不让 Alice 提前预测到的随机数。
假设 Bob 挑选的是最下面的一条边，然后告诉 Alice。
这时候 Alice 揭开这条边两端的纸片，让 Bob 检查，Bob 发现这两个顶点的颜色是不同的，那么 Bob 认为这次检验同构。这时候，Bob 只看到了图的局部，能被说服剩下的图顶点的染色都没问题吗？你肯定觉得这远远不够，也许恰好 Alice 蒙对了呢？其它没暴露的顶点可能是胡乱染色的。
没关系，Bob 可以要求 Alice 再来一遍，看下图
Alice 再次把颜色做一次变换，把蓝色改成紫色，改绿色改成棕色，把橙色改成灰色，然后把所有的顶点盖上纸片。然后 Bob 再挑选一条边，比如像上图一样，选择的是一条竖着的边，然后让 Alice 揭开纸片看看，如果这时候 Bob 再次发现这条边两端的顶点颜色不同，那么 Bob 这时候已经有点动摇了，可能 Alice 真的有这个染色答案。可是，两次仍然不够，Bob 还想再多来几遍。
那么经过反复多次重复这三个步骤，可以让 Alice 作弊并能成功骗过 Bob 的概率会以指数级的方式减小。假设经过 n 轮之后，Alice 作弊的概率为
这里 |E| 是图中所有边的个数， 如果 n 足够大，这个概率 Pr 会变得非常非常小，变得「微不足道」。
可是，Bob 每次看到的局部染色情况都是 Alice 变换过后的结果，无论 Bob 看多少次，都不能拼出一个完整的三染色答案出来。实际上，Bob 在这个过程中，虽然获得了很多「信息」，但是却没有获得真正的「知识」。
③比特币隐私交易场景
在比特币网络中，用户需要将交易明文广播给所有矿工，由他们来校验交易的合法性。但是有些情况下，基于隐私的考虑，又不想把交易的具体内容公布出来。这就形成了一对矛盾。
解决这个矛盾的关键思路是： 校验一个事件正确与否，并不需要验证者重现整个事件。
比如，验收一款软件，通常只要看最终测试结果是否通过即可，并不需要把整个软件开发过程的每一个细节都重放一遍。对于比特币的例子，一笔转帐交易合法与否，其实只要证明三件事：
- 发送的钱属于发送交易的人
- 发送者发送的金额等于接收者收到金额
- 发送者的钱确实被销毁了
整个证明过程中，矿工其实并不关心具体花掉了多少钱，发送者具体是谁，接受者具体是谁。矿工只关心系统的钱是不是守恒的。
zcash 就是用这个思路实现了隐私交易。
; 三、零知识证明原理
零知识证明过程有两个参与方，一方叫 证明者，一方叫 验证者。证明者掌握着某个秘密，他想让验证者相信他掌握着秘密，但是又不想泄漏这个秘密给验证者。双方按照一个协议，通过一系列交互，最终验证者会得出一个明确的结论，证明者是或不掌握这个秘密。
零知识证明原理详解见物质实验室github仓库(不同算法采用的实现原理有部分区别)
仓库链接：https://github.com/matter-labs/awesome-zero-knowledge-proofs
这里主要介绍一下三种典型的零知识证明技术：zk-SNARKs, Zk-STARKs和 BulletProofs。
(1) Bulletproofs 和 Zk-STARKs 不需要可信设置，zk-SNARKs则需要可信设置；
zk-STARKs：通过证明者与验证者之间的交互来执行，以一种有效的数学方法，使得验证者通过验证每一个步骤，最终确信证明者确实知道某个信息或者拥有某种权益。其特点是：证明快、验证快，但证明体积大。
SNARK指无需双方交互，证明人单方出具即可，不需要反复在双方之间传递信息。其特点是：证明慢、验证快，证明体积小。
(2) 证明速度对比：zk-STARKs > zk-SNARKs > Bulletproofs
(3) 文件大小：zk-SNARKs < Bulletproofs
Original: https://blog.csdn.net/qq_40392981/article/details/123041409
Author: KAZIMIYA
Title: 【 BlockChain 】零知识证明
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/794533/
转载文章受原作者版权保护。转载请注明原作者出处！