Byzantine and Honest Nodes Distribution in Random Partitions Under an Adaptive Adversary

Following the Fischer, Lynch, and Paterson impossibility result, a certain degree of synchronisation or randomisation is used in agreement tasks such as Byzantine Agreement protocols. Ben-Or and Bracha designed intuitive randomised protocols to solve Byzantine Agreement, but both terminate in expected exponential time in general. Subsequently, Kapron, Kempe, King, Saia, and Sanwalani presented the first efficient Byzantine Agreement. It integrates several fundamental components of randomisation, including the averaging samplers. Averaging samplers are mainly used against static adversaries because they generate small subsets of nodes, where most of them are honest. So, very useful for scaling byzantine task as Byzantine Agreement, committee election and broadcast protocols. However, given the small size of these subsets, an adaptive adversary can potentially compromise the entire subset. In this work, we propose a theoretical alternative to averaging samplers that allows any arbitrary selection of byzantine nodes \(\mathcal {B}\) $\mathcal{B}$ \(\left( \frac{|\mathcal {B}|}{n} < \frac{1}{3} \right) \) $\left(\frac{|\mathcal{B}|}{n},<,\frac{1}{3}\right)$ . We start by considering a set of nodes indexed as integers [n] and then generate a partition \(\{I_1, \dots , I_p\}\) $\{I_1,\cdots ,I_p\}$ of [n]. Then, we focus on the values taken by the vector \( \left[ |I_1 \cap \mathcal {B}|, \dots , |I_p \cap \mathcal {B}| \right] ^T\) ${\left[|,I_1,\cap ,\mathcal{B}|,\cdots ,|,I_p,\cap \mathcal{B}|\right]}^T$ . Through a combinatorial analysis, we generate \(\tilde{\mathcal {O}}(1)\) $\tilde{\mathcal{O}}(1)$ independent random partitions and show that, almost surely, for any set of Byzantine nodes \(\mathcal {B}\) $\mathcal{B}$ , there exists at least one partition where the number of fully compromised subsets is significantly small, in the sens that each honest nodes can be separated by at most poly-logarithmic in n byzantine nodes. While an adaptive adversary may compromise multiple subsets in some partitions, across the \(\tilde{\mathcal {O}}(1)\) $\tilde{\mathcal{O}}(1)$ partitions, there will be partitions where only a limited number of subsets that are fully Byzantine. The probability of failure of our result is negligible, i,e., bounded by \(e^{-n (1-\ln (2))}\) $e^{-n(1-ln(2))}$ . This work serves as a guide for future efficient and scalable distributed protocols that consider an adaptive adversary.