Develop with pleasure!

福岡でCloudとかBlockchainとか。

BIP32鍵導出パスのパステンプレートを定義したBIP-88

BIP Bitcoin

Bitcoinの秘密鍵やアドレスは決定性ウォレットによって導出されるのが主流だが、シードからどんなアドレスを導出するか（どんなBIP32導出パスを使うか）は、スクリプトタイプによっていくつかのBIPが定義されており、そのどれが使われているか、もしくは独自のカスタム仕様になっているかは、使用するウォレットによって異なる。つい最近も、マルチシグ用のパス仕様の提案がされたばかり↓

techmedia-think.hatenablog.com

そのため、あるウォレットから別のウォレットに移行するための、シードをインポートしたとしても、同じアドレスを導出するとは限らない。

そこで、多々ある導出パスの仕様がある中、各ウォレットがそのどれを使っているのか、またはカスタム仕様がある場合、どういった制約があるのかを表現できるフォーマットの標準を定めようというのが最近提案されたBIP-88↓

https://github.com/bitcoin/bips/blob/master/bip-0088.mediawiki

m/{44,49,84}'/0'/0'/{0-1}/{0-50000}や{0-2,33,123}/*のようなフォーマットで、各ソフトウェアが使用するパスおよびその制限（ある階層以下では何個以上の鍵を導出してはならないなど）を表現する。

この仕様とは別に、output descriptorもパスを表現する方法もあり、こないだ書いたBSMSの提案ではdescriptorテンプレートとして制限の置き換えが可能な/**の表記の提案もある↓

techmedia-think.hatenablog.com

ので、今後の標準化とどう採用が進むかはまだ柔らかそう。

以下、BIPの意訳。

概要

このドキュメントでは、BIP32導出パスに課すことができる制約を指定するテンプレートの表現形式を説明する。

テンプレートで指定された制約により、制約にマッチした有効なパスと、制約を超えた無効なパスを簡単に識別できる。

動機

BIP32の導出パスフォーマットは普遍的なもので、BIP43を始めBIP44、45、49、84などで多くの導出スキームが提案された。また、フォーマットの柔軟性により、業界の参加者は、一般的には必ずしも有用ではないが、特定の目的にあったカスタム導出スキームを実装することができた。

導出スキームに既存のBIPを使用する場合でも、その使用法はウォレット間で一様ではない。これは、ソフトウェアベンダーが導出パスを決定する際に、考慮事項や優先順位が異なる可能性があるためだ。これにより、ユーザーが以前使用していたウォレットとは異なるアドレスを導出するウォレットを使ってコインにアクセスしようとすると、問題に直面する可能性がある。

既知の解決策

この問題は、異なるウォレットで使用されているパスを追跡する専用のウェブサイト（walletsrecovery.org）が作られるほど、一般的なものだ。

この記事を書いている時点で、このウェブサイトは、複数の導出パスを簡潔に記述するために独自のフォーマットを使用している。著者が知る限り、このBIPが登場する前にパステンプレートを記述するために公に使われていた唯一のフォーマットだった。このフォーマットは、ウェブサイトのメインページ以外、どこにも明記されていなかった。このフォーマットでは代替導出インデックス（例：m/|44'|49'|84'/0'/0'）や代替パス全体（m/44'/0'/0'|m/44'/1'/0'）を示すのに|が使われている。

これは、ソフトウェアで処理するためのテンプレートフォーマットとして宣言されたものではなく、説明のためだけのアドホックなフォーマットのようだ。このようなアドホックなフォーマットに対し、本BIPえは、ソフトウェアによる曖昧さのないパースと、人間による容易な読み取りを同時に実現することを目的としたフォーマットを採用している。人間はパスのテンプレート化された部分を、テンプレート内で|を使った場合よりも簡単に視覚的に検出することができる。より広い範囲のパスを1つのテンプレートでより簡潔かつ明確に定義できる。

使用目的とメリット

ウォレットソフトウェアの作者は、提案されているフォーマットを使って、そのソフトウェアが使用している導出パスを記述することができる。これにより、別のソフトウェアに切り替える際や、旧ウォレットの復元をする際のユーザーの利便性が向上する。

導出パスを無制限に使用するのは、特定の状況下では安全ではないかもしれない。特にあるトランザクションのお釣り用のアウトプットが、送信者にとって未知のパスで導出されたアドレスに送信された場合、送信者はお釣り全体へのアクセスができなくなる可能性がある。

既知のパスのチェックソフトウェアやファームウェアにハードコードするという単純なアプローチは、相互運用性の低下に繋がる。ベンダーは、特定の非汎用アプリケーション用にカスタムパスを選択することができず、既知のパスを使用するように改造するか、他のベンダーにカスタムパスをサポートするよう説得するしかなくなる。このアプローチでは、拡張性に欠ける。

本ドキュメントで提案する柔軟なアプローチは、「BIP32パステンプレート」の標準的な表記法を定義することである。このテンプレートには、導出パスに課すべき制約が簡潔に記述されている。

このパステンプレートを広くサポートすることで、ソリューションの相互運用性と柔軟性が向上し、ベンダーや個々の開発者が独自のカスタム制限を簡単に定義できるようになる。このようにして、制限のない導出パスの偶発的もしくは悪意ある使用のリスクに柔軟で正確な方法で対処できる。

既知のパステンプレートは、デバイスやアプリケーションでデフォルトで設定されるが、ユーザーは自分の用途に関係のないテンプレートを無効にするオプションを使用できる。

カスタムパステンプレートのフォーマットを標準化することで、デバイスやアプリケーション固有のパス制限を適用する際に、共通のアプローチで開発することができる。このようなアプローチの一連として、パステンプレートやその他のカスタムパラメータを含むアプリケーション固有のプロファイルを利用できるようになる。ただし、悪意あるプロファイルや不正なプロファイルが誤ってインストールされることがないよう、注意が必要だ。

仕様

テンプレートのフォーマットは、読みやすく便利で、視覚的に明確であるよう選択されている。

テンプレートはオプションのプレフィックスm/で始まり、スラッシュ文字（/）で区切られた１つ以上のセクションが続く。

実装は、セクションの最大数を制限する場合がある。

各セクションは、インデックステンプレートで構成され、オプションでアポストロフィ（'）もしくは文字hのいずれかの強化導出のマーカーが後ろに付く。

インデックステンプレートには、

  • 0〜2147483647の整数値（ユニットインデックステンプレート）
  • 0〜2147483647の任意の整数値を表す単一文字*（ワイルドカードインデックステンプレート）
  • 文字{の後にカンマで区切られた複数のインデックスが続き、その後に文字}で終わる（範囲インデックステンプレート）

がある。

実装は、範囲インデックステンプレート内のインデックス範囲の最大数を制限することができる。

インデックステンプレートの直後に強化導出マーカーが続く場合、これは、そのインデックステンプレートで指定されたすべての値が、照合のために2147483648だけ増加することを意味する。

インデックス範囲は、

  • 0〜2147483647の整数値（ユニット範囲）
  • 0〜2147483647の整数値の後に文字-が続き、その後に0〜2147483647の別の整数値が続く（非ユニット範囲）

がある。

非ユニット範囲について、-の左側の値はrange_startで、右側の値はrange_end。

ユニット範囲については、start/endはなくても、range_startとrange_endは等しい。

ユニットインデックステンプレートにはユニット範囲である単一のインデックス範囲が含まれている。

ワイルドカードインデックステンプレートには、単一のインデックス範囲が含まれ、range_startは0、range_endは2147483647に設定される。

制約：

  1. 曖昧さをなくすため、パステンプレートに空白があってはいけない。
  2. 範囲インデックステンプレート内のカンマは、インデックス範囲の間にのみ出現する。
  3. 曖昧さをなくすため、単一の値にマッチするインデックス範囲はユニット範囲として指定する必要がある。
  4. 曖昧さをなくすため、0-2147483647といったインデックス範囲は許可されず、代わりにワイルドカードインデックステンプレートを使わなければならない。
  5. 非ユニット範囲について、range_endは必ずrange_startより大きくなければならない。
  6. 範囲インデックステンプレート内に複数のインデックス範囲がある場合、２つめ以降の範囲のrange_startは、前の範囲のrange_endよりも大きくなければならない。
  7. 曖昧さをなくすため、0より大きい整数値のすべての表現は0で始めてはならない（先頭0は許可されない）。
  8. パステンプレート内のいずれかのセクション内に強化導出マーカーが現れた場合、先行するすべてのセクションも強化導出を指定しなければならない。
  9. 曖昧さをなくすため、パステンプレート内で強化導出マーカーが現れた場合、先行するすべてのセクションでも同じ強化導出マーカー（hもしくは'）を使用しなければならない。
  10. 曖昧さをなくすため、末尾のスラッシュ（例えば1/2/）や重複するスラッシュ（例えば0//1）が、テンプレート内にあらわれてはならない。

有効なパステンプレート文字列ごとに、まったく同じパスのセットにマッチする有効なテンプレート文字列が存在しないような、完全に曖昧さのないエンコーディングが望まれるかもしれない。この場合、誰ががテンプレートを比較する際、パースせずに単純に文字列の同一性をチェックすることができるようになる。

これを実現するには2つの追加ルールが必要だ。

  • 範囲インデックステンプレートでは、後続の範囲は前の範囲の終わりに1を加えた値で始まってはならない。したがって、{1,2,3-5}は許可されず、{1-5}と指定する必要がある。このルールにより、頻繁に編集する場合テンプレートの利便性が低下する可能性がある。
  • 強化導出のマーカーは1種類のみ（hもしくは'）のみ許可される。

2つめのルールを必要とする代わり、実装はテンプレート文字列を比較する前に、あるタイプのマーカーを別のタイプに置き換えるだけで済む。

フルテンプレートと部分テンプレート

テンプレートがm/で始まる場合、これは完全なフルテンプレートで、パス全体にマッチすることを意味する。

テンプレートがm/で始まらない場合、これは部分テンプレートであることを意味し、適切な文脈において、パスの一部にマッチするのに使用できる（例えば、パスのサフィックスに対する制約が動的で、パスのプレフィックスに対する制約が固定されている場合など）。

フルテンプレートは、部分テンプレートを組み合わせることができる。部分テンプレートはフルテンプレートを拡張し、より長いフルテンプレートになる。

部分テンプレートは他の部分テンプレートと組み合わせることができ、その結果より長い新しい部分テンプレートになる。

フルテンプレートは別のフルテンプレートと組み合わせることはできない。

実装では、フルテンプレートのパースと、フルテンプレートに対するパスのマッチングをサポートしなければならない。

実装は、部分テンプレートのパースと、部分テンプレートに対するパスのマッチングおよびテンプレートの結合をサポートしてもよい。

パース結果

有効なパステンプレートのパースに成功すると、結果はセクションのリストで表すことができる。各セクションはインデックス範囲のリストで、インデックス範囲は（range_startとrange_endの）タプル。セクションの長さはテンプレート長とも呼ばれる。

マッチング

マッチングは、BIP32パス（部分テンプレートの場合はBIP32パスの一部）を表す整数値のリストに対して実行されることになる。このリストの長さをパス長と呼ぶ。

このリストの非強化導出インデックスは、0〜2147483647の値で表す必要がある。

強化導出インデックスのリストは、2147483648〜4294967295の値で表す必要がある。

マッチングアルゴリズムは：

1. パス長がテンプレート長と異なる場合は失敗。
2. パス内の位置Nにある書く値Vについて、
   テンプレート内の位置Nにあるセクション内のすべてのインデックス範囲について、
   値Vがrange_startより小さいか、range_endより大きい場合は失敗
3. それ以外は成功

正式な仕様

記述されたテンプレートフォーマットのパーサーの有限状態マシン（FSM）とマッチング式は、TLA+仕様言語（https://github.com/dgpv/bip32_template_parse_tplaplus_spec）で規定されている。

この仕様は、TLCチェッカーと付属のスクリプトを使って実装のテストデータを生成することができる。

実装

正式な仕様ではFSMを指定しているが、これは豊富な文字列処理機能を利用できない実装には不向きである。しかし、そのような機能が利用できる場合は、テンプレートをまずセクションに分割し、次にセクションをインデックステンプレートに分割し、各インデックステンプレートを個別に解析するという文字列全体を分解するアプローチを採用することになるだろう。

しかしFSMベースのアプローチは、正式な仕様に近づけることができ、またTLCチェッカーで生成されたテストデータは、FSMベースの実装に対してより良いカバレッジを与えるだろう。テンプレート文字列にいくつかのエラーが含まれている場合、分解を行うアプローチを使用した実装は、FSMベースの実装よりも速くこれらのエラーを検出する可能性があり、その逆も同様。

現時点で3つの実装が存在する

互換性

ユニットインデックステンプレートのみを含むフルパステンプレートは、完全に有効なBIP32パスを表す。

現在作者が知っている他のパステンプレート標準は存在しない。

https://github.com/bitcoin/bitcoin/issues/17190には、Bitcoin Scriptのdescriptorのパステンプレートに関する議論があり、xpub...{0,1}/*というフォーマットが提案されているが、この内{0,1}/*の部分が、このBIPのフォーマットの部分パステンプレートに相当する。

サンプル

m/{44,49,84}'/0'/0'/{0-1}/{0-50000}は、アドレスインデックスが50000を超えることができないという制約付きのBIP44およびBIP49、BIP84パスの外部チェーンと内部チェーンの両方にマッチするフルテンプレートを定義する。

パース後の表現は次のようになる（Pythonのシンタックスを使用し、フル/部分の区別は無視する）：

[[(2147483692, 2147483692), (2147483697, 2147483697), (2147483732, 2147483732)),
 [(2147483648, 2147483648)],
 [(2147483648, 2147483648)],
 [(0, 1)],
 [(0, 50000)]
]

{0-2,33,123}/*は、１つめのインデックスとして非強化導出の値0、1、2、33、123にマッチし、2つめのインデックスは任意の非強化導出値にマッチする部分テンプレートを定義する。

パース後の表現は次のようになる：

[[(0, 2), (33, 33), (123, 123)], [(0, 2147483647)]]

*h/0は、強化導出されたインデックスの後に、非強化導出インデックスが続く部分を定義する。

パース後の表現は次のようになる：

[[(2147483648, 4294967295)], [(0, 0)]]