比特币架构简述之Merkle树

来源于bitcoin wiki
Merkle Trees
Merkle树是哈希值构成的二叉树。比特币中的Merkle树使用双 SHA-256，即SHA-256散列的SHA-256散列。

在树中（树的根除外）形成一行时，若这一行目前一共有奇数个元素，则最末尾的这个双重哈希值将被复制以确保该行具有偶数个哈希值。

首先形成树的底部行，其中块里面的交易是有序的，顺序按照交易的双SHA-256散列的字节流记性排序（有点绕口啊，大意就是按照每个交易的哈希值进行排序）。

那么它上面的那行的哈希值个数就是当前行的哈希值数目的一半。每个条目都是树中它下面相应两个哈希的64字节连接的双SHA-256。

这个过程以递归的方式重复，直到我们到达由单个双重散列组成的行。这是树的Merkle根。

例如，想象一个包含三个事务a，b和c的块。梅克尔树是：
dhash(a) = sha256(sha256(a))//双哈希

//底部的行
d1 = dhash(a)
d2 = dhash(b)
d3 = dhash(c)
d4 = dhash(c)            # a, b, c 是 3. 这是个奇数，所以再取一遍c的双哈希

//倒数第二行
d5 = dhash(d1 concat d2)
d6 = dhash(d3 concat d4)

//树根
d7 = dhash(d5 concat d6)

d7是这个块中3个交易的Merkle根。
值得注意：块浏览器中显示的Merkle树中的哈希值是小端模式(符号)。对于某些实现和计算，这些字节在散列之前或之后需要反转操作。
附上一个地址：在线计算哈希