2017年3月11日 星期六

SPV Node如何用Bloom Filter詢問自己有多少錢?

Wallet (SPV Node)如何知道自己有多少錢?在上一篇文章,如何知道Bitcoin Wallet有多少錢,列出三種方法。

方法一:下載完整帳本(Blockchain)後自己從裡面去找
方法二:向Peer公開Wallet的所有訊息,Peer就回傳屬於該Wallet的UTXO
方法三:向Peer公開Wallet的部份訊息,Peer回傳可能屬於該Wallet的UTXO

三種方法,各有優缺點。本篇介紹第三種,參考自,BIP37 - Connection Bloom Filtering。想深入了解Bloom Filter在Bitcoin Protocol的運作原理,建議多花一些時間閱讀。看得懂的,本篇文章就不用再看下去了。若看不太懂,希望本文對大家會有一些幫助,當然,最重要的一點是,鼓勵大家對照原來的BIP37,質疑本文的正確性,這樣做,有助於提升大家的思考能力。

用下圖說明,Wallet如何用Bloom Filter,去向Peer問,自己擁有多少錢。這裡,我們的前提條件是,Wallet被重啟後,只剩下Private Key,其它什麼都沒有。不用擔心,透過下面步驟,可以把錢找回來。


Wallet向Peer詢問,自己應該有多少錢,步驟如下:

  1. Wallet從Private Key推衍Public Key,再來是一組Address (a1, a2, a3)。最後建立Bloom Filter。可以想像它是一個過瀘器,用來過瀘大部份不屬於Wallet的Transaction。
  2. Wallet對Peer發送filterload message,將Bloom Filter傳給Peer。
  3. Wallet發送getblocks message,要求Peer傳回Block。若Wallet沒有發filterload,那麼Peer會準備一股腦的Block。但因為現在Peer有了Bloom Filter,所以它會過瀘大部份不相干的Transaction。
  4. 這時Peer開始從Blockchain中,用Bloom Filter找出可能屬於Wallet的Transaction,及其所屬的Block。假設第一個找到的是Block1,底下掛了一個tx1,其output指向a1,表示該transaction屬於Wallet。
  5. 為了要確保tx1的output沒有被花費到,Peer必須檢查是否有其它的transaction的input花費了a1。假設Peer發現了Block1底下掛了一個tx2,其input指向a1,就表示tx2花費了tx1的output。
  6. 若在Step 5發現Transaction有被花費,則Peer會依據Transaction的格式,及當初從filterload設定的Flag,決定要不要更新Bloom Filter。這樣會造成Bloom Filter的孔會愈來愈大,導致判定Transaction屬於Wallet的準確率也會變大。其中的細節,留待下一篇文章說明吧!
  7. 當Peer找到所有可能的Transaction後,就會發一個inv message,給Wallet。inv裡面會有:待選Transaction所屬Block的頭、Merkle Path、以及Transaction本身。
  8. 最後,Wallet收到inv message帶來的東西後。就依照中本聰論文理所提的兩種檢查方式:Merkle Path Proof和Proof of Work(這一點我以後再解釋),檢查那些Transaction是屬於Wallet,並且是尚未被花費的Transaction,然後建立UTXO Pool,暫時存放尚未被花費的屬於該Wallet的Transaction。將這些Transaction的Output加總,就是該Wallet的餘額(Balance)了。
本文遺留幾個問題,近期之內會說明:
  • Peer在什麼情況下,會去更新Bloom Filter?
  • 如何從,中本總Bitcoin P2P Network論文,解釋SPV檢查Transaction的方法?
至於Merkle Tree和Bloom Filter的原理,建議大家自己上網找資料,沒必要我就不多解釋了。

-Count

沒有留言:

張貼留言