区块链如何运用merkle tree验证交易真实性

merkle tree就是一个 hash 二叉树，父节点是两个子节点的 double sha256 的结果，叶子节点就是交易的 content 的 double sha256 结果。

上图中最下面那一层就是交易数据，每一个交易都可以计算出一个hash，从而层层向上，得到merkle root。但是由于blockchain里面都merkle运算要求叶子节点是偶数，所以，当一个区块内包含当交易数量为奇数时，把最后一个交易复制一份，凑成偶数。

最后就是把merkle root保存在区块头中，交易数据被保存在区块体中，其实中间当那些 hash 并没有被保存，它们只是运算过程数据。

SPV

为什么要搞这么复杂？直接把所有交易数据保存起来了，要验证交易是否存在还不简单吗？之所以要这么干，是因为比特币发明之初，中本聪想到有一种轻钱包的设计，这就是简化支付验证 SPV（Simplified Payment Verification）。

轻钱包并不保存完整的区块链，而是只保存每一个区块的区块头。区块体保存了完整的交易信息，而交易信息需要的存储量大部分都是交易头的千倍以上。所以，如果只保存交易头，就可以极大的减少本地客户端存储的区块链信息。

但是，不能因此让区块链无法工作啊。如果这个时候轻钱包要对某一个交易进行验证，而本地又没有这个交易的信息，那怎么验证呢？这时，区块头里面的merkle root就要起作用了。

验证路径

在讲述轻钱包的验证过程之前，我们需要知道如何在merkle tree里面做验证。我们已知merkle tree里面父节点和子节点的运算关系，因此，当我们要证明一个叶子节点存在于这棵树时，只需要得到从该叶子节点到根的运算过程里面需要的那些hash即可，并不需要所有叶子节点参与计算。

你可能觉得有点奇怪，为什么不直接把所有的叶子节点告诉它就行了，你用所有叶子节点能算出root hash就验证通过了。但事实就是这样，因为每一个父节点hash一定是由两个子节点hash运算得到，所以，我们只需要挑选出所有参与运算的节点，就可以证明这个叶子节点存在于树中。这样可以减少hash运算的次数。而这些被挑选出来的节点，以及它们之间的层级关系，就是验证路径，即上图中merkle root那个盒子下面的所有盒子。

如何证明交易的真实性？

比特币网络中的交易，只有已经被记录到区块链，并且已经得到6个确认的，才被认为是真实的，只有基于这些真实交易发起的新交易（输入与输出的概念），才是合法的。

我们询问一个交易是否真实，往往基于以下前提：

• 我们在问一个交易是否已被记录到区块链中
• 而且这个交易所在的区块链是最长的哪一条，没有在分叉链上
• 当每个节点接收到一条交易广播时，我们要查询作为一笔新交易的输入的真实性
• 矿工对交易进行打包之前，对所有的输入进行真实性验证（在矿工接收到交易信息时就已经验证过了，打包的时候验证2000条交易信息不可能）

那么对于SPV轻钱包而言，怎么知道一个交易是否真实的呢？SPV拿到一个交易信息之后（比如接收到一笔钱），并不能确认这个交易是否合法，因此要对这个交易的输入进行验证。但是它只拿到了单个交易的信息，而没有本地的完整区块链数据，因此，SPV要拿着这个交易的信息向网络发起查询请求，这个请求被称为merkle block message。当其他有完整区块链数据的客户端收到这个请求之后，利用传过来的交易信息在自己的区块链数据库中进行查询，并把验证路径返回给请求源，SPV拿到验证路径之后，再做一次merkle校验，确认无误之后，就认为这个交易是可信的。

现在的问题是：

• 怎么从区块链里面查一个交易？
• 怎么获取merkle验证路径？
• 怎么确保网络上这个返回的验证路径不是伪造的？

从区块链查交易

区块链的数据结构是离散的，比特币里面一个区块被保存在一个文件里面，要得到一个交易的验证路径，必须得到这个交易所在的区块链。这是一个复制的查询过程，可能需要把所有的区块都遍历一遍才能找到。因此，blockchain.info这样的网站孕育而生，帮助你通过一个信息查这个信息在区块链上的所有相关记录。但是对于客户端而言，可没那么容易，它不能信任blockchain.info这个网站，只能信任自己本地存储的区块链。所以，只能用比较合理的算法，去优化交易查询。

一种设计是，把每一个区块的数据结构修改为关系型数据库，通过关系型数据库，可以用sql语句快速查询。但是，要遍历查询所有区块链，是比较浪费的。还有一种想法是，利用交易的时间戳来快速定位区块位置，在临近的几个区块中快速找到它。

如何获取merkle验证路径？

实际上，merkle的验证路径生成的前提是已经存在一棵完整的merkle树。市面上有很多merkle树的实现包，有的包直接给出来getProof的方法来获取某个叶子节点的验证路径。

在客户端收到merkle block message之后，要执行下面的步骤：

1. 通过上述方法找到包含该交易的区块
2. 检查该区块是否是整个网络中最长链条里面的
3. 取出所有交易生成merkle tree，利用getProof方法得到该交易的验证路径
4. 将该验证路径发送回请求源

SPV得到响应之后，要做如下验证：

1. 同步区块链，确保是整个网络中最长的一条
2. 先拿到merkle root去区块链中查找，确保该merkle root hash是在链条中
3. 利用拿到的验证路径，再进行一次merkle校验，确保验证路径全部合法

为什么SPV还要再做一次merkle校验呢？主要是为了确保响应方发送的验证路径的有效性。

确保验证路径的真实性

上面提到了SPV还要做一次merkle校验，这也是“不信任”的表现之一。我们并不确保响应我们的节点不会作弊或欺诈，因此，我们要自己进行校验。但是，有没有可能虽然校验过程顺利，但是实际上校验路径是伪造的呢？

我们来做一个假设：1）merkle root为真；2）交易为假；3）路径中的hash可真可假。这个假设是否成立？

我们知道，不同字符串碰撞到同一个sha256的概率极小，那么double sha256的概率就是它的平方，而merkle root是经过一层一层计算上来的，如果一个区块只有一个（或2个）交易，那么就是double^(2+1) sha256，而如果是4个交易，就有double^(4 + 2 + 1) sha256，更何况一个区块有那么多交易，要经过merkle运算得到一个相同的hash，几乎是不可能的，因此，在merkle验证中用一个伪造的交易hash来得到一个已知来merkle root是不可能的。

如果还想更进一步校验，可以在区块头中存储区块打包的交易的数量，这样就可以知道从交易hash到merkle root需要经过几层的运算。这也是一个检验点。

小结

merkle tree被广泛运用于区块链中，但并不是只有区块链使用它来进行校验。比如一些p2p下载，如迅雷，就需要把文件分割为小块文件，每块都有一个hash，每块从不同的网络节点下载，最后组成一个完整的文件，但是也需要进行hash验证，它也可以使用merkle来进行验证。merkle tree也不一定是二叉树，可以是任意树结构。而在以太坊中，merkle验证还不够用，增加了Patricia Tree验证，合起来称为“Merkle Patricia Tree”。