MerkleTree in BTC

Merkle 树是一种用于高效且安全地验证大数据结构完备性和一致性的哈希树。它在比特币网络中起到至关告急的作用。Merkle 树是一种二叉树结构，此中每个叶子节点包含数据块的哈希值，每个非叶子节点包含其子节点哈希值的组合哈希。
比特币网络中的 Merkle 树

在比特币区块链中，每个区块包含多个交易。为了高效地验证区块内的交易，比特币使用了 Merkle 树。区块头包含一个 Merkle 根（Merkle Root），代表了该区块内所有交易的哈希摘要。
Merkle 树的构建

• 叶子节点：每笔交易的哈希值被用作叶子节点。
  
• 非叶子节点：每对叶子节点的哈希值被组合并哈希，形成上一级节点。这个过程递归进行，直到形成唯一的根节点，即 Merkle 根。
  

Merkle 树的生成示例

假设一个区块包含四笔交易 \(T1\)、\(T2\)、\(T3\) 和 \(T4\)。生成 Merkle 树的步骤如下：

• 计算每笔交易的哈希值 \(H1\)、\(H2\)、\(H3\)、\(H4\)：
  
  \[H1 = \text{Hash}(T1) \]
  
  \[H2 = \text{Hash}(T2) \]
  
  \[H3 = \text{Hash}(T3) \]
  
  \[H4 = \text{Hash}(T4) \]
  
• 计算相邻交易哈希的组合哈希 \(H12\) 和 \(H34\)：
  
  \[H12 = \text{Hash}(H1 || H2) \]
  
  \[H34 = \text{Hash}(H3 || H4) \]
  
• 计算根节点哈希 \(H1234\)：
  
  \[H1234 = \text{Hash}(H12 || H34) \]
  

最终，\(H1234\) 就是包含这四笔交易的 Merkle 根。
Merkle 树的作用

• 验证交易：通过 Merkle 树，可以高效地验证某笔交易是否包含在某个区块中，而不需要检查整个区块。
  
• 轻客户端（SPV）：简化付出验证（SPV）客户端可以通过请求区块头和所需交易的 Merkle 路径来验证交易，而不需要下载整个区块链。
  

Merkle 路径验证

假设我们要验证交易 \(T3\) 是否在某个区块中：

• 获取交易 \(T3\) 的哈希 \(H3\)。
  
• 获取 \(H3\) 的相邻哈希 \(H4\)。
  
• 计算组合哈希 \(H34 = \text{Hash}(H3 || H4)\)。
  
• 获取 \(H34\) 的相邻哈希 \(H12\)。
  
• 计算根节点哈希 \(H1234 = \text{Hash}(H12 || H34)\) 并与区块头中的 Merkle 根比较。
  

如果计算出的根哈希值与区块头中的 Merkle 根匹配，则验证成功，阐明交易 \(T3\) 包含在该区块中。
btcd 中的 Merkle 树实现

在 btcd 中，Merkle 树的实现主要在 blockchain/merkle.go 文件中。以下是该文件中关键部分的详细阐明：

1. // HashMerkleBranches 采用两个哈希值，分别视为左树节点和右树节点，并返回它们串联的哈希值。用于帮助生成默克尔树
2. func HashMerkleBranches(left, right *chainhash.Hash) chainhash.Hash {
3.         // Concatenate the left and right nodes.
4.         var hash [chainhash.HashSize * 2]byte
5.         copy(hash[:chainhash.HashSize], left[:])
6.         copy(hash[chainhash.HashSize:], right[:])
8.         return chainhash.DoubleHashRaw(func(w io.Writer) error {
9.                 _, err := w.Write(hash[:])
10.                 return err
11.         })
12. }
14. // BuildMerkleTreeStore creates a merkle tree from a slice of transactions,
15. // stores it using a linear array, and returns a slice of the backing array.  A
16. // linear array was chosen as opposed to an actual tree structure since it uses
17. // about half as much memory.  The following describes a merkle tree and how it
18. // is stored in a linear array.
19. func BuildMerkleTreeStore(transactions []*btcutil.Tx, witness bool) []*chainhash.Hash {
20.         // Calculate how many entries are required to hold the binary merkle
21.         // tree as a linear array and create an array of that size.
22.         nextPoT := nextPowerOfTwo(len(transactions))
23.         arraySize := nextPoT*2 - 1
24.         merkles := make([]*chainhash.Hash, arraySize)
26.         // Create the base transaction hashes and populate the array with them.
27.         for i, tx := range transactions {
28.                 // If we're computing a witness merkle root, instead of the
29.                 // regular txid, we use the modified wtxid which includes a
30.                 // transaction's witness data within the digest. Additionally,
31.                 // the coinbase's wtxid is all zeroes.
32.                 switch {
33.                 case witness && i == 0:
34.                         var zeroHash chainhash.Hash
35.                         merkles[i] = &zeroHash
36.                 case witness:
37.                         wSha := tx.MsgTx().WitnessHash()
38.                         merkles[i] = &wSha
39.                 default:
40.                         merkles[i] = tx.Hash()
41.                 }
43.         }
45.         // Start the array offset after the last transaction and adjusted to the
46.         // next power of two.
47.         offset := nextPoT
48.         for i := 0; i < arraySize-1; i += 2 {
49.                 switch {
50.                 // When there is no left child node, the parent is nil too.
51.                 case merkles[i] == nil:
52.                         merkles[offset] = nil
54.                 // When there is no right child, the parent is generated by
55.                 // hashing the concatenation of the left child with itself.
56.                 case merkles[i+1] == nil:
57.                         newHash := HashMerkleBranches(merkles[i], merkles[i])
58.                         merkles[offset] = &newHash
60.                 // The normal case sets the parent node to the double sha256
61.                 // of the concatenation of the left and right children.
62.                 default:
63.                         newHash := HashMerkleBranches(merkles[i], merkles[i+1])
64.                         merkles[offset] = &newHash
65.                 }
66.                 offset++
67.         }
69.         return merkles
70. }

复制代码

BuildMerkleTreeStore 从交易切片创建默克尔树，使用线性数组存储它，并返回支持数组的切片。选择线性数组而不是实际的树结构，因为它可以节流约莫一半的内存。下面描述了merkle树以及它如何存储在线性数组中。

1.          root = h1234 = h(h12 + h34)
2.         /                           \
3.   h12 = h(h1 + h2)            h34 = h(h3 + h4)
4.    /            \              /            \
5. h1 = h(tx1)  h2 = h(tx2)    h3 = h(tx3)  h4 = h(tx4)

复制代码

以上存储为线性数组如下：

1. [h1 h2 h3 h4 h12 h34 root]

复制代码

如上所示，默克尔根始终是数组中的末了一个元素。
  

声明：本作品采用署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)进行允许，使用时请注明出处。
Author: mengbin
blog: mengbin
Github: mengbin92
cnblogs: 恋水无意
腾讯云开发者社区：孟斯特

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。