AlgorandMITのCSとゲーム理論の専門家が結集したAlgorandのビザンチン合意プロトコルは既存のプロトコルの課題を超えている可能性があるが、保留されている誘因設計が吉と出るか凶とでるかが、その価値を分けることになる。readTl;DRMITのCSとゲーム理論の専門家が結集したAlgorandのビザンチン合意プロトコルは既存のプロトコルの課題を超えている可能性があるが、保留されている誘因設計が吉と出るか凶とでるかが、その価値を分けることになる。ラーメン一蘭合意」と結論を読んでいただければ大体わかる。一蘭は最高傑作のたとえ話である。Agreement”である。これが2016年に発表され、2018年2月に400万ドルを集めAlgorandは正式に企業として登録された。2018年7月にテストネットが稼働し、今年の10月、6200万ドルを集めた。Capital”を設立した。Micaliはチューリング賞受賞のMITコンピュータサイエンス教授であり暗号学者。ランダム関数、デジタル署名、紛失通信プロトコル、セキュアマルチパーティーコンピュテーションに関する研究で最もよく知られている。(アルゴリズム的ゲーム理論)の専門家。アルゴリズム的ゲーム理論とはゲーム理論とアルゴリズム理論の融合領域で戦略的環境におけるアルゴリズムを設計・解析することを目的とした理論であり、経済学とコンピュータサイエンスの交差点とも言える領域に属している。ミクロ経済学、分散システム、ネットワークを専門とするMITの教授、出身者の面々が名を連ねている。経営部分を担当するCEO、COO、CTO、エンジニアリング、プロダクト、HR、マーケティングには企業でキャリアを積んだベテランが雇われている。既存アルゴリズムとの比較MicaliがAlgorandを提案する文脈を知るため、合意アルゴリズムがたどってきた経緯を振り返ろう。合意アルゴリズムはブロックチェーンよりずっと前から存在していた。分散システムで一貫した結果を生むアルゴリズムはすべて「コンセンサス(合意)アルゴリズム」と呼ばれる。これまでにも多くの合意アルゴリズムが使用されているが、多くは悪意のある攻撃者を想定しないモデルだった。悪意のある攻撃者を想定する分散合意の問題が、ビザンチン将軍問題である。中央の管理システムが存在せず、参加者の中に故障したコンピュータや悪意を持った個人が紛れ込んでいる状態で、全体で正しい合意を形成できるのか。知られているPaxosアルゴリズムでもビザンチン問題に対処できるし、Paxosの改善されたバージョンが公開されている。多くのBFTプロトコルはヘビーな通信が必要であるため、多数の参加者に対応できない。PoWのようなブロックチェーン合意アルゴリズムでは、多数の参加者を想定しており、トランザクションごとの対話が少なくて済むが、一貫性が保証されるのではなく、より制限の少ない確率的なモデルが採用されることがよくある。合意アルゴリズムには以下の4つの分類がある。下の項目に進むほど難易度が上がる。下の2項目を「ビザンチン合意」と呼ぶ。Paxos未知の参加者、ビザンチン障害耐性:プルーフ・オブ・ワーク(PoW)、プルーフ・オブ・ステークス(PoS)多くのBFTはノードの母集団を事前に”知っている”ことを想定している。通常、ブロックチェーンアルゴリズムはこの仮定をせず、参加者はいつでも参加できる。区分の一番下、PoWとPoSは多数で未知の参加者、しかも悪意の参加者を含むなかでの分散合意を成し遂げたのことが画期的だった。party”(信頼される第三者)を必要としない、”価値移転を可能にした。Bitcoinはサードパーティに依存せずプロトコルに従い、ステークホルダーのふるまいで継続し続けた。採掘者にとっては、P2Pネットワークを攻撃するよりも採掘(コンピュテーション資源を投入し新しいブロックを生成するための競争をすること)することの方が儲かるのだ。2009年にBitcoinが登場しやがて中国山間部に信頼の置けない採掘者の集団が生まれた後もPoWはBFTを実証し続けたのだ。PoWには課題があった。PoWの課題PoWの欠点とは、ひとつは余りにも無駄なコンピューテーションリソースと電力を投入されていることだ。PoWは採掘者にハッシュ関数の”SHA-256”を利用した問題を解くことを求めている。それは32ビットの値である”nonce”をSHA-256に入れ、出力される値が求められる条件を満たすかを探るクイズである。採掘者にとってこのクイズを解く最適な手段は”総当たり方式”である。Bitcoinの法定通貨建て価格が高騰するに従い、総当たり方式に最適なコンピュータを作るインセンティブが生まれている。価格が下落した現在はそうでもないが、一時期は採掘者が寒冷な地域にある余剰電力のある水力発電所の近くに多量のASICとともに殺到するできごとを引き起こした。VRなどに取り組む人たちにリソースが回らないという社会的損失をもたらした。ひとつはコンピューティングリソースの投入量とスループット(機器や通信路などが単位時間あたりに処理できる量)が相関しないことだ。Bitcoinのスループットは10分に1回の1MBのブロックに限定されているが、価格がピークの2017年12月には途方もないコンピューティングパワーが”廃棄”されていた。PoWはハッシュパワーの51%を超える単一、あるいは共謀した採掘者の攻撃に脆弱である。近年は採掘者の寡占化が進んでおり、サトシ・ナカモトが残した遺産を基にビットコインを開発する開発者との溝が深まっていた。Classic”を生み出したりした。この通りPoWは分散合意を成し遂げたが同時に高いコストを作った。欲張りな人は低いコストでの不特定多数間のビザンチン合意がほしいと思うだろう。それで、より高いスループットを必要としていたEthereumを筆頭に多数のプレイヤーがもともと議論が存在したプルーフ・オブ・ステーク(PoS)に注目するようになる。直訳すると”賭けの証明”ということになる。PoSの利点と課題PoSは「あなたがどれだけ賭けたかに基いた確率で報酬を獲得できる仕組み」だ。「あなたが新しいブロックを生成する権利を獲得する確率が、コインの持ち分に応じて変化する」仕組みである。(この記事で詳述した。『”独占戦略"に脆弱な分散合意アルゴリズム「Pos」』)PoSは持ち分に応じて投票するだけなので、PoWの課題であるクイズを解くための軍拡競争が起きない。PoWはBFTを確保するためさまざまな”儀式”を織り込んでいるが、PoSは投票と承認のプロセス、そしてその報酬の分与だけなので、コストが低い。PoWで指摘したビッグプレイヤーが行儀の悪いことをする可能性を排除できているという想定をしている。PoSでは大量のコインを持っている参加者が検証プロセスにおいて悪意のある行動を起こす動機がないと想定する。多量のコインを保有する「金持ち」は確実により金持ちになれるのだから偽りの行動をする誘因に欠けているためだ。お金持ちが次のブロックを生成する人になれる確率が高く、もたらされた報酬がお金持ちにさらなるお金をもたらすからだ。ビザンチン合意のシミュレーションでは自己利益の最大化を目指す利己的主体を想定する。これによりステークを持つ主体はそのステークを手放さず、投票に参加する誘因があると想定できる。PoSはこれが合意に安定をもたらすと想定する。わかった人もいると思うが、PoSには明確な脆弱性がある。賭けたステークに基づいて確率的に報酬が配分されるのなら、他者を押し出すために自分が必要な額以上を賭ける”攻略法”がある。この攻略法はゲーム理論が想定する利己的主体というプレイヤー像とフィットする。市場価格より高い価格でコインを値付けして買収していけばいくほど、PoSの結果生み出される報酬を獲得できる確率が拡大していく。プレイヤーに正直な投票をする誘因のために報酬を設定したはずなのに、その報酬と報酬の分配メカニズムが他者を追い出す戦術の誘因を生みだしてしまうわけだ。この『サトシコンセンサスの次、Algorandの挑戦』でMicaliはその点に言及している。”失敗したPoS”の先行例NemをPoSコインと類似する実験と捉えてみよう。PoSの類似例である。PoIでもコインの保有量が一番大きな要素であり、大量保有者は少量保有者よりも著しく効果的にコインを増やせるのだ。生みだす収益のほとんどを大量保有者が飲み込んでおり、いわゆるマルチ商法と同様の構造で、大量保有者にはNemネットワーク(ネットワーク商法のネットワークではないよ)の重要な役割が優先的に付与されるようになっていた。保有者たちのメカニズムへの理解は、コインの保有量と比例するのだ。大量保有者は積み重なった大量のコインを法定通貨に換えたい。Nemの通貨Xemは傍流で安かった。大量保有者は情報の非対称性を活かし新規参入者にNemの”利点”を説得し、取引所での購入を勧めた。新規参入者には取引所での法定通貨との交換レートを引き上げる役割が期待されていたのだ。新規参入者はこのメカニズムに組み込まれるとほどなく状況を理解し、利益を得たいがため、より”新しい新規参入者”を呼び寄せるようになった。だまされた初心者の大群が価格を高騰させると、大量保有者は保有コインの一部を高値で売ることができた。大量の売りで価格が急落し、高値づかみの新規参入者は大損をした。「モラルハザード」である(詳細はこちらの記事で。『”独占戦略"に脆弱な分散合意アルゴリズム「Pos」』)。ここで、興味深いのは、暗号通貨取引所という存在は、法定通貨との交換可能性を提供するため、攻撃者が不正を働くインセンティブを著しく高めていることだ。余談だが、史上最大のクラック案件となったCoincheck事件では、盗まれたXem(Nemのトークン)はクラッカーがダークウェブに自ら構築した取引所で法定通貨と交換された。暗号通貨と法定通貨の交換レートが生じるためPoS通貨ではこのようなモラルハザードも想定できるだろう。PoSにもPoIと同じエコノミクスが働いているので、同様のスキームが起こる可能性がある。法定通貨で儲けることを目的としなければ、独占、あるいは共謀を含みにした複占、寡占をすればPoSはいとも簡単にクラックできる。Ethereumはこの可能性を織り込んでいるが不十分である。EthereumはPoSの採用に伴い多数派を形成して不正なトランザクションを承認させようとしたり、共謀の兆候があるプレイヤーを検出し罰するアルゴリズムの採用を検討している。Micaliは会社設立時のインタービューで罰の活用に否定的な考え方を話している。「脆弱な国家は脅威と恐怖で支配を行います。ある国では犯罪と戦うために残酷な刑罰を課すことにしているか、というと、犯罪者はめったに捕まえられないからだ。悪い行為をした人を追放したいと思うはずですが、よく作り込まれたシステムは、人を罰する必要がないシステムです」。この「アメとムチ」というのはメカニズムを維持するために採用する古典的な手段であり、最悪の中の最高とも言うべきだろう。パターナリズムでもリバタリアニズムでもない社会設計』)。この記事『Googleの検索広告で学ぶオークションの理論と実践』ではオークションを通じてこのようなメカニズムデザインについて検討しているのでぜひ読んでほしい。EthereumはPoSへ移行すると言われるが、執筆時点ではまだPoWにとどまっている。Bitcoinは1秒あたり7トランザクション、Ethereumは1秒あたり15トランザクションしか処理できない壁にぶつかっている。Bitcoinにもライトニングネットワークという解決策があるが、これも様々な問題点が現れたため開発の経過は難航している。両者は現状、明らかにスケーラビリティ(拡張性)がないのだ。もとから既存金融機関の利用を念頭にいれたRippleは信頼できる一部の承認者(validator)による投票で取引を承認できるようにしている。この記事の序盤で指摘した、既知の参加者、非ビザンチン障害耐性の最も古典的な合意アルゴリズムを採用していることになる。これによりRippleは取引を承認するまでにかかる時間が3~6秒と高速化しており、BitcoinとEthereumよりもスループットは遥かに大きい。Rippleでは単一の承認者だけが悪意を持ったとしても、システム全体を破壊することはできないが、過半の承認者が悪意を持てばシステムを破壊できる。権威による証明)と大差がない。Rippleは拡張性は確保したがビザンチン合意を放棄した。ビザンチン合意と拡張性はトレードオフになっている。裏を返せば、このトレードオフを乗り越えれば、いままでにない暗号通貨が生まれるわけだ。AlgorandはPoSの暗号学的、ゲーム理論的な改善によりこのトレードオフを解決しようとしている。Algorandの本体の仕組みを説明しよう。Protocolの実施形態Algorandはリーダーによる選挙を伴うシンプルなビザンチン合意のプロトコルである。正直なユーザーが多数派(2/3以上)であることを条件としている。Algorandのビザンチン合意は、バリデータ(検証者)の検証時間を完全に同期させる必要がない。バリデータには他社の存在を知らないまま瞬間的な同意を求める瞬間合意アルゴリズムが適用されている。Algorandは以下のステップを採用している。ランダムに選択されたユーザーがリーダーとなり、新しいブロックを提案して循環させる。ランダムに選出された複数ユーザーによる委員会が設置される。委員会はリーダーから提案されたブロックに関して2/3以上の賛成投票によりビザンチン合意に達する。合意されたブロックは委員会メンバーによりデジタル署名される。デジタル署名は参加者全員が新しいブロックについての確証をもてるよう参加者によって回覧される。署名者の信用証明書の回覧をだけでなく、ハッシュ値が確定するとハッシュ値も回覧され、参加する誰もが新ブロックについて知ることが保証される。※選出されたリーダーが偽りのブロックを提案した場合、委員会がブロックを否決し、新たにリーダーを選び直すステップに入る。最初のブロック生成をする”リーダー”とそれを検証(Validate)する”委員会”のメンバーは秘密裏にランダムに選ばれる。リーダーと委員会のメンバーは匿名の状態で、一時的にあてがわれた公開鍵だけが回覧される。委員会のメンバーはプロトコルとの通信はあるが、他のメンバーが誰かは知らされないまま投票に入る。承認後のブロックのデジタル署名と信用証明書(Credidential)の回覧により、承認の正しさが確定する。参加者による逐次設定される”委員会”への監視が働くことになる。Algorandプロトコルはブロックがネットワークを伝播する間に提案されると同時に、ブロックに対する合意プロセスを進める。Consensus)である。ユーザーはブロックを受け取った瞬間にブロックに投票することを要求され、その間もブロックは残りのユーザーに伝播し続ける。すべてのユーザーがブロックを見た時点で、すべての投票が完了しているのだ。入り組んだDPoSとは異なり、1回の投票で合意に達する。伝播後、複数回の投票の後に追加の作業を必要とする従来のメカニズムとは対照的だ。この即時合意は、新しいブロックが正しく伝搬されることを前提としている。悪意のあるブロック提案者が現れるケースでは、プロトコルは悪意のプレイヤーであることを認識するとそのプレイヤーを無視してすぐに新しい提案者の選択に進む。sortition(暗号化くじ引き)”という。ほとんどのPoSシステムはある種のランダム性に依存しているが、Algorandは自分のコンピュータで”宝くじ”を実行して自己選択するという点で他のアルゴリズムとは異なるとMicaliは主張する。宝くじは過去のブロックのデータに基づくが、選択は参加者同士のメッセージ交換を伴わず自動かつ完全にランダムである。Micaliは古代ギリシアの都市国家アテナイで採用されていた直接民主制の手法である”sortition”(くじを引いて選択する行為)から命名したという。先述したDPoSが「間接民主制」ならAlgorandは「直接民主制」であるという含意があるとみられる。