Sparse Merkle Tree 的優點及用途
--
本文將介紹 Sparse Merkle Tree（以下簡稱 SMT）、其和一般習慣的 Merkle Tree 的不同，以及它的優點及用途。
在了解 SMT 之前，你會需要知道密碼學雜湊函式（Cryptographic Hash Function）的特質
如果你已經知道 Merkle Tree 和 Merkle Proof，可以跳過接下來這一段，直接進到下一段 Sparse Merkle Tree。
熟悉的 Merkle Tree
這邊我們以區塊鏈的區塊裡的 Transaction Merkle Tree 為例，簡短複習一下平常熟悉的 Merkle Tree。
Merkle Tree：
Transaction Merkle Tree（葉節點是 H(Tx)，交易內容的雜湊值）：
每個區塊所包含的交易的交易內容不會全部直接塞在 Block Header 裡，而是將這些交易做雜湊，然後再將這些雜湊值組成 (Transaction) Merkle Tree，最後只會有一個值 (Transaction) Merkle Root 存在 Block Header 裡。
為什麼要這麼做？因為並不需要所有人都知道這個區塊打包了哪些交易。像是輕節點，它不像全節點一樣需要驗證過每個區塊的每一個交易以確保自己紀錄的鏈是一個合法的鏈。
輕節點用一些信任換取一些便利性：它只驗證 Block Header 的合法性，像是 PoW、Previous Header Hash，並且相信全節點給它的 (Transaction) Merkle Root 所包含的交易存在且合法。
Membership Proof
那這樣做對它有什麼幫助呢？輕節點身為一般使用者和區塊鏈之間的橋樑，它只在意這個使用者在意的交易，它只要確保自己（高機率）是在最長鏈上，且確保它在意的交易已被打包在某個區塊裡。而這就帶到我們要介紹的 Merkle Tree 的其中一個最大的優點：Membership Proof，證明某個值存在在某個 Merkle Root 對應的 Merkle Tree 裡。
而且這個證明是精簡 (Compact) 的！想像一下，如果你有上面圖中四筆交易，你可以選擇把這四筆交易接起來丟進雜湊函式裡得到一個雜湊值，並放在 Block Header 裡，簡單粗暴：
H(Tx_A || Tx_B || Tx_C || Tx_D)
當你要向我證明 Tx_B 被打包在這個區塊裡時，你就給我 Tx_A、Tx_C 和 Tx_D，然後我再用同樣方式把它們接起來丟進雜湊函式，再把結果和 Block Header 裡的值做比對。
但當今天交易數量有數百筆、數千筆時，你為了要向我證明其中一個交易存在，你要給我其他全部的交易我才能驗證，這樣一點也不精簡、不有效！
Compact Membership Proof
那如果今天換成 Merkle Tree，要怎麼證明 Tx_A 存在在 Block 2 的 Transaction Merkle Tree 裡？
橘色是你我已知的資訊：Merkle Root 及 Tx_A。接下來你只要提供給我綠色的部分就行了，我拿著橘色和綠色的值，照著原本組出 Merkle Tree 的方式就可以自己算出 Merkle Root 了。綠色的部分就叫做 Merkle Proof。
而 Merkle Proof 的大小不會隨葉節點數量線性增長，而是對數增長。假設葉節點數量有 100 萬個時，Merkle Proof 的數量只會增長到 20 個。
Recap:
Merkle Tree -> Compact Membership Proof！
State Tree(Trie)
在進入 SMT 前，讓我再延伸一下介紹 (Ethereum) State Tree，因為這會和 SMT 的優點有關。
可以看到 Ethereum 的 Block Header 除了 Transaction 的 Merkle Root 外，還有一個 State Root，而圖中 State Tree 的葉節點是一個 Ethereum Account 的 State，裡面包含這個 Account 相關的資訊。
證明某個 Account 在某個區塊的 State 長怎樣（例如 Balance 多少、Nonce 多少）的方式也和 Transaction 一樣。
Sparse Merkle Tree
SMT 和一般 Merkle Tree 第一個不一樣的地方就在於，它的大小預先就固定了。
從前面的 Transaction Merkle Tree 範例中可以看到，當一個區塊收入四筆交易時，它的 Transaction Merkle Tree 就由這四筆交易組成，即它的葉節點只會有四個；如果一個區塊收入一百筆交易，那它的 Transaction Merkle Tree 就由這一百筆交易組成，這棵樹會更大棵。
但把一個 Merkle Tree 的大小預先就設好有什麼用處？Transaction Merkle Tree 由每個區塊收入的交易多寡來決定該區塊的樹長多大，這是動態、不固定的。但如果今天我們要用來存預先就知道有多少數量且數量不會改變的東西的話，用一個固定大小的樹來存就非常合理了。
那有什麼東西是預先知道有多少數量且數量不會改變的呢？像是 Ethereum 的 Account 數量：Ethereum 地址長度 20 bytes，表示有 2¹⁶⁰ 個不同的地址，即 2¹⁶⁰ 個 Account。Ethereum 的 state 就可以用 SMT 來存。
固定大小、固定的值
Transaction Merkle Root 因為知道 Transaction 有哪些，所以可以知道葉節點要填什麼值。但 SMT 有這麼多葉節點，不可能 Ethereum 的所有 Account 都有 Balance 吧？這些不存在的 Account 要填什麼值？答案是預設值。
什麼預設值？可以是 0，可以是 1，或任意值，只要你的 Protocol 有訂好一個預設值就行了。
你可以看到，基本上這棵樹的每一層的預設值都會是一樣的：
H(0)、H(H(0) + H(0))、…
所以任何人只要知道樹高及預設值，都可以自己算出每一層的預設值。
所以事實上你的節點在保存 SMT 時，是不需要把空白（是預設值的）節點存在資料庫裡的！你只需要儲存非空白的節點：
而這就是為什麼它會被稱作 Sparse 的原因了。
Proof 的大小
你可能會想，Transaction Merkle Tree 裡，如果交易放得少，那棵 Merkle Tree 的 Proof 大小就會小。那今天 Ethereum State 這棵 SMT 裡如果 Account 很少，結果每個 Merkle Proof 都是一樣、固定的，這樣不是很浪費嗎？
是沒錯，但這其實是可以優化的：大部分節點都會是空白節點，也就是預設值，這時候你給我的 Merkle Proof 裡除了非空白節點，其他是空白節點的，你只要用一個 bit 告訴我在這一層要用預設值就好，這樣我就能自己補出完整的 Merkle Proof 了。
雖然最後拼出來的 Merkle Proof 還是固定大小的，但我們之間傳遞的資料量卻可以縮小很多，避免網路頻寬成為一個效能瓶頸。
Non-membership Proof
接下來就要直接進入 SMT 的最大優點之一：Non-membership Proof。直覺上聽起來會有點奇怪，要怎麼證明一個東西不存在某個群體裡？或是更直接的，為什麼？
要怎麼證明一個東西不存在某個群體裡？(How)
首先要先定義出這個群體，才能證明一個東西不存在這個群體。我們以 Ethereum State 為例，這個群體就是 Ethereum State 定義的 2¹⁶⁰ 個 Account。目前 Ethereum 累積的地址數才只有 1.9 億個（約是 2²⁸），所以絕大多數 Ethereum State Tree 裡的葉節點都是預設值（即空的 Account：Balance、Nonce 等等都是 0 的 Account）。
為什麼？(Why)
如果我要向你證明某個地址還不存在、還沒有任何活動痕跡，就是要向你證明那個 Account 在 Ethereum State 裡的值是預設值！這就是我們利用 SMT 來證明一個東西不存在某個群體的方式及原因。
（正確的定義可能是要說：證明某個地址不存在於活躍的 Ethereum 地址群體中，但你知道我的意思。下面還有另一個例子會更合理。）
如果我要向你證明地址 3（假設這個 State 總共只有 16 個地址）不存在、是空的，我就給你圖中綠色的部分，你就能驗證地址 3 的值真的是預設值。
Replay Protection
最後要講到的是 SMT 目前的一個很大的用途，也是因為我常常要解釋這個用途，解釋了太多遍，乾脆把它寫下來介紹完整：Replay Protection。
如果你今天設計了一個應用或系統，你要怎麼防止交易被 replay 而導致使用者或是系統受害？
- 如果交易是一筆 transfer，則必須要防止同樣一筆 transfer 能再被 replay 一次，導致使用者賠錢
- 如果交易是投下一張選票或是按一個讚，則必須要防止同樣一張選票或點讚能再被 replay，導致整個系統被操弄
其中一個答案是：證明交易不存在（交易存在則表示這是一個 replay）
透過 SMT Non-membership Proof，就可以用驗證 Merkle Proof 這個有效率的方式來驗證一筆交易是否存在過，避免交易被 replay。
延伸閱讀：可以參考這一篇在介紹不同隱私應用怎麼防止 replay 的文章：
下面這篇文章從實作的角度出發介紹 SMT，有興趣了解 SMT 實作的可以參考：
附註
內文在 SMT 的段落裡有提到 Ethereum state 可以用 SMT 來儲存。Ethereum state 目前是用 Merkle Patricia Trie (MPT) 的結構儲存，雖然實際上運作方式及優缺點不一樣，但我個人覺得抽象來說 Ethereum state 的 MPT 也是屬於一種 SMT 的：固定高度、可以證明 Non-membership、不需存中間的空白節點 （Sparse Tree）。
Special thanks to Chih-Cheng Liang for reviewing and improving this post
