編集者注: この記事は以下から引用しましたチェーンニュース ChainNews (ID:chainnewscom)編集者注: この記事は以下から引用しました
チェーンニュース ChainNews (ID:chainnewscom)
、著者：李華、許可を得て出版されました。
ブロックチェーンは分散システムです。分散システムがどのように機能するかを理解していなければ、ブロックチェーンを真に理解することは困難です。
ブロックチェーンを理解していないと問題となるのは、「分散化」や「パーミッションフリー」などの概念や、「TPS」や「セキュリティ」などの文脈を失った議論に陥ることです。これでは、ブロックチェーンプロジェクトを正確に分析、判断することができないだけでなく、ブロックチェーンの技術開発ルートを認識することもできなくなります。
もっと率直に言うと、分散システムの基本的な知識を習得する必要があります。このため、ブロックチェーン自体の限界がわかり、真に価値のあるブロックチェーン プロジェクトは、特定の問題を解決するために、特定の環境で特定のソリューションを作成する必要があることがわかります。
単純なインデックスの比較は客観的ではないため、より適切な基準は、このソリューションがこの問題の解決に適しているかどうかです。
分散システムがどのように機能するかを理解することは、ブロックチェーンの世界にとって非常に重要です。それでは、分散システムの探索を始めましょう。
コンピュータの機能は情報を処理することであり、条件 A をコンピュータに入力すると、結果 B が出力されます。情報を処理する作業が 1 台のコンピュータによって行われる場合、これは集中型構造であり、情報を処理する作業が複数の独立したコンピュータの協力によって行われる場合、それは「分散システム」と呼ぶことができます。
情報処理のさまざまな方法を実装する分散システムにはさまざまなアーキテクチャが存在します。システム内に 10 台のコンピュータがあると仮定すると、1 つのアーキテクチャは次のとおりです。計算タスクを 10 の部分に分割し、各コンピュータに独立してタスクを処理させ、最後に計算結果を出力としてまとめます。
これは、同じ作業を 10 回行うのと同じような「苦労を求める」システムであることが容易にわかり、異なるコンピュータ間での追加の通信作業が必要になります。
では、なぜそのようなシステムが必要なのでしょうか?それは、中央集権的なコンピューターや、そのコンピューターの背後にある中央集権的な企業や組織への依存を避けることができるからです。このようにして、単一障害点や悪を回避し、権力の集中と乱用を減らすことができます。
副題
1. 分散システムの理想的な目標
ブロックチェーンが属する分散システムは、「レプリケートされたステート マシン」としても知られています。その目標は単純です。システム内のすべてのコンピューターが特定の出力値に同意することです。つまり、システム内のすべてのコンピューターが、すべてのノード/コンピューターに、初期状態は同じであり、トランザクションの実行後は、すべてのノードが同じ最終状態になります。
すべてのコンピュータが正常に機能し、コンピュータ間の通信が完全に同期されていれば、これを達成するのは難しくありません。しかし現実はそうではなく、主に次の 2 種類の問題があります。
一部のコンピューターがダウンしているため、結果を計算できないか、システムに接続できない可能性があります。
これらの問題は一般的かつ避けられないものであり、一度問題が発生すると、すべてのコンピュータが特定の出力結果に同意することは不可能になります。有名な分散システム「FLP 不可能性の原則」は次のように説明されています。ネットワークは信頼できるが、ノード障害が許容される最小限の非同期モデルを備えたシステムでは、一貫性の問題を解決できる決定論的なコンセンサス アルゴリズムは存在しません。平たく言えば、システム内の 1 台のコンピューターに障害が発生する限り、システムは出力値について合意に達することができません。
FLP 不可能性原則は、あらゆるシナリオに直面する分散システムのコンセンサス アルゴリズムの設計に時間を無駄にしないでください、それは不可能であることを示しています。
副題
2. 分散システムのコンセンサスアルゴリズム
FLP の不可能性原理は残酷ですが、分散システムがもたらす利点は困難に直面する価値があります。すべてのシナリオに対応するコンセンサス アルゴリズムは存在しないため、特定のシナリオで効果的なコンセンサス アルゴリズムを見つけることができる場合があります。コンセンサス アルゴリズムとは、分散システムがコンセンサスに達するための方法を指します。
科学者がどのようにシナリオを段階的に制限し、このシナリオでコンセンサスアルゴリズムを実現するかを見てみましょう。
まず、システム内の各コンピューターが独自の結果を導き出すことができる場合、どの結果について合意に達するかさえわからないため、状況は間違いなく複雑になります。したがって、コンセンサス問題を解決するための最初のステップは、コンセンサスが何であるかを決定することです。最も単純な方法は、あるコンピュータが最終決定権を持ち、そのコンピュータが結果を提案し、他のコンピュータがその結果に同意するというものです。
最終決定権を持つコンピューターは提案者またはリーダーと呼ばれます。リーダーを通じてコンセンサスを達成することが問題を解決する唯一の方法ではありませんが、ブロックチェーン システムで使用されるコンセンサス アルゴリズムを含め、ほとんどのプロトコルはこれに基づいて実装されています。
完全な地方分権というものは存在せず、合意を得る最初のステップは中心を決めることです。
余談: これを知ると、地方分権についてより効果的な議論ができるようになります。
話題に戻ります。リーダーを必要とするコンセンサス アルゴリズムの作業手順は、大まかに次のとおりです。
リーダーを選出する。
リーダーは結果を提案します。
全員が結果について合意に達すると、システムは最終結果を出力します。全員が合意に達しない場合は、ステップ 1 に戻ってやり直します。
この考え方は合意を得る方法を提供しますが、実際に合意を得るには程遠いです。なぜなら、コンピュータがシステムに接続できない場合、リーダーの結果に同意するかどうかを投票することができず、問題のあるコンピュータがたまたまリーダーだった場合、状況はさらに悪化し、システム全体が停止してしまうからです。行き止まりに。
副題
3. 同期仮説コンセンサスアルゴリズム
上記のダウンタイムの問題を解決するにはどうすればよいでしょうか?方法は簡単です。コンピュータがシステムに接続できない場合は、それを無視し、このラウンドの合意には参加しないでください。
次に、システムに接続できないかどうか、またはコンセンサスに参加しているが速度が他のマシンより遅いかどうかをどうやって知ることができるのかという新たな疑問が生じます。
その結果、科学者たちは、コンセンサス問題を解決するための最も重要な仮定の 1 つである、共時性の仮定を開発しました。共時性の仮定では「タイムアウト」という概念が導入されており、あらかじめ時間枠が設定されており、リーダーが時間枠内に提案を出さなかった場合、その提案は排除され、新しいリーダーが選出される。このようにして、リーダー ノードの障害を許容できます。 (注: 共時性の仮定は共時性の仮定と同じではありません)
Paxos アルゴリズムと Raft アルゴリズムは両方とも共時性の仮定に基づいて提案されています。しかし、これら 2 つのアルゴリズムは、システムについて別の仮定を行う必要もあります。つまり、システム内のすべてのコンピューターは「善人」であり、リーダーの提案に正しく応答するか、失敗により応答できないかのどちらかです。
ということで、厳しい条件はあるものの、ようやく合意形成が可能な分散システムが完成しました。
Paxos コンセンサス アルゴリズムは、1990 年に Leslie Lamport によって提案された、メッセージベースでフォールトトレラント性の高いコンセンサス アルゴリズムです。Google を含む分散システム アプリケーションの分野で重要な位置を占めています。このアルゴリズムは、多くの企業の大規模分散システムで使用されており、含む 。そして、探索の第 1 段階もここで終了し、その後に第 2 段階が続くこともあります。
副題
4. システム内の「悪者」を排除する
Paxos はコンセンサスを得ることができますが、そのアルゴリズムはすべてのコンピュータが「善人」であるという前提に基づいています。そして、コンピュータ内に「悪者」がいる場合、システムには悪者の声と善人の声が現れることになり、Paxos のアルゴリズムはこの状況に対処できません。
悪意のある者が存在する場合でも合意を達成できるアルゴリズムが必要ですが、それは可能でしょうか?レスリー・ランバートは、この可能性を議論するために、ビザンチン将軍問題と呼ばれるモデルを開発しました。このモデルでは、ビザンチン ノードは、システム全体の合意形成を妨げる破壊的なメッセージを送信する悪者ノードです。
論文「ビザンチン将軍問題」の中で、ランバートはいくつかの解決策を提案しました。そのうちの 1 つは、ビザンチン ノードが 1/3 未満の場合にシステムのコンセンサスを達成できます。言い換えれば、システム内の悪者の数が 1/3 未満であれば、アルゴリズムを通じて合意を得ることができます。
その後登場した DLS アルゴリズムや PBFT アルゴリズム (Practical Byzantine Fault Tolerant Algorithm) はすべてこれに基づいて開発されました。
PBFT は代表的な Byzantine フォールトトレラントアルゴリズムであり、その実装プロセスは大まかに以下のとおりです。このコミュニケーション方法を通じて合意に達することができるということを知っていれば、プロセスを理解していなくても問題ありません。
事前準備フェーズ: リーダーは結果をすべてのフォロワーに送信します。このグラフのリーダーはノード 0 であり、結果をフォロワー 1、2、および 3 に送信します。
準備フェーズ: フォロワーが結果が正しいと考える場合は、他のすべてのノードに結果を承認するように指示します。たとえば、ノード 1 は承認メッセージをノード 0、2、および 3 に送信します。
コミットフェーズ: フォロワーは、ノードの 2/3 以上がリーダーの結果に一致することを発見した場合、他のすべてのノードにこの結果を最終結果として受け入れるように指示します。
これまでのところ、ビザンチン ノードを備えた分散システムのコンセンサス問題を解決してきました。ただし、システム内の悪者の数が 1/3 以上の場合、依然として合意に達することは不可能です。私たちにできることは、システムのアクセス条件やインセンティブによって悪者を1/3以下にすることです。
分散システムの第 2 段階の探索はここで終了し、次は第 3 段階に入ります。
副題
5. ナカモトコンセンサスアルゴリズム
Paxos と PBFT はどちらも共時性の仮定を使用しており、実際、ナカモト コンセンサスが出現するまでは、コンセンサス アルゴリズムに関するほとんどすべての研究がこの方向で行われていました。ナカモトのコンセンサスは非決定論的なメカニズムを使用しています。
それはどういう意味ですか？ 12 台のコンピュータで構成される分散システムを、12 人の陪審員からなる陪審と考えることができます。私たちはこれら12人を会議室に閉じ込め、事件を説明するメモを提出し、会議室の入り口に座って裁判の結果が出るのを待ちました。
この12人は判断の仕方について意見が異なり、議論が進むにつれて立場が変わったり、居眠りして意見を言えなくなる人もいるかもしれない（『十二人の怒れる男』参照）。次に、ドアの前に座って待っている人には 2 つの選択肢があります。最初のオプションは、あなたがそれについて話し合うことであり、私はあなたが望む限り待つことができますが、最終的にはあなたが唯一の明確な試験結果を私に提供しなければなりません; 2 番目のオプションは、私は待つことができない、そしてあなたは最初に私は、より多くの人が同意する結果があれば、その結果に変更します。
結果の確認が必要な場合は結果が得られるという保証はなく、結果の確認が必要な場合はその結果が最終結果でなければならないという保証はありません。
これは分散システムの場合に当てはまります。オプションは 2 つだけです。最初のオプションはファイナリティと呼ばれ、「結果の確実性」またはセキュリティを意味します。2 番目のオプションはライブネスと呼ばれ、ネットワークのアクティビティまたは可用性を意味します。
これら 2 つの選択により、分散型コンセンサスのための 2 つの異なる設計アイデアが決まります。
ファイナリティの追求は結果を優先するため、ネットワーク上の要件を作成する必要があります。 PBFT と Tendermint は両方ともこのタイプのアルゴリズムであり、ネットワーク同期を前提としており、このようなアルゴリズムを使用するシステムはフォークしません。
余談ですが、Finality と Liveness のどちらを選択するかは、分散システムの CAP 定理 (不可能な三角形) の現れでもあります。この定理は次のように述べています。分散システムでは、一貫性、可用性、および分割耐性を同時に満たすことは不可能です。パーティションフォールトトレランスとは、システムがネットワーク分割を許容できる必要があり、実際のネットワークは必ず分割されるため、この条件が満たされなければならないことを意味します。実際、CAP 定理によれば、分散システムは一貫性と可用性の両方を満たすことができません。そのうち、CAP の一貫性はファイナリティを反映し、CAP の可用性はライブネスを反映します。
FLP 不可能性原理であれ、CAP 不可能性定理であれ、彼らは私たちに「この道は歩きにくい、突破できれば素晴らしいイノベーションになる」とは言っていないのです。やるべきことは、ニーズに応じてトレードオフと選択を行うことです。
同期性の仮定を使用したコンセンサス アルゴリズムについては上で詳しく紹介しましたが、タイムアウトの概念を導入し、問題のあるコンピュータを無視することでコンセンサスを達成します。
非決定論的メカニズムを使用するナカモトのコンセンサスも簡単に説明できます。最も高いプルーフ・オブ・ワークを持つ提案されたブロックを見つけたら、そのブロック (最長連鎖ルールとも呼ばれます) を受け入れます。その具体的な実装プロセスは誰もがよく知っているので、この記事では繰り返しません。
ここで、同期性の仮定を使用するシステム (Finality、PoS でよく使用される) が、非決定性メカニズムを使用するシステム (Liveness、PoW でよく使用される) とどのように異なるかを見てみましょう。ただし、PoW に関する Finality コンセンサスを設計した人は誰もいませんが、すべての PoS が Casper FFG などの Finality ルートであるわけではなく、PoW は Liveness ルートに限定されないことに注意する必要があります。
PoW と PoS の違いは、一方がワークであり、もう一方がステークであることです。この点を強調する必要がある理由は、PoW と PoS に関する議論では、Work メカニズムと Stake メカニズムの違いについて議論するのではなく、Finality システムと Liveness システムの違いを比較することが多いためです。たとえば、「パーミッションフリー」は基本的に Finality システムと Liveness システムの間のトピックであり、Work と Stake の間の議論ではありません。
12人のレビュアーがいる部屋に戻りましょう。 Finalityを追求するためには、各レビューワが他の全員のアイデアを知る必要があり、また自分のアイデアを他の全員に伝える必要があるため、レビューワの数が増えるとコミュニケーションの複雑さが急激に増加し、システム全体が利用できなくなります。したがって、陪審員の数は管理されなければなりません。
次に、分散システムの場合、会議室に入るために少数のノードだけが選択され、それらのノードがコンセンサスを決定しますが、他のノードはコンセンサスのみを受け入れます。したがって、このシステムには、リーダー、フォロワー、学習者の 3 つの役割があり、リーダーとフォロワーは会議室のレビュー担当者であり、これらがうまく機能しなければ、システムは合意に達することができません。
中本コンセンサスはLivenessを追求しており、ノード/レビュワーは他のノードと通信する必要はなく、周囲のノードと通信するだけでよいため、ノード数の増加による通信の複雑さは増加しません。裁判官になりたければ、勝手に会議室に入って裁判官になることができ、陪審員の合意形成が困難になることはありませんが、同時に仕事をしたり、仕事を辞めたりすることはできません。時間。システムにはリーダーとフォロワーの 2 つの役割しかなく、全員がその会議室の合意に参加します。
ナカモトのコンセンサスは、分散システムのオープン性に対するみんなの期待により一致しているように見えますが、Finality が犠牲になっているため、この方法で設計できること、そしてその出力が確率的な最終結果であることを忘れないでください。
想像してみてください。スターバックスではコーヒー 1 杯が 100% 得られますが、スターバックスはお金を 100% 受け取っていません。これは、ほとんどの人が理解している世界のルールと一致しません。したがって、非決定論的なメカニズムには独自の欠点と不適切なシナリオがあります。
一方、ファイナリティ方式で結果の確実性が保証された後は、システム設計でLivenessを追求する必要があり、Liveness方式でネットワークのオープン性を確保した後は、逆にファイナリティを追求するシステム設計が必要になります。結果の確実性や安全性を高めるために、ナカモト・コンセンサスはTPSなど他の譲歩をする必要がある。
つまり、分散システムの設計はサタンと取引するようなもので、何かを得たり、何かを与えたりしなければなりません。最適なシステムというものはなく、特定のタイプの問題を解決するのに適したシステムがあるだけであり、単純なインデックスの比較はなく、どのような設定の下でこのインデックスを達成するかだけが存在します。
これを理解できれば、この記事の目的は達成されたことになり、分散システムの探索はここで終わりです。
6、さらに進んでください
リアンウェン 注:
- How Does Distributed Consensus Work?
この記事は、記事「分散コンセンサスはどのように機能しますか?」からインスピレーションを得たものです。分散システムについてさらに詳しく知りたい場合は、専門的な観点から分散コンセンサスを紹介するこの記事をお勧めします。また、「私たちが語るときのこと」もお勧めします。 DISTRIBUTED SYSTEMS」には、分散システムに関する古典的な論文が体系的にリストされています。
- WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS
リアンウェン 注:
- EthFans による「How Distributed Consensus Works」の中国語翻訳
分散システムにおけるもう 1 つの重要な問題はタイミングです。すべてのコンセンサス アルゴリズムがそれを解決する必要がありますが、これは別の手がかりであるため、この記事では取り上げません。知りたい場合は、レスリー ランバート博士から学ぶことができます (あなたは何歳ですか) ): 「分散システムにおける時間、クロック、およびイベントの順序」。
Finality と Liveness のバランスを見つけることに興味がある場合は、Liveness の一部と Finality の一部を備えた Casper FFG コンセンサスを研究してください。同時に、Casper FFG の PoS と Tendermint の PoS の違いもわかります。
最後に、この記事の要約を作成します。主に次の内容が含まれます。
2 つの定理: FLP 不可能性原理、CAP 不可能性定理。
2 種類のフォールト トレランス: ダウンタイム フォールト トレランス、ビザンチン フォールト トレランス。
2 つのコンセンサス アルゴリズム設計アイデア: Finality、Liveness。
3 つのコンセンサス アルゴリズム: Paxos、PBFT、サトシ ナカモト コンセンサス。
参考文献:
記事の簡略化や類推により、不正確な点や不完全な点があるかもしれませんが、ご了承ください。修正していただきありがとうございます。
2.《WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS》，Alvaro Videla
3.《Time, Clocks and the Ordering of Events in a Distributed System》，Leslie Lamport
4.《The Byzantine Generals Problem》，LESLIE LAMPORT、ROBERT SHOSTAK、MARSHALL PEASE
5.《Paxos Made Simple》，Leslie Lamport
6.《Bitcoin: A Peer-to-Peer Electronic Cash System》，Satoshi Nakamoto
