2019-01-15 | 이화여대 융합보안연구실

[Decenter学院(第3部)]⑧图灵完备在区块链中的意义

本页标题和正文均由AI机器翻译,未经人工审校。准确内容请以韩文原文为准。

随着2018年收尾,各领域取得突出研究成果的研究者获得了多个奖项。特别是10月图灵奖(Turing Award)颁奖典礼举行,人工智能领域的大师“拉吉·雷迪(Raj Reddy)”成为首位亚洲裔获奖者,令公众的关注聚焦于“图灵(turing)”。图灵奖被称为“计算机科学界的诺贝尔奖”,每年颁发给在计算机科学领域留下功绩的人。

图灵奖的词源来自数学家艾伦·图灵(Alan M. Turing)。

数学家艾伦·图灵于1936年提出“图灵”,这是他为说明机器的一般概念而设想的虚拟机器。艾伦·图灵表示,如果机器能够被实现得看起来像真正的人类,那么该机器就被视为智能地通过了对人工智能的测试,即图灵测试。这种测试是让一名实验者与另一名实验者以及计算机对话,如果无法区分二者中谁是人,则最终判定该计算机具备人工智能。

2014年,英国雷丁大学宣布,名为“Eugene·古斯特曼”的人工智能通过了图灵测试。当时的图灵测试标准是,若30%以上的评委判断其在与人类对话即为通过,Eugene·古斯特曼在5分钟内与25名评委进行了文本对话,其中33%的评委判断Eugene是真正的人类。具备这种图灵性质的情形被称为具备图灵完备性(Turing Complete),即确保了“图灵的完备性”。

图灵的完备性,是指以无限的存储空间为基础制造出能够解决这世上所有问题的机器——图灵机(Turing Machine),而能够实现可输入该图灵机中的算法的语言即为“图灵完备语言(Turing Complete Language)”。通过图灵完备语言可以确保图灵的完备性,但为此必须满足以下必备要件。

首先,图灵完备语言必须能够使用足以充分分割进程的小单位,并且要有条件设定和循环指令。一般而言,如今为大众所熟知的机器语言或汇编语言虽被划分为足够小的单位,但实用性较低。例如,C语言、JAVA等在分割程度或实用性方面并不充分,因此被称为“松散图灵完备(Loose Turing Completeness)”。

随着区块链的出现,这种图灵开始受到更多关注,那么区块链与图灵有着怎样的关系呢。

下面更具体地通过区块链的代表案例比特币与以太坊来考察图灵。

比特币为智能合约提供一种名为“脚本(Script)”的语言。驱动比特币交易的这种脚本语言包含许多运算符,但除条件性流程控制功能外,有意不具备循环或复杂的流程控制能力,从而有意限制特定语句的重复。简单来说,就是在比特币的脚本语言上无法使用for语句和while语句。也就是说,完备图灵所要求的“由极小单位构成的语句的重复执行”在比特币上是不可能的。因此可以确认,比特币的脚本语言是图灵不完备的(Turing-Incomplete)。

结果比特币交易脚本的复杂性只能受到限制,且不可能存在无限重复的语句,因此执行时间可以预测。因此构成比特币的脚本语言并非多用途语言,在局限于比特币的同时,在比特币交易中也难以从一开始就实现无限循环或“逻辑炸弹(logic bomb)”的复杂形态。

尽管如此,比特币的脚本之所以从根本上被设计为无法使用循环语句,原因在于即便是极其简单的语句,一旦允许重复,就难免暴露于DOS(denial of service)攻击之下。例如,攻击者在脚本中插入重复语句,比特币执行该脚本时,无意义的无限作业就会在区块链上执行。这有可能在短时间内使比特币网络过载或瘫痪。此外,也是为了防止在交易过程中有意重复“汇款”语句,导致他人钱包中的比特币不断流出的滥用案例。

与比特币不同,被评价为第二代区块链技术的以太坊提供名为“Solidity”的编程语言。以太坊针对比特币所提供脚本语言的图灵不完备性,引入了“燃料(Gas)”这一概念。也就是说,以太坊让运行建立在对每项计算机代码作业收取手续费即Gas的系统基础之上,从而确保了图灵完备性。由于这种图灵完备性,基于以太坊平台可以在以太坊之上开发各种分布式应用(DApp)。归根结底,以太坊使图灵完备语言得以实现,可以说在区块链层面之外,也展现了编程语言本身的技术进步。

以太坊的Solidity与比特币不同,能够使DOS攻击简化。由于区块链的特性,参与的矿工要对代码进行验证和执行,因此若在参与该代码设计的所有矿工的机器上执行,区块链本身可能瘫痪。但以太坊为解决这一问题引入了Gas的概念。每个操作码都定有Gas价格,首次执行代码时可以设定Gas量。例如,如果最初设计为使用100 Gas来运行程序,那么其后若Gas不足,代码就无法执行到底。因此,要反复持续执行语句,就需要与之成比例的相应数量的Gas;而要让代码无限重复执行,就必须消耗无限数量的以太。因此,若有人有意让语句重复,就需要相应的Gas,形成用户必然承担成本的结构,通过无限循环语句进行滥用的案例在以太坊中可以得到一定程度的防范。

最初提出以太坊的维塔利克·布特林曾多次在采访中表示,要通过以太坊提供植入“完备图灵编程语言”的区块链,由此可见他对“图灵完备性”有着认知。因此以太坊克服了比特币的局限,作为第二代区块链受到关注。但如今被评价为第三代区块链的EOS已经出现,EOS的创始人丹尼尔·拉里默(Daniel Larimer)同样表明了要通过EOS打造图灵完备的区块链的抱负。

当然,图灵完备性并不保证所有基于代码的系统的完备性。也有因图灵完备性而发生运算语无限重复,反而在黑客威胁面前显得脆弱的情形。但以太坊、EOS的创始人在开发各自平台时强调这一点并将其设为核心实现目标的原因值得关注。因此,我们有必要继续审视区块链图灵完备性的意义,并且在今后将登场于世的众多基于区块链的平台中,以图灵完备性为指标来评价各自作为编程语言的技术进步,这一点具有价值,相信所有人都会认同。/梨花女子大学融合安保研究室

阅读韩文原文