On consensus in public blockchains

In this paper, we formulate the consensus problem and its solutions as seen in public blockchains and contrast them to those of the traditional distributed consensus. The Proof of Work (PoW) algorithm introduced in Bitcoin provides the first elegant and practical solution for reaching distributed consensus in a large-scale untrusted environment. Due to the enormous energy cost of PoW, many alternative consensus algorithms have been proposed for public blockchains aiming at drastically reducing the energy consumption for reaching consensus. We examine four blockchain consensus algorithms, namely Proof of Work, Proof of Stake, Proof of Space, and Proof of Elapsed Time, with respect to the consensus model we have formulated and point out the challenges of adopting them in public blockchains.