来源于 bitcoin wiki
Merkle Trees
Merkle 树是哈希值构成的二叉树.比特币中的 Merkle 树使用双 SHA-256,即 SHA-256 散列的 SHA-256 散列.
在树中(树的根除外)形成一行时,若这一行目前一共有奇数个元素,则最末尾的这个双重哈希值将被复制以确保该行具有偶数个哈希值.
首先形成树的底部行,其中块里面的交易是有序的,顺序按照交易的双 SHA-256 散列的字节流记性排序(有点绕口啊,大意就是按照每个交易的哈希值进行排序).
那么它上面的那行的哈希值个数就是当前行的哈希值数目的一半.每个条目都是树中它下面相应两个哈希的 64 字节连接的双 SHA-256.
这个过程以递归的方式重复,直到我们到达由单个双重散列组成的行.这是树的 Merkle 根.
例如,想象一个包含三个事务 a,b 和 c 的块.梅克尔树是:
d7 是这个块中 3 个交易的 Merkle 根.
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)
值得注意: 块浏览器 中显示的 Merkle 树中的哈希值是小端模式 (符号).对于某些实现和计算,这些字节在散列之前或之后需要反转操作.
附上一个地址: 在线计算哈希
来源: http://www.jianshu.com/p/8113d318cd9c