Merkle樹作為區塊鍊中重要的資料結構，有着很廣泛的應用。
基本就是每個葉節點作為資料存儲點，對它進行哈希之後，得到最初的葉子節點，再兩兩相加哈希，一直類推，到隻剩一個節點，即根節點即可。
說到哈希啊，就不得不提到祖師爺Leslie Lamport：
就當你發現Hash、LaTex，拜占庭将軍問題、Paxos都是一個人搞出來的之後，那種五體投地的感覺....orz
Leslie Lamport在1973年第一個提出hash簽名方案，hash有多偉大就不用說了吧。
Merkle樹其實最早不是應用在區塊鍊中的，Ralph Merkle：
他最先提出Merkle樹應用在數字簽名中：Merkle提出一種方法可以保持簽名N條不同的消息的能力，而公鑰成本沒有爆炸性增長。Merkle的方法大概類似這種：
Merkle樹在這裡有一個粗略的描述：它們提供了一種方法，用這種方法可以收集很多不同的值，這樣這些值可以由單個“根”散清單示。給出這個散列值，就很容易生成一個元素在hash樹中的簡單的證明，這個證明的大小是樹中葉節點的個數。比如說上圖，我要驗證OTS1是否正确，我隻需要驗證圖中黑色的H2和H6即可，根據H2和H6我們就能哈希出樹根，對比區塊中的樹根是否一緻即可。
那麼如何應用在區塊鍊中呢？
我們知道啊，區塊鍊中的資料和交易量都是非常大的，一般情況下，一個區塊中包含幾百上千筆交易是很常見的。由于區塊鍊的去中心化特性，網絡中的每個節點必須是獨立，自給自足的，也就是每個節點必須存儲一個區塊鍊的完整副本。那麼随着越來越多的交易，以及越來越多的挖礦，資料存儲成為了一筆巨大的開銷。
如何縮小這筆開銷呢？
區塊鍊中每個區塊都會有一個 Merkle 樹，它從葉節點開始，一個葉節點就是一個交易哈希。葉節點的數量必須是雙數，但是并非每個塊都包含了雙數的交易。如果一個塊裡面的交易數為單數，那麼就将最後一個葉節點（也就是Merkle樹的最後一個交易，不是區塊的最後一筆交易）複制一份湊成雙數。
從下往上，兩兩成對，連接配接兩個節點哈希，将組合哈希作為新的哈希。新的哈希就成為新的樹節點。重複該過程，直到僅有一個節點，也就是樹根。根哈希然後就會當做是整個塊交易的唯一标示，将它儲存到區塊頭，然後用于工作量證明。
也就是說，我們不必存儲所有的交易資訊在區塊中，隻需存儲Merkle樹根就行了，大大減小了存儲量。
像上圖這樣，就不用把所有交易存儲下來啦~
那麼，如何用代碼優雅的實作它呢？
Merkle樹有一個特點，初始化時它的葉節點個數必須是雙數，如果不是雙數，那麼複制最後一個葉節點湊成雙。
Duang~代碼來了
老規矩，先引入包：
package main
import (
"crypto/sha256"
"fmt"
"strconv"
) 定義Merkle樹和樹節點資料結構：
type MerkleTreeNode struct {
Data []byte
Hash []byte
Left *MerkleTreeNode
Right *MerkleTreeNode
}
type MerkleTree struct {
Root *MerkleTreeNode
} 實作一個隊列，簡單的Push和Pop，友善建樹，因為建樹肯定是每次兩兩合并，新生成的節點放後面，類似于哈夫曼樹建樹過程：
type Queue struct {
List []MerkleTreeNode
}
func NewQueue() *Queue {
list := make([]MerkleTreeNode, 0)
return &Queue{list}
}
func (q *Queue) Push(node *MerkleTreeNode) {
q.List = append(q.List, *node)
}
func (q *Queue) Pop() *MerkleTreeNode {
if q.Len() == 0 {
panic("Empty!")
}
node := q.List[0]
q.List = q.List[1:]
return &node
}
func (q *Queue) Len() int {
return len(q.List)
} 生成Merkle樹節點部分，注意啊，因為Merkle樹是一種完全二叉樹，是以它的節點隻有兩種情況：兩個孩子的非葉節點和無孩子的葉節點：
func NewMerkleTreeNode(left, right *MerkleTreeNode, data []byte) *MerkleTreeNode {
var node MerkleTreeNode
if left == nil && right == nil {
hash := sha256.Sum256(data)
node.Hash = hash[:]
} else {
childHash := append(left.Hash, right.Hash...)
hash := sha256.Sum256(childHash)
node.Hash = hash[:]
}
node.Left = left
node.Right = right
node.Data = data
return &node
} 建樹函數，使用一個隊列來進行建樹：
func NewMerkleTree(data [][]byte) *MerkleTree {
var root MerkleTree
nodes := NewQueue()
if len(data)%2 != 0 {
data = append(data, data[len(data)-1])
}
for _, i := range data {
nodes.Push(NewMerkleTreeNode(nil, nil, i))
}
for nodes.Len() > 1 {
left := nodes.Pop()
right := nodes.Pop()
node := NewMerkleTreeNode(left, right, nil)
nodes.Push(node)
}
root.Root = nodes.Pop()
return &root
} 先序周遊看看咱們建立的樹是否成功：
func PreOrderVisit(root *MerkleTreeNode) {
if root != nil {
fmt.Print(root.Data)
PreOrderVisit(root.Left)
PreOrderVisit(root.Right)
}
} 寫個main函數看看結果呗，建立一個存儲6個資料的Merkle樹：
func main() {
data := make([][]byte, 6)
for i := 0; i < 6; i++ {
data[i] = []byte(strconv.Itoa(i))
}
root := NewMerkleTree(data)
PreOrderVisit(root.Root)
} 列印看看：
對應的樹就是這樣子：
好啦，簡單的Merkle樹就實作了，對于它的插入删除，那就是優化和工程問題了，二叉平衡樹啊紅黑樹啊伸展樹啊都可以的，主要是reigns還不能手撸一個紅黑樹，此事以後再議~