Dankshardingとは?
↓この辺を和訳しながら紐解く
0. 今までのデータシャード
beacon chainにn=64のdata shardを追加する。
各スロットで n人のblock proposerが独自にshard blobを提案し、committeeがそれを確認する。
shard blobが確認されると、実行チェーンから参照できるようになる。
data availabilityもcommiteeが検証する
懸念点
ほとんどの場合、次のbeacon blockには、確認されたすべてのshard dataに関する情報が含まれるが、これは保証されていない
すべてのシャードについてグローバルにチェックを行うことはできない
各block proposerがプロセス全体を中断する可能性もある(liveness failure)
https://scrapbox.io/files/620a336d6dec4f0023a36b31.png
https://scrapbox.io/files/620a338c57949c001d5f3d52.png
32ETH以上保有すればバリデータになれるので、そのようなアカウントを多数作成すれば、committeeは乗っ取れる。 →つまり、そのようなシャード次第では中央集権的に活動ができ、理論上は二重支払いも可能?
もともとEthereumは複数のexecution shardsを持つことによる水平方向のスケーリングを計画していた。
shardingにはPoS移行が前提となるので、直近のアップグレードはPoS移行に注力しておりshardingはまだ実装されていない
しかしexecutionとsettlementを分離するrollupの発明により、L2・L3による垂直方向のスケーリングが可能となったり, ボトルネックはsettlementにおいていかに安価にdata availabilityを確保するかという点となった。
これに合わせてshardingについてもまずはexecutionを行わないdata shardsとする方針が固まりつつある。
つまり、データだけシャーディングして、実行は後回し
ちなみに、PoWを用いたEthereumを指すETH1は、"execution Layer "に「改名」され、ETH2(またはEthereum 2.0)、つまりPoSへの移行が確定した段階は、"Consensus Layer "とされる
The Margeの理解が必要そう...
1. Danksharding
今までの危険性を考慮し、新しい設計では大きく以下の2点がポイント
1. beacon blockにすべてのshard blockが含まれる
2. それらはすべて1つのcommitteeによってまとめて確認される
すべてのbeacon dataとshard dataが一緒に確認できる
各committeeのメンバーは、シャードデータの小さなサブセットのみをサンプリングして統計的に検証する
この変更にはKZG Commitmentによる証明-検証プロセスが用いられている。
具体的には以下のように変更が加えられる。
新しいタイプのトランザクションを追加し、calldataとして追加のシャードデータを含むことができるようにする。
そしてブロックは単一のブロックビルダー(プロポーザルビルダー分離を使用してプロポーザルと異なることができる)によって構築され、通常のトランザクションだけでなく、シャードされたcalldataを持つトランザクションも含まれる。
https://scrapbox.io/files/620a338347c6e7001d67c6fc.png
calldataのshardingが行われる新しい種類のトランザクションを導入し、rollupのsettlement時にデータを保存するのに使おうという提案でもある
calldataとはトランザクションの引数で、コントラクトに状態を保存するより安価なのでrollupのdata availabilityを担保するのに使われている。このcalldataをshardingすることで、より安価なdata availabilityを実現する。この辺はこのスライドがわかりやすい Dankshardingが可能となる前提にPBS(Proposer/Builder Separation)とcrListがある。
PBSはハードウェア要件の低いblock proposerとハードウェア要件の高いblock builderを分離することで分散性を確保するもの。Dankshardingではblock builderのコストが上がるのでPBSが必要。
誰がblock builderになるのか?という問いについては、MEVによって利益を得たい者が解となる。MEVが発見される以前には考えられなかったコンセプト。
crListはPBSを前提として、proposerがbuilderにトランザクションの取り込みを強制することで対検閲性を上げる仕組み。
2. 背景、PBS、crList
以前は、cencershipを最大化し、block proposerの要件を最小化するために、多くの異なるshard proposerを持つことが最善であるとされていたが、MEVを考慮する必要が出てきた
↓
現在では、MEVに対する唯一の実行可能な解決策は、PBS(Proposer/Builder Separation)によるexcutiion blockのオークションだと考えられている
つまり、仕事の担当者を分けることでフロントランニングを防ぐ方針?
↓
したがって、通常のバリデータ(proposer)は、多数のblock builderから最も入札の多いブロックを選択するだけでよくなった
↓
しかしPBSの世界では、cencershipの点については非常に注意する必要がある
あーもしかして、PBSを使っているわけではない?PBSでは役割分担しても目的が一緒ならフロントランニングできるから、それを防ぐ的な?
block proposerは、ブロックに含ませたい全てのトランザクションのリスト(crList)を作成することができる。
そしてblock builderは、それらをすべて含めるか、あるいはガスの上限まで他のトランザクションでブロックを埋めなければならない。
これは、検閲のコスト=継続的にトランザクションを競り落とすコストであるべきという性質を保存するもの
同期設計のおかげで、我々はL1上の新しいシャードデータ構造を持ち、シャードデータに直接依存しアクセスすることができ、それはcrListに入ることができる
つまり、今までよりも「cencershipを最大化し、block proposerの要件を最小化」できるようになるよという提案?
3. メリット
現在のEth1チェーンとの緊密な結合 - ロールアップデータがマネージャーコントラクトに即座に表示される。
すべてのデータはロールアップコールと一緒に確認される。
shard blockが確認されるまで待つ必要もshard dataの重複などを気にする必要もない。
Rollupは、shard scan Logicを実装する必要がない。それらに宛てられたデータは、L1トランザクションを使用して直ちにラベル付けすることができる
シャード用に別のPBSを用意する必要がない
これにより、block builderは2つの異なるシステムを構築する必要がなくなる
また、データとexcutionの相互作用によるMEVをblock builderがリスクなく利用できることを意味し、block builderの中央集権化を抑制できる
シャードトランザクションの決済システムを別途用意する必要はない
シャードされたcalldataのコストは、それを使用しているトランザクションに直接請求することができる
既存のイーサリアム取引決済インフラを全てそのまま利用できる
より大きなcommittee(バリデータ集合の1/32)でデータを確認できるため、賄賂への耐性が向上する。
shard blockの確認が不要なため、トランザクションの集計が容易になる
1スロットあたり1committeeのみでよい(PBSは2committee)
beacon blockとexcution blockをdata availabilityセットに即座に追加することができる
アプリケーションが使用したいシャードにコミットする必要がない
4. Dankshardingが実装された先の世界
4.1 L2
同じbeacon block内のTxがshard dataにアクセスできるので、zkruとL1間の同期トランザクションも可能になる
ZKRollupsによりL2からL1への同期呼び出しが可能
実際にKZG Commitment使ったzkru実装あるっけ?
4.2 ライトクライアント
beacon chainがfraud proof可能なものになれば、スーパーライトクライアント(データ利用のみ)が可能になる。
現在のshard blob市場は非効率的
私たちは64人の独立した提案者を主張しています。しかし、実際には、これは不可能です。なぜなら、これは多くの重複を確認することにつながり、その結果、市場の中央集権化を招くことになるからです。
1つのシャードで10個のblobを確認する必要がある場合、それらすべてを同じスロットに含めるように入札する効率的な方法はありません(オール・オア・ナッシング入札)。
より小規模なクライアントが可能
1MB/ビーコンブロック(60kb/s)→ 約40kb/ビーコンブロック(2.5kb/s)
2dサンプリングを即座に提供できるため、これだけで全データ可用性サンプリングを行うことができるようになった
verkle triesの準備が整い次第、data availability+不正防止されたライトクライアントが実行できる
"ロールアップとしてのEth1"
フルEth1ノードを実行する必要のない、より軽量なバリデータ+ノードを可能にする。
5. デメリット
Block Builder への要求が増える
32MBのデータに対してKZG証明を1秒で計算する。これには32-64コアのCPUが必要。
最低必要帯域を大きくする。64MBのデータをビルダー期限内に送信できること、P2Pで配信されることを確認する必要がある。おそらく上流で最低2.5GBitは必要。
Block Builder の作業は以下の二つ
1. サンプルのKZG Witnessを計算すること
めっちゃ時間かかるのでデータセンター使って分散処理させる?
GPU で計算を ~1 秒で完了させることができるという意見もある
2. サンプルをP2Pネットワークに播種すること
まずは2つ目のタスクから。約128MBのサンプルがあり、各サンプルを少なくとも5つのピアに分散させたい
そしてこれらすべてが1秒以内に行われるとすると、ビルダーは640MB/sまたは5GBit/sのアップストリームを必要する
excutionとdata availabilityを提供するビルダーは、より強力になる。
しかし、PBSでは、とにかく他の検閲耐性方法が必要。このシステムでは、それらは別の問題として扱われることができる。現在提案されているモデルは、提案者が特定の取引を強制的に含ませる力を持つ
6. シャード化されたmempoolが必要
6.1 理由
現在のmempoolは、データトランザクションに対して拡張性がない。
すべてのノードが全mempoolを処理するが、シャーディングによってチェーンの容量は1.3MB/sに増加し、これはすべてのトランザクションがそれを通過する場合に予想されるmempoolの帯域幅の下限値でもある
ノードに全mempoolの処理を要求しながら、データトランザクションをチェーン上でシャーディングする代わりに、データトランザクションが関係している場合は、mempool上でもdata availabilityのサンプリングを行う
6.2 そもそもmempoolは必要?
パブリックmempoolにトランザクションを送る代わりに、ブロックビルダーにトランザクションを送るという方法がある。
ブロックビルダーはトランザクションをフロントランしないことを約束できるのが利点
もしそうであれば、ユーザーは他のブロックビルダーに乗り換えればいい
したがって、mempoolのサイズはかなり小さくなり、チェーンにはまったく必要なくなる可能性が高い。
Solanaはこの設計を実装していて、トランザクションを次の提案者にしか送らないらしい
7. 実装
2次元のKZGコミットメントを使用してすべてのデータをコミットするBlockKZGCommitmentというブロック用のコミットメントは以下の3つのコミットメントに用いられる。
1. BeaconBlock
2. ExecutionPayload
3. shard data
ExecutionPayloadはThe Margeで新設されたデータ。今までのL1及び、Execution Layerから上がってくるデータのこと
code:constrant
MAX_SHARDS = 2**8 # 256
SHARD_SIZE_FIELD_ELEMENTS = 2**12 # 2**12*31 = 126976 bytes
MAX_BLOCK_SIZE = SHARD_SIZE_FIELD_ELEMENTS * MAX_SHARDS # 2**20 field elements / 32,505,856 bytes
TARGET_BLOCK_SIZE = MAX_BLOCK_SIZE // 2 # EIP1559 for data gas
code:BlockKZGCommitment
class ShardedBeaconBlockCommitment(Container):
beacon_block_commitments: uint64 # Number of commitments occupied by Beacon block + Execution Payload
# Aggregate degree proof for all sharded_commitments
degree_proof: KZGCommitment
beacon_block_commitmentsまでのShardedBeaconBlockCommitmentは、BeaconBlock(ExecutionPayloadを含む)をフィールド要素ごとに31バイトにエンコードしたもの
code:ExecutionPayload
class ExecutionPayload(Container):
# Execution block header fields
parent_hash: Hash32
fee_recipient: ExecutionAddress # 'beneficiary' in the yellow paper
state_root: Bytes32
receipt_root: Bytes32 # 'receipts root' in the yellow paper
random: Bytes32 # 'difficulty' in the yellow paper
block_number: uint64 # 'number' in the yellow paper
gas_limit: uint64
gas_used: uint64
timestamp: uint64
base_fee_per_gas: uint256
# Extra payload fields
block_hash: Hash32 # Hash of execution block
# NEW fields for data gas market
data_gas_limit: uint64
data_gas_used: uint64
data_base_fee_per_gas: uint256
code:TransactionKZGCalldataPayload
@dataclass
class TransactionKZGCalldataPayload:
chain_id: int = 0
signer_nonce: int = 0
max_priority_fee_per_gas: int = 0
max_fee_per_gas: int = 0
# New data gas
max_priority_fee_per_data_gas: int = 0
max_fee_per_data_gas: int = 0
gas_limit: int = 0
destination: int = 0
amount: int = 0
payload: bytes = bytes()
# KZG Calldata
access_list: List[Tuple[int, Listint]] = field(default_factory=list) signature_y_parity: bool = False
signature_r: int = 0
signature_s: int = 0
タイプ3の各トランザクションのすべてのkzg_calldata_commitmentsがShardedBeaconBlockCommitmentのsharded_commitmentsに含まれることを要求するvalidity conditionがある。
EVMに新しいオペコード、KZGCALLDATAを追加し、指定したメモリー位置にkzg_calldata_commitmentsを追加
シャード化されたコミットメントが正しくエンコードされていることを検証する
各コミットメントについて、その次数(degree)が < SHARD_SIZE_FIELD_ELEMENTS であることを証明する次数証明があり、以下のペアリング式でチェックされる。
e(degree_proof,$ {[1]}_2 )=e(sharded_commitment,$ { s^{SETUP-MAX-DEGREE-SHARD-SIZE-FIELD-ELEMENTS}}_2)
シャードされたコミットメントが2N個ある場合、最初のN個はデータを表し、残りのN個は多項式の拡張である。2N個が次数N-1の多項式上にあることを検証する必要がある。
標準的な方法:2Nの大きさのFFT(高速フーリエ変換)を行い、高次のN個の係数が0であることを確認する。
これには2Nlog2Nの群発乗算が必要であり、比較的高価である
より安価な方法:バリセントリック公式を使い、フィールドのランダムな点での最初のN個のコミットを評価し、後半も同じように評価する。もし両方の点が同じであれば、それらは次数N-1の同じ多項式上にあることになります。
つまり統計的に検証する手法
これには2Nの大きさのMSMが1つ必要なだけで、時間は約30分かかります。
2N/log2Nの群乗算の時間がかかります。
BLS12_381オペコードの追加(合理的なシャーディングの実装には必要です)
8. サンプリング
元データに対して最大256個のシャードされたコミットメントがあり、多項式拡張により最大512個まで拡張される 各シャードされたコミットメントは次数が$ 2^{12} である。
サンプリングのために $ 2^{13} のフィールド要素に拡張される。
そうすると、512×512の正方形をサンプリングすることになる
1ブロックあたり $ 32∗512=2^{18}=262144 個のサンプル
これらのサンプルのうち50%がブロック全体を再構成するのに十分な量
さらに、50%のサンプルからは任意の行/列を復元できるため、ブロックのシードが意図的に 欠けている場合でも、効率的に復元することができる。
各バリデータには32個のランダムな列が割り当てられ、次のattestationの際にそれらを 保管しなければならない。
つまり、attestationは合計で 32・32・512サンプル
これは、各ブロックがバリデータ全体の1/32の賄賂抵抗力を得るという良い副次的効果をもたらす
1つのブロックに対して、バリデータの1/2以下の賄賂は意味がない)。
blobがなぜ成り立つのか
PBSがなぜ必要なのか
KZGが重いからseparationが必要