コンセンサスキャノン

プラトン再発行

フォロワー： 0

コンセンサスは、PlatoBlockchain Data Intelligence の基準となります。垂直検索。あい。

編集者注: a16z 暗号には長い一連の「銃」 — オリジナルからクリプトカノン私たちへ DAO カノンおよび NFTカノン最近では、私たちのゼロ知識カノン. 以下に、理解し、深く掘り下げ、構築するための一連のリソースを集めました。 コンセンサス: 暗号通貨が機能することを可能にし、トランザクションの有効性とブロックチェーンのガバナンスを決定する合意システム。

コンセンサスプロトコルは、ブロックチェーンの世界で起こっているすべての中心的な部分です。残念ながら、文献を理解するのは難しい場合があります。ここでは、最新の研究の最新情報を入手できるリンクのリストを示します。

議論されているプロトコルの種類に応じて、以下のリンクを分類します。ただし、最初に、既存の研究の概要を説明する一般的なリソースのリストを示します。

一般的なリソース

分散思考. このブログは Ittai Abraham と Kartik Nayak によって運営されていますが、他の主要な研究者からも多くの寄稿があります。基礎からはじめますが、最近の論文の簡単な解説もあります。

50ページのコンセンサス. 古典的なコンセンサス文献からの主要な結果をカバーする Andrew Lewis-Pye によるメモ。このリンクのバージョンは作成中で、頻繁に更新されます。これらのメモに基づく a16z 暗号化セミナーも参照してください (パートI, パートII).

分散コンセンサスとブロックチェーンの基盤. Elaine Shi による教科書の草案。

ブロックチェーンの基礎. Tim Roughgarden による YouTube でのレクチャーシリーズ。

ブロックチェーンの基礎. David Tse によるプルーフオブワークおよびプルーフオブステークプロトコルに焦点を当てた講義ノート。

コンセンサスの定義

最も研究されている XNUMX つのコンセンサス問題は次のとおりです。 ビザンチン放送, ビザンチン協定, ステートマシンのレプリケーション (ブロックチェーンプロトコルが解決する問題)。これらの問題間の関係の説明については、Consensus in 50 Pages (上にリストされている)、または Decentralized Thoughts の次のブログを参照してください。コンセンサスとは"と"ステートマシンレプリケーションのコンセンサスに設立された地域オフィスに加えて、さらにローカルカスタマーサポートを提供できるようになります。」

ビザンチン将軍問題 (1982) レスリー・ランポート、ロバート・ショスタク、マーシャル・ピーズ共著。
本稿では、有名な「ビザンチン将軍問題」を紹介します。それでも読む価値はありますが、いくつかの証明のより良いバージョンは他の場所で見つけることができます。公開鍵基盤 (PKI) が与えられた任意の数の障害のあるプロセッサの問題を解決できることを証明するために、Dolev と Strong による論文で、より単純で効率的なバージョンを見つけることができます (以下の「同期」のセクションを参照)。プロトコル」）。 PKI がない場合、プロセッサの XNUMX 分の XNUMX 未満がビザンチン障害を表示しない限り、問題は解決できないという有名な不可能性の結果については、フィッシャー、リンチ、およびメリットによる論文 (以下も参照) で、より理解しやすい証拠を見つけることができます。 .

ステートマシンアプローチを使用したフォールトトレラントサービスの実装: チュートリアル (1990) フレッド・シュナイダー著。
また、ブロックチェーンプロトコルによって解決される問題である State-Machine-Replication (SMR) の問題を扱っているこの古い論文も参照してください。

次のリンクは、考慮されるプロトコルの種類に従って分類されています。 許可された プロトコル (ほとんどの古典文献で考えられているように)。許可されたプロトコルは、すべての参加者がプロトコル実行の開始から認識されているプロトコルです。以下のリンクでは、許可されたプロトコルは、メッセージの信頼性のモデルに従ってさらに分類されています。 シンクロナス, 部分的に同期または 非同期.

これらの用語の説明については、次を参照してください。同期、非同期、部分同期」分散思考で。さまざまなモデルで得られた結果の概要については、分散思考チートシート.

同期プロトコル

メッセージ配信が信頼できる場合、つまり、メッセージが常に配信され、メッセージ配信の最大時間に有限の既知の境界が存在する場合、「同期」設定になります。正式な定義については、上記のリンクを参照してください。

ビザンチン契約の認証済みアルゴリズム (1983) Danny Dolev と H. Raymond Strong による。
ここには XNUMX つの重要な証拠があります。公開鍵インフラストラクチャ (PKI) があれば、障害のあるプロセッサがいくつあってもビザンチンブロードキャストを解決できるという証拠があります。これに関する別の説明については、「Dolev-Strong認証ブロードキャスト」分散思考で。という証拠もあります f + 1 Byzantine Broadcast を解決するにはラウンドが必要です。 f プロセッサに障害がある可能性があります。より簡単な証明については、 t-Resilient Consensus が t+1 ラウンドを必要とする単純な二価性証明マルコス・アギレラとサム・トゥエグ。

分散コンセンサス問題の簡単な不可能性証明 (1986) マイケル・フィッシャー、ナンシー・リンチ、マイケル・メリット。
これをカバーする最近の講演も参照してください。アンドリュー・ルイス＝パイおよびティム・ローガーデン.

ビザンチン協定のための情報交換の境界 (1985) Danny Dolev と Rüdiger Reischuk による。
ありませんそれコンセンサス文献における不可能性の証明の多くの形式。これは、コンセンサス問題を解決するために送信する必要があるメッセージの数に下限を設定する方法を示す重要なものです。

「フェーズキングプロトコル」、論文よりビット最適分散コンセンサス (1992) ピオトル・バーマン、フアン・ガライ、ケネス・ペリー著。
PKI を使用しない同期設定でビザンチン協定を解決するプロトコルを見たい場合は、おそらくこれが最も有益です。これを明確に説明している最近のブログ投稿については、「Gradecast のレンズを通して見た Phase-King: 認証されていない単純な同期ビザンチン契約」分散思考で。

部分的同期プロトコル

大まかに言えば、メッセージ配信が信頼できる場合とそうでない場合があるとき、私たちは「部分的に同期」の設定にいます。プロトコルは常に「安全」を確保する必要がありますが、メッセージ配信が信頼できる間隔でのみ「有効」である必要があります。これをモデル化する標準的な方法は、未知の「Global Stabilization Time」(GST) の存在を想定することです。その後、メッセージは常に既知の制限時間内に配信されます。正式な定義については、上のボックス内のリンクを参照してください。

部分的同期の存在下でのコンセンサス (1988) シンシア・ドワーク、ナンシー・リンチ、ラリー・ストックマイヤー共著。
これは、部分的な同期設定を紹介し、重要な結果の多くを証明する古典的な論文です。

クロマグロのコンセンサスに関する最新のゴシップ (2018) イーサン・バックマン、ジェ・クォン、ザルコ・ミロシェビッチ著。
適切なプレゼンテーションがあれば、Tendermint プロトコル (このホワイトペーパーで説明) は十分に単純であるため、部分的な同期設定でステートマシンレプリケーションを学習するのに適しています。非常に簡単なプレゼンテーションが 50 ページのコンセンサス (上記参照) に見られます。アンドリュー・ルイス＝パイおよびティム・ローガーデン.

Streamlet: 合理化されたブロックチェーンの教科書 (2020) ベンジャミン・チャンとエレイン・シー著。
このホワイトペーパーでは、簡単に教えられるように特別に設計されたブロックチェーンプロトコルについて説明します。 Elaine Shi による講義を見つけることができます。こちら.

キャスパー・ザ・フレンドリー・ファイナリティ・ガジェット (2017) ヴィタリックブテリンとヴァージルグリフィス。
これは、イーサリアムのプルーフ・オブ・ステークに対する現在のアプローチのバックボーンを形成するプロトコルです。これは本質的に、Tendermint の「連鎖」バージョンです。「連鎖」の説明については、以下にリストされている Hotstuff の論文を参照してください。

HotStuff: ブロックチェーンのレンズにおける BFT コンセンサス (2018) Maofan Yin、Dahlia Malkhi、Michael K. Reiter、Guy Golan Gueta、Ittai Abraham 著。
これは基本的に、Facebook の Libra プロジェクト (名前を Diem に変更) が最初に実装することを意図したプロトコルでした。 Tendermint に対する利点は、プロトコルが 楽観的に反応する、これは、リーダーが正直な場合、確認済みブロックを「ネットワーク速度」で生成できることを意味します。つまり、各確認済みブロックを生成するために事前定義された最小時間を費やす必要はありません。これに関するIttai Abrahamの講演もご覧いただけますこちら.

予想される線形ラウンド同期: 線形ビザンチン SMR のミッシングリンク (2020) Oded Naor と Idit Keidar 著。
このホワイトペーパーでは、「ビューの同期」のための効率的なメカニズムが確立されていないという Hotstuff の問題に対処します。このブログ Dahlia Malkhi と Oded Naor によるでは、ビューの同期の問題に関する作業の概要が説明されています。こちらもご覧くださいこのさらなる最適化 Andrew Lewis-Pye と Ittai Abraham による。

Paxosをシンプルに (2001) レスリー・ランポート著。
Tendermint などの最近のブロックチェーンプロトコルにすぐに飛びつきたくない場合は、別の方法として Paxos (ビザンチン障害を処理しない) から始めて、リストの次のリンクである PBFT に進むこともできます。（そしてどちらがそうします）。

実用ビザンチンフォールトトレランス (1999) ミゲル・カストロとバーバラ・リスコフ。
これは古典的な PBFT プロトコルです。 Barbara Liskov によるプロトコルに関する素晴らしい講演を見つけることができますこちら.

非同期プロトコル

「非同期」設定では、メッセージの到着が保証されますが、有限の時間がかかる可能性があります。正式な定義については、上のボックス内のリンクを参照してください。

XNUMX つの不完全なプロセスによる分散コンセンサスの不可能性 (1985) マイケル・フィッシャー、ナンシー・リンチ、マイケル・パターソンによる。
FLP 定理 (著者にちなんで名付けられた) は、コンセンサスプロトコルに関する文献でおそらく最も有名な不可能性の結果です。不明なプロセッサが XNUMX つでも故障している可能性がある場合、非同期設定でビザンチン契約 (または SMR) を解決する決定論的プロトコルはありません。 Tim Roughgarden による講義で素敵なプレゼンテーションを見つけることができますこちら.

紙面初登場の「ブラチャ放送」非同期ビザンチン協定プロトコル (1987) ガブリエル・ブラチャ著。
FLP 不可能性定理を回避する XNUMX つの方法は、終了要件を弱めることです。 Bracha's Broadcast は、ブロードキャスターに障害が発生した場合に終了を必要としない、より弱い形式のビザンチンブロードキャストを解決することにより、非同期設定で機能する決定論的プロトコルです。 Bracha の Broadcast は上記の論文で最初に登場しましたが、この論文では、ランダム性の助けを借りて、ブロードキャストプロトコルを使用してビザンチン協定を解決する方法も示されています。 Bracha's Broadcast だけを学びたい場合は、明確なプレゼンテーションを見つけることができますこちら.

FastPay: 高性能ビザンチンフォールトトレラント決済 (2020) マチュー・ボーデ、ジョージ・ダネシス、アルベルト・ソンニーノ著。
このホワイトペーパーでは、信頼できるブロードキャストを使用して非同期設定で支払いシステムを実装する方法について説明します (完全な順序付けを確立する必要はありません)。

非同期設定でビザンチン契約または SMR を解決する必要がある場合、FLP の結果は、何らかの形式のランダム性を使用する必要があることを意味します。 Bracha の論文 (上記) と同様に、次の XNUMX つのリンクは、ランダム性を使用してビザンチン協定を解決する方法を説明する文献の古典です。

自由選択のもう XNUMX つの利点: 完全に非同期の合意プロトコル (1983) マイケル・ベン・オー
コンスタンティノープルのランダムオラクル: を使用した実用的な非同期ビザンチン協定暗号学 (2005) Christian Cachin、Klaus Kursawe、Victor Shoup 著

最適な回復力と漸近的に最適な時間と言葉のコミュニケーションを備えた検証済みの非同期ビザンチン契約（2018）Ittai Abraham、Dahlia Malkhi、Alexander Spiegelman 著。
非同期設定で SMR (およびビザンチン協定) を解決する方法を理解するための代替ルートは、Hotstuff を変更する上記の論文に飛び込むことです。すでに Hotstuff を理解している場合、変更は非常に簡単です。リーダーが選択された後、敵対者はそのリーダーからのメッセージを差し控えることができるため、非同期設定で標準の Hotstuff を実行することはできません。正直な当事者は、リーダーが不誠実でメッセージを送信していないのか、それともリーダーが正直でメッセージが遅れているのかを知らないため、最終的には別の方法で前進しようとすることを余儀なくされます. この問題を解決するには、すべてのパーティが同時にリーダーとして機能するようにします。大多数の当事者が Hotstuff プロトコルの標準的な「ビュー」を正常に完了すると、遡及的に無作為にリーダーを選択します。確認済みのブロックが生成された場合は、そのブロックを使用し、残りは破棄します。

Dumbo-MVBA: 最適な多値検証済み非同期ビザンチン契約の再考 (2020) Yuan Lu、Zhenliang Lu、Qiang Tang、Guiling Wang 著。
この論文では、Abraham、Malkhi、および Spiegelman による以前のものを最適化し、予想される通信の複雑さを軽減しています。

BFTプロトコルのハニーアナグマ (2016) Andrew Miller、Yu Xia、Kyle Croman、Elaine Shi、Dawn Song 著。

最適な認証されたビザンチン契約を求めて（2020）アレクサンダー・スピーゲルマン著。
非同期プロトコルの利点は、メッセージ配信が信頼できない場合でも処理を進めることができることです。不利な点は、ネットワークの状態が良好な場合、通信コストが (さまざまな点で) 最適ではないことです。上記の論文は、「両方の長所をどの程度得ることができるか」という問題に取り組んでいます。

DAG プロトコル

許可された DAG ベースのプロトコルに関する最近の作業が相次いでいます。これらは、確認されたブロックのセットが線形に順序付けられるのではなく、有向非巡回グラフを形成するプロトコルです。通常、これらは非同期または部分的な同期設定で動作します。

この a16z 暗号化セミナーで、Andrew Lewis-Pye は次のように述べています。概要 DAGベースのコンセンサス。

次の XNUMX つの論文では、トランザクションの効率的な全順序付けを実現する DAG プロトコルについて説明しています。 DAG-Rider は非同期設定で動作し、Cordial Miners に似ていますが、待ち時間が長く、予想される (償却された) 通信の複雑さが低くなります。 Narwhal は mempool プロトコルであり、Tusk は Narwhal の上で動作する SMR プロトコルであり、特定の点で DAG-Rider の効率を向上させます。 Bullshark は似ていますが、部分的な同期設定で発生した良好なネットワーク状態を利用するように最適化されています。

必要なのはDAGだけ (2021) Idit Keidar、Lefteris Kokoris-Kogias、Oded Naor、Alexander Spiegelman 著。
DAG-Riderプロトコルを紹介した論文です。

イッカクとタスク: DAG ベースの Mempool と効率的な BFT コンセンサス (2022) ジョージ・ダネシス、レフテリス・ココリス・コギアス、アルベルト・ソンニーノ、アレクサンダー・スピーゲルマン著。

Bullshark: 実用化された DAG BFT プロトコル (2022) Alexander Spiegelman、Neil Giridharan、Alberto Sonnino、Lefteris Kokoris-Kogias 著。

Cordial Miners: あらゆる事態に対応する Blocklace ベースの注文コンセンサスプロトコル (2022) Idit Keidar、Oded Naor、Ehud Shapiro 著。
分散型決済システムを実装するために実際にブロックチェーンを必要としないのは興味深い事実です — 後者は、厳密に簡単な作業です ( 本論文証明のために）。トランザクションの全体的な順序付けを確立する方法を分析する前に、上記の Cordial Miners の論文では、まず、非同期設定で支払いを正常に実装する決定論的 (かつ非常に洗練された) DAG プロトコルについて説明しています。

無許可プロトコル

パーミッションレスプロトコルは、パーミッションレスエントリを持つものです。誰もがコンセンサスに達するプロセスに自由に参加でき、参加者のセットは、プロトコル実行中の任意の時点で不明になることさえあります。

Bitcoin：ピアツーピア電子式キャッシュシステム (2008) 中本聡.
あなたはこれについて聞いたことがあります。ここにもブログ投稿プルーフ・オブ・ワークなど、プロトコルのさまざまな側面の必要性と、ネットワーク同期がプロトコルでどのように役割を果たすかを直感的に分析する Kartik Nayak によるものです。

ビットコインとCryptocurrencyテクノロジーズ (2016) Arvind Narayanan、Joseph Bonneau、Edward Felten、Andrew Miller、Steven Goldfeder 著。
この教科書は、ビットコインの初心者向けの素晴らしい入門書です。関連もあります無料コースラコース.

より技術的なレベルでは、次の XNUMX つの論文でビットコインのセキュリティと活性が分析されており、モデル化の仮定がわずかに異なります。「Bitcoin Backbone」紙が最も有名です。表記が重いため読みにくくなっていますが、証明の背後にある基本的な考え方は、最初に思われるほど複雑ではありません。 Dongning Guo と Ling Ren による証明は、基本的な考え方を説明しており、より短く単純です。

ビットコインバックボーンプロトコル: 分析と応用 (2015) フアン・ガライ、アゲロス・キアヤス、ニコス・レオナルドス。
非同期ネットワークにおけるブロックチェーンプロトコルの分析 (2017) Rafael Pass、Lior Seeman、Abhi Shelat 著。
ビットコインのレイテンシとセキュリティの分析がシンプルに (2022) Dongning Guo および Ling Ren 著。

すべてはレースであり、中本は常に勝つ (2020) Amir Dembo、Sreeram Kannan、Ertem Nusret Tas、David Tse、Pramod Viswanath、Xuechao Wang、および Ofer Zeitouni 著。
この論文では、著者は、より長いチェーンを構築するための競争の最も明白な攻撃が最も効果的であることを示すことによって機能する、Bitcoin の洗練されたセキュリティ分析を実行します。分析は、Ouroboros、SnowWhite、および Chia (すべて以下にリストされています) にも拡張されます。

次に、次の XNUMX つの論文では、ビットコインと古いプルーフオブワークイーサリアムに対するさまざまな攻撃形態について説明しています。

過半数では十分ではありません: ビットコインのマイニングは脆弱です (2014) Ittay Eyal と Emin Güun Sirer 著。
これはよく知られた「利己的なマイニング」論文です。

ビットコインのピアツーピアネットワークに対する Eclipse 攻撃 (2015) Ethan Heilman、Alison Kendler、Aviv Zohar、Sharon Goldberg 著。

イーサリアムのピアツーピアネットワークに対する低リソース Eclipse 攻撃 (2018) ユヴァル・マーカス、イーサン・ハイルマン、シャロン・ゴールドバーグ著。

FruitChains: 公正なブロックチェーン (2017) ラファエル・パスとエレイン・シー著。
上記の論文は、利己的なマイニングの問題への対応です。著者は、マイナーの正直な戦略が近似平衡の形になるようなプロトコルを説明しています。

Prism: ブロックチェーンを解体して物理的限界に近づく (2019) Vivek Bagaria、Sreeram Kannan、David Tse、Giulia Fanti、Pramod Viswanath 著。
ビットコインでは、ブロックはトランザクションをリストするために使用されるという意味で複数の役割を果たしますが、ブロックの順序付けでコンセンサスに達するという意味でも使用されます。上記の論文では、著者は中本氏のブロックチェーンを基本的な機能に分解し、高スループットで低レイテンシーのプルーフオブワークプロトコルを構築する方法を示しています。

次の XNUMX つの論文は、証明可能な保証を備えた最長チェーンのプルーフオブステークプロトコルを実装する方法を示しています。

ウロボロス: 安全性が証明された Proof-of-Stake ブロックチェーンプロトコル (2017) Aggelos Kiayias、Alexander Russell、Bernardo David、Roman Oliynykov 著。
Snow White: Proof of Stake を確実に保護するための堅牢に再構成可能なコンセンサスとアプリケーション (2019) Phil Daian、Rafael Pass、Elaine Shi 共著。

アルゴランド: 暗号通貨のビザンチン契約のスケーリング (2017) Yossi Gilad、Rotem Hemo、Silvio Micali、Georgios Vlachos、Nicolai Zeldovich 著。
このペーパーでは、従来の BFT スタイルのプロトコルをプルーフオブステークプロトコルとして実装する方法を示します。ここはアルゴランドの話シルヴィオ・ミカリ。

ゴーストとキャスパーの組み合わせ (2020) ヴィタリックブテリン、ディエゴヘルナンデス、トールカンフェフナー、キームファム、ジチャオ、ダニーライアン、ジュヒョクシン、インワン、ヤン X チャン著。

Proof-of-Stake イーサリアムに対する XNUMX つの攻撃 (2022) Caspar Schwarz-Schilling、Joachim Neu、Barnabé Monnot、Aditya Asgaonkar、Ertem Nusret Tas、および David Tse 著。
イーサリアムの現在のバージョンには、さらに分析が必要です。この論文では、いくつかの攻撃について説明します。

Chiaネットワークブロックチェーン (2019) Bram Cohen と Krzysztof Pietrzak 著。
このペーパーでは、空間と時間の証明を使用して最長チェーンプロトコルを構築する方法を示します。

無許可の設定でのビザンチンの将軍（2021）アンドリュー・ルイス・パイとティム・ラフガーデンによる。
この論文では、著者は、許可のないプロトコルの不可能な結果を証明するなどのことを行うことを可能にし、プルーフ・オブ・ワークおよびプルーフ・オブ・ステークのプロトコルの一般的な機能を明確に描写することを可能にする、許可のないプロトコルの分析のためのフレームワークを開発します。 .

***

アンドリュー・ルイス＝パイロンドン・スクール・オブ・エコノミクスの教授。彼は、数理論理、ネットワーク科学、集団遺伝学、ブロックチェーンなど、さまざまな分野で働いてきました。過去 XNUMX 年間、彼の研究の焦点はブロックチェーンにあり、主な関心はコンセンサスプロトコルとトークンノミクスにあります。 Twitterで彼を見つけることができます @AndrewLewisPye .

謝辞: 多くの tリン・レンに感謝します。イッタイアブラハム, カルティック・ナヤク, ヴァレリアニコレンコ, アレクサンダー・シュピーゲルマン, マチュー・ボーデ有用な提案のために。

***

ここに示されている見解は、引用された個々のAH Capital Management、LLC（「a16z」）の担当者の見解であり、a16zまたはその関連会社の見解ではありません。ここに含まれる特定の情報は、a16zが管理するファンドのポートフォリオ企業を含むサードパーティの情報源から入手したものです。 a16zは、信頼できると思われる情報源から取得したものですが、そのような情報を独自に検証しておらず、情報の永続的な正確性や特定の状況に対するその適切性について表明していません。さらに、このコンテンツにはサードパーティの広告が含まれる場合があります。 a16zはそのような広告をレビューしておらず、そこに含まれる広告コンテンツを推奨していません。

このコンテンツは情報提供のみを目的として提供されており、法律、ビジネス、投資、または税務に関するアドバイスとして信頼されるべきではありません。これらの問題については、ご自身のアドバイザーにご相談ください。証券またはデジタル資産への言及は、説明のみを目的としたものであり、投資の推奨または投資顧問サービスの提供を構成するものではありません。さらに、このコンテンツは、投資家または将来の投資家による使用を目的としたものではなく、a16zが管理するファンドへの投資を決定する際にいかなる状況においても信頼されない場合があります。（a16zファンドへの投資の申し出は、私募覚書、サブスクリプション契約、およびそのようなファンドの他の関連文書によってのみ行われ、その全体を読む必要があります。）言及、参照、または記載されているのは、a16zが管理する車両へのすべての投資を代表するものではなく、投資が有益である、または将来行われる他の投資が同様の特性または結果をもたらすという保証はありません。アンドリーセンホロウィッツが管理するファンドが行った投資のリスト（発行者がa16zに公開を許可していない投資、および公開されているデジタル資産への未発表の投資を除く）は、https：//a16z.com/investmentsで入手できます。 /。

記載されているチャートおよびグラフは、情報提供のみを目的としており、投資を決定する際に信頼することはできません。過去の実績は将来の結果を示すものではありません。内容は、示された日付の時点でのみ話されています。これらの資料に記載されている予測、推定、予測、目標、見通し、および/または意見は、予告なしに変更される場合があり、他の人が表明した意見と異なる場合があります。その他の重要な情報については、https：//a16z.com/disclosuresを参照してください。