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

Masahiko Hyuga
Nov 15, 2019 · 8 min read

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

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

Image for post
Image for post
Bech32の換字テーブル

Bech32とは?

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

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

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

深刻なバグ

概要

バグが発現するケース

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

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

  • ii2134hk2xmat79tqp
  • ii2134hk2xmat79tqqp
  • ii2134hk2xmat79tqqqp
  • ii2134hk2xmat79tqqqqp

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

  • eyg5bsz1l2mrq5ypl40hqqqp
  • eyg5bsz1l2mrq5ypl40hqqp
  • eyg5bsz1l2mrq5ypl40hqp
  • eyg5bsz1l2mrq5ypl40hp

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

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

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

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

バグの影響

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

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

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

fressetsお知らせ

HashHubお知らせ

Wantedly:https://www.wantedly.com/companies/hashhub/projects

■HashHubでは入居者募集中です!
HashHubは、ブロックチェーン業界で働いている人のためのコワーキングスペースを運営しています。ご利用をご検討の方は、下記のWEBサイトからお問い合わせください。また、最新情報はTwitterで発信中です。

HashHub:https://hashhub.tokyo/
Twitter:https://twitter.com/HashHub_Tokyo

GBEC Tech Blog

This Blog is for all Blockchain Engineer

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store