ニュース

ブロックチェーン講座その1[ビザンチン将軍問題]

ブロックチェーン講座その1[ビザンチン将軍問題]

2018年09月09日

 

 

ブロックチェーン、分散型台帳、PBFT、コンセンサスアルゴリズム、これらを調べると必ずこの単語にたどり着くと思います。「ビザンチン将軍問題」。

 

じゃあこのビザンチン将軍問題、何なのかと調べると、ビザンチン将軍都市攻撃計画がどうだの、そんな話ばかりでイマイチ分かりにくい。私達は言葉の意味とそのイメージが知りたいわけで、ビザンチン将軍の都市攻撃が成功するかどうかなんていうのはどうでも良いのです。

そこで、そんな話は一切せずに、分散型台帳におけるビザンチン将軍問題とは何なのかを簡単に説明してみたいと思います。

「ブロックチェーン聞いたことあるし何となく知ってるけど正直よくわからん」というエンジニアが理解できれば良いな程度の感覚で書きます。

 

タナカ氏の送金

下記図のような分散型台帳ネットワークがあるとします。

このネットワークでは不正をさせないように下記のルールがあるとします。

  • トランザクション(送金申請)には本人を証明する署名が必要
  • 残高不足であればそのトランザクションは却下

ここがスタート地点です。

あるとき、口座残高に10yen持っているタナカさんが、

  1. タナカからサトウに10yen送る
  2. タナカからナカモトに10yen送る

という2つのトランザクションを、それぞれ別のサーバーに投げたとします。下記図の状態です。

トランザクションはノードのバケツリレーによってどんどんネットワークに広がっていきます。

ここで、ある時困ったことが起きます。

上記図の真ん中の緑色のノードたちは混乱します。何故なら「AもBも正真正銘タナカさんの署名があるが、両方受け入れるには残高が足りない」からです。

この混乱がビザンチン将軍問題です。

一応続きを書きます。

混乱はネットワーク全体に広がってゆきます。

さて、どうしましょうか。

解決法 1 : 時間優先

「後から来たやつ無視すればいいぢゃん。」

はい、それ採用。やってみましょう。

はい、見事に台帳が2種類に分裂しました。これではまずい・・・

解決法 2 : 天の声に従う

混乱したネットワークに1週間後、天の声が響いたとします。「Aを受け入れよ…」

はい。解決しました。

ように見えますが、これを扱っている人間は大混乱です。なぜならBを信じて運用していた人たちの帳簿履歴が一部完全に変わってしまうからです。

帳簿は口座への出入金の記録の連鎖で出来ています。ある点のトランザクションがなかったことになると、その後それによって帳尻があっていた部分が合わなくなってしまいます。そしてその影響は、時間が経てば立つほど大きくなっていきます。

10秒前の記録が消えるぐらいならレジの前で待てば良いけれど、1週間分とか変わられると使いものにならない。(待ってられない)やっぱりこれでもマズイわけです。

ブロックチェーンはどうなっているの?

これを書き出すと今回説明したい範囲からそれるので書きませんが、いくつか追加でルールを設けて、「確率的に言ってまず間違いなくこれが正しいはず!」といえるようにしています。

で、実は「解決法? 2 : 天の声に従う」で問題視していたトランザクションがなかったことになる問題は、ブロックチェーンは完全に解決しておらず、30分前まではこれで良いとされていたトランザクションが無効になる程度のことは度々起きています。これは reorg と呼ばれます。

reorgに関しては、「まぁまぁ私達が考える仮定に沿って動いていればそんな長い期間の履歴がひっくり返ることないっしょ」という感じで受け入れられているものです。(だから取引所はビットコインなどの入金にどうしても承認時間が必要なんですよね)