Knowledge Connectivity Requirements for Solving BFT Consensus with Unknown Participants and Fault Threshold (Extended Version)
<|reference_start|>Knowledge Connectivity Requirements for Solving BFT Consensus with Unknown Participants and Fault Threshold (Extended Version): Consensus stands as a fundamental building block for constructing reliable and fault-tolerant distributed services. The increasing demand for high-performance and scalable blockchain protocols has brought attention to solving consensus in scenarios where each participant joins the system knowing only a subset of participants. In such scenarios, the participants' initial knowledge about the existence of other participants can collectively be represented by a directed graph known as knowledge connectivity graph. The Byzantine Fault Tolerant Consensus with Unknown Participants (BFT-CUP) problem aims to solve consensus in those scenarios by identifying the necessary and sufficient conditions that the knowledge connectivity graphs must satisfy when a fault threshold is provided to all participants. This work extends BFT-CUP by eliminating the requirement to provide the fault threshold to the participants. We indeed address the problem of solving BFT consensus in settings where each participant initially knows a subset of participants, and although a fault threshold exists, no participant is provided with this information -- referred to as BFT Consensus with Unknown Participants and Fault Threshold (BFT-CUPFT). With this aim, we first demonstrate that the conditions for knowledge connectivity graphs identified by BFT-CUP are insufficient to solve BFT-CUPFT. Accordingly, we introduce a new type of knowledge connectivity graphs by determining the necessary and sufficient conditions they must satisfy to solve BFT-CUPFT. Furthermore, we design a protocol for solving BFT-CUPFT.<|reference_end|>
@article{heydari2024knowledge,
    title={Knowledge Connectivity Requirements for Solving BFT Consensus with
  Unknown Participants and Fault Threshold (Extended Version)},
    author={Hasan Heydari, Robin Vassantlal, Alysson Bessani},
    journal={arXiv preprint arXiv:2405.06055},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.06055},
    primaryClass={cs.DC}
}