Consensus is 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 identified for knowledge connectivity graphs by BFT-CUP are insufficient to solve BFT-CUPFT. Accordingly, we introduce a new type of knowledge connectivity graph that is sufficient for solving such a problem. To validate its sufficiency, we design a protocol for solving BFT-CUPFT.

Byzantine Consensus is fundamental for building consistent and fault-tolerant distributed systems. In traditional quorum-based consensus protocols, quorums are defined using globally known assumptions shared among all participants. Motivated by decentralized applications on open networks, the Stellar blockchain relaxes these global assumptions by allowing each participant to define its quorums using local information. A similar model called Consensus with Unknown Participants (CUP) studies the minimal knowledge required to solve consensus in ad-hoc networks where each participant knows only a subset of other participants of the system. We prove that Stellar cannot solve consensus using the initial knowledge provided to participants in the CUP model, even though CUP can. We propose an oracle called sink detector that augments this knowledge, enabling Stellar participants to solve consensus.

Byzantine Fault-Tolerant (BFT) State Machine Replication (SMR) is a classical paradigm for implementing trustworthy services that has received renewed interest with the emergence of blockchains and decentralized infrastructures. A fundamental limitation of BFT SMR is that it provides integrity and availability despite a fraction of the replicas being controlled by an active adversary, but does not offer any confidentiality protection. Previous works addressed this issue by integrating secret sharing with the consensus-based framework of BFT SMR, but without providing all features required by practical systems, which include replica recovery, group reconfiguration, and acceptable performance when dealing with a large number of secrets. We present COBRA, a new protocol stack for Dynamic Proactive Secret Sharing that allows implementing confidentiality in practical BFT SMR systems. COBRA exhibits the best asymptotic communication complexity and optimal storage overhead, being able to renew 100k shares in a group of ten replicas $5 \times $ faster than the current state of the art.