Byzantine fault tolerant public key authentication in peer-to-peer systems

We describe Byzantine fault tolerant authentication, a mechanism for public key authentication in peer-to-peer systems. Authentication is done without trusted third parties, tolerates Byzantine faults and is eventually correct if more than a threshold of the peers are honest. This paper addresses the design, correctness, and fault tolerance of authentication over insecure asynchronous networks. An anti-entropy version of the protocol is developed to provide lazy authentication with logarithmic messaging cost. The cost implications of the authentication mechanism are studied by simulation.