はじめに
前回の記事では、関連する理論やアルゴリズムについて書きましたが、それらのアルゴリズムはブロックチェーンシステムでは使用できませんし、悪い状況を防ぐこともできません。
このセクションでは、ブロックチェーンでよく使われるコンセンサス・アルゴリズムを見てみましょう。まず、なぜ分散型ネットワークにコンセンサスが必要なのかを見てみましょう。
二軍問題
写真のように、白軍は強力で要衝にあり、青軍は白軍に離されて2軍となり、青2軍が合意に達した場合のみ、白軍を破ることができます。ただし、青1と青2が合意に達するためには、白兵戦の領地を通じて使者で連絡を取り合い、同時に攻撃して勝利する必要があります。しかし、白軍がメッセンジャーを捕獲する可能性があるため、2 つの青軍が合意状況に達することは不可能です。つまり、両軍問題は、メッセンジャーが信頼できないことを表しており、信頼できるメッセンジャーが存在すれば、両軍問題は解決できるのです。
両軍間の通信は、TCPの3回のハンドシェイクのように、双方が正しいメッセージを受信してコンセンサスに達したことを確認するために、フィードバックを送受信する必要があります。
ビザンチン将軍に関する質問
ビザンチン将軍の問題はコンセンサス問題の1つです。1982年に**Leslie Lambert**と他の2人によって初めて提起され、ビザンチンの失敗として知られています。中心的な説明は、軍隊の中に裏切り者がいるかもしれないが、攻撃は一貫していなければならないということです。分散システムとのアナロジーは、ノードの中に邪悪なノードがあり、それもハッキングされる可能性があるということです。
写真はちょっと醜いから、これで何とかしましょう（顔を覆って泣く）。
ビザンツ帝国はある強力な都市を攻撃しようと考え、そのために10個もの軍隊を派遣してこの敵を包囲しました。この敵はビザンチン帝国ほど強くはありませんでしたが、ビザンチンの正規軍5軍の一斉攻撃に耐えるには十分な強さでした。さまざまな理由から、この10個軍を一点に集めて突破することはできず、別々の包囲網で同時に攻撃しなければなりませんでした。敵国を占領するためには、少なくとも6軍が同時に攻めなければ、どの軍も単独では勝ち目がありません。彼らは敵国周辺に分散し、通信使を頼りに互いの意思を伝え合い、攻撃のタイミングを交渉しました。そんな将兵たちを悩ませたのは、将兵の中に裏切り者がいて、勝手に攻撃の意図やタイミングを変える者がいないかどうかわからないという問題でした。このような状況の中で、ビザンツの将軍たちは、戦いに勝つために遠隔で交渉できる分散プロトコルを見つけることができたのでしょうか？これが有名なビザンチン将軍の問題です。
ビザンチン将軍の問題では、通信している兵士が傍受されないか、メッセージを伝えることができないか、つまり、メッセージが配信されるチャネルが信頼され安全であるかといった問題は考慮されていないことは明らかです。Lamportは、メッセージが失われる可能性のある信頼性の低いチャネル上でのメッセージの受け渡しによって一貫性を達成しようとすることの不可能性を実証しました。以下は、安全で信頼できるチャネルであると仮定されています。
この問題は結局のところ一貫性と正しさに関するアルゴリズムの問題であり、このアルゴリズムは忠実な将軍のためのものです。裏切り者はパスを通さないか、メッセージに干渉してめちゃくちゃにすることができるからです。裏切り者が存在しても干渉を許容するアルゴリズムを見つけること、それがBFT Byzantine Fault Toleranceです。
このように、両軍の問題はビザンチン将軍の問題の特殊なケースです。
ビザンチン・エラーとは？
邪悪なノードやハッキングされたノード。ノードのダウンタイム、ネットワークの分割、タイムアウトなどはビザンチンエラーではありません。
ビザンチン将軍の問題を解決するには？
准将モデル
ビザンチン将軍問題では、各将軍は、他の将軍の攻撃の配置を知るために、すべての将軍と通信し、合意に達する必要があります。従って、ビザンチン将軍問題は、司令官-副官モデルに単純化することができます。複数の准将を持つ指揮官は、指揮官が出した命令が複数の准将に対して一貫した結果をもたらすことを保証する一貫性プロトコルを必要とします。
指揮官が命令をn-1人の副官に伝えているところ：
一貫性：すべての忠実な准尉は、ひとつの命令に従います。
正しさ：指揮官が忠実であれば、忠実な准尉はみな指揮官の出す命令に従います。
なぜBFTはノード数n>=3f+1を必要とするのですか？
fはビザンチンエラーノードの数であり、BFTが許容できる裏切り者の数です。
逆は、n＜3f+1、つまりf＝1のときn＝3であれば真。
- 司令官が忠実な場合、副官1人が忠実で、副官1人が裏切り者です。司令官が2人の准尉に攻撃命令を送ると、2人の准尉は互いに司令官の命令は何かと尋ねます。このとき裏切り者の准尉は、司令官の命令は退却であると偽の命令を偽造します。
- もし司令官が裏切り者なら、2人の副官は忠実。司令官は2人の副官にそれぞれ攻撃と退却の命令を与えますが、2 人の副官は連絡を取り合い、互いに同じ命令を受けず、同意もできないことに気づきます。
PBFT
BFTは、チャネルに問題がないこと、すなわち、メッセージの到達不能、メッセージの損失、ジャンブル、重複、ネットワークの分割などを考慮しないことを前提としています。pbftアルゴリズムは、1999年の論文Practical Byzantine Fault ToleranceでMiguel CastroとBarbara Liskovによって最初に提案され、そのアルゴリズムはフォールトトレランスの数も3f+1<=nを満たします。
pbftアルゴリズムの基本的なプロセスには、主に4つのステップがあります：
クライアントはマスターノードにリクエストを送信します。
マスターノードは他のノードにリクエストをブロードキャストし、ノードはpbftアルゴリズムの3段階のコンセンサスプロセスを実行します。
ノードは3段階の処理を行った後、クライアントにメッセージを返します。
クライアントがf+1ノードから同じメッセージを受信した場合、コンセンサスが正しく完了したことを意味します。
イメージは論文のスクリーンショット。この図ではマスターノードが忠実で、3番のノードがビザンチンノード。
PBFTは3段階の提出プロトコルです。
- クライアントはリクエストをマスターノードに送り、マスターノードはそれをシステム内のレプリカに配布するためのpre-prepareメッセージにパッケージします。
- レプリカノードはマスターノードからpre-prepareメッセージを受け取り、それを検証します。注意：マスターノードはprepareメッセージをブロードキャストしません。
- すべてのノードは、一定時間内に有効な異なる2fのPREPAREメッセージを受信した後、COMMITメッセージのブロードキャストを開始します。
- すべてのノードは2f+1個のコミットメッセージを受信し、今日の操作をコミットします。
完了したらクライアントに応答。クライアントは f+1 メッセージを受信して、運用コンセンサスの終了を判断します。
なぜクライアントはf+1のメッセージしか必要としないのですか？
仮にf個のメッセージが受信されなかったとして、そのf個のノードがビザンチン・ノードであることを見分ける方法がなく、最悪の場合、受信されたメッセージのf個がビザンチン・ノードからのものである可能性があるとします。フォールト・トレランスを維持するためには、忠実なノードの数がビザンチン・ノードの数よりも多い、つまりf+1個の忠実なノードが必要です。つまり、クライアントはf+1個の同じメッセージを受信するだけで、コンセンサスが成功したと結論づけることができます。
また、PBFTのフォールトトレランスはfのみに限定され、n >= f + f+ = 3f + 1となります。
PBFTには、マスターノードの切り替えに使用されるViewという概念もあります。レプリカノードとマスターノード間のハートビートがタイムアウトすると、マスターノード切り替えのためのビュー変更が開始されます。ビューが変更されるたびに、view=view+1となります。
マスター・ノード = view % n . ご覧のように、PBFTはポーリングを使ってマスターノードを選出します。PREPAREフェーズを見ると、マスターノードが悪ノードの場合、マスターノードがクラスタ内のように複数の異なるメッセージを送信するため、このフェーズでは2fのPREPAREメッセージを受信することができません。
ビットコインのPOWコンセンサス
POW(プルーフ・オブ・ワーク)は 、合法的な乱数の計算を利用して、悪のノードのコストを増加させます。悪事を働くには正規の nonce を計算する必要があるため、ブロックの情報を変更したい場合は、そのブロックから始めて、すべてのバックブロックについて正規の nonce を再計算する必要があります。そのため、ビットコインは10年近くPOWに依存して安全に運用してきました。POWについてもっと知りたい方は、私の記事「ビットコイン入門」をご覧ください。
POSコンセンサス
POS：プルーフ・オブ・ステーク。大きな言葉で言うと、コインを多く保有し、長く保有すればするほど、採掘できる確率が高くなり、より多くのコインを手に入れることができるということです。例えば、ダッシュコインを1,000枚保有していればマスターになることができ、マスターになれば採掘できるチャンスがあります。POSによってお金持ちはよりお金持ちになりますが、コインの年齢が一定の値に達すると0にリセットされます。これによって、新しく採掘に来た人と入れ替わることができ、貧富の差が大きくなりすぎないようにすることができます。
DPOSコンセンサス
DPOS: Delegated Proof of Interestの略。通常、DPOSはDelegated（委任）にあり、スーパーノードに自分の利権を預け、スーパーノードが自分の代わりにブロックを持ち出すことを選択し、委任された利権の割合に応じて自分の利権を得ます。興味のある方は、Bitshares、Steem、EOS、Aschなどのプロジェクトをご覧ください。
私は0から1までの2つのパブリックチェーンの開発に参加したことがあり、DPOSのアイデアも選択されていますが、どちらも自社開発のDPOSアルゴリズムです。DPOSについて私が理解しているのは、証人ノードは一定のルールで選択され、これらのノードは、マイナーたちがブロックをパックした後、ブロックのコンセンサスと検証にのみ責任を負うということです。マイナーは他の方法で選ぶことができます。選び方は様々で、ポイントを使うことも、クレジットスコアを使うこともできます。ネットワーク全体が同じデータを使い、計算された結果がユニークで、検証や追跡が可能であることを保証できる限り、問題はありません。
立会人ノード間のコンセンサスは、悪質なノードを防ぐという点で、基本的な考え方はBFTに遠く及びません。何か良いアイデアがあれば、お互いに話し合ってください。
概要
最後に、ブロックチェーンにおける一般的なコンセンサスアルゴリズムの一般的な議論、コンセンサスアルゴリズム、コンセンサスアルゴリズムのアイデアの主な理解は、私は個人的には、思考の拡大の実際の状況に応じて、特定のアルゴリズムによって投獄されるべきでないと思う、よりエレガントなコンセンサスアルゴリズムを作成することができるかもしれません。
重要：記事の誤りはご指摘ください。また、ブロックチェーンに関心のあるパートナーとの議論や交流も歓迎します。
::
