ビットコインの新アドレスフォーマット「Bech32」に潜む、深刻なバグ

2019年11月15日 2019年11月15日

こんにちは！フレセッツ株式会社の日向です。気づけばもう11月も半ば、令和元年も残すところあと一ヶ月半といったところですね。だいぶ寒くなってきたので去年使っていた暖房器具《マイニングリグ》を引っ張り出してきたんですが、どうもGPUファンがどれも動作不良で寒い日々を過ごしております。

今回は、ビットコインの新しいアドレスフォーマットである「Bech32」で発見された設計上のバグについてお話しようと思います。

Bech32とは？

ビットコインで長らく使われていた「1」または「3」から始まるアドレスフォーマットは base58(check)と呼ばれるものであり、秘密鍵のエクスポート時などにも使われるなど、広く使われてきました。しかしながら長く使われていくにつれていろいろと不便な点が浮き彫りになってきたため、Segregated Witness (SegWit) の導入と合わせて投入されたのが、今回の題材である「Bech32」です。Bech32 の BIP (Bitcoin Improvement Proposal; ビットコイン版の RFC のようなもの) で挙げられている base58 のデメリットを列挙してみましょう。

base58 を用いると QR コードの英数字モードを使うことができないため、QR コードが大きくなりがち
base58 では大文字も小文字も両方使われていたため、書き留めたり、携帯端末で打ち込んだり、読み上げたりして相手に伝えるのに不便
エラー検出で使われていたダブル SHA256 ハッシュ関数は遅く、またエラー検出が必ずできる数学的な保証がない
多くのエラー検出符号は、文字セットが素数のべき乗のものに対して研究されており、base58 は文字セットが 58 文字なためそれらの研究が適用できない
Base58 のデコードは複雑で、比較的遅い

一方で Bech32 は英数字から「1」「b」「i」「o」という文字を除いた 32 文字の文字セットで構成されており、BCH符号と呼ばれるエラー訂正符号を用いています。これにより、伝達しやすく、また文字の写し間違いや文字のスワップなどのエラーを数学的に保証された確率でエラーを検出できます。

当初は SegWit 用に発明されたエンコード方式ではあるものの、Lightning Network のインボイスデータのエンコードフォーマットに用いられるなど、利用シーンは広まっています。

深刻なバグ

そんな中で2019年5月頃に GitHub のこちらのイシューにて報告されたのが今回紹介するバグです。その内容をかいつまんで見てみましょう。

概要

特定の Bech32 文字列に対して、単一の文字を削除または挿入を行っても、有効な文字列となってしまう。

バグが発現するケース

主に二つの場合がある：

挿入：Bech32 として有効な文字列が「p」で終了していた場合、文字「q」を「p」の前に挿入しても、Bech32 として有効な文字列となってしまう。
削除：Bech32 として有効な文字列が「qp」で終了していた場合、文字「q」を削除しても、Bech32 として有効な文字列となってしまう。

これらの発現ルールを繰り返し適用すると、文字「q」を複数削除または挿入したとしても、有効な Bech32 文字列となってしまう。

例

Bech32 として有効な文字列「ii2134hk2xmat79tp」に対して、以下の文字列はすべて Bech32 として有効。

ii2134hk2xmat79tqp
ii2134hk2xmat79tqqp
ii2134hk2xmat79tqqqp
ii2134hk2xmat79tqqqqp

また同様に、以下の文字列もすべて Bech32 として有効。

eyg5bsz1l2mrq5ypl40hqqqp
eyg5bsz1l2mrq5ypl40hqqp
eyg5bsz1l2mrq5ypl40hqp
eyg5bsz1l2mrq5ypl40hp

バグの原因となった設計上の問題

なぜこのようなバグが生じてしまったのでしょうか？それを理解するには Bech32 で用いられている BCH 符号の設計思想を振り返ってみる必要があります。

BCH 符号を含む、多くのエラー検出／訂正符号では、文字が他の文字に置き換わってしまったり、また転写ミスなどで隣同士の文字が入れ替わってしまったりといったケースを主に想定しています。ここで問題なのが文字が追加されてしまったり、削除されてしまったりといったケースが考慮されていない、ということです。そのため、今回発見されたバグのように文字列が追加または削除されてしまった場合のエラー検出や訂正については数学的な保証が全くありません！

「なんでそんな単純な単純なことを見落としてたんだ！いったい情報科学者は一体何をやっているんだ！」というお叱りの声（？）が聞こえてきそうですね……。そこで少しだけ弁明（？）させてください。

エラー検出／訂正符号の主な利用シーンはノイズのある通信路を使ってデータの送受信をする、というのを想定しています。例えば無線通信などは自然界や他の機器から発せられる様々な電波がノイズとして入ってきてしまいますし、有線接続でもやはり電流に熱雑音や外界からの誘導電流などが流れてきてしまいます。そういった様々なノイズが混入してきてしまっても、エラーを確実に検知し（できればエラーを訂正し）、正常なデータを受信できるようにする、というのが BCH 符号を含む多くの符号化理論の達成目標となっております。ですので、データビットが増えたり減ったりするという状況は一般的には想定しづらく、BCH 符号ではそれは全く考慮されていなかった、というのが結論です。

バグの影響

最後に、このバグがもたらす実害を考えてみましょう。

まず、SegWit アドレスについては、もしこのバグを踏んでしまったとしても、データのバイト長が20バイト（P2WPKH、シングルシグ）または32バイト（P2WSH、マルチシグなど）ではなかった場合にエラーとなるようにすれば回避できるでしょう。

一方で、データのバイト長が決まっていない Lightning Network のインボイスや、現在実装に向けて議論されている Taproot などについては、単純なバイト長の検査などではエラーを検出することができず、実際にペイロードデータを解析する段階にならないと不具合を検出できません。場合によっては「q」を挿入または削除した後のデータがそうした解析段階でもエラーにならずに処理が進んでしまい、（セルフ）Gox したり anyone-can-spend なトランザクションができてしまう可能性があるでしょう。

実際、このバグ自体は2019年5月頃から認識されていたものの、Taproot の実装が最終段階に近づいてきた今頃（2019年11月）になって、このバグに対する議論が再燃してきているようです。今後何らかの形で修正ないし新しいアドレスフォーマットの議論などが起きてくることと思います。今後の議論に注目ですね。