spv.md

※図は Mastering Bitcoin (PDF) からの引用

SPV (Simplified Payment Verification) を支える技術

Bitcoin クライアントの種類

UTXO (Unspent Transaction Output)

• ビットコインウォレットの残高は、ビットコインネットワークから自分のビットコインアドレスが output になっているトランザクションの情報 UTXO (Unspent Transaction Output) を集めて金額を合計したもの
• ビットコインで支払うぞってなったら、集めて使おうとしてる UTXO が本当にまだ使われてないかをチェックする必要がある
• UTXO が使われていないかどうかの検証は、そのトランザクションより下の全てのブロックに含まれる全てのトランザクションをチェックする
• 全部集めるにはブロックチェーン全部をダウンロードして探索しないといけない？

SPV クライアント

概要

• フルブロックチェーンを保持しないウォレットが作れる
• SPV クライアントがやりたいこと
  • 自分に関係のあるトランザクションだけをダウンロードしたい → Bloom Filter
  • トランザクションが二重使用された不正なものでないかを知りたい → Merkle tree

Bloom Filter

• 自分に関係のあるトランザクションだけを集めるための仕組み
• 自分に関係のあるトランザクションをリクエストするのに自分のアドレスを送ってしまうのはプライバシーの問題がある
• Bloom Filter
  • 自分に関係のないトランザクションも含まれるけど、自分に関係のあるトランザクションは漏らさない
  • 誤検知はあるけど検知漏れは無い
  • false positive はあるけど false negative は無い

Merkle tree / Merkle path

• ブロックに含まれているということは不正なトランザクションではないことが合意されているということなので、あるトランザクションがいずれかのブロックに含まれていることが分かれば良い
• SPV ノードは全てのトランザクション、完全なブロックチェーンをダウンロードしない
• あるトランザクションがブロックに含まれているかどうかを知りたいが自分ではわからない
• フルノードにトランザクションを渡して Merkle Path の証明を送ってもらうことで確実にブロックに含まれていることを知る
• SPV ノードはトランザクションがブロックに含まれているかどうかの確認にブロックヘッダと Merkle path という 1KB 以下のデータを受け取るだけでいい

SPV ウォレットが自分に関係のあるトランザクションだけを集めてきて検証して残高に加えるまで

1. SPV ウォレットはフルノードに Bloom Filter を送る
2. フルノードは Bloom Filter に合致するトランザクションのみを集め、Merkleblock message (ブロックヘッダと Merkle path) と共に SPV ウォレットに返してあげる
3. SPV ウォレットはトランザクションハッシュ、ブロックヘッダの Merkleroot、Merkle path からそのトランザクションがブロックに含まれているかどうかを検証
4. そのトランザクションがブロックに含まれて以降何ブロックできたか(何承認されたか)がわかって、よくあるクライアントだと6承認された時点でその UTXO を使用可能とする

※厳密にはちょっと違った。正しくは → https://gist.github.com/morishin/95696b41b1c81e218f4e74ae54bfb7b4#gistcomment-2302556

参考文献

• Mastering Bitcoin P153 PDF
• Bitcoin Wiki - Protocol Rules
  • トランザクションの検証フロー
  • ブロックの検証フロー

https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki#Motivation

実際に Bloom Filter を送って merkleblock message を受け取るやりとり

Send: version 86
Recv: version 102
Send: verack 0
Recv: verack 0
Send: filterload 74
Send: getblocks 69
Recv: inv 253
Send: getdata 181
Recv: merkleblock 344
Merkleblock {version = 536870912, prevBlock = Vector [189,249,210,51,5,217,94,60,158,35,143,87,0,121,199,122,78,10,118,148,66,66,83,165,188,100,7,0,0,0,0,0], merkleRoot = Vector [94,54,105,9,137,93,232,49,36,193,215,23,63,5,196,229,15,103,146,60,103,84,154,141,234,251,91,169,1,242,152,1], timestamp = 1513782853, b$ts = 436585798, nonce = 1906871403, totalTransactions = 14, nHashes = VarInt 8, hashes = ["e}D!\149K\153#\150\CANk\198\245\179Q\203\164\214\150+\v\ESCi\189\&${X\217\215\&2\136\222","\FS\225\ETB ='\242X\187>a\220\242\STX\ESCB\163h\157D\155U\145\238\224\228\237'@V\ACKG","\171\DLE\234\NUL\213\210,0]\180f%\247\219\251$199\SIl_\DC1zSc\165\186p\r5wu\137\224","\214K\232\138\SUB#\134\177\DC3\SI\131\152\247G\243\225AL\226\137\156K\155\ACK\164\221\209V\146\157P\ESC","\198\163\EM$198\&6t\220v\SOH\242\132\145\137\USGI\216Bx\146\ENQ\r\197d\151\248\178\146\151\165\170\181","\169\DEL$\169RC\231\211\ACK\229\132\SO\222\206\131\210S\158\233\$31\225\210#\DC1!\\\EM}\206\206_R","\254`\214\"\182\225c\247g=\DLE\219p-?\147\USS!\179\ETB\200m\"\ETX\231\142W\179~\174\140","\215>:?\197\173\223\206\247|\222$\139\180\152c2\ENQ\136)\253\214\155Z\133JE\f\161\183\&6?"], nFlags = VarInt 2, flags = [239,14]}
Recv: tx 140
Recv: tx 140
Recv: tx 204

L1 ~ L4 ハンドシェイク
L5 filterload でブルームフィルタをセット
L6 getblocks でブロックを要求 → "フィルタに合致したトランザクションが含まれるブロック(複数)のブロックヘッダ“ が返ってくる
L7 ~ L8 inv の中の inventory type が MSG_BLOCK のものが返ってきたブロックヘッダ(複数)で、それらに対して MSG_FILTERED_BLOCK というメッセージで getdata する
L9 merkleblock ゲット

https://bitcoin.org/en/developer-reference#merkleblock

merkleblock message から Merkle root を計算する流れ

Flag の意味

Flag	TXID Node	Non-TXID Node
0	Use the next hash as this node’s TXID, but this transaction didn’t match the filter.	Use the next hash as this node’s hash. Don’t process any descendant nodes.
1	Use the next hash as this node’s TXID, and mark this transaction as matching the filter.	The hash needs to be computed. Process the left child node to get its hash; process the right child node to get its hash; then concatenate the two hashes as 64 raw bytes and hash them to get this node’s hash.