Segwitのアドレスフォーマットを定義したBIP-173

取り下げられたSegwitのアドレスフォーマットを定義したBIP-142↓

techmedia-think.hatenablog.com

に変わって、新しい仕様でSegwitのアドレスフォーマットを定義したBIP-173が登録されてたので見てみる↓

bips/bip-0173.mediawiki at master · bitcoin/bips · GitHub

イントロダクション

概要

このBIPでは、チェックサムが付与されたBase32フォーマットBech32と、Bech32を使ったsegwitのネイティブ出力（P2WPKHとP2WSH）のアドレスの標準について定義している。

Copyright

このBIPは二条項BSDライセンス下にある。

動機

これまでBitcoinは、ダブルSHA-256をトランケートしたチェックサムを付与したBase58アドレスを使ってきた。BIP-13で定義されたPay-to-script-hash (P2SH)も同様の仕組みを採用している。しかし文字セットとチェックサムのアルゴリズムには以下のような制限がある。

Base58は英数字モードが使えないため、QRコードで多くのスペースを必要とする。
Base58では大文字小文字が混ざってるので、確実に書き留めたり、モバイルキーボードで入力したり、大きな声で読み上げるのには不向き。
ダブルSHA-256のチェックサムは遅く、エラー検出の保証はない。
エラー検出に関する研究のほとんどは、character-setのサイズに対してのみ行われており、Base58は対象ではない。
Base58のデコードは煩雑で比較的遅い。

Segregated Witness（Segwit）の提案には、新しい種類の出力（BIP-141参照）と、その２つの例（P2WPKHやP2WSHなどBIP-143参照）が含まれている。この２つの機能はP2SHでネストすることで、Segwitに対応していない古いクライアントでも間接的に利用することができるが、セキュリティやトランザクションサイズの最適化を考慮するとネストせずに直接使用したほうがいい。このBIPではネイティブのwitness出力（P2WPKHとP2WSH）のための新しいアドレスフォーマットを提案する。

このBIPは以前議論されたBIP-142を置き換えるものである。

サンプル

公開鍵 0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798を使用したアドレスの例が↓P2WSHはkey OP_CHECKSIGというスクリプトを使用した場合の例。

MainnetのP2WPKH
bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t4
TestnetのP2WPKH
tb1qw508d6qejxtdg4y5r3zarvary0c5xw7kxpjzsx
MainnetのP2WSH
bc1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3qccfmv3
TestnetのP2WSH
tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sl5k7

仕様

まず最初にBech32と呼ばれるBase32フォーマットのチェックサムのについて説明し、続いてそれを使用したSegregated Witnessアドレスについて定義する。

Bech32

Bech32の文字列は最大90文字で、以下の要素で構成される↓

human-readable part
読み手に関連するデータの種類やその他の情報を伝えることを意図した要素。有効性はアプリケーションによるが、33〜126の値の範囲のASCII文字に制限されている。
sepalator
常に"1"。human-readable partに1が含まれている場合は、文字列の最後の1がセパレーター。
data
少なくとも6文字で、"1"、"b"、"i"と "o"を除く英数字で構成される。

以下の表はdata部のデータを文字列から数値に変換するための変換表

	0	1	2	3	4	5	6	7
+0	q	p	z	r	y	9	x	8
+8	g	f	2	t	v	d	w	0
+16	s	3	j	n	5	4	k	h
+24	c	e	6	m	u	a	7	l

（表示幅の関係で折りたたんであるだけで、0〜31までの32個データ）

チェックサム

data部分の最後の６文字はチェックサムで、情報を含まない。有効な文字列は、以下のPython3のコードスニペットで指定された有効性の検証をパスする必要がある。以下の引数が与えられたbech32_verify_checksum関数がtrueを返せば有効。

hrp
human-readable partの文字列
data
data部の文字列を上記の変換表で変換した後の整数のリスト

def bech32_polymod(values):
  GEN = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]
  chk = 1
  for v in values:
    b = (chk >> 25)
    chk = (chk & 0x1ffffff) << 5 ^ v
    for i in range(5):
      chk ^= GEN[i] if ((b >> i) & 1) else 0
  return chk

def bech32_hrp_expand(s):
  return [ord(x) >> 5 for x in s] + [0] + [ord(x) & 31 for x in s]

def bech32_verify_checksum(hrp, data):
  return bech32_polymod(bech32_hrp_expand(hrp) + data) == 1

これは最大４文字に影響を与えるエラーの検出とエラー検出できない確率は1/10⁹未満であることを保証するBCH符号 *1の実装になる。より詳細な特性はAppendixを参照。human-readable partは、まず最初に各文字のASCII値の上位bitをチェックサムの計算に送り、続いて０と各下位bitが処理される。

human-readable partとチェックサムが付与されていないdata部の値が与えられた際、その有効なチェックサムは以下のコードで計算できる。

def bech32_create_checksum(hrp, data):
  values = bech32_hrp_expand(hrp) + data
  polymod = bech32_polymod(values + [0,0,0,0,0,0]) ^ 1
  return [(polymod >> 5 * (5 - i)) & 31 for i in range(6)]

エラー訂正

BCH符号の特性の１つとして、エラー訂正に使える点が挙げられる。ただ、エラー訂正にはエラー検出を蝕む副作用がある。訂正により無効な入力を有効な入力に変更することができるが、訂正により有効と判定した入力は、実は本当は正しい入力ではない可能性がある。間違っているけど有効な入力を使うと、資金を使用不能にしてしまう危険性がある。このため実装では、文字列中にエラーが見つかった場合、ユーザーに修正を提案することなく勝手にエラー訂正をすべきではない。

大文字/小文字

デコーダーは大文字と小文字、両方の文字列受け入れなければならないが、両方を混在させないこと。小文字の書式はチェックサム用の文字を決める際に使われる。表示する際は（通常小文字が望ましいが）、大文字の英数字モードだと、通常のバイトモードより45%コンパクトになるので、QRコード内では大文字を使用するのが望ましい。

Segwitのアドレスフォーマット

Segwitアドレスは次のBech32エンコーディングとなる。

human-readable partは、mainnetがbc、testnetがtb
data-partの値は
- 1文字がwitness version
- （BIP-141で定義されている）２〜40バイトのwitness programを以下の手順でbase32に変換
  - witness programのbitから処理する
  - これらのビットを５つのグループに再配置し、必要に応じて末尾にゼロをパディングする
  - 上記の変換表を使ってこれらのbitを文字に変換する

デコード

ソフトウェアは以下の手順でSegwitのアドレスを解釈する。

human-readable partがmainnetではbc、testnetではtbである
デコードされたデータ最初のデータが0〜16の間（witness version）である
残りのデータをバイトに変換する
- データの値をそれぞれ5 bitシフトする。
- それらのbitを8 bitのグループに再配置し、最後の不完全なグループは4 bit以下で、値は全て０で、破棄される。
- これらは2〜40のグループで、witness programのバイトとして解釈される。

デコーダーはwitness programの既知の長さの制限を適用する必要がある。例えばBIP-141では、version byteが0で、witness programが20バイトか32バイトでなければならず、それ以外の場合そのスクリプトは失敗する。

この規則の結果、アドレスは常に14〜74文字の長さとなり、8を法とする長さは0もしくは３，５にはならない。version 0のwitnessアドレスは常に42文字か62文字だが、実装では任意のバージョンの使用を許可しなければならない。

アドレスをscriptPubkeyに変換する際は実装に特に注意する必要がある。witness version nはOP_nとして保存されているため、OP_0は0x00になるがOP_1からOP_16は0x51から0x60としてエンコードされる。bech32アドレスが正しくないscriptPubkeyに変換されると、使用できないもしくは不正なものになってしまう。

互換性

Segwitに対応した新しいソフトウェアのみがこのアドレスを使用できる。それ以外の場合は、今まで通りP2SHもしくはP2PKHを使用する。

論拠

なぜBase32を使うのか？
大文字と小文字が混在しないので、音声での読み上げやQRコードの読み込みが効率的になる。既存のアドレスに比べ、15%ほどデータは長くなるがコピペするアドレスにとっては重要な問題ではない。
Bech32と呼ぶ理由は？
Bechには（エラー検出アルゴリズムが使われている）BCHの文字が含まれ、Baseのように聞こえるから。
なぜアドレスの中にセパレーターを含めるの？
そうすることでhuman-readable partとdata partが明確に分離され、プレフィックを共有する他のhuman-readable partとの潜在的な衝突をさけることができる。またhuman-readable partに文字セットの制限を設けるのを避けることもできる。英数字以外の文字を使うとアドレスのコピーがしにくくなるため（いくつかのアプリケーションではダブルクリックで選択できない）、セパレーターは１にしている。これらの理由により通常の文字セットではない英数字が選択された。
なぜ既存のRFC3548やz-base-32といった文字セットを使わななかったの？
文字セットはこの視覚的類似性データに従って曖昧さを最小限抑えるよう選択され、順序付けは類似した文字のペアを最小にするように選択される。少数のbitの誤りの検出能力をを最大にするためにチェックサムが選択されるが、この選択によりいくつかのエラーモデルの下で性能が改善する。
human-readable partの上位bitが最初に処理されるのはなぜ？
これにより実際にチェックサムされたデータは[high] 0 [low] [data]というデータになる。これはhuman-readable partのエラーが（アルファベットの文字を別のものに変えるような）5 bitのみの変更によるエラーを前提にすると、エラーは[low] [data]部に制限され、このデータは最大89文字になるため、（appendixに記載している）エラー検出のプロパティが適用できる。
Segwitに限らず全てのscriptPubkeyの汎用アドレスフォーマットを定義しては？
それをすると既存のscriptPubKeyタイプのアドレスに混乱をきたす。さらに複数のscriptPubKeyからなるアドレスのようにscriptPubKeyとアドレスが１対１にマッピングされないアドレスが導入された場合、それを古い汎用アドレスフォーマットとして解釈でき、Bitcoinを喪失するかもしれない。
human-readable partに指定するのかbtcじゃなくbcなのはどうして？
bcの方が短いから。
testnetのhuman-readable partの指定がtbなのはどうして？
mainnetのbcと同じ長さにしたかったのと、視覚的にも区別されてる。

参照実装

エンコーダーとデコーダーの参照実装
エラーをローカライズするデコーダー
- JavaScriptの実装（デモサイト）

Appendix

Test vectors

以下の文字列は有効なBech32チェックサムを持つ。

A12UEL5L
an83characterlonghumanreadablepartthatcontainsthenumber1andtheexcludedcharactersbio1tt5tgs
abcdef1qpzry9x8gf2tvdw0s3jn54khce6mua7lmqqqxw
11qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqc8247j
split1checkupstagehandshakeupstreamerranterredcaperred2y9e3w

以下のリストは有効なSegwitアドレスとその16進数のscriptPubkeyを示す。

BC1QW508D6QEJXTDG4Y5R3ZARVARY0C5XW7KV8F3T4: 0014751e76e8199196d454941c45d1b3a323f1433bd6
tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sl5k7: 00201863143c14c5166804bd19203356da136c985678cd4d27a1b8c6329604903262
bc1pw508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7k7grplx: 5128751e76e8199196d454941c45d1b3a323f1433bd6751e76e8199196d454941c45d1b3a323f1433bd6
BC1SW50QA3JX3S: 6002751e
bc1zw508d6qejxtdg4y5r3zarvaryvg6kdaj: 5210751e76e8199196d454941c45d1b3a323
tb1qqqqqp399et2xygdj5xreqhjjvcmzhxw4aywxecjdzew6hylgvsesrxh6hy: 0020000000c4a5cad46221b2a187905e5266362b99d5e91c6ce24d165dab93e86433

以下のリストは無効なSegwitアドレスと、その無効な理由

tc1qw508d6qejxtdg4y5r3zarvary0c5xw7kg3g4ty: human-readable partが無効
bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t5: チェックサムが無効
BC13W508D6QEJXTDG4Y5R3ZARVARY0C5XW7KN40WF2: witness versionが無効
bc1rw5uspcuh: witness programの長さが無効
bc10w508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7kw5rljs90: witness programの長さが無効
BC1QR508D6QEJXTDG4Y5R3ZARVARYV98GJ9P: version 0のwitness programの長さとして無効
tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sL5k7: 大文字/小文字の混在
tb1pw508d6qejxtdg4y5r3zarqfsj6c3: 4 bitより多いの0パディング
tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3pjxtptv: ゼロパディングされていない

チェックサムの設計

設計の選択肢

BCH符号は、任意のアルファベットで構成でき、サイズとエラー検出機能において良いトレードオフの関係がある。BCH符号はほぼバイナリのアルファベットに対して使用するが、これは必須要件ではない。このためCRC符号より我々のユースケースに適している。リード・ソロモン符号と違い、アルファベットのサイズより１つ小さい長さの制限もない。効率的なエラー訂正もサポートしており、エラー検出の実装は非常に簡単である。

アドレスの長さとエラー検出のレベルはトレードオフにあり、６つのチェックサム文字列を採用した。６文字ではランダムな障害の可能性が1/100,000,000という充分低い数になる。witness programのデータにセットできる最大長は40バイトで、その保護データを含めると最大71バイトになり、BCH符号ではこれで最大４つのエラーを検出できる。

選択されたプロパティ

これらのコードの多くは検出した数より多くのエラーを処理すると悪い結果になる。３つのエラー検出と４つのエラー検出で実際にどの程度のパフォーマンスの影響があるか分析する。

選択した符号は以下の通り↓

93, 151, 165, 341, 1023, 1057までの長さのデータに対し、３つもしくは４つのエラーを検出するよう設計された159605のBCH符号の網羅的なリストを用意する。
長さ71までで４つのエラー検出をし、結果残り28825個の符号が残る。
それから５文字エラーに対してワーストケースのウィンドウを持つ符号を選択すると310個の符号が残る。
続いて、少数のビットエラーを検出しない可能性が最も低い符号を選択する。

単純計算で6.5 * 10¹⁹のチェックサムの評価が必要なので、分析のため衝突検索のアプローチを使う。コードはここにある。

プロパティ

以下の表は検出失敗の可能性についてまとめたもの↓

f:id:techmedia-think:20170509112919p:plain

これは、P2WPKHのアドレス３９文字に対し、ランダムにその５文字を変更した場合、エラー検出できなくなる確率は0.756/100,000,000であることを意味している。この５文字の変更の範囲が19文字の範囲内の場合、確率はさらに0.093/100,000,000に減少する。エラーの数が増えるにつれ、確率は1 in 2³⁰ = 0.931 / 100,000,000に収束する。

選択された符号は1023文字までは合理的にうまく実行されるが、他の設計では、上記の89文字の長さ（セパレーターを除く）が適している。

まとめ＆所感

BIP-142を置換するBIPで、Segwitのアドレスフォーマットを定義する。
P2PKHやP2SHではアドレスを算出する際にBase58エンコーディングされていたけど、今回はそれとは別のBase32ベースのエンコーディングを提案してる。
Base32では大文字/小文字の区別が無い。
QRコードでは大文字の英数字の場合は英数字モードが利用でき、同じスペースに付与できるデータ量が増え、読み込みも効率的に行われる。
Base58と違って、エラー訂正が可能。ただ訂正結果が実はホントのデータではなかった場合、資金を失うことになるので、自動訂正は推奨しないと。
Segwitのアドレスではhuman-readable part部にmainnet: bc、testnet: tbという人が見分けるためのコードを、data-part部をwitness versionとwitness programで構成する。
このBIPはInformational BIPというガイドライン的な位置付けのBIPなので、version bitsを使ったデプロイなどは行われず、ウォレットや各ノード実装がこれに従うかどうかの判断は各実装者に委ねられるけど、参照実装があるのでCoreには取り込まれるんだろう。
符号化のアルゴリズムもいろいろあって、面白そうね。

参照実装でRubyの実装が無かったのでPython版を参考に移植してみた↓

github.com

*1:誤り訂正符号の一種。考案者のAlexis HocquenghemとRaj Chandra BoseとD. K. Ray-Chaudhuriの名前からBCHと名付けられた。

Develop with pleasure!

福岡でCloudとかBlockchainとか。