談雜湊樹（merkle tree）之前，簡單複習雜湊函數（hash functions）的雜湊碰撞（collision）性質。密碼學中，發生「碰撞」的意思是，兩隻不同顏色的牛 input，通過雜湊函數搗碎機器磨碎後，出來居然是一樣顏色的牛肉排 output。意思是，兩個不同的 input，經過雜湊函數後，竟得到相同的 output hash 值，這是雜湊碰撞。詳細內容可參考維基百科：(https://en.wikipedia.org/wiki/Collision_resistance)、(https://en.wikipedia.org/wiki/Cryptographic_hash_function)
想看更多牛、搗碎機與牛肉排表演，可參考這部談 hash function 教學用途的動畫影片：(https://youtu.be/8E6IanXSRxY?si=MXhrjsNMSS8LVnk7)
假想情境：一個月前，你上傳了四個 1 MB 的歌曲音樂檔案（叫 A 檔案）到某個你不信任的雲端空間，但你有留下這四個音檔的雜湊樹根（merkle root）。過了一個月，你準備下載音檔 4 號（叫 B 檔案），但你想確定，雲端給你的它宣稱的音檔 4 號，是不是就是你一個月前上傳的檔案。你想進一步驗證、檢查，檔案有沒有偷偷加料，有沒有被改過、編輯過，是否真的就是一個月前你上傳的檔案。
這時，雲端會給你一個雜湊樹證明（merkle proof），一個 32 bytes 的 hash value 和一個 32 bytes 的 hash value。更精確的說（比照維基百科雜湊樹的圖(https://en.wikipedia.org/wiki/Merkle_tree)），雲端會給你雜湊樹證明，是一個 Hash 0 和一個 Hash 1-0。這個時候，你會怎麼驗證、檢查你的檔案資料的完整性（data integrity）？確保資料沒有被奇怪的人篡改？
你會把下載的 B 檔案 hash 起來，得到 Hash 1-1。接著，再與 Hash 1-0 進行 hash，會得到 Hash 1。接著 Hash 1 與 Hash 0 再進行一次 hash，會得到雜湊樹根 Top Hash，這個是自己算出來的雜湊樹根。
算出來的雜湊樹根應該要和 Top Hash （你存在電腦裡的一個月前的雜湊樹根）一樣。這個 32 bytes 必須要長得一模一樣，就像驗指紋，指紋必須長得一樣。雜湊樹根一樣的話是 true，表示 valid 驗證通過。不一樣的話是 false，表示 invalid 驗證未通過或驗證失效，可能檔案曾被改動過。
雜湊樹的樹狀結構，樹形的結構，有點類似平時逛花店會看到的那種「倒掛著的乾燥花束」。店家通常會把花倒掛、吊起來，放在通風的地方。雜湊樹的樹狀結構，特別之處在於樹的根在上面，葉子在底下，稱「樹狀」，或稱「樹形」結構。今天想了解的是，為什麼雜湊樹必須是樹狀的結構？
試想今天如果不是以樹狀結構來做雜湊函數，會發生什麼事情？例如，另外發想一個單純使用「串接」（動詞 concatenate，名詞 concatenation）的作法，以串接的方式，把四個資料串接在一起。例如，L1, L2, L3, L4 四個資料，不假思索就串接在一起，接著再通過雜湊函數，產出 32 byte 的 hash value output。如此串接的方式又與樹狀結構，有什麼不同？
如果是串接作法，假設我今天只想驗證一個 L4 檔案他的資料完整性，我只能四個檔案 L1, L2, L3, L4 全下載下來才能夠檢查當初存在電腦的 hash value。但如果是樹狀的話，我就不用全部四個檔案都下載，只要下載 L4 檔案就可以檢查 L4 的資料完整性。
為什麼樹狀結構可以行得通？假設有一個冒牌的 L4，他可能是損壞的檔案。比如說，缺了幾個 bit 的導致音檔的聲音播放不流暢，或是加入奇怪的病毒。假設不信任的雲端空間的 server 要騙你收下一個竄改過的 L4'，但你很聰明會執行雜湊樹證明的檢查，他不可能騙得過你，因為 L4' 會到最後算出來的新的雜湊樹根 Top Hash'，一定會和你一個月前電腦存的雜湊樹根（Top Hash）不同。這是沒有騙過的正常的雜湊樹證明的檢查，是 invalid 驗證失效。
重新回想一次，同樣你執行雜湊樹證明的檢查，什麼樣的情形才會通過雜湊樹證明的驗證？不信任的雲端的 server 唯一能夠騙過你的條件是，他找到一個 Hash 0' 和 Hash 1' 這兩個 hash 起來，會得到你一個月前存在電腦裡的那一個雜湊樹根（Top Hash）。相當於攻擊者找到一個雜湊樹根的「碰撞」。
區塊鏈技術中幾乎所有東西都雜湊函數。陌生節點可能充滿了壞人，他給的資料都需要檢查和驗證。區塊鏈的交易（transactions）需要 hash，區塊（block）需要 hash，以太坊世界狀態（world state）需要 hash。以太坊世界狀態用的雜湊樹是「modified Merkle-Patricia Trie」，詳細內容可參考以太坊官方網站的資料：(https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/)。
雜湊函數對於區塊鏈技術是不可或缺的存在。區塊鏈的運作，其中非常多的步驟，絕大多數都是繞著資料完整性在打轉，也就是忙著驗證和檢查資料到底有沒有被篡改這件事情。包括智慧合約的程式碼有沒有被改過，包括餘額有沒有被改掉等等。如果有去參加一些以太坊技術相關的社群活動或研討會會議，也會觀察到，講者們經常討論到雜湊函數相關的議題。不難了解到，雜湊函數在區塊鏈技術扮演關鍵角色。
最後講一個 Merkle tree 的笑話。我在研究的時候問 ChatGPT 他有沒有相關的笑話，然後他就展現了他的幽默感。
Why did the Merkle tree bring a ladder to the blockchain?
Because it wanted to hash things out at every level!
iThome鐵人賽
看影片追技術