2017年3月15日 星期三

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

1 則留言: