ビットコイン・インスティテュート

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 される定数 10x2bc830a3 に置き換える。得られるチェックサムの検証・生成アルゴリズムは次のとおり(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 進数で示したものである。

  • BC1QW508D6QEJXTDG4Y5R3ZARVARY0C5XW7KV8F3T40014751e76e8199196d454941c45d1b3a323f1433bd6
  • tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sl5k700201863143c14c5166804bd19203356da136c985678cd4d27a1b8c6329604903262
  • bc1pw508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7kt5nd6y5128751e76e8199196d454941c45d1b3a323f1433bd6751e76e8199196d454941c45d1b3a323f1433bd6
  • BC1SW50QGDZ25J6002751e
  • bc1zw508d6qejxtdg4y5r3zarvaryvaxxpcs5210751e76e8199196d454941c45d1b3a323
  • tb1qqqqqp399et2xygdj5xreqhjjvcmzhxw4aywxecjdzew6hylgvsesrxh6hy0020000000c4a5cad46221b2a187905e5266362b99d5e91c6ce24d165dab93e86433
  • tb1pqqqqp399et2xygdj5xreqhjjvcmzhxw4aywxecjdzew6hylgvsesf3hn0c5120000000c4a5cad46221b2a187905e5266362b99d5e91c6ce24d165dab93e86433
  • bc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vqzk5jj0512079be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

以下は無効な 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 各確率(02-302-252-202-152-10)について、前の列の制約に該当する誤りパターンのうち、その確率で誤って受理されるものの割合を示す。

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

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

errorsof typewindowcode/verifier02-302-252-202-152-10
≤ 4subst. のみanyBech32m/Bech32m100.00%なし(a)なし(a)なし(a)なし(a)なし(a)
anyany≤ 4Bech32m/Bech32m56.16%43.84%なし(b)なし(b)なし(b)なし(b)
≤ 2any≤ 68Bech32m/Bech32m7.71%92.28%なし(b)なし(b)なし(b)なし(b)
≤ 2anyanyBech32m/Bech32m7.79%92.20%0.004%なし(b)なし(b)なし(b)
≤ 3any≤ 69Bech32m/Bech32m7.73%92.23%0.033%(d)なし(b)なし(b)なし(b)
≤ 3anyanyBech32m/Bech32m7.77%92.19%0.034%0.000065%なし(b)なし(b)
≤ 4subst. のみanyBech32/Bech32100.00%なしなしなしなしなし
anyany≤ 4Bech32/Bech3254.00%43.84%1.08%0.90%0.17%0.0091%
≤ 2any≤ 68Bech32/Bech324.59%92.29%1.09%1.01%0.99%0.039%
≤ 2anyanyBech32/Bech324.58%92.21%1.11%1.04%1.02%0.038%
≤ 3any≤ 69Bech32/Bech326.69%92.23%0.56%0.48%0.041%0.00055%
≤ 3anyanyBech32/Bech326.66%92.19%0.59%0.52%0.041%0.00053%
0--Bech32m/Bech32100.00%なし(a)なし(a)なし(a)なし(a)なし(a)
1any-Bech32m/Bech3246.53%53.46%なし(b)なし(b)なし(b)なし(b)
≤ 2anyanyBech32m/Bech3222.18%77.77%0.048%なし(b)なし(b)なし(b)

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

errorsof typewindowcode/verifier02-302-252-202-152-10
≤ 4subst. のみanyBech32m/Bech32m100.00%なし(a)なし(a)なし(a)なし(a)なし(a)
1any-Bech32m/Bech32m24.34%75.66%なし(c)なし(c)なし(c)なし(c)
≤ 2any≤ 28Bech32m/Bech32m16.85%83.15%なし(c)なし(c)なし(c)なし(c)
anyany≤ 4Bech32m/Bech32m74.74%25.25%0.0016%なし(c)なし(c)なし(c)
≤ 2anyanyBech32m/Bech32m15.72%84.23%0.039%0.0053%なし(c)なし(c)
≤ 3anyanyBech32m/Bech32m13.98%85.94%0.078%0.00063%なし(c)なし(c)
≤ 4subst. のみanyBech32/Bech32100.00%なしなしなしなしなし
1any-Bech32/Bech3214.63%75.71%2.43%2.43%2.43%2.38%
≤ 2any≤ 28Bech32/Bech3214.22%83.15%0.94%0.84%0.79%0.054%
anyany≤ 4Bech32/Bech3273.23%25.26%0.76%0.63%0.12%0.0064%
≤ 2anyanyBech32/Bech3212.79%84.24%1.06%0.95%0.92%0.041%
≤ 3anyanyBech32/Bech3213.00%85.94%0.57%0.45%0.044%0.00067%
≤ 3subst. のみanyBech32m/Bech32100.00%なし(c)なし(c)なし(c)なし(c)なし(c)
1any-Bech32m/Bech3270.89%29.11%なし(c)なし(c)なし(c)なし(c)
≤ 2anyanyBech32m/Bech3236.12%63.79%0.092%0.00049%なし(c)なし(c)

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

選定プロセス

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

  • Bech32 の 1 とは異なる 230-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 である。

脚注

謝辞

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