handle_consensus_output()を読んだ時点でBullsharkで理解していないことを解決する

以下をVSCodeに移管する

handle_consensus_output()でtxの順序付けは確定できるが，アンカーリーダーのコミットに関する順序付けについては記述されていない．

handle_consensus_output()でサブDAGをコミットするかどうかを決める

サブDAG内の各証明書とバッチを処理します。これは順序付けの主要な部分です

code:.rs

if matches!(

self.epoch_store

.protocol_config()

.consensus_transaction_ordering(),

ConsensusTransactionOrdering::ByGasPrice

) {

let _scope = monitored_scope("HandleConsensusOutput::order_by_gas_price");

order_by_gas_price(&mut sequenced_transactions);

}

ここでトランザクションの完全な順序付けを達成する

code:.rs

consensus_commit_batch

.commit(checkpoint)

.expect("Failed to commit consensus commit batch");

コミットしてファイナリティを達成する

code:.rs

self.transaction_scheduler

.schedule(transactions_to_schedule)

.await;

まだ理解できていないこと in Bullshark Consensus

-> VSCodeに移管する

リーダーの選出アルゴリズム

仮説

ステークウェイトとランダムネス？

leader_schedule()関数

ラウンドロビン

目的

公平性を満たす

スケジューリングアルゴリズムの一種

均等な時間とか順番を割り当てている

ここでは何かはわかっていない

論文のアルゴリズム見たらわかるはず

すべてのノードがリーダーになるチャンスを得ることができる

解答

重みづけランダムネスよりも複雑

追加でスケジュール期間やreputation scoreなどを活用する

リーダー選出の順序も決めている

ラウンドロビンは公平性に寄与

参加の公平性

全てのバリデータがリーダーになる可能性がある

経済的な公平性

ステーク量に応じて重み付けされる

システムへの貢献度に応じた公平性

reputation score

目的

システムの公平性、効率性、そしてセキュリティを向上させること

数式

具体的なリーダー選出確率を定式化

$ p(v) = \{(s(v) * r(v))\} \div \{Σ(s(i) * r(i))\} \ for \ all \ i

TODO: 本当に足りないものはないか？

抽象化して短く書くと

$ lim(t→∞) N(v) \div t = p(v)

定義

リーダーの選出確率p(v)

vとiはバリデータ

s(v)はバリデータvのステーク量、r(v)は評判スコア

バリデータvの実際の選出頻度（N(v) / t）

各バリデータがリーダーになる回数 N(v)

tは総ラウンド数

説明

この式は、各バリデータが必ずリーダーとして選出されることを保証するものではない

p(v)が0に近い場合、そのバリデータがリーダーに選出される可能性は非常に低くなる

有限の時間内では、理論的な確率と実際の選出頻度に乖離が生じる可能性がある

アンカーリーダーのコミット対象txの順序付け，ブロックのシーケンス（execution layerに提出する配列？？）

仮説

txについて，ガスプライスとタイムスタンプのみ

ガスプライスでの順序付け

process_consensus_transactions_and_commit_boundary()関数について，本当かわからない

論文内のOrdering the DAGのアルゴリズム内に書いてあるかも

handle_consensus_output()関数内

Suiはアンカーとラウンドを知っていて，アンカーをコミットするための投票を待っている？

解答

ガスプライスをベースにタイムスタンプやトランザクションサイズなどあらゆるものが考慮されている

全員が同じ順序付けになる = 決定論的

ガスプライスの詳細

order_by_gas_price()関数

ガスプライスに基づいて降順に並び替える

アンカーの投票のquorum intersectionについて

仕組みがやはり完全に理解していない

perplexity.icon

DAG構造を使った各ノードへの投票を行うバリデータが複数いて，そのバリデータがfaultyである可能性もあるとき，quorum intersectionとはなんなのかという概要と，この場合での役割と機能について説明してください．

解答

目的

分散システムにおける一貫性の維持

概要

任意の2つのクォーラム（決定に必要な最小集合）が少なくとも1つの正常なノードを共有することを保証する性質

ローカル上でのアンカーリーダーへの投票の数（f + 1）とアンカー間のパスが正しくつながっていることが共有する対象

TODO: 何に対してのquorumか？ものによってはSui上でも安全性の検証をすることができて，f + 1投票に少なくすることができているかもしれない

なぜn - fではなく，f + 1なのか？

部分同期モデルだと，最終的に同期されるからf + 1で安全性を失わず，高速に処理可能

異なるパスの情報を全てのバリデータで統合する

これが安全であるというのは，Bullsharkの論文では証明されていない

条件

直接的なコミットでのf + 1の投票が必要

1つしか投票されていないアンカーはコミットできないが，1つでも投票がある場合，スキップされずにSuiは待つ？それとも条件なしでスキップ？

早そうなのはスキップとして現在ラウンドr + 2で再試行する

解答

現在f + 1投票を満たすA3をコミットするには，現ラウンド以前でのアンカーがある場合，スキップできない

A3に対して，A1がパスがあり，投票が足りなくてもA3に十分に投票されているのであれば，A3の参照を辿るとA1があるということがパスであり，バリデータはA1にも投票しているとみなすことができるため，A1はコミット対象となる

それゆえ，A3からA1間の投票されたサブDAGも全てコミット対象となっている = 決定論的ルールの一つ

それぞれのノード（ブロック / サブDAG）が一つ前のラウンドでn - fのノードを参照している

結果

アンカーAが直接的にコミット（投票）される

将来における全てのアンカーは，アンカーAに対して少なくとも1つの投票することでパスを持つ

将来における全てのアンカーはAへのパスを持つ

faultyとは

パスを持っていないバリデータ

原因は悪意 / 通信の遅延のはず？

アンカーの投票ルールについて，やることとしてはいけないこと

仮説

Narwhalの時と同じように署名 = 投票

コミットに必要な > f + 1 の投票におけるfは遅延のみ？もし悪意のあるトランザクションを含んだとしてもNarwhalでDAGを作るまでに除外されるはず

Narwhal -> BullsharkにDAGを渡すのはバリデータではなくてSuiから？

handle_consensus_output()がいつ誰から実行されているかで理解することができる

リーダーであることの受信は，リーダーから？ゴシップから？Suiから？

解答

Bullsharkの技術的目的

要は，リーダー決めて正しいルールに従って順序付けしてねってこと

順序付けするanchorを決めること

偶数ラウンドごとにanchorを決める

決定論的に因果関係をを順序付けすること

奇数ラウンドごとにvoteする

ローカルビューで違いがある

スキップもある

弱いリンクもある

公平性, fairnessを満たす？

Non-equivocation

Narwhalの時も

二重投票または矛盾する行動を排除していること

各投票したサブDAGの投票先は同じ = 因果関係は同じ

reliable broadcast protocolで実行されている

アンカーの投票は，Narwhalと同じようにバリデータによる投票によって達成される

直接的コミットは，十分な数の投票（f + 1以上）が集まった時点で行われて，結果としてコンセンサスが達成する

fの意味はfaultyで，Narwhalと同じく，遅延だけでない悪意のある投票も含まれる

SuiシステムがNarwhalのサブDAG（証明書）をBullsharkに受け渡す

ConsensusOutput構造体がインターフェースっぽい

アンカーリーダーはシステムが決定し，バリデータがシステムから受信する