Exposing computationally-challenged Byzantine impostors

James Aspnes, Collin Jackson, and Arvind Krishnamurthy. Exposing computationally-challenged Byzantine impostors. Available as YALEU/DCS/TR-1332, July 2005.


Internet protocols permit a single machine to masquerade as many, allowing an adversary to appear to control more nodes than it actually does. The possibily of such Sybil attacks has been taken to mean that distributed algorithms that tolerate only a fixed fraction of faulty nodes are not useful in peer-to-peer systems unless identities can be verified externally. The present work argues against this assumption, by presenting practical algorithms for the central distributed computing problem of Byzantine agreement that defend against Sybil attacks by using moderately hard puzzles as a pricing scheme for identities. Though our algorithms do not prevent Sybil attacks entirely, they solve Byzantine agreement (and some useful variants) when the limited fraction of nodes that can fail is replaced by a limited fraction of the total computational power. These results suggest that Byzantine agreement and similar tools from the distributed computing literature are likely to help solve the problem of adversarial behavior by components of peer-to-peer systems.


title="Exposing computationally-challenged {B}yzantine impostors",
author="James Aspnes and Collin Jackson and Arvind Krishnamurthy",
institution="Yale University Department of Computer Science",

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page