AUPE: Collaborative Byzantine fault-tolerant peer-sampling
Published in NCA, 2024
Peer sampling is a crucial primitive in distributed systems, used to manage overlays and disseminate information in large-scale scenarios such as permissionless blockchain systems. Its purpose is to maintain and regularly update a local and partial snapshot, or view, of the complete system’s membership. These protocols are often targeted by malicious actors who aim to disrupt higher-level protocols. Typically, an adversary who controls a set of Byzantine nodes attempts to manipulate how legitimate nodes perceive the presence of Byzantine ones by increasing their representation in the view of honest nodes. While state-of-the-art Byzantine-tolerant peer sampling protocols mitigate this bias, their effectiveness decreases ignificantly as the number of malicious nodes increases. This paper introduces AUPE, the first collaborative Byzantine-tolerant peer sampling protocol that leverages the presence of trusted nodes, such as Intel’s SGX capable devices, to collaboratively track the spread of identifiers in the system and locally debias the representation of Byzantine nodes. Simulations with 10,000 nodes demonstrate that AUPE outperforms state-of-the-art solutions, achieving near-perfect resilience even when faced with an adversary controlling 26% of the nodes. Overall, by including as few as 10% of trusted nodes, AUPE increases the tolerance of BRAHMS by up to 60% while limiting the impact of the adversary’s attack, even when possessing up to 40% of the nodes.
Recommended citation: A. Mukam, J. Bruneau-Queyreix and L. Réveillère, "AUPE: Collaborative Byzantine fault-tolerant peer-sampling," 2024 22nd International Symposium on Network Computing and Applications (NCA), Bertinoro, Italy, 2024, pp. 17-24, doi: 10.1109/NCA61908.2024.00015. keywords: {Fault tolerance;Protocols;Limiting;Fault tolerant systems;Collaboration;Peer-to-peer computing;Blockchains;Object recognition;Resilience;Gossip;Peer Sampling;Distributed System;Byzantine tolerance;Eclipse Attacks},
Download Paper | Download Slides