Tendermintコンセンサスアルゴリズムの詳細な説明

BFTF技术社区联盟

特邀专栏作者

2018-10-18 15:36 (UTC+8)

この記事は約5584文字で、全文を読むには約8分かかります

Tendermint アルゴリズムの中心となるプロセスは何ですか? Tendermint にはどのようなロックメカニズムが暗示されていますか?

AI要約

展開

Tendermint アルゴリズムの中心となるプロセスは何ですか? Tendermint にはどのようなロックメカニズムが暗示されていますか?

原作者：ソウルマシン

原作者：ソウルマシン

Tendermint は、pBFT アルゴリズムのバリアントである Tendermint のオープンソースプロジェクトです。Tendermint と pBFT の関係は、Raft と Paxos の関係に似ています。Tendermint は、pBFT の簡易バージョンです。

アルゴリズムコアプロセス

Tendermint のコアアルゴリズムフローを次の図に示します。

Tendermint アルゴリズムは、最初にいくつかのノードをバリデーターとしてランダムに選択し (検証ノードを選択する方法は? 以下の「検証ノードの選択方法」を参照)、次にバリデーターの 1 つを提案者ノードとして選択します。プロポーザーノードはネットワーク全体のすべてのトランザクションの監視と収集を開始し、数分後に新しいブロックを組み立ててネットワーク全体にブロードキャストします。これがプロポーザルブロックです。この提案ブロックを受信した後、ネットワーク全体のすべてのバリデーターノードは、このブロック内のすべてのトランザクションを読み取り、1 つずつ検証し始めます。問題がなければ、投票前投票メッセージを送信し、これへの同意を表明します。ブロック内に不正なトランザクションがあることが判明した場合は、否定票を投じ、これらの投票メッセージはすべてのバリデーターノードにブロードキャストされるため、各バリデーターノードは、投票メッセージだけでなく、他の人の投票メッセージも収集します。同意された投票の数が 2/3 を超えると、投票の第 2 段階である事前コミット投票メッセージが送信され、各ノードも事前コミット投票メッセージを監視および収集します。投票メッセージをコミットします。バリデーターノードによって収集されたコミット前の投票数が 2/3 を超えた場合、そのブロックは大多数の人によって承認されたことを意味し、このブロックをローカルブロックチェーンに安全に書き込み、ブロックチェーンの末尾に追加できます。コミットを完了します。同時に、ブロックの高さが 1 増加し、提案者ノードのインデックスも 1 増加して、次のラウンド (ラウンド) に入り、新しいブロックの提案を開始します。

上記の説明は 90% の確率で正常なプロセス、つまり青い矢印で示される大きなサイクルです。次に、内側の円の赤い矢印で示された小さなループについて説明します。ほとんどの場合、ブロックは確認を完了して合意に達するまでに 1 ラウンドのみを必要としますが、ネットワークの状態が悪くタイムアウトが頻繁に発生する場合があり、このときは内側の円の赤いプロセスに入ります。各ラウンドでブロックを生成する権利を持つプロポーザーは 1 人だけなので、プロポーザーが電話を切ったり、ネットワークが悪くてタイムアウトになった場合はどうすればよいでしょうか?誰もがこの提案者を永遠に待つことは不可能です。アルゴリズムは明らかにそれほど愚かに設計されておらず、明らかな単一障害点があります。提案者ノードの提案フェーズでは、すべての検証ノードがタイマーを開始し、タイムアウト期間を T に設定します (T の値はネットワーク状況に応じて動的に計算されます)。この期間内に提案者ノードからの新しいメッセージが受信されない場合、時間ブロックでは、提案者ノードがハングアップしていると見なされ、すべての検証ノードは待機し続けず、ローカルマシン上で特別な構造を持つ空のブロックを即座に生成し、空のブロックが提案者ノードから受信されたかのように見せかけます。したがって、何があっても、時間 T 以内に、通常のブロックまたは空のブロックのいずれかの提案ブロックが受信されます。次に、このブロックに対する事前投票と事前コミット投票に進みます。プロポーザーが電話を切ると、ほとんどのバリデーターには空のブロックが表示されるため、空のブロックが過半数の票を獲得し、コミット段階に入ります。空のブロックをコミットする場合、実際には空のブロックをブロックチェーンに書き込むのではなく、何も書き込まず、ブロックの高さも自動的に増加せず、変更されないままになります。これは、何もしないのと同じです。アイドリング中です。このラウンドは終了し、次のラウンドが始まると、バリデーターがプロポーザーとして置き換えられ、現在一時停止されているプロポーザーがネットワーク全体でスタックすることはありません。

ネットワーク通信の複雑さ

Tendermint のネットワーク通信の複雑さは O(n2) です。2 つの投票ステージで、各バリデーターノードが 2/3 を超える投票メッセージを収集する必要があり、ネットワークによって送信されるデータパケットの数が n2 であるため、ネットワークの同心円の複雑さは次のようになります。 O(n2)。提案フェーズでは、新しいブロックはすべてのバリデーターによって受信されるだけでよく、ネットワーク通信の複雑さは O(n) です。全体としては O(n2) です。ネットワーク通信の複雑さはO(n2)であり、Tendermintのノード数はあまり多くないのが宿命であり、多すぎるとネットワーク通信がボトルネックとなるため、Tendermintはプライベートやアライアンスに適しているこれは論文の 17 ページにも明記されています 1 点: Tendermint は、コンソーシアムまたは組織間ロジック向けに最適化されたソリューションですただし、優れたシャーディングメカニズムと連携していれば、パブリックチェーンにも使用できます。それはまた別の話です。

ネットワーク仮説

Tendermint のネットワークに対する要件は、ネットワークが半同期である必要があることです。 Tendermint には提案フェーズでのタイムアウトメカニズムがありますが、このタイムアウト期間は一定ではなく動的に変化するため、この段階ではネットワークが半同期である必要があります。事前投票および事前コミット投票段階では、ネットワークに対する要件はありません。つまり、ネットワークは非同期です。したがって、Tendermint のネットワーク要件は半同期です。

ネットワークは投票前およびコミット前の投票段階では非同期であるため、投票の 2/3 以上が収集されない場合、すべてのバリデーターノードが無期限に待機することになり、システム全体が停止します。 Tendermint は、より強力な Finality と引き換えに Liveness を犠牲にしました。

たとえば、プロポーザーノードが特定のラウンドで新しいブロック blockX をブロードキャストし、バリデーター A ノードが新しいブロックを時間通りに受信しなかった場合、A はローカルマシン上で空のブロックを構築します。提案者が到着し、事前投票 nil 投票メッセージを送信し、事前投票ループに入り、タイムアウトタイマーを開始して、赤い内側の円のループに入ります。A はネットワークの監視と投票情報の収集を開始します。
指定された時間内に収集された投票数が、空のブロックまたはブロック X のいずれであっても 2/3 を超えなかった場合、投票の総数が 2/3 を超えるまで無期限に待機します。

総投票数の 2/3 以上を集めた後、空のブロックの投票数が 2/3 を超えた場合、事前投票 nil を発行して空のブロックに投票しますが、依然として赤い内側の円に留まります。 ; blockX の投票数が 2/3 を超えた場合 3. blockX に事前投票を送信し、青い外側の円に切り替えます; 空のブロックと blockX の投票数が 2/3 を超えない場合は、 pre-vote nil メッセージを使用すると、空のブロックに投票し、赤い内側の円のままでコミット前の段階に入ります。

A がプリコミット nil 投票メッセージを送信すると、A は依然として赤い内側の円内に留まり、プリコミットプロセスは上記と同様になります。全体として、赤い内側の円内のプロセスは、ネットワークが半同期であることを前提とする必要があります。

ファイナリティとライブネス

Tendermintのファイナリティは決定的であるのに対し、ビットコインのファイナリティは確率的であり、Tendermintのファイナリティはビットコインよりも強いです。

しかし、ライブネスの観点では、たとえば、ネットワークが分割されると、Tendermint は理論的にはスタックし、新しいトランザクションを作成できなくなります。一方、ビットコインは 2 つのフォークに分割され、それぞれが独立して動作し、新しいトランザクションは継続できます。

ロック機構

上の図では、図には示されていませんが、実際には暗黙的にロック機構が存在します。たとえば、ある R ラウンドには 4 つのバリデーターノード A、B、C、D があり、
提案フェーズでは、提案者ノードが新しいブロック blockX をブロードキャストします。
A はタイムアウト期間内に新しいブロックを受信できず、事前投票 nil を外部にブロードキャストし、B、C、D はすべて受信し、事前投票をブロック X にブロードキャストしました。
これで 4 つのノードがプリコミット段階に入りました。A は赤い内側の円内にあり、B、C、D は青い外側の円内にあります。
A のネットワークが貧弱で、指定された時間内にブロック X に対して 2/3 を超える投票を受け取っていないと仮定すると、空のブロックに投票するために事前コミット nil 投票メッセージを送信することしかできません。
D は B と C の事前投票メッセージと自分自身の投票メッセージを受信しましたが、2/3 を超えたため、D はローカルブロックチェーンに blockX をコミットしました
B と C のネットワークに問題があり、D はコミット前メッセージを受信できません。これは、B と C がブロック X に対して 2 票しか参照できず、空のブロックに対して 1 票しか参照できないためです。 2/3 なので、B と C C は空のブロックのみをコミットでき、高さは変更されず、R+1 ラウンドに入ります。A はブロック X に対して 2 票、空のブロックに対して 1 票のみを参照でき、空のブロックのみをコミットできます。、高さは同じまま、R+1ラウンドへ

R+1 ラウンドでは、新しい愛の提案者が新しいブロック blockY を提案したため、A、B、C が合意に達して blockY を提出する可能性があるため、同じ高さに 2 つの blockX と blockY ブロックが存在し、フォークが発生します。。

Tendermint は、特にステップ 7 でロックメカニズムを追加しました。提案者が新しいブロック blockY を生成した場合でも、A、B、C はステップ 6 のコミット前のブロックでのみロックできます。つまり、A はステップ 7 です。 6 ステップ 1 で空のブロックに投票した場合、ラウンド R+1 でのみ空のブロックに投票し続けることができ、ステップ 6 で B がブロック X に投票すると、新しいラウンドでは永久にブロック X にのみ投票できます。、Cも同様です。このようにして、R+1 ラウンドでは、空のブロックに 1 票、blockX に 2 票があり、最終的に blockX について合意に達し、A、B、C はすべて blockX をコミットします。これは D と一致します。、矛盾はありません。

テンダーミント vs. pBFT

Tendermint と pBFT は非常によく似ています。次に例を示します。
すべては BFT タイプのアルゴリズムに属しており、悪意のあるノードの最大 1/3 しか許容しません。
Tendermint の提案 -> 事前投票 -> 事前コミットの 3 段階は、pBFT の事前準備、準備、コミットの 3 段階に対応しています。

すべてがタイムアウトになったら、プロポーザー/プライマリを置き換えます。

不十分 Tendermint には、pBFT と比較して 2 つの簡略化があります。

Tendermint には pBFT の View Change ステージがありません. Tendermint はタイムアウト状況と通常状況を巧みに統合して統一された形式にします. それらはすべて提案 -> 事前投票 -> 事前コミットの 3 つの段階にあり、新しいブロックのみですタイムアウトが発生すると作成されます。特別な空のブロックです。プロポーザーの切り替えは空のコミットブロックを送信することでトリガーされますが、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.

ビューの変更を排除することに加えて、Tendermint は別の場所でも簡素化されており、Tendermint のすべての情報はブロックチェーンに保存されます。 pBFT は 1999 年に提案されたため、当時はブロックチェーンなど存在しませんでした (ブロックチェーンは 2009 年のビットコインの出現後にのみ利用可能になりました)。そのため、pBFT のすべてのノードは一貫したデータを保持しますが、データは分散された方法で保存されます。 pBFT の各ノードのデータには以下が含まれます。

ブロックチェーンは分散データベースであり、たとえば、MySQL などの DBMS データベースが登場する前、人々はデータをファイルに書き込んでハードディスクに保存し、さまざまな奇妙なファイル形式や編成方法を発明しました。 MySQL を使用すると、データの管理がはるかに便利になります。同様に、Tendermint はすべてのデータをブロックチェーンに保存しますが、pBFT はブロックチェーンのような分散データベースを持たず、メッセージログを圧縮したり、古いメッセージを破棄したりするために、すべてのフルノードがハードディスク上のデータを独自に管理する必要があります。ハードディスクの容量を節約するためのチェックポイントが導入されていますが、データ管理だけでも面倒な手順がたくさんあります。

Tendermint と pBFT の関係は、Raft と Paxos の関係に似ており、Tendermint は pBFT の簡略化されたバージョンであり、ブロックチェーンシナリオ用の pBFT の簡略化されたバージョンです。

バリデーターの選び方
まず、ジェネシスブロックで一連のバリデーターノードを静的に設定でき、次に、チェーンの開始時に ValidatorUpdate メッセージを送信してバリデーターリストを更新できます。バリデータの更新を参照してください

この文書ではこの点についてはあまり言及されておらず、比較的原始的なもののようですが、アルゴランドの暗号宝くじのようなランダムサンプリングアルゴリズムはありません。しかし、この場所はいつでも拡張できるはずです。

提案者を順番に変更する方法
バリデーターノードのグループが選択されると、ネットワーク全体のすべてのバリデーターノードがコピーを、たとえば円形配列に保存します。

通常、ブロックは 1 ラウンドで生成されることがほとんどですが、ネットワークの状態が悪い場合には、ブロックの生成に複数のラウンドがかかる場合があります。いずれの場合も、各ラウンドでは新しいバリデーターがプロポーザーとして選択され、ローテーションルールは単純に順番に増加します。最初のラウンドでは、配列内の 0 番目のバリデーターがプロポーザーとして選択され、2 番目のラウンドでは、最初のバリデーターが選択されるなど、最後のバリデーターに到達すると 0 にリセットされ、無限ループします。
次にコンセンサスアルゴリズムを開始し、0ラウンド目では位置が0のバリデーターを提案者ノードとして選択し、1ラウンド目では位置が1のバリデーターを選択し、2ラウンド目では位置が2のバリデーターを選択します。提案者として選択され、最後まで到達すると0にリセットされる無限ループ。

このラウンドロビン戦略により、タイムアウトになったプロポーザーノードを効果的にスキップできます。提案者ノードがハングアップしたり、ネットワークが貧弱な場合、ほとんどのノードは新しいブロックを時間通りに受信できません。そのため、タイムアウト後、各検証ノードはローカルに空のブロックを構築し、投票メッセージをブロードキャストアウトします。投票、投票、プリコミットを繰り返し、最後に空のブロックをコミットします。これは何もしないことと同じ高さで、新しいラウンドを開始します。新しいラウンドが開始されるたびに、次のプロポーザーに順番に置き換えられるため、ハングアップした提案されたプロポーザーノードは自然にスキップされ、アルゴリズムは自動的に続行されます。