Merkle Tree：
是一种树（数据结构中所说的树），可用于简易支付验证SPV
在比特币中，每个块都会有一个 Merkle 树，它从叶子节点（树的底部）开始，一个叶子节点就是一个交易哈希（比特币使用双 SHA256 哈希）。叶子节点的数量必须是双数，但是并非每个块都包含了双数的交易。因为，如果一个块里面的交易数为单数，那么就将最后一个叶子节点（也就是 Merkle 树的最后一个交易，不是区块的最后一笔交易）复制一份凑成双数。
从下往上，两两成对，连接两个节点哈希，将组合哈希作为新的哈希。新的哈希就成为新的树节点。重复该过程，直到仅有一个节点，也就是树根。根哈希然后就会当做是整个块交易的唯一标示，将它保存到区块头，然后用于工作量证明。
Merkle 树的好处就是一个节点可以在不下载整个块的情况下，验证是否包含某笔交易。并且这些只需要一个交易哈希，一个 Merkle 树根哈希和一个 Merkle 路径。
代码实现
package main
import "crypto/sha256"
//Merkle 树的作用:一个节点可以在不下载整个块的情况下，验证是否包含某笔交易。
// 并且这些只需要一个交易哈希，一个 Merkle 树根哈希和一个 Merkle 路径。
//默克尔树
type MerkleTree struct {
RootNode *MerkleNode
}
//节点
type MerkleNode struct {
Left *MerkleNode
Right *MerkleNode
data []byte
}
//创建默克尔树
func NewMerkleTree(data [][]byte) *MerkleTree {
var nodes []MerkleNode
if len(data) % 2 != 0 { //如果节点数为单数,复制最后一个节点数据并追加
data = append(data, data[len(data) - 1])
}
for _, datum := range data {
node := NewMerkleNode(nil, nil, datum)
nodes = append(nodes, *node)
}
for i := 0; i < len(data)/2; i++ { //一层层向上合并
var newlevel []MerkleNode
for j := 0; j < len(nodes); j += 2 {
node := NewMerkleNode(&nodes[j],&nodes[j+1],nil)
newlevel = append(newlevel, *node)
}
nodes = newlevel
}
mTree := MerkleTree{&nodes[0]}
return &mTree
}
//创建一个节点
func NewMerkleNode(left ,right *MerkleNode, data []byte) *MerkleNode {
mNode := MerkleNode{}
if left == nil && right == nil {
hash := sha256.Sum256(data)
mNode.data = hash[:]
} else {
preHashes := append(left.data, right.data...)
hash := sha256.Sum256(preHashes)
mNode.data = hash[:]
}
mNode.Left = left
mNode.Right = right
return &mNode
}
func (b *Block) HashTransactions() []byte {
var transactions [][]byte
for _, tx := range b.Transactions {
transactions = append(transactions, tx.Serialize())
}
mTree := NewMerkleTree(transactions)
return mTree.RootNode.Data
} |
