Blockchain－以太坊Merkle Tree

以太坊Merkle树

Merkle tree作为区块链技术的最重要组成部分之一，通过利用此技术，将以太坊的所有节点运行在所有的计算机、笔记本、智能终端上。区块链上包括很多节点，每个节点有两部分组成，区块头和区块体，如果区块链的节点不使用Merkle树，那么也可以完成相应的工作，但是会限制智能手机，小型计算机的加入，具大的区块头会严重影响计算机的计算能力，从而影响其区块链的可扩展性。

Merkle Tree在一般情况下，作为哈希大量聚集数据块的一种方式，通过利用Merkle Tree将此数据快分割，形成小单位的数据块。在每一个bucket中包含部分数据块，当取出每个数据块时，再次哈希，重复此过程到根节点。 Merkle Tree最简单的形式是二进制树，每个bucker的数据块都有两个子节点的数据块，其具体描述如下： 既然可以通过常规的哈希函数解决问题，为什么要用Merkle Tree？原因在于，Merkle Tree允许一个整齐的机制，这个过程我们称为Merkle proofs。 Merkle proofs包含一个根节点数据块，根节点的数据块包含沿数据块到根路径的所有哈希分支。可以简单验证一个哈希值，同时也可以验证整个根节点所覆盖的范围。

比特币系统的Merkle证明

Merkle proofs最先在比特币系统中得以应用，在支付的过程中，将每一笔交易存储到相应的区块中，通过将交易存储，实现简单的支付操作，无需下载每笔交易的区块，轻型客户端可以仅仅下载区块头部，每个区块的头部包括五个内容，每个数据块的大小为80字节，通过减少数据块的数据量，使得每一个智能的机器，参与到区块链的工作过程中，不必消耗过多的计算机内存的资源。 其五部分区块内容包括如下：

• 上一个区块的哈希值
• 时间戳
• 挖矿难度值
• 工作量证明随机数
• 包含该区块交易的Merkle的根哈希 如果一个轻型客户端希望确定一笔交易状态，那么可以简单的要求一个Merkle证明，显示出一个在Merkle特定的交易过程，其根是在主链上的区块头。轻型客户端的确很便利，但是也具备很多限制，无法证明当前的状态（例如：数字资产的持有，名称注册，金融合约的状态等）。由于Merkle proof的局限性，以太坊将Merkle Tree的结构改造。

以太坊的Merkle证明

以太坊的每一个区块头，并非只包含一颗Merkle树，同时包含三颗Merkle树，分别对应三种对象：

• 交易（Transactions）
• 收据（Receipts，展示每一笔交易影响的数据条）
• 状态（state） 通过增加Merkle Tree的数量可以提高轻型客户端的功能，让更多的功能加入，同时轻型客户端可以进行并核实以下类型的查询答案：
  
  1 此交易是否被包含在特定区块中？
  2 此地址在一段周期内，发生x类型事件的所有实例有哪些
  3 目前此账户的余额是多少？
  4 此账户是否存在？
  5 假设一笔交易在合约中运行，这笔交易的输出是什么？
  
  第一种情况由交易树（Transaction Tree）处理；第二种通过收据树（Receipt Tree）第三种和第四种通过状态树（state tree）负责处理。服务器找到对象，获取Merkle分支，通过分支回复轻客户端。第五种查询任务同样通过状态树处理，但是计算方式比较复杂，通过构建Merkle状态转变的证明。

  帕特里夏树（Patricia Trees）

  Merkle作为最简单的二进制Merkle Tree，以太坊实用的Merkle更为复杂，我们把如下的结构称为“梅克尔.帕特里夏树”（Merkle Patricia Tree）。 二进制Merkle Tree对于验证清单格式的信息，是很好的数据结构，本质上是一系列数据块。对于交易树而言。当树形结构一旦建立，所花费的时间并不重要。而状态树，情况会变的复杂。以太坊的状态树包含一个键值映射，其中的键包括地址和各种值，包括账户的声明、余额、随机数、代码及每一个账户的存储。例如，摩登测试网络（the Morden testnet）的创始状态码如下：

  {
  "0000000000000000000000000000000000000001": {
  "balance": "1"
  },
  "0000000000000000000000000000000000000002": {
  "balance": "1"
  },
  "0000000000000000000000000000000000000003": {
  "balance": "1"
  },
  "0000000000000000000000000000000000000004": {
  "balance": "1"
  },
  "102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": {
  "balance": "1606938044258990275541962092341162602522202993782792835301376"
  }
  }
  

  状态树需要经常性更新信息，其信息包括如下：账户余额和账户的随机数nonce，伴随着新账户的插入，存储的键会经常被插入和删除。在插入、更新、修改的操作后，根节点可以被快速计算出。如需计算整棵树形结构。
  1 树的深度有限制，即使考虑攻击者会故意制造一些交易，但是这棵树尽可能的深，不然攻击者可以通过操纵树的深度，执行拒绝服务攻击（DOS attack），使更新变缓慢
  2 树的根取决于数据，和其中的更新顺序无关，无论从何角度入手更新，其计算根节点的结果不会改变。
  Merkle Patricia Tree可同时满足这些特性，一个以编码形式存储到记录树的“路径”的值。

参考文献

原文链接：https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/