Asynchronous Byzantine consensus suitable for decentralized networks using cryptographic randomness

Dominic Williams


For over 30 years the distributed computing community has worked on Byzantine consensus protocols, but when Bitcoin became the world's first transactional decentralized network it introduced a new type of consensus system. Known as Proof of Work or Nakamoto consensus, its new consensus system relied heavily on expenditure of electricity for security, scaled poorly and was slow and only eventually consistent. That such a system should trounce decades of work was down to critical difficulties with conventional consensus protocols. These include the vulnerability of protocols that must pass messages to reach consensus to sybil attack, message passing that is minimally quadratic in the number of distributed processes and reliance on theoretical computing constructs that cannot be easily be obtained in decentralized environments.

As a consequence of such difficulties, many hailed Nakamoto blockchain technology with all its drawbacks as a necessary compromise in decentralized network design. However, in fact this is far from the truth. The author's research focuses on combining Nakamoto chains with conventional consensus techniques to produce fast and scalable decentralized networks. In these systems a Nakamoto chain acts as a source of randomness, heart beat and log of Merkle roots, and the task of agreeing upon data transitions is performed by a new generation of highly tuned and optimized conventional consensus protocols. The science behind these protocols and their designs are interesting subjects in their own right, and are addressed by this talk. The protocol framework eventually presented enables 500 distributed processes to simultaneously present their data sets to the group and quickly reach strongly consistent agreement on an accepted superset by passing between only 0.5 and 1MB of protocol messages (such that a network reaching consensus every 5 seconds would have spare bandwidth to process many thousands of transactions a second).

We will first explore a more structured approach to understanding sybil resistance, and review three means by which sybil-resistant cryptographic identities that allow the use of conventional consensus protocols might be created. Then we will see how consensus protocol math is optimized and proven sound against different network models, and see arguments why those designed using asynchronous network models (as opposed to synchronous and partially synchronous models that include timing assumptions) are preferable in decentralized environments. We will see how asynchronous protocols can be leader-free and how they can use on-demand sources of shared randomness (known as "common coins") to bring participating processes to agreement. Finally we will examine a specific protocol framework that uses deterministic homomorphic threshold signatures to create cryptographic randomness without having a trusted dealer, and which leverages a new trick that allows it to efficiently run massive numbers of binary leader-free asynchronous randomized consensus protocols in parallel to quickly agree a combined data set from the inputs of large numbers of processes.

Time and Place

Tuesday, May 5, 4:15pm
Gates 463