阿里巴巴的零知识证明

标签: 计算机科学 原创 哈米尔顿回路 零知识证明 | 发表时间:2010-04-25 06:10 | 作者:奥卡姆剃刀 见涛
出处:http://songshuhui.net

战争中你被俘了,敌人拷问你情报。你是这么想的:如果我把情报都告诉他们,他们就会认为我没有价值了,就会杀了我省粮食,但如果我死活不说,他们也会认为我没有价值而杀了我。怎样才能做到既让他们确信我知道情报,但又一丁点情报也不泄露呢?

这的确是一个令人纠结的问题,但阿里巴巴想了一个好办法,当强盗向他拷问打开山洞石门的咒语时,他对强盗说:“你们离我一箭之地,用弓箭指着我,你们举起右手我就念咒语打开石门,举起左手我就念咒语关上石门,如果我做不到或逃跑,你们就用弓箭射死我。”

强盗们当然会同意,因为这个方案不仅对他们没有任何损失,而且还能帮助他们搞清楚阿里巴巴到底是否知道咒语这个问题。阿里巴巴也没损失,因为处于一箭之地的强盗听不到他念的咒语,不必担心泄露了秘密,而且他确信自己的咒语有效,也不会发生被射死的杯具。

强盗举起了右手,只见阿里巴巴的嘴动了几下,石门果真打开了,强盗举起了左手,阿里巴巴的嘴动了几下后石门又关上了。强盗还是有点不信,说不准这是巧合呢,他们不断地换着节奏举右手举左手,石门跟着他们的节奏开开关关,最后强盗们想,如果还认为这只是巧合,自己未免是个傻瓜,那还是相信了阿里巴巴吧。

“零知识证明”说的是示证者向验证者表明他知道某种秘密,不仅能使验证者完全确信他的确知道这个秘密,同时还保证一丁点秘密也不泄露给验证者。阿里巴巴的这个方案,就是认证理论“零知识证明”的一个重要协议。

除了被俘后如何靠情报保命这个问题,零知识证明在社会领域中还有着很多应用场合。例如你证明了一个世界级的数学难题,但在发表出来之前,总是要找个泰斗级的数学家审稿吧,于是你将证明过程发给了他,他看懂后却动了歪心思,他把你的稿子压住,把你的证明用自己的名义发表,他名利双收,你郁闷至死,你去告他也没用,因为学术界更相信的是这位泰斗,而不是你这个无名之辈。

这并不是天方夜谭,而是学术界常见的难题,前些年有个博士生告他的泰斗级导师剽窃他的成果,但除了令师生关系恶化外没有任何效果,最后他使出了撒手锏,称他在给导师审阅的论文的关键公式中,故意标错了一个下标,而这会导致整个推导失败。学术委员会一查果真如此,但还是有倾向于泰斗的声音,有人说那是泰斗的笔误,只不过让你发现了而矣,并不能证明那公式就是你推导出来的。

这个博士生故意标错下标,不能说他没有心眼,但他没有把“零知识证明”理论用好,以致于落到这种地步。“零知识证明”早在1986年就被A.Fiat和A.Shamir用数学的方法给出了解决方案,并在同年申请了美国专利,但由于该理论可能被用于军事领域,专利局被军方密令搁置,6个月后,军方命令:“该申请发表后会有害于国家安全……所有美国人的研究未经许可而泄露将会被判刑罚款”。看来军方认为作者肯定是美国人了,但作者实际上是在美国申请专利的以色列人,研究也是在以色列的大学里做的,军方这个命令摆了个大乌龙,虽然两天后撤消了,但已经成为了学术界的笑柄。

这个笑柄也说明了一个问题,即“零知识证明”非常重要。基于数学的推理虽然非常复杂,但思路却很简单,上述的阿里巴巴方案就是其中之一。其它的一些方案,也都是像这样遵循着分割和选择(Cut and Chose)协议的。

例如图论中有个哈米尔顿回路(Hamiltonian Cyclic)问题,说的是多个顶点的全连通图,若有一条通路通过了所有顶点,且每个顶点只通过一次,那这就是哈米尔顿回路。如果顶点较多的话,即使用计算机穷举计算很难找出这条回路,因为通路的可能性真在是太多了。

如果松鼠会贴了一张全连通图(命名为A图)悬赏哈米尔顿回路,而且任命我(奥卡姆剃刀)作为评审官,你幸运的找到了一条,那该怎么办呢,将结果直接发给我吗?千万不要,因为保不齐我会将你的成果让给了我的亲信。那你该怎么办呢?应该这么办:

1、你将A图的顶点搞乱了,并生成一张新图,只是顶点的位置变了,而新图顶点之间的连线关系与A图是完全一致的。这时,新图中每个顶点与A图中每个顶点的对应关系你是清楚的,而且新图中的哈米尔顿回路你也是知道的。

2、你将这张新图发给我,没错,就是仅仅一张新图,上面并没有画着你发现的牛B回路。

3、我收到后,对你提出两个问题中的一个:一是证明新图就是从A图变形过来的,所有顶点和连线的关系完全一致,二是画出新图中的哈米尔顿回路。

4、如果你真的找到了A图的哈米尔顿回路,这两个问题当然都能轻松回答。需要注意的是:你只需要回答第3步的其中一个问题,千万不要两个问题一并回答,否则我就知道你关于A图的哈米尔顿回路了,你就SB了。

5、我还是不相信你,因为有可能你只是将A图变了形,却根本不知道A图的哈米尔顿回路,而我在第3步时恰好要求你证明新图就是从A图变形过来的,你当然能证明。或者有可能你找了个你知道哈米尔顿回路的图,但这张图跟A图一点关系都没有,而我在第3步恰好要求你画出这张图的哈米尔顿回路。

6、我要求你从第1步开始重复这个验证过程,随着次数的增加,第5步那种巧合的可能性就越来越低,如果你多次能回答对第3步中的问题,那我还不相信你已经找到了A图的哈米尔顿回路,那我就是一个傻瓜。

7、为了表明我不是傻瓜,我在松鼠会群博里宣布你找到了A图的哈米尔顿回路,而这时我并没有看到你所画的A图的哈米尔顿回路。

回到你证明了世界级的数学难题的问题,你可以用这种分割和选择协议来进行零知识证明,来保护你的权利。你公开声称你解决了这个数学难题后,验证者会给你出一个其它的题,而能做出这道题的前提条件是已经解决了那个数学难题,否则的话无解,而且这个条件是学术界所公认的,这个题就是所谓的平行问题。不出所料,你靠着已经解开数学难题的基础把这个平行问题做出来了,但验证者还是不信,他又出了一道平行问题,你又做出来了,多次较量后,验证者就确信了你已经解决了那个数学难题,虽然他并没有看到具体的解法。

大家已经看出来了,零知识证明需要示证者和验证者的密切配合,但如果你只是一个数学界的无名之辈,即使你宣称你解决了数学难题,也不会有人跟你配合着玩零知识证明,那你该怎么办呢?

我告诉你一个可以在法庭上都能当作有效证据的招数,你将证明打印好,选择一个最可靠最权威的邮政公司,把它寄给自己,当你收到这个扣着邮戳的包裹后,不要打开,把它放好,然后就可以把证明寄给数学泰斗。如果他用自己的名义发表了,不必着急,等他依靠其影响力把这个证明炒热后再出手,你上法庭控告他,他当然不承认,在法庭上你将那个没开封的包裹拿出来,上面清清楚楚地盖着时间戳,这就证明了你包裹里的证明是发生在那个时间戳之前的,加上之后的你邮给泰斗论文的邮件存根,和泰斗以自己名义发表论文的时间,三者就构成了一个完整的证据链,泰斗灰头土脸名声扫地,而你大获全胜名利双收。

参考文献:《通信网的安全-理论与技术》,王育民等编著,西安电子科技大学出版社,2000.5

本文地址(转载请注明出处): 复制
收藏、分享这篇文章: 豆瓣 新浪微博 人人网 开心网 QQ空间 qq书签 GOOGLE书签 MySpace 百度搜藏 鲜果 做啥       更多...

相关 [阿里巴巴 知识 证明] 推荐:

阿里巴巴的零知识证明

- 见涛 - 科学松鼠会
战争中你被俘了,敌人拷问你情报. 你是这么想的:如果我把情报都告诉他们,他们就会认为我没有价值了,就会杀了我省粮食,但如果我死活不说,他们也会认为我没有价值而杀了我. 怎样才能做到既让他们确信我知道情报,但又一丁点情报也不泄露呢. 这的确是一个令人纠结的问题,但阿里巴巴想了一个好办法,当强盗向他拷问打开山洞石门的咒语时,他对强盗说:“你们离我一箭之地,用弓箭指着我,你们举起右手我就念咒语打开石门,举起左手我就念咒语关上石门,如果我做不到或逃跑,你们就用弓箭射死我.

[原]阿里巴巴B2B搜索学习

- - 文武天下
主搜索:商品搜索、商家搜索、采购搜索、app搜索. 行业搜索:淘货源、淘工厂、聚好货、主题市场、品牌馆等. 由于用户多,需求强烈,收益大,所以功能、场景、架构做到极致高效. 代码复用性强:基础通用功能进行组件抽象化. 组件通用性好:一些组件或者组件进行组合的服务,适用更多场景,支持更多功能. 转化效果好:算法做的比较深入、细致.

专访阿里巴巴研究员赵海平:从Facebook到阿里巴巴

- - 博客园_新闻
赵海平,2007 年加入只有不到 50 个软件工程师的 Facebook,致力于软件性能和架构分析,在此期间创建了 HipHop 项目,重新编写和实现 PHP 语言,使其速度提高 5 到 6 倍,为公司节约数十亿美元. HipHop 项目之后,致力于“用异步处理来优化分布式系统”的设计理念中,并为此做了多项分布式数据库的优化研究,在 PHP 语言中加入了 yield 和 generator 的新功能,来帮助日趋复杂的 Facebook 网页设计.

阿里巴巴开源项目: 阿里巴巴去Oracle数据迁移同步工具

- - agapple
   08年左右,阿里巴巴开始尝试MySQL的相关研究,并开发了基于MySQL分库分表技术的相关产品,Cobar/TDDL(目前为阿里云DRDS产品),解决了单机Oracle无法满足的扩展性问题,当时也掀起一股去IOE项目的浪潮,愚公这项目因此而诞生,其要解决的目标就是帮助用户完成从Oracle数据迁移到MySQL上,完成去IOE的第一步. .

阿里巴巴高层震动的扯淡

- chenqj - It Talks--上海魏武挥的博客
这是真扯淡了,完全就是写博客,没有什么中心思想,想扯哪里扯哪里. 国内外有两家公司,遥相呼应地都非常强调所谓“价值观”,外有谷歌,内有阿里. 谷歌上市时,可以挑战华尔街的规矩,阿里上市时,则创下当时一批IPO的新高. 故而,这两家公司都是一时的翘楚,属于“从优秀到卓越”的公司. 公司是非常象一个宗教组织的——或者这么说,“好”公司都得象宗教组织.

阿里巴巴集团股权结构图

- telefan - Finacial Planet China 中国投资专家博客集
雅虎SEC文件原文是:“为了尽快获得一个重要牌照,阿里巴巴集团旗下在线支付公司支付宝已经被重组,其100%流通股现由阿里巴巴集团CEO马云控股的一家中国公司持有. 阿里巴巴集团管理层、主要股东雅虎和软银参与了有关支付宝重组条款的详细讨论. 收起 | 查看大图 | 向左转 向右转.

TradeSparq:阿里巴巴+Linkedin的采购网站

- anger - 互联网的那点事...
为什么人们会在Linkedin注册. 其中一个原因在于,他们想和他们的同伴(卖家或者买家)保持联络. 那么阿里巴巴这些年又是为什么这么流行呢,是因为它让国外用户很容易的找到数以千计的中国商品. 但是,你在Linkedin上,通常并不知道你联系的公司实际销售的是什么产品;而在阿里巴巴,如果你是一个制造商,想要推广自己的产品通常需要支付高昂的会员费(供应商会费一年3012美元).

马云给阿里巴巴员工的公开信

- Alex - cnBeta全文版
董事会已经批准B2B公司CEO卫哲、COO李旭晖引咎辞职的请求,原B2B公司人事资深副总裁邓康明引咎辞去集团CPO,降级另用. 几个月前,我们发现B2B公司的中国供应商签约客户中,部分客户有欺诈嫌疑. 而更令人震惊的是,有迹象表明直销团队的一些员工默许甚至参与协助这些骗子公司加入阿里巴巴平台. 大家已经看到了公司的公告,董事会已经批准B2B公司CEO卫哲、COO李旭晖引咎辞职的请求,原B2B公司人事资深副总裁邓康明引咎辞去集团CPO,降级另用.

TechCrunch:阿里巴巴收购雅虎很划算

- David - cnBeta.COM
知名科技博客网站TechCrunch昨天载文称,从财务方面来看,阿里巴巴收购雅虎是很划算的,非常明智. 阿里巴巴CEO马云今天在斯坦福大学演讲时表示,该公司有兴趣收购雅虎. 从表面上来看,马云正是雅虎在后巴茨时代所需要的CEO类型:擅长与外界沟通、精明、相对寡言少语.

阿里巴巴Dubbo分布式服务框架已开源

- tangfl - ITeye论坛最新精华讨论帖
Serving services with invocations everyday, Dubbo becomes the key part of Alibaba's SOA solution and has been deployed to the whole alibaba.com family:.