動画でN / B, 研究担当者によるNarwhalとBullsharkの解説

https://www.youtube.com/watch?v=xKDDuPrYUag

Narwhal and Bullshark: DAG-based Mempool and Efficient BFT Consensus

Speaker:

Alberto Sonnino

ジョージ・ダネジス（George Danezis）とイェンス・グロース（Jens Groth）の助言を受け、ユニバーシティ・カレッジ・ロンドン（UCL）で博士号を取得しました。

chainspace -> metaに買収 -> libra -> Mysten

chainspace

Chainspaceは、ノードのサブクォーラム間で状態をシャーディングすることでスケーリングし、ゼロ知識証明によって契約の実行ロジックを検証から分離することで、プライバシーを保護したスマートコントラクトをサポートしている。

meta

NoviウォレットとLibra決済システムの設計

FastPayコンセンサスレス決済システム（博士論文の最終章）、Narwhal DAGベースのメンプール、Bullsharkコンセンサスプロトコルも共同執筆

ver1ではFacebookで発表されている

最新版でも発表している

典型的なleader-based protocol

leaderと呼ばれるノードが大量のCPUやストレージなどのリソースを使う

他のノードはメッセージを受け取り、検証し、短い文(Vote)を返す

そんなリソースを使わない

Narwhal

どうデータを送るか

dag-based mempool

simple

zero-message overhead

no view-change

pbftとかは複雑

no common-coin

どういう意味？

performant

take advantage of Narwhal

Exploit periods of synchrony

同期期間を利用する

design

一体化している

多分bullsharkとのデータのインタラクションがあるから

データを送るレイヤー

1年のプロトタイピングと1年のproduction化

かなりハイレベルなアーキテクチャの説明なので，わからないことがあったらここで全体像を俯瞰して理解するというようなアプローチの方がいい

Narwhalの中にworker, primaryがある

詳細は自分がまとめたもので

ここはもっとハイレベル

primary = 特別なprocess

https://scrapbox.io/files/65be397cd7d9800025f5ee5b.png

clientがworkerにtxnを送る

workerが他のノードのworkerにtxを送る

https://scrapbox.io/files/65be3bbc0bb31d0026812c16.png

txを集めてバッチへ

500KBくらい

これはおそらくバッチサイズ

you will have a worker one of validator A sending its batch exclusively to worker one of validator B, worker one validator C and so on so far.

worker two communicate only with two workers of all other nodes worker N with N of all other nodes

- Worker Xについて

Validator AのWorker XはValidator B, Cなど全てのValidatorsのWorker X（同じWorkerの種類？）とバッチを交換する

Worker Y, Worker Zもそれぞれ他のすべてのValidatorのWorker Y, Zとバッチを交換する。

つまり、Worker Nは他のすべてのノードのWorker Nと通信するということができる。

これのベネフィットは効率性とセキュリテ、信頼性である。

- ネットワーク全体で情報が迅速に伝播されると同時に、不要な重複通信を避けることができる。

- 特定の種類の攻撃や障害に対する耐性を高めるためにも用いられる

このworker 1が送っているbatchの先にはworker1があるのか？？

workerがバッチを送る

workerはrolling hash batchesをキープする

ここからprimaryについて

primaryはworkerからダイジェストを受け取る

https://scrapbox.io/files/65be3d4041582d0024258d7f.png

ここからmempool

https://scrapbox.io/files/65be40f070ca580024a990c9.png

mempoolがやっていることの詳細

並行処理？

primaryはすべてのダイジェストを受け取る

block headerというデータ構造

block

メタデータ

ダイジェストのコレクション

バッチのハッシュ

header

前のブロックの12 plus 1 links

後で詳しく説明します

すべての他のauthoritiesにデータを送る

Gはなに？

データのグループのことだと思う

HはHeader？

https://scrapbox.io/files/65be41cd0bb31d0026816165.png

最初のヘッダーは投票するしかない

senderはquorumを集める

12 plus 1の投票

証明書

senderはcertificateをすべての他のノードへ送り返す

ヘッダーは以前のラウンドのcertificatesのquorumをリンク付けする

CはCertificate?

V =

https://scrapbox.io/files/65be465d55b752002509d451.png

これがラウンド1

分散コンピューティングやっているとわかるらしい

Byzantine reliable broadcastのインスタンス

条件

12 + 1linksがあること

background sychronizer to think of band whatever blocks may have been missed by some authorities

authority, nodeごとに複数のラウンドを並列処理で実行

https://scrapbox.io/files/65be472b58578c002465106d.png

ラウンドイメージ

dag

バリデータごとに違った部分的なDAGを持っている

それぞれのdagは互いのサブセットになるだろう

サブセットとはどういうこと？

dagはcertificated headerで作られる

ただのヘッダーじゃない

equivocationsはない

同じラウンド番号において、同じバリデータが2つの違ったdagの頂点を作ることはできない

mempoolのゴール

certificated dagがすべてのバリデータによって、並列で作られたラウンドごとに構造化されていること

linearize

ブロックのシーケンスを持っている

バリデータごとに同じブロックのシーケンスに同意している

バリデータは部分的なビューしか持っていない

ここからは好きなコンセンサスプロトコルを使える

SuiではBullshark

https://scrapbox.io/files/65be4818e9b5e000259b4fe9.png

ここから部分同期のNarwhal

dark to have timeouts

livenessを証明している限り

新しいブロックを作るときにpredefined leaderを待つ

後ほど説明

https://scrapbox.io/files/65be659019b8cf002364651b.png

ここからBullshark

ゼロメッセージという部分が肝なのか

非同期のフォールバックなしで

フォールバック(Fallback)は、主要な通信手段やネットワーク接続が利用できない、または失敗した場合に使用される代替の通信手段や接続方法

ネットワーク管理者は障害やダウンタイムの影響を最小限に抑え、エンドユーザーにとって透過的な方法でサービスの可用性を維持することができます。

フォールバック戦略は、事前に計画され、テストされるべきであり、障害発生時の自動切り替えや、必要に応じた手動での介入を可能にするための監視とアラートシステムと組み合わせて使用されます。

ちゃんとtest sentenceあったね

現時点

正しく構築されたDAGがある

目的

線形化されたブロックのシーケンスの出力

方法

デッキをどう解釈するか

デッキとは正しく構築されたDAGのこと？

これ以上protocol messageは不要

以下の説明

2つのラウンドのnodeのview

時間に従って右へ

validatorは4つ

始めにやること

偶数ラウンドごとに決定論的にバリデータの中からリーダーを選ぶこと

https://scrapbox.io/files/65bee1444eb1280025619865.png

定義

L1 = リーダー

vertex = 頂点 = リーダー

anchor = ある特定のノード

グラフ理論じゃない’

ここでは順序づけのリーダー？？

edge = 辺

ラウンドロビン

目的

公平性を満たす

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

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

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

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

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

正直なバリデータがアンカーに同意して、同じ線形化されたブロックのシーケンスになる

https://scrapbox.io/files/65bee25d11d2420026efc854.png

ルール

リーダーはラウンドRでのf＋1のリンクを持っている必要がある

ここではリーダーはラウンド2にいる

次のラウンド3ではf+1の子を持つ必要がある

f+1のブロックcertificateはリーダーにリンクしている

そうなっていたらコミット

ここではラウンド3のブロックがリーダーとリンクしていない

https://scrapbox.io/files/65bee694e1b568002cad2002.png

他のブロックのパターン

赤い線がcertificateがリーダーとリンク付けされているということ

certificateはblockのこと？

ここではf+1 =

https://scrapbox.io/files/65bee7cb5e9fc60023c24103.png

十分なサポートがないパターン

リーダーはサポートを不足すると、viewの変更のトリガーを作動させる必要がある

トリガー

bullsharkの特別なところ

無視するだけでいい

L1をコミットしないだけ

またDAGを構築し続けるだけ

追加で通信（リクエストしたり）する必要がないってことやね

違う

https://scrapbox.io/files/65bee88955b75200250d9682.png

ラウンド4でDAG完成

偶数ラウンドなので、また別のリーダーを決定論的に決めることができる

ラウンドロビンを使って次のリーダーはL2へ

https://scrapbox.io/files/65bee9d941582d00242a1591.png

また、L2が十分なサポートを持っているかどうかを次のラウンドで確認

今回はcertificatesからf+1のリンクがある（青い線）

f+1のリンクがあるという状態なのかどうかがわからない

コミットができる！！

https://scrapbox.io/files/65beea8d7f812800242dd9f3.png

コミットできるアンカーを見つけたら、

次は、ここではL2とL1の間にリンクがあるかどうか

つまり、DAGを通るパスがあるかどうか

ここでは白のcertificateを通して、dagがある

再帰的に次の時点に戻る

再帰性はどこか

以前にコミットしていない最も早いリーダーをコミット、次のリーダーがコミット

時間とかで決めてる？？

https://scrapbox.io/files/65beeb5b22c7bf0025ccfafd.png

L1をコミットするというのは、L1のサブDAGコミットするということ

各certificateが違うnodeによって作られた

各certificateは多くの様々なバッチとリンク付けされたダイジェストのvarietyを保持している

100くらいのハッシュが含まれているとする

500MB分のtxn

実際は違う？

多くのtxnをコミットできる

決定論的に線形化された

ここでは緑

サブDAG

始めの3つの

gas feeによって順序付けできる

アルファベット順？

https://scrapbox.io/files/65beed638511630025d4fb8a.png

L1, そしてL1のサブDAGのコミットが終わったら

すでにコミットしたL1のサブDAG以外のL2のサブDAGをコミットできる

Networking: Tokio(TCP)

Storage: RocksDB

Cryptography: ed25519-delek

https://scrapbox.io/files/65bef0a5c8c57a00258e9245.png

biggest-mistakesとして実装面でやるべきことではないこと

- クラッシュリカバリーの事後追加

- シンクロナイザーの事後追加

- エポックの変更を事後追加

- 初日からベンチマークを行うな

- 空想の暗号から始める

- シリアライズを避ける

直列化

- ネットワークシステムの複雑化

- 論文のようにモジュールを分離する

- grpcとMagic Network Stackを使う

Fast Finality: 32:40

Version Objects

ZKP

Randomness

https://www.youtube.com/watch?v=oefRA55o7K8&t=2033s

object-centric model

https://scrapbox.io/files/65bef7dc3876160025faf732.png

クライアントはtxをすべてのバリデータに送る

クライアントはバリデータからsignatureを受け取る

https://scrapbox.io/files/65bef881a92acb0025df330e.png

並列化することができることもすごいことの1つ

https://scrapbox.io/files/65bef9c23876160025fb03e4.png

初期Bullshark共同執筆者

https://www.youtube.com/watch?v=aW1-XcGzJ8M&t=8s

background

atomic broadcastはdag-riderから

https://scrapbox.io/files/65befab4fbf1080025fe69c0.png

メタデータの順序付けからデータ配信を切り離すことが、パフォーマンスの鍵になる

dagは異なるviewかも

非同期が理由

https://scrapbox.io/files/65befbf4a92acb0025df59d9.png

ここからbullshark

部分同期

レイテンシの改善

実用的なスタンドアロンな部分同期のBullshark

以下のdagはalephによって導入された

以前のラウンドからn - fのvertexへのリンクがある

次のラウンドに進むにn - f vertexが揃うまで待たないといけない

https://scrapbox.io/files/65befcadd061560024c6e848.png

ローカルview

丸をつけたvertexのリンク等はどのローカルviewでもすべて同じリンク付け

因果関係は全く同じになっている

-> 信頼できるブロードキャスト

目的

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

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

偶数ラウンドごとにanchorがある

奇数ラウンドごとにvoteがある

エンコードは事前決定されているとみなせる

いくつかのマッピングにおけるロングドロップだから

validator2がanchor1なのはみんな同じ認識

やること = コンセンサスロジック

どのエンコードを順序付けするか

どのエンコードをスキップするか

https://scrapbox.io/files/65befe518cefae00246b753a.png

direct commit rule

コミットにはf+1のvoteが必要

https://scrapbox.io/files/65beffb7e1b568002cadcf77.png

f + 1 = 2

A2は3票持っている

A2はバリデータによって直接コミットできる

https://scrapbox.io/files/65bf00432b02390025b633e6.png

A2のコミットの前にA1を参照しないといけない

https://scrapbox.io/files/65bf00e00bb31d00268619b2.png

quorum intersectionについて

https://scrapbox.io/files/65bf013408ffb600250bdf38.png

A1がダイレクトコミットすると、A2があり、A2はA1へのパスがある

結果的に投票されたcertificateもコミットされる？

パスがないということは正直なバリデータではないコミットだったということ

A1はvoteが一つしかないからA1はコミットできない

A2はvoteが0

A3は直接コミットできる

次はA3とA2の間にパスがあるか確認

ないのでスキップする

だけどA3の前にA1をコミットしないといけない

理由はわかるけど、A2しなくていいのはパスがないから？

ということはA1 - A3間でパスがなかったらスキップできるということ？

それともA1はVoteしているからスキップできない？

A1からの順序付けは再帰的に続行される

https://scrapbox.io/files/65bf037858578c002469b39f.png

決定論的にDAGの因果関係をエンコードする

決定論的であればルールがどうでも同じ結果になる

https://scrapbox.io/files/65bf04724719350024246d76.png

Byzantine Consistent Broadcast

所有オブジェクトのシンプルなtxのためのアルゴリズム

例

P2Pトークン転送、NFTの大量鋳造、投票、dAppsでのメッセージ送信

コンセンサスレス

https://scrapbox.io/files/65bf06f7ba54c90023bb5d29.png

誰でも読み書きできる共有オブジェクト

例

AMM、公開入札によるオークション、あらゆる取引を受け付けるセントラル・リミット・オーダーブック（CLOB）など

ここでdag構築までやる

https://scrapbox.io/files/65bf07a47962240024e0333e.png

Bullsharkはtxの完全なソートをしているだけ

bullsharkはnarwhalが構築してくれたdagの最適化、通信オーバーヘッドをゼロにした

https://scrapbox.io/files/65bf07e8d94aa90024b3c5e0.png

まとめると

ラウンド1までnarwhalの役割

Suiの検証者はEtherやSolanaのような計算プレッシャーにさらされることはない

NFTの大量mintは取引はDeFiのアクティビティに関連する取引から分離されるため、コンセンサスを得る必要がなく（すなわち、グローバルな順序付けが不要）

検証者とコンセンサスのリソースが解放される

https://scrapbox.io/files/65bf07f83876160025fb6b94.png

並行処理

EVMの課題

効率性

スケラビリティ

理由

EVMの主な制限の1つは、トランザクションを逐次実行しなければならないことである。一度に実行できるトランザクションは1つだけで、他のトランザクションは実行が完了するまで待たなければならない。

sequential execution

並列実行, parallel execution

独立したトランザクションを特定し、それらを同時に実行すること

その後、依存するトランザクションは実行順に並べ替えられ、順次実行される。

難しいのはtx間の依存関係を特定すること

sui moveのobject-centric data modelが寄与してる

Evanの解説

スケーリングするためのobject-centric data model

トランザクションは対象のオブジェクトに基づいてグループ化される

各グループは別々のworkerによって独立して処理できる

バリデータはworkerを追加することでキャパシティを水平方向に拡張できる

バリデータは需要の急増に対応するため、より多くのworkerを「オン」にすることができる

https://scrapbox.io/files/65bf0a404a192200259fb49f.png

Suiは左側

駅はtxのグループ

それぞれのtxのグループごとに次の駅に行くように処理してあげればいい

既存のブロックチェーンは目的地（トランザクションの処理完了）までに全ての駅に行っている、東京で言えば半蔵門線、銀座線のようにトランザクショングループごとに目的地に連れて行ってあげたほうが早い

Suiの完全なasset-centric

各アセットは型付きオブジェクトとして表現される

グローバル・ストレージはMap<ObjectID, Object>

すべてのオブジェクトは安定したグローバル一意のIDを持つ

"すべてがNFT"といえる

全てのTXの入力、出力はオブジェクトで表現される

Txの依存関係は明示的で、静的に把握される

https://scrapbox.io/files/65bf0aa70bb31d0026866ef2.png