ランダムサンプリング

DAブロックはヘッダーと本体で構成されています。ヘッダーは比較的小さく、直接ダウンロードして確認できますが、本体ははるかに大きく、データ可用性を検証するためにランダムにサンプリングする必要があります。ブロックが生成されると、サイズによって $k * k$ の断片にスライスされ、2次元RS（Reed-Solomon）コードを適用することで $2k * 2k$ の断片が生成されます。次に、各断片の各行と列に対してマークルツリーが作成されるため、 $2k + 2k = 4k$ のマークルツリーが存在します。

図5：データ可用性レイヤーのブロックスライシングとエンコーディング

これらの $4k$ のマークルルートは最終的に1つのマークルツリーを形成し、そのツリーのルートがブロック全体のルートとして使用されます。そして、ルートと他のメタデータをヘッダーに組み合わせます。その後、ヘッダーと元の本体がP2Pネットワークを通じてブロードキャストされます。他のDAノードがブロックを受信すると、上記と同じ方法で2次元RSエンコーディングを繰り返し、ルートを計算し、ヘッダー内のものと同じであれば受け入れます。

決済レイヤーのバリデータはDAブロック提案者からヘッダーを受け取り、少なくとも1つのDAノードに接続します。これらのバリデータはランダムに断片のsとそれらのブロックルートへのマークルパスをダウンロードします。それらの断片がすべて正常に取得できれば、サンプリングバリデータは非常に高い可能性でDAブロックの可用性を確認できます。

次に、ランダムサンプリングのこのようなメカニズムの下で、利用不可能なDAブロックが利用可能と認識される確率を計算します。上述のように、DAブロックは $2k * 2k$ 断片のRSコードにエンコードされ、各行または列の任意のk断片でその行または列を復元できるため、敵対者はブロック全体を利用不可能にするために少なくとも断片を保留する必要があります。

1つのバリデータがDAブロックからランダムに断片をサンプリングすると仮定すると、DAブロックが最小限の利用不可能な部分を持つ場合、単一のバリデータによって実行される少なくとも1つの利用不可能な断片をサンプリングする確率は以下のように示されます。

$P_{single}=1-\frac{C_S^{2k ⋅ 2k-(k+1)^2}}{C_S^{2k ⋅ 2k}}=1-\prod_{i=0}^{S-1}(1-\frac{(k+1)^2}{4k^2-i})$

これは、利用不可能なDAブロックを正しく認識できる最小確率でもあります。そして、決済レイヤーの委員会にN個のアクティブなバリデータがあり、そのうち最大でfが悪意のあるものであり、これはN/3未満です。また、DAブロックを確認するためにはN - f票を集める必要があります。したがって、無効なDAブロックを確認しないためには、N - f個の誠実なバリデータのうち少なくともf+1個のバリデータが利用不可能性を発見する必要があります。したがって、利用不可能なDAブロックは以下の確率でネットワークによって認識されます：

$P_{network}=1-\sum_{i=0}^f C_i^{N-f} ⋅ P_{single} ⋅ (1-P_{single})^{N-f-i}$

NEROでは、N = 21、f = 6なので、異なるkとSの下での確率は以下のように計算できます

$k=64, S=5 ⇒ P_{single}=77.94\%, P_{network}=99.81\%$

$k=64, S=10 ⇒ P_{single}=94.94\%, P_{network}=99.9999917\%$

$k=128, S=10 ⇒ P_{single}=94.66\%, P_{network}=99.9999987\%$

$k=128, S=15 ⇒ P_{single}=98.77\%, P_{network}=99.9999999999969\%$

$k = 128$ かつ $S = 15$ の場合、利用不可能なDAブロックはほぼ100%の確率で明らかになり、サンプリングバリデータはこのような条件下で元のデータのわずか0.09%をダウンロードするだけで済むことがわかります。

概要不正証明