# 5.2.1 Random Sampling

Last updated

Last updated

The DA block contains a header and body. The header is relatively small and can be downloaded and checked directly, whereas the body is much bigger, which is the one needed to be sampled randomly to verify data availability.When a block is produced, it is sliced into * k* ∗

These 4* k* Merkle roots are finally formed into one Merkle tree and the root of the tree is used as the root of the whole block, and we combine the root and other metadata into the header. Then the header and original body are broadcast through the P2P network. When other DA nodes receive the block, they will repeat the 2-dimension RS encoding the same way above and calculate the root, then accept it if it is the same as the one in the header.

The validators of the settlement layer receive the header from the DA block proposer and connect to at least one of the DA nodes. These validators randomly download s of the fragments and their Merkle paths to the block root. If all of those fragments can be acquired successfully, the sampling validator can confirm the availability of the DA block at a very high possibility.

That is also the minimal probability that one can correctly recognize an unavailable DA block. And if we have * N* active validators in the committee of the settlement layer and at most

In NERO, we have * N* = 21,

We can see that when * k* = 128 and

Next, we will calculate the probability that an unavailable DA block is recognized as available under such a mechanism of random sampling. As stated above, the DA block is encoded into RS code of 2* k* * 2

Assuming that one validator randomly samples $S(0 \lt S \le (k+1)^2)$ fragments from a DA block, the probability of sampling at least one unavailable fragment performed by a single validator is shown below if the DA block has the minimal $(k+1)^2$ unavailable pieces.

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

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

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

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

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

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