BIP 350 — v1以降の​ウィットネスアドレス向けBech32m形式

  BIP: 350
  Layer: Applications
  Title: Bech32m format for v1+ witness addresses
  Authors: Pieter Wuille <pieter@wuille.net>
  Status: Deployed
  Type: Specification
  Assigned: 2020-12-16
  License: BSD-2-Clause
  Discussion: 2021-01-05: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-January/018338.html [bitcoin-dev] Bech32m BIP: new checksum, and usage for segwit address
  Replaces: 173

序論

概要

本文書はBech32の改良版であるBech32mを定義し、BIP173を改訂してバージョン1以降のネイティブなウィットネス出力にBech32mを用いるようにする。バージョン0のウィットネス出力は引き続きBech32を使用する。

著作権

本BIPは2条項BSDライセンスの下でライセンスされる。

動機

BIP173はBech32と呼ばれる、汎用のチェックサム付き32進エンコード形式を定義した。これはバージョン0のウィットネス出力（P2WPKHとP2WSH、BIP141参照）や、その他の用途で使われている。

Bech32には予期しない弱点 (https://github.com/sipa/bech32/issues/51)がある。末尾の文字が ‘p’ であるとき、その直前に任意個の ‘q’ を挿入または削除してもチェックサムが無効にならないというものだ。これはバージョン0のBIP173アドレスが2種類の長さに限定されているため既存の用途には影響しないが、将来の用途やBech32エンコーディングを用いる他のアプリケーションには影響しうる。

本文書はこの問題に対処するため、この挿入弱点と関連する問題を緩和したBech32の変種であるBech32mを規定する。

仕様

まず新しいチェックサムアルゴリズムを規定し、続いて将来のビットコインアドレスでの使用方法を文書化する。

Bech32m

Bech32mはBech32仕様のチェックサムを変更し、末尾でxorされる定数1を0x2bc830a3に置き換える。得られるチェックサムの検証・生成アルゴリズムは次のとおり（Pythonで記す。BIP173のBech32節 (https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki#Bech32)のコードも参照）。

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)]

その他のBech32の側面（人間可読部分（HRP）を含む）はすべて変更しない。

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を返し、成功時にはそれぞれの規格に従ったデコードを示すBECH32またはBECH32Mのいずれかの列挙値を返す。

ウィットネス出力向けのアドレス

バージョン0の出力（具体的にはP2WPKHとP2WSHアドレス）は、BIP173で規定されたとおり引き続きBech32を用いるなぜv0アドレスにBech32とBech32mの両方を許可しないのか？ 両方のエンコーディングを許可すると誤り検出能力が低下する（チェックサムが実質29ビットしかないのと同等になる）。。バージョン1から16のウィットネス出力向けのアドレスはBech32mを用いる。ここでもエンコーディングのその他の側面（‘bc’ のHRPを含む）はすべて同じままである。

ウィットネス出力のアドレスを生成するには、

• ウィットネスバージョンが0の場合、Bech32でエンコードする。
• ウィットネスバージョンが1以上の場合、Bech32mでエンコードする。

アドレスをデコードする際、クライアントソフトウェアはBech32とBech32m両方のデコーダーでデコードを試みる単一の文字列が同時にBech32かつBech32mとして有効になりうるか？ ならない。有効なBech32文字列とBech32m文字列は、同じ長さであれば必ず3文字以上異なる。か、両方を同時にサポートするデコーダーを用いるべきである。いずれの場合も、アドレスデコーダーは、デコードされたウィットネスバージョンについて期待されるエンコーディング（バージョン0はBech32、それ以外は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と同様、少数の置換誤りの位置を特定誤り訂正についてはどうか？ BIP173で説明されているとおり、誤り訂正を導入すると誤り検出能力が下がる。Bech32(m) はBCH符号としての性質上、少数の誤りを技術的には訂正できるが、実装は誤りが存在しうる位置を示す以上の用途にこれを使うべきではない。できる。本文書が提案するウィットネス出力アドレスにこの機能を組み合わせるには、単純にBech32とBech32mの両方で誤り位置の特定を試みればよい。片方だけで誤り位置が見つかった場合はそれを報告する。両方で見つかった場合（これは非常にまれなはずである）、いくつかの選択肢がある。

• 訂正数がより少ない方を報告する（両者が異なる場合）。
• 矛盾する応答を除外する。誤り位置に当たらない記号は、どれも照合に使える。たとえば、ウィットネスバージョンの記号が誤り位置に当たらないのに、使っている規格の値（Bech32なら0、Bech32mなら1以上）と合わない場合は、その応答を除外できる。

上に述べたことの実例は、下記の高機能なJavaScriptデコーダーを参照のこと。

互換性

本文書はv1以降のウィットネス出力向けに新しいエンコーディングを導入する。受信側に互換性の問題は生じないはずである。v1のウィットネスアドレスを生成するウォレットはまだ存在しない。この出力タイプはメインネットではまだ使用できないためである。

一方で、Bech32mの提案はv1以降のバージョンのウィットネスアドレスへの送金について前方互換性を破壊する。この非互換性は意図的 (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-October/018236.html)なものである。将来のアドレスの特定のサブセットについてBech32を使い続ける代替案も検討された (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-November/017460.html)が、最終的には退けられた (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018293.html)。明確な断絶を導入することで、新しいソフトウェアだけでなく既存の送金者も、この書き換えの問題（挿入弱点）から守られる。新しいアドレスは既存のBech32アドレス検証と非互換になるからである。Taproot提案者による実験 (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-November/018268.html)によれば、より高いバージョンのウィットネス出力への送金をサポートするウォレットやサービスはほとんど存在しなかったため、前方互換性を破壊 (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018298.html)しても失うものはわずかである。さらに、これらの実験により、セグリゲーテッドウィットネスの実装のせいで、v1アドレスへ送金するときにウォレットが資金を焼失させかねないケースが見つかった。仮にそうしたソフトウェアが今なお使われている場合でも、本文書が選んだ方式であれば、Bech32mアドレスへの送金を試みたときに資金を破壊してしまう事態を防げる。

参照実装

• 参照エンコーダーおよびデコーダー：

  • Pythonによるリファレンス実装 (https://github.com/sipa/bech32/blob/master/ref/python)
  • Cによるリファレンス実装 (https://github.com/sipa/bech32/blob/master/ref/c)
  • C++ によるリファレンス実装 (https://github.com/sipa/bech32/blob/master/ref/c++)
  • Bitcoin CoreによるC++ 実装 (https://github.com/bitcoin/bitcoin/pull/20861)
  • JavaScriptによるリファレンス実装 (https://github.com/sipa/bech32/blob/master/ref/javascript)

• 誤り位置を特定する高機能デコーダー：

  • JavaScript版 (https://github.com/sipa/bech32/blob/master/ecc/javascript)（デモサイト (http://bitcoin.sipa.be/bech32/demo/demo.html)）

テストベクトル

実装上の助言BIP173実装を対象とした実験では、多くのウォレットやサービスが、より高いバージョンのウィットネス出力への送金に対応していないことが判明した。Taproot (https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki)のソフトフォークがネットワークにv1ウィットネス出力を導入することを見越し、以下に示すテストベクトルの完全な集合を用いること、および実装がv1以上のすべてのバージョンへの送金に対応していることを強く推奨する。ネイティブなウィットネス出力のより高いバージョンはすべて、有効な受取先として認識されるべきである。より高いバージョンはネットワーク上でまだ定義されていないため、いかなるウォレットもそれらを生成すべきではなく、いかなる受取人もそれらを送金者に提供すべきではない。受取人がそうしたアドレスを偽って送金者に示そうとする理由もないはずである。受取人は自分宛の支払いが焼失するのを目にするだけだからである。しかし、より高いバージョンを今のうちに有効な受取先として定義しておくことで、将来ネイティブなSegWit出力のより高いバージョンを導入するソフトフォークが、Bech32m仕様を正しく実装しているすべてのウォレットと前方互換になる。

Bech32mのテストベクトル

以下の文字列は有効なBech32mである。

• A1LQFN3A
• a1lqfn3a
• an83characterlonghumanreadablepartthatcontainsthetheexcludedcharactersbioandnumber11sg7hg6
• abcdef1l7aum6echk45nj3s0wdvt2fg8x9yrzpqzd3ryx
• 11llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllludsr8
• split1checkupstagehandshakeupstreamerranterredcaperredlc445v
• ?1v759aa

いかなる文字列もBech32とBech32mの両方に同時に有効となることはないため、上記の例はBech32にとっての無効なテストベクトルとしても機能する。

以下の文字列はBech32mとして無効である（無効となる理由とともに示す）。

• 0x20 + 1xj0phk：HRPの文字が範囲外
• 0x7F + 1g6xzxy：HRPの文字が範囲外
• 0x80 + 1vctc34：HRPの文字が範囲外
• an84characterslonghumanreadablepartthatcontainsthetheexcludedcharactersbioandnumber11d6pts4：全体の最大長を超過
• qyrz8wqd2c9m：区切り文字がない
• 1qyrz8wqd2c9m：HRPが空
• y1b0jsk6g：無効なデータ文字
• lt1igcx5c0：無効なデータ文字
• in1muywd：チェックサムが短すぎる
• mm1crxm3i：チェックサム内に無効な文字
• au1s5cgom：チェックサム内に無効な文字
• M1VUXWEZ：HRPを大文字形にしてチェックサムを計算している
• 16plkw9：HRPが空
• 1p2gdwpf：HRPが空

v0〜v16のネイティブウィットネスアドレスのテストベクトル

以下は有効なSegWitアドレスと、それが変換されるscriptPubKeyを16進数で示したものである。

• BC1QW508D6QEJXTDG4Y5R3ZARVARY0C5XW7KV8F3T4：0014751e76e8199196d454941c45d1b3a323f1433bd6
• tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sl5k7：00201863143c14c5166804bd19203356da136c985678cd4d27a1b8c6329604903262
• bc1pw508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7kt5nd6y：5128751e76e8199196d454941c45d1b3a323f1433bd6751e76e8199196d454941c45d1b3a323f1433bd6
• BC1SW50QGDZ25J：6002751e
• bc1zw508d6qejxtdg4y5r3zarvaryvaxxpcs：5210751e76e8199196d454941c45d1b3a323
• tb1qqqqqp399et2xygdj5xreqhjjvcmzhxw4aywxecjdzew6hylgvsesrxh6hy：0020000000c4a5cad46221b2a187905e5266362b99d5e91c6ce24d165dab93e86433
• tb1pqqqqp399et2xygdj5xreqhjjvcmzhxw4aywxecjdzew6hylgvsesf3hn0c：5120000000c4a5cad46221b2a187905e5266362b99d5e91c6ce24d165dab93e86433
• bc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vqzk5jj0：512079be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

以下は無効なSegWitアドレスと、その無効性の理由である。

• tc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vq5zuyut：無効なhuman-readable part
• bc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vqh2y7hd：無効なチェックサム（Bech32mであるべきところがBech32）
• tb1z0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vqglt7rf：無効なチェックサム（Bech32mであるべきところがBech32）
• BC1S0XLXVLHEMJA6C4DQV22UAPCTQUPFHLXM9H8Z3K2E72Q4K9HCZ7VQ54WELL：無効なチェックサム（Bech32mであるべきところがBech32）
• bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kemeawh：無効なチェックサム（Bech32であるべきところがBech32m）
• tb1q0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vq24jc47：無効なチェックサム（Bech32であるべきところがBech32m）
• bc1p38j9r5y49hruaue7wxjce0updqjuyyx0kh56v8s25huc6995vvpql3jow4：チェックサム内に無効な文字
• BC130XLXVLHEMJA6C4DQV22UAPCTQUPFHLXM9H8Z3K2E72Q4K9HCZ7VQ7ZWS8R：無効なウィットネスバージョン
• bc1pw5dgrnzv：無効なプログラム長（1バイト）
• bc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7v8n0nx0muaewav253zgeav：無効なプログラム長（41バイト）
• BC1QR508D6QEJXTDG4Y5R3ZARVARYV98GJ9P：ウィットネスバージョン0として無効なプログラム長（BIP141参照）
• tb1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vq47Zagq：大文字・小文字の混在
• bc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7v07qwwzcrf：4ビットを超えるゼロパディング
• tb1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vpggkg4j：8→5変換における非ゼロパディング
• bc1gmk9yu：データ部が空

付録：チェックサムの設計と性質

チェックサムはデータ転送中に発生した誤りを検出するために用いられる。Base58Checkのようなハッシュ関数ベースのチェックサムはあらゆる種類の誤りを一様に検出するが、実際に発生しやすい誤りの種類は誤りのクラスごとに一様ではない。Bech32は置換誤りの検出を優先しており、あるクラスの誤りの検出能力を高めれば、必然的に別のクラスの誤りの検出能力は低下する。Bech32の設計時には、置換以外の単純な誤りパターンもハッシュ関数ベースの設計と同程度の検出率を持ち、検出能力が下がるのは複雑で実用上まれな誤りに限られると想定されていた。今回発見された挿入弱点は、この想定が成り立たないことを示している。

Bech32mでは、置換誤りに対するBech32の保証を維持しつつ、他の一般的な誤りについてもハッシュ関数ベースのチェックサムより性能が劣らないようにすることを目指す。新しい規格を実装しやすく保つため、変更範囲は末尾でxorされる定数の変更のみに限定する。これは ‘q’ 挿入問題を緩和しつつ意図した置換誤り検出を維持するのに十分であると確認された (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-December/017521.html)ためである。以下では、新しい定数0x2bc830a3をどのように選定したかを説明する。

誤りパターンと検出確率

誤りパターンは、次の操作の並びと定義する。まず1個以上の削除、次に隣接する文字の入れ替え、続いて置換・挿入・重複を、この順に、それぞれ決まった位置で行う。対象は、有効なチェックサムを持ち、それ以外はランダムに選んだ文字列である。挿入と置換については、一様ランダムな新しい文字を仮定する。たとえば、「17番目の文字を削除し、11番目の文字と12番目の文字を入れ替え、24番目の位置にランダムな文字を挿入する」は誤りパターンである。「43〜48番目の文字を “aardvark” に置き換える」は有効な誤りパターンではない。新しい文字がランダムではなく、しかもこの特定の文字列がほかのどの文字列よりも置換に使われやすいと考える理由もないためである。

30ビットのハッシュを用いるハッシュ関数ベースのチェックサム設計であれば、あらゆる誤りパターンについて誤って受理してしまう確率は2^-30に等しい。Bech32は、4個以下の置換からなる誤りパターンを誤って受理する確率が0である。つまり常に検出される。‘q’ 挿入問題は、Bech32に確率2^-10の単純な誤りパターン（「最後から2番目の位置にランダムな文字を挿入する」）が存在することを示す。これは末尾の文字が ‘p’ である必要があり（32通りのうち1通りに限られる）、挿入される文字が ‘q’ である必要がある（挿入されうる32通りの文字のうち1通りしか許されない）ためである。

どの誤りパターンを取るか（どの種類の誤りが、どこで起きるか）は、この確率には含めていないことに注意されたい。人間が起こす誤りの種類には偏りがあり、どの誤りが起きやすいかを容易にモデル化できないため、我々は特定の誤りパターンだけでなく、あらゆるパターンが良好に振る舞うことを目指している。

Bech32mの検出性能

以下の表はBech32mの誤り検出性能を示し、Bech32との比較も行う。この分析に用いたコードはこちら (https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e#file-const_analysis-cpp)にある。各行は左側4列の制約によって1つの誤りパターンを規定する。残りの列は、その制約に該当する誤りパターンのうち、それぞれの確率で検出されなかったものの割合を示す。列の意味は次のとおり。

• errors考慮する個々の誤りの最大数
• of type考慮する誤りの種類（置換のみを考慮する場合は “subst. only”、削除・入れ替え・挿入・重複も含める場合は “any”）
• window誤りが発生しうる範囲の最大サイズ誤りパターンの「windowサイズ」とは何か？ 誤りパターンのwindowサイズとは、変更されたすべての文字（入力・出力のいずれか大きい方）を含む、連続する文字範囲のうち最小のものの長さである。たとえば “abcdef” を “accdbef” に変える誤りパターンは、“bcd” を4文字の “ccdb” に置き換えているためwindowサイズが4になる。windowサイズは誤りが2個以上のパターンにおいてのみ意味を持つ。
• code/verifierこの行がBech32とBech32mのどちらでエンコードされた文字列を扱っているか、またBech32検証器とBech32m検証器のどちらに受理される確率を評価しているかを示すなぜBech32検証器がBech32m文字列を受理してしまう確率を気にするのか？ ウィットネスアドレスのようにBech32mが既存のBech32の用途を置き換えるアプリケーションでは、新しいソフトウェアが生成したBech32m文字列が、Bech32を前提とする古いソフトウェアに誤って受理されないことを確認したい。少数の誤りが混入した場合でも同様である。有効なBech32m文字列に誤りが生じた結果、Bech32検証器に受理されてしまうケースも考慮すべきか？ この状況は理論上、v1以降のアドレスにおいてバージョン番号がv0に変わってしまう誤りが起きた場合にウィットネスアドレスで発生しうる。この種の誤りの特殊性と、v0アドレスに適用される追加の制約とを考えると、これは起こりにくく分析も難しい。
• error patterns with failure probability各確率（0、2^-30、2^-25、2^-20、2^-15、2^-10）について、前の列の制約に該当する誤りパターンのうち、その確率で誤って受理されるものの割合を示す。

これらの性質は2つのクラスに分けられる。あらゆるHRP（human readable part）について平均化したときにすべての文字列に当てはまる性質と、ウィットネスアドレスに課される長さの制約の下で “bc1” というHRPに特有の性質”bc1” 特有の分析ではどのような制約を考慮したか？ ウィットネスプログラムが最低2バイトであることによる最小長、最大40バイトであることによる最大長、ウィットネスプログラムが8ビットの倍数であるという事実である。先頭のデータ記号が16を超えられないことや、パディングが0でなければならないことは考慮していない。である。

すべてのHRPについて平均化した性質

HRP “bc” のウィットネスアドレスに関する性質

この表の数値、および1という定数や過去に提案された改良定数との比較はこちら (https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e#file-results_final-txt)にある。

選定プロセス

選定プロセスの詳細はこちら (https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e)にあるが、要約すると次のとおりである。

• Bech32の1とは異なる2³⁰-1通りの定数すべての集合から出発する。これらはすべて上記の表で ^(a) と印された性質を満たす。
• 網羅的な分析により、^(b) と印された性質選定基準となる性質はどのように選ばれたか？ これらの性質はいずれも、定数が1つも残らなくなる限界まで厳しくしてある。確率をより低く、誤りの数をより多く、windowをより広く要求すれば、候補は残らなくなる。を満たさない定数をすべて棄却する（たとえば、68文字以下のwindowで、2個以下の誤りからなる誤りパターンのどれかを、≥ 2^-20の確率で誤って受理してしまう定数すべて）。この選定により候補は12054個まで絞られる。
• 上記の表で ^(c) と印された性質を満たさない定数をすべて棄却するなぜウィットネスアドレス（HRP “bc1”）向けに特化して最適化するのか？ 汎用HRPに対する我々の分析には限界がある（詳細な説明はこちら (https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e#file-bech32m_mail-txt)の「Technical details」を参照）。まず汎用の用途を優先して最適化し、ウィットネスアドレスについては同点の場合の決め手として最適化する。。これにより候補は79個まで絞られる。
• 最後に、最終的な決め手として、上記の表で ^(d) に該当する誤りクラスの数が最小となる候補を選ぶ。結果として得られる定数はただ1つ、0x2bc830a3である。

脚注

謝辞

コード選定と分析の計算の大半を行い、意見をくれたグレゴリー・マクスウェルに感謝する。 本文書の執筆と編集を助けてくれたマーク・エアハートに感謝する。 既存の送金者との互換性を意図的に破壊するという、本仕様で採用された方針をめぐる議論をしてくれたラスティ・ラッセルおよびbitcoin-devメーリングリストの参加者に感謝する。