比特幣中使用哈希指針保存前一個區塊頭的哈希值，將多個區塊連接成一條鏈，保證了區塊鏈的不可篡改特性。比特幣還使用梅克爾樹保存區塊體中的交易數據，從最底層的交易數據通過哈希指針層層傳遞到根哈希，濃縮了所有的交易數據，提高了篡改交易的難度。梅克爾樹還提供交易數據隸屬證明和非隸屬證明的高效方法，時間複雜度均爲O(log N)。

哈希指針H( )

比特幣中通過哈希指針將多個區塊連接成一條鏈。在本質上，區塊鏈也是一個鏈表，只不過用哈希指針代替了普通指針。

爲了說明哈希指針的優點，我們先了解一下 單向鏈表(singly-linked list)和普通指針 。

以C++爲例，單向鏈表中的節點通常是結構體數據類型，包含節點的值val和指向下一個節點的指針next。

//單向鏈表節點 結構體，包含節點的值val和指向下一個節點的指針next
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

Node 0又稱爲根節點(root node)，根節點是鏈表的初始節點，沒有指向任何節點，因此根節點的next指針爲空(Node 0.next = NULL)。Node 1中的next指針存儲了Node 0的地址(Node 1. next = Node 0_address)，指向Node 0。同理，Node 2指向Node1， Node 3指向Node 2... 如果要往鏈表中加入新節點，只需要新建一個節點，並將新節點的next指針指向鏈表的末尾節點。鏈表相比於數組的優勢是什麼？鏈表的可擴展性更強，一個數組中的元素在磁盤上是先申請一塊空間然後連續存儲的，而鏈表中的節點元素可以存儲在不同的磁盤位置，通過指針存儲下一個節點的地址，然後去磁盤上尋址找到下一個節點。如果要修改鏈表中的某個節點的值，我們可以尋址找到該節點，並修改節點的值val即可。

在使用普通指針的單向鏈表中，我們可以隨意修改任意節點的值val，而不會破壞鏈表的完整性。如果比特幣也採用普通指針連接成一個普通鏈表，那我們就可以任意修改區塊中的交易信息，這就破壞了區塊鏈的不可篡改特性(嚴格來說，是難以篡改)。 相比於普通指針，哈希指針不僅能把區塊連接成一條鏈，還能保證區塊不可篡改。 一個區塊(Block)的結構，包含區塊頭(Block Header)和區塊體(Block Body) ，下圖簡單列舉了Block Header和Block Body中包含的數據信息，區塊結構的具體內容我將在系列博客3-比特幣協議中詳細講解。

哈希指針H( )是對上一個區塊的Block Header取哈希值，Block Header中的Merkle Tree哈希值已經包含了Block Body的信息，這也是爲什麼只需要對Block Header 取哈希的原因，減少了哈希函數的輸入數據大小從而提高哈希運算的速度。Block 0又稱爲創世區塊(genesis block)，Block 1中的H()爲Block 0 header的哈希值，Block 2中的H()爲Block 1 header的哈希值······ 如果有新區塊要加進來，只需把最末尾區塊的header哈希值計算出來，放在新區塊的header中即可，這樣就連接成了一條區塊鏈。

哈希指針提高了篡改的難度，防止篡改區塊中的數據。假設我修改了Block 1中的數據，那麼根據哈希函數的碰撞阻力特性，Block 1 header的哈希值發生變化，那麼我就要修改Block 2 header中的哈希指針，Block 2 header發生變化，同理我也需要修改Block 3 header······ 相當於一個連鎖反映，篡改區塊鏈中的某個區塊，就需要篡改該區塊之後的所有區塊，大大提高了篡改區塊的難度 。

Merkle Tree(梅克爾樹)

Block body中存儲交易信息的數據結構就是Merkle Tree。Merkle Tree根哈希反映了所有的交易信息，修改任意一個交易數據都會造成根哈希的變化，防止篡改交易數據，並且能夠快速驗證某筆交易屬於這個區塊(隸屬證明)或者不屬於這個區塊(非隸屬證明)。

相比於普通的二叉樹，Merkle Tree採用了哈希指針代替普通指針，提高了篡改交易的難度。 Merkle Tree的最底層葉子節點存的是交易信息 ，對每一筆交易取哈希值得到H( )，兩個相鄰的H()拼接在一起作爲兩個相鄰哈希指針節點的父節點，依次迭代，最終得到Merkle Tree的根節點。根節點也是由兩個子節點的哈希值拼接在一起的， 根節點相當於包含了所有的交易信息，假設任意一筆交易信息變化，都會層層傳遞導致根節點的變化 。最終，對Merkle Tree的根節點取哈希值，存在區塊頭的Merkle Tree Hash字段中，從而保證區塊頭包含了所有的交易信息， 任意一筆交易信息變化層層傳遞導致區塊頭的變化，該區塊頭的變化又會導致區塊頭取哈希值的變化，塊塊傳遞導致該區塊之後每一個區塊發生變化 ，提高了篡改交易信息的難度。

查找一筆交易是否屬於Merkle Tree，驗證一筆交易屬於Merkle Tree稱爲隸屬證明，反之成爲非隸屬證明。

隸屬證明

下圖中， 假設我們需要驗證一筆待證交易存在Merkle Tree中，只需要提供部分節點信息(下圖中紅圈部分)，經過自底向上的哈希運算後，最終算出Merkle Tree hash 。我們將哈希運算結果與該區塊頭中的Merkle Tree hash作比較，如果相等則證明了待證交易確實存在這個Merkle Tree中。

使用Merkle Tree做交易的隸屬證明，假設包含N筆交易，Merkle Tree的高度爲O(log N)+1，則 驗證一筆交易的時間複雜度爲O(log N) 。

非隸屬證明

如何證明一筆交易不屬於Merkle Tree？方法是使用 排序梅克爾樹(sorted Merkle Tree) ，相比於Merkle Tree， sorted Merkle Tree中最底層的交易數據是有序排列的 。先假設待證交易X在Tree中，根據有序排列的交易數據可以推算出排在待證交易之前的交易A和排在待證交易之後的交易B，如果我們使用隸屬證明中的方法證明了交易A和B都隸屬於sorted Merkle Tree且交易A和B是相鄰緊挨着的（時間複雜度爲O(log N)），那麼意味着在樹中A和B之間是沒有空間放下待證交易X的，從而證明了待證交易X不隸屬於Merkle Tree。

小結

比特幣中使用哈希指針保存前一個區塊頭的哈希值，將多個區塊連接成一條鏈，保證了區塊鏈的不可篡改特性。比特幣還使用梅克爾樹保存區塊體中的交易數據，從最底層的交易數據通過哈希指針層層傳遞到根哈希，濃縮了所有的交易數據，提高了篡改交易的難度。梅克爾樹還提供交易數據隸屬證明和非隸屬證明的高效方法，時間複雜度均爲O(log N)。

參考文獻：

  1. 北京大學肖臻老師《區塊鏈技術與應用》公開課
  2. 《區塊鏈 技術驅動金融：數字貨幣與智能合約技術》[美] 阿爾文德·納拉亞南（Arvind Narayanan），約什·貝努 等 著，林華，王勇，帥初 等 譯

哈希指針H( )

比特幣中通過哈希指針將多個區塊連接成一條鏈。在本質上，區塊鏈也是一個鏈表，只不過用哈希指針代替了普通指針。

爲了說明哈希指針的優點，我們先了解一下 單向鏈表(singly-linked list)和普通指針 。

以C++爲例，單向鏈表中的節點通常是結構體數據類型，包含節點的值val和指向下一個節點的指針next。

//單向鏈表節點 結構體，包含節點的值val和指向下一個節點的指針next
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

Node 0又稱爲根節點(root node)，根節點是鏈表的初始節點，沒有指向任何節點，因此根節點的next指針爲空(Node 0.next = NULL)。Node 1中的next指針存儲了Node 0的地址(Node 1. next = Node 0_address)，指向Node 0。同理，Node 2指向Node1， Node 3指向Node 2... 如果要往鏈表中加入新節點，只需要新建一個節點，並將新節點的next指針指向鏈表的末尾節點。鏈表相比於數組的優勢是什麼？鏈表的可擴展性更強，一個數組中的元素在磁盤上是先申請一塊空間然後連續存儲的，而鏈表中的節點元素可以存儲在不同的磁盤位置，通過指針存儲下一個節點的地址，然後去磁盤上尋址找到下一個節點。如果要修改鏈表中的某個節點的值，我們可以尋址找到該節點，並修改節點的值val即可。

在使用普通指針的單向鏈表中，我們可以隨意修改任意節點的值val，而不會破壞鏈表的完整性。如果比特幣也採用普通指針連接成一個普通鏈表，那我們就可以任意修改區塊中的交易信息，這就破壞了區塊鏈的不可篡改特性(嚴格來說，是難以篡改)。 相比於普通指針，哈希指針不僅能把區塊連接成一條鏈，還能保證區塊不可篡改。 一個區塊(Block)的結構，包含區塊頭(Block Header)和區塊體(Block Body) ，下圖簡單列舉了Block Header和Block Body中包含的數據信息，區塊結構的具體內容我將在系列博客3-比特幣協議中詳細講解。

哈希指針H( )是對上一個區塊的Block Header取哈希值，Block Header中的Merkle Tree哈希值已經包含了Block Body的信息，這也是爲什麼只需要對Block Header 取哈希的原因，減少了哈希函數的輸入數據大小從而提高哈希運算的速度。Block 0又稱爲創世區塊(genesis block)，Block 1中的H()爲Block 0 header的哈希值，Block 2中的H()爲Block 1 header的哈希值······ 如果有新區塊要加進來，只需把最末尾區塊的header哈希值計算出來，放在新區塊的header中即可，這樣就連接成了一條區塊鏈。

哈希指針提高了篡改的難度，防止篡改區塊中的數據。假設我修改了Block 1中的數據，那麼根據哈希函數的碰撞阻力特性，Block 1 header的哈希值發生變化，那麼我就要修改Block 2 header中的哈希指針，Block 2 header發生變化，同理我也需要修改Block 3 header······ 相當於一個連鎖反映，篡改區塊鏈中的某個區塊，就需要篡改該區塊之後的所有區塊，大大提高了篡改區塊的難度 。

Merkle Tree(梅克爾樹)

Block body中存儲交易信息的數據結構就是Merkle Tree。Merkle Tree根哈希反映了所有的交易信息，修改任意一個交易數據都會造成根哈希的變化，防止篡改交易數據，並且能夠快速驗證某筆交易屬於這個區塊(隸屬證明)或者不屬於這個區塊(非隸屬證明)。

相比於普通的二叉樹，Merkle Tree採用了哈希指針代替普通指針，提高了篡改交易的難度。 Merkle Tree的最底層葉子節點存的是交易信息 ，對每一筆交易取哈希值得到H( )，兩個相鄰的H()拼接在一起作爲兩個相鄰哈希指針節點的父節點，依次迭代，最終得到Merkle Tree的根節點。根節點也是由兩個子節點的哈希值拼接在一起的， 根節點相當於包含了所有的交易信息，假設任意一筆交易信息變化，都會層層傳遞導致根節點的變化 。最終，對Merkle Tree的根節點取哈希值，存在區塊頭的Merkle Tree Hash字段中，從而保證區塊頭包含了所有的交易信息， 任意一筆交易信息變化層層傳遞導致區塊頭的變化，該區塊頭的變化又會導致區塊頭取哈希值的變化，塊塊傳遞導致該區塊之後每一個區塊發生變化 ，提高了篡改交易信息的難度。

查找一筆交易是否屬於Merkle Tree，驗證一筆交易屬於Merkle Tree稱爲隸屬證明，反之成爲非隸屬證明。

隸屬證明

下圖中， 假設我們需要驗證一筆待證交易存在Merkle Tree中，只需要提供部分節點信息(下圖中紅圈部分)，經過自底向上的哈希運算後，最終算出Merkle Tree hash 。我們將哈希運算結果與該區塊頭中的Merkle Tree hash作比較，如果相等則證明了待證交易確實存在這個Merkle Tree中。

使用Merkle Tree做交易的隸屬證明，假設包含N筆交易，Merkle Tree的高度爲O(log N)+1，則 驗證一筆交易的時間複雜度爲O(log N) 。

非隸屬證明

如何證明一筆交易不屬於Merkle Tree？方法是使用 排序梅克爾樹(sorted Merkle Tree) ，相比於Merkle Tree， sorted Merkle Tree中最底層的交易數據是有序排列的 。先假設待證交易X在Tree中，根據有序排列的交易數據可以推算出排在待證交易之前的交易A和排在待證交易之後的交易B，如果我們使用隸屬證明中的方法證明了交易A和B都隸屬於sorted Merkle Tree且交易A和B是相鄰緊挨着的（時間複雜度爲O(log N)），那麼意味着在樹中A和B之間是沒有空間放下待證交易X的，從而證明了待證交易X不隸屬於Merkle Tree。

小結

比特幣中使用哈希指針保存前一個區塊頭的哈希值，將多個區塊連接成一條鏈，保證了區塊鏈的不可篡改特性。比特幣還使用梅克爾樹保存區塊體中的交易數據，從最底層的交易數據通過哈希指針層層傳遞到根哈希，濃縮了所有的交易數據，提高了篡改交易的難度。梅克爾樹還提供交易數據隸屬證明和非隸屬證明的高效方法，時間複雜度均爲O(log N)。

參考文獻：

  1. 北京大學肖臻老師《區塊鏈技術與應用》公開課
  2. 《區塊鏈 技術驅動金融：數字貨幣與智能合約技術》[美] 阿爾文德·納拉亞南（Arvind Narayanan），約什·貝努 等 著，林華，王勇，帥初 等 譯

本文參與登鏈社區寫作激勵計劃 ，好文好收益，歡迎正在閱讀的你也加入。

  • 發表於 25分鐘前
  • 閱讀 ( 9 )
  • 學分 ( 0 )
  • 分類：比特幣
相關文章