I read the Ouroboros paper so you don’t have to; here’s what I learnt.
Ouroboros is complex. As I was searching the web, trying to find out more about this Egyptian iconography named consensus protocol at the heart of Cardano, I found only brief overviews on the one hand and brain-numbing mathematical proofs on the other.
So I decided to go to the source; after reading the ouroboros papers for multiple days, here’s what I learnt.
Before we begin, I will mainly describe the process of how the protocol works and not the why (feel free to find out yourself, good luck).
Lastly, we will focus on the currently implemented version of Ouroboros, Praos, but will be pointing out differences briefly as we encounter them.
What are Consensus Methods?
Ouroboros is a consensus protocol. You can imagine it as the beating heart of Cardano; without it, everything else fails.
Consensus is blockchain is one of the critical fundamentals. It defines the laws and parameters that govern how the distributed ledgers work. Put simply, a rule set that all participants within a decentralised network use to agree on the state of the ledger and how messages are propagated through the network.
This is, if not the most significant advantage decentralised blockchains have compared to centralised systems. Instead of participants needing to trust the intentions of the other parties involved, trust is built into the protocol.
Distributed Ledgers
A distributed ledger is a list of transactions where multiple entities have identical copies of this ledger.
A ledger should satisfy these two main concepts:
Persistence — Any node implementing the ledger will give you the same version of the log, which also holds true over time. The log you see tomorrow is an extension of the log seen today.
Liveliness — New transactions are added at regular frequencies. Therefore, there is an upper bound for when a transaction sent to the nodes will be included in the log.
These can be derived from the following elemental properties Common Prefix, Chain Quality, and Chain Growth.
These characteristics are essential for proving that Ouroboros satisfies and maintains a secure and functioning ledger. We won’t be going into this further as it gets quite mathematical, but see [KP15] and Praos for more info.
The How, the How, and the How
We should all be familiar with how the bitcoin consensus algorithm works with PoW(read this to recap) and probably that Cardano uses DPoS(Delegated Proof-of-Stake).
So let’s look into exactly how this works, how nodes are chosen and how security and stability are maintained.
As mentioned here, Cardano breaks down time into Epochs (which are five days long) and within each Epoch are 432,000 slots, each lasting for one second. In each slot, nodes have a chance of becoming slot leaders and, thereby, the ability to mint a block.
Before an Epoch begins, a few epoch-wide calculations are done.
- The stake distribution of the nodes is calculated from the last block of the current Epoch -2, with a derived threshold for each stake percentage(of the overall number of ADA). This is used as the probability model for leader selection.
- A Random Oracle is generated by the hash of the first ⅔ of slots in the previous Epoch (more on this later).
Stake distribution is calculated as shown below, with p being the probability of being selected as slot leader and a being the stake. Parameter f of the protocol is what we refer to as the active slot’s coefficient.
Observe that φf(1) = f; in particular, the parameter f is the probability that a party holding all the stake will be selected as a leader for a given slot.
Currently, f is set to 0.05, meaning that 5% or 1 in 20 slots will contain a block.
In the original Ouroboros protocol, slot leaders were chosen before an epoch began, and this slot leader schedule was distributed among the nodes.
However, this has the vulnerability of the adversary(bad faith actor) from learning the slot leaders’ identity ahead of time and using this knowledge to strategically corrupt coalitions of parties with significant (future)influence.
Local private elections using VRFs in Praos are used to deal with these adaptive corruptions where an adversary cannot predict which node will be the slot leader in any given slot.
Variable Random Function (VRF)
A VRF is a public-key pseudorandom function that provides proof that its outputs were calculated correctly.
Evaluate (Input) =(output,proof)
Verify (input,output,proof) = 0/1
Every node has a private key and a public key. With the public being made available to everyone for verification.
The election process is as follows for every slot:
1. Each node takes the VRF function of the epoch randomness(the random oracle generated at the beginning of the Epoch), their private key and the slot number. If this number is below the stake distribution threshold, they are a slot leader and can mint a block.
2. The node mints the block adding in all the valid transactions from the mempool, and broadcasts the block along with its proof. This VRF number produced by each node can be verified by anybody else using their public key.
3. Each node that mints a block also emits another VRF random value to be used in the creation of the subsequent epochs Random Oracle.
This results in empty and multileader and empty slots to enable short periods of silence that facilitate synchronisation.
The Snake That Eats Its Tail — Why the Random Oracle
Without this value, the protocol would be vulnerable to pre-computation attacks. For example, an adversary could potentially precompute all the random numbers they will generate in the upcoming Epoch as the stake distribution is set from current -2 epochs.
This could potentially allow an adversary to plan an attack in the future!
The random oracle prevents this by adding another level of randomness to the VRF values, given that it takes the hash of the random values from the first ⅔ of slots in the previous Epoch. The period between when the hash is available, and the next Epoch begins is too short of a time to precompute the future random values currently.
The blockchain itself becomes its source of new randomness — a homage to Ouroboros, the infinite cyclical event of the snake that eats its own tail.
Key Evolving Signatures — KES
An assumption made in Ouroboros Praos is an adversary’s ability to corrupt other network nodes.
The Ouroboros Praos paper explains this concept pretty well:
In regular digital signature schemes, an adversary who compromises the signing key of a user can generate signatures for any messages it wishes, including messages that were (or should have been) generated in the past. Forward secure signature schemes prevent such an adversary from generating signatures for messages that were issued in the past, or rather allows honest users to verify that a given signature was generated at a certain point in time. Basically, such security guarantees are achieved by “evolving” the signing key after each signature is generated and erasing the previous key in such a way that the actual signing key used for signing a message in the past cannot be recovered, but a fresh signing key can still be linked to the previous one.
Basically, the private key is evolved(a new one is generated) with every signature while also having the new key linked to any messages signed in the past with past keys.
Rewards
Rewards for generating a block come from transaction fees and the Ada reserve.
Rewards are distributed among stakeholders at the end of an epoch, i.e. they are not blocked but rather epoch-dependent. These rewards, in the case of stake pools, are distributed among the pool participants with fees associated with maintaining and running the pool.
An intriguing utilisation of stake pools, while not initially designed for, is being used as an airdrop mechanism where stake pool fees are set to 100% and the rewards are used as seed funding for the project. And in return, tokens are issued to the delegators at certain time snapshots.
There is a lot of information and concepts that I have completely or partially left out of this explanation due to complexity or the need for brevity.
One big concept that has been totally left out is forking and why the protocol is secure, given the assumption that an adversary maintains < 50% control of the stake.
A great video to watch on this is Dr. Peter Gaži, presenting Ouroboros at MIT or take a stab at reading the paper if you’re masochistically inclined.
Resources
