Bech32の問題を修正した改良版Bech32m（BIP-350）

Segwit導入にあたって新しいアドレス（bc1から始まるアドレス）のエンコーディング方式として導入されたのがBIP-173として定義されたBech32

techmedia-think.hatenablog.com

Bech32にはタイプミスなどのアドレスの間違いが検出できるチェックサムが含まれているが、チェックサムを使った検証を回避する予期しない問題が含まれていた。

この問題は、pで終了する有効なBech32データについて、その前にqを挿入したり、qpで終了する場合はqを削除してもチェックサムは有効と判断されてしまういうもの。

現在導入されているsegwit version 0のアドレスについては、データ長が固定であるため、データ長のチェックをすれば基本的に問題ないが、Lightning Networkのインボイスなど可変長なデータのエンコードにBech32を利用している場合は影響する（まぁBech32の本来の定義ではデータ長は最大90文字という制限があるにも関わらずインボイスにBech32を採用してるので、採用根拠に疑問もあるけど）。

Taprootの導入にあたって、↑の問題に対処するためBech32の改良版であるBech32mがBIP-350として定義された↓

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

Segwitアドレスの内、segwit version 1以降のアドレスについてはこのBech32mが使用されることになる。なお、segwitのwitness version 0＝P2WPKHとP2WSHのアドレスは既存のBech32のまま。

Bech32mでは、Bech32のチェックサムの修正が行われているが、大きな仕様変更ではなく、チェックサム計算時にXORする定数を1から0x2bc830a3に置き換えているだけ。

以下、BIP-350の仕様の訳。

仕様

最初に、新しいチェックサムアルゴリズムを定義し、続いてそれを将来のBitcoinアドレスでどのように使用するか文書化する。

Bech32m

Bech32mは、Bech32のチェックサムの仕様を変更し、最後にチェックサムにxorされている定数1を0x2bc830a3に置き換える。結果のチェックサムの検証およびチェックサムの作成アルゴリズムは：

BECH32M_CONST = 0x2bc830a3

def bech32m_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 bech32m_hrp_expand(s):
  return [ord(x) >> 5 for x in s] + [0] + [ord(x) & 31 for x in s]

def bech32m_verify_checksum(hrp, data):
  return bech32m_polymod(bech32m_hrp_expand(hrp) + data) == BECH32M_CONST

def bech32m_create_checksum(hrp, data):
  values = bech32m_hrp_expand(hrp) + data
  polymod = bech32m_polymod(values + [0,0,0,0,0,0]) ^ BECH32M_CONST
  return [(polymod >> 5 * (5 - i)) & 31 for i in range(6)]

他の部分は、 human-readable part (HRP)を含めてBech32から変更されていない。

Bech32とBech32m両方を同時にデコードする関数は、以下のように書ける：

class Encoding(Enum):
    BECH32 = 1
    BECH32M = 2

def bech32_bech32m_verify_checksum(hrp, data):
    check = bech32_polymod(bech32_hrp_expand(hrp) + data)
    if check == 1:
        return Encoding.BECH32
    elif check == BECH32M_CONST:
        return Encoding.BECH32M
    else:
        return None

デコードに失敗した場合はNoneを返し、成功した場合はECH32 / BECH32Mの列挙値を返す。

Segregated witnessアウトプットのアドレス

バージョン0のアウトプット（具体的にはP2WPKHとP2WSHアドレス）は、BIP173で定義されているようにBech32*1を引き続き使用する。Segregated witnessアウトプットバージョン1〜16までのアドレスは、Bech32mを使用する。ここでも、HRP bc を含むエンコーディングに関する他の機能は同じまま。

Segregated witnessアウトプットのアドレスを生成するには、

witness versionが0の場合はBech32を使ってエンコード
witness versionが1以上であればBech32mを使ってエンコード

アドレスをデコードするには、クライアントソフトウェアは、Bech32とBech32m両方のデコーダーを使ってデコードするか*2、両方をサポートするデコーダーのいずれかを使用する。どちらの場合も、デコーダーはエンコーディングがデコードされたwitness version（Bech32の場合はバージョン0、その他のバージョンはBech32m）が期待する値と一致するか検証しなければならない。

以下のコードは、実行する必要があるチェックを示している。呼び出されたコードの詳細については、以下の参照実装セクションでリンクされているPythonのコードを参照。

def decode(hrp, addr):
    hrpgot, data, spec = bech32_decode(addr)
    if hrpgot != hrp:
        return (None, None)
    decoded = convertbits(data[1:], 5, 8, False)
    # Witness programs are between 2 and 40 bytes in length.
    if decoded is None or len(decoded) < 2 or len(decoded) > 40:
        return (None, None)
    # Witness versions are in range 0..16.
    if data[0] > 16:
        return (None, None)
    # Witness v0 programs must be exactly length 20 or 32.
    if data[0] == 0 and len(decoded) != 20 and len(decoded) != 32:
        return (None, None)
    # Witness v0 uses Bech32; v1 through v16 use Bech32m.
    if data[0] == 0 and spec != Encoding.BECH32 or data[0] != 0 and spec != Encoding.BECH32M:
        return (None, None)
    # Success.
    return (data[0], decoded)

エラー箇所

Bech32mはBech32と同様、いくつかの置換エラーの位置を特定できる*3。この機能を、このドキュメントで提案されているsegregated witnessアドレスと組み合わせるには、単純にBech32とBech32m両方でエラー位置を検索する。片方だけがエラー位置を見つけた場合、その片方を報告し、両方ともエラーを見つけた場合（非常に稀なことだが）、いくつかのオプションがある：

結果が異なる場合、修正が少ないものを報告する。
矛盾しているレスポンスを削除する。エラー位置にないシンボルは全てチェックできる。例えば、witness versionのシンボルがエラー位置ではなく、仕様（Bech32では0、Bech32mでは1+）に対応していない場合、その応答を削除できる。

これらの例については、以下のJavascriptのデコーダーを参照。

互換性

このドキュメントでは、v1 segregated witnessアウトプット以上のバージョンの新しいエンコーディングを紹介する。受信側には互換性の問題はないはず。これらのアウトプットタイプはまだmainnetでは使用できないため、ウォレットはまだv1 segregated witnessアドレスをまだ作成していない。

一方、Bech32mの提案はv1以降のsegregated witnessアドレスの前方互換性を破っている。この非互換は意図的なものだ。代替案としてBech32を将来のアドレスの特定のサブセットで使用することも検討されたが、最終的に破棄された。このクリーンブレークにより、新しいアドレスは既存のBech32アドレスの検証と互換性がなくなるため、新しいソフトウェアだけでなく既存の送信者も突然の変更の問題から保護することができる。Taprootの支持者による実験では、バージョン0より高いsegregated witnessアウトプットのバージョンへの送金をサポートするウォレットやサービスはほとんどないため、前方互換性を破ることで失われるものはほとんどない。さらにこれらの実験では、segregated witnessの実装により、バージョン1のアドレスに送信する際にウォレットが資金をバーンしてしまうケースが特定された。このケースがそのまま使われる場合には、この選択されたアプローチにより、そのようなソフトウェアがBech32mアドレスに送信しようとした際に、資金の破壊を防ぐだろう。

参照実装

エンコーダーおよびデコーダーの参照実装
エラーの位置を特定するデコーダー
- JavaScript（デモサイト）

Test Vector

実装のアドバイス BIP173の実装をテストした実験では、多くのウォレットやサービスが高いバージョンのsegregated witnessアウトプットへの送信をサポートしていないことが分かった。ネットワーク上にv1 segregated witnessアウトプットを導入するTaprootのソフトフォークの提案を見越して、実装がv1以降のバージョンへの送信をサポートしていることを確認するとともに、以下に示すTest Vectorの完全なセットを採用することを強く推奨する。ネイティブのsegregated witnessアウトプットのすべての上位バージョンは、ネットワーク上では定義されていないため、ウォレットがそれらを作成したり、受信者が送信者に提供したりすることはできない。また、受信者は自分自身を対象とした支払いがバーンされるだけなので、誤ってそれらを提供したいと思うこともない。ただし、より上位バージョンを有効な受信者として定義することで、ネイティブsegwitアウトプットの上位バージョンを導入する将来のソフトフォークは、Bech32mの仕様を正しく実装するすべてのウォレットと前方互換性がある。

※ 実際のTest Vectorの値はBIP本体を参照。

Appendix：チェックサムの設計と特性

チェックサムはデータを送る途中で入り込んだエラーを検出するのに使われる。Base58Checkのようなハッシュ関数ベースのチェックサムはあらゆるタイプのエラーを均一に検出するが、実際にはすべての種類のエラーが同じように発生することはない。Bech32は置換エラーの検出を優先するが、ある種類のエラーの検出を優先すると、必然的に他の種類のエラーの検出が悪化する。Bech32の設計では、置換以外の単純なエラーパターンはハッシュ関数ベースの設計と同様の検出率を持ち、複雑で実用的でないエラーの検出率が悪くなるだけであるよう仮定していた。Bech32で発見された挿入の弱点は、これが当てはまらなかったことを示している。

Bech32mの場合、置換エラーに対するBech32の保証を維持しつつ、他の一般的なエラーがハッシュ関数ベースのチェックサムよりも悪くならないようにすることを目的としている。新しい標準が実装しやすいように、意図した置換エラーの検出を維持しつつ、q挿入問題を緩和するのに十分であることが観察されたため、設計の変更をxorされる最終的な定数の修正のみに制限している。続いて、新しい定数0x2bc830a3がどうやって選ばれたか説明する。

エラーパターンと検出確率

我々はエラーパターンを、最初に１つ以上の削除、次に隣接する文字の入れ替え、続いて、置換、挿入、重複の順で、特定の位置にあるものとして定義し、有効なチェックサムを持つ文字列に適用されるか、そうでなければランダムに選択される。挿入と置換については、一様にランダムな新しい文字を想定する。例えば、「17番目の文字を削除し、11番目の文字と12番目の文字を交換し、24番めにランダムな文字を挿入する」のはエラーパターンになる。「43番めから48番めの文字をaardvarkに置き換える」のは有効なエラーパターンではない。新しい文字はランダムではなく、この特定の文字列が他のどの文字列よりも秋変えられる可能性が高い理由がないためだ。

30ビットのハッシュを使ったハッシュ関数ベースのチェックサムの設計では、すべてのエラーパターンに対して、 ${2^{-30}}$ で値を誤って受け入れる可能性がある。Bech32は、最大4つの置換で構成されるエラーパターンを誤って受け入れる確率は0であり、常に検出される。q挿入の問題は、Bech32の場合、確率 ${2^{-10}}$ の単純なエラーパターン（最後から2番めの位置にランダムな文字を挿入）が存在することを示している。この時、最後の文字はpで（32文字の中の１つだけ）、挿入される文字はq（32の挿入可能な文字で１つだけ）でなければならない。

エラーパターンが何であるか（どのような種類のエラーがどこで発生するか）の選択は、確率の一部ではないことに注意してほしい。我々はランダムに選択されたものだけでなく、すべてのパターンが上手く動作することを確認しようとしているが、おそらく人間はある主のエラーを他のエラーよりも多く起こし、それを簡単にモデル化することができないからだ。

Bech32mの検出特性

以下の表で、Bech32mのエラー検出特性とBech32の比較を示す。この分析に使用されたコードはここにある。各行は、左4列の制約を介した１つのエラーパターンを指定する。残りの列はこれらのパターンの何%が検出されない特定の確率を持っているか示す。列は以下の通り：

errors: 考慮される個々のエラーの最大数。
of type: 考慮されるエラーのタイプ（置換のみの場合の「subst. only」か、削除、交換、挿入、重複を含む「any」のいずれか）。
window: エラーが発生しなければならないウィンドウの最大サイズ*4。
code/verifier: この行ががBech32もしくはBech32mでエンコードされた文字列かどうか、およびそれらがBech32もしくはBech32mのいずれかの検証によって受け入れられる確率について評価されるかどうか*5 *6。
error patterns with failure probability: 各確率（ ${0, 2^{-30}, 2^{-25}, 2^{-20}, 2^{-15}, 2^{-10}}$ ）について、前の列の制約によって制限されたエラーパターンの何%が誤って受け入れられる確率を持っているか。

特性は２つの種類に分類される。すべてのとりうるHRPを平均化したときに全ての文字にわたって保持されるものと、segregated witnessアドレス*7によって課される長さ制限を持つHRPbc1固有のものだ。

※ 表自体はBIP本体を参照。

表内の数値および以前の定数1との比較は、こちら。

選定プロセス

選定プロセスの詳細はここにあるが、簡単に言うと：

Bech32の1とは異なる ${2^{30}-1}$ の集合から検討する。これらの定数はすべて上の表の(a)でマークされた特性を満たしている。
徹底的な分析により、上の表の（b）でマークされた特性を示さない *8。すべての定数（例えば検出確率 ${2^{-20}}$ で68文字以下のウィンドウ内で2つ以下のエラーのエラーパターンを許容するすべての定数）を除外する。この選択により12054の候補に絞られる。
上の表の（c）の特性を示さない全ての定数を除外することで *9 、候補は79個になる。
最後にタイブレーカーとして、上の表の(d)に一致するエラークラスの数を最小にする候補を選択する。結果が単一の定数0x2bc830a3。

脚注

*1:v0アドレスにBech32とBech32mの両方を許可しない理由は？両方を許可するとエラーの検出機能が低下する（29ビットのチェックサムしかないことと同等）

*2:1つの文字列をBech32とBech32mとして両方同時に有効にすることは可能か？いいえ、有効なBech32とBech32mの文字列は同じ長さの場合、常に少なくとも3文字は異なる。

*3:エラー訂正についてはどうか？BIP-173で説明されているようにエラー訂正を導入すると、エラーを検出する機能が低下する。Bech32(m)のBCH符号としての性質により、技術的には少数のエラーを修正することは可能だが、実装では、エラーが存在する可能性のある場所を示す以上の目的でこれを使用するのは控えること。

*4:エラーパターンのウィンドウサイズとは？エラーパターンのウィンドウサイズは、変更された全ての文字を含む最小の連続範囲の長さになる（入力もしくは出力でもいずれか大きい方）。例えば「abcdef」を「accdbef」に変換するエラーパターンは「bcd」を4文字の[ccdb]に置き換えているため、ウィンドウサイズは4になる。ウィンドウサイズはパターンが２つ以上のエラーで構成されている場合にのみ意味がある。

*5:Bech32の検証でBech32m文字列を受け入れる可能性を気にするのはなぜ？Bech32mが既存のBech32の使用を置き換えるアプリケーションの場合、たとえ少数のエラーが発生したとしても新しいソフトウェアによって作成されたBech32m文字列が、Bech32を想定する古いソフトウェアによって受け入れられないようにする必要がある。

*6:有効なBech32m文字列を取得することで障害が発生し、発生後Bech32の検証は受け入れられるケースも考慮する必要がある？この状況は、理論的にはv1アドレスのバージョン番号をv0に変更するエラーが発生した際のsegregated witnessアドレスで発生する可能性がある。このタイプのエラーの特異性に加えて、v0アドレスに適用される追加の制約のため、これは可能性は低く、分析が困難だ。

*7:bc1固有の分析ではどのような制限が考慮された？（witness programが少なくとも2バイトなので）最小長と、（witness programは最大40バイトであるため）最大長と、witness programは8ビットの倍数であるという事実、最初のデータシンボルは16を超えることはできないという事実や、パディングが0でなければならないという事実はすべて考慮されない

*8:特性はどうやって選択された？これらの特性はすべて、確率が低い定数の拒否やエラーの多い定数、もしくはウィンドウが広い定数を拒否するなどのすべての定数を拒否することなく、可能な限り協力だ

*9:HRP bc1を使用したsegregated witnessアドレスに特化して最適化するのはなぜ？一般的なHRPの解析には制限がある。ここの"Technical details"を参照。我々はまず一般的な使用法に対して最適化をするが、segregated witnessアドレスに対してはタイブレーカーとして最適化を行う

Develop with pleasure!

福岡でCloudとかBlockchainとか。