《锋哥论道区块链》之三区块链基础--Merkle Tree

1.Merkle Tree基本概念
Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。

21.png

在最底层，把数据分成小的数据块，有相应地哈希（hash）和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样得到了上一层的哈希（hash）。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的上一层哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root。
2.Merkle Tree的特点
（1）MT是一种树，大多数是二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点；
（2）Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。
（3）非叶子节点的value是根据它下面所有的叶子节点值，然后按照Hash算法计算而得出的。
通常，加密的hash方法像SHA-2和MD5用来做hash。但如果仅仅防止数据不是蓄意的损坏或篡改，可以改用一些安全性低但效率高的校验和算法，如CRC。
3.Merkle Tree基本操作
（1）Merkle Tree的创建
Step1：加入最底层有9个数据块。
　　Step2：（红色线）对数据块做hash运算，Node0i = hash(Data0i), i=1,2,…,9
　　Step3: （橙色线）相邻两个hash块串联，然后做hash运算，Node1((i+1)/2) = hash(Node0i+Node0(i+1)), i=1,3,5,7;对于i=9, Node1((i+1)/2) = hash(Node0i)
　　Step4: （黄色线）重复step2
　　Step5：（绿色线）重复step2
　　Step6：（蓝色线）重复step2，生成Merkle Tree Root

22.png
易得，创建Merkle Tree是O(n)复杂度(这里指O(n)次hash运算)，n是数据块的数量。得到Merkle Tree的树高是log(n)+1（此处的log以2为底）
（2）数据块检索
我们假设有A和B两台机器，A与B都有8个文件，文件分别是f1 f2 f3 ....f8。这个时候我们就可以通过Merkle Tree来进行快速比较。假设我们在文件创建的时候每个机器都构建了一个Merkle Tree。
23.png

从上图可得知，叶子节点node7的value = hash(f1),是f1文件的HASH;而其父亲节点node3的value = hash(v7, v8)，也就是其子节点node7 node8的值得HASH。就是这样表示一个层级运算关系。root节点的value其实是所有叶子节点的value的唯一特征。
　　假如A上的文件f5与B上的f5不一样,其他七个文件一模一样。我们怎么通过两个机器的merkle tree信息找到不相同的文件? 这个比较检索过程如下:
　　Step1. 首先比较v0是否相同,如果不同，检索其孩子node1和node2.
　　Step2. v1 相同，v2不同。检索node2的孩子node5 node6;
　　Step3. v5不同，v6相同，检索比较node5的孩子node 11 和node 12
　　Step4. v11不同，v12相同。node 11为叶子节点，获取其目录信息。
　　Step5. 检索比较完毕。
　　以上过程的理论复杂度是Log(N)。
4.Merkle Tree具体应用
（1）bitcoin
Merkle tree最早的应用是Bitcoin，它是由中本聪在2009年描述并创建的。Bitcoin的Blockchain利用Merkle tree来存储每个区块的交易。而这样做的好处，也就是中本聪描述到的“简化支付验证”（Simplified Payment Verification，SPV）的概念:一个“轻客户端”（light client）可以仅下载链的区块头即每个区块中的80byte的数据块，包含六个元素，而不是下载每一笔交易以及每一个区块。
如果客户端想要确认一个交易的状态，它只需简单的发起一个Merkle proof请求，这个请求显示出这个特定的交易在Merkle trees的一个之中，而且这个Merkle Tree的树根在主链的一个区块头中。但是Bitcoin的轻客户端有它的局限。一个局限是，尽管它可以证明包含的交易，但是它不能进行涉及当前状态的证明（如数字资产的持有，名称注册，金融合约的状态等）。Bitcoin如何查询你当前有多少币？一个比特币轻客户端，可以使用一种协议，它涉及查询多个节点，并相信其中至少会有一个节点会通知你，关于你的地址中任何特定的交易支出，而这可以让你实现更多的应用。但对于其他更为复杂的应用而言，这些远远是不够的。一笔交易影响的确切性质（precise nature），可以取决于此前的几笔交易，而这些交易本身则依赖于更为前面的交易，所以最终你可以验证整个链上的每一笔交易。为了解决这个问题，Ethereum的Merkle Tree的概念，会更进一步。
（2）ethereum
每个以太坊区块头不是包括一个Merkle树，而是为三种对象设计的三棵树：
1）交易Transaction
2）收据Receipts(本质上是显示每个交易影响的多块数据)
3）状态State
这使得一个非常先进的轻客户端协议成为了可能，它允许轻客户端轻松地进行并核实以下类型的查询答案：
1）这笔交易被包含在特定的区块中了么？
2）告诉我这个地址在过去30天中，发出X类型事件的所有实例（例如，一个众筹合约完成了它的目标）
3）目前我的账户余额是多少？
4）这个账户是否存在？
5）假如在这个合约中运行这笔交易，它的输出会是什么？
　　第一种是由交易树（transaction tree）来处理的；第三和第四种则是由状态树（state tree）负责处理，第二种则由收据树（receipt tree）处理。计算前四个查询任务是相当简单的。服务器简单地找到对象，获取Merkle分支，并通过分支来回复轻客户端。第五种查询任务同样也是由状态树处理，但它的计算方式会比较复杂。这里，我们需要构建一个Merkle状态转变证明（Merkle state transition proof）。从本质上来讲，这样的证明也就是在说“如果你在根S的状态树上运行交易T，其结果状态树将是根为S'，log为L，输出为O” （“输出”作为存在于以太坊的一种概念，因为每一笔交易都是一个函数调用；它在理论上并不是必要的）。
　　为了推断这个证明，服务器在本地创建了一个假的区块，将状态设为 S，并在请求这笔交易时假装是一个轻客户端。也就是说，如果请求这笔交易的过程，需要客户端确定一个账户的余额，这个轻客户端(由服务器模拟的)会发出一个余额查询请求。如果需要轻客户端在特点某个合约的存储中查询特定的条目，这个轻客户端就会发出这样的请求。也就是说服务器(通过模拟一个轻客户端)正确回应所有自己的请求，但服务器也会跟踪它所有发回的数据。然后，服务器从上述的这些请求中把数据合并并把数据以一个证明的方式发送给客户端。然后，客户端会进行相同的步骤，但会将服务器提供的证明作为一个数据库来使用。如果客户端进行步骤的结果和服务器提供的是一样的话，客户端就接受这个证明。