「フレアネットワーク☀️」コンセンサスプロトコルのホワイトペーパーの和訳

以下、フレアネットワークのホワイトペーパーから引用した文をDeeplにて和訳したコピペです。
引用: https://flare.network/wp-content/uploads/FCP-White-Paper.pdf
※問題があれば即消します。又、数式なども規格が合わない箇所がありますので実際のホワイトペーパーを参考にしてください。

Flare Consensus Protocol (FCP) は Federated Byzantine Agreement (FBA) の新しいコンセンサス構造である。FBAは、個々の参加者がクォーラムスライスを独立して決定できるため、合意を確保するための経済的メカニズムに依存しない。ネットワーク上のクォーラムスライス決定の重なりが、ネットワーク全体の合意のためのルールを生み出す。FCPはリーダーレスで完全順序型であるため、攻撃者がトランザクションセットで2つのトランザクションのうちどちらを先に注文するか影響を与えることが非常に困難である。また、FCPは非同期で、Federated Virtual Votingと呼ばれる新しい連合合意メカニズムを利用しているため、これまでのFBA構築よりもはるかにシンプルな構成となっています。これらの特性から、FCPはインターネットレベルのチューリング完全コンセンサスの有力なモデルである。

1 はじめに
潜在的に悪意のある参加者がいる分散システムで合意に達する問題は、ビザンチン将軍問題[LSP82]を通じて初めて紹介された。ここで、ネットワークの参加者は必ずしも信頼できるわけではなく、より広くはビザンチン障害のカテゴリに入る振る舞いである。これにより、分散システムは異なる観測者あるいは障害検出システムに対して予測不可能に障害と機能の両方に見えることがある。このような場合、メッセージの交換により、安全性として知られる非ビザンチン系参加者間の合意に達する必要がある[Bra87]。このようなシナリオにおいて、ビザンチン耐故障アプローチは、サービスを維持するために、すなわち十分な合意またはコンセンサスを得るために、正しく動作するコンポーネントが十分に存在すると仮定して、システムサービスの提供の継続性を確保しようとするものである。言い換えれば、ビザンチン合意は、閉じたシステム集合の中に特定の割合の誤動作する構成要素またはメンバーが存在する場合でも、合意を確保することができる。
例えば、従来、台帳は整合性を保つために、ある取引を受け入れるべきか否かを中央機関が判断し、その結果、台帳が更新されることが必要でした。実際、参加者は必ずしも正直ではないため、あるエンティティがコインを2回使ってしまうという二重支出の問題が核心的な懸念事項となっています。ビットコイン[Nak+08]プロトコルは、ネットワーク上に分散された暗号的に安全な公開取引台帳であるブロックチェーンを導入した。ここで、ネットワーク参加者は、各取引を受け入れるか拒否するか、また、取引の順序に同意するかについてコンセンサスを得る必要がある。オープンな分散システムにおけるコンセンサスは、Proof of Work [Nak+08]、Proof of stake [KN12; DN92] または Federated Byzantine Agreement (FBA) [Maz15] など、様々なメカニズムによって達成することができるが、それぞれ利点と欠点の両方を有している。
二重支出のような悪意ある行動は、より広い意味でのビザンチン障害の範疇に入る。これにより、分散システムは、異なる監視者や障害検出システムから、予測不可能に障害と機能の両方に見えることがある。このようなシナリオでは、ビザンチンフォールトトレランス(BFT)[PSL80]アプローチは、サービスを維持するために正しく動作するコンポーネントが十分にある、すなわち十分な合意またはコンセンサスを達成すると仮定して、システムサービスの提供の継続性を確保することを目指します。言い換えれば、ビザンチン合意[PSL80]は、閉じたシステム集合の中に誤作動するコンポーネントやメンバーが特定割合で存在しても、合意を保証することができます。
プルーフ・オブ・ステーク[8]のような純粋に経済学に基づくブロックチェーンプロトコルに関する緊急の懸念は、参加者のコアセットが有限かつ少量の資本、またはステークを活用してのみ確保される場合、そのようなシステムがネットワーク状態に表される大量の価値をどのようにしてサポートできるかということです。これがトップヘビー・ブロックチェーンの概念です。

Federated Byzantine Agreement (FBA) [Maz15]は、オリジナルのビザンチン合意のフレームワークをオープンで許可なしの設定に拡張し、Proof of stakeなどの安全を提供するための経済的ソリューションによってもたらされるトップヘビーなブロックチェーンリスクを本質的に回避しています。ネットワーク上の参加者の信頼の重なりが、合意のためのネットワーク全体のルールを定義します。つまり、従来のBAが参加者の対称的な信頼を必要とするのに対し、FBAは参加者の非対称的な信頼を可能にします。ネットワーク参加者の信頼が非対称であることで、各参加者がネットワークとやりとりする際の安全ルールを独自に定義することが可能になる。例えば、ネットワーク参加者のサブセットが特定の法的管轄区域に拠点を置いている場合、彼らは地元の規制機関からの表現を安全セットに含めることができます[SD19]。
Bitcoin [Nak+08]、practial BFT (pBFT) [CL+99]、XRP Ledger consensus protocol [SYB+14], BFT-CUP [Alc+08] or Stellar Consensus Protocol (SCP) [Maz15] などのように、様々な合意形成の仕組みが開発されていて、性能向上のための新しいアプローチが求められる研究分野でもある。例えば、仮想投票はHashgraphコンセンサスプロトコル[Bai16]で初めて導入され、その後Blockmaniaコンセンサスプロトコル[DH18]で活用された、コンセンサスネットワークの複雑性を軽減する技術で、広域ネットワーク上で高い処理能力で非常に速い最終決定を可能にするものである。しかし、仮想投票はSybil攻撃[Dou02]の影響を受けやすく、参加者が異なるIDで複数回ネットワークに参加することで、投票手順に悪意ある影響を与えることができる。このため、仮想投票ベースのネットワークは本質的にシビル攻撃を回避できず、プルーフ・オブ・ステーク[Dai98]のような回避のためのアドオン機構を導入する必要がある。
本論文では、Federated Byzantine Agreementのフレームワークとして、従来のStellar Consensus Protocol (SCP) [Maz15] に続く最新の構成であるFlare Consensus Protocol (FCP) を紹介する。FCPはSCPと比較して、以下のような利点があります。FCPはリーダーレス、非同期ビザンチン耐故障、全順序トランザクションを持ち、連合仮想投票と呼ばれる新しいネットワーク複雑性低減技術により、高いスケーラビリティを持つ。さらに、FCPは連合仮想投票と呼ばれる仮想投票の新しい一般化であり、従来の仮想投票技術と全く同じネットワーク複雑性の低減を維持しつつ、連合ビザンチン合意のフレームワーク内に存在することで本質的にシビル攻撃を克服している。
本論文は以下のように進められる。まず、第2章では、FBA構築に関連する必要な背景定義を紹介する。次に、第3節でFlare Consensus Protocolを紹介し、最後に第4節でFCPを関連するコンセンサスアルゴリズムと比較する。

2 前提条件
FCPは、Hashgraphコンセンサスプロトコル[Bai16]によって導入された仮想投票と同様に、FBAのフレームワークをベースにしている。FCPはグラフに関するアイデアに依存しており、次にこれを紹介する。次に、FBAの主要なアイデアと、本論文で使用する用語、およびプロトコルを支えるいくつかの主要な前提を示す。
2.1 グラフ理論
グラフG = (V, E)は、頂点Vと有向辺Eの集合からなる。有向非循環グラフ(DAG)は、サイクルを持たない有向グラフである。頂点u∈Vからv∈Vへの有向辺は(u, v)と書かれ、つまり順序が重要である。u∈Vからw∈Vへの長さnのパスは、vi∈V,i=0,...,n-1で、v0 =uandvn =wで、(vi,vi+1) ∈Eとなる頂点v0,...,vnの連続である。この関係は、a→b、b→cはa→cを意味するという部分順序を生成する。
anc(u)をu∈Vの祖先の集合、すなわち anc(u) = {v ∈ V|v → u}とする。uの親は、(v, u) ∈ Eとなる任意の頂点v∈Vである。
2.2 Federated Byzantine Agreement (FBA)について
従来のビザンチン協定ネットワークは、安全性を確保するために(N -1)/3 の故障にしか耐えられない(N は参加者の数)。統合ビザンチン協定ネットワークは必ずしもこの制限を受けず、ネットワーク全体の定足数重複の特性によって、相当数のノード故障に耐えることができる。この特性により、FBAネットワークは本質的にシビル攻撃を回避することができる。なぜなら、ノードはクォーラムスライスセット内に信頼できない悪意のあるノードを含めないことを独自に選択することができるからである。
ステラ・コンセンサス・プロトコル(SCP)[Maz15]はFBAのための構成であり、図1と図2に示すように、他のFBA構成がSCPと同等以上の安全性を保証できるような最適な安全性を達成するものである(定義2.1参照)。重要な特徴は、ネットワークの参加者が、クォーラムスライスとして知られる、信頼したい他者を選択できることである。このため、個々のノードはクォーラムスライスの決定を独立して行うことができる。その後、市場原理によりネットワーク上でクォーラムスライスの決定が重なり、ネットワーク全体の合意形成のためのルールが生じる。取引はネットワークの十分な数のノードがそれを受け入れたときに決済され、これは投票手続きによって達成される。

定義2.1.[Maz15] FBAS 連立ビザンチン合意システム、またはFBASは、ノードVのセットと、各ノードに対して1つ以上のクォーラムスライスを指定するクォーラム関数Q : V → 22V {φ}からなるペア⟩で、ここで、あるノードは自身のクォーラムスライスのすべてに属する(すなわち、∀v∈V∀q∈Q(v)∀v(q)∀q)。
ノードはそれ自身のクォーラムスライスのすべてに属します。つまり、∀v∈V, ∀q∈Q(v), v∈q.
したがって、クォーラムは、各ノードがクォーラムに含まれる少なくとも1つのクォーラムスライスを有するノードの集合として定義することができる。非連邦ビザンチン協定では、すべてのノードが同じスライスを受け入れる必要があり、したがって、クォーラムとクォーラムスライスの間には区別がないことに注意すること。
定義2.2.[Maz15] quorum FBAS⟨におけるノードU⊆Vのセット、Q⟩は、U̸= ∅かつUが各ノードのスライスを含む場合 - すなわち、q⊆Uとなる∀v ∈ U,∃q ∈ Q(v)、である。


図1:1、2、3、4とラベル付けされた4つのノードを持つFBASの例。矢印は、v∈{1、2、3、4}に対して、ノードがそのクォーラムスライス関数Q(v)において指し示す他のノードを含むことを表しています。ノード2、3、4はそれぞれ、ノード{2、3、4}からなるクォーラムを有する。ノード1は、そのクォーラムスライスに2と3のみを含むが、それらは両方ともそのクォーラムスライス内の4に依存するため、Q(1)={1、2、3、4}となる。


図2:図1に示したFBASの例は、上記の配色を用いて代替的に表現することができる。ここで、青色で着色されたノード1のクォーラムは、ノード1、2、3、4で構成され、他のノードについても同様である。
定義2.3.[Maz15] quorum intersection FBASは、その2つのクォーラムがノードを共有している場合、つまり、すべてのクォーラムU1とU2に対して、U1 ∩ U2 ̸= ∅ を満たす場合にquorum intersectionを享受します。
定義2.4.[Maz15] delete ⟨V , Q⟩をFBASとし、B⊆Vをノード集合とすると、⟨V, Q⟩からBを削除するには、⟩V , Q⟨で、QB = {q \ B|q∈Q(v) }の修正FBAS、QP27E9を計算することである。
そして、ノードの集合は、それを削除してもネットワークの合意形成に支障がない場合、dispensable set DSet(定義2.5参照)と呼ばれる。言い換えれば、DSetの外にあるノードの安全性と活性度はそれに依存しない。したがって、理想的なシナリオでは、すべての行儀の悪いノードと 故障したノードはDSetに属し、それによってシステムが合意に達する 能力に影響を与えないだろう。
定義2.5.[Maz15] DSet ⟨V, Q⟩をFBASとし、B⊆Vをノードの集合とする。以下の場合、Bはディセンシブルセット(D-Set)であると言う。
(1) (Bにもかかわらず定足数交差)⟨V, Q⟩Bが定足数交差を享受している、かつ、以下の場合、BをD-Setと呼ぶ。
(2) (Bにもかかわらず定足数を満たす) V \ Bが⟨V, Q⟩の定足数であるか、B = Vのどちらかである。
一方、与えられたセットが与えられたノードのクォーラムスライスのそれぞれに属する場合、そのとき、それはv-ブロッキングであると言われる。定義2.6 [Maz15]v-blocking.v∈VをFBAS ⟨V, Q⟩のノードとする。集合B⊆Vがv-blockingであるのは、それがvのスライスと重なる
すなわち、∀q ∈ Q(v), q ∩ B ̸= ∅ である。

2.3 ノードの専門用語
分散環境では、システムが正しく機能するのを妨げようとする悪意ある行為者が大きな懸念材料となる。しかし、悪質な行為者はどのように正式に定義されるのだろうか。これを捉えるために、善良な行為者の行動を捉えるwell-haveed(honestと呼ばれることもある)の概念が導入される。非公式には、善良な行為者は非公式に分別ある行動をとらなければならない。つまり、プロトコルに従い、クォーラムスライスに関して正しい選択をし、リクエストに応じなければならないのである。そうでなければ、行儀が悪く、ビザンチン障害に陥ると言われている。
プロトコルの時間的な進行を通じて、参加者が更新を適用することが目標とされ、これはスロットと呼ばれる。次に、ノードvはスロットi(スロットとは例えば台帳の取引番号)に更新xを適用することを決定する。もしvが最初にスロットiが依存するすべての依存関係に更新を適用し、次に正しく機能している他のすべてのノードもそれを適用すると確信した場合である。この場合、vはスロットiのxを外在化したという。
定義2.7.[Maz15]安全性 FBASのノードの集合は、それらのうちの2つが同じスロットで異なる値を外部化することがない場合、安全性を享受する。そうでなければ発散する。
定義2.8.[Maz15] 活性(liveness) FBASのノード集合が、失敗した(ill-behaved)ノードの参加なしに新しい値を外在化できる場合、そのノードは 活性を享受している。そうでない場合、それはブロックされる。
定義2.9.お行儀の良いノードは、安全でかつ生きている場合、正しいノードという。そうでない場合は失敗となる。
定義2.10.[Maz15] intact ノードvは、すべてのill-behavedなノードを含むDSet Bが存在する場合、 intactであるという。
であり、v ̸∈ Bである。
最後に、かつて誠実だったノードが不品行なノードになることも、その逆もあり得ることに注意。

2.4 前提条件
このプロトコルは、いくつかの共通の仮定に依存している。1つ目は、メッセージの偽造が不可能であることに関するものである。
仮定2.1.つまり、ノードは公開鍵によって命名され、暗号的に安全なデジタル署名を使用する。
次に、非同期システムの文脈では、メッセージは遅れるかもしれないが、最終的には配達されることが一般的に仮定されている。到着した順番は必ずしもこれらが送信された順番と一致しないことに注意。
仮定2.2.ネットワークはお行儀の良いノード間で、任意に遅延や再順序があっても、最終的にメッセージを配送する。
最後に、最後の仮定はクォーラムスライスの存在を保証する。仮定2.3.DSetを削除した後、すべてのノードのクォーラムは交差する。
これで予備的なセクションは終わりです。次のセクションでは、Flare コンセンサスプロトコルを紹介し、分析する。

3 Flareコンセンサス・プロトコル 3.1 グローバルグラフの生成
ネットワークはN個のノードの集合からなり、以降、曖昧さをなくすために参加者と呼ばれ、これらは集合Vで表される。Uをすべてのクォーラムの集合とし、より具体的には、Ux = {U∈U |x∈V} を参加者x∈Vのクォーラムの集合とする。
参加者は互いに任意のトランザクションを実行し、重要なのは、ネットワークの整合性を維持するためにこれらのトランザクションを順序付けることを望む。以下では、例として金融取引の特殊なケースを使用する。FCPはあらゆるタイプのステートフルな決定論的取引を扱う一般化されたプロトコルであることに注意することが重要である。
例えば、アリス(参加者A∈V)はボブ(参加者B∈V)にトランザクションを送信したいと思う。実際には、アリスはボブへ送りたい金額を含むメッセージを作成することでこれを実現する。次に、この情報をできるだけ効率的に全参加者に伝え、取引の順番を合意させる必要がある。これはコンセンサスの問題であり、FCPでは広く共有された特定のメッセージ、すなわち多くの参加者に伝達されたメッセージに対する投票手続きによって達成される。

このように、メッセージは作成、送信、受信のいずれかを行うことができます。例えば、プロトコルの開始時に、アリスが作成した最初のメッセージはm(1)と呼ばれます。この情報を他の参加者に伝達し、グローバルな知識にするために
ゴシッププロトコル[Dem+88]が実行されます。ここで、アリスは他のノードを確率分布p(ρ)に従って
ここで、アリスは残りの参加者の確率分布p(θ)に従って別のノードを選ぶ。最も単純な場合、これは残りの参加者全員に対する一様な確率分布
分布である。例えば、彼女はチャーリー(参加者C∈V)を選び、彼にメッセージm(1)を送る。
A
このメッセージを受け取ったチャーリーは、受け取ったメッセージに関する情報と、彼自身が最後に作成したメッセージに関する情報を含む新しいメッセージを、例えばMerkle木[Mer87]で行われているように、作成しなければならない。この新しいメッセージの作成はまた、このメッセージの負荷にトランザクションを付加する機会でもあり、その後ゴシッププロトコルによって伝搬される。参加者間のメッセージの生成と伝播はDAGで表され、頂点はメッセージを表し、有向辺はある参加者から別の参加者にメッセージが送られ、その結果新しい頂点が生成されることを表しています。図3は、メッセージの流れの一例である。
ここで、Vはグラフの頂点の集合、すなわちメッセージ、Eはエッジの集合、すなわちメッセージ間の接続を表す。このDAGには、各参加者が通信したメッセージ、受信したメッセージ、作成したメッセージの履歴が含まれている。しかし、どの参加者もこの情報に直接アクセスすることはできない。実際、参加者は自分自身が受け取ったメッセージと、その中に含まれる履歴に関連する追加情報しか知ることができない。したがって、各参加者はこの部分情報を、def 3.4で定義されるローカルDAGとして表現することになる。したがって、プロトコルは各参加者がこのローカル構造を構築し、これらのメッセージを順序付ける目的で、3.8節を参照して連合仮想投票手続きを実行することで構成される。

3.2 メッセージ
より正式には、メッセージは5つのフィールドでラベル付けされたデータ構造である:その2つの親のそれぞれのハッシュ、トランザクション、その作成者のクォーラムスライス関数のハッシュ、およびデジタル署名である。これらの5つのフィールドはメッセージを一意に決定する。
(n) 定義 3.1. メッセージ メッセージmx
のことである。
(1)ペイロードデータ。
(n-1) (2)ハッシュ[mx
∈ は、参加者 x ∈ V が作成する n 番目のデータ構造であり、(n) からなる。
(k) (3)Hash[my(マイ)
(k)
]、myは親、y ̸= xで、n≧2である。
メッセージ認証のためのスキーム。
A
(n-1)
の親をmx とし、n≧2 とする。
(4) Hash[Q(x)] ここで、Q(x)は参加者x (n)に対するクォーラムスライス関数である。
(5) Sign(mx ),
ここで、Hash(x)は暗号的に安全なハッシュ関数を表し、Sign(mx)は
a preprint - november 5, 2019(2019)である。
m(1) m(2) AA
m(1) m(2) EE
(1) (2) (3)
mBmB mB (1) (2)
mC mC


図3:4人の参加者によるコンセンサスアルゴリズム内のメッセージフローの例であり、時間的に左から右へメッセージが流れる。ここでは、4人の参加者(A、B、C、E)がおり、それぞれがクォーラムスライスを持つ。Q(A) =
{A, B, C, E}、Q(B) = Q(C) = Q(E) = {B, C, E}となります。このシステムにおいて、メッセージm(2)の祖先は、メッセージB
{m(1), m(1)}、メッセージm(2)の祖先は{m(1), m(2), m(1), m(2), m(1)} である。メッセージm(2)の親は、AB AACCBB A
m(1)とm(2)である。AC
5
(n)
) はデジタル署名を表す

定義3.2. 初期メッセージ 初期メッセージとは、n = 1のとき、プロトコルの開始時に参加者が 作成した最初のメッセージのことである。
例えば、参加者x∈Vによって作成されたメッセージは、mxと呼ばれることがある。
参加者が2つのメッセージを作成し、どちらも他方の情報を含んでいない場合、二重支出やその他の悪意のある行動が発生する可能性があり、これはフォークとして知られています。
(n) (k) (n) (k)
定義3.3. フォーク メッセージのペア(mx , mx )は、mx と mx が同じ参加者によって作成された場合、フォークとなる。
x ∈ Vであるが、どちらも他方の先祖ではない。
より一般的には、Fxは任意のx∈Vに対して参加者xによって作成されたすべてのフォークの集合を示すとします。
はフォークを作成しない。
3.3 ローカルグラフの生成
しかし、各参加者は、特定のメッセージと、DAGで表されるネットワーク履歴の一部しか知らないだろう。Gxを参加者x∈VのDAGとし、Vxを参加者xのDAGのメッセージの集合、すなわちDAGの頂点を示すとする。
したがって、例えば、アリスは、自分が受け取るメッセージと、それが含む情報を認識しており、それは、ハッシュの二分木であるMerkle木[Mer87]と同様に、先祖のハッシュを介してネットワークの歴史に関する情報を含んでいる。彼女が認識している情報は、ローカルグラフGAで表現される。これは、他の参加者(例えばBob)のネットワークに関する知識とは異なる可能性があり、GBというDAGで表現される。

定義3.4. ローカルグラフ 各参加者x∈Vは、参加者xが認識しているメッセージの集合に対応する頂点Vx = {m(k)|i∈V, k∈N}の集合からなるDAG Gx = (Vx , Ex ) であるローカルグラフを生成し、さらに、そのローカルグラフを構成する集合
i
ここで、(mi,mj)はメッセージm(k)からm(k′)までの有向辺である。

3.4 グラフの整合性
このように、ローカルグラフはグローバルグラフの部分的な情報を含んでおり、より具体的にはVx ⊆ Vである。時間の経過とともに、参加者間でより多くのメッセージが共有され、彼らのローカルグラフはますますグローバルグラフを反映するようになる。このようなメカニズムにより、各参加者は自分のローカルDAGに対してローカル投票手続きを実行することができるようになる。
GAとGBという2つのローカルDAGがあるとき、それぞれの特定の頂点が同じメッセージを表しているとする。これは、形式的には以下のように定義される。
(n) (n)
定義3.5. 同一のメッセージ 二つのローカルグラフGAとGBが与えられたとき、二つのメッセージmx ∈ VAとm ̃ x ∈ VB , に対して
x, y ∈ V は、同じハッシュとデジタル署名だけでなく、同じペイロードを含む場合、同一であるという。このとき、メッセージは両方のグラフに現れるという。
これにより、一貫性のあるグラフの概念を導入することができる。
定義3.6. 整合性のある2つのローカルグラフGAとGBは、任意の2つの同一の
(n) (n)
メッセージ mz ∈ GA および m ̃ z ∈ GB , for z ∈ V, 両方とも同じ親エッジを持つ同じ祖先の集合を含む。
を含む。
次のレンマは、個々の参加者が持つローカルデータ構造すなわちDAGは、すべてこの一貫性の性質を満たすことを述べている。

Lemma 3.1 (consistent DAGs).すべての参加者が一貫したローカルDAGを持つ。 (n)
証明する。メッセージmxが2つのローカルDAGであるGAとGAの両方に含まれているとする。定義3.5により、これは両方のメッセージが同じ3つのハッシュを含み、特に両方の親のハッシュが同じであることを意味する。このことは、両方のグラフ
(n)
にはmxの親が含まれている。暗号ハッシュ関数は衝突のない安全なものであると仮定しているので、この場合
(n)
の親は同じでなければならない。帰納的に、GAとGBでmxの祖先はすべて同じでなければならないので、 整合性の条件1が満たされる。
を満たす。仮定により、2番目の条件も満たします。よって、GAとGBは一致する。

3.5 グラフの接続性
ローカルDAGが構築されると、参加者はトランザクションの順序に関してコンセンサスを得たいと思うようになる。これは、参加者間でより広く伝達され共有されるという意味で、他のメッセージよりも重要であるとみなされるメッセージを考慮することによって達成される。これはローカルグラフの接続性、すなわち頂点の到達可能度によって決定される。
フォークの存在は、システムの完全性を脅かす可能性がある。したがって、メッセージのローカルDAGの文脈では、頂点の 到達可能性の定義はこれを考慮するように修正される。
定義3.7. 到達可能 メッセージmxは、1)myからmxへのパスが存在する場合、my→mxと書き、VAのメッセージmyから到達可能であるという。
2)anc(mx)∩Fy =φである。
局所グラフが与えられたとき、頂点uから頂点vへのパスのうち、vの作成者によるフォークを含まないパスの集合をPu→vとすると、|Pu→v|はそのパスの個数を表す。直感的には、2つの頂点を結ぶ経路が多ければ多いほど、その2つは強く結ばれていることになる。このことを理解するために、2つの頂点が十分な数のパスで接続されているだけでなく、それらがさらに十分な数の関連する参加者を経由していなければならない、強い到達可能性が導入される。より正確には、2つの頂点uとvは、vの作成者の頂点の定足数を通る経路で接続されていなければならない。
定義3.8. strongly reachable メッセージmxは、以下の場合、メッセージmy =⇒ mxと書かれたメッセージによって strongly reachableであるという。
1)my →mx,and
2)∃Ux∈Ux st∀i∈Ux,∃mi stmy →mi andmi →mx.であるとき。
さて、メッセージmxが与えられたとき、mxから強く到達しうるすべてのメッセージの集合を考えることができる。R(mx)={mi|mx =⇒ mi,i∈V}とする。(1)
この集合に対して、同じクリエータから強く到達可能な頂点のみを考慮するための制限を加えることができる。R′(m(k)) = {m(n)|m(k) =⇒ m(n)}, (2)
ここで、R′(mx) ⊆ R(mx)である。
次に、行儀の悪い参加者xがフォークを作成した場合を考える。この場合、2つの矛盾のないローカルグラフはどのような結果になるのだろうか。次のレンマは、参加者がフォークを作った場合、次のラウンドでメッセージに強く到達できるのは、このうちの1つだけであることを教えてくれる。
xxxx
レンマ3.2(強い到達可能性)。二つの無矛盾な局所グラフGAとGBを考え、参加者x∈V(n)(n′)(n)を考える。
がフォーク(mx , mx )を作成したと考える。さらに、mz ∈VAを無傷のノードからのメッセージとすると、mx =⇒ mz .(n′ )
とすると、mx ≠⇒ mj,∀mj ∈VBとなる。

証明すなわち、メッセージmj∈VB st mx =⇒ mj が存在すると仮定することで矛盾を解決する。の定義により
(n′ )
の定義により、∃Uj ∈ Uj st mx → ml と ml → mj 、∀ml ∈ Uj が強く到達することを意味する。さらに、仮定により
(n′ )
mx =⇒ mz,ここでmx ,mz ∈VA.By the definition of strongreachabilityの(2)ポイントにより,quorumが存在する。
(n) (n) (n)
Uz∈Uz st ∀i∈Uz,mx → mi,mi → mzとなる。GA≒GBの仮定により、DSet Bを削除すると全てのクォーラムはクォーラム交差を持つ。DSetの定義により、⟨V, Q⟩Bはquorum intersectionを享受する。さらに、cは行儀が良い。そして、mc∈VAとm ̃ c∈VBをこれによって生成されるメッセージとする。
(n′ ) (n)
mx → m ̃ c と m ̃ c → mj と mx → mc と mc → mz となるようなローカルグラフの参加者が作成したメッセージであるとする。ここで、well-behavedの定義により
の定義により、(mc , m ̃ c ) はフォークになりえないので、一方は他方の祖先である。mcを先祖とすると、(n) (n)
は、mc → m ̃c となる。よって、mx → mc となり、mc → m ̃c が成り立つ。よって、mxはm ̃の祖先となる。しかし、(n′)(n′)(n)(n′)(n′)として
仮定により、(mx , mx )はフォークなので、mx ̃はm ̃の先祖であり、矛盾となる。
3.6 スロット数
Strongly reachableメッセージはメッセージの集合に部分的な順序を導入する。より具体的には、プロトコルの開始時に初期メッセージが作成される。より多くのメッセージが作成され、送信されると、これらのいくつかは広く到達可能、すなわち以前のメッセージとより強く接続される。与えられたローカルDAG GAにおけるメッセージの広がりと接続性を追跡するために、メッセージスロット番号σA[m]が導入される。プロトコルの開始時に、各メッセージは(1) (n) (1)
にある。ここで、mxから同じ(n)′(1)(n)作成者によって強く到達可能な最初のメッセージをmxとする。
の作成者、すなわちmx ∈ R (mx ) とする。さらに、mx は、x のための (n) の定足数を形成する初期メッセージのセットから強く到達可能であるとする。
この場合、メッセージmxのスロット番号は1つ増加する。これらの条件が満たされない場合、スロット番号は単にメッセージの親の最大スロット番号となり、この場合、1であろう。
定義3.9. スロット数σA[mx]:mx∈VA →N,x∈V,A∈V, は次のように定義される。


メンバーは常に一貫したローカルグラフを持つことを想起してほしい。次のレンマは、あるメッセージが2つのローカルグラフに含まれるとき
に含まれる場合、各参加者がそのスロット番号に同意することを保証する。
レンマ3.3 (一貫性のあるスロット).GAとGBを、メッセージmxを含む2つの無矛盾なローカルグラフとすると
(n) (n) (n)はmxに同じスロット作成番号を割り当てる、すなわちσA[mx ] = σB[mx ]となる。

証明する。仮定により、GAとGBの両方がメッセージmx を含む。GA ≈ GB なので、整合性の定義により、両者は
を含むので、整合性の定義により、両者は同じ祖先の集合を含み、これらの間に同じ親エッジがあります。これには、最初に作成されたメッセージも含まれる。そして、証明は帰納的に行われる。両方のグラフは、その最初のメッセージのスロット番号に同意しており、それは定義により1である。さて、myを両方のグラフに属する任意のメッセージとする。次に、スロットsのコアメッセージから強く到達可能なスロットsの参加者の定足数Uy∈Uyが存在するかどうかを決定する必要がある。先祖集合のグラフ接続性が同じであるため、両方のグラフがmyのスロット番号に同意することになる。したがって、彼らはmxを含む共有するすべてのメッセージのスロット番号に同意することになります。
したがって、今後、スロット番号関数から添え字を削除する。すなわち、すべての参加者A∈Vについて、σ[x]はσA[x]と書かれることになる。
3.7 コアメッセージ
このように、スロット番号の定義から、各スロットで最初に作成されるメッセージのセットが特に重要です。これらをコア・メッセージと呼ぶ。
定義3.10.コアメッセージ コアメッセージの集合は次のように定義されます。
C = {m(k)|mink st σ[m(k)] = s,∀s ∈ N,∀i ∈ V}とする。(5)
ii
さらに、コアメッセージmxがフォークでない場合、それは、すなわち、mx∈C st mx ̸∈Fxであり、ユニークであると言われる。
次に、コアメッセージの集合は、各スロット番号に従って不連続な集合に分割される


ここで、Ci={m∈C|σ[m]=i}とする。さらに、σ[m] ≥ σ[n]に対して、△(m, n) = σ[m] - σ[n]を導入する。
次に、強く到達したメッセージの重要度について、参加者のコンセンサスを得ることになる。これは
これは、連合仮想投票手続きによって達成される。
3.8 連帯仮想投票
3.8.1 概要
各参加者が自分自身のローカルDAGを構築したので、目標はメッセージの順序に関するコンセンサスに達することである。これは連合仮想投票アルゴリズムによって達成され、投票プロセスによって特定のコアメッセージがピボットであると決定される。図4では、ある発言aが確認されるまでの道のりを示している。次に、これらが評価されると、メッセージに順序番号が付与され、これにより、すべてのメッセージが順序付けされ、コンセンサスが達成される。 

ここで、Ci={m∈C|σ[m]=i}とする。さらに、σ[m] ≥ σ[n]に対して、△(m, n) = σ[m] - σ[n]を導入する。
次に、強く到達したメッセージの重要度について、参加者のコンセンサスを得ることになる。これは
これは、連合仮想投票手続きによって達成される。


図4:文aの確認までのFBAパス[Maz15]

3.8.2 投票
このプロトコルは、各参加者が投票手順を実装することで、各コアメッセージは、投票関数を通じて、前のコアメッセージの接続性に関する票を投じることで構成される。例えば、あるコアメッセージmyは前のスロットからのコアメッセージmxに投票する(各参加者は各ラウンドで1つのコアメッセージを持っていることを思い出してほしい)。投票は投票関数によって決定され、このプロセスは選挙と呼ばれる(def 3.12 参照)。
定義3.11.選挙は、投票関数の評価、すなわち、あるコアメッセージが前のスロットのコアメッセージに投票した結果を指す。
投票関数は、まず、連続したスロットの2つのコアメッセージについて定義される。もしmyがmxから到達可能であれば、myはyesに投票し(a = 1)、そうでなければnoに投票する(a = 0)。メッセージmyとmxが2つ以上のスロットで区切られている場合、投票はタリー関数 (定義3.14参照) によって実装される。タリーは前のスロットに投じられた票を集計する。これは、投票者集合の構築を通じて行われ、その投票が集計される。投票メッセージ、たとえばmyが、その投票者セットが投票中のメッセージのための定足数であり、これらがすべて同じように投票するとわかったとき、myもまたそのように投票することになる。このような決定がなされたとき、myはさらに、ピボット関数の評価によって、mxをピボットと決定する(定義3.15参照)。最後に、投票関数において、投票手続きの終了を保証するために、コインフリップを導入する。
定義3.12.投票投票関数v(my,mx):C×C→{0,1,⊥}、定義は以下の通りである。


ここで、[P]は文Pの真偽、τ(my,mx)は11で定義した集計関数、r(my,mx)は12で定義したランダマイズ関数
関数、⊥は未コミット状態、c∈Nはコインフリップである。
v(my,mx) はメッセージmyのコアメッセージmxに対する投票である。ここで、メッセージmyは、関連する、すなわち、yの定足数で、前のスロットでコアメッセージからの投票を集計する必要がある。 これらのメッセージは、投票者セットと呼ばれる。
定義3.13.投票者セット スロットs′のコアメッセージ(と投票者)myの投票者セットは、次のように定義される。
V(my) = {mi|mi∈Cs′-1, i∈Uy, mi =⇒ my}と定義される。(8)
さらに、myに対する投票者集合V(my)は、以下のように分割することができる。 V(my)=V1(mx)∪V0(mx)、ここでVa(mx)={m ∈ V(my)|v(m,mx) = a}、(9)。
ここで、a∈{0,1}である。これらの集合は、スロットs′におけるメッセージmyに依存することに注意されたい。
ここで、a∈{0,1}に対して、Va(mx )に属するメッセージを作成した参加者を考える。
Pa(mx)={j ∈ V|mj ∈ Va(mx)}とする。(10) これにより、集計関数を以下のように定義することができる。

定義 3.14.タリー タリー関数 τ (my , mx ) :C × C → {0, 1} は以下のように定義される。

ここで、B(x)はx-ブロック集合であり、定義2.6を参照のこと。
最後に、コインフリップの場合、ランダマイズ関数r(my, mx) :C × C → {0, 1} は次式で与えられる。

ここで、rはmyの署名の中間ビットである。 このようにして、投票手順の第1段階が定義される。
3.8.3 受け入れ
次のフェーズでは、特に重要なコアメッセージであるピボットメッセージを導入する。
定義3.15.ここで、πA : C → {0, 1}は次のように定義されるピボット関数である。

したがって、ピボット・メッセージは、投票関数と集計関数の両方が計算されていることが必要です。なお、ピボットメッセージは定義上コアメッセージである。Pはすべてのピボットの集合であり、コアメッセージと同様にP=∪Pi、ここでPi={m∈P|σ[m] = i, i∈N}であるとする。図5では、5人の参加者のDAGの例を示しており、コアメッセージとピボットの両方が計算されている。


図5:コンセンサスアルゴリズムにおけるメッセージの流れの一例。黒い点が1つある頂点がコアメッセージで、黒い点が2つある頂点がピボットと判定されたものである。
このように、あるコアメッセージについてコアメッセージの定足数が同じ票を投じた場合、合意に達したとされ、選挙結果が得られる。このように、参加者はどのコアメッセージがピボットであり、どれがピボットでないかに関して合意に達する。
定義3.16.選挙結果 前のスロットのコアメッセージがピボットであるかないかを決定するとき、選挙はスロットsで結果aを持つ(それがピボットであればa=1、そうでなければa=0)。
定義3.17.決定 コアメッセージがピボットであるかないかが決定されたとき、選挙は決定されたという。これはビザンチン合意(Byzantine agreement)と呼ばれる。
このように、コアメッセージは前のコアメッセージがピボットであるかどうかを評価する。先験的に、異なるコア・メッセージは異なる結果をもたらしうる、すなわち、あるメッセージが特定の投票者セットによってピボットと評価されるか否かを想像することができる。次のレンマは、そうではないことを述べている。一旦、ある有権者集合に対してコアメッセージがピボットであると決定されれば、他のどの有権者集合も同じ結論に達するということである。

定理3.4 (一貫性のある投票)GAとGBを二つの一貫性のあるローカルグラフとする。GA上で動作するアルゴリズムが、ある選挙において、スロットsのコアメッセージmxがスロットs+1のコアメッセージmyに投票ax∈{0, 1}を送ることを示すとする。そしてGB上のアルゴリズムが、スロットsのコアメッセージm ̃ xが投票a ̃x ∈ {0, 1}をスロット+1内の証人m ̃yに送ることを示すとしよう。
証明する。mx∈VAとm ̃x∈VBを考える。レンマ3.2により、これらのメッセージのうち1つだけが他のメッセージに強く到達できる。しかし、仮定により、メッセージmxとm ̃ xは両方とも自分の票を送る、つまり両方ともmyに強く接続されていなければならず、したがって矛盾となる。したがって、これはxによって作られたメッセージのうちの1つが他のメッセージの祖先であることを意味する。しかし、これらは仮定上コア・メッセージであり、したがって最小のスロット番号を持たなければならない、つまりそれらは同じであることを意味する。したがって、2つの票は両方のグラフで同一のメッセージmxからきているはずです。メッセージが送る票は、純粋にその祖先の関数として計算されます。2つのグラフは一貫しているので、これらは同じであり、したがって2つのグラフは投票について同意しなければならず、ax = a ̃xである。
このように、異なるコア・メッセージは、前のコア・メッセージのピボット性に関して同じ結論に達する。さらに、次のレンマは、最大でも互いに2スロット以内にこの結論に到達することを保証している。
レンマ3.5(一貫した判断)。GAとGBを2つの一貫性のあるローカルグラフとする。GAがスロットsで結果aの連合ビザンチン合意選挙を決定し、GBがs以前に決定していない場合、GBはスロットs+2かそれ以前にaを決定する。
証明する。これは、スロットsにおいて、σ[mx]<sのコアメッセージmxが存在し、スロットsにおいて、π(mx)=aのピボットであるかないかが決定されることを意味します。ピボット関数の定義により、スロットs - 1における参加者のセットPa(mx)は、xのためのクォーラムを形成し、それらはすべて同じ方法すなわちaを投票している存在する。 レンマ3.4により、一貫性のあるグラフでは、同じスロットの同じクリエイターからのコアメッセージは、同じ方法で投票する。送られる票は純粋に先祖に依存し、したがって定足数全体は、このように両方のグラフのすべてのコアメッセージにaを送ることになることを思い出してください。一貫性の定義により、GAとGBのすべてのクォーラムは、DSetを削除した後、クォーラムの交差を持つ。したがって、GAとGBの両方におけるスロットsのすべてのコアメッセージは、aに投票する(そして、いくつかはaを決定するかもしれない)。そして、スロットs+1が通常のスロットであれば、そのスロットのGAとGBのすべてのコアメッセージは全会一致でaに投票し、aを決定する。スロットs+1がコインフリップであれば、全員が満場一致でaに投票するので、無作為抽出とはならず、全員がaに投票し、スロットs+2で全員がaを決定する。
このように、ある参加者が以前のコアメッセージのピボット状態に関して結論を出すと、その直後にそれが定足数交差を持つすべての参加者が一致することが保証されるのである。しかし、あるコア・メッセージのピボットの状態が未確定である可能性はないのだろうか。次の定理はこの問いに否定的に答えます。

定理3.6(ピボットの計算)。ピボット関数は最終的に確率1で決定される。
証明する。あるコアメッセージmzを考える。レンマ3.5により、ある参加者xがmzがピボットであるかどうか、すなわちa∈{0,1}に対してπ(mz )=aと決定した場合、xと定足数交差するすべての参加者は2スロット以内に同じように決定する。つまり、mxのピボットの状態が未決定のまま、すなわちπ(mx)=⊥となるのは、これらの参加者のうち1人も決定しない場合のみであり、コアメッセージが全会一致の定足数を受け取ることはないためである。しかし、コインフリップでは、そのような定足数がまだ達成されていない場合、すべての無傷のノードはランダムに自分の投票を選択し、すべてが同じ投票を選択するゼロでない確率を持つことになります。cスロットごとにコインフリップが行われ、コインフリップは永遠に周期的に発生するので、最終的に無傷のノードは確率1で全員一致となり、レンマ3.5により2スロット以内にコンセンサスに到達することになる。
コアメッセージは、投票関数と投票者セットを介して、以前のコアメッセージに対するピボット関数の値を決定する。次のレンマは、あるコアメッセージがピボットであるかどうかが数スロット以内に決定されることを保証している。
レンマ3.7(ピボットの存在)。任意のスロット番号sにおいて、参加者zが作成したスロットs+3のメッセージmzを少なくとも1つ持つ任意のローカルDAGについて、スロットsにおいて少なくとも1つのコアメッセージが存在し、この決定はスロットs+3、またはそれ以前にzとクォーター交差する参加者からのすべてのコアメッセージによってなされる。
証明する。ローカルDAGの一つを考え、s∈N st mz∈Cs+3とする。以下のコアメッセージの集合Si={mx∈Ci|mx =⇒my,my∈Ci+1} wherei<s+3.IfSy̸=∅, bydefinition of strong reachability, this means that exist a Uy∈Uy st mz → mi,mi → my, ∀i∈Uy.IfSy ̸=φ]がスロットiで、存在していること。強い到達可能性は到達可能性を意味するので、Ss+1にメッセージを持つ各参加者は、Ssのメッセージの定足数によって到達することになる。さて、レンマ3.2により、どの参加者も与えられたスロットで強到達性のコアメッセージを2つ以上作成することはできない。スロットi+1におけるコアメッセージの存在は、ノードのクォーラムがスロットiにおいて強く到達することを保証し、参加者の誰も、強く到達する与えられたスロットにおいて1つ以上のコアメッセージを作成することができない。仮定により、mzはs+3におけるコア・メッセージである。したがって、Siのすべてのクォーラムはzと交差する、∀i≦s+2である。
さらに、強到達性は到達性を意味するので、Ss+1内のメッセージを持つ各参加者は、Ss内のメッセージのクォーラムから到達することができる。Ss+1内の定足数の交差特性により、Ss+1内の参加者の定足数に到達するSs内のメッセージ(mxと呼ぶ)が少なくとも1つ存在するはずである。これは、Ss+1内のコアメッセージの定足数は、それぞれSs内のメッセージの定足数によって到達し、Ss+1内の定足数からコアメッセージの全てに到達する少なくとも1つのメッセージを含む少なくともvブロック集合がSs内に存在しなければならないからである。したがって、Ss+1内の参加者の定足数は、mxがピボットであることの選挙で賛成票を投じることになる。したがって、Ss+2内のすべてのメッセージは、システム全体の状態をyes-valentにするmxがピボットであるかどうかについての少なくともv-blocking setのyes投票を受信し、したがって、mxがピボットであるかどうかについて投票する(mxがピボットであると決定してもよいし、決定しなくてもよい)。したがって、Ss+3のメッセージは、mxがピボットであることに対する満場一致の投票を受け、mxがピボットであると決定することになる。したがって、スロットs+3においてxと定足数交差するメッセージを持つすべての参加者は、まず、mxがapivotineitherslots+2or+3であることを決定する。

最後に、次のレンマは、DAGに新しいメッセージを追加することが、与えられたスロットのピボットの集合に与える影響について考察している。
レンマ3.8(新しいピボットはない)。GAがメッセージmxを含まないが、mxのすべての祖先を含むようなものであるとし、GAにmxを追加した結果をG′Aとする。さらに、mxをスロットsで作成されたコアメッセージとし、GAにはスロットsでピボットかピボットでないかのどちらかに決定されたコアメッセージが少なくとも1つあるとする。すると、G′Aではmxはピボットでないと判定される。
証明する。仮定により、スロットsのGAにおいて、スロットsのコアメッセージがピボットであるかどうかを決定するコアメッセージ、例えばmw∈Csが存在する。mwの祖先は、mx∈/GAであるため、mxから到達可能なものはない。mx以外の全てのメッセージは両方のグラフに含まれているので、それらは全て両方のグラフに同じ祖先を持つことになり、mxはどのメッセージの祖先にもなれないことになります。したがって、mxはどちらのローカルDAGのどのメッセージにも到達することができない。したがって、先祖はs+1において0票を投じることになり、GA′ins+2においてitnotbeapivotとなる。
このように、各コアメッセージは、ピボットであるか、経由しないかのどちらかで評価される。重要なことは、異なる参加者からのコア・メッセージは、あるメッセージがピボットであるかどうかに関して、すべて同意することが示されていることである。これらのピボットは、DAG内のメッセージの順序を決定するために使用される。
3.8.4 確認

最終的に各メッセージには注文番号が付けられます。これを計算するためには、問題のメッセージより小さいか等しいスロットを持つすべてのコアメッセージについてピボット関数が決定されている必要があります。オーダー関数の領域は次のようになります。
D={mx∈VA|∀my∈C st σ[my] ≦ σ[mx],π(my) ̸=⊥y∈Ux,∀Ux∈Ux} である。(14)
すなわち、これらは次数計算が可能なメッセージであり、以下のように決定される。

定義 3.18.オーダーナンバー メッセージmxのオーダーナンバーは、オーダー関数oA : D → N, ∀A ∈ Vによって決定され、次のように定義される。

oA[mx] = s, (15)

wheres=min σ[m ]=t,wherem ∈anc(m ),π(m )=1,m ∈/F ∀z∈U ,∀U ∈U andDisdefined
in 14.

オーダー番号が割り当てられると、因果関係のある順序は、例えば、分散環境でのイベントの順序を決定する有名なアルゴリズムであるLamportタイムスタンプ[Lam79]を活用したものなど、決定論的順序付けプロセスによって計算される。
したがって、メッセージはまず順序番号でソートされ、次に因果的順序でソートされ、最終的に必要であれば、ハッシュ値でソートされる。次の定理は、すべてのメッセージに順序番号が割り当てられることを保証し、メッセージの順序付けに到達することを保証する。
(n)
定理3.9(メッセージの順序付け)。無傷の参加者xが作成した各メッセージmxには、最終的に、メッセージの総順序のうち
は、メッセージの総順序において、確率1で順序番号が割り当てられる。
(n)
証明する。お行儀の良い参加者xが作成したメッセージmxを考える。お行儀が良いということは、同期
を頻繁に行い、仮定2.2により、これらのメッセージは最終的に配信される。したがって、すべての行儀の良い参加者、その中でもxと定足数交差を持つ参加者は、最終的にmx を知ることになる。したがって、最終的に
′(n)あるスロット、例えばsでは、xとクォーラム交差する参加者によるすべてのユニークピボットがmxの子孫である。
′ (n) したがって、スロットsで、あるいはそれ以前に、すべてのピボットがmxの子孫であるスロットsが存在することになる。これは
(n)
であり、そのスロット内でmxに順序番号sが(因果関係のある順序と同様に)割り当てられるに十分である。そのコンセンサス
の位置は固定される。さらに、後で新しいメッセージmyを発見して、それがコンセンサス順で(n)
mxの前に来る新しいメッセージmyを発見することはできない。実際、コンセンサス履歴で先に来るためには、myはs以下のオーダー番号でなければならない。そうなるためには、スロットsのすべてのピボットがmyを受信していなければならない。しかし、一旦スロットのピボットのセットが知られると、その先祖もすべて知られ、したがって、DAGが成長するにつれて将来それらのための新しい先祖を発見する方法はない。さらに、あるスロットの既知のコアメッセージがすべてピボットであるかどうかが決定されると、そのスロットが将来的に新しいピボットを獲得することは不可能になる。作成者が既知のスロットs+1のコアメッセージの作成者とクォーラム交点を持つ、新しいスロットsのコアメッセージが将来発見されても、既知のスロットs+1のコアメッセージの祖先にはならない。そのため、スロットs+1コアメッセージのどの定足数にも強く到達できないので、ピボットではないとのコンセンサスが即座に得られることになる。したがって、あるメッセージが全体の順番に割り当てられると、他の既知のメッセージと入れ替わったり、新しいメッセージが後で発見されて前に挿入されたりしても、その位置は決して変わりません。

4 結論
FCPは簡略化された、公正な全銀協の構成である。FCPはFBA協定の文脈の中に存在し、Hashgraphによって導入された仮想投票の一般化である。FCPをHashgraph、SCP、Blockmaniaと比較する。
ネットワークに一定の参加者数Nがいるとする。参加者がそれぞれクォーラムスライスを(2N + 1)/3 人の参加者のすべての組み合わせに設定する場合、すなわち各メンバーのスライスのセットがそのメンバー自身を含むような場合、この特別なケースはハッシュグラフコンセンサスプロトコルに戻る。ハッシュグラフコンセンサスプロトコルは、この(2N + 1)/3 の構成、すなわち従来のビザンチン合意でのみ存在でき、シビル攻撃を本質的に克服することはできません。Flareコンセンサスプロトコルは、Federated Byzantine Agreementのフレームワークに存在するため、Sybil攻撃を本質的に克服し、参加者がクォーラムスライス決定を独立して行うことを可能にする。
Blockmania [DH18]は、PBFT [CL+99]フレームワークで定式化された従来のビザンチン合意プロトコルであり、ハッシュグラフ合意プロトコルで確立した仮想投票技術を利用して、通常のPBFTよりも大幅に通信量を削減することができます。
Flare Consensus Protocolは、Federated Virtual Votingの技術により、投票ベースのアプローチ(Stellar Consensus Protocolなど)と比較して通信量の大幅な削減を実現しています。ステラコンセンサスプロトコルもリーダーベースであり、リーダー候補がFBAネットワーク内の中心部にどれだけ位置しているかに基づいてリーダーを選択する。このため、ネットワークの周辺に存在する参加者は、ネットワーク内でほとんど力を持たず、多数の参加者が合意に与える影響を大幅に抑制することができる。一方、Flare コンセンサスプロトコルは、完全にリーダーレスであり、ネットワーク上の参加者数の増加に伴い、ネットワークに対する公正な制御が可能となる。これは、例えばダークプール取引など、多くの場面で公平性を確保するために非常に重要である。
Flare Consensus Protocol (FCP)は、Federated Byzantine Agreementの表記法とStellar Consensus Protocolの論文で確立された理論的保証を活用し、連合体による仮想投票を導入するものである。FCPは簡略化された公正なビザンチン合意構成であり、ビザンチン耐故障性が証明されています。これらの特性により、FCPはインターネットレベルのチューリング完全合意に対する説得力のあるモデルとなっています。
この論文に対する有益なフィードバックを下さったHugo PhilionとArtem Vorobievに感謝します。

この記事が気に入ったらサポートをしてみませんか?