IOHK recently released their latest research paper, Ouroboros Genesis. You can read their announcement here.
For full details on the design of the protocol, Ouroboros Genesis, and explanations of the protocol executions, I highly recommend you watch the full video. The research paper is also available to the public, and you can read it here.
Here, I tried my best at providing a summary of Professor Aggelos’ presentation video, primarily only covering the introductory topics such as the origins of the protocol and its evolution into Genesis.
Concept of Robust Transaction Ledger
It starts with the concept of robust transaction ledgers, which is the problem that Bitcoin solves. The formal definition of the ‘robust transaction ledger’ can be found in this paper. The linked paper set out to define a model and objective that a ledger protocol has to meet. From there, many other papers came out which looked at other aspects such as property definition, partial synchrony and composition definitions.
What does it take to realize the ledger?
Realizing the ledger can be achieved by Bitcoin, seeing that their protocol was the inspiration for defining this protocol. Despite this remarkable feature of the protocol to provide consensus in this setting, there are significant scalability and energy efficacy disadvantages. Thereby leading to the question: is it possible to realize it in a more efficient way without compromising its basic assumptions? And subsequently leading to Proof-of Stake. This was an alternative discussed in the Bitcoin realm to replace Proof-of-Work. (Note: for the rest of this forum post, I will refer to Proof-of-Stake as POS, and also use POW for Proof-of-work.)
A little background on POW
If you look at the way blockchain protocol works in Bitcoin, its similar to an election. The next entity that will produce the block, that is going to be added to the blockchain, will be elected. Election in some sense is based on probability proportional to your hashing power. More hashing power, higher chance of being elected.
Here, Professor Aggelos makes a note that “collisions” may occur. This happens in a system that is decentralized and that has no correlation between parties running the protocol. But that the protocol is designed to absorb such collisions (or momentary disagreements between the parties). Modifying this is what POS is about.
Background on POS
POS, uses stake or a ‘virtual resource’ instead of hashing power (a physical power). This is the core of the POS idea. Also, miners are substituted with those who have ‘stake’. This is reported in the ledger. Once we have this, then we need a randomized process that is capable of emulating the same election idea that naturally comes in the POW domain. This idea proved to be powerful and motivating for people to propose a number of protocols for implementing the POS concept.
POS approaches
Currently, there are 2 main approaches. Both are classified as POS because the participation is based on your stake.
- POS blockchain → basically the same way that Bitcoin blockchain works, while using POS in a way that does not jeopardize any of the features that the POW protocol provides
Examples of this include: Ouroboros, Snow White, NXT, and a number of others - The other approach is POS BFT (Byzantine Fault Tolerant) → this approach can be upgraded to operate in the POS setting
Example of this: Algorand
"Bitcoin Folklore"
POS didn’t come without controversy. Folklore was that POS blockchains are impossible to work. The main deficiencies brought up being:
-
Costless Simulation
This suggests that in the absence of POW, POS is a proof of a virtual resource. There is nothing that prevents you from doing it over and over, perhaps in parallel in multiple times. Fundamental differences between POW and POS, is the fact that in the POW case, all the parties must commit to a protocol execution and advance that execution, using their POW algorithm. This is not the case in POS. Because its ‘nearly’ costless to execute POS protocol. In principle, there is virtually nothing at stake and one would be capable of advancing multiple different executions of the protocol so that it can find the one that is more favorable. That could be lead to… -
Long-range attacks
In long range attacks, there is a victim node that tries to distinguish between two alternative histories without access to recent information. If you are constantly online, you have a good understanding about what is communicated in the network. But imagine you join the network after a big hiatus or you are new node, then you face the bootstrapping problem. How do you synchronize with that blockchain without any recent information?
Bootstrapping from Genesis
A new party is trying to find ‘what is the right history’, but does not have any information about the protocol. There are honest parties providing one blockchain and an ‘adversary’ providing another. The only information the new party has is the genesis block and is faced with this decision of choosing the correct blockchain. In the POW world, what you can prove is that the main chain (maintained by honest parties) is going to have the most blocks. Meaning the adversary chain will be substantially shorter and this will enable the new party to connect to the correct blockchain. This is a powerful idea, but relies on the assumption that majority is made up by honest parties who follow the protocol, not adversaries.
Dynamic Availability
The following model for understanding how blocks and protocols operate is what Professor Aggelos and his research team have called Dynamic Availability. This is the setting where we analyze blockchain protocol that suggests an environment that:
- parties will join and leave at will
- the number of online and offline parties will dynamically change over time (they may lose clock synchronization or network connection)
- and there will be no a-priori knowledge at any given time
All this is the motivation of the new version, Ouroboros Genesis, based on Ouroboros Praos. The new version of the protocol is dealing with the problem of dynamic availability. The intention is to see whether it is feasible to produce a POS blockchain that is capable of natively working in the same setting as Bitcoin. And the main novel feature is that they designed a new chain selection rule that enables parties to bootstrap from genesis.
Let’s step back into understanding Ouroboros
Ouroboros was designed together with formal proof that it realizes the functionality of a robust transaction ledger. Proof strategy involves properties of the underlying blockchain data structures: these are properties that are shared with Bitcoin POW analysis. Common prefix, chain quality, chain growth are the fundamental properties that previous work has identified as important building blocks for security of blockchain protocols.
So now the question is…can we apply this logic to the POS setting?
What ouroboros has done is to show that the problem of an adversary reusing an opportunity to issue a block in multiple paths of a fork (because of costless simulation) can be overcome.
There are 3 important quantities that are important when studying protocol execution like this one. Every path that you see in the execution will have these 3 quantities:
- Gap = Find this by looking at a certain path in the execution and then looking at how far it is from the leading one.
- Reserve = Look at certain path, and see how many slots are still at full control of adversary and that the adversary might use to advance that path forward.
- Reach = Substract gap from reserve to see what the reach of that path is. Example: The reach of -1 is too short (by 1) to win over the leading path. If you are in such a situation, and you are an honest node using the longest chain rule then you won’t be fooled by the adversary.
Then at the end, look at whole execution. We look at 2 concepts:
- Reach: maximum reach across all times
- Margin: what is the second best disjoint reach
When analyzing this, you want the margin to always be below zero. That would be a setting that the adversary will not be able to fool a honest party that tries to connect in this protocol execution.
So reach and margin are the 2 fundamental quantities that are interesting when analyzing protocol executions. The researcher team can show that the adversary will win if and only if the margin is at least 0. What is interesting now is that these 2 quantities together, define a random walk. Even those it is more complex than the random walk analyzed in Bitcoin, is still has good features that can be used to prove security.
Going back to the original question
When you are dealing with 2 chains, that have forked at certain point, and you need to choose the correct blockchain. If the fork is somewhat recent, either by short range attack or a disagreement between nodes that was produces naturally because of network conditions, then the longest chain rule will apply. But if the fork is bigger than k blocks, then the following plenitude rule will apply. --> Go to the moment chain diverges, and shortly after, isolate a certain region of blocks. Within the certain time range, look at which of the 2 chains is more dense. The party is going to follow the chain that is more dense within that time range. This rule is still quite simple to implement, meaning it is quite easy to program and it works to enhance the longest chain rule.
Intuition for Plenitude Rule and what was proven in protocol.
If the majority of parties follow the protocol, then at any sufficiently long time segment, the corresponding chain will be more dense (especially after a fork). They were able to prove that adversarial blockchains shortly after the divergence point will exhibit a less dense block distribution. Use this rule to determine what is the right blockchain to connect to.
First time, that these researchers can now say, POS blcockahisn can operate in the same dynamic availability setting that we know Bitcoin POW based blockahins are operating in.
More to come in Ouroboros research
- incentive structure, delegation, stake pools of the protocol
- sidechains, software updates and ecosystem sustainability
- smart contracts and domain specific language
- Permissioned version of Ouroboros blockchain
- looking at how POS blockchains shard and can be scalable
Again, here is the video if you are interested in learning about Ouroboros Proof of Stake:
These are really nicely done, and very useful! It helps to spread this information to other parts of the community (other languages), and it’s just very useful to have such summary in the text.
Italian translation