SaaSベンチャーで働くエンタープライズ部長のブログ

SaaSベンチャーでエンジニア→プロダクトマネージャー→エンタープライズ部長として働いています。

いまさらビザンチン将軍問題

いまさらながらビザンチン将軍問題を整理し、proof-of-workとどのように絡んでいるかを書いてみました。派生系の問題なども色々ありますが、起源となった問題をまとめています。

ビザンチン将軍問題とは

ビザンチン将軍問題とはLamportが1982年に提唱した問題です。

Lamportの論文「The Byzantine Generals Problem」

https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf

分散型コンピュータのうち、どの程度が障害を起こしても正常に動作するかをテーマに比喩的に論文に書いています。ビザンチン帝国の師団が分割されて存在しており、各師団は将軍が率いていますが、裏切り者の将軍がいくらか紛れています。

論文には2つの条件が書かれています。

f:id:naomasabit:20190416224306p:plain

IC1. All loyal lieutenants obey the same order.

IC2. If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.

IC1. 忠実な将軍は同じ命令に従う

IC2. 指揮官が忠実であれば、忠実な将軍は彼の命令に従う。

という条件の時、どのような条件であれば正しく行動計画が伝わるかを考える問題がビザンチン将軍問題です。

この時に、以下の2つを達成するための条件(アルゴリズム)を考えます。

f:id:naomasabit:20190416224319p:plain

f:id:naomasabit:20190416224324p:plain

A.すべての忠実な将軍は同じ行動計画を決定する

B.少数の裏切り者が、忠実な将軍たちに悪い計画を採用させることはできない

Lamportの解法 - Oral Messageアルゴリズム

Lamportは、3分の2より多くの将軍が忠実であるときに合意形成が可能であるOral Message(口伝)アルゴリズムを提唱しています。

前提条件

We let RETREAT be this default order.

RETREAT(撤退)はデフォルトの命令とする

OM(0)の時

Algorithm OM(0).

(1) The commander sends his value to every lieutenant.

(2) Each lieutenant uses the value he receives from the commander, or uses the value RETREAT if he receives no value.

  1. 指揮官は各将軍に命令を送る

  2. 各将軍は指揮官から受け取った命令を使う。もし何も受け取らなかった場合はデフォルトのRETREAT命令を用いる

こちらはシンプルだと思います。

OM(m)の時, m > Oの時

Algorithm OM(m), m > O.

(1) The commander sends his value to every lieutenant.

(2) For each i, let vi be the value Lieutenant i receives from the commander, or else be RETREAT if he re :eives no value. Lieutenant i acts as the commander in Algorithm OM(m - 1) to send the value vi to each of the n - 2 other lieutenants.

(3) For each i, and each j ~ i, let vj be the value Lieutenant i received from Lieutenant j in step (2) (using Algorithm OM(m - 1)), or else RETREAT if he received no such value. Lieutenant i uses the value majority (vl . . . . . v,-1 ).

  1. 指揮官は各将軍に命令を送る

  2. 各将軍iが受け取った命令をViとおく。もし何も受け取らなかった場合はデフォルトのRETREAT命令を用いる。各将軍はOM(m-1)アルゴリズムを使って自分と指揮官以外の将軍に命令を送る。

  3. 各将軍iがステップ2で他の将軍jから受け取った命令について、Vjとおく。(何も受け取らなかったらデフォルトの撤退命令)将軍iは他の将軍から受け取った命令のうち、マジョリティの命令を採用する

少し複雑になってきており、論文内でも例が示されています。 例えば、m=1(裏切り者が1)、n=4(全将軍が4)の時を考えます。Lamportの論文には、指揮官が忠実であり、将軍L3が裏切り者だった場合の図が乗っています。

f:id:naomasabit:20190416224635p:plain

まず、指揮官が命令vを送り、各将軍は同一の命令vを受け取ります。(ステップ1)

将軍L1,L2は指揮官からの命令を他の将軍に送り、将軍L3はL2に別の命令xを送ります。(ステップ2)

L2はL3から命令xを受け取るが、L1と指揮官から受けた命令であるvをマジョリティであるため採用します。(ステップ3)

Lamportは、裏切り者がm人のとき、忠実な将軍が2m+1人以上、全体で3m+1人以上のとき、忠実な将軍同士で合意に至ることが可能としています。

これはビザンチン帝国の戦いの話ですが、忠実な将軍は正常なプロセス、裏切り者は障害のプロセスとして置き換えると、分散システムの話として置き換えられます。

ビザンチン将軍問題はこの裏切り者の数の制約、そして他の参加者の伝達内容を知る必要があるという制約を示しています。

ビザンチン将軍問題とproof-of-workに関するSatoshiとJamesのメールやりとり

ここからは、これまでの話を前提として、この話とproof-of-workと絡めたSatoshiのメールのやり取りをのぞいてみます。

James A. Donald wrote:

It is not sufficient that everyone knows X. We also

need everyone to know that everyone knows X, and that

everyone knows that everyone knows that everyone knows X

  • which, as in the Byzantine Generals problem, is the

classic hard problem of distributed data processing.

James A. Donaldは各参加者が答えXを持っているだけでは十分ではなく、他の参加者が答えを知っていることが重要だと言っており、ビザンチン将軍問題として告げています。

Lamportの提唱は

・裏切り者をm以下に抑える必要がある

・他の将軍全てがどのような命令を受けているかを知る必要がある

という制限を示唆していま須賀、Jamesは2番目の「他の将軍全てがどのような命令を受けているかを知る必要がある」の制限について触れていると考えられます。

The proof-of-work chain is a solution to the Byzantine Generals' Problem. I'll try to rephrase it in that context.

A number of Byzantine Generals each have a computer and want to attack the King's wi-fi by brute forcing the password, which they've learned is a certain number of characters in length.

対して、SatoshiはPoWチェーンがビザンチン将軍問題の解になると言っています。ビザンチン帝国の将軍たちがコンピューターを持って、ブルートフォースアタック(総当たり攻撃)でパスワードをクラックするシチュエーションと読み替えています。

They don't particularly care when the attack will be, just that they all agree. It has been decided that anyone who feels like it will announce a time, and whatever time is heard first will be the official attack time. The problem is that the network is not instantaneous, and if two generals announce different attack times at close to the same time, some may hear one first and others hear the other first.

いつ攻撃を行うかは気にする必要はないものの、ほぼ同時に攻撃を行った場合、近くの将軍が一方の攻撃時間をきき、別の将軍はもう一方の攻撃時間をきくことがあり得ます。この場合、どちらが正しいかを決めるロジックが必要になります。

They use a proof-of-work chain to solve the problem. Once each general receives whatever attack time he hears first, he sets his computer to solve an extremely difficult proof-of-work problem that includes the attack time in its hash. The proof-of-work is so difficult, it's expected to take 10 minutes of them all working at once before one of them finds a solution. Once one of the generals finds a proof-of-work, he broadcasts it to the network, and everyone changes their current proof-of-work computation to include that proof-of-work in the hash they're working on. If anyone was working on a different attack time, they switch to this one, because its proof-of-work chain is now longer.

Satoshiはproof-of-workチェーンがこの問題の解決策になると続けています。各将軍は攻撃時間を聞いたら、攻撃時間もハッシュの材料に含めて、チェーンを連鎖させていきます。proof-of-workは将軍が問題解決までに10分程度かかりますが、解き終わったら他の将軍に伝えます。他の将軍が別の攻撃時間を聞いて、長い方のチェーンを見つけたらそちらにブロックをつなげるため問題を解いていきます。

これはブロックチェーンのマイニングの仕組みを比喩で表しています。長い方のチェーンを正しいとみなすとしています。

Satoshiの返答は、「他の将軍全てがどのような命令を受けているかを知る必要がある」というビザンチン将軍問題の制約について、先に答えを出してしまう(マイニングしてブロックを生成する)事で避けているように見えます。長い方のチェーンを正しいとみなす事で、後から正しさを決定するとしています。

裏切り者をm以下に抑える、という点についてはBitcoinホワイトペーパーの中で、不正者がいた場合にブロックが覆る確率を出力しています。

f:id:naomasabit:20190416225504p:plain

proof-of-workによる効果

proof-of-workを採用する事で、チェーンをつないで共有し、まずその時点での合意を伝えるというアプローチをとることができました。

ビザンチン将軍問題における、他の将軍全てがどのような命令を受けているかを知る必要がある、という制約については合意に至る前に各自が 受け取った命令を共有するという制約を逃れました。

一方で裏切り者を抑える、という点については不正者がいた場合にブロックが覆る確率は依然示されています。

最後に、JBA日本ブロックチェーン協会)のブロックチェーンの定義を紹介しておきます。

1)「ビザンチン障害を含む不特定多数のノードを用い、時間の経過とともにその時点の合意が覆る確率が0へ収束するプロトコル、またはその実装をブロックチェーンと呼ぶ。」

1) A blockchain is defined as a protocol, or implementation of a protocol, used by an unspecified number of nodes containing Byzantine faults, and converges the probability of consensus reversion with the passage of time to zero.

2)「電子署名とハッシュポインタを使用し改竄検出が容易なデータ構造を持ち、且つ、当該データをネットワーク上に分散する多数のノードに保持させることで、高可用性及びデータ同一性等を実現する技術を広義のブロックチェーンと呼ぶ。」

2) In a broader sense, a blockchain is a technology with a data structure which can easily detect manipulation using digital signatures and hash pointers, and where the data has high availability and integrity due to distribution across multiple nodes on a network.