原作者：ソウルマシン
FLP不可能性の原理により、
No completely asynchronous consensus protocol can tolerate even a single unannounced process death
したがって、純粋な非同期ネットワーク用のコンセンサス アルゴリズムの設計に時間を無駄にしないでください。解決策は、ネットワークの要件を強化して、ネットワークが同期または部分同期であることを要求するか (非同期から同期または半同期に移行すると、ネットワークの状態が向上します)、ファイナリティの要件を緩和して、確定的なファイナリティを必要としないことです。 、確率的ファイナリティのみが必要です。両方を同時に行うことも可能です。
表 1 さまざまなコンセンサスアルゴリズムの比較
上記の表の内容については、以下で詳しく説明します。
Finality
FinalityはSafety、Consistencyと似ていますが、違うようで非常にわかりにくいです。
わかりやすくするために、Finality、Safety、Consistency は同義語、つまり Finality=Safety=Consistency と考えるとよいでしょう。
より深く理解するには、Finality は、Finality > Safety > Consistency という複雑な要素だと思います。一貫性は、Hadoop などの信頼できる環境やビットコインなどの信頼できない環境を含むすべての分散システムに適用できます。安全性はビザンチン環境に適用できます。ファイナリティはブロックチェーン シナリオの用語であり、ブロックチェーンはビザンチン シナリオのサブセットです (ビザンチン問題には非依存性があります)。 -ブロックチェーンに加えてブロックチェーン ソリューション)。一貫性は CAP 理論の C であり、より一般的で、ファイナリティよりも必要な要件が少なくなります。ファイナリティには、一貫性よりも多くのより強力な意味が含まれています。ファイナリティには、次のすべての意味が含まれます。
すべてのノードのデータは一貫している必要があります。クライアントは読み取り操作をどのノードに送信しても、結果は同じになるはずです。これは CAP で言及されている一貫性であり、この用語は、Hadoop などの信頼できる環境やビットコインなどの信頼できない環境を含む、すべての分散システムに適用されます。
すべてのノードは、相互に競合や分裂の状態にならないこと、つまり安全性を確保する必要があります。この用語は、ビザンチン フォールト トレランスの分野に適用されます。ビザンチンのようなオープン環境では、悪意のあるノードが 2 つの矛盾するメッセージ (二重支払いトランザクションなど) をブロードキャストし、ネットワーク全体のすべてのノードをスプリット状態に陥らせます。 、一貫した を達成できず、安全性の性質が破壊されます。すべてのビザンチン コンセンサス アルゴリズムは、ネットワーク全体の安全を確保するために悪意のあるノードの問題に対処する必要があります。
トランザクションがブロックに入ると、それは取り消し不能、つまり不変性でなければなりません。ブロックチェーンのシナリオでは、安全性を確保するには、悪意のあるノードによって発行されたトランザクションの二重支払いの問題に対処するだけでなく、悪意のあるノードがブロックにパッケージ化されたトランザクションを取り消すことを防ぐことも必要です。ブロックチェーンは単一リンクリストであり線形構造であるため、悪意のあるノードは理論的には古いブロックから開始し、より長い新しいチェーンをフォークし、送信したすべてのトランザクションをキャンセルして、自分のお金を再び使うことができます（別の形式のお金を使う）二重支出）
要約すると、ファイナリティ = 一貫性 + 安全性 + 不変性です。
Liveness
Liveness は、CAP における Availability と同等であると考えることができます。光海底ケーブルが断線し、世界のインターネットが二つに分断されるなど、ネットワークに分断が生じた場合、ブロックチェーンシステム全体は正常に新しいトランザクションを書き込むことができるのでしょうか？ Finality のコンセンサス アルゴリズムが好きです。現時点では、無期限に待つことにします。海底光ケーブルが修復され、双方のインターネットが相互運用可能になるまで、新しいトランザクションを書き込むことはできません。Availability のコンセンサス アルゴリズムが好きです。現時点では、この 2 つがネットワークが独立して動作し、データが分離され、フルノードのデータが不整合になります。
たとえば、Tendermint はこのタイプで、Liveness を犠牲にして決定的な Finality を追求します。海底ケーブルが破損し、ネットワークが 2 つの側に分割されていると仮定すると、各側にバリデーターの半分が存在するため、投票とコミットの段階では、各側のすべてのバリデーターが特定の提案ブロックに 100% 投票し、ブロックされた提案のみを受け取ることができます。最大でも提案の 50% がブロックされ、投票は 2/3 に達しないため、ブロックチェーン ネットワーク全体は 2/3 の投票が集まるまで無期限に待機します。この待機期間中は、次のブロックを生成できず、新しいトランザクションを書き込むことができず、ネットワーク全体が麻痺します。
ビットコインがこの種のネットワーク分割に遭遇しても、ビットコイン システムの 2 つの部分は前進を続け、新しいトランザクションを書き込んで新しいブロックを生成することができます。海底ケーブルが修復され、両側のインターネットが接続されると、 「結合」を選択します。
次の図に示すように、海底光ケーブルが切断される前は、世界中のすべてのフル ノードのステータスは一貫しています。
海底光ケーブルが切断されると、グローバルネットワークは 2 つの部分に分割され、2 つの部分は独立してブロックを生成します。このとき、双方は矛盾していますが、お互いを認識することができず、まだ線形ブロックチェーンであると考えています。 、次の図のように:
左側と右側では、新しいブロックが 10 分ごとにマイニングされていますが、左側の block07 と右側の block07 のブロック ハッシュは等しくありません。現時点では、ビットコインネットワークはまだ利用可能ですが、ファイナリティは破壊されています。
海底光ケーブルが修理されると、この時点で、次の図に示すように、双方でブロックが同期され、分岐があることが認識されます。
これで世界中のフルノードの状態は上の図のようになり、フォークが存在しますが、両側の高さが8なので、どちらのフォークが正しいか判断することはできません。マイナーのサポートとどちらの側がカウントされます。リガオ、どちらの側が最初に新しいブロックを持っていて、次にどちらの側が勝ち、短いチェーンが破棄されます。たとえば、右側が最初に新しいブロックを持っている場合は、右側が勝ちます。すべてのフル ノード内のデータは再び線形ブロック チェーンになり、次の図に示すようにコンセンサスに達します。
実際、海底光ケーブルが連続していてネットワークに分割がなくても、2人の鉱山労働者が同時に新しいブロックを掘り出すことはよくありますが、このときはどちらが運がいいかを競うのです。そして、次の新しいブロックが継承するフォークが勝ちます。つまり、理論上、ビットコインは決定論的な一貫した状態を持つことはなく、フォークはいつでも、どの高さでも現れるため、ビットコインはより強力なライブネスと引き換えにファイナリティを少し犠牲にします。
Network Assumption
すべての分散コンセンサス アルゴリズムには、ネットワークに関する暗黙の仮定があります。
まずネットワークの分類について説明します。
同期: メッセージは特定の時間 T 以内に配信される必要があります。上限の値 T は既知の定数であり、すべてのノードがそれを知っています。メッセージが T 時間以内に配信されない場合、メッセージはカウントされず、ノードはメッセージが失われたと判断し、メッセージを待ち続けません。どのノードも整然としていて、Tが通過するたびに1歩前に進んでいくのがとてもきれいです。
準同期: メッセージは一定の時間 T 以内に配信されなければなりませんが、T の値は固定値ではなく、ネットワークの状況に応じて動的に計算されるなど、動的に変化します。すべてのノード
非同期: メッセージはいつでも到着しますが、非常に速い場合もあれば、非常に遅い場合もあります。つまり、明確な上限はなく、さらには無期限の遅延さえありません。ノードはメッセージを受け入れて処理する必要がありますが、タイムアウトのため単純にメッセージを破棄することはできません。
ネットワーク上のビットコインの前提は、ネットワークが同期していることです, 制限時間は約 10 分です. マイナーがブロックを掘り出した後, ネットワーク全体にブロードキャストします. この時点で, ビットコイン システム全体はこのブロックが期待されています.オンラインのフル ノードがそれを受信しました。つまり、10 分ごとに、すべてのフル ノードがきちんと 1 歩前進する、つまり、自身のブロックチェーンの最後にブロックを追加します。ネットワーク速度が非常に速い場合でも、たとえば 3 分未満で、この新しいブロックはすべてのフルノードによって受信され、ビットコインは引き続き 10 分ごとに前進します (新しいブロックが生成されます)。イーサリアムも同様ですが、制限時間は15秒です。
Tendermint は、提案フェーズではネットワークが半同期であると想定します。このステップにはタイムアウト期間があるためです。時間が経過しても新しい提案ブロックが受信されない場合、他のバリデーターは提案者ノードがハングアップしたと判断します。次の提案者へのラウンドロビンまで空のブロックが生成されます。 Tendermint は、prevote と precommit の両方で投票の 2/3 以上を収集する必要があり、無限に待機します。つまり、これら 2 つの段階では、ネットワークが非同期であると想定されます。最終的に、Tendermint のネットワーク要件は半同期です。
pBFT は、pre-prepare、prepare、commit の 3 つの段階で非同期ですが、非同期であり、タイムアウト機構がないため、どのように処理を進めることができるでしょうか。 2/3以上集めたら先に進むことができます。ただし、すべてのノードはクライアントからのリクエストを受信するとタイマーを開始し、一定時間内にリクエストが完了しない場合はビュー変更がトリガーされます。ビュー変更セクションは半同期です。
ここでは、pBFT と比較して Tendermint が簡素化されていることがわかります。 Tendermint は、タイムアウト メカニズムを提案ステージ (pBFT の事前準備ステージに相当) に移動しました。プロポーザーが指定された時間内に提案ブロックをブロードキャストすると、次のステップに進みます。タイムアウトになった場合も、次のステップに進みます。ただし、これは提案ブロックが空のブロックであるということです (ブロックが空の場合、事前投票と事前コミットのプロセスは完全に完了しますが、ブロックの高さは 1 増加しません。これは同等です)次のラウンドロビンまでネットワークがアイドリングされます。新しい提案者ノードが新しい提案ブロックを再ブロードキャストします。つまり、いずれにしても提案段階は次のステップに進むことになります。ただし、Tendermint の事前準備は非同期であるため、永久に停止する可能性があります。 pBFT はタイムアウト メカニズムをビュー変更部分に移動したため、pBFT には追加のビュー変更ステップがあり、これは Tendermint よりも少し複雑です。 Tendermint は空のブロックとラウンドロビンを送信することでプロポーザー ノードを置き換えますが、pBFT は View Change を通じてプライマリ ノードを置き換えます。 Tendermint では、複雑なビュー変更手順が不要になります。
ビューの変更を排除することに加えて、Tendermint は別の場所でも簡素化されており、Tendermint のすべての情報はブロックチェーンに保存されます。しかし、pBFT が提案されたのは 1999 年で、当時はブロックチェーンなど存在していなかったので、pBFT のすべてのノードは一貫したデータを保持しますが、データは分散的に保存されます。 pBFT の各ノードのデータには以下が含まれます。
The state of each replica includes the state of the service, a message log containing messages the replica has accepted, and an integer denoting the replica’s current view.
ブロックチェーンは分散データベースであり、たとえば、MySQL などの DBMS データベースが登場する前、人々はデータをファイルに書き込んでハードディスクに保存し、さまざまな奇妙なファイル形式や編成方法を発明しました。 MySQL を使用すると、データの管理がはるかに便利になります。同様に、Tendermint はすべてのデータをブロックチェーンに保存しますが、pBFT はブロックチェーンのような分散データベースを持たず、メッセージ ログを圧縮したり、古いメッセージを破棄したりするために、すべてのノードがハードディスク上のデータを独自に管理する必要があります。ハードディスクのスペースを節約するには、チェックポイントの概念が導入されます。
Tendermint と pBFT の関係は、Raft と Paxos の関係に似ており、Tendermint は pBFT の簡略化されたバージョンであり、ブロックチェーン シナリオ用の pBFT の簡略化されたバージョンです。
次の図は、Tendermint のアルゴリズム フローチャートです。
次の図は、pBFT のアルゴリズム フローチャートです。
参考文献
参考文献
1999.Castro. Practical Byzantine Fault Tolerance
Tendermint: Byzantine Fault Tolerance in the Age of Blockchains
Consensus Compare: Casper vs. Tendermint
A Proof of Stake overview
Compared with traditional PBFT, what advantage does Tendermint algorithm has?
Synchronous, partially synchronous and asynchronous consensus algorithms
GRANDPA Block Finality in Polkadot: An Introduction (Part 1)
Finality in Blockchain Consensus
