电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 区块链背后的密码学原理（2） [打印本页]

作者: look_w 时间: 2019-3-8 20:12 标题: 区块链背后的密码学原理（2）

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
}

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)