Introduction
In this blog post, we present a high-level overview of the paper describing the Ouroboros Proof of Stake protocol implemented in Cardano´s blockchain. After the overview follow some comments about theoretical aspects of the protocol.
In general, Proof of Stake (PoS) consensus protocols elect the network nodes responsible to send the next block to the blockchain on the basis of the nodes’ amount of stake. The great benefits of PoS blockchains compared to Proof of Work blockchains are
- Much smaller consume of energy when scaled to millions of users
- Decentralised due to its intrinsic way of electing the next block proposer (no mining power concentration)
- Better performance
The main challenge of such protocols consists in designing a secure block proposer election which is safe against any adversarial intent to bias the outcome of the sortition. The Ouroboros PoS protocol solves this challenge and provides formal security proofs which guarantee a consistent view of the ledger to all users. There are several other research projects on this topic such as Algorand and Snow White. The Dfinity project is only about consensus, but can be coupled with some PoS to protect against Sybil attacks. There are different versions of PoS protocols like Ethereum’s Casper bonded PoS which is based on penalizing misbehaviour or delegated PoS proposals, e.g. in BitShares.
Historical note: In 2011, QuantumMechanics proposes in the forum BitcoinTalk PoS instead of PoW.
Ouroboros Protocol Overview
In this section we briefly summarize the basic ideas behind the Ouroboros protocol.
2.1. Epochs. The entire history of the blockchain is built by epochs in which the distribution of stake is considered to be fixed. Each epoch is subdivided into slots and each slot has one block proposer who extends the chain by signing the block which includes the slot number. The genesis block contains the public keys of all stakeholder together with their stake which is updated at the end of each epoch.
2.2. Leader Election and Consensus. For each slot of an epoch a stakeholder U is elected for proposing a block with the probability reflecting his or her amount of stake at the current epoch. Similar to Bitcoin, honest block proposers select the longest chain to continue the blockchain, and valid blocks are those belonging to the chain of maximal length.
2.3. Incentives. Stakeholders should be online and verify transactions when they are elected for a block proposer (or even a bit before). The incentive function distributes the transaction fees of the blocks between block proposers. There are also block endorsers who are elected the same way as block proposers. They can reject or let pass the blocks and receive as well a part of the fee.
2.4. Stake Delegation. It is important that most stakeholders are online when elected. If this is not possible, stakeholders can delegate their rights to other stakeholders who form a staking pool. This is instantiated with a proxy signature scheme while the size of the staking pool is such that a malicious majority basically never occurs.
A “close-up” of some aspects of Ouroboros
The essential contribution of Ouroboros by Kiayias et al. to the cryptocurrency research community consists in setting forth a formal security model for PoS protocols and in defining a PoS protocol along with an instantiation. We try to detail the most important contributions in a concise manner.
3.1. Security Model. The authors of Ouroboros introduce a new security model suitable for their PoS protocol. This model is a modification and extension of the Bitcoin Backbone model. The functionalities modeled are the communication to extend the chain and for key registration reflecting the possibility of the adversary to corrupt stakeholders. The authors consider first a static state in which one epoch describes the entire lifetime of the blockchain and corruption is only allowed at the very beginning. In a second step, the dynamic state is described as an increasing sequence of epochs (static states) which reflects stakeholder and stake changes shortly before of each new epoch. The set of functionalities is extended by a perfect sub-routine of a random beacon generation necessary for the leader election. This random beacon is implemented later with standard cryptographic tools as explained below.
3.2. Proof: Static State. The security proof in the static state translates the chain extension rule into a pure combinatorial argument leading to the concept of forkable strings. The static model differs from the Bitcoin protocol as the next slot leaders of an entire epoch are known at once giving the adversary new attack strategies. Therefore, the proof of consistency and availability of the Ouroboros protocol does not follow directly from the Backbone Protocol paper. To capture this novelty, the notion of forkable strings is introduced representing honest and dishonest slot leaders in form of a string. Each entry of the string is associated to a directed tree with a labelling function reflecting all possible results of adversarial intents to fork the blockchain. The main result shows that even in the presence of an adversary the density of forkable strings decreases rapidly in time (even in exponential decay; see [RMKQ17]). The proof reformulates the problem as biased random walks and then applies probability estimates of Markov chains.
3.4. Instantiation and Proof: Dynamic State. The dynamic protocol adds to the static protocol the selection of the next slot leaders. The block proposers for each slot of epoch j are elected using a pseudo-random number generator with the follow-the-satoshi rule. It is necessary to introduce entropy in order to prevent grinding attacks. Ouroboros generates the random seed (uniformly distributed) using a secure multi-party coin-tossing protocol. Each block proposer of the previous epoch commits to a secret string in the commitment phase which they have to reveal at the end of the epoch in the opening phase and from which the random seed is derived. To protect the protocol against adversaries who will not open their secret, a verifiable secret sharing protocol is used so that honest parties can recover the secret even if an adversary withholds its secret. In order to prove high probability of consistency and liveness of the protocol, some assumptions have to be made. These are that all honest players are online for a sufficient long time, that the maximum stake shift over the last blocks is restricted, and that the adversary is not allowed to instantaneously corrupt. There is a lower bound for the corruption delay.
3.5. Nash Equilibrium. Beyond the cryptographic security, there might be rational strategies to win more than the honest strategy pays out. The authors prove (see theorem 7.1) that together with the second layer system of endorsement the honest strategy of the protocol is a near-Nash equilibrium showing in particular that the selfish-mining strategy does not apply to Ouroboros (See also this critical analysis).
Ouroboros Praos / Genesis / Crypsinous
Some improvements in subsequent work address the follwing topics
4.1 Network assumption. The synchronous network assumption says that the network delay is bounded by a known constant, i.e. < c. This assumption is not uncommon but the strongest about networks. In the subsequent work [DGKR17], Ouroboros Praos, the assumption is weakened to the semi-synchronous network assumption where c is unknown.
4.2 Adaptive Adversary. The Ouroboros protocol has to assume a certain delay for the corruption of stakeholders by an adversary. The Ouroboros Praos PoS protocol is fully adaptive corruption resistant in the sense that the adversary can corrupt at any time. This comes by using the same concept of Algorand, i.e. verifiable random functions.
4.3 Secure Bootstrapping. See the video Ouroboros Genesis for bootstrapping PoS protocols without any trust assumptions (and a great exposition of the entire Ouroboros proof).
4.4 Privacy. Crypsinous uses SNARKs to introduce privacy to Proof of Stake protocols.
References
[DGKR17] B. David, P. Gazi, A. Kiayias, and A. Russell, Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake protocol, Cryptology ePrint Archive, Report 2017/573, 2017.
[GKL15] J. Garay, A. Kiayias, and N. Leonardos, The bitcoin backbone protocol: Analysis and applications, Advances in Cryptology – EUROCRYPT 2015 (Elisabeth Oswald and Marc Fischlin, eds.), Springer Berlin Heidelberg, 2015, pp. 281–310.
[KRDO17] A. Kiayias, A. Russell, B. David, and R. Oliynykov, Ouroboros: A provably secure proof-of-stake blockchain protocol, CRYPTO, Springer, 2017, pp. 357–388.
[RMKQ17] Alexander Russell, Cristopher Moore, Aggelos Kiayias, and Saad Quader, Forkable strings are rare, Cryptology ePrint Archive, Report 2017/241, 2017, https://eprint.iacr.org/2017/241.
