【Bullshark】順序付けのプロセス，プログラムベースと数式ベースのメモ
mainブランチ変更に伴って
VScodeProjects/sui/suiにmainnetブランチをダウンロード
主要過去のメモをrefとして
成果物の予定
仮想のケースを用意して，必要な条件分岐を作って数学ベースの説明
Narwhalでのcert_AがBullsharkに渡されてコミットされるまでのプロセスとして
TODO
ファイナリティ達成のタイミングは？
アンカーリーダーがf+1の署名を得たタイミングで順序付けはされていないが，コミットすることが確定する
storeに保存した瞬間
アンカーリーダーが順序付けされたタイミングで，プログラムベースだとlinked()でリーダー間のリンク付けがわかった時点
証明書，間接的にはトランザクションを実行していなくても確定はしている
できた
commit_certificate()
リーダー選出をしているプロセスタイミングが確定していない
おそらくというところになっている
Bullsharkの論文でも詳細なアルゴリズム，プロセスの明記はない
executorはsui nodeで実行されている
解説を他ページで分解する
プロセス
Narwhalの動作も含めて，バリデータはすでに新しいprimary nodeをstart()で動作させている
プログラム上では，start()関数内のspawn_primary()で起動させる．
SimpleExecutionState::new()も非同期で達成するために実行している
spawn_primary()では新しいプライマリを生成するためにspawn_consensus()を非同期関数で実行した後，Primary::spawn()でプライマリノードを生成している．
他の関数ではあるが，事前にやっていること
w-1のround4で選出されたsteady-state leaderとfallback leaderが選出される
spawn_consensus()では，まずNarwhalによってすでに処理されたサブDAGを対象に，get_restored_consensus_output()で最後にコミットされたサブダグとリーダースケジュールをリカバーのために取得する，
TODO: コンセンサス終了後の処理も最後に追加する
--- ここからが本当のBullshark構造体の出番
次にBullshark::new()で新しいBullshark構造体のインスタンスを生成する
TODO: Bullshark構造体の説明を追加する
これをコンセンサスプロトコルで処理するためにConsensus::spawn()を実行する
Consensus構造体の状態を更新し，これをrun()メソッドを使用する．run()はrun_inner()を実行し，うまくいかない場合にエラーのログを残したりプログラムの終了を行う．
TODO: Consensus構造体の説明を追加する
run_inner()では，新しい証明書を受信している限り，Bullsharkのprocess_certificate()メソッドを起動する．
TODO: コンセンサス終了後の処理も最後に追加する
よって，バリデータが新しい証明書を受信することで，NarwhalでのサブDAGとなるcert_AがBullsharkに渡される
これが前に書いた抽象的プロセスの最初の部分
ConsensusState構造体を持つConsensus構造体とその証明書をprocess_certificate()に渡す
プロトコルはもちろんBullshark
TODO: ConsensusState構造体の説明を追加する
ConsensusState構造体はクラッシュリカバリー用のStateとあるが，last_committed_sub_dagなどのフィールドを持っている
他の関数ではあるがやっていること
wでround1でanchor leader a1が配置されブロードキャストされる
round2でn = 4, f = 1とする．v1とv2がa1に投票する
a1がquorum（f+1）を達成するとこれが他の全てのバリデータに同期される
この結果から，round1のanchor leader a1はsteady-state leaderと定義される
そして，round3のためのsteady-state leaderであるanchor leader a2が選出される
round 3 anchor leader a2が配置されブロードキャストされる
round 4でv2とv3とv4がa2に投票する
process_certificate()
偶数ラウンドである場合
コミットされていない最新のラウンドと現在のConsensusState構造体をcommit_leader()に渡す
commit_leader()
1つ前のラウンド（子ラウンド）でf+1のQuorumを達成していることを確認する
ここはcommit_leader()内でやっているわけではない
a2がquorum（f+1）を達成し，これが他の全てのバリデータに同期される
w+1のためのsteady-state leaderとfallback leaderが選出される
a1とa2はQuorum IntersectionとDAGの構造によりa1の後にa2がコミットされるように順序付けされる
process_certificate()で受け取った，引数をそのままorder_leaders()に渡す
order_leaders()
最新のラウンド-2から最後にコミットされたラウンド+2
ラウンドを2つずつ戻って最後にコミットされたラウンド+2まで行う
rとr-2の次はr-2とr-4
linked()に最新のラウンドのリーダーと前のリーダーを渡す
linked()が2つの証明書（リーダーと前のリーダーの間）が連結されているかどうかを確認しboolで返す
trueでリーダー（証明書）間連結されている場合，コミット予定のリーダーを両端キューでcommit_leader()に返す
リーダーを古い順からシーケンスする
新たに最後にコミットされたDAGをバリデータが保持できるように永続化する
コミットのトリガーしたことの通知とコミットするcommitted_sub_dagsを返す
Outcome::Commitが通知
commit_leader()から集めたcommitted_sub_dagsを足していく
committed_sub_dagに何もなかったらリターン
commit_leader()と同様，コミットの結果とcommitted_sub_dagsを返す
コミットに失敗した証明書はNarwhalに返す
committed_certificates変数にcommitted_sub_dags変数の全ての証明書を正しい順序でベクターに追加する
シーケンスしたものを他の変数でもやっているので実際の抽象プロセスでは削除する内容
正しく順序付けされたDAGのシーケンスをself.tx_sequenceに送信する
最新ラウンドとcommitted_certificates変数を送信して，最新ラウンドとConsensusState構造体内のlast_round.committed_roundが一緒であることを確認しておく
非同期でやっているので，システムのどっかのタイミングでラウンドを一致させてからじゃないとコミットするべきでないのでやってる
spawn_consensus()のConsensus::spawn()の続き
Executor::spawn()でトランザクションを実行するクライアントをspawn, 生成する
Executor::spawn()
spawn_subscriber()
run_notify(state, rx_notifier, rx_shutdown_notify)
state.handle_consensus_output(message).await;
message = ConsensusOutput構造体
handle_consensus_output()
最後にコミットされたラウンドとConsensusOutputのリーダーラウンドと違うことを確認する
トランザクションが重複していないか，すでに処理されていないかを確認
ガスフィーに基づくトランザクションの順序付け
アンカー間の並び替えもトランザクションベースではここで行われている，決定論ルール
コミットされたサブDAGをもとに最終的な実行トランザクションを基本的にガスプライスに従ってシーケンスする
Executor::spawn()の結果をつなげてコレクション構造で格納する，spawn_consensus()の終了
これも抽象プロセスだと削除
run_inner()の続き
process_certificate()の後，コミットに失敗した証明書はNarwhalに返す
他はトランザクション処理に関係ない
非同期処理特有の確認とか
終了
ここからはSuiNodeでコミット
SuiNodeのmain()を実行
SuiNode::start_asyncでSuiノードを非同期で起動する
start_async()
目的: Sui Nodeを非同期で起動し初期化する
AuthorityState::new()
現在のエポックのプロトコルバージョンを確認する
メトリクスを初期化する
チャネルを作成する
トランザクションマネージャーの初期化
AuthorityStateの作成
実行プロセスの開始
準備完了の証明書を実行するタスクを開始する
execution_process()
新しいtxが処理可能になるたびに実行するループ処理
実行中に恒久的なエラーは起こるはずがなく，一時的な障害のために最大10回，try_execute_immediately()メソッドを実行，再試行する．
try_execute_immediately()
TODO: 関数の処理プロセスの詳細をもう一度確認する
前提
ロックが設定されていることが前提
ロックをやっている関数は，enqueue_impl()で
enqueue_impl()
まだ実行していないトランザクションだけを集める
対象トランザクション内のオブジェクトのロック情報を取得する
self.inner.write()で書き込みロックを取得する
multi_input_objects_available()でオブジェクトの可用性を確認
オブジェクトの可用性とキーをペアする
enqueue()で実行されている
enqueue_certificates()で実行されている
enqueue_certificates_for_execution()で実行されている
execute_certificate()で実行されている
handle_submit_to_consensus()で実行されている
in sui/crates/sui-core/src/authority_server.rs
handle_transaction_v2()で実行されている
同じファイル
transaction_v2_impl()
引数にリクエスト
同じファイル
ロックの設定の保証ができない場合，execute_certificate()を実行する
TODO: 関数内に記載されていないので，条件分岐でこの関数ではなく，execute_certificate()が使われている箇所があるはず
実行と出力のコミットは原子的に行われ、クラッシュした実行は観察可能な影響を持ちません
実行が成功した場合、出力はストレージにのみ書き込まれる
これがまさにファイナリティ達成の瞬間，実際はcommit_certificate()
プロセス
cquire_tx_guardを使用して、同じトランザクションの同時実行を防ぎます。
トランザクションの効果がすでに書き込まれているかをチェックし、重複実行を避けます。
read_objects_for_execution()を呼び出して、実行に必要な入力オブジェクトを読み取ります。
process_certificate()を呼び出して、実際の証明書の処理を行います。
process_certificate()
トランザクションの実行ロックを取得
prepare_certificate()を呼び出して、トランザクションの準備をする
commit_certificate()を呼び出して、トランザクションをコミット
let _metrics_guard = self.metrics.commit_certificate_latency.start_timer();
バリデータの場合はトランザクションとその効果について署名
トランザクションキーと効果の署名をエポックストアに挿入します。これにより、トランザクションの記録が永続化されます。
tx_guard.commit_tx()を呼び出し、トランザクションを完全にコミットします。この時点で、トランザクションは完全に永続化され、ファイナリティが達成されます。
notify_commit()を呼び出し、トランザクションとその出力オブジェクトがコミットされたことをトランザクションマネージャーに通知します。
notify_commit()
トランザクションがコミットされたことを通知し、ロックを解放
効果と実行エラー（存在する場合）を返す
再試行のインターバルは1秒
シャットダウン
--- プロセスはここで終了
リーダーブロックをコミットするということは、その依存関係をすべてコミットすることを意味します。
Bullshark構造体も使うタイミングまたはインスタンス生成のタイミングで説明を入れる．
Q. Can anyone give an example of the deterministic rule that is used to order blocks between two anchors?
A. To be as concrete as possible the magic happens here:
書いた
ExecutionStateトレイトの一部として実装されている
code:.rs
pub trait ExecutionState {
/// Execute the transaction and atomically persist the consensus index.
async fn handle_consensus_output(&mut self, consensus_output: ConsensusOutput);
/// The last executed sub-dag / commit leader round.
fn last_executed_sub_dag_round(&self) -> u64;
/// The last executed sub-dag / commit index.
fn last_executed_sub_dag_index(&self) -> u64;
}
ExecutionStateトレイトで実装されている
ExecutionStateトレイトを実行する実行エンジンNarwhal/内に構築している
SimpleExecutionState構造体にブロックチェーンに書き込み済みのtxを格納しておく
run() in node/src/main.rs
ワーカーノードまたはプライマリノードを実行するところでSimpleExecutionState構造体が使用されている
ノードの動作の流れは主旨と異なるので割愛する
run()はmain()内で使用されている
バリデータがCLIから直接使用する関数である
SimpleExecutionState::new()はプライマリノードを新たに実行し非同期の終了まで待機する
5.2 Ordering The DAG
やっぱり抽象的すぎる
プロセス
バリデータが頂点をコミットするとcommit_leader(v)が呼び出される
最後にコミットしたリーダーまで遡る
steady-stateリーダーとfallbackリーダーそれぞれに対する投票を確認
f+1以上の投票を持つリーダーを順序付けし、leaderStackにプッシュ
order_vertices()関数で、コミットされたリーダーの因果履歴にある頂点を決定論的な順序で配信
決定論的というのがgeorgeのいうところなはず
4.2 Our DAG protocol Algorithm 1
タイムアウトメカニズムがあり、一定時間経過後にラウンドを強制的に進めることができる
commit_one()
これは実際処理されているプロセスで，テストケースとして実装されている．その中で最もシンプルで理想的な（faultyのいない）処理がなされている．
コンセンサスに対してはほとんど何をやっていなくて，ラウンド1，2はhonestな形で済むようにして，ラウンド3でf+1の証明書を用意して，Bullshark構造体のインスタンス生成とConsensus::spawn()関数にその用意したものを投げて，帰ってきた結果が正しいことを確認しているだけ．
つまり，コンセンサスを詳細はConsensus::spawn()
Consensus::spawn()について，コンセンサスアルゴリズムの実行に必要な初期設定を行い、実際の処理を行うタスクを起動する役割を果たしているだけ，コンセンサスの核ではない
run_inner()
Consensus::spawn()が使うrun()が使っている関数
新たな証明書を受信した時
NarwhalからDAGが送信されているはず
ConsensusState構造体を持つConsensus構造体とその証明書をprocess_certificate()に投げる
ConsensusState構造体はクラッシュリカバリー用のStateとあるが，last_committed_sub_dagなどのフィールドを持っている
プロトコルを指定可能，Bullshark
committed_certificates変数はコミットに失敗した時にNarwhalに返す用
committed_certificates変数にcommitted_sub_dags変数の全ての証明書を正しい順序でベクターに追加する
正しく順序付けされたDAGのシーケンスをself.tx_sequenceに送信する
最新ラウンドとcommitted_certificates変数を送信して，最新ラウンドとConsensusState構造体内のlast_round.committed_roundが一緒であることを確認しておく
非同期でやっているので，システムのどっかのタイミングでラウンドを一致させてからじゃないとコミットするべきでないのでやってる
Bullshark.rs徹底解説
Bullshark構造体
Bullsharkトレイト
あるメソッドで使われているメソッドは入れ子状態にする
new
インスタンス生成
resolve_reputation_score
前回のコミットからの評判スコアの計算と更新
process_certificate
この関数はConsensus構造体の非同期関数run_inner()で使用されている
最新ラウンドから始める
certificateのラウンドの-1
run_inner()より新しい証明書を受け取った時にこの関数自体が動作している
-1しているのは，rが偶数の場合，まだ投票中であり，このラウンドをコミット対象に入れることができない，rが奇数の場合，リーダーのブロードキャストが完了しており，-1することですでに投票が終了した偶数ラウンドのf+1を確認することができる
偶数ラウンドのみが対象
order_leaders()でもなぜか再度確認している
まだコミットされていない最新のラウンドからcommit_leader()関数に投げる
引数はleader_round, state
leader_roundはコミットされていない最新のラウンドかつ偶数ラウンド
stateはConsensusState構造体
最後にコミットしたラウンドのlast_roundフィールド
ラウンドに直接関連するサブDAGも
commit_leader()から集めたcommitted_sub_dagsを足していく
committed_sub_dagに何もなかったらリターン
commit_leader()と同様，コミットの結果とcommitted_sub_dagsを返す
commit_leader()
order_leadersに投げるleader変数の条件
あるリーダーのラウンドでそのリーダーの証明書があること
leader_round+1（子ラウンド）でf+1のQuorumを達成していること
leader_round+3もありうるのか？
おそらくあり得ない
理由
leader_round+1でf+1を達成していないとする
leader_round+2がleader_round+3よりf+1を達成しているとする
leader_round+1で一つでもleader_roundへの署名が確認されるならば，leader_round+3をコミットできるということはleader_roundをコミットできるということとなる
これはlinked()では確認できない
もう一つ
// Check if the leader has f+1 support from its children (ie. leader_round+1).
コメントアウトされた文章より，リーダー証明書のchildrenと記載されており，あるリーダーに投票可能な複数のバリデータを示しており，投票できないleader_round+3のバリデータのことを示していない
孫を含むなら，descendantsやchildren and grandchildrenとかになるはず
self.order_leaders(leader, state);でleaders_to_commitを作った後
リーダーを古い順からシーケンスする
このシーケンスごとに評判スコアを保存する
更新を永続化する
self.store.write_consensus_state(&state.last_committed, &sub_dag)?;
コミットすることになるから，last_committed_sub_dag変数を更新
コミットのトリガーしたことの通知とコミットするcommitted_sub_dagsを返す
order_leaders
偶数ラウンドのみ実行
ラウンド範囲の指定
最後にコミットされたラウンド + 2から現在のリーダーのラウンドの2つ前のラウンドまで
これがそのまま下のlinked()の範囲
理由
最後にコミットされたラウンドはすでにコミットされたもので，次にコミットされるのは2nより，+2になる，まだコミットされていない最小のラウンドとも言える
2つ前のラウンドというのは，現在のリーダーはまだ十分な署名を得ていないのでコミット対象にならない．2つ前であれば十分な署名を得ている可能性がある．
次にリーダーの証明書があるものだけlinked()に投げている
linked()がtrueで，証明書間で連結されている場合，
to_commit変数にコミット予定のリーダーを格納
返り値
to_commit変数
両端キュー（デック）の証明書を配列する
commit_leaderの核の変数として使用
linked
2つの証明書（リーダーと前のリーダーの間）が連結されているかどうかを確認しboolで返す
update_leader_schedule
report_leader_on_time_metrics
以上ではどのような順番でleaderとprev_leader間にlinkedがあるかを確認していますか？
以下であっていますか？
最新ラウンドをrとし，そこからr-2, r-4, r-6, r-nとし，r-nは最後にコミットされたラウンド+2とする．
また，全てのラウンドでリーダー証明書は存在するものとする．
プロセス手順
1. rとr-2の間にlinked()があるか確認する
ある場合は簡単であるが，ここでは1でlinked()がfalseだった場合を考える
その時，以下のkとlどちらのプロセスに行くことになりますか？
k. rとr-4の間にlinked()があるか確認する．ここでももしなかったら最大r-nまでrとlinkedがあるかを一つずつ確認する．
l. r-2とr-4の間にlinked()があるかを確認する．あくまで最大-2の間でのlinked()を先に確認する．
答えはlの方
以下はステークベースでf+1を超えていることを確認していますが，f+1 support from its childrenについて例としてleader_round+1が記載されています．
これはリーダーのブロードキャストラウンドの次のラウンドで署名が行われているから+1となっていますが，+3となるケースもありますか？
ある場合，その可能性を考えて実装されているプログラム部分を示してください．
linked()では先述した通り，±2のラウンド間のlinkedしか確認していません．
---
ファイナリティについて
金融的には決済完了性だから，Suiはオブジェクトに対してそうなので，オブジェクト完了性になる？他のチェーンも加味して広義的に考えるならば，オブジェクトではなくてリソースやアセット
NarwhalまたはSuiシステムから証明書を受け取ってその証明書に紐づいたトランザクションから指定のオブジェクトをSuiシステムがロックし，トランザクションの内容を実行し，そのオブジェクトが書き換えられます．
ここではより正確なファイナリティ達成について理解するために，指定オブジェクトがロックされた後，トランザクションの内容に従ってオブジェクトが変更されたその瞬間をファイナリティとしたい
覆されないだろうという推移性を持ったファイナリティについては，過去のDAGとアンカーリーダーA1が結びついた時に，A1を含む全ての因果関係を誰もが計算可能になるので，f+1の投票を得たアンカー間A0とA1が結びついていることが確認された瞬間，つまり，linked()がtrueを返した時となる
---
execution_driver.rs
execution_process()を実行
authority.rsで定義
AuthorityState::new()関数内で使用されている
crates/sui-node/src/lib.rs でstart_async()で使用されている
main.rsのmain()で使用
ロック
TransactionManager構造体
enqueueメソッド
トランザクションを受け取り、必要なオブジェクトのロックを試みる
このメソッドの次が大事！enqueue()はenqueue_certificates()で使用されている
enqueue_certificates()
TODO: enqueue_certificates()がどこで呼び出されているのか？
enqueue_certificates_for_execution()で使われている
execute_certificate()
同ファイル内でこれに使われている
handle_certificate()
これから違う
所有オブジェクトは実行，共有オブジェクトは待機している
submit_certificate()で使用，同ファイル内
これが使われていることの裏を取れなかった
他の答えがしっかりあった
証明書/検証済みのトランザクションをTransactionManagerにキューに入れる
キューに入れるはenqueue()で実行している
すべての入力オブジェクトがローカルで利用可能になると、証明済みのトランザクションがexecution driverに送信される
try_acquire_lockメソッド
特定のオブジェクトに対するロックの取得を試みる
LockQueue構造体：
オブジェクトに対するロック待ちキューを管理
notify_commitメソッド：
このメソッドは、トランザクションがコミットされたことを通知し、ロックを解放します。これはトランザクション実行後の処理の一部と考えられます。
通知したら該当証明書を取り除いてもう一度通知することがないようにしている
inner.executing_certificates
self.certificate_ready
certificate_readyメソッド：
このメソッドは、ロックが取得されたトランザクションを実行のために送信します。
実行
execution_process()
同時実行数を制限するためのセマフォを作成
CPUの数の制限
新しいtxが処理可能になるたびに実行するループ処理
実行中に恒久的なエラーは起こるはずがなく，一時的な障害のために最大10回，try_execute_immediately()メソッドを実行，再試行する．
再試行のインターバルは1秒
try_execute_immediatelyメソッドの内容自体はAuthorityState構造体でauthority.rsにある
try_execute_immediately()
ポイント
ロックが設定されていることが前提
ロックの設定の保証ができない場合，execute_certificate()を実行する
実行と出力のコミットは原子的に行われ、クラッシュした実行は観察可能な影響を持ちません
実行が成功した場合、出力はストレージにのみ書き込まれる
これがまさにファイナリティ達成の瞬間
Suiシステムしか実行しない
acquire_tx_guardを使用して、同じトランザクションの同時実行を防ぎます。
トランザクションの効果がすでに書き込まれているかをチェックし、重複実行を避けます。
read_objects_for_executionを呼び出して、実行に必要な入力オブジェクトを読み取ります。
process_certificateを呼び出して、実際の証明書の処理を行います。
process_certificate()
トランザクションの実行ロックを取得
prepare_certificate()を呼び出して、トランザクションの準備をする
commit_certificate()を呼び出して、トランザクションをコミット
効果と実行エラー（存在する場合）を返す
commit_certificate()
let _metrics_guard = self.metrics.commit_certificate_latency.start_timer();
バリデータの場合はトランザクションとその効果について署名
トランザクションキーと効果の署名をエポックストアに挿入します。これにより、トランザクションの記録が永続化されます。
tx_guard.commit_tx()を呼び出し、トランザクションを完全にコミットします。この時点で、トランザクションは完全に永続化され、ファイナリティが達成されます。
notify_commit()を呼び出し、トランザクションとその出力オブジェクトがコミットされたことをトランザクションマネージャーに通知します。
---
Bullsharkのインスタンスは本番環境でどこで生成されているのか？
もちろん，プライマリノードはやっていて，ここで使用されている．
この部分は書いた
start<State>()
ノードがすでに動作中かを確認して，動作していなかったら続ける
ネットワークキーペアからPeerIdを生成し保存する
生成していないかも
新しいメトリクスレジストリを作成する
spawn_primary()を呼び出す
spawn_primary()
プライマリノード生成のための準備をする
コンセンサスにおいては重要なものではない
新しいプライマリを生成する
spawn_consensus()を非同期関数で実行する
consensus_handles, leader_scheduleを返す
Primary::spawn()でプライマリノードを生成する
spawn_consensus()
プロセス
get_restored_consensus_output()で最後にコミットされたサブダグをリカバーする
処理されなかったサブDAGは無視する
リーダースケジュールの取得する
Bullshark::new()で新しいインスタンスを生成する
返り値は次のConsensus::spawn()の引数として使用
Consensus::spawn()
ここからはコンセンサスの処理後
Executor::spawn()でトランザクションを実行するクライアントをspawn, 生成する
処理がうまくいかなかったものはsubscriberと同期する
Executor::spawn()の結果をつなげてコレクション構造で格納する
Executor::spawn()
sui/narwhal/executor/src/lib.rs
spawn_subscriber()