Owner: @Alexander Mozeika

Reviewers: 🟢@Marcin Pawlowski 🟢@Marvin Jones ****🟢@Mehmet  🟢@Álvaro Castro-Castilla

Introduction

This document examines the conditions required for fair and reliable distribution of rewards in a decentralised data availability (DA) network, where $N$ nodes independently sample peers to judge their performance. Our focus is on three core properties:

1. Ensuring coverage. We show that even when each node samples only a small number of peers per round, across $T$ rounds, the probability that every node gets observed is very high when $N<T$.
2. Stability of peer sampling. By treating the collection of all peer samples as a random graph, we demonstrate that each node's number of observations remains tightly clustered around the average. This ensures the mechanism stays predictable and robust.
3. Robust opinion aggregation. We consider a simple majority-vote rule for combining all (binary) reports of nodes into a single consensus judgment and prove that this rule tolerates the maximum number of inconsistent or malicious reports without breaking.

Throughout, we support our theoretical claims with simulations and numerical experiments, showing that the proposed sampling rates, observation windows, and voting thresholds create an efficient, scalable reward system that is both reliable and resilient against failures or adversarial behaviour.

Key Findings

• Small sampling rates achieve network coverage exponentially fast when the block count exceeds some fraction of the network size as can be seen in the figure below:

The probability to achieve full coverage plotted as function of the number of blocks $T$ for the network size $N\in\{10^2,10^3,10^4\}$. Here it assumed that a node samples $K=20$ nodes per block.

• The number of blocks $T$ needed to achieve full coverage (with high prob. ) is less than the network size $N$ as can be seen in the figure below:

The number of blocks $T$, which is needed to achieve full coverage (with prob. $0.99$ and $0.999$), is plotted as function of the network size $N$. Here it assumed that a node samples $K=20$ nodes per block.

• Node connectivity follows a predictable binomial distribution.
• The $N/2$ threshold maximises disagreement tolerance while recovering true opinions.
• The system tolerates up to $\lfloor N/2 \rfloor$ disagreements in odd-sized networks and $N/2 -1$ disagreements in even-sized networks.

This analysis provides theoretical foundations for a robust decentralised reward system resistant to failures and adversarial behaviour.

Overview

This document examines conditions for fair and reliable reward distribution in a decentralized data availability network with independent peer sampling.

We present a comprehensive mathematical model and theoretical framework supporting the reward distribution system. The framework consists of: