区块链100讲上期我们讲了哈希算法和公开密钥算法，说到哈希算法提到了一个名词“Merkle tree”，梅克尔树，这棵树是啥呢？它是如何工作的呢，它们又能够提供些什么价值呢，现在以及未来的？我们这期来讲讲“Merkle tree”。

1 Merkle tree

梅克尔树，又叫哈希树，顾名思义，就是存储hash值的一棵树。是一种二叉树，由一个根节点、一组中间节点和一组叶节点组成。最下面的叶节点包含存储数据或其哈希值，每个中间节点是它的两个孩子节点内容的哈希值，根节点也是由它的两个子节点内容的哈希值组成。

图片.png

image

比特币的一个重要特性，这区块是存在一个多级数据结构中的。一个区块的“哈希值”实际上只是这个区块的头信息的哈希值，一个大约 200 个字节的数据，其中包含了时间戳，随机数，上一个区块的哈希和一个存储了这个区块中所有交易的称之为默克尔树的数据结构的根哈希。

2 梅克尔树的结构和特征

图片.png

image

如图，我们来看梅克尔树的数据结构，所有的数据区块两两分组（如图的最底层），指向这些数据的哈希指针被储存在上一层的父节点（parent node）中。

而这些父节点再次被两两分组，并且指向父节点的指针被储存在上一层的父节点中，一直持续这个过程，直到我们得到一个单一的区块，即树根节点。

根据梅克尔树的数据结构，我们可以清楚的了解到，只要我们记住最前面的树根节点的哈希指针，我们就可以根据哈希指针回溯到表中的任意位置，这让我们能保证表中的数据不被篡改。

如果有人篡改了梅克尔树底部的一些数据区块，会导致上一层的哈希指针不匹配，那么他不得不一直篡改上一层的哈希指针，直到数的顶端，而此刻，篡改即将终止，因为我们存储了树根节点的哈希指针。

因此，只要我们记住树根顶部的哈希指针，任何企图篡改数据的行为都会被检测到，这让数据篡改变得不可能实现。

梅克尔树的特点：

MT是一种树，大多数是二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点；
Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。
非叶子节点的value是根据它下面所有的叶子节点值，然后按照Hash算法计算而得出的。

通常，加密的hash方法像SHA-2和MD5用来做hash。但如果仅仅防止数据不是蓄意的损坏或篡改，可以改用一些安全性低但效率高的校验和算法，如CRC。

Second Preimage Attack: Merkle tree的树根并不表示树的深度，这可能会导致second-preimage attack，即攻击者创建一个具有相同Merkle树根的虚假文档。一个简单的解决方法在Certificate Transparency中定义：当计算叶节点的hash时，在hash数据前加0x00。当计算内部节点是，在前面加0x01。另外一些实现限制hash tree的根，通过在hash值前面加深度前缀。因此，前缀每一步会减少，只有当到达叶子时前缀依然为正，提取的hash链才被定义为有效。

3 梅克尔树的形式

1、二进制梅克尔树

梅克尔树最为常见和最简单的形式，是二进制梅克尔树（ binary Mekle tree），其中一bucket单位的数据块总是包含了两个相邻的块或哈希，它的描述如下：

图片.png

image

那么，这种奇怪的哈希算法有什么好处么？为什么不直接将这些数据块串接成一个单独的大块，用常规的哈希算法进行呢？答案在于，它允许了一个整齐的机制，我们称之为梅克尔证明（Merkle proofs）：

图片.png

image

一个梅克尔证明包含了一个数据块，这颗梅克尔树的根哈希，以及包含了所有沿数据块到根路径哈希的“分支”。有人认为，这种证明可以验证哈希的过程，至少是对分支而言。应用也很简单：假设有一个大数据库，而该数据库的全部内容都存储在梅克尔树中，并且这颗梅克尔树的根是公开并且可信的（例如，它是由足够多个受信方进行数字签名过的，或者它有很多的工作量证明）。那么，假如一位用户想在数据库中进行一次键值查找（比如：“请告诉我，位置在85273的对象”），那他就可以询问梅克尔证明，并接受到一个正确的验证证明，他收到的值，实际上是数据库在85273位置的特定根。它允许了一种机制，既可以验证少量的数据，例如一个哈希，也可以验证大型的数据库（可能扩至无限）。

比特币系统的梅克尔证明

梅克尔证据的原始应用是比特币系统（Bitcoin），它是由中本聪（Satoshi Nakamoto）在2009年描述并且创造的。比特币区块链使用了梅克尔证明，为的是将交易存储在每一个区块中：

图片.png

image

而这样做的好处，也就是中本聪描述到的“简化支付验证”（SPV）的概念:而不是下载每一笔交易以及每一个区块，一个“轻客户端”（light client）可以仅下载链的区块头，每个区块中仅包含五项内容，数据块大小为80字节：

上一区块头的哈希值
时间戳
挖矿难度值
工作量证明随机数（nonce）
包含该区块交易的梅克尔树的根哈希

如果一个轻客户端希望确定一笔交易的状态，它可以简单地要求一个梅克尔证明，显示出一个在梅克尔树特定的交易，其根是在主链（main chain，非分叉链）上的区块头。

它会让我们走得很远，但比特币的轻客户确实有其局限性。一个特别的限制是，它们虽然可以证明包含的交易，但无法证明任何当前的状态（例如：数字资产的持有，名称注册，金融合约的状态等）。你现在拥有了多少个比特币？一个比特币轻客户端，可以使用一种协议，它涉及查询多个节点，并相信其中至少会有一个节点会通知你，关于你的地址中任何特定的交易支出，而这可以让你实现更多的应用。但对于其他更为复杂的应用而言，这些远远是不够的。一笔交易影响的确切性质（precise nature），可以取决于此前的几笔交易，而这些交易本身则依赖于更为前面的交易，所以最终你可以验证整个链上的每一笔交易。为了解决这个问题，以太坊的梅克尔树的概念，会更进一步。

以太坊的梅克尔证明

以太坊的每一个区块头，并非只包含一颗梅克尔树，而是包含了三颗梅克尔树，分别对应了三种对象：

交易（Transactions）
收据（Receipts，基本上，它是展示每一笔交易影响的数据条）
状态（State）

图片.png

image

这使得一个非常先进的轻客户端协议成为了可能，它允许轻客户端轻松地进行并核实以下类型的查询答案：

这笔交易被包含在特定的区块中了么？
告诉我这个地址在过去30天中，发出X类型事件的所有实例（例如，一个众筹合约完成了它的目标）
目前我的账户余额是多少？
这个账户是否存在？
假装在这个合约中运行这笔交易，它的输出会是什么？

第一种是由交易树（transaction tree）来处理的；第三和第四种则是由状态树（state tree）负责处理，第二种则由收据树（receipt tree）处理。计算前四个查询任务是相当简单的。服务器简单地找到对象，获取梅克尔分支，并通过分支来回复轻客户端。

第五种查询任务同样也是由状态树处理，但它的计算方式会比较复杂。这里，我们需要构建下我们称之为梅克尔状态转变的证明（Merkle state transition proof）。从本质上来讲，这样的证明也就是在说“如果你在根S的状态树上运行交易T，其结果状态树将是根为S'，log为L，输出为O” （“输出”作为存在于以太坊的一种概念，因为每一笔交易都是一个函数调用，它在理论上并不是必要的）。

为了推断这个证明，服务器在本地创建了一个假的区块，将状态设为 S，并假装是一个轻客户端，同时请求这笔交易。也就是说，如果请求这笔交易的过程，需要客户端确定一个账户的余额，这个轻客户端会发出一个余额疑问。如果这个轻客户端需要检查存储在一个特定合约的特定项目，该轻客户端会对此发出针对查询。服务器会正确地“回应”它所有的查询，但服务器也会跟踪它所有发回的数据。然后，服务器会把综合数据发送给客户端。客户端会进行相同的步骤，但会使用它的数据库所提供的证明。如果它的结果和服务器要求的是相同的，那客户端就接受证明。

图片.png