Unpredictability properties in Algorand consensus protocol

Abstract

The Algorand consensus protocol, introduced by Chen and Micali in 2016, uses a pure proof-of-stake protocol based on Byzantine agreement rather than the well-known Bitcoin proof-of-work. In this paper, we analyze specific security properties of Algorand related to "unpredictability". The unpredictability property has been initially defined by Boneh et al. in the context of single secret leader election. We show that Algorand satisfies the original unpredictability property. Then, we extend the unpredictability property to a more generic property referred to as "t-forward unpredictability" and show that for a particular setting of Algorand, the t-forward unpredictability property is not satisfied. Specifically, we provide a strategy enabling to predict the future leaders.