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

区块链学堂第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 条评论
登录 后参与评论

相关文章

来自专栏目标检测和深度学习

【资源】史上最全数据集汇总

无论是数据挖掘还是目前大热的深度学习,都离不开“大数据”。大公司们一般会有自己的数据,但对于创业公司或是高校老师、学生来说,“Where can I get l...

1093
来自专栏大数据挖掘DT机器学习

数据挖掘这些年,这些算法,这些反思

写这篇文章,缘自于前几天部门内部成员们进行了一次部门内部现有涉及的一些算法的review以及整理。不过比较囧的就是,由于boss不在,我们讨论讨论着就...

2776
来自专栏PPV课数据科学社区

【学习】关于数据挖掘算法的反思

 写这篇文章,缘自于前几天部门内部成员们进行了一次部门内部现有涉及的一些算法的review以及整理。不过比较囧的就是,由于boss不在,我们讨论讨论着就成了吐槽...

3025
来自专栏大数据文摘

2017 NIPS 哪家强?我们统计了大会发文数量,谷歌和CMU稳居老大

1223
来自专栏程序员维他命

《如何高效学习》- 读书笔记

本书介绍了整体性学习法:强调在学习过程中,需要通过比喻和抽象的方法,将新知识与旧知识相互联系,以提高学习效率和深度的学习方法。

782
来自专栏PPV课数据科学社区

【数据可视化专题】做好数据可视化的五虎将

  因为接下来要做卖家后台数据纵横的改版,对数据可视化这块儿又进行了研究和心得的整理,跟大家分享下数据可视化常用的五种方式,希望能给大家带来思路的拓展。概念 ...

3374
来自专栏数说工作室

周一鸡血 | 编程不好怎么学数据挖掘? | 数说 · 精选

本文作者谢科,是数说君在知乎认识的一位数据科学大牛,Twitter的Data Scientist,目前正在创业(“用软件定义商家做生意的方式”)。 对于一个编...

3366
来自专栏PPV课数据科学社区

数据可视化常用的五种方式及案例分析

因为接下来要做卖家后台数据纵横的改版,对数据可视化这块儿又进行了研究和心得的整理,跟大家分享下数据可视化常用的五种方式,希望能给大家带来思路的拓展。 概念 借助...

3225
来自专栏互联网杂技

做好数据可视化的五虎将

概念 借助于图形化的手段,清晰、快捷有效的传达与沟通信息。从用户的角度,数据可视化可以让用户快速抓住要点信息,让关键的数据点从人类的眼睛快速通往心灵深处。数据...

3387
来自专栏用户3246163的专栏

[脑书笔记]《整体性学习》1-整体性学习策略

从上面的英文解释可以看出Learn主要指的是获取知识或者技能的结果,而Study主要指阅读,记忆,去学校来达到获取知识的各种形式。所以从书名就可以猜测的作者的本...

541

扫码关注云+社区