分析的コンセンサスアルゴリズムの分類 (パート 1)

—— Part1 コンセンサスの分類 ——

初期の分散型コンセンサス アルゴリズムのゆっくりとした開発から今日のブロックチェーン コンセンサスの隆盛に至るまで、コンセンサス アルゴリズムの開発には約 40 年がかかりました。コンセンサスアルゴリズムが異なれば焦点も異なるため、直面する問題や環境も異なります。この記事では、次のさまざまな観点からコンセンサス アルゴリズムを分類します。

▲耐障害性タイプ

ビザンチン エラーが許容されるかどうかに応じて、コンセンサス アルゴリズムは 2 つのカテゴリに分類できます。

1) ビザンチンフォールトトレラントコンセンサスアルゴリズム: PBFT、PoW、PoS、DPoS

2) 非ビザンチンフォールトトレラントコンセンサスアルゴリズム: Paxos、Raft

Byzantium を許容するかどうかは、アルゴリズムが信頼性の低いネットワークに適用できるかどうかを示します。一般に、パブリック チェーン環境ではビザンチン フォールト トレラント アルゴリズムを使用する必要がありますが、アライアンス チェーンではアライアンス参加者間の信頼度に応じて選択できます。

▲ アルゴリズムの決定論

アルゴリズムの確実性に従って、コンセンサス アルゴリズムは 2 つのカテゴリに分類できます。

1) 決定論的コンセンサスアルゴリズム: Paxos、Raft、PBFT

2) 確率的コンセンサスアルゴリズム：PoW、部分PoS

決定的コンセンサスとは、一度コンセンサスの決定に達すると、ロールバックの可能性がないことを意味します。通常、このカテゴリは、従来の分散型コンセンサス アルゴリズムとその改良版です。確率的とは、到達したコンセンサス決定が将来一定の確率でロールバックされることを意味します。この確率は時間の経過とともに 0 になる傾向がありますが、このタイプのブロックチェーンは通常、パブリック チェーンに適用されます。コンセンサス アルゴリズム。

▲主な選考戦略

リーダーを選択する戦略に応じて、コンセンサス アルゴリズムは 2 つのカテゴリに分類できます。

1) 選挙コンセンサスアルゴリズム: Raft、PBFT

2) 証明コンセンサスアルゴリズム: PoW、PoS

選挙型コンセンサスとは、投票によるブロック生成ノードの選択を指します。同じノードが複数の連続するラウンドでブロック生成ノードとして存在することができます。通常、このカテゴリは、従来の分散型コンセンサス アルゴリズムとその改良版です。証明型コンセンサス アルゴリズムとは、ブロックを生成する権利を得るために、ブロック生成ノードが特定の方法で特定の能力を持っていることを証明する必要があることを意味します。このタイプのコンセンサス アルゴリズムでは、通常、異なるブロック生成ノードが存在します。通常、ブロック権利の公平性はパブリック チェーンに適用されます。

—— Part2 非ビザンチンフォールトトレラントコンセンサスアルゴリズム——

Paxos

Paxos は、非同期ネットワーク モデルの下で正確性とフォールト トレランスを保証できる最初のコンセンサス アルゴリズムです。これに先立ち、FLP は、非同期ネットワーク モデルでは、ノード障害がある限り、終了できるコンセンサス アルゴリズムを持つことは不可能であると明確に指摘しました。したがって、Paxos は一定の犠牲も払っています。Paxos は、システムのセキュリティを確保するために、一定量のアクティビティを犠牲にしました。つまり、システムが非同期状態にある場合、コンセンサスの進行は一時停止され、それ以上である限り、コンセンサスは中断されます。ノードの半分が同期状態に戻り、コンセンサスを促進して終了を完了できます。

画像の説明

図 1. Paxos の基本的なコンセンサスプロセス

文章

Raft

確かにPaxosは分散型コンセンサスアルゴリズムの基礎を築いたともいえる、非常に影響力のあるコンセンサスアルゴリズムですが、その理解と実装が難しいため、完全なPaxosアルゴリズムを実装することは非常に困難です。したがって、多くの Paxos の亜種が存在しており、その中で最も有名なものは Raft コンセンサス アルゴリズムです。

Raft は、ログ レプリケーションを管理するためのコンセンサス アルゴリズムであり、理解しやすいように設計されています。 Paxos はフォールト トレランスとパフォーマンスを備えていますが、違いは一貫性の問題を 3 つの比較的独立したサブ問題、つまりリーダー選出 (リーダー選出)、ログ レプリケーション (ログ レプリケーション)、およびセキュリティ (安全性) に分解していることです。これにより、Raft の理解が深まり、実際のシステムの構築に適用しやすくなります。

Raft では、各ノードは次の 3 つの状態のいずれかでなければなりません: Leader (マスター ノード)、Candidate (候補ノード)、Follower (スレーブ ノード)。通常の状況では、1 つのノードのみがリーダーであり、残りのノードはフォロワーになります。リーダーは、クライアントからのすべてのリクエストを処理する責任を負い (クライアントがフォロワーと通信する場合、フォロワーはリーダーに情報を転送します)、ログ データ (ブロックチェーンのパッケージ化に相当) を生成し、それをフォロワー ノードにブロードキャストします。フォロワーは受動的です。積極的にリクエストを送信することはなく、リーダーから一方向でのみログ データを受信できます。候補は、次のリーダーを選出するプロセス中に発生する移行状態であり、どのノードも候補になり、プライマリ ノードの障害が検出された後にリーダーになる可能性があります。

Raft アルゴリズムは、時間を任意の長さの用語 (用語) に分割します。任期は連続番号で表されます。すべての任期は選挙から始まります。候補者が選挙に勝った場合、その候補者は残りの任期にわたってリーダーを務めます。場合によっては票が割れてリーダーが選出されず、その後新たな任期が始まり、すぐに次の選挙が始まる可能性もある。

画像の説明

文章

要約する

Paxos と Raft は両方とも、非ビザンチン フォールト トレラント テクノロジであるクラッシュ フォールト トレランス コンセンサスです。非ビザンチンとは、分散システムにクラッシュ障害があるが、悪意のある (破損した) ノードのシナリオはなく (つまり、メッセージが失われるか繰り返される可能性があるが、エラー メッセージは存在しない)、分散システムであることを意味します。コンセンサスフィールド。最も一般的な質問。 Paxos と比較すると、Raft はより簡潔でありながら、同じフォールト トレランスとパフォーマンスを保証します。

文章

  PoW

Proof of Work (PoW) は、1993 年に Cynthia Dwork と Moni Naor によって学術論文 [3] で初めて言及され、同年に「Proof of Work」の概念が Markus Jakobsson と Ari Juels によって正式に提案されました [4] 。当初、PoW は主にスパムを防ぐために使用されていました。 2008 年に、PoW がコンセンサス アルゴリズムとしてビットコイン システムに適用されました。 PoW には次の 3 つの基本属性があります。

1) 数学パズル: PoW コンセンサス アルゴリズムは数学パズル (数学パズル) を設計します。このアルゴリズムでは、ノードが新しいブロックを生成する前にパズルの解を得るために特定のコンピューティング リソースを消費する必要があり、それによってブロックがネットワークや他のノードにブロードキャストされます。この解決策の有効性を検証するのは簡単です。

2) ハッシュ アルゴリズム: ハッシュ アルゴリズム (Hash Algorithm) は、任意の長さの入力を固定長の出力に変換できるアルゴリズムで、y = hash(x) として記録でき、出力 y は異なる入力 x から得られます。変化する。さらに、x が既知の場合、y はすぐに計算できますが、y が既知の場合、x は網羅的な方法でのみ逆推定できます。ハッシュ アルゴリズムは早送りと逆戻りが難しいという特徴があるため、PoW の数学的問題の設計によく使用されます。

3) ブロック生成: ブロック生成のラウンドでは、システムは出力値に条件を設定することで数学問題の難易度を調整し、ノードが問題を正常に解決し、チェーン上の検証に合格した後、対応する報酬を受け取ります。 。

新しいブロックを生成する前に、PoW は目標値を事前に設定し、ブロック生成ノードによって計算されたハッシュ値が PoW の難易度を表すために目標値未満であることを要求します。ブロックを生成して報酬を得るために、ブロックプロデューサーはまずトランザクションのセットを収集してブロックにパックし、ブロックを生成するための数学的問題を解決しようと試み始めます。

この期間中、ブロック生成ノードは乱数を生成し、現在のブロック データと前のブロックのハッシュを使用して複数ラウンドのハッシュ演算を実行し、現在のブロックのハッシュ値を計算する必要があります。

現在のブロック ハッシュが条件を満たすまで:

画像の説明

文章

PoS

前述のproof-of-workコンセンサスアルゴリズムは、コンピューティングパワーを利用して「リーダー」の資格を競いますが、proof-of-workの過程で多量のリソースが浪費されるため、受け入れが困難です。大規模なアプリケーション。これに関連して、一部の人々は「リーダー」資格の選出基準として「ステーク」を直接使用しようとし始め、その後、プルーフ・オブ・ステーク（PoS）コンセンサス・アルゴリズムを生み出しました。

PoSのアイデアは社会から来ています。つまり、人がより多くの株式を所有するほど、より多くの配当と配当金を受け取ることになります。このようにしてブロックチェーンシステムも維持されれば、過剰なリソース消費を必要とせず、ブロックチェーン資産の自然なインフレを引き起こす可能性もあります。ノードは一定量のトークンを投資することでコンセンサスに参加し、新しいブロックをパッケージ化する権利を獲得し、トークン保有量に応じて報酬を受け取ります。現在、イーサリアムには PoS に切り替えるイーサリアム 2.0 計画もあります。

トークンの保有状況を説明するために、PoS コンセンサス アルゴリズムには「コイン エイジ」の概念が導入されています。コインエイジは、ノードがパスの一部を保持する期間を示します。ノードがパスを「シェア」として投資すると、パスのこの部分にコインエイジが蓄積され始めます。コインエイジの計算方法は次のとおりです。以下に続きます:

パスのこの部分を使用した後は、ブロック生成に使用されるか単純なトランザクションに使用されるかに関係なく、パスのこの部分に対応する通貨年齢は破棄されます。独自のPoSコンセンサスアルゴリズムではコイン年齢が重要な判断基準となっており、ノードがブロック生成時に使用するコイン年齢が高いほどブロック生成が容易となり、短期的な投機をある程度制限することができます。

PoS コンセンサス アルゴリズムはブロックを生成するときに、コインの年齢とハッシュ操作の難易度の両方を考慮するため、ノードはブロック生成を完了するためにごくわずかなコンピューティング リソースを消費するだけで済みます。

DPoS

Delegated Proof of Stake (DPoS) コンセンサス アルゴリズム [5] では、選挙人はブロックを直接生成する代表を選出し、選挙人は代表の選出を通じて間接的にブロックを争う権利を行使します。委任されたプルーフ・オブ・ステークのコンセンサスアルゴリズムは、実際には一連の選択ルールを通じて候補者を制限し、一連の投票ルールを策定します。一般の参加者が候補者の中から委任者を投票によって選出し、委任者がブロックを作成し、要件を満たさない委任者は剥奪され、新たな委任者が再選されます。

DPoS は特定の集中化機能を保持しているため、高効率のトランザクション スループットを保証でき、その速度は Visa、Mastercard などの一般的な集中化機関と比較できます。このアルゴリズムでは、主にブロック生成権の制御性に分散性の特徴が反映されています。つまり、株主は投票して信頼できる代表ノードを選択し、代表ノードがブロックチェーン データを維持します。

——Part4 まとめ——

上記のコンセンサス アルゴリズムは、主にビットコイン、イーサリアムなどのパブリック チェーン シナリオで使用されます。パブリック チェーン シナリオではノードの規模が大きいため、決定論的な分散型コンセンサス アルゴリズムを採用するのは困難です。 PoW は、Proof of Work を通じてより高いセキュリティと分散化を実現します。PoW と比較して、PoS はエネルギー消費を削減するためにある程度のセキュリティを犠牲にしますが、DPoS はより抜本的な方法を使用してより少ないノードを選択してコンセンサス効率を向上させます。

著者について

著者について

参考文献

FunChain技術部 基盤プラットフォーム部 コンセンサスアルゴリズム研究グループ

参考文献

[1]Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.

[2] Chandra T D, Griesemer R, Redstone J. Paxos made live: an engineering perspective[C]//Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.

[3] Dwork C, Naor M. Pricing via processing or combatting junk mail[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992: 139-147.

[4] Jakobsson M, Juels A. Proofs of work and bread pudding protocols[M]//Secure Information Networks. Springer, Boston, MA, 1999: 258-272.

[5]Delegated Proof of Stakehttps://github.com/dacplayproject/cpp-play/wiki/Delegated-Proof-of-Stake