Introduction To Ouroboros

“Ouroboros” is the name of Cardano’s Proof of Stake consensus algorithm. So far it comes in two flavours, Ouroboros and Ouroboros Praos. This post gives my high level interpretation of how they both work along with some commentary. If you want a low level view check out the papers here and here. This presentation by Dr. Peter Gaži is a great companion to this post (luckily it came out just as I was writing it).

As Dr. Gaži points out, there are two properties you want with any type of distributed ledger: “persistence” and “liveness”. Where 𝐤 is the security parameter, they’re defined as:

• Persistence: once a transaction goes more than 𝐤 blocks deep into the blockchain of one honest player, then it will be included in every honest player’s blockchain with overwhelming probability. Or more simply, Once your transaction is in the blockchain it will stay there.
• Liveness: all transactions originating from honest account holders will eventually end up at a depth more than 𝐤 blocks in an honest player’s blockchain, and hence the adversary cannot perform a selective denial of service attack against honest account holders. Or more simply, if you make a valid transaction it will end up in the blockchain.

Bitcoin’s Proof of Work (PoW) protocol provably achieves both of the above according to the GKL15 paper (where I took both of the definitions from). Getting a Proof of Stake (PoS) protocol to achieve the same is a challenge. PoW selects block creators by a computationally intensive competition outside of the blockchain. With PoS, the input to the block creator selection process is the blockchain itself — the blockchain chooses who will extend the blockchain! This presents some problems for persistence and liveness:

• Grinding: Attackers might be able to bias the block creator selection process in their favour by contriving the state of the blockchain. If they can, they could repeatedly re-elect themselves as block creators. If they dominate block creation they can censor transactions, violating liveness.
• Nothing-at-stake: Since it costs you nothing to create a block you may as well create blocks wherever you can. If an attacker can wield this power effectively, they may be able violate persistence by creating blocks on a competing chain, or bribing/encouraging others to do so. If the chain becomes long enough it will overtake the main chain and so rewrite history.

Both Ouroboros protocols produce unbiased random numbers to address the grinding problem. This randomness allows for an unbiased “slot leader” (block creator) selection process that chooses leaders with a probability proportional to their stake. During an “epoch” (time period partitioned into many slots) participants write random numbers to the blockchain which end up selecting the slot leaders for the next epoch. The main difference between the two in this respect is:

• Ouroboros: Slot leaders are known publicly ahead of time and there is always one slot leader per slot.
• Praos: Each stakeholder knows which slots they lead ahead of time. Others only find out once they publish a block. There can be multiple slot leaders for a slot or none at all.

The papers address the nothing-at-stake problem by proving that persistence and liveness are achieved even with an attacker’s ability to create forks easily (the video demonstrates the approach to the proof). There’s also a yet to be implemented idea of “input endorsers” in the papers that would create invectives to behave honestly.

The original Ouroboros was conceived to prove that a PoS protocol could be secure. It can also be used in practice and is being used right now on the Cardano network. However, only a handful of authorised stakeholders are currently eligible slot leaders. All stake is essentially assigned to them. At some point in 2018 these training wheels come off, and stake delegation will stakeholders will be able to re-assign their stake. Eventually, Cardano will transition over to Praos which is a “substantial leap forward compared to Ouroboros” according to one of it’s authors, Prof. Aggelos Kiayas.

The rest of this post goes into more detail about the leader election process for both protocols.

Ouroboros

In Ouroboros, the main cryptographic scheme used in the randomness generation process is publicly verifiable secret sharing (PVSS). In Secret sharing schemes, a “sharer” splits up a secret into multiple “shares”. The original secret can only be reconstructed if a single party has access to certain proportion of shares (here it will be >50%). In publicly verifiable secret sharing schemes, the sharer publicly posts proof that the shares are valid.

Using PVSS, stakeholders play a coin flipping game on the blockchain. The random outcome of the game generates the slot leaders for the next epoch. To play the game, each participant publishes a secret random number to the blockchain. During the epoch, these random numbers are revealed. At the end, they’re combined to deterministically produce a final public random number that all participants use to determine slot leaders for the next epoch.

The protocol runs something like this, with an epoch defined as 10𝒌 slots long:

1. Committee formation: The distinct slot leaders for the epoch form a notional committee that will play the coin flipping game. Each committee member privately generates a random number 𝒖 (their flip of the coin).
2. Commit phase: In the first 2𝒌 slots of an epoch, committee members post their PVSS data for 𝒖 to the blockchain according to the particular PVSS scheme the protocol uses. Each party posts:
   1. A commitment to 𝒖.
   2. A “share” of 𝒖 for every other committee member encrypted with their public key. This share gives them no information about 𝒖 but if you have more than half of the shares you can reconstruct it.
   3. Cryptographic proof that the 𝒖 committed to and the one shared are the same.
3. Reveal phase: In the next 2𝒌 slots, committee members reveal their 𝒖 on the blockchain.
4. Recovery phase: In the last 1𝒌 slots, committee members check who hasn’t revealed their 𝒖. For every party who hasn’t revealed 𝒖, each member posts their share of that party’s 𝒖 to the blockchain. Once over half the shares are posted, all parties can reconstruct the 𝒖 for that party.
5. New Epoch: The 𝒖 values from each party are now publicly known. They are xor’d together to get 𝞺 which is used as a seed to pick a random satoshi (the smallest currency unit) for each slot in the next epoch. The owner of that satoshi is the slot leader. The committee formation for the next epoch now begins.

Notes

• The PVSS scheme mentioned in the Ouroboros paper is Sch99. The one developed for Cardano is SCRAPE. I haven’t gone through SCRAPE yet so keep that in mind when reading the conjecture below! A Haskell implementation for both of them was written by IOHK developers here: https://github.com/input-output-hk/pvss-haskell.
• A lot of stuff is written to the blockchain in the commit phase. The number PVSS related messages is proportional to 𝒎² where 𝒎 is the size of the committee. Large committee sizes cause large communication and computational overheads. This necessitates a minimum stake limit for being a committee member to cap the size of the committee.
• Minimum stake limits are not great. They mean you need a delegation scheme for people who hold less than the limit to participate. Compulsory delegation is basically a social system, like voting. If a malicious party convinces enough people to vote for them using social manipulation, then they might be able to get more than 50% of the stake and thus violate the assumptions made in the security model.
• Ouroboros is totally immune to grinding. Even if parties produce their random number (𝒖) adversarially, they will be unable to influence the leader selection seed 𝞺. Even if they never reveal their 𝒖, it will be reconstructed and 𝞺 will remain the same regardless.
• Ouroboros uses a synchronous network model to prove its security, meaning that all parties’ messages won’t be delayed longer than a slot. Adversarial parties can’t delay certain parties at will. In the Praos paper there is a description of an attack against Ouroboros if this condition isn’t realised.
• An attacker can identify which parities it would be best to corrupt or hack into ahead of time because the slot leader schedule for the current epoch is public. The model assumes that attackers can’t corrupt other parties instantaneously after seeing 𝞺 which means it’s not secure against “fully-adaptive corruption”.
• The best three hours of research you can do to understand how PVSS is used in Ouroboros is this video: https://youtu.be/hMgxZOsTlQc, where Bernardo David (co-author of Ouroboros, Praos and SCRAPE) explains the cryptographic primitives clearly and simply. I’ll probably be referencing it in future posts.

Ouroboros Praos

Praos uses a verifiable random function (VRF) as it’s core randomness generating scheme. Given a private key and an input, a VRF scheme outputs a pseudo-random number and a proof. Anyone with your public key and the proof can verify that the number was produced with the given input but can’t produce the number before that time.

In Praos, each epoch has an agreed upon nonce which all participants must use as input to their VRF. For each slot, each participant uses their VRF and the nonce to produce a random number. If the number is less than a threshold value proportional to their stake, then they are a leader for that slot. Since these random numbers are produced independently per participant there can be multiple leaders for a slot or none at all. The nonce for the next epoch is produced from VRF values embedded in the block headers of the preceding epoch.

Defining a epoch as 24𝒌 slots long, the leader selection process runs something like this:

• For every slot 𝒊, as a stakeholder, you run the VRF with 𝝶, 𝒊 and an arbitrary string “TEST” as input to produce a random number 𝘆ᵢ and proof 𝞹ᵢ. You are a slot leader if 𝘆ᵢ < 𝗧, where 𝗧 is proportional to your stake at the start of the previous epoch. When you publish a block, 𝘆ᵢ and 𝞹ᵢ are included in the block header so others can verify you’re eligible to produce a block at slot 𝒊. Here’s some pseudocode that might make it clearer:

T = calculateMyThreshold(myAmountOfStake)
foreach 1..nSlots -> i:
  y, proof = VRF(myPrivateKey, concat(epochNonce, i, "TEST"))
  if y < T:
    getReadyToGenerateBlockAt(i, y, proof)

• When generating a block you run the VRF again on the same input except with “NONCE” instead of “TEST” to produce 𝞀ᵢ which you put into the block header as well (along with its associated proof).
• At the end of an epoch, each participant looks at the blocks in its first 16𝒌 slots to produce a 𝝶 for the next epoch. From these blocks, they concatenate all the 𝞀 values together along with the previous 𝝶. Hashing the result produces the 𝝶 for the upcoming epoch. Each participant also updates their 𝗧 value to reflect the stake distribution at the start of the just completed epoch.

Notes

• There is no reason to have a minimum stake limit to participate in the protocol. Delegation can just be optional for parties who don’t have enough stake to make staking profitable. Having no fixed minimum is a big improvement over Ouroboros.
• Grinding attacks are possible but limited. An adversary can’t arbitrarily control 𝝶 because she can’t even arbitrarily control the value of 𝞀ᵢ in her own blocks (thanks to the VRF). What she can do is try and create as many forks as possible leading up to the end of the 16𝒌 slots that determine 𝝶. She calculates which one of them is most advantageous to her and tries to make sure it ends up as the longest chain. According to the analysis of the paper this advantage doesn’t change the security properties of the protocol.
• Grinding attacks are also limited by the adversary’s hashing power. To compare the desirability of different values for 𝝶, you have to generate all (or some large proportion) of the 𝘆ᵢ values for each slot in the next epoch for every 𝝶 you want to compare. Calculating each 𝘆ᵢ requires a number of hashes. Increasing the number of hashes needed to calculate 𝘆ᵢ in the protocol wouldn’t affect honest parties too much (who can just calculate their 𝘆ᵢ values lazily) but would greatly increase the computational power an adversary needs to gain any benefit from grinding. In my opinion, this computational asymmetry for honest vs dishonest parties is a really cool feature.
• When two or more parties are elected in the same slot they will create a fork even if they’re all honest. They should be short lived. For a grinding attacker, the more “honest forks” there are at the end of the nonce determining slots the better.
• The paper suggests that in case of a fork, honest parties should choose the chain they got first (see end of page 24). This means slot leaders who relay their blocks faster have a better chance of ending up in the longest chain.
• The arbitrary values “TEST” and “NONCE” are there to seperate 𝘆ᵢ from 𝞀ᵢ, but it’s not totally clear why 𝞀ᵢ is needed. I think it’s because the 𝘆ᵢ values that make it into blocks are biased towards low numbers (because they have to be less than 𝗧) and therefore not random enough to be used to generate 𝝶.
• Praos’ security proof is done under a semi-synchronous model where an attacker can delay messages for longer than a slot. According to the paper, the intermittent empty slots (where no one is a slot leader) counteracts this ability as it gives parities who are being delayed by an attacker some time to catch up.
• Since slot leaders aren’t publicly known ahead of time, an attacker can’t see who was a slot leader until after they’ve published a block. An attacker can’t know who specifically to attack in order to control a certain slot ahead of time.
• Praos uses a “forward secure” digital signature scheme which means that block creators use a different private key each time they create a block (and delete the old one), while preserving their public key. So, even if an attacker was able to corrupt a party they can’t create blocks in their already published slots. This point and the one above mean that, unlike the original Ouroboros, Praos is secure against fully-adaptive corruption.
• Praos isn’t the only blockchain protocol using a VRF. Algorand, was published before Praos and uses a VRF in a similar way. There’s also Dfinity.

In the upcoming posts I’m going to be going through the cryptographic primitives that make up the protocol. We’ll start towards PVSS and then go onto VRFs. I think the series will go something like:

• hash based commitment schemes (done)
• discrete logarithm based commitment schemes (done)
• PVSS, using SCRAPE or Shoenmakers’ scheme
• The VRF described in the Praos paper

And we’ll see where we go from there. Keep in mind I’m learning this stuff as I go along so I’m not sure how long it will take me 😅!