United Statesからアクセスのようです。言語設定をEnglishに切り替えますか?
Switch to English site
Skip to main content

ブロックチェーン入門 - パート3 「ビザンチン将軍問題」

BlockChainPart3-Smaller_aa3cfa62860f3575b0be1db7efcf6af8aba79a49.jpg

前回パート2の入門編で、パブリックブロックチェーンのような分散型P2P(ピア・ツー・ピア)システムの効果的な運用には、「データ追加」と「履歴修正」の両方について、合意形成の必要があることについて説明した。一見簡単そうに見えるが、実際には何千というノードが対象となるため、合意形成は想像以上に複雑なものになる。

この問題を扱った論文の中で、1982年にLeslie Lamport・Robert Shostak・Marshall Peaseの3人が発表した「ビザンチン将軍問題」(The Byzantine Generals Problem )という思考実験のレポートが面白い。学術論文ではあるが分かりやすく、一読の価値がある。

2zcek9_69fe9bd7f5861bbcd1d8628d5f3edc7e3c0c854e.jpg

ビザンチン将軍問題

複数の当事者が将来の行動について合意を形成する必要があるという状況を考える。たとえば、かつての東ローマ帝国の複数の将軍たちが、反乱都市を包囲している状況を思い浮かべてみよう。ただし将軍の中には裏切者がいる可能性もある。各将軍は複数の部隊で構成された軍隊とともに各々の基地おり、基地間の通信は開けた土地(危険のある土地)を越えていくメッセンジャーによってのみ可能とする。

いま包囲している都市は、全部隊で攻撃すれば勝利することができる。1部隊でも欠けた状態で攻撃すれば、敗退してしまう。またもう一つ、戦力を維持するために、攻撃を行なわず全部隊一緒に撤退するという選択肢もある。

この判断を行なうために各将軍が送らなければならないメッセージについて、先述の論文は、本問題の最も簡単な形は1名の指揮官と2名の将軍の場合だとしている。論文に示された条件は次のとおりだ。

[ビザンチン将軍問題] 1人の指揮官(Commander)はn-1人の将軍(Lieutenant)に指令を送る必要があり、次の条件があるとする。

条件1. 忠実な将軍は全員同じ指令に従う。
条件2. 指揮官が忠実であれば、すべての忠実な将軍は指揮官の送る指令に従う。

とても単純に見えるが、将軍たちが公開された(又は口頭の)メッセージを使用する場合、2/3を超える将軍が忠実でなければ、合意に達することはできない。言い換えると、3人の将軍のうち1人の裏切者がいる場合、合意は形成されず一部の部隊のみが攻撃を仕掛けることになり、結果は敗退となる。以上の状況は、次の2つの図で示すことができる。

generals_8624b21fd1a2242b96b3ee58f856edfddb73a5d2.png

図1では、指揮官(Commander)が両方の将軍(Lieutenant)に攻撃(Attack)するよう指令を送っている。将軍2は裏切者(Traintor)で、将軍1に撤退(Retreat)の指令を受けたというメッセージを送る。条件2より、将軍1は攻撃の指令に従う。

ところが、図2では、指揮官が裏切者で、将軍1には攻撃命令を、将軍2には撤退の指令を送っている。裏切者が誰かを知らない、あるいは将軍2に送られたメッセージの内容を知らない将軍1は、図1で受け取った情報と全く同じ情報を受け取っている。裏切者が一貫した嘘をつく限り、将軍1は常に攻撃をしなければならない。

論文では、人数が3m + 1未満のとき、m人の裏切者がいると合意形成が不可能となることが数学的に証明されている。つまり、裏切者が1/3未満であれば合意に達することができるということだ。

裏切り者の偽情報を防ぐ

図1と図2を見ると、裏切者が嘘をつく能力こそビザンチン将軍問題の核心であることが分かるだろう。嘘をつく能力を制限できれば、合意形成は容易となる。そのためには、偽造できない署名付きでメッセージを送るようにすればいい。この例では次のように仮定する。

A1. 送られるメッセージはすべて正確に届けられる
A2. メッセージの受信者は、送信者が誰かを知っている
A3. メッセージの不在は検出できる

これらの前提は前述の「口頭メッセージ」の例にも当てはまるが、ここでは次の仮定を追加する。

A4. (a) 忠実な指揮官 / 将軍の署名は偽造できず、署名済みメッセージの内容の改ざんは検出可能である。
       (b) 指揮官 / 将軍の署名が本物であることは誰でも検証できる。

このシナリオでは、指揮官がそれぞれの将軍に署名済み指令を送る。将軍も指令に各自の署名を付け加えてからもう一人の将軍に送る。このアルゴリズムを前回のシナリオに当てはめると次の図のようになる。

generals2_7f3c39063960e91901f1db2c46a472854b8662a1.png

指揮官は指令に「0」と署名する。それぞれの将軍は受け取った指令に署名してもう一人の将軍に送る。この場合将軍は、指揮官が裏切者であることを知るだろう。2つの相反する指令に指揮官の署名があり、仮定A4より指揮官が署名を作成したと分かるからだ。

論文では、このアルゴリズムによって任意の人数の将軍に対するm名の裏切者に対応できるという事実と、さらに通信経路が失われた場合など他のシナリオでこれがどのように機能するかという点について数学的証明を示している。これについては「入門」記事の範疇を超えているので割愛する。とりあえず、ここまで読んでくれた方には、ブロックチェーンの合意形成方法の基礎として、暗号化を使って署名を作成するアルゴリズムが何故採用されたかを分かってもらえたと思う。

オーファン、アンクル、ステイル化

ブロックチェーンネットワークのマイナー(採掘者)は誰もが現在のブロックの暗号パズルを最初に解読しようとしている、ということを覚えているだろうか?解読したマイナーはそのソリューションを検証のためネットワークに送信する。すべて問題はないと想定して、マイナーは次のブロックに取り掛かる。

ではもし2人のマイナーが同じブロックを同時に解読したらどうなるのだろう?データがすべてのノードを通過するには時間がかかるため、すべての分散型ネットワークにはレイテンシがある。このレイテンシは数ミリ秒から数秒にもなるため、2人の別のマイナーが多数のノードによってブロックの検証を受け、チェーンに追加することもありえるということだ。

ここでブロックチェーンにフォーク(分岐)ができ、2つの別のチェーンとして成長する。どちらも有効であるため、この問題を解決する間もマイニングは停止できない。これがブロックチェーンの問題であり、映画「ハイランダー」のように本物は1つだけでなければならないのだ。

それぞれのブロックチェーンは独自のアプローチでこのジレンマを解消している。ここでは、最も普及しているビットコインとイーサリアムがどのように安定した状態に戻っているのかを見ていこう。

ビットコイン

マイナーXとマイナーYがどちらもブロック番号1001を解読した、という状況を考えてみよう。ネットワークレイテンシが低いため、マイナーXは、新しいブロックをビットコインネットワークの60%に渡したとする。またマイナーYは、ブロックを残りの40%に渡したとする。この時点では、どちらのブロックも有効とみなされ、マイニングが続行される。

マイナーXのブロックを引き受けたマイニングノードは、マイナーXのブロックの次のブロックを追加するためマイニングしており、マイナーYのブロックを引き受けたノードはYのチェーンに追加するためにマイニングする。

orphan01_1e0ffc3465b73dac334344d6da92837511ecb5bd.png

ここで下図のように、Xのチェーンに追加しているマイナーがブロックを1つ追加し、Yのチェーンに追加するマイナーがブロックを2つ追加した場合を考える。ブロックチェーンは、最長のチェーンが正当なチェーンとみなされるので、Xのチェーンをマイニングしているノードのほうが多いにも関わらず、利益を得て真のチェーンとして認められるのは、長いYのチェーンの方となる。

orphan02_c4291633e08e4a07520244efe163b91e85c3ae24.png

Xのブロック番号1001はチェーンから切り離され親ブロックがない状態のままになる。この孤立したブロックを、「オーファン(孤立)ブロック」と呼ぶ。Xのマイナーは発掘した追加ブロックに対する報酬を得ることはできず、そのブロックはステイル(陳腐化)ブロックになる。

なお以上の例は、オーファンブロックの理解を助けるための、極端な例となっている。実際は、ブロック番号1002が採掘された時点で、ネットワークは正当なチェーンの判断を行ない、もう一つのチェーンを孤立させる。

ところでオーファンブロックに入ってしまった取引はどうなるのだろうか。そうした取引は自動的に最長の正当なブロックチェーンに戻り、次のブロックに追加されるのを待つこととなる。

イーサリアム

イーサリアムはこの問題についてやや異なるアプローチを取っている。GHOST (Greedy Heaviest Observed Subtree)プロトコルという形式で、ビットコイン内のオーファンブロックやステイルブロックになりそうなものを見つけたマイナーに報酬を与えている。イーサリアムではこれをアンクルブロックと呼び、メインのブロックチェーンには追加されませんが、マイナーは報酬を受ける。ただし、チェーンに追加される標準ブロックよりも報酬は低い。

イーサリアムはアンクルブロックに7つのレベルを設定している。1つはビットコインのオーファンブロックに、残り6つはステイルブロックに相当する。報酬は次の式で算出される。

([アンクルブロック数] + 8 – [ブロック数]) x ([イーサリアムの報酬] /8)

よって、標準ブロックに対する報酬が3 ETHである場合、最初のアンクルブロックの報酬は2.625 ETH、次のブロックは2.25 ETH、その次は1.87 ETHとなる。ここでもマイナーノードは、1つ(最大でも2つ)ブロック後のアンクルチェーンを破棄する。

今後の展望

ブロックチェーンは開発途上の技術であり、この技術の最も有益な用途は、ブロックチェーンが幻滅期に入ってしばらくした後に明らかになると私は考える。またおそらく、真に有用なものとなるには基盤技術の根本的な発展が必要だろう。

思うにブロックチェーンは、1973年にMotorolaに勤めていたMartin Cooperが特許申請した「無線電話システム」と同じような進化の過程をたどるのではないだろうか。Cooperは同年、初の携帯電話での通話を成功させた。一方でこの技術が普及したのは、1990年代半ばにデジタルGSMネットワーク(これにより低電力かつ低価格の端末が実現し、高効率な伝送帯域幅の使用により広いセルカバレッジが実現した)が公開されてからのことだった。それ以降、無線電話システムは次々に新しい機能を持つようになり、目覚ましい進化をとげた。

同様に、ブロックチェーンにも克服が必要な限界がいくつかある。たとえば、ビットコインのブロックチェーンは1秒当たり7トランザクションしか処理できず、1つのブロックをマイニングするには平均で10分かかる。1日に数百万件のトランザクションを処理する金融機関にとって、これは大きな問題である。加えて、1つのブロックに追加された1つのトランザクションには、米国の平均的家庭が24時間に消費するエネルギーの1.6倍ものエネルギーが必要となる。さらに、チェーンのサイズは25GBを超え現在も増え続けているため、個人用デバイスではますます処理が難しくなっている。

一方、研究には多額の資金が流入しており、Global Blockchain Business Council (GBBC)のような団体はブロックチェーンの新たな用途の開発を積極的に進め、Hyperledger Projectはオープンスタンダードを策定して異業種間相互運用性を実現しようとしている。IBMはSamsungと共同で、ブロックチェーン技術を利用したADEPT (Autonomous Decentralized Peer-to-Peer Telemetry: 自律分散型ピアツーピアテレメトリ)を開発し、分散型IoTエコシステム内の自律型デバイスの分散型ネットワークのセキュリティを確保している。

現時点でブロックチェーンの用途を見出せるのは、従来は台帳に記録されていたようなデータで、例えば金融取引(マイクロトランザクションを含む)、地方政府の記録(投票、土地登記、自動車登録など)、医療データ、追跡データなどである。基盤技術の改良により、他のさまざまなセキュアデータのストレージの用途にも対応可能になると私は予測している。

Mark completed his Electronic Engineering degree in 1991 and worked in real-time digital signal processing applications engineering for a number of years, before moving into technical marketing.
DesignSpark Electrical Logolinkedin