深入区块链——比特币的Merkle Tree(第五讲)

导言

区块链(Blockchain)技术源于比特币,本质上其实是一个分布式的,不可篡改的数据库,具有可验证、可信任的特性。

本系列教程带你逐步深入理解区块链技术,并附带源码教程(主要使用PHP编写),但需要你对密码学原理、安全机制、共识算法、哈希算法有一定的认知。

教程源码:https://github.com/wenshunbiao/bitcoin-tutorial

正文

在计算Block Hash中,接触到一个变量mrkl_root,即Merkle Tree,默克尔树,Merkle Tree看起来非常像二叉树,其叶子节点上的值通常为数据块的哈希值,而非叶子节点上的值,所以有时候Merkle tree也表示为Hash Tree,如下图所示:

在构造Merkle Tree时,首先要对数据块计算哈希值,通常,选用SHA-256等哈希算法。然后将数据块计算的哈希值两两配对(如果是奇数个数,最后一个自己与自己配对),计算上一层哈希,再重复这个步骤,一直到计算出根哈希值。

Merkle Tree大多用来进行完整性验证,比如分布式环境下,从多台主机获取数据,怎么验证获取的数据是否正确呢,只要验证Merkle Tree根哈希一致,即可。

Merkle Tree还可以用来对数据进行快速比对,快速定位到不一致的数据。比如分布式存储中,一份数据会有多个副本,并且分布在不同的机器上。
为了保持数据一致性,需要进行副本同步,而首要的就是比对当前副本是否一致,如一致,则无需同步,如不一致,还需找出不一致的地方,然后进行同步。
很明显,如果采用直接传输数据进行比对,非常低效,一般采用对数据进行哈希,传输哈希值进行对比的方法。
为此,可以对每台机器需要比对的数据构造Merkle Tree,如果根哈希一致,则数据相同,如果根哈希不一致,则通过Merkle Tree快速检索到不一致的数据。

计算Merkle Tree

计算block高度123456的merkle tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
hash_tx1 = "5b75086dafeede555fc8f9a810d8b10df57c46f9f176ccc3dd8d2fa20edd685b"
hash_tx2 = "e3d0425ab346dd5b76f44c222a4bb5d16640a4247050ef82462ab17e229c83b4"
hash_tx3 = "137d247eca8b99dee58e1e9232014183a5c5a9e338001a0109df32794cdcc92e"
hash_tx4 = "5fd167f7b8c417e59106ef5acfe181b09d71b8353a61a55a2f01aa266af5412d"
hash_tx5 = "60925f1948b71f429d514ead7ae7391e0edf965bf5a60331398dae24c6964774"
hash_tx6 = "d4d5fc1529487527e9873256934dfb1e4cdcb39f4c0509577ca19bfad6c5d28f"
hash_tx7 = "7b29d65e5018c56a33652085dbb13f2df39a1a9942bfe1f7e78e97919a6bdea2"
hash_tx8 = "0b89e120efd0a4674c127a76ff5f7590ca304e6a064fbc51adffbd7ce3a3deef"
hash_tx9 = "603f2044da9656084174cfb5812feaf510f862d3addcf70cacce3dc55dab446e"
hash_tx10 = "9a4ed892b43a4df916a7a1213b78e83cd83f5695f635d535c94b2b65ffb144d3"
hash_tx11 = "dda726e3dad9504dce5098dfab5064ecd4a7650bfe854bb2606da3152b60e427"
hash_tx12 = "e46ea8b4d68719b65ead930f07f1f3804cb3701014f8e6d76c4bdbc390893b94"
hash_tx13 = "864a102aeedf53dd9b2baab4eeb898c5083fde6141113e0606b664c41fe15e1f"

mrkl_tree1_2 = double_hash256(hash_tx1 + hash_tx2)
mrkl_tree3_4 = double_hash256(hash_tx3 + hash_tx4)
mrkl_tree5_6 = double_hash256(hash_tx5 + hash_tx6)
mrkl_tree7_8 = double_hash256(hash_tx7 + hash_tx8)
mrkl_tree9_10 = double_hash256(hash_tx9 + hash_tx10)
mrkl_tree11_12 = double_hash256(hash_tx11 + hash_tx12)
mrkl_tree13_13 = double_hash256(hash_tx13 + hash_tx13) #奇数个数,自己与自己配对

mrkl_tree1_2_3_4 = double_hash256(mrkl_tree1_2 + mrkl_tree3_4)
mrkl_tree5_6_7_8 = double_hash256(mrkl_tree5_6 + mrkl_tree7_8)
mrkl_tree9_10_11_12 = double_hash256(mrkl_tree9_10 + mrkl_tree11_12)
mrkl_tree13_13_13_13 = double_hash256(mrkl_tree13_13 + mrkl_tree13_13) #奇数个数,自己与自己配对

mrkl_tree1_2_3_4_5_6_7_8 = double_hash256(mrkl_tree1_2_3_4 + mrkl_tree5_6_7_8)
mrkl_tree9_10_11_12_13_13_13_13 = double_hash256(mrkl_tree9_10_11_12 + mrkl_tree13_13_13_13)

mrkl_root = double_hash256(mrkl_tree1_2_3_4_5_6_7_8 + mrkl_tree9_10_11_12_13_13_13_13)

echo mrkl_root
// 0e60651a9934e8f0decd1c5fde39309e48fca0cd1c84a21ddfde95033762d86c

计算过程中注意大小端的数据转换,大小端数据转换参考 https://www.jianshu.com/p/7623cec7620a

完整源码实现,请看 教程源码:https://github.com/wenshunbiao/bitcoin-tutorial

评论