Bootstrapping Public Blockchains Without a Trusted Setup

We propose a protocol that allows the participants of a permissionless decentralized system to agree on a set of identities in the presence of a computationally-bounded Byzantine adversary. Our protocol guarantees that the fraction of identities belonging to the adversary in the set of identities is at most equal to the total computational hash power of the adversary. We significantly improve on the existing state-of-the-art in the following four ways. First, our algorithm runs in expected O(1) rounds, in contrast to previous results which require O(log n/log log n) rounds, where n is the number of initial nodes in the system. Second, we require each node to solve just one computational puzzle, whereas previous algorithms require O(log n/log log n) puzzles per node. Third, our algorithm sends only O(n) bits per node in expectation, whereas previous algorithms send O( (log2 n/log log n)) bits in expectation. Finally, in contrast to past results, our algorithm handles dynamic joining and leaving of nodes.