小雨走進了便利超商領取網購的貨物，店員問他手機後三碼。店員在貨架上翻找一番後，宣布沒有看到，早先有另外一個人拿走了小雨的貨物 -- 那人有一樣的手機末三碼。店員保證以後會再確認姓名和證件。

小雨心情不是很好。假設手機號碼位數為 0~9 均勻分布，末三碼共有 1000 種組合。 1000 看似很大的數字，但只要少少的人數就會發生撞號。

小雨查了生日攻擊的 網站 ，在 Solve N(D, P) 選項中，輸入 D 為 1000 ，P 為 50%。網站算出 N 為 38 。意思是末三碼 1000 種組合裡面，這家超商有 38 個人來取貨，就有一半機率會發生手機末三碼撞號。人數越多撞號的機率更越大。想像 100 家服務 38 人的超商，其中 50 家會發生撞號。

小雨走著走著遇到了特務 K 。

「我們得談談這個雜湊值，我看到他好幾次了，這串亂碼的意義是什麼呢？」特務 K 問

「可以想像是代表一組資料的代號」小雨試著用簡單的話說「他透過一種密碼學的 雜湊函式（Hash function） 產生」

他們走到了一個安全的地方，翻開筆電。上次使用的 ethers 遊樂場網站 似乎不錯用。

小雨先敲了一個 keccak256 ，這是以太坊協定中處處使用的雜湊函式。

> keccak256("0x01") // ether.js 要求必須要 0x 開頭
"0x5fe7f977e71dba2ea1a68e21057beebb9be2ac30c6410aa38d4f3fbe41dcffd2"

「keccak256 會固定輸出 256 位元，也就是 32 位元組」小雨說。「不管你輸入什麼資料」

特務 K 數了一下，確實有 64 個十六進位位數，確實是 32 位元組

小雨在 0x0100 後面再加上 00

> keccak256("0x0100")
"0x628bf3596747d233f1e6533345700066bf458fa48daedaf04a7be6c392902476"

即使是這麼小的更動，keccak 函式輸出的值看起來完全不一樣了。

「雜湊函式對輸入非常敏感，只要輸入有一點點不一樣，輸出就會大變」小雨說。

資料完整性

「這樣的設計，是什麼意圖呢？」特務 K 問。

「我們想要給資料指派一組很短的代號來代表它」小雨說「然後祈禱不同的資料不要撞號」

「32 位元組看起來比我們的輸入資料長很多，這個短是短在哪呢？」

「我們現在用的範例太短了，上次用的交易原始資料就長些，或想像 2 GB 的輸入資料，32 位元組相較之下超級短」小雨說。

「為什麼要短呢？」

「原因有很多，一種原因是有些演算法計算上非常昂貴，例如你沒辦法直接對 2 GB 的資料做數位簽章」小雨說「但簽署 32 位元組的雜湊值就容易得多」

「然後因為你沒辦法找到會撞號的資料」特務 K 想了一下「所以簽署雜湊值就相當於簽署原來的資料本人」

「對」

「大多數的原因會是資安上說的資料完整性（data integrity）」小雨接著說「如果你要分批下載 2 GB 的資料，你怎麼知道中間有沒有在傳送的過程中被竄改過呢？」

「了解，假設我下載前能取得 2 GB 資料的雜湊值，這樣就能夠在下載後跑雜湊函式驗證」攔截資料這種事特務 K 常做，所以反應很快「最好雜湊值還是資料提供者簽署過的，確定我不是拿到壞人給的雜湊值。」

短、撞號

「那為什麼是 32 位元組呢？」特務 K 問「為什麼不是更短或更長？」

「太短的話就太容易撞號」小雨說「太長又太冗贅不好用，密碼學家會視現在攻擊者的運算能力到哪裡，選擇適當的保守長度作為業界標準」

「想像極端情況，你只用 keccak256 的第一個 1 位元組作為輸出長度」小雨說

「這樣我的輸出剩下 256 種組合，很容易就撞號了」特務 K 想。

「比手機末三碼還慘」小雨評論。

以太坊中的雜湊函式使用

「以太坊中，雜湊函式用在哪些地方呢？」特務 K 問。

「基本上幾乎所有的地方」小雨說「記得以太坊的身體是全節點構成的，所有資料都是在網路中廣播，因此處處都要有資料完整性的設計。」

「所以我只要看到哪裡漏掉雜湊值，我就可以欺騙其他的節點收下不同的資料了」特務 K 想「交易要有交易雜湊值，區塊要有區塊雜湊值，並指涉到前一個區塊的雜湊值，可能還有一些我們現在沒看到的。」

「像是交易或是區塊這種有欄位的資料，必須要用沒有模糊空間的編碼方式，如舊的 RLP 或新的 SSZ 先序列化成位元組」小雨說「然後再取得資料的雜湊值。」

雜湊樹

「又如果是像陣列這種有多種同質性元素的資料結構，像是裝載好幾筆交易的陣列」小雨說「就會使用 雜湊樹（Hash Tree / Merkle Tree） 這樣的資料結構」

「這個雜湊樹長什麼樣子呢？」

image: By Azaghal - Own work, CC0 Link

「他是陣列裡面的每個元素的雜湊值，兩兩再雜湊再一起，形成一輪數量減半的雜湊值，再兩兩雜湊，以此往復，最後會剩下一個稱為 雜湊樹根（Merkle Root） 的雜湊值」小雨說「雜湊樹十分普遍，普遍到在許多新的設計中，如信標鏈區塊，其雜湊值已經不叫 區塊雜湊值（Block Hash） 而叫 區塊根（Block Root） 」

「雜湊樹這麼複雜的設計，有什麼好處呢？」

「雜湊樹可以做 成員證明（Membership proof / Inclusion proof）」小雨說「你想像你有一個 200 筆交易的陣列，但通常你只想證明其中一筆交易（陣列中的成員或元素）屬於那個陣列」

「如果只用純粹的雜湊函式，我應該會把 200 筆交易序列化，用雜湊函式取得值」特務 K 思索「但一旦要證明其中一筆，我得取得其他 199 筆的資料，才能重製最後的雜湊值」

「又或是我只把 200 筆交易各自的交易雜湊值雜湊在一起」特務 K 換條思路「這樣我只要取得其他 199 筆交易的雜湊值即可。要取得 199 * 32 位元組的資料」

「使用雜湊樹的話，這個數量會減少很多，8 個雜湊值，也就是 8 * 32 位元組即可」小雨說「看到二元樹就無腦想到 log2 就是了， log2(200) 接近 8」

電腦科學家喜歡樹，樹根在上方，葉子在下方。樹是一種每個中間節點都會分叉 X 個支幹出去的結構，因此葉子的數量會是 X 的層數次方，或層數會是葉子的 Log_X （以 X 為底數的對數）。當運算是指依賴層數的時候，代表運算量會比葉子的數量小很多。

「陣列越大，資料會省越多」特務 K 現在也略懂這些樹和木頭。

總結

小雨做了一些總結，裡面提到的一些新的樹或範例，日後才會遇到。

• 小小有固定欄位的資料
  • 範例：像一個區塊、一筆交易這類。
  • 一般程式語言類比：想像是 Python 中的 class 。
  • 雜湊策略：序列化然後取得雜湊值。
• 靜態陣列：建構出來就不需要再更動的話
  • 範例：區塊裡的交易。一旦交易的雜湊樹建構出來後就不再更動。
  • 一般程式語言類比：想像是 Python 中的 list ，但不能更動。精確地來說像是 Python 的 FrozenList 套件或 Rust 的 immutable 。
  • 需求：在陣列長度很長之下，要能有效率證明成員。
  • 雜湊策略：用簡單的雜湊樹。
• 動態陣列：需要頻繁更動陣列的成員。
  • 範例：TornadoCash 中的存款者、信標鏈中的存款合約。
  • 一般程式語言類比： Python 中正常的 list 。
  • 需求：除了成員證明外，要能更動成員狀態，或在陣列中新加入成員。
  • 雜湊策略：用 遞增雜湊樹（Incremental Merkle Tree） 或 稀疏雜湊樹（Sparse Merkle Tree）
• 字典或 鍵-值資料
  • 範例：以太坊的全域狀態(World State)、合約帳戶的儲存區（Storage）。
  • 一般程式語言類比： Python 中的字典（Dictionary）。
  • 需求：
    • 節點同步要頻繁的在電腦硬碟中更新
    • 要避免攻擊者特意挖一條特別深的樹分支，造成節點同步難度
    • 希望樹根只因成員本身變動，而非更新順序
    • ... 之類等等
  • 雜湊策略：現在用 MPT 樹（Merkle Patricia Trie） ，但未來有眾多 潛在方案 在激烈討論中

有趣的參考資料

• https://arxiv.org/abs/2504.10944 這是一篇新論文提倡一種新的樹，但文獻整理的部分有提到既有的各種樹的優劣
• https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/ ethereum.org 對 MPT 樹的介紹
• https://blog.ethereum.org/2015/11/15/merkling-in-ethereum 2015 年 Vitalik 在講以太坊雜湊樹的設計。裡面略過了 MPT 樹的具體實作細節，但講了為什麼要設計一個這麼複雜的樹。