1.hash pointer 哈希指針

哈希指針與普通指針不同的是，哈希指針中不僅指向了某個結構體，並且還保存了該結構體的哈希值。

哈希指針不僅指向了結構體，並且還能檢測該結構體是否被篡改。

2. block chain 區塊鏈

區塊鏈就是使用哈希指針代替普通指針的鏈表。

第一個區塊稱為 genesis block 創世紀塊。

最後一個區塊稱為 most recent block 最近塊，最近塊的哈希值存儲在系統內。

tamper-evident log 防篡改日誌

我們只需要保存最近塊的哈希值，就可以校驗整個區塊鏈是否被篡改。

3. merkle tree 默克爾樹

默克爾樹就是使用哈希指針代替普通指針的二叉樹。

默克爾樹的葉子節點是數據塊，存儲實際的數據；非葉子節點保存了其左右子節點的哈希值。

通過保存根節點的哈希值，就可以校驗整個默克爾樹是否被篡改。

比特幣中，默克爾樹存儲於 block body 區塊身，默克爾樹的根哈希值存儲於 block header 區塊頭。默克爾樹的葉子節點（數據塊）中存儲 TX (Transaction) 交易。

merkle proof 默克爾證明

比特幣的使用端有兩種：全節點和輕節點

全節點：保存了整個區塊的內容。

輕節點：僅保存了區塊頭的內容。

輕節點可以使用默克爾證明來校驗某一個 TX 交易的真實性：

1. 輕節點向全節點請求交易所在葉子節點到根節點路徑上另一邊的哈希值。
2. 輕節點根據交易對象提供的 TX 交易計算哈希值。
3. 將計算得到的哈希值與請求得到的另一邊的哈希值結合為非葉子節點，然後對非葉子節點求哈希值。如此迭代，直到計算出一個根哈希值。
4. 將計算得到的根哈希值與區塊頭中保存的根哈希值比較，最終校驗交易是否已經寫到區塊鏈上。

默克爾證明的時間複雜度為 \(O(log(n))\)

sorted merkle tree 排序的默克爾樹

默克樹可以在\(O(log(n))\)的複雜度下證明交易存在於某個區塊，而證明區塊中不包含某個交易，則需要\(O(n)\)的時間複雜度。

對於排序的默克爾樹，則可以實現\(O(log(n))\)複雜度證明區塊中不存在某個交易。

比特幣中沒有用到排序的默克爾樹。

4. 擴展其他的數據結構

無環的數據結構均可以通過讓哈希指針替換普通指針形成新數據結構。

有環的區塊下，哈希指針會產生循環依賴，因此較難找到這樣的一個數據結構。