【BTC】數據結構

那比特幣區塊鏈的組織形式到底是以鏈表的形式，還是樹的形式呢？

區塊頭和區塊體與默克爾樹的關系

默克爾證明詳解

區塊鏈和鏈表最大的區別就是區塊鏈用哈希指針代替了普通指針。

鏈表的指針就是指向一個結構體在內存中的地址，而哈希指針除了記錄這一個區塊的地址外，還會記錄這個區塊的哈希值（這個哈希值是整個區塊所有數據進行哈希得到的），這樣就能更方便的驗證這個區塊是否被篡改過（如果被篡改過，那么哈希值肯定就和以前的不一樣了）。

第一個區塊就是創世紀塊，新創建出來的區塊會被追加在最后，每一個區塊有一個指向前序節點哈希指針。

基于區塊鏈的這種結果，實現了通過其中一個區塊的哈希值，就能推算出任何區塊的哈希值是否被篡改（防止數據篡改），每一個區塊的哈希值是根據自己以及前面的區塊計算得來的。因為只要有一個惡意節點篡改了其中一個節點的數據，這個結點哈希值變了，那么連帶著后面的所有結點哈希值都要跟這變，牽一發而動全身，這也就給了我們驗證的條件。

比特幣中的另外一個數據結構就是Merkle tree，他和binary tree（二叉樹）的一個區別就是用哈希指針代替了普通指針。

每個區塊之間是通過鏈表組織起來的，而每個區塊內部會存儲很多交易數據塊（tx）。這些區塊內部的交易數據塊是通過Merkle tree組織起來的。Merkle tree的葉子節點就是交易數據塊，上面的都是哈希指針節點，存儲的是哈希指針。同樣的道理，我們只要是有了根哈希指針（root hash index），我們就能判斷出鏈上的數據區塊的數據是否被篡改（因為只要是有一個區塊發生了變化，那么根哈希指針肯定也會變化），并且通過Merkle tree的結構，使得查詢速度有了很大提高。

只要記住根哈希值，就能檢測樹中任何部位的修改，如某個交易數據塊修改會傳導至根節點使根哈希值變化。

那比特幣區塊鏈的組織形式到底是以鏈表的形式，還是樹的形式呢？

在比特幣中，區塊鏈的組織形式本質上是鏈表結構，但同時結合了默克爾樹（Merkle Tree）這一樹狀結構來處理交易數據，二者相互配合，共同為區塊鏈的運行提供支持。

鏈表形式：區塊鏈由一個個區塊組成，這些區塊之間通過哈希指針依次連接，形成了類似鏈表的結構。其中，最前面的是創世紀塊，最后面的是最新產生的區塊。每個區塊的哈希指針是根據前面整個區塊的內容計算得出的。這種鏈表結構使得區塊鏈具有抗時間篡改的特性，任何對前面區塊內容的修改，都會導致后續所有區塊的哈希指針發生變化，從而被輕易檢測到。例如，若有人修改了中間某個區塊的內容，那么該區塊的哈希值會改變，這會使得下一個區塊中指向它的哈希指針不再匹配，并且這種影響會像多米諾骨牌一樣傳遞到后續所有區塊，最終導致系統中保存的最后一個區塊的哈希值也發生變化。
樹的形式（默克爾樹）：在每個區塊內部，交易數據是通過默克爾樹來組織的。默克爾樹底層的葉節點是一個個交易數據塊，上層的內部節點都是哈希指針。這些哈希指針是由下層相鄰數據塊的哈希值拼接后再取哈希得到的，層層向上直至根節點，根節點的哈希值保存在區塊頭（block header）中。默克爾樹的主要作用是提供默克爾證明（Merkle Proof），用于驗證交易是否存在于區塊中。比特幣節點分為全節點和輕節點，全節點保存整個區塊的內容，包括交易的具體信息；輕節點只保存區塊頭（比如我們本地下載的錢包，就只保存輕節點數據，用于驗證交易數據），當輕節點需要驗證某個交易時，全節點會提供從交易所在葉節點到根節點路徑上的哈希值，輕節點通過計算這些哈希值來驗證交易是否存在。

區塊鏈的整體數據結構如下：各個區塊用哈希指針連接，默克爾樹的根哈希值存于區塊頭（block header），區塊頭無交易具體內容，交易列表存于區塊體（block body），區塊體就存儲了默克爾樹的結構。

我們本地下載的錢包只會存儲輕節點，輕節點只存儲了區塊頭（block header），區塊頭中存儲了交易所在的默克爾樹的根哈希值，但并沒有存儲區塊鏈上的交易數據本身。

假設存在一個輕節點，該輕節點僅保存了 Merkle 樹的根哈希值（存于區塊的 block header 中），沒有保存交易列表及 Merkle 樹的具體內容。此時，輕節點想要驗證某一特定交易（PPT 中標為黃色的交易）是否存在于區塊中。

輕節點會向某個全節點發出請求（某一臺礦工機器），全節點收到請求后，將圖中標為紅色的三個哈希值發送給輕節點。輕節點在接收到這些哈希值后，在本地進行計算。首先計算黃色交易自身的哈希值（圖中標為綠色），然后將該綠色哈希值與全節點提供的相鄰紅色哈希值進行拼接，通過計算得出上一層節點中的綠色哈希值。按照這樣的方式，繼續將新得到的綠色哈希值與相鄰紅色哈希值拼接計算，進而算出再上一層的綠色哈希值，直至計算出整棵 Merkle 樹的根哈希值。

最后，輕節點將計算得到的根哈希值與自身保存的 block header 里的根哈希值進行比較，以此來判斷黃色交易是否存在于該 Merkle 樹中，即是否存在于對應的區塊里。如果兩者一致，則表明該交易在對應的區塊中。

區塊頭和區塊體與默克爾樹的關系

結構組成：在比特幣的每個區塊中，分為區塊頭（block header）和區塊體（block body）兩部分。
默克爾樹根哈希值存儲位置：默克爾樹的根哈希值存放在區塊頭中。這一設計至關重要，因為區塊頭包含的是與整個區塊相關的關鍵元數據，根哈希值作為默克爾樹的關鍵標識，放在此處可用于快速驗證整個區塊內交易數據的完整性。而區塊頭并不包含交易的具體內容，這使得其數據量相對較小，便于節點存儲和傳輸。
區塊體的交易列表：區塊體則存放著該區塊內的交易列表。這些交易作為默克爾樹的葉節點數據，通過層層計算哈希值構建出完整的默克爾樹結構。每個交易在區塊體中都有其對應的記錄，是區塊鏈交易信息的具體承載部分。

默克爾證明詳解

證明的作用：默克爾證明（Merkle Proof）主要用于在比特幣網絡中，讓輕節點能夠高效驗證某個交易是否存在于特定區塊中。由于輕節點只保存區塊頭，缺乏完整的交易列表信息，默克爾證明提供了一種可靠的驗證方式。
證明過程
- 請求與響應：當輕節點想要驗證某個交易時，會向全節點發出請求。全節點收到請求后，會將從該交易所在葉節點到根節點路徑上的哈希值發送給輕節點。
- 本地計算驗證：輕節點收到這些哈希值后，在本地進行計算。首先計算該交易本身的哈希值，然后將其與全節點提供的相鄰哈希值依次拼接并計算新的哈希值，按照默克爾樹的構建規則層層向上計算，直至得到根哈希值。最后，將計算出的根哈希值與自己保存的區塊頭中的根哈希值進行比較。
- 驗證原理：如果兩個根哈希值一致，根據默克爾樹的特性，即樹中任何一個部位的修改都會導致根哈希值變化，就可以證明該交易確實存在于這個區塊中。因為如果交易不存在或被篡改，計算出的根哈希值必然會與區塊頭中的根哈希值不同。
安全性討論：在驗證過程中，雖然輕節點只能驗證交易所在分支的哈希值，但篡改交易數據并使驗證通過的難度極大。因為即使修改了交易內容，想要通過調整旁邊不用驗證的哈希值來保持整個節點的哈希值不變，這在實際中是不可行的，屬于人為制造哈希碰撞，而哈希函數的抗碰撞性保證了這種操作幾乎無法實現。
復雜度分析：從復雜度角度來看，若底層有 n 個交易，默克爾證明的時間和空間復雜度都是對數級別的。這意味著隨著交易數量的增加，驗證所需的時間和空間增長速度較慢，是一種高效的驗證方式。對于證明交易不存在，如果不對葉節點排序，需要驗證整個樹，復雜度為線性；若對葉節點按交易哈希值排序，可通過提供相鄰交易到根節點的路徑證明，復雜度為對數級，但比特幣中由于沒有證明交易不存在的硬性需求，默克爾樹不要求排序。

比特幣中的兩種基本結構 —— 區塊鏈和默克爾樹，都是用哈希指針構造。比特幣并不要求默克爾樹的葉子節點是有序的，因為比特幣中沒有證明交易不存在的需求。同時指出，只要數據結構無環，都可用哈希指針代替普通指針，有環結構會出現循環依賴問題。