查看原文
其他

小学生也能看懂的零知识证明科普(2)虚拟机与非交互式证明 | ZKP101

曼达洛人 Manta Network Protocol 2022-10-11
注:本篇示例引用自https://medium.com/qed-it/the-incredible-machine-4d1270d7363a。作者Aviv Zohar,Ghost、Spectre 协议创始团队成员。
小学生也能看懂的零知识证明科普(1)零知识证明与交互式证明 | ZKP101
本系列将试图用通俗的举例和语言,帮助大家理解复杂概念。本系列非学术论述,举例只为帮助大家通俗理解,更严谨的表述,欢迎大家查看专业论文学习。
上篇文章,我们从数独游戏开始,介绍零知识证明。
奇异博士在不告诉绿巨人解法的前提下,证明了数独游戏有解。
绿巨人回到家,辗转难眠,第二天对奇异博士说,“这个零知识证明很有意思啊,现在直播这么火,我们为什么不开个视频直播呢?”
奇异博士想了想,有道理啊。于是,两人在某音平台直播。
他们还拉上了好朋友钢铁侠。奇异博士、绿巨人负责直播,钢铁侠负责运营。新奇的解法,很快吸引了一大群粉丝。
但某次直播开始前,奇异博士把“解法”弄丢了。他赶紧告诉绿巨人,直播开始后,按照自己偷偷暗示的方式进行验证。
一旁的钢铁侠目睹全过程,大失所望。
非交互式证明 (Non-interactive Proofs)
几天后,钢铁侠带着一台机器来找奇异博士和绿巨人。
这是一台自动验证数独的机器。只要把卡牌摆在传送带上,机器会随机按照某种方式验证奇异博士提供的解法是否正确。
钢铁侠当着奇异博士和绿巨人的面,完成最后的编程工作,让机器生产随机数,这样所有人都不知道机器会用哪种方式验证了。然后,他把面板焊死。
就这样,机器会随机选择,是按照列,还是行,亦或是3*3方格来验证。奇异博士和绿巨人就无法作弊了。
小结
1/ 交互式零知识证明(Interactive Zero-Knowledge Proof)和非交互式零知识证明(Non-Interactive Zero-Knowledge Proof)
回想下,奇异博士与绿巨人刚开始的验证过程。奇异博士一遍一遍地摆牌,放入纸袋中,让绿巨人验证。
注意是“一遍一遍地”,一会按列把卡牌放入纸袋,一会又按行,一会又按3*3方格。
两人按照不同的验证方式,持续交互。这个过程叫交互式证明。
问题在于,万一奇异博士与绿巨人串通好,只按行验证呢?这就会出现作弊情况。
于是,钢铁侠在目睹奇异博士、绿巨人串通作弊后,发明了机器,让大家按照第三方程序随机验证,防止了奇异博士和绿巨人串通。
只要将卡牌放到传送带上,机器就可以直接验证该数独是否有解。这个过程叫非交互式证明。
平时比较常见的 zk-SNARK,zk-STARK 都属于非交互式证明。
但,新问题来了,如果程序由钢铁侠编写,这下奇异博士和绿巨人没法作弊了,但钢铁侠自己呢,万一他作弊怎么办?
所以,非交互式证明的关键在于,如何保障验证程序的不受任何人控制。于是,就有了可信设置(Trusted Setup)。
2/ 模拟器与可信设置
钢铁侠发明的,可自动验证数独的机器,在零知识证明中,称为模拟器(Simulator)。
机器内部生成随机数,选择验证方式,相当于模拟器的随机预言(Random Oracle)、公共参考串(Common Reference String、CRS)。
而钢铁侠输入初始程序的过程,类似可信设置(Trusted Setup)。
但是,等等。
如果程序是钢铁侠设计的,他不就知道算法规律了?那他岂不是可以作弊?
幸好有种方式,叫安全多方计算(MPC)。
大概可以理解成,奇异博士、绿巨人、钢铁侠每个人都输入一个数字,影响变量。输入之后,要把自己的数字隐藏起来,这样每个人都只能看到自己的那部分。
比如:
验证方式 Y = aX + bY + cZ + dA + ……
Abcd由奇异博士、绿巨人、钢铁侠输入,每个人输入之后,用胶带把数字挡上。
他们还可以邀请成百上千个朋友,每个人都输入一个字符。点击运行。
只要其中有一个人是可信的,不透露自己的数字,那大家就无法还原算法,也就无法作弊了。
这也是为什么,可信设置发布对于零知识证明协议来说,是极其重要的。通常会有“仪式”。
在现实中的可信设置仪式中,项目方通常会邀请各个不同的人来设置,之后把电脑直接砸毁。
Zcash 进行可信设置时,搞了直播,还特意跑到了切尔诺贝利去。就是为了吸引大家关注,让所有人都相信 Zcash 自己是无法作弊的。
再梳理下。
安全多方计算,参与者都掌握一段信息,拼起来,就可以掌握验证算法规律。但只要其中有一个人销毁信息,就无法再恢复了。
所以,安全多方计算用于可信设置。
可信设置完成后,模拟器的验证结果将变得可靠。通过随机预言或公共参考串协助验证者和证明者完成验证。
在不透露信息的前提下,证明验证者手中信息为真的。
在本文,我们通俗地了解了交互式证明、非交互式证明、模拟器、可信设置、可信多方计算等概念,以及稍微接触到了 zk-SNACK 和 zk-STARK。
至此,我们已经通俗了解零知识证明的基本原理。
那么,zk-Rollup、zk-EVM、zk-SNACK、zk-STARK 到底都是什么,有什么关联,请继续关注该系列文章。
欢迎关注Manta Network Protocol公众号,或关注推特@manta_china
获取更多关于零知识证明和 Manta Network 的资讯。

关于 Manta Network
Manta Network 致力于通过隐私保护构建一个更好的 Web3 世界。Manta 的产品设计从第一性原理出发,通过 zkSNARK 等领先的密码学架构为区块链用户提供端对端的隐私保护。在保障隐私的同时,Manta 兼具互操作性、便捷性、高性能以及可审计性,允许用户进行任意平行链资产间的隐私转账和交易。Manta 的愿景是为整个区块链世界提供更便捷的隐私保护服务。
Manta 的创始团队由多位加密货币资深人士,教授和学者组成,他们的经验包括哈佛大学,麻省理工学院和 Algorand。Manta 的投资机构包括 Polychain、ParaFi、Binance Labs、Multicoin、CoinFund、 Alameda、DeFiance 以及 Hypersphere 等。Manta 也是波卡官方 Web3 基金会资助获得者,Substrate Builder Program 成员,伯克利大学区块链加速器成员。
We're Hiring!
访问查看开放职位:https://jobs.lever.co/MantaNetwork
关注官方频道了解有关 Manta/Calamari 的更多信息:
Website:https://manta.network/
Github:https://github.com/Manta-Network
Twitter:https://twitter.com/MantaNetwork
Medium:https://mantanetwork.medium.co
Telegram:https://t.me/mantanetwork
Discord:https://discord.gg/ZtSuSKRy8X
Telegram中文:https://t.me/mantanetwork_zh
Twitter中文:https://twitter.com/manta_china

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存