ビットコインにおけるブルームフィルターとマークルツリーパス

現時点(2018年2月)において2009年から作られたビットコインのブロックの数(=ブロック高)は、
こちら Bitcoinブロックエクスプローラ - ブロックチェーンをみるとわかるように、 508786 です。
最新の４つのブロックを見ると、一つのブロックには、200 ~ 1600 個のトランザクションが含まれていました。

ビットコインフルノードはトランザクション情報全てを持つ必要があるため、現時点で、
500GBほどのディスクを必要としますが*1、フルノードでないビットコインノードである、
ウォレットノード、マイニングノードなどの軽量ノード(SPVノード)では、すべてのトランザクション情報を持つ必要はありません。
しかし、あるアドレスから送信、受信したあるトランザクションがどこのブロックに含まれるかを効率よく知る必要があります。
SPVノードはすべてのトランザクション情報を持つフルノードに対してトランザクションIDを送り、
フルノードは、それをすべてのブロックから検索し、見つかれば、そのトランザクションの情報をSPVノードに送り返します。
この仕組みを使えばSPVノードはすべてのトランザクション情報を持つ必要がありません。

あるトランザクションがどのブロックに含まれるか、高速に検索するには事前にインデックスをつけておけばよいです。
これを実現するための仕組みがマークルツリーパスです。

マークルツリーパス

マークルツリーパスに関してネット上に分かりやすい解説が見つからなかったので、
(マークルツリーの解説はありますが。。)
オライリーのmastering bitcoin の解説か日本語訳した無料版の資料 https://www.bitcoinbook.info/translations-of-mastering-bitcoin/ を参照するのがよさそうです。

C++が分かる方はオリジナルソースを読むのもいいかと思います。
該当ロジック部分だけであれば、量的にはわずかです。
GitHub - bitcoin/bitcoin: Bitcoin Core integration/staging tree

マークルツリーの実装ヘッダはこれだけです。
https://github.com/bitcoin/bitcoin/blob/master/src/merkleblock.h

マークルブロッククラスCMerkleBlockは一つのブロック内にある複数のトランザクションとその位置(マークルパス)を表現したものです。
SPVノードとフルノード間でやりとりされるのは、このクラスの値をバイナリでシリアライズしたものになります。

CMerkleBlockクラスのシリアライズしている関数の実装を見てみましょう。

class CPartialMerkleTree {
protected:
    /** the total number of transactions in the block */
    unsigned int nTransactions;
    /** node-is-parent-of-matched-txid bits */
    std::vector<bool> vBits;
    /** txids and internal hashes */
    std::vector<uint256> vHash;
    ...
}

template <typename Stream, typename Operation>
inline void SerializationOp(Stream& s, Operation ser_action) {
    // トランザクションの数
    READWRITE(nTransactions);
    // トランザクションIDのarray
    READWRITE(vHash);
        
    std::vector<unsigned char> vBytes;
    if (ser_action.ForRead()) {
        // read
        READWRITE(vBytes);
        CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree*>(this));
        us.vBits.resize(vBytes.size() * 8);
        for (unsigned int p = 0; p < us.vBits.size(); p++){
            us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0;
        }
        us.fBad = false;
    } else {
        // write
        // トランザクションIDのarrayに対するビットOn/Offをバイトにしたもの
        vBytes.resize((vBits.size()+7)/8);
        for (unsigned int p = 0; p < vBits.size(); p++){
            vBytes[p / 8] |= vBits[p] << (p % 8);
        }
        READWRITE(vBytes);
    }
}

コメントに書いていますが、シリアライズされているのは、このクラスのメンバ変数である
nTransactions, vHash, vBits の値だけを使っています。
例えば、対象トランザクションが一つだけ、このブロックに含まれるトランザクションの数が14個の場合の構造を図にしたものがこちらです。

f:id:pebble8888:20180812220229p:plain:w500

vBitsはそのノードの子孫に対象トランザクションが含まれる場合 true です。
枝の場合 true, 葉の場合 false とも言えます。
vHashはそのノードの子孫に対象トランザクションが含まれない場合そのノードのハッシュです。
一番下のノードはトランザクションIDです。
vHashの値が枝のハッシュ値なのか、一番下のノードの葉(トランザクションID)なのかどうかは
Depth(最初の頂点から枝分かれの数)によって判別できます。

vHashの要素数はツリーの末端の葉(leaf)の数となります。この例では 5 です。
vBitsの要素数はツリーの末端の葉の数+ツリーの頂点の数となります。この例では 5+4 = 9 です。

vHash,vBitsのインデックスの順序づけは、もっとも深い葉(トランザクションID)の先頭側、depth が浅い方が先頭側となっています。

CMerkleBlock の利用箇所

CMerkleBlockが利用されているのは、net_processing.cpp, rpc/rawtransaction.cpp, wallet/rpcdump.cpp の3つのソースファイルですが(残りは単体テスト), 簡単そうな、rpc/rawtransaction.cppをみてみます。

CMerkleBlock が使われているのは、以下２つの関数です。

// @param  一つのブロック内にあることを前提としたトランザクションIDの配列
// @return 指定されたトランザクションの情報を含むマークルブロックをHEX文字列にしたもの
UniValue gettxoutproof(const JSONRPCRequest& request)

// @param gettxoutproof で返されたマークルブロックHEX文字列
// @return 指定されたマークルブロックがブロックチェーンに含まれるvalidなものかどうか
UniValue verifytxoutproof(const JSONRPCRequest& request)

どちらも引数を見ると分かるようにJSONRPCのリクエストに応答を返すものです。
gettxoutproof はフルノード上で、指定したトランザクションのunspentなアウトアップトランザクションが存在するブロックを、
ブロックチェーン内を検索します。これにはディスクアクセスを必要とします。
verifytxoutproof はマークルブロック内のマークルパスのハッシュを合成したものがマークルルートハッシュに一致するかどうかを確認します。もし、クラッカーが不正なトランザクションをこのブロックに追加されたものとして利用しようとした場合、
マークルルートハッシュが異なる値を持つので、ブロックチェーンの検証が行われた際に不正データとして破棄されます。

vHashの値に加えて、vBitsの値が必要なのは、マークルルートハッシュを計算するために、vHashをどの順番で合成していけば良いのか順序を知る必要があるためです。
ここでの例でのトランザクション数は14なので、height は4となります。
vHashの値の個数は height + 1 (=5) vBitsの値の個数は 2 * height + 1 (=9) となります。トランザクション数が大きくなっても、heightが大きくなる速さはlog2なので、シリアライズ結果のデータサイズはそれほど大きくはならないことが分かります。

ブルームフィルター

ブルームフィルターとは、一般にはデータベースなど、大量のデータを扱う際に用いられる、インデックス手法の一種です。

ググって見つかったブルームフィルターに関する解説はこちら。

ブルームフィルタ - Wikipedia

ビットコインの技術 BloomFilter プログラミングJava

Scalable Bloom Filtersとは一体....？

C++でブルームフィルタを実装する方法 | POSTD

ブルームフィルターの実装ヘッダはこれだけです。 https://github.com/bitcoin/bitcoin/blob/master/src/bloom.h

あるビットコインアドレスが現在所有してしているコイン量を知るには関連するトランザクション情報全てを全てのブロックからとってくる必要がありますが、その検索方法だと、SPVノードからの問い合わせを受けつけるフルノードはそのSPVノードが利用しているビットコインアドレスを特定できる事になります。
これに若干の秘匿性を持たせる仕組みがブルームフィルターです。

参考:
作って学ぶBitcoin！ゼロから作るSPVウォレット

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