Cardano Multiverse

How to handle Cardano’s short-lived branches in the most efficient way.

Milkomeda is pleased to open source the Multiverse, which is a multi-platform library specifically designed to handle Cardano’s short-lived rollback (short-lived branches).

Cardano’s consensus

Cardano uses a cryptographic tool to determine who will be creating a block at a given slot: the Verifiable Random Function (VRF). In essence, it is a cryptographic scheme to generate random numbers and to be able to prove the number has been randomly generated. The interesting part is how this is used for Cardano. Cardano divides time into epoch. There are 432,000 slots in each epoch and each slot lasts one second. Each slot is an opportunity for a stake pool to submit a block and identify if the stake pool has been elected to submit a block. For a given slot, they use the VRF (their chance is proportional to the total stake). The block schedule is private for each stake pool.

Three things can happen:

1. No one is allowed to create a block for this slot.

2. Only one is allowed to create a block for this slot.

3. Many are allowed to create a block for this slot.

The first two cases are easy, whereas the later case may generate conflicts, in which case the network will have to decide which branch to take. Now the node already has an algorithm to make that decision, but as you can see, this is already creating some issues:

In addition, the block propagation may experience problems. A stake pool has one second to receive the latest blocks, create the new block and then propagate the block to the whole network. This is the case because at the end of the one second, a new block may be created and they will want to make sure it is referencing their block.

What are the solutions available?

The network will make a decision. However, the case may arise where the decision my local node has made is not the one the network made. If this occurs, my local node will detect it has diverged from the network’s consensus regarding which branch to take and will do a “rollback”. If you are using cardano-db-sync like we do, this means you will experience a pause while it removes the information from the discarded branch and applies the blocks of the new newly selected one.

When this happens, you may feel a bit annoyed that some data has been deleted from your database and you have to design your code with uncertainty in mind. Usually, you do this by applying a delay before confirming a given object in the database is confirmed.

This creates a delay for everyone who is depending on this tool. I might create a transaction with some UTxO as inputs that are going to be invalid by the time my transaction reaches the network because I made the mistake of not waiting for the three to five minutes it takes to reach 10 blocks confirming the transaction.

We can do better. I should not have to wait for three to five minutes to have a good level of confidence that my transaction is confirmed. I also should not have to be concerned about the indexer to pause while it applies a rollback. As a matter of fact, through Milkomeda Foundation, we made a Catalyst Proposal to design and implement a better algorithm to handle the short-lived branches: The Multiverse.

The Multiverse

The multiverse is a tool that keeps track of every branch of the blockchain: Every variant of the timeline. It’s fairly simple, in fact. The trick is not to consider the blockchain like a linked list of blocks but instead like a tree (this is why we call these forks “branches”). Ideally, these branches are short-lived (a few blocks at most) and only one branch is continuously growing.

Now, we don’t want to be maintaining the whole blockchain and all the branches in memory. So one of the first requirements we set ourselves is to only manage a given window.

We make sure this view is large enough to handle the instability of the blockchain. Beyond this view we assume the likelihood of a fork is near 0.

Let’s define some concepts:

• The tips are the blocks that don’t have any child block;
• The roots are the blocks where the parents have been garbage collected (they fell outside the view)

Adding a new block as a child to one of the tips may trigger the view to slide to the right: roots will fall outside of the view and will be garbage collected.

Now that we have a view of the head of the blockchain we can start adding different tools that will be useful for us.

When writing the Milkomeda Bridge we needed to keep track of the UTxOs we control, but not necessarily all the blocks. So instead of storing the whole blockchain’s state for each block, we are simply storing a subset of the ledger. Each snapshot contains the list of UTxOs we control at that given point in time.

We thought about storing these in a database. However it was too difficult to efficiently represent the different states between two given branches: some UTxO are available if we are at state s7 but not at s7'. We then decided it would be more efficient to keep these in memory instead. The naive approach is to use a HashMap: UTxOPointer -> UTxO. Very quickly this approach starts to use a lot of memory. Indeed, for each new block we are copying the parent’s state and then removing/adding UTxO in order to create the new state.

Fortunately, there is a data structure perfect for this kind of situation: Hash Array Mapped Tries (HAMT). Some operations may be a bit slower but the gain in space is largely increased. This data structure has the advantage of sharing memories between two copies. Consequently, adding and removing entries in both copies will mutate the local copy, yet keep the intersection shared.

This is the most optimal way of storing the state between two blocks. We only pay the cost of the difference between two blocks.

Applications

Wallet

It is possible to take advantage of the multiverse to confirm a transaction faster than waiting for blocks to be added. Now that we are monitoring all the branches of the blockchain, we can check if our transaction is on all of these branches. For example, two block miners competing for the same slot may have added our transaction in their respective blocks.

If our transaction, T, is on all of the possible branches as follows, then it is likely our transaction is going to be confirmed on chain:

Or

Explorer

One item that is often missing in the blockchain explorer is that it is not possible to identify the blocks that have been dismissed. Being able to see how the network is currently behaving and monitoring the forks as they happen (or have happened) will demonstrate the robustness of the blockchain. Users will be able to understand why a transaction, that was a moment ago on the explorer, has been removed. Stake pool operators will be able to understand why their block has been dismissed by the network.

Website: www.milkomeda.com

Twitter: @milkomeda_com

Written by Nicolas Di Prima, Milkomeda contributor.