Formalizing Proof of Stake-based Consensus: Ouroboros

From Wikipedia entry on Ouroboros: “The Ouroboros or uroborus is an ancient symbol depicting a serpent or dragon eating its own tail.. from ancient Greek: οὐροβόρος, from οὐρά (oura), ‘tail’ + βορά (bora), ‘food’ “

I read the Ouroboros paper this summer, and we spent some time discussing it in a Blockchain research reading group yesterday. I wanted to jot down a few notes about it that may be of interest to researchers wanting to learn how to formally analyze permissionless consensus mechanisms.

Ouroboros is a Proof of Stake (PoS)-based permissionless consensus protocol for cryptocurrencies. It is deployed as part of Cardano, which has a cryptocurrency called ADA associated with it. The basic idea in PoS is to replace the energy-expensive Proof of Work (PoW) common in first generation Blockchain protocols such as Bitcoin and the current version of Ethereum (although Ethereum has its own PoS protocols under development), with a lighter-weight mechanism where each node’s probability of being a block producer is proportional to how many coins it has.

A simplified version of how Ouroboros works is as follows. The protocol is synchronous, proceeding in rounds or slots corresponding to block creation. Several slots are batched into an epoch. At the beginning of each epoch, a committee of stakeholders uses secure multi-party computation to elect a random sequence of block producers for the slots within that epoch. The probability of selecting a particular node as block producer is proportional to its stake (number of coins owned). The committee also elects the committee for the next epoch.

The most important feature of Ouroboros is that it provides a formal framework to define what its guaranteed properties are and prove that they are achieved.

The authors of the paper, Kiayias et al., focus on the following two properties:

• Persistence: If a node declares that a transaction is stable (is validly included in the chain K blocks ago, where K is a given security parameter ensuring the property holds with very high probability), then other nodes will either confirm this statement or will not report as stable any other inconsistent transaction.
• Liveness: If all honest nodes attempt to commit a transaction as stable, then all queried nodes that respond honestly will report its stability within some transaction confirmation time u.

In earlier work it was shown that there are three elementary properties that guarantee the above two properties. The first of these, called common prefix, requires that the chain at two honest nodes share a common prefix before some k number of slots; the second, called chain quality, requires that in any sub-chain of length at least l, no more than a fraction (1-µ) can be from adversarial nodes; and the third, called chain growth requires that the chain grow linearly with some lower-bounded rate.

Figure from the Ouroboros paper: gray circles (blocks) are from adversarial block producers, which can suppress blocks and cause forks. Double-lined white circles (blocks) are from honest producers which follow an adopt the longest chain policy and pick a single chain starting from the genesis block. There is effectively a “race” between adversaries to create forks and honest nodes to stop them. By their higher power, the honest nodes win this race relatively quickly. In this example, at the final block 9, there is a single longest chain.

The crux of their analysis of how these elementary properties are achieved in Ouroboros is showing that while adversaries can introduce forks in the chain (by sharing different versions of the chain with other parties and by suppressing blocks) they are limited by their lower stake-power to how long these forks can be. In particular, they show that the probability of a fork of length n is upper-bounded by a decreasing function that is exponential in the square-root of n. This analysis, in turn, relies on some key capabilities provided by the honest parties. To quote from the text:

“… any chain C broadcast by an honest player must begin with a chain produced by a previously honest player (or, alternatively, the genesis block), continue with a possibly empty sequence of adversarial blocks and, finally, terminate with an honest block. It follows that the chains broadcast by honest players form a natural directed tree. The fact that honest players reliably broadcast their chains and always build on the longest available chain introduces a second important property of this tree: the “depths” of the various honest blocks added by honest players during the protocol must all be distinct.”

Regarding chain quality, something interesting that the authors bring up is that the ratio of blocks contributed by honest µ within any sub-chain of some minimum length scales as (1–2α)/(1-α) for both Bitcoin and Ouroboros where α is the proportion of stake held by adversarial parties— this function decreases monotonically from 1 to 0 as α varies from 0 to 0.5 (showing the complete advantage that adversaries have when they exceed 50% power).

There is quite a bit more to this protocol; the paper presents and analyzes it under different adversarial assumptions and dynamic stake changes, and also presents a discussion of validation and incentive mechanisms, delegation mechanisms, and also various attacks and how the protocol addresses them. It also presents some results from an experimental implementation.

The secure multiparty computation used for the slot leader election is elucidated further in the Cardano documentation. Roughly speaking, a commit-reveal-recover protocol involving multiple electors is used to generate for them a common random seed that they then use (via an additional algorithm called FTS — for “follow the Satoshi”) to pick the holder of a coin uniformly from the set of coins to be nominated as the slot leader for a given slot. This is equivalent to picking a coin-holder proportional to the number of coins they hold.

I think the biggest contribution of the Ouroboros paper is showing how formal tools can be brought to bear on analyzing different permissionless blockchains, building on prior work by some of the same authors, on formally analyzing the Bitcoin protocol. These tools may be useful for analyzing other protocols as well.

References

• Kiayias, Aggelos, Alexander Russell, Bernardo David, and Roman Oliynykov. “Ouroboros: A provably secure proof-of-stake blockchain protocol.” In Annual International Cryptology Conference, pp. 357–388. Springer, Cham, 2017.
• Garay, Juan, Aggelos Kiayias, and Nikos Leonardos. “The bitcoin backbone protocol: Analysis and applications.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2015.
• Kiayias, Aggelos, and Giorgos Panagiotakos. “Speed-Security Tradeoffs in Blockchain Protocols.” IACR Cryptology ePrint Archive 2015 (2015): 1019.
• Cardano Settlement Layer Documentation: Ouroboros Proof of Stake Algorithm.