Bitcoin Block 如何儲存 Merkle Tree？

中本聰在Bitcoin P2P Network的論文提到，Merkle Tree在SPV Client應用。我們知道，SPV Client不儲存所有的Transaction。當它要確認某個Transaction是否在Block裡，就去問Peer，Peer回傳Merkle Path，給SPV Client驗證就行了。

本篇提出一些問題給大家深入思考：

1. Merkle Tree存在何處？
2. 除了Merkle Tree，還有什麼別的方法，可以用在SPV Client上？

問題一：Maerkle Tree存在何處？

我們知道，Merkle Tree是一種Binary Hash Tree。它的用途和原理這裡就不多說了，不熟的，請大家自己上網找。為了本文講解方便，列出相關名詞。

Merkle Tree裡的Node分為兩類，Leaf Node與Non-Leaf Node，Non-Leaf Node裡面，還有一個惟一的Node叫Root Node，用來代表整個Merkle Tree。

Merkle Tree

• Leaf Node
• Non-Leaf Node
• Root Node

簡單來說，每一個Transaction的Hash值存在Leaf Node，兩兩Leaf Node的Hash值存放在上一層的Node，直到Root Node，其值，就是用來代表Block所包含的所有Transaction。

那麼，Merkle Tree存在那裡？我一直以為是在Block，後來發現，其實Block只存Root Node，連Leaf Node都不存。除了Root Node之外，其它Node都是依照需要，當場計算出來的。我把Block和Transaction的關係，畫成下面這張圖：

從圖中，我們可以很清楚的知道，Block和Transaction都不存Merkle Tree，連Leaf Node都無，只有存在Block Header的Merkle Root，是用來驗證它所包含的Transactions完整性的最後一關。

Full Peer會儲存完整的Block：Block Size + Block Header + Transaction Counter + Transactions

SPV (Simplified Payment Verification) Client只存精簡的Block：Block Size + Block Header

Full Peer會儲存完整的Transaction，但也沒有Merkle Tree，甚至連Transaction Hash也沒有。

Transaction Input的Transaction Hash指的是關連到上一筆的Transaction，而非這一筆。

由此可知道，整個Blockchain、Block、與Transaction的資料結構，在設計上，是以儲存空間最小為考量，而非查詢方便為考量。這是因為Blockchain是大家共用的帳本，愈小，愈利於傳輸。

不管是Full Peer還是SPV Client，Transaction有兩項要檢查：

1. Transaction存在性檢查 - 檢查Transaction是否真的存在Block裡
2. Transaction沒有被重覆花費 - 檢查Transaction的Input不是重覆花費

Full Peer和SPV Client對這兩項的檢查方式會有所不同，我將會寫另一篇文章探討。本文拿，SPV Client對Transaction做存在性檢查，做為一個例子，解釋Merkle Tree在這檢查的過程中，起了什麼樣的做用。

檢查Transaction是否真的在某個Block裡？我猜想的步驟如下：

1. SPV Client將這個問題包裝成 Q = (Transaction, Block Header) 
2. SPV Client將問題Q傳給Full Peer
3. Full Peer拆解Q，若發現Transaction屬於Block，則建立Merkle Path
4. Full Peer將Merkle Path傳給SPV Client
5. 若SPV Client拿到Merkle Path，就表示Full Peer回答了Transaction是在Block裡。
6. SPV Client也會對Merkle Path驗證Transaction是否真的存在Block，做二次驗證。

這裡有一個問題：為何不讓Full Peer直接給答案就好了？還要丟一個Merkle Path給SPV Client，讓它做二次驗證？

這是因為，SPV Client無法確認Full Peer是否可信的？Bitcoin世界裡，Blockchain是惟一可信的，當然裡面的Block、Merkle Root、Transaction都是可信的。若待驗證的Transaction透過Merkle Path，可以接到可信的Merkle Root，那麼就可以驗證Transaction的存在性。

這種驗證Transaction存在性的方法，叫做Merkle Path Proof。再次強調，此法無法驗證Transaction的合法性，因為無法證明Transaction的Input不是重覆花費。

若Full Peer是惡意的，分析一下欺騙SPV Client的可能性如下：

Transaction不屬於Block1：
Full Peer可以騙SPV Client說：Transaction在Block1裡嗎？不行，因為很難做出一個假的Merkle Path，因為Merkle Root是一個不斷SHA256的值，要造假很困難。(題外話，若是SHA1就很容易造假了，因為Google最近發表，在可接受的時間內，產生相同的SHA1出來)

Transaction屬於Block1：
Full Peer可以騙SPV Client說：Transaction不在Block1嗎？可以。

以後再探討Bitcoin Network的安全問題。

問題二：除了Merkle Tree，還有什麼別的方法，可以用在SPV Client上？

為了建立Merkle Path，Full Peer要先從計算所有Leaf Node開始，再往上算出Non-Leaf Node，直到Root Node。為何不用較簡單的List資料結構？Hash所有Leaf Node，放到第1個Node？

List

• Root Node
• Leaf Node

用List，的確可以減輕Server的運算量，因為不用計算Node。但從Full Peer傳給SPV Client的資料量會變很多。原來傳給SPV Client的只要Merkle Path，只要Log(2, N)，現在要N。想像1個Block有1024筆Transaction，其資料量就是 1024 x 36 (SHA256 size) = 36K bytes。如果傳的是Merkle Path，其資料量是 Log (2, 1024) x 36 = 360 bytes。

由此可見，Merkle Tree雖然會增加Full Peer計算Node的負擔，但不會很多。計算Leaf Node運算量會比較大，因為它是Hash兩個32 bytes的Leaf Node。而傳輸的資料會少很多。

再來看本文最初提的兩個問題：

1. Merkle Tree存在何處？
2. 除了Merkle Tree，還有什麼別的方法，可以用在SPV Client上。

結論：

• Blockchain不存放Merkle Tree。
• 但在實作上，Full Peer可以建立一個方便查詢或建立Merkle Tree的Index。建Index的方法就有很多了。
• SPV Client採用Merkle Tree，這是運算量和資料傳輸量之間的折衷方案。

-Count