Building an Efficient Blockchain

Last week, we enabled Omega blocks in the CasperLabs Testnet. Since we received a lot of inquiries on what Omega blocks are and why they matter, we wanted to take some time to explain this concept.

Highway

To understand Omega blocks, first you have to understand Highway. Highway is the consensus protocol that powers the CasperLabs blockchain. It is the first specification for a provably live and safe consensus protocol within the CBC Casper framework.

In Highway within a given era there are a fixed set of validators, each with their own stake and round exponent. The individual round exponents dictate how frequently the validator will send messages and participate in consensus. For each millisecond, the protocol determines who is the leader (so each round has a leader; someone with round exponent 0 would consider every millisecond as a separate round for themselves). This is a deterministic process in the protocol, it depends on some entropy collected between the key and the booking block, in addition to their stake.

For example, with round exponent 15, the validator would participate in rounds starting at every 2**15=32768th milliseconds (~32 seconds) after the start of the era. Each validator can have a different round exponent. This is the partial synchrony property of Highway.

In each round, validators have to “show up” and minimally vote on the leader block with an Omega message. Without Omega blocks, only the leader proposes a Lambda block with transactions. This is a simple description of the liveness property of the protocol.

There are a few optimizations that we need to make to Highway so that the protocol provides a great user experience and is efficient. Optimizations are trade-offs between security (validator set size), consensus message overhead (O(N)) and time to finalization (round lengths). We won’t compromise security, so that is off the table for us. That leaves us with message overhead and time to finality to work with.

Say you have Alice, Bob and Charlie with stakes 50, 49 and 1, respectively. Maybe Charlie has a lower round exponent than Alice or Bob, and participates in a lot of rounds where none of the other two are doing anything, but still he only has 1% chance of leading any round. That means if some user deploys to Charlie, their deploy could be stuck there for a long time.

If we want blocks to go out quickly, we would need low round exponents, but every round has 2*N messages, where N is the number of validators. This generates a lot of useless data in storage and creates a lot of work as well to validate the correctness of all the messages.

In consensus-speak this is referred to as the O*(N) message problem. Many fork choice PoS protocols (like Tendermint) suffer from this problem. This is the reason for the small validator set sizes in many of these protocols. Our goal is to support many hundreds and hopefully thousands of validators in the CasperLabs protocol — so O*(N) message overhead won’t do.

Optimizing Highway with Omega Blocks

Enter Omega blocks. Omega blocks work really well if you have a decentralized application and plan to send a lot of transactions to the blockchain. Rather than sending a ballot, your node can propose blocks during each round and these transactions will be finalized by the end of the round. This reduces the consensus overhead from O*(N) and provides a better UX for developers and end users. This also reduces network overhead, as these deploys don’t have to be gossiped over the network.

Here is a screenshot from the testnet. Omega blocks show up “between the rounds”. Omega blocks are larger than ballots and take much more time to gossip.

What about those nodes that aren’t a front end for a decentralized application or users that want to send transactions to the blockchain that don’t know about a trusted node? They will want assurances that eventually their transaction will make its way to an honest node. Deploy gossiping is how this happens. Deploy gossiping happens in both Bitcoin and Ethereum today.

Now what if we run both deploy gossiping and Omega blocks enabled at the same time? That again depends on the round exponent. With just Omega blocks enabled, only validators who had a deploy will produce a block for an Omega, and the others will send a ballot. If we enable deploy gossiping across the network, we could assume that all the nodes always have deploys, so they can each produce blocks for Omega during each round. Whether they do so depends on how long the round is: if it’s long enough and they have a chance to see each other’s Omegas, then the next validator to propose will eliminate all the deploys which are already executed and in the past cone of the DAG. Otherwise they will produce a block which will likely contain some of the same deploys as other Omega blocks. Validating these blocks cannot sidestep executing the contracts to check the correctness of the post state hash, making the combination of the two potentially wildly inefficient.

However, with longer rounds, enabling both could be beneficial because:

• If an Omega-message block is not picked as a parent by the next block, then some other validator will include the same deploys, rather than just the same validator in the next round. This reduces the likelihood of orphaned blocks.
• A deploy doesn’t have to wait on a leader block, rather it would appear at whoever is producing the next Omega.

This configuration enables us to maintain liveness in the protocol and reduce the consensus overhead in the protocol.

We updated the configuration in the testnet to have 8 minute rounds. With Omegas enabled and assuming uniform distribution, the network can propose up to 25 blocks per round (1 lambda, 24 omegas), so once per ~20 seconds, which is more stringent without the massive communication overhead and wasted disk space.

The Last Finalized Block moves less often, but the orphan rate is reasonably low at the same time.

A Deeper Dive into Efficiency

The beauty of the Highway protocol is that it adjusts according to network conditions and traffic, such that it will optimize for the best efficiency and performance. Omega blocks are one facet of what we have developed to bring this technology to its proper scale. Other areas where we are fine tuning the protocol are block sizes, deploy sizes and of course, the performance of the VM and software itself.