比特币区块链哈希树(MerkleRoot)的计算方法
在比特币代码里 block.h 头文件里声明区块头的结构，有下面几个字段，其中有一个叫哈希树(MerkleRoot) 的字段，它的作用是可以校验当前区块里所有的交易记录。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class CBlockHeader { public: // header int32_t nVersion; uint256 hashPrevBlock; uint256 hashMerkleRoot; uint32_t nTime; uint32_t nBits; uint32_t nNonce; //... }; |
MerkleRoot 是将当前区块里的所有交易记录的 Hash 使用二叉树的方式，层层相加并计算出新的 Hash，直到最后一个节点 Hash 就是MerkleRoot，这样只要有一笔交易出现被篡改，很容易定位到这笔交易。比如一个区块里有 4 条交易记录，每条交易记录的 Hash 我们分别定义成 H1、H2、H3、H4 变量，计算 MerkleRoot 的方法是下面这样的步骤。
（1） H1 和 H2 做一次大小端反转，然后相加计算出一个Hash，生成一个节点叫 H12。
（2） H3 和 H4 做一次大小端反转，然后相加计算出一个Hash，生成一个节点叫 H34。
（3） H12 和 H34 相加计算出一个Hash，最后的节点得到的 Hash 还需要做一次大小端反转，得到的结果就是 MerkleRoot。
步骤如下图所示：
每一次计算 Hash 是通过两次 sha256，最终得到计算 MaerkleRoot 的计算公式是：
|
1 2 |
sha256(sha256(sha256(sha256(H1+H2))+sha256(sha256(H3+H4)))) |
上面我们看到是交易数量是双数，如果交易数量是单数该怎么处理？比如只有 3 个交易，H1 和 H2 的处理没有变化，只是处理的过程会把 H3+H3 计算出一个 Hash 做为上层节点，如下图所示：
还有一种情况，如果交易数量只有一个呢？只有一个交易数量，不需要进行任何计算，直接将第一笔的交易 Hash 做为 MerkleRoot，比如区块高度是 0，也就是第一个区块，看到它的 MerkleRoot 和第一笔交易的 Hash 是完全一样的。如果区块里有两笔交易，H1+H2 计算 Hash 得到的 H12 节点是最后的根节点，也就是 MaerkleRoot。下面我们尝试在本地验证 MerkleRoot 计算的过程，比如找到区块高度 181，这个区块里有两笔交易，第一笔交易的 Hash 是8347cee4a1cb5ad1bb0d92e86e6612dbf6cfc7649c9964f210d4069b426e720a，大小端转换反转过后的十六进制数据是：
|
1 2 |
0a 72 6e 42 9b 06 d4 10 f2 64 99 9c 64 c7 cf f6 db 12 66 6e e8 92 0d bb d1 5a cb a1 e4 ce 47 83 |
第二笔交易的 Hash 是 a16f3ce4dd5deb92d98ef5cf8afeaf0775ebca408f708b2146c4fb42b41e14be 大小端转换反转过后的十六进制数据是：
|
1 2 |
be 14 1e b4 42 fb c4 46 21 8b 70 8f 40 ca eb 75 07 af fe 8a cf f5 8e d9 92 eb 5d dd e4 3c 6f a1 |
将两个交易记录的 Hash 大小端反转后再相加在一起，组合的结果如下：
|
1 2 |
0a726e429b06d410f264999c64c7cff6db12666ee8920dbbd15acba1e4ce4783be141eb442fbc446218b708f40caeb7507affe8acff58ed992eb5ddde43c6fa1 |
然后计算 sha256，第一次计算的结果是 4bb234b71d205dba7936c5e6241e1666479e56f0e370e7725de2c99e6cf5de81，如下图所示：
第二次计算的 sha256 的结果是 366c2a0915f05db4b450c050ce7165acd55f823fee51430a8c993e0bdbb192ed，最后得到的 Hash 需要做一次大小端转换，得到的 merkleRoot 是 ed92b1db0b3e998c0a4351ee3f825fd5ac6571ce50c050b4b45df015092a6c36。
还可以编写 010editor 脚本来实现，具体代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
uchar sha256[32]; int count=ChecksumAlgBytes(CHECKSUM_SHA256,sha256,0,0,"",-1,-1); Printf("sha256: %02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x\n", sha256[0], sha256[1],sha256[2], sha256[3],sha256[4], sha256[5], sha256[6], sha256[7],sha256[8], sha256[9],sha256[10], sha256[11],sha256[12], sha256[13], sha256[14], sha256[15], sha256[16], sha256[17],sha256[18], sha256[19], sha256[20], sha256[21], sha256[22], sha256[23], sha256[24], sha256[25], sha256[26], sha256[27], sha256[28], sha256[29], sha256[30], sha256[31]); uchar H12[32]; count=ChecksumAlgArrayBytes(CHECKSUM_SHA256,H12,sha256,32,"",-1,-1); //大小端转换反转 Printf("merkleRoot: %02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x\n", H12[31], H12[30], H12[29], H12[28], H12[27], H12[26], H12[25], H12[24], H12[23], H12[22], H12[21], H12[20], H12[19], H12[18], H12[17], H12[16], H12[15], H12[14], H12[13], H12[12], H12[11], H12[10], H12[9], H12[8], H12[7], H12[6], H12[5], H12[4], H12[3], H12[2], H12[1], H12[0]); |
输出的结果和我们手动用 010editor 验证的是一样的。
|
1 2 3 |
sha256: 4bb234b71d205dba7936c5e6241e1666479e56f0e370e7725de2c99e6cf5de81 merkleRoot: ed92b1db0b3e998c0a4351ee3f825fd5ac6571ce50c050b4b45df015092a6c36 |