読者です 読者をやめる 読者になる 読者になる

bitcoin と ビザンチン将軍問題

計算機 考察 ノート マンガ

bitcoinビザンチン将軍問題を解決したとしばしば言われます。これが厳密には誤りだそうです。私もそんなに詳しくないのだけれども、確かにそうかなと思います。

ビザンチン将軍問題というのは――離れた場所にいる複数の将軍間で作戦の合意をとりたい;ただし将軍の中に裏切り者がいたり、伝令が失踪したり遅れたりする可能性がある――という問題です。

bitcoin がこれを解決したと言われるのは、悪意のある参加者が過半数以下の場合は帳簿が改竄できないようになっていて、参加者が帳簿を共有しているので、bitcoin では帳簿の内容について合意がとれているように見えるからでしょう。

しかし、上でいう「合意」というのは「分散システムにおける合意」(以下 consensus とする)とは全く別物です。例えば、bitcoin には最も長いブロックチェーンを参加者がみんな知っている、つまり consensus がとれている、という保証はどこにもないはずです。*1だから、bitcoinビザンチン将軍問題をちゃんと解決したわけではない。

でも、bitcoin は現実に動いているので、何かの問題は解決している。それは一体何なのだろうというのが私の疑問です。bitcoin は別にビザンチン将軍問題を解決したわけではない――と批判するのは簡単なんですが、それよりも問題の方をもう一度定式し直した方がいいのではと思うわけです。ビザンチン将軍問題は、おそらくもう解決できないし、現実に即してないので、もはや悩むだけ無駄かと。この辺をちゃんと考えた人いるのかな?

bitcoin が、別にビザンチン将軍問題を解決したわけでもないのに、悪意のある参加者がいる状況で実用的には正しい帳簿を共有できているのはなんでだろうと考えると、おそらく bitcoin は PoW によって CPU ネックになっていて、相対的にネットワークがすごく速くなっているからだと予想する。bitcoin のブロックチェーンにひとつのブロックが追加されるのに10分を要するのは、確かに遅い。しかし、インターネットみたいな不安定な通信網の上で、どんなマシンもネットワークに参加していいという条件下で、世界中に情報が伝播することがだいたい確信できるであろう時間を考えると、そこまで変な値ではないように思う。つまり、10分ぐらい待てば、consensus を保証しなくても、ほとんどのノードには情報が伝わったことを期待してもよかろうということだ。10秒では短すぎる。この辺のさじ加減も bitcoin というのはようできてる。あぶない橋を渡っている気はするが……。

詳しくないけど、ビザンチン将軍問題を解決しようとしたときに最も難しいのは、通信だろう。遅延や欠損なんて無視できるレベルで小さい、完全な通信があれば、ビザンチン将軍問題は解決できそうだ。*2ドリフターズ』という漫画で、織田信長が無線通信装置(のようなもの)を見た時に、遠隔地にある部隊をリアルタイムで連携できるとその可能性を見出していた。これがおそらく答えで、現実に将軍がいて合意をとりたいという、実地のビザンチン将軍問題が仮にあったら、それは無線通信があれば概ね解決できるように思う。

だから、bitcoin というのはビザンチン将軍問題を解いたわけではなくて、それを解決せずに済むような条件を絶妙なバランスで作っているから上手いこと動いているのではないかというのが、今のところの仮説です。

*1:実装までは把握していないのでこれは推測です。ゴシッププロトコルか緊急連絡網方式か、何かしらの方法で最新のブロックが追加されたことを広報しているだけで、それが確実に全体に伝わっているかは保証していないはず。10分ごとにそれをするのは不可能だと思う。

*2:いくらかの制限は要りそう。そういう条件下での解法は誰かがもう証明しているにちがいない。詳しくないので知らん。