ZODA's security relies on two key probabilistic checks to ensure that the sampled data is correctly encoded:

Sparsity Check: Ensures that a randomly selected subset of rows or columns is "close" to a valid codeword.

Subspace Distance Check: Ensures that the encoding follows the expected RS structure.

In addition to these, this document will also include probability calculations for DAS:

Unrecoverability Check: Ensure whether enough encoded data is available to reconstruct the original data

Sparsity Check in ZODA

Purpose

The sparsity check ensures that a random subset of rows or columns follows the expected error-correcting code structure. This prevents an adversary from constructing "fake" encodings that pass verification with only a few correct rows/columns.

Mathematical Formulation

The probability that a randomly sampled subset S of rows (or columns) is incorrectly encoded but still passes the check is:

$p = \left(1 - \frac{q}{m} \right)^{|S|}$

where:

• $q=n/2$ (for RS encoding with rate 1/2),
• m = 2n (since RS encoding doubles the size),
• $|S|$ is the number of sampled rows.

Intuition

• If too many rows or columns are incorrect, the check fails.
• Increasing |S| (sample size) reduces error probability.
• If $p$ is small, the sampled rows are likely to be correct.

Subspace Distance Check in ZODA