occur when malicious users create multiple fake identities to gain an advantage over honest users. Wireless ad hoc networks are particularly vulnerable to these attacks because the participants are not known in advance, and they use an open and shared communication medium. In this paper, we develop algorithms that thwart sybil attacks in multi-channel wireless ad hoc networks using
radio resource testing
strategies. In particular, we describe and analyze new anti-sybil algorithms that guarantee, with high probability, that each honest device accepts a set of trusted and unforgeable identities that include all other honest devices and a bounded number of fake (sybil) identities. The proposed algorithms provide trade-offs between time complexity and sybil bounds. We also note that these algorithms solve, as subroutines, two problems of independent interest in this anonymous wireless setting: Byzantine consensus and network size estimation.