Moonshot Consensus: Optimistic Proposal for Blockchain-Based State Machine Replication

DOWNLOAD WHITEPAPER PDF | VIEW PRESENTATION DECK

Public blockchain networks are revolutionizing modern society by securely decentralizing computation and storage. They do this by marrying fault-tolerant distributed systems design with cryptography to enable greater transparency, accountability and integrity than traditional, centralized computer networks. This makes them well-suited for solving many problems that have traditionally required reliance on a small number of trusted parties.

Consequently, blockchains provide many opportunities for increased personal autonomy and societal efficiency. We at Supra believe that this technology has the potential to revolutionize the global economy and culture in a way that will define the next century.

The advent of Bitcoin in 2008 paved the way for the blockchain industry of today. Today, there are many public blockchains and the space continues to grow in exciting ways.

Blockchains and Consensus

So, what exactly is a blockchain? Well, a blockchain is essentially a type of distributed database. This database keeps a growing log of finalized transactions, which are submitted by the users of the system when they want to interact with it. What these transactions can do depends on the capabilities of the blockchain in question, but they always have some kind of side-effect. These side-effects update another part of the database called the state of the blockchain, which keeps track of the information that the users care about. The goal of the blockchain network is to ensure that all of the computers in the network—often called nodes—process the same transactions in the same order so that they arrive at the same state.

Each blockchain network relies on a consensus protocol to achieve this consistency. This protocol is run by computers called validators and typically groups transactions into blocks for the sake of efficiency. The validators collectively agree upon the order of each block and produce an unforgeable and verifiable proof of this agreement, which we will refer to as a canonicity proof. This proof allows nodes outside of the validator set to participate in the blockchain network by maintaining their own local copy of the blockchain without having to participate in the consensus protocol.

When a node adds a new block to its local blockchain that block is said to have some degree of finality. Some blockchains, like Bitcoin and its derivatives, only guarantee probabilistic finality. For example, when a Bitcoin node adds a new block to its local blockchain, it is possible that it may eventually have to replace it due to the validators collectively generating a longer chain that does not include this block. Since Bitcoin nodes are required to accept the longest chain that they are aware of, if this occurs then the node would be forced to change its view of the chain in order to remain a part of the canonical network.

Other networks have different rules that achieve the same effect. However, for the sake of this article we are specifically interested in blockchain consensus protocols that achieve deterministic finality. These protocols ensure that if any node commits a new block to its blockchain then it will never have to replace that block with another. These protocols are more formally known as State Machine Replication (SMR) protocols.

More precisely, SMR protocols ensure that if any two honest processes each commit a block to the same position in their respective local blockchain, then these two blocks are the same. This property is called Safety. These protocols also ensure that validators continue to add new blocks to their local blockchains while the network continues to operate. This property is called Liveness.

There are different types of SMR protocols, but today we are specifically interested in those that order blocks one at a time by explicitly linking each block to its immediate predecessor. We’ll refer to these types of SMR protocols as blockchain-based SMR protocols.

The figure above illustrates the consensus process of a blockchain-based SMR protocol. The protocol begins with one of the validators, depicted here as white circles, building a block from its local pool of transactions and proposing it to its peers as a candidate for addition to the blockchain. We refer to this validator as a leader. The remaining validators then work to generate a canonicity proof for this proposal, the construction of which depends on the protocol. Any node that observes such a proof commits the corresponding block to its local blockchain by adding all of the included transactions to its log of finalized transactions and applying their side-effects to its state, as shown in the figure below.

Problem Setting

Today, we want to introduce the Moonshot family of blockchain-based SMR protocols, a novel collection of blockchain consensus protocols characterised by Optimistic Proposal. We will be primarily focusing on Chained Moonshot, the first of the Moonshot family of protocols. We will start by defining the setting that Moonshot is built for.

Moonshot protocols, like many other blockchain consensus protocols, are Byzantine Fault Tolerant (BFT). This means that they will continue to function correctly even if some of the validators crash or otherwise deviate from the protocol. We call validators that behave in this manner Byzantine, and those that follow the protocol correctly, honest.

We assume that all of the Byzantine validators are controlled by a single adversary, meaning that they may cooperate to cause as much damage to the system as possible. We also assume that this adversary is static, meaning that it may choose which subset of the validators to corrupt before the protocol starts, but may not make any changes to this set during execution.

Informally, Moonshot protocols tolerate up to one third of the validators becoming Byzantine. More precisely, we require that the total number of validators in the network \(n\) satisfy \(n \ge 3f+1\), where \(f\) is the number of Byzantine validators. For the sake of this article we will assume that \(n = 3f + 1\) and will use the term quorum to refer to a group of \(2f + 1\) or more validators.

We also allow the adversary some degree of control over the communication channels between the validators. We assume that all of the validators in the network communicate with each other directly. We also assume that the messages sent on these point-to-point links are cryptographically authenticated, meaning that they cannot be forged or modified by the adversary. We allow the adversary to delay these messages, but require that it must eventually deliver them.

Specifically, Moonshot operates in the Partially Synchronous setting. A Bounded Synchronous network is one where there is a known upper bound \(\Delta\) on the delay between the dispatch of a message by its sender and its receipt by its intended recipient. Comparatively, an Asynchronous network is one where there is no such time-bound on message delivery latency.

The Partially Synchronous network model lies at the intersection of these two models. There are several variants of Partial Synchrony, but we specifically consider the type that we consider to be most representative of real-world public networks. In this version of Partial Synchrony, the network may alternate between periods of asynchrony and synchrony. We refer to the moments at which the network transitions from asynchrony to synchrony as Global Stabilization Times (GSTs). You will find a more formal treatment of this definition in our technical paper.

While we use \(\Delta\) to represent the upper bound on message delivery latency after GST, we use \(\delta\) to represent the average delivery latency after GST. Accordingly, \(\delta \le \Delta\) depending on the behavior of the adversary.

Introducing Moonshot

Let’s take a look at some existing blockchain-based SMR protocols that operate in the same setting as Moonshot so that we can understand the intuition behind Moonshot’s Optimistic Proposal technique. We will evaluate these protocols in terms of their block finalization latency, block period and message complexity (alternatively called communication complexity). We define block period as the time between block proposals, and block finalization latency as being the time between the proposal of a block and it being committed by a majority of the honest validators. We measure message complexity asymptotically by approximating the number of messages required to achieve consensus on a single block in terms of \(n\).

Specifically, to keep things simple we will just be focusing on the Normal Path of each of these protocols. A protocol is said to be in its Normal Path (sometimes called Fast Path, Happy Path or Steady State) when there are no interruptions to the consensus process. Comparatively, the protocol enters its Fallback Path whenever it fails to make progress towards agreement on a consensus instance after a certain amount of time, measured in terms of \(\Delta\), which can occur due to network asynchrony or Byzantine leaders. These protocols are most efficient when operating in their Normal Paths, while their Fallback Paths enable them to achieve Liveness. We will examine the Fallback Paths of these protocols further in future content.

Tendermint

The Practical Byzantine Fault Tolerance (PBFT) SMR protocol was designed by Miguel Castro and Barbara Liskov, and was published in this paper in the proceedings of the 1999 OSDI conference. PBFT was the first published solution for Byzantine Fault-Tolerant SMR in the partially synchronous setting. Many years later, PBFT was adapted to the blockchain setting in the Tendermint protocol. Cosmos and many of the blockchains in its ecosystem currently use this protocol as their consensus engine.

Unlike Moonshot, which assumes a fully-connected network and that communication between different validators occurs directly over point-to-point links, Tendermint assumes that messages are sent via a gossip protocol. Consequently, for the sake of a fair comparison we will instead be considering a variant of Tendermint that operates in the same setting as Moonshot. Accordingly, we assume that whenever a Tendermint validator receives a previously-unseen message from one of its peers, it immediately forwards that message on to all others.

This gives the protocol a communication complexity of \(O (n^3)\), since each process receives \(O (n)\) unique votes when the system is operating normally. We acknowledge that a more efficient translation of Tendermint to the point-to-point setting may exist, but use this implementation because it is simple and because we are sure that it preserves the guarantees afforded by the original gossip protocol. We leave this forwarding out of the following diagram for the sake of readability.

So, letʼs examine how this modified version of Tendermint operates in its Normal Path. Suppose that we have a network of 4 validators, one of which we designate as the leader, making it responsible for proposing the next block to add to our blockchain. The Normal Path of Tendermint proceeds as follows:

• Step 1. The leader builds a new block of transactions that extends the last committed block and proposes it by broadcasting it to the other 3 validators in a Proposal message (called Pre-Prepare in the Tendermint paper).
• Step 2. The validators send their endorsements of this proposal—Prepare votes—to every other validator. At the end of Step 2, the validators receive one Prepare vote from each of their peers. They each collect a quorum of these votes and form a Prepare Quorum Certificate (Prepare QC), then lock the related block.
• Step 3. After forming a Prepare QC, and on this basis, the validators then send their second endorsements of the proposal—Commit votes (called Pre-Commit in Tendermint paper)—to each other. Again, they each collect a quorum of these votes and form a Commit QC. The Commit QC serves as a canonicity proof for the block, allowing the nodes that observe it to commit the related block.

After Step 3, the validators enter a new round and the process repeats. This gives the Normal Path of Tendermint the following characteristics:

• Block Finalization Latency. Tendermint finalizes a block in \(3\delta\).
• Block Period. Tendermint produces one block every \(3\delta\).
• Communication Complexity. Tendermint validators must send \(O (n^3)\) messages to achieve consensus on a block.

Tendermint’s two rounds of voting help it to obtain the Safety SMR property. The Prepare QC produced by the first round of voting proves that a majority of the honest validators consider the new block to be valid. The Commit QC produced by the second round proves that a majority of the honest validators are aware of this fact and have locked the related block. Tendermint’s voting rule ensures that if a validator has locked a block then it will not vote for any other block that is proposed for the same position, or height, in the blockchain.

Consequently, since QCs require \(2f + 1\) out of \(3f + 1\) votes, if a block achieves a Commit QC then any other block proposed for the same height will receive at most \(2f\) votes, even if the Byzantine validators vote for both blocks. However, this rule is quite strict, precluding concurrency and posing difficulties to Liveness without the guarantees provided by Tendermint’s gossip protocol. Later protocols would relax this requirement, as we will see.

Jolteon

Now, let’s consider a more recent SMR protocol, Jolteon. This protocol illustrates the concept of round pipelining and, like Tendermint, has two voting phases. Jolteon operates in its Normal Path as follows:

• Step 1. Similarly to Tendermint, the leader builds a block \(\mathcal{B}_1\) and broadcasts it to all.
• Step 2. Again, like Tendermint, the validators send Prepare votes for this block. However, rather than broadcasting these votes they instead send them directly to the leader of the next round, who acts as an aggregator and constructs a QC as before.
• Step 3. This leader then creates a new block, including the QC for \(\mathcal{B}_1\) in it as proof that it is extending the block most recently accepted by the network. At the end of Step 3, all of the validators end up with the QC for \(\mathcal{B}_1\), allowing them to lock \(\mathcal{B}_1\).
• Steps 4 and 5. Steps 2 and 3 are then repeated to construct a Prepare QC for \(\mathcal{B}_2\), which serves as the Commit QC for \(\mathcal{B}_1\) and reaches all validators along with the third leader’s proposal of \(\mathcal{B}_3\), allowing them to lock \(\mathcal{B}_2\) and commit \(\mathcal{B}_1\).

As we can see, Jolteon does several things differently to Tendermint. Firstly, it allows leaders to propose on the basis of a Prepare QC for the proposal of their predecessor. This enables the protocol to make progress towards consensus on multiple blocks concurrently, a significant optimization when compared with Tendermint’s strictly-sequential progression. This in turn allows it to further reduce the number of messages required to achieve consensus by merging Prepare and Commit votes into a single message, with Prepare votes for \(\mathcal{B}_2\) also corresponding to Commit votes for \(\mathcal{B}_1\), at least in the Normal Path. We call this latter optimization, which was first introduced in Chained HotStuff, QC chaining.

However, the former optimization comes with some side-effects, including potential threats to Safety. Jolteon overcomes these threats via a modified commit condition called the Two-Chain Commit Rule. This rule requires a node to commit a block \(\mathcal{B}\) proposed for round \(\mathcal{r}\) and all of its uncommitted ancestors in ascending order of height, only if it observes QCs for two consecutive blocks \(\mathcal{B}\) and \(\mathcal{B’}\), where \(\mathcal{B’}\) was proposed for \(r + 1\) and includes the QC for \(\mathcal{B}\).

In short, this means that if any node triggers the Two-Chain Commit Rule with \(\mathcal{B}\) then at least \(f + 1\) honest validators must have locked \(\mathcal{B}\) before voting for any block proposed after \(\mathcal{B}\). Jolteon’s voting rules are a little more complicated than Tendermint’s, so without going into the details of why, this in turn ensures that every future certified block (i.e. block that achieves a QC) is guaranteed to extend \(\mathcal{B}\).

Finally, whereas Tendermint validators broadcast their votes, Jolteon relies on a vote aggregator. HotStuff, Jolteon’s progenitor, initially introduced the concept of vote aggregation in order to obtain a protocol that could reach consensus in the Normal Path despite validators communicating with only one other validator during the voting phase. More precisely, the goal of HotStuff was to achieve a Normal Path message complexity for each consensus instance of \(\mathcal{O}(n)\).

However, using a single validator to aggregate votes also means that it takes longer for the remaining validators to learn the outcome due to having to wait for the aggregator to send them the QC. As a result, aggregator-based protocols like HotStuff and Jolteon essentially split the voting phase into two steps. Accordingly, while Leader 3 in the diagram above is able to finalize \(\mathcal{B}_1\) \(4\delta\) after its proposal by Leader 1, the remaining validators must wait an additional \(\delta\) to do the same.

To summarize, then, Jolteon achieves the following in its Normal Path:

• Block Finalization Latency. Jolteon finalizes a block in \(5\delta\).
• Block Period. Jolteon produces one block every \(2\delta\).
• Communication Complexity. Jolteon validators must send \(\mathcal{O}(n)\) messages to achieve consensus on a block.

Chained Moonshot

This brings us to Moonshot. Moonshot protocols take the concurrency of Chained HotStuff and its derivatives one step further by way of a new optimization that we call Optimistic Proposal. This technique is as simple as it sounds; rather than waiting for a QC for the block proposed by its predecessor, a Moonshot leader instead creates its own proposal as soon as it receives the block itself. This allows the protocol to start a new consensus instance every \(\delta\) during its Normal Path, which is the optimal block period for a blockchain-based SMR protocol.

Chained Moonshot is a variant of Moonshot that, like Jolteon, implements the QC chaining of Chained HotStuff. However, it eschews the vote aggregator approach, instead preferring the broadcast model of Tendermint and other PBFT-like protocols to obtain a better block finalization latency. Let’s see how its Normal Path works:

• Step 1. As before, the first leader broadcasts a new block \(\mathcal{B}_1\).
• Step 2. As in Tendermint, the validators then broadcast their votes for \(\mathcal{B}_1\). However, additionally, the leader of the next round simultaneously proposes \(\mathcal{B}_2\), referring to \(\mathcal{B}_1\) as its parent by including a concise summary called the digest of \(\mathcal{B}_1\) in \(\mathcal{B}_2\) (e.g. a cryptographic hash of \(\mathcal{B}_1\)). After receiving a quorum of votes for \(\mathcal{B}_1\), the validators lock it and enter the next round.
• Step 3. Subsequently, Step 2 repeats and a third leader proposes \(\mathcal{B}_3\) while the validators broadcast their votes for \(\mathcal{B}_2\). However, after locking the QC for \(\mathcal{B}_2\) the validators additionally commit \(\mathcal{B}_1\).

Importantly, a Chained Moonshot validator only votes for a block proposed during the Normal Path if it is already locked on its parent. Additionally, a Chained Moonshot validator is only allowed to lock a block proposed for round \(\mathcal{r}\) if it observes the QC for that block whilst in \(r + 1\), which is the round in which it is permitted to vote for the block, and before entering the Fallback Path. This, in conjunction with the Two-Chain Commit Rule—modified to require \(\mathcal{B’}\) to include the digest of \(\mathcal{B}\) instead of the QC for \(\mathcal{B}\)—ensures the Safety of the Normal Path.

Unlike our simple version of Tendermint, Chained Moonshot’s Fallback Path ensures that validators do not need to re-broadcast every message that they receive for the protocol to obtain the Liveness property. However, its broadcasting of votes still gives the protocol a communication complexity of \(\mathcal{O}(n^2)\) messages per decision in the Normal Path.

In summary, Chained Moonshot exhibits the following characteristics under normal operation:

• Block Finalization Latency. Chained Moonshot finalizes a block in \(3\delta\).
• Block Throughput. Chained Moonshot produces one block every \(\delta\).
• Communication Complexity. Chained Moonshot validators must send \(\mathcal{O}(n^2)\) messages to achieve consensus on a block.

The following figure summarizes the properties of the Normal Paths of Tendermint, Jolteon and Chained Moonshot:

Demonstrably Improved Performance

We implemented Chained Moonshot and put our theoretical predictions to the test by modifying the implementation of Jolteon available in the Narwhal-HotStuff implementation provided by Facebook Research. We then compared this implementation to the existing implementation of Jolteon, separating both from Narwhal to ensure that our measurements were not affected by the behavior of the mempool.

We considered two metrics: block throughput and block finalization latency. We measured the former by counting the number of blocks committed by at least \(2f + 1\) validators, and the latter as the time between a block being created by the leader and being committed by the \(2f + 1\)th validator.

We tested network sizes ranging from 10 to 200 nodes and block sizes ranging from 1.8kB to 18MB. We ran each benchmark in AWS on m5.xlarge instances spread globally across multiple regions, using 5 regions for the 10 and 50 node tests, and 20 regions for the 100 and 200 node tests. We ran each configuration for 5 minutes, repeating each three times to help eliminate outliers. We observed the following results.

In accordance with our theoretical analysis, Chained Moonshot finalized more blocks than Jolteon over the five minute period in all configurations. Interestingly, Chained Moonshot’s relative improvement in throughput generally increased along with the network size, showing that the communication overhead incurred by broadcasting votes instead of aggregating them was negligible in the tested configurations.

However, Chained Moonshot’s improvement to throughput was less than expected. It produced a minimum of 24.5%, a maximum of 78.4% and an average of 54.9% higher throughput across all configurations, falling short of the expected 100% improvement implied by comparing its theoretical block period to that of Jolteon.

That said, the analytical model that we used to model the block period was imprecise: it factored in neither the relative size of votes and blocks, nor the size of the network, both of which affect the actual message latencies. We will elaborate on this further in a future article when we introduce another variant of Moonshot that we have developed in response to insights gained from applying a more precise analytical model.

Comparatively, Chained Moonshot’s improvement to commit latency was even better than the 40% reduction implied by comparing its theoretical block finalization latency to Jolteon’s. Chained Moonshot produced a minimum improvement of 22.8%, a maximum of 58.7% and an average of 41.1% across all configurations.

Combining the results for these two metrics produces the graph presented below. This graph shows the throughput of both protocols as measured in bytes finalized per second versus their average block finalization latency. Both axes are log-scaled to help emphasize the relative differences in performance under smaller payload sizes. Except for the 10 node plots, each point on the graph corresponds to one of the payload sizes from the x-axis of the previous two graphs, with the payload size increasing along the line starting from zero on the x-axis. We added an extra payload size of 180MB to the set of tests for the 10 node network for this metric to help to clarify the trend.

As you can see, the plots for the 100 and 200 node networks curve back upon themselves for the larger payload sizes. The point at which this inversion happens marks the saturation point of the related protocol, after which increasing the payload size only serves to degrade performance.

Overall, this graph clearly shows that Chained Moonshot produced a higher throughput with a lower latency across all configurations. Moreover, it also produced a higher saturation point for the network sizes that reached saturation. You will find a more detailed discussion of our experiments with Chained Moonshot and Jolteon in our technical whitepaper.

Moonshot Advances the Cutting Edge

In conclusion, Chained Moonshot is a novel improvement over Jolteon, a state-of-the-art blockchain consensus protocol. It combines vote broadcasting and proposal pipelining to deliver low latency and high throughput, especially when the network is experiencing favorable conditions. This brief introduction has abstracted away many of the details of the protocol, including how it behaves in the presence of Byzantine failures. We also have yet to discuss the other variants of Moonshot, some of which we are still developing.

We will be releasing more content on these topics soon, but for now we encourage all interested readers to dig deeper by reading the latest version of our technical paper and discussing with us in our Discord. See you again soon!