> 內容整理自 北京大學肖臻老師《區塊鏈技術與應用》公開課 ## 雜湊指標(hash pointers) 普通指標儲存的是某個結構體在記憶體中的地址。 雜湊指標不僅儲存地址，還儲存hash值 h( )。不僅能找到位置，還能檢測出內容是否被篡改。 比特幣最基本的資料結構---區塊鏈，就是一個個區塊組成的連結串列。 和普通區塊的區別：**雜湊指標代替普通指標。block chain is a linked list using hash pointers.**  透過這樣的資料結構可以實現tamper-evident log，如果修改某個區塊的內容，則後面區塊的h（ ）對不上，包括系統保留的h（ ）都需要修改。我們只需要記住最後一個h（ ），就會檢測出對區塊鏈的任何修改。 普通連結串列可以改變其中一個元素，對連結串列中其他元素是沒有影響的。而區塊鏈牽一髮而動全身。 有這個性質，比特幣中有些節點，就沒必要儲存整個區塊鏈的內容，可以只儲存最近幾千個區塊。如果用到其他區塊，可以問系統中其他節點要這個區塊。 有些節點可能有惡意，給的區塊不一定正確，可以透過雜湊指標的性質，算出該區塊的雜湊值，和儲存的雜湊值對比即可知道是否正確。 ## 默克爾樹(merkle tree) 與binary tree區別：**雜湊指標代替普通指標**。  好處是隻要記住root hash,就能檢測出對樹中任何位置的修改。因為只要一個資料塊修改，根hash值也會修改。 比特幣中，各區塊之間用雜湊指標連線在一起，每個區塊所包含的交易組織成merkle tree.每個資料塊實際是一個交易。 每個資料塊分為塊頭（block header）和塊身（block body）兩部分。header裡儲存root hash的值，區塊所包含的所有交易組成的merkle tree的root hash存在header中，但是header中沒有交易的具體內容，只有root hash。body中有具體的交易列表。 merkle tree作用：提供merkle proof。 比特幣中的節點分為兩類：全節點和輕節點。其中全節點儲存整個區塊的內容，輕節點只儲存header。向輕節點證明某交易寫在區塊鏈中，就用到proof（從交易到root hash的路徑）。  如圖，最上面一行是小型區塊鏈，最下面一行是交易。展現其中一個區塊的merkle tree。假設某個輕節點想要知道黃色交易是不是包含在merkle tree裡面，輕節點沒有儲存交易列表，也沒有merkle tree的具體內容，只有root hash，儲存在header裡。輕節點向某個全節點發出請求，請求一個能夠證明黃色交易被包含在merkle tree中的proof。全節點收到收到請求後，把圖中紅色的雜湊值發給輕節點。有了這些雜湊值，輕節點在本地可以依次計算出圖中標為綠色的雜湊值，最後可以算出整棵樹的root hash值。輕節點把算出的雜湊值和block header中的雜湊值比較，就知道黃色交易是不是包含在merkle tree中。 proof of membership /proof of inclusion o(log(n)) proof of non-membership o(n) 只要無環，都可以用雜湊指標代替普通指標。有環的話，會產生迴圈依賴 ———————————————— 版權宣告：本文為csdn博主「啥也不是的菜雞」的原創文章，遵循 cc 4.0 by-sa 版權協議，轉載請附上原文出處連結及本宣告。 原文連結：https://blog.csdn.net/a972669015/article/details/104496465