比特币中MerkleTree默克尔树的构造

有点比特币基础的应该都知道，在一个区块的区块头中有一个字段叫RootHash，这个根哈希是该区块中所有交易构建默克尔树之后计算的树根哈希。但是基本上所有的文章都只说到如果交易数不是偶数个的时候需要补齐，但是具体怎么补齐呢？下面简单说明一下，以解这个细节上的疑惑。

一、3个交易时

如果只有3个交易Tx1，Tx2，Tx3，那么在构造默克尔树的时候，只需要把最后的那个Tx3和自己再算相加，计算Hash33即可。如图：

Tx3

二、5个交易时

如果是有4个交易，那最简单，没什么好说的，接下来说如果有5个交易的情形，那么这里就需要做多次自己和自己相加，然后计算上一级哈希的情况，具体计算如图：

Tx5

三、6个交易时

那么如果有6个交易的时候，是把Tx6复制多次进行填充吗？不是的！！！而是在计算的过程中遇到单个Hash的时候进行重复，也就是对H56就行重复，所以实际上是把Tx5和Tx6进行了填充，如图：

UntitledImage

总之在计算默克尔树的根哈希时，都是简单的从下到上层层推进，每一层在算的时候如果下面的哈希是奇数，就复制一个哈希，在5个交易时，计算H55就是复制了一份H5，然后上一层计算H5555的时候下面又是奇数，所以复制了一份H55。同理在计算6个交易的默克尔树时，算H5656时，因为下面只有一个H56，所以复制了一份H56。对于更大量的交易数的时候，处理逻辑都是这样的。