BIP44が分からなくなる話

この記事はVALU Advent Calendar 7日目のエントリです。

株式会社VALUのバックエンドエンジニアのMito Memelです。先日、HDウォレットの残高を監視するコードを書いた際にBIP44について無駄に詳しくなりましたので、知見を共有します。

BIP44とは

BIP44はHDウォレットのアドレス階層の仕様です。 HDウォレットのアドレス生成アルゴリズムはBIP32で定められていますが、BIP32だけでは「あるHDウォレットのマスターキーを別のメーカーのHDウォレットにインポートしたら残高が復元できる」ということを実現するには足りません。なぜかというと、マスターキーからはアドレスが無限に生成できるので、好き勝手なアドレスに入金してしまうとインポート先のウォレットでどのアドレスに入金されているのかを調べるのに無限時間掛かってしまうためです。

アドレス階層

BIP44では、アドレス階層の使い方を以下の形式に定めています。

m / purpose' / coin_type' / account' / change / address_index

先頭の m はマスターキーのことです。' は強化鍵を使っているかどうかですが、説明すると長くなるのでBIP32を読んでください。各階層の意味は以下の通りです。

purpose

アドレス階層がどのBIPに従っているかを示す番号です。BIP44に従っている場合は 44 になります。

coin_type

Bitcoinは 0 、Ethereumは 60 、というように通貨種別を表す定数です。定数は https://github.com/satoshilabs/slips/blob/master/slip-0044.md で定義されています。この階層により、複数通貨に対応したウォレットも1つのマスターキーだけで表現可能になります。

account

HDウォレットは通常、1種類の通貨内でも複数の口座に分けて残高を管理することができます。この階層にはどの口座かを示すindexが入ります。

change

BIP44では入金用アドレスとお釣り用アドレスの階層を明確に分けています。この階層が0なら入金アドレス、1ならお釣りアドレスです。

address_index

アドレスの連番です。新しいアドレスを生成する際はここをインクリメントしていくことになります。

以上の階層を使用することにより、例えば以下のようにアドレス階層を一意に決めることができます。

Bitcoinの2番目の口座の10番目の入金アドレス: m/44’/0’/1’/0/9
Ethereumの5番目の口座の8番目のお釣りアドレス: m/44’/60’/4’/1/7

※indexは0始まりなので、「2番目」のindexは 1 になります。

アカウント探索

さて、前述の「どのアドレスに入金されているのかを調べるのに無限時間掛かってしまう」問題についてですが、これを解決するためにBIP44では gap limitという概念を導入しています。gap limitとは、「この数以上入金履歴がないアドレスが続いた場合、それ以降のアドレスには入金しない」ということを定めた定数です。BIP44ではこの定数は20となっています。また、account の階層では、未使用の口座がある状態で新しい口座を作成することは禁止されています。つまり、「ウォレット内の全てのBTC口座」を列挙する擬似コードは以下のようになります。

function get_accounts($wallet)
{
    $result = [];
    $account = 0;
    $index = 0;

    while(true){
        $address = $wallet->derive_address("m/44'/0'/{$account}'/0/{$index}");
        $transactions = fetch_transactions($address);
        if($transactions->isEmpty()){
            if(++$index == 20){
                break;
            }
        }else{
            $result[] = $account;
            $account++;
            $index = 0;
        }
    }

    return $result;
}

これで account 階層の列挙はできました。各 account の残高を取得する擬似コードは以下のようになります。

function get_balance($wallet, $account)
{
    $balance = 0;
    $index = 0;
    $gap = 0;

    foreach([0, 1] as $change){
        while(true){
            $address = $wallet->derive_address("m/44'/0'/{$account}'/{$change}/{$index}");
            $transactions = fetch_transactions($address);
            if($transactions->isEmpty()){
                if(++$gap == 20){
                    break;
                }
            }else{
                $balance += get_balance($transactions);
                $gap = 0;
            }
            $index++;
        }
    }

    return $balance;
}

account の列挙では change が0のアドレスのみ走査すれば大丈夫でしたが、残高を取得するにはお釣りアドレスも走査する必要があります。ここが罠ポイントで、BIP44には紛らわしい記述があります。

We scan just the external chains, because internal chains receive only coins that come from the associated external chains.

この記述は前述の account 列挙時の話であって、入金アドレスの走査だけだと「複数のoutputのうちどれが出金先でどれがお釣りなのか？」が分からないので残高を出すことはできません。ここで引っかかっている人は多いようで、Stack Exchangeにも複数の質問が上がっていました。

次に問題になるのが、お釣りアドレスにもgap limitが設定されているのか？それとも account 階層のように必ず 0 から順番に使わないといけないのか？という点ですが、実はこれについてはBIP44の記述は曖昧です。gap limitは入金アドレスについての記述しかなく、上記の擬似コードではひとまず入金アドレスと同じ20としています。実際のウォレットではお釣りアドレスにもっと小さいgap limitを使用している場合もありますが、とりあえず大きめに取っておけばアドレスの取りこぼしは防げます。そこ曖昧にしたらあかんやろと思うのですが、完璧な絶望が存在しないように完璧な仕様も存在しないので、適当にうまいことやりましょう。

まとめ

HDウォレットの互換性はわりとふわっとしているので、同じBIPを採用していると謳っている別メーカーのウォレットにマスターキーをインポートしても100%残高が復旧できるとは限りません。が、同じアドレス階層を採用したウォレットで、インポート先でgap limitを大きく取れば大抵はなんとかなると思われます。知らんけど。

蟻地獄

Twitterに書ききれない長めの文とか書くよ