L1 Public Blockchain「Sui」のDAG生成の流れ
はじめに
こんにちは。前回の概要記事で、Suiというブロックチェーンの特徴について解説しました。そこで話した大きな特徴は「DAGデータ構造でMempool Layerにブロックを保存する」ということでした。
この記事では、実際にSuiがDAGを生成する流れを図と共に説明していきます。
ここで説明する流れは実際にSuiのソースコードを元に作成しています。具体的な実装を追いたい方はソースコードを見てみるといいでしょう。
Architecture & Data Structure
SuiはDAG-Based Mempool 「Narwhal」とBFT Consensus 「Tusk/Bullshark」で構成されたLayerd Consensus Architectureになっています。
Narwhalのデータ構造はこのようになっています。
それぞれ、2つのデータ構造が一方向に参照を持ってこのような全体のアーキテクチャを構成しています。
- Certificate
- Block
さらに、それらはRoundベースで区切られています。
例えば4つのNodeがあったとき、Round 1では4つのBlockと3つのCertificateが保存され、Round 2では更に新たな4つのBlockと3つのCertificateが保存されます。
ではそれぞれのデータ構造を見ていきましょう。
Certificate
Certificateとは、あるBlockの可用性を証明するデータです。
これらのデータを元に構成されています。
- Block Hash: どのBlockのCertificateなのか
- Signatures: Blockを検証した署名のNodeごとのリスト
Block
Blockは基本的にはBitcoinなどの従来のブロックチェーンと同じデータ構造を持っています。そこで主に異なるのはHeaderです。
従来のBlockは、Headerに前のBlock Hashを持ちます(それが連なってブロックチェーンとなります)。NarwhalのBlockは、Headerに前のRoundで生成されたCertificateのリストを持ちます。
例えばRound NのBlock Headerでは、Round N-1で生成された3つのCertificate Hashのリストを持っています。
こうして、CertificateがBlockを、Blockが前のRoundのCertificateを参照していくことでDAGが構成されます。
DAG生成の流れ
ここでは、簡略化のためにNodeが3つあると仮定しています。
(本来Nodeが3の時はCertificateの数は3つ必要ですが、簡単化のために2つで十分になるようにしています)
0. receive transactions
まず前段階として、Nodeは常にクライアントからtxを受け付けます。
txはNodeの中のWorkerが受け取ります。Workerは受け取ったtxを検証し、バッチに貯めます。
バッチが貯まり切ると、他の全てのWorker Nodeにそのバッチをシェアします。
もちろん同様に他のWorkerからバッチが送られてきたら、それを検証して自身のストレージに保存します。
0. send tx digests
Workerがバッチを生成したとき、他のWorkerにシェアすると共に、それぞれのtxのdigest(hash)をPrimaryに送信します。Primaryは受け取ったdigestを自身の変数に保存します。
同様に他のWorkerからバッチを受け取ったときも、そのdigestをPrimaryに送信します。
1. start Round N
PrimaryにはRound Timerがあり、そこで新しいRoundスタートの合図が走ります。
Roundが切り替わるのはround N-1のBlockが既に生成されていて、かつ以下の条件を満たしたときです。
- 一定時間経過(defaultは100ms)
- 既にWorkerから一定量のtx digestを受け取っており、2個以上のCertificateを持っている
if (timer_expired || (enough_digests && advance)) && enough_parents {
if timer_expired && matches!(self.network_model, NetworkModel::PartiallySynchronous)
{
// It is expected that this timer expires from time to time. If it expires too often, it
// either means some validators are Byzantine or that the network is experiencing periods
// of asynchrony. In practice, the latter scenario means we misconfigured the parameter
// called `max_header_delay`.
debug!("Timer expired for round {}", self.round);
}
2. create block headers
新しいRoundが始まると、まずWorkerから貯められたtx digestsをもとにBlock Headerを作成します。
生成したBlock Headerは他のPrimaryにブロードキャストされ、検証された後に保存されます。
3. create votes
PrimaryがBlock Headerを生成したときと他のPrimaryからBlock Headerを受け取った時、PrimaryはそのBlockのVoteを生成します。
Voteとは「自分はこのブロックが正しいことを署名します」というメッセージで、そこにはBlockへのSignatureが含まれています。
Voteを作成すると、そのVoteを他のPrimaryにシェアします。
4. create certificates
一つのBlockについてのVoteが2つたまると、その中身のSignatureを元にCertificateを作成します。
Certificateを作成すると、同様にそのCertificateも他のPrimaryにシェアします。
シェアされたCertificateは検証され、ストレージに保存されます。
5. end Round N
Certificateが2つ貯まった時点でPrimaryはこのRoundのBlock Header/Vote/Certificateの受付をストップし、次のRoundが開始するのを待ちます。
これが一連のRoundの流れです。あとはこのRoundを無限に繰り返し、一定時間ときにnodeの数だけのBlockが貯まっていきます。
6. consensus
Suiのコンセンサスの詳しい流れについては次に紹介したいと思いますが、現状そこまで多くのコードは書かれていません。
Consensus LayerもPrimaryにあります。PrimaryはCertificateの生成/受信と共に、そのCertificateをConsensusに送信しています。
PrimaryのConsensus LayerがCertificateを受け取ると、そのCertificateのBlockについてのコンセンサスがスタートします。論文では、これが非同期下/攻撃下でも正常に動作するような工夫がされていると説明されています。
おわりに
ここではSuiのDAG Mempoolの生成の流れを、実装を元に詳細に説明しました。ブロックチェーンにおけるブロック生成の一例としても参考になるのではないかと思います。もし興味ある方はEthereumなど他のチェーンの実装も見てみると面白いかもしれません。
ここで一番興味深い点は、PrimaryとWorkerはtxのdigestをもとにロジック/検証を行ない、ConsensusとMempoolはBlockのCertificateをもとにロジック/検証を行なっている点です。どちらも、実体を見ておらず、Zero Knowledge Proofのもとでコンセンサスが行われています。これがSuiのMempoolとConsensusが疎結合で分離されているとされる由縁です。ただ、Certificateの生成が少々ボトルネックになっており、ここにはまだまだ改善の余地があるかもしれません。
Discussion