区块链学堂——图灵完备、零知识证明

区块链学堂第14篇

前言

在学习区块链的过程中,常常被一些外星人词汇(专业术语)困扰,图灵完备、零知识证明就是其中之二,今天就彻底搞定这两个“天外来客”。

学习目标

①   理解图灵完备、零知识证明的定义

②   了解图灵完备和非图灵完备的优缺点

③   理解零知识证明的定义

图灵完备

一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。

图灵完备的系统和图灵完备的语言

一个能计算出每个图灵可计算函数(Turing-computable function)的计算系统被称为图灵完备的。一个语言是图灵完备的,意味着该语言的计算能力与一个通用图灵机 (Universal Turing Machine)相当,这也是现代计算机语言所能拥有的最高能力。

图灵完备深入解释

在可计算理论中,当一组数据操作的规则(一组指令集,编程语言,或者元胞自动机)满足任意数据按照一定的顺序可以计算出结果,被称为图灵完备(turing complete)。一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的,它(计算机设备)有能力执行条件跳转(“if” 和 “goto”语句)以及改变内存数据。 如果某个东西展现出了图灵完备,它就有能力表现出可以模拟原始计算机,而即使最简单的计算机也能模拟出最复杂的计算机。所有的通用编程语言和现代计算机的指令集都是图灵完备的(C++ template就是图灵完备的),都能解决内存有限的问题。图灵完备的机器都被定义有无限内存,但是机器指令集却通常定义为只工作在特定的,有限数量的RAM上。

图灵完备优缺点

图灵完备意味着你的语言可以做到能够用图灵机能做到的所有事情,可以解决所有的可计算问题。 图灵不完备也不是没有意义, 有些场景我们需要限制语言本身. 如限制循环和递归, 可以保证该语言能写的程序一定是终止的。图灵不完备会更安全些,图灵完备会更智能些。

比特币的图灵非完备性

比特币脚本语言包含许多操作,但都故意限定为一种重要的方式——没有循环或者复杂流控制功能以外的其他条件的流控制。这样就保证了脚本语言的图灵非完备性,这意味着脚本的复杂性有限,交易可执行的次数也可预见。脚本并不是一种通用语言,施加的这些限制确保该语言不被用于创造无限循环或其它类型的逻辑炸弹,这样的炸弹可以植入在一笔交易中,通过引起拒绝服务的方式攻击比特币网络。受限制的语言能防止交易激活机制被人当作薄弱环节而加以利用。

以太坊是一个图灵完备的区块链

以太坊的核心就是能够运行“无所不能”的智能合约,拥有图灵完备的编程语言,比如Solidity,可以解决所有可计算问题。

零知识证明

“零知识证明”-zero-knowledge proof,是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下,使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议,即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息,但证明过程不能向验证者泄漏任何关于被证明消息的信息。大量事实证明,零知识证明在密码学中非常有用。如果能够将零知识证明用于验证,将可以有效解决许多问题。

定义

零知识证明满足三个属性:

1、如果语句为真,诚实的验证者(即,正确遵循协议的验证者)将由诚实的证明者确信这一事实。

2、如果语句为假,不排除有概率欺骗者可以说服诚实的验证者它是真的。

3、如果语句为真,证明者的目的就是向验证者证明并使验证者相信自己知道或拥有某一消息,而在证明过程中不可向验证者泄漏任何有关被证明消息的内容。

零知识证明并不是数学意义上的证明,因为它存在小概率的误差,欺骗者有可能通过虚假陈述骗过证明者。换句话来说,零知识证明是概率证明而不是确定性证明。但是也存在有技术能将误差降低到可以忽略的值。

零知识的形式定义必须使用一些计算模型,最常见的是图灵机的计算模型。

证明举例

案例一:A要向B证明自己拥有某个房间的钥匙,假设该房间只能用钥匙打开锁,而其他任何方法都打不开。这时有2个方法:

1、A把钥匙出示给B,B用这把钥匙打开该房间的锁,从而证明A拥有该房间的正确的钥匙。

2、B确定该房间内有某一物体,A用自己拥有的钥匙打开该房间的门,然后把物体拿出来出示给B,从而证明自己确实拥有该房间的钥匙。

后面的②方法属于零知识证明。好处在于在整个证明的过程中,B始终不能看到钥匙的样子,从而避免了钥匙的泄露。

案例二:A拥有B的公钥,A没有见过B,而B见过A的照片,偶然一天2人见面了,B认出了A,但A不能确定面前的人是否是B,这时B要向A证明自己是B,也有2个方法。

1、B把自己的私钥给A,A用这个私钥对某个数据加密,然后用B的公钥解密,如果正确,则证明对方确实是B。

2、A给出一个随机值,B用自己的私钥对其加密,然后把加密后的数据交给A,A用B的公钥解密,如果能够得到原来的随机值,则证明对方是B。

后面②方法属于零知识证明。

参考文献:百度百科、《区块链技术指南》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SAP最佳业务实践

从SAP最佳业务实践看企业管理(152)-生产物流-生产线物流规划

企业的运营过程中,物流、资金流和信息流贯穿始终,三位一体,不可分割。物流是最基本的活动,相对于信息流和资金流,物流规划的科学性对企业的整体效益有着决定性的影响。...

2726
来自专栏数据冰山

谷歌「机弦」有何玄机?

11月15日北京开始冬季供暖那天,谷歌科研博客发布了开源软件SLING,又一个号称能让计算机更容易看懂人话的技术。 SLING: A Natural Langu...

3895
来自专栏镁客网

特斯拉Model 3更多功能曝光,预估售价约为35000美元

1634
来自专栏青青天空树

1166-敌兵布阵

描述:C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tid...

903
来自专栏量子位

凭一张照片找到视频中你所有的镜头,包括背影丨商汤ECCV 2018论文

别担心,商汤可不是准备拍电影,而是提出了新的视频找人方法——也就是,无论一位电影明星演的是青春少女还是白发老人,无论TA露出了正脸还是侧颜,无论影片的镜头明亮鲜...

940
来自专栏镁客网

黑科技 | 消除VR视疲劳问题,研究人员研发出新型3D显示器

1080
来自专栏IT派

大吉大利,今晚如何用 Python 解锁“吃鸡”的正确姿势

大吉大利,今晚吃鸡~ 今天跟朋友玩了几把吃鸡,经历了各种死法,还被嘲笑说论女生吃鸡的100种死法,比如被拳头抡死、跳伞落到房顶边缘摔死 、把吃鸡玩成飞车被车技秀...

892
来自专栏顶级程序员

用Python模拟弹道轨迹

转自:中国统计网(小编微信:itongjilove) ‍作者:Toby:python数据科学爱好者。国内最大药品数据中心任职,二十多个数据库负责人。 最近美国...

4545
来自专栏企鹅号快讯

原来C语言还可以这样玩?你见过吗?历届混乱代码大赛作品

曾经刚开始学习编译语言的时候导师就一个劲的强调,程序一定要美观整洁,做好这些以后才算是合格的程序员,知道小编看到了关于国际C语言混乱代码大赛的成果,小编发现,一...

3145
来自专栏Data Analysis & Viz

乱炖“简书交友”数据之代码(2)

继续更新出来本系列的代码:乱炖数据之2700余篇“简书交友”专题文章数据的花式玩法

933

扫码关注云+社区