Proof-of-Stake systems randomly choose, on each round, one of the participants as a consensus leader that extends the chain with the next block such that the selection probability is proportional to the owned stake. However, distributed random number generation is notoriously difficult. Systems that derive randomness from the previous blocks are completely insecure; solutions that provide secure random selection are inefficient due to their high communication complexity; and approaches that balance security and performance exhibit selection bias. When block creation is rewarded with new stake, even a minor bias can have a severe cumulative effect. In this paper, we propose Robust Round Robin, a new consensus scheme that addresses this selection problem. We create reliable long-term identities by bootstrapping from an existing infrastructure, such as Intel's SGX processors, or by mining them starting from an initial fair distribution. For leader selection we use a deterministic approach. On each round, we select a set of the previously created identities as consensus leader candidates in round robin manner. Because simple round-robin alone is vulnerable to attacks and offers poor liveness, we complement such deterministic selection policy with a lightweight endorsement mechanism that is an interactive protocol between the leader candidates and a small subset of other system participants. Our solution has low good efficiency as it requires no expensive distributed randomness generation and it provides block creation fairness which is crucial in deployments that reward it with new stake.
@cite_35: Algorand is a truly decentralized, new, and secure way to manage a shared ledger. Unlike prior approaches based on proof of work , it requires a negligible amount of computation, and generates a transaction history that does not fork with overwhelmingly high probability. This approach cryptographically selects ---in a way that is provably immune from manipulations, unpredictable until the last minute, but ultimately universally clear--- a set of verifiers in charge of constructing a block of valid transactions. This approach applies to any way of implementing a shared ledger via a tamper-proof sequence of blocks, including traditional blockchains. This paper also presents more efficient alternatives to blockchains, which may be of independent interest. Algorand significantly enhances all applications based on a public ledger: payments, smart contracts, stock settlement, etc. But, for concreteness, we shall describe it only as a money platform.
@cite_9: We present “Ouroboros Praos”, a proof-of-stake blockchain protocol that, for the first time, provides security against fully-adaptive corruption in the semi-synchronous setting: Specifically, the adversary can corrupt any participant of a dynamically evolving population of stakeholders at any moment as long the stakeholder distribution maintains an honest majority of stake; furthermore, the protocol tolerates an adversarially-controlled message delivery delay unknown to protocol participants.
Ouroboros Praos @cite_9 is another PoS scheme that leverages VRFs for new random value generation on each round, similar to Algorand @cite_35 . The main limitation of this approach is that such randomness can be biased and thus the solution does not provide fairness.