Ouroboros Proof-of-Stake Blockchain Protocol: Assumptions and Main Theorems

Image Source: http://maxpixel.freegreatpicture.com/Coin-Money-Currency-Bitcoin-Electronic-Money-2729807 — Bitcoin and blockchain protocols

A blockchain protocol is essentially a distributed consensus protocol. A Proof-of-Work protocol such as Bitcoin requires a user to show a proof — such as making a large number of computations — before he can add a block to an existing chain. Proof-of-Stake protocols, on the other hand, would not require “burning electricity” since the ability to “mine” a coin would depend only on the user’s current stake at the system.

The growing computing power of the bitcoin miners is already consuming a significant amount of electricity. One can easily see the necessity of a provably secure and efficient cryptocurrency without the heavy energy requirement. However, it is easier said than done. So far, I am aware of only three Proof-of-Stake protocols which give provable security guarantees. These are Ouroboros, led by Aggelos Kiayias, Alex Russell, and others; Snow White, led by Rafael Pass and Elaine Shi; Ouroboros Praos from the Ouroboros team; and Algorand, led by Silvio Micali. There is also an open-source initiative to implement Ourorboros, named Cardano.

In this post, I am going to present the main theorems of Ouroboros.

A Brief Survey of Proof of Stake Blockchain Protocols with Provable Security

Garay, Kiayias, and Leonardos proved that the Bitcoin backbone protocol is secure. Pass, Seeman, and Shelat proved that the blockchain protocol is secure even in an asynchronous network. Ouroboros was the first proof-of-stake protocol which was provably secure in the synchronous setting. Snow White came soon after, proving security in an asynchronous setting with a focus on allowing users to leave and join as they wish.

In the traditional blockchain protocol, each user computes a hash function on a random input. This is similar to tossing a biased coin: If (a prefix of) the output string contains a given number of zeros, the user “wins” and becomes a “leader” i.e., he gets to add a block to a chain. Ouroboros departs from this idea in that the leaders for a designated number of future time slots are publicly precomputed. This, however, makes it necessary that the honest users be present when the leader election takes place. Additionally, Ouroboros assume that the network is synchronous.

On the other hand, in Ouroboros Praos, the leader election happens in private. This makes the protocol secure against an adversary who can immediately corrupt anyone. In addition, the protocol operates on a semi-synchronous network: packets are allowed to have at most a $\Delta$ delay; this parameter is known only to the protocol but not to the users. A nice commentary on both Ouroboros and Praos can be found in LLFOURN’s Medium post.

Snow White operates on an asynchronous network. They circumvent the “sporadic presence” issue by using their Sleepy Consensus protocol which allows the users to become online/offline in an arbitrary way. They also keep the coin-tossing approach while focusing on preventing the corruption of past leaders. Every node decides in private whether he is a leader, as is done in Praos and Algorand. However, the adversary is restricted with a corruption delay, as in Ouroboros. Moreover, it turns out that the interval between two successive leader-elections (i.e., the epoch length) must be polynomial in the number of users, which puts forth a scalability concern. (This is an artifact of using the Sleepy Consensus protocol in Snow White; see the last lines of Section 6.1 of the Sleepy Consensus paper under the heading “Parameterization and Analysis”.)

Algorand, meanwhile, solves the leader-election problem using a Byzantine Agreement protocol which reaches an agreement with probability at least $1/3$ at every round; the BA protocol completes, in expectation, in a constant number of rounds. Although the protocol mentioned in the Algorand paper needs at least an honest-majority of $> 2/3$ . Moreover, Algorand allows the following: tolerating an immediate corruption thanks to their private leader-election; a completely asynchronous network where clocks are merely required to have the same speed; and discarding/replacing players (with possibly malicious ones) immediately after they send their messages. Lastly, while the exposition in the Algorand paper assumes an honest majority of users, it has been later shown to work with the honest majority of money assumption to achieve a proof-of-stake flavor. (See Section 8 of the paper.)

Without further ado, let us delve into a deeper discussion about Ouroboros.

Ouroboros: Model

Epochs, Slots, Slot Leaders, Committee. The protocol proceeds in epochs. An epoch is a sequence of a fixed number of time-steps, called slots. Some elected user adds a block to a chain at each slot; this user is called a slot leader. However, it is possible that no blocks are issued in a slot. This means the length of the current chain does not equal the number of slots in the past. See the Chain Growth property below.

The probability that a user becomes a leader is proportional to his stake in the system. The pool of potential leaders is called a committee. Importantly, the set of slot-leaders are computed before an epoch begins.

Stake Evolution. The probabilities used for the leader-election are the ones at the beginning of each epoch. These probabilities change as stakes evolve. However, Ouroboros assume that the stake distribution does not change “too much” — that is, the statistical difference in the stake distribution before and after an epoch is no more than some $\sigma$ — a protocol parameter.

Message Delay and Synchrony. Ouroboros assumes synchronous network, meaning no network delay. However, the adversary is responsible to deliver messages to all users.

Chain Adoption. An honest leader always chooses the longest available chain; ties are broken by the adversary.

Sporadic Presence. It is not clear to me at this point how new users would join the system and get a consistent view. However, for the sake of leader election, the protocol stipulates that users can be offline for no more than a fixed number of contiguous slots.

Corruption Model.

There is a corruption delay — that is, it takes a while for the adversary to corrupt a user
The adversary controls strictly less than 50% stake
The adversary generates all keys. He is responsible for delivering messages to the stakeholders.
When an honest user has to choose between multiple chains of the same length, the adversary breaks the tie.

Desired Properties

We expect that the following three properties hold during the lifetime of the protocol with high probability in the number of users and the length of an epoch.

Common Prefix (CP) property with parameter $k \in \mathbb{N}$ : The view of all honest users must be the same if they ignore the $k$ most recent blocks.

Chain Quality (CQ) property with parameters $\mu \in (0,1)$ and $\ell \in \mathbb{N}$ : In a chain of length at least $\ell$ , the number of adversarial blocks is at most $(1- \mu) \ell$ .

Chain Growth (CG) property with parameters $\tau \in (0,1)$ and $s \in \mathbb{N}$ : The length of the blockchain generated from a sequence of $s$ slots — where the terminal slots are honest — must be at least $\tau s$ .

The three properties above ensure the following two properties:

Liveness: A newly-added block becomes a part of the common-view after a sufficient period of time.

Persistence: If an honest node proclaims a block to be “stable,” all other truthful nodes must agree.

There is another, non-cryptographic desideratum: rational players will not gain “much” by making an adversarial-coalition. Ideally, they should stand to lose in such an endeavor.

Randomness and Leader Election

The first epoch is bootstrapped with fresh random bits needed for the first leader-election process. The random bits for subsequent epochs are generated by the users at an earlier time in private; these random bits are added to each block and is called “per-block randomness.” These bits are propagated through the blockchain and later accumulated to form a “random” key, giving an impression of a source of randomness or a “Trusted Randomness Beacon.”

The key, called “per-epoch randomness,” is used to select a hash function. This function is used in (a distributed) leader election as well as generating per-block random bits. The list of elected leaders is made public, with proofs.

The adversary will likely try to tamper with the per-epoch randomness so that (a) his stake increases over time, and (b) he controls more slot leaders than what is expected from a binomial distribution according to honest/adversarial relative stake.

Important Parameters

The lifetime of the protocol is $L$ epochs, where each epoch contains $R$ slots.
The stake distribution has $\epsilon$ bias, $0< \epsilon \leq 1$ . That is, the honest players control at least $(1+\epsilon)/2$ fraction of the total stakes at the beginning of each epoch.
$\alpha$ is the fraction of the adversarial stake at the beginning of any epoch.
The maximum relative stake-shift in an epoch is at most $\sigma$ . That is, after an epoch, the stake of the adversary players is at most $(1-\epsilon)/2 + \sigma$ .
The honest players have to be online at least once in every $k$ slots.

Some Definitions

Characteristic String. In Ouroboros, slot leaders are already assigned before an epoch begins. A characteristic string $w$ for an epoch is a Boolean string of length $R$ with $1$ indicating a dishonest node and $0$ for an honest node. Clearly, this string has a binomial distribution with parameters $R$ and $\alpha = (1-\epsilon)/2$ .

Tine. A tine is a stripped-down valid blockchain that can possibly be generated from a characteristic string $w$ . Each node in a tine contains only the slot-index it was issued.

A Forkable String. Since the adversary is in control of delivering messages, he can confuse an honest player by presenting him with two competing tines of the same length. A characteristic string is forkable if there exist two different tines, each with the maximum length among all tines of $w$ .

It is easy to see that a forkable string does not bode well for the protocol. Fortunately, forkable strings are rare.

Theorem. For a characteristic string of length $n$ , the probability that it is forkable is at most $\exp( - \epsilon^3 (1 + O(\epsilon))n/2 )$ .

Divergence. Consider two tines $t_1, t_2$ of a characteristic string $w$ of length $n$ . If the length of the common prefix is $n-m$ , we say that these two tines have divergence $div(t_1, t_2) = m$ . The divergence of $w$ , denoted by $div(w)$ , is the maximum of $div(t_1, t_2)$ where the maximum is taken over all tine-pairs.

Intuitively, the divergence captures the power of the adversary to produce competing tines. As you have imagined, the notion of divergence is intricately related to the notion of forkability. Indeed, a large divergence implies the forkability of a substring of the characteristic string.

Theorem. There exists a forkable substring of the characteristic string $w$ . Its length is at least $div(w)$ .

Main Theorems, Static Stake

The above theorem can be used to show the following important theorem about common prefix.

Main Theorem. (Common Prefix, Static Stake.) The probability that the protocol satisfies the common prefix property with parameter $k$ throughout an epoch of $R$ slots is at least $1 - R \exp( - \Omega(k) )$ . The constant hidden by the $\Omega()$ notation depends only on $\epsilon$ , the bias in favor of honest stakes; it is the same as the $\epsilon$ -expression in the exponent of the bad probability from the Forkability Theorem.

Now on to the chain growth and chain quality.

Main Theorem. (Chain Growth, Static Stake.) Let $\alpha - \delta$ be the adversarial stake ratio. The protocol satisfies the CG property with parameters $\tau = 1 - \alpha$ and $s \in \mathbb{N}$ throughout an epoch of $R$ slots with probability at least $1- R \exp( - \Omega(\delta^2 s) )$ .

Main Theorem. (Chain Quality, Static Stake.) Let $\alpha - \delta$ be the adversarial stake ratio. The protocol satisfies the CQ property with parameters $\mu := \alpha/(1-\alpha)$ and $\ell \in \mathbb{N}$ throughout an epoch of $R$ slots is at least $1 - R \exp( - \Omega(\delta^2 \alpha \ell ))$ .

Main Theorem, Dynamic Stake

Main Theorem. (Full Protocol)

Fix $k \in \mathbb{N}$ , the security parameter. Also fix $latex \epsilon, \sigma \in (0, 1)$ to be used below.

Let $R = 10 k$ be the epoch length of the system, and $L$ the total number of slots in the lifetime of the system.

Assume that the fraction of the adversarial stake is at most $(1-\epsilon)/2 - \sigma$ .

Assume that the protocol for static-stake satisfies the CP property with parameter $k$ throughout $R$ slots, with $\epsilon_{CP}$ probability of error. This means, if two honest players are at slots $s_1, s_2, s_1 < s_2$ and have chains $C_1, C_2$ , then the prefix obtained by deleting the last $k$ blocks from $C_1$ would also be a prefix of $C_2$ .

Assume that the protocol for static-stake satisfies the CQ property with parameters $\mu \geq 1/k$ and $k$ , with $\epsilon_{CQ}$ probability of error. This means, in every $k$ consecutive blocks, at most $1/k$ blocks are generated by the adversary.

Assume that the protocol for static-stake satisfies the CG property with parameters $\tau \geq 1/2$ and $k$ , with $\epsilon_{CG}$ probability of error. This means, if two honest parties are separated by at least $k$ slots, their respective chains must differ by at least $k/2$ in length.

Assume that the dynamic-stake protocol simulates a perfect randomness beacon with distinguishing advantage $\epsilon_{DLS}$ .

Assume that $\sigma$ is the maximum stake-shift over $R$ slots

Assume that the adversary is restricted to a corruption delay $D \geq 2R - 4k = 16 k$ slots

Assume that no honest player is offline for more than $k$ slots.

Then, the protocol for dynamic-stake satisfies persistence with parameters $k$ and liveness with parameter $u=2k$ throughout a period of $L$ slots with probability

$\displaystyle 1 - (L/R) \left( \epsilon_{CP} + \epsilon_{CQ} + \epsilon_{CG} + \epsilon_{DLS} \right)$ .

I would like to present a similar overview of Snow White and Ouroboros Praos, as well as details about Ouroboros: I did not talk about the incentive mechanism in the protocol, and how it achieves approximate Nash equilibrium for the players. I also did not discuss various attack scenarios. We’ll do these in future posts. Until then, goodbye.

Ouroboros Proof-of-Stake Blockchain Protocol: Assumptions and Main Theorems

A Brief Survey of Proof of Stake Blockchain Protocols with Provable Security

Ouroboros: Model

Desired Properties

Randomness and Leader Election

Important Parameters

Some Definitions

Main Theorems, Static Stake

Main Theorem, Dynamic Stake

Next

Published by saad0105050

Leave a Reply Cancel reply

A Brief Survey of Proof of Stake Blockchain Protocols with Provable Security

Ouroboros: Model

Desired Properties

Randomness and Leader Election

Important Parameters

Some Definitions

Main Theorems, Static Stake

Main Theorem, Dynamic Stake

Next

Share this:

Like this:

Related

Published by saad0105050

Leave a Reply Cancel reply