我对比特币和以太坊的几个重要概念的理解（1）

图灵完备性（Turing-completeness）

比特币缺少图灵完备性

图灵完备这个词，源于数学家艾伦·图灵(Alan Turing)，1936年图灵在 《论可计算数及其在判定性问题上的应用》这篇重要论文中提出了图灵机这一数学模型概念。论文中，他证明了：只要图灵机可以被实现，就可以用来解决任何可计算问题。可计算问题，在计算机领域，我们研究的一切问题都是计算问题，比如给定一个正整数 n，判断它是否是质数。与之相对应的是非计算问题，比如女朋友脑子里到底在想什么？

因此，针对一种语言，如果能模拟出图灵机，我们就可以说这个语言是图灵完备的。判断一个非图灵完备语言的常见方法有：是否有循环语句和是否能实现类似数组这样的数据结构。

从这一点出发，我们可以判断比特币脚本语言缺少图灵完备性。

以下引用以太坊白皮书中对比特币脚本语言缺少图灵完备性的解释：

尽管比特币脚本语言可以支持多种计算，但是它不能支持所有的计算。最主要的缺失是循环语句。不支持循环语句的目的是为了避免交易确认时出现无限循环。理论上，对于脚本程序员来说，这是可以克服的障碍，因为任何循环都可以用多次重复if 语句的方式来模拟，但是这样做会导致脚本空间利用上的低效率，例如，实施一个替代的椭圆曲线签名算法可能将需要256次重复的乘法，而每次都需要单独编码。(翻译：巨蟹 、少平)

缺少图灵完备也不是没有意义，至少能避免很多问题，系统更加简洁，比特币被设计出来就是作为一种货币来使用的，图灵完备不是必要的。

以太坊支持图灵完备

不同于比特币，以太坊被设计出来是要作为一个区块链应用平台的，想要在平台上跑各种各样的应用，就必须要支持图灵完备，方便开发者开发。

以太坊为了解决上面说的交易确认时无限循环的问题，引入了 Gas 的概念，任何人想要在以太坊网络上执行代码，比如发起一笔交易，为了防止交易有可能被无限的执行下去，你需要为你的交易付费，需要执行的代码越多，所需要付出的代价越高，如果执行交易的过程中，用完了 Gas，所有的状态改变恢复原状态，但是已经支付的交易费用不可收回了，这些费用会打给为你打包交易（这是一种服务）的矿工。如果执行交易中止时还剩余 Gas，那么这些 Gas 将退还给发送者。

默克尔树（Merkle tree）

默克尔树是一种二叉树，由一组叶节点、一组中间节点和一个根节点构成。最下面的大量的叶节点包含基础数据，每个中间节点是它的两个子节点的哈希，根节点也是由它的两个子节点的哈希，代表了默克尔树的顶部。默克尔树的目的是允许区块的数据可以零散地传送：节点可以从一个源下载区块头，从另外的源下载与其有关的树的其它部分，而依然能够确认所有的数据都是正确的。

上文的哈希指的是一种加密算法，这种算法可以把一串数据处理成一个特定长度的字符串，相同的数据经过处理后的字符串不会变化，对数据做任何的改动都会导致处理后的字符串发生变化，这种算法是单方向的，即只能把数据处理成字符串，反过来无法推导，但验证非常简单。

如果一个恶意用户尝试在树的下部加入一个伪造的交易，所引起的改动将导致树的上层节点的改动，以及更上层节点的改动，最终导致根节点的改动以及区块哈希的改动，这样协议就会将其记录为一个完全不同的区块，这样的数据结构决定了大概率区块中的交易数据不会被篡改。

区块链数据结构（Authenticated data structure）

区块链是一个分布式的数据库账本，数据由一个一个的区块构成，区块按时间戳排序，上一个区块的数据经过连续两次哈希算法处理会被记录在下一个区块上，区块中除了上一个区块的数据，还有时间戳和交易数据在默克尔树上的根数据等。

让我们来想象一下，假如我把一个最新的区块拎在手上，因为所有的区块是连在一起的，所有的旧区块会因为我提起最新区块这个动作跟着被拎起来，这样的数据结构，决定了只要篡改任何一个区块上的数据，都会导致跟这个数据相关的数据发生改变。

未完待续…

说明：题图基于 COO 协议，Photo byAlexonUnsplash