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

区块链学堂第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。

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

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