A Review of Asynchronous and Semi-Synchronous Blockchains

Headshot

Eden Block

• Categories:

Project Designs

The previous articles on blockchain design discussed the theoretical implications of design choices and trade-offs in Blockchain projects. The main distinction is made between asynchronous and semi-synchronous networks. Asynchronous networks do not provide any feedback messages to nodes on whether a message has been received or not. To provide readers with a better understanding and to put the concepts discussed into context, this article provides an overview of several projects. Each of these projects focuses on one of the two design choices outlined in the FLP and CAP theorem. This article will analyze the implications of networks that prioritize consistency over availability and vice versa.

Asynchronous

Availability over Consistency: HashGraph

HashGraph prioritizes availability over consistency in an asynchronous network. The system does not provide any feedback to nodes about whether their messages was received. Therefore, nodes are likely to have different views of the overall state of the network. Additionally, the network only synchronizes periodically. Even if nodes have different views on the network, HashGraph’s consensus still allows them to make transactions, because the system relies on a predefined set of validator nodes who are expected to be honest and maintain the recent network state. HashGraph is an example of an asynchronous network that prioritizes availability over consistency.

Consensus
Using guaranteed byzantine fault tolerance, HashGraph is based on a gossip protocol in which participants don’t just gossip, but they gossip about gossip. This means that a member, A, of the network will choose another member, B, of the network at random. A will then tell B everything they know about the current state of the network and about new events (e.g. transactions). If this happens a finite but previously undefined amount of times, the messages will reach B, and B will be able to adapt the new state. This is an ongoing process between nodes to ensure that all nodes see the same network state. However, there is no guarantee that messages have been transmitted successfully.

HashGraph’s consensus model leads to improved transaction throughput because nodes do not have to wait until other nodes have received their messages. As such, they can continue validating transactions, overcoming a large network bottleneck. However, the downside of HashGraph is that it will never achieve complete decentralisation. If nodes could constantly leave and rejoin the network, gossip about gossip would be highly inaccurate. Therefore, HashGraph is a permissioned network.

Fault tolerance
Asynchronous networks have to be more resistant to partitions because they are less able to recover from them. HashGraph assumes that malicious activities on the network will only contribute to message delays. At some point, an adversary has to let a message through or the actor will be skipped by participants for being offline. Therefore, the consensus system relies on its participants to continually send messages, whereby one of these messages will eventually reach an honest recipient. On one hand, nodes in the network have to deal with a constant message overhead, which refers to more messages being sent than actually needed to broadcast the network state. On the other hand, the message overhead ensures successful message transfer in an asynchronous network that does not provide feedback mechanisms. Without feedback mechanisms, the network design has to ensure that nodes still receive messages on the state of the network. It accomplishes this by simply spamming messages.

Non-deterministic
The messaging system, implemented by HashGraph, makes the network non-deterministic, because the network structure will not always lead to the same outcome. Imagine a system where text messages are only delivered to a phone when the user presses the home button. Pressing the home button will either facilitate the delivery of the waiting message or nothing will happen. If there’s no message, nothing will always be the outcome. But even if there is a waiting message, sometimes the message will come up as nothing because the message is simply delayed. The only requirement is that pressing the home button infinitely many times will ensure that all texts are eventually received. This means that messages may be arbitrarily delayed, but not completely lost. This is nondeterministic since the same action (button press) doesn’t always result in the same result (receive message).

However, “most of the time in distributed systems, things are not so simple. Any binary decision that must be agreed on by multiple nodes can be in one of three states: ‘definitely yes,’ ‘definitely no,’ or ‘undecided.’ When a decision is ‘definitely yes,’ we mean that no honest node will ever output ‘no’ for that decision. Until a node is certain that none of its peers will output ‘no,’ it must keep the decision in an ‘undecided state.’” (10)

Hashgraph
Transactions have to be approved by a supermajority of the validator nodes in the system. Any transaction is only final if a majority of nodes in the network have seen and signed the transaction. Once the transaction is final, it is broadcasted to the remainder of the network. In other words, the consensus decision will be based on the “first” transaction that reached the majority of the nodes. Resulting, it does not matter if transaction A has been submitted to the network before transaction B. If transaction B reaches the majority signatures first, it will be appended to the network first. Eventually, all participants will receive the same ordered list of transactions.

Note, that in some systems, this relative ordering is very important, whereas for other systems, it does not matter.

Summary
HashGraph does not have an intrinsic ordering of the transactions it processes. Instead, it computes the median timestamp of each transaction, based on when it has reached the majority of validator nodes. The first transaction to be validated is the first to reach the majority of nodes. Hashgraph’s gossiping protocol does not implement any feedback mechanisms. Therefore, nodes do not know when other nodes have received their transactions and every node has to broadcast the same message several times to ensure other nodes have received it. All transactions eventually become appended to the network. Resulting, all nodes are rarely in a consistent state and the network favours availability over consistency in an asynchronous environment.

Semi-Synchronous

Network Focused on Consistency: Dfinity

Dfinity aims to be a decentralised super-computer for cloud computing, whereby nodes are able to run software deployed by smart contracts.

Dfinity prioritizes consistency over availability. Resulting, if the network is partitioned, consensus between nodes will slow down, at which nodes are unable to make any further transactions. As such, the network ensures that there is never a split in the network’s global state, even at the sake of a functioning network. In contrast, when the network is not under the influence of an adversary, any transaction, which is appended to the network, is supposed to be processed.

Consensus
In order to prioritize consistency over availability, Dfinity introduces Notarization, which is a majority signature signed by a committee. Notarization on Dfinity depends upon a random beacon generator. The combination of a random beacon generator with notarization ensures that the network will never partition into different states.

Notarization acts as a proof of consistency. The network knows that if a transaction is notarized, then the network knows that the majority of nodes have the same state, and thus, the network is consistent.

Notarization works as such. A committee is a random sample of the whole network, which is selected through a random beacon generator. Recognize that creating true randomness is not an easy task; thus, Dfinity employs a random beacon generator. Consider that a universe has 30% malicious actors. When a sample is taken from the universe, the probability that the sample is malicious actor decreases as the sample size increases. A group is honest if it has less than 50% malicious actors. A notarisation is a proof of publication and a timestamp. Once a transaction is notarized, it is considered to be valid. Ultimately, the network makes the assumption that if the majority of a large sample has seen it, then everyone has seen it and it is valid. Therefore, if the committee notarizes a transaction, the transaction should be seen by the majority of nodes in the network. Thus, the network is consistent. However, if transactions are not notarised, then the network cannot ensure that the transactions have been seen and validated by the majority of nodes in the current committee. In that case, the network would slow down and no further transactions would be made until the current transactions are notarised.

However, to prevent collusion and ensure true decentralization, the network must frequently elect a new committee. The network accomplishes this by assigning a different committee according to each new block height, whereby the block height represents the timeline. A committee is assigned for each block height and every block has a time interval. The network divides the consensus into time interval and committees. The consensus process is as follows: All nodes in Committee 1 authorize a block. Once Committee 2 has seen the authorized block of Committee 1, their time starts. The moment they see a Round 3 authorized block, Round 2 ends. Resulting, every committee is only active for a limited time frame. In addition, the process does not have to be synchronized across every member of each committee but it is important that each member of a committee is only active for a limited time interval. This ensures that no committee is active for long enough to be able to collude and that all participants have an opportunity to be involved in the consensus.

Note that a block is only valid if it is notarized and a block cannot be withheld. If only half of the members of a committee see a block before their time runs out, the block is only partially notarised. The time interval restricts block validators in the time they have to receive block proposals before they have to sign these off. This ensures that only valid blocks are notarized.

In case of a network partition, the random beacon will stop projecting on both forks. This brings the network to a halt. Resulting, while nodes might have the same view of the network, they will not be able to confirm further transactions, because no committee will be elected to validate these transactions. Dfinity thus favours consistency over availability. Only if one fork is substantially larger than the others will it continue to produce random numbers and thus, elect the next committee.

How do they recover in the case of a fault or if a set of validators is offline?
Dfinity assumes that the majority of the participants are honest and online. Otherwise the system will stop until the majority of nodes are online again. This operation is enabled through the efficient system design. Dfinity prioritizes Safety over Liveness (or Consistency over Availability).

Summary
Dfinity elects a committee based on a random number of nodes, who are elected through a random beacon generator. The committee has a certain time, measured by the prior and the next committee, to receive and sign off blocks. In case of a network fork, the random beacon will stop electing committees until the network has identified the fork with the longest notarised chain. Resulting, Dfinity chooses consistency over availability. The network does not risk receiving additional transaction, which it might not be able to process. Instead, it halts and waits until the partition is resolved.

Network focused on Availability: Solana

Solana is a high-performance blockchain that can deliver up to 710k transactions/second on a 1GB network without any data partitioning. The throughput provided by Solana is only possible because the network prioritises availability over consistency. In case of a partition, the network does not prevent nodes from broadcasting new transactions to the network. A verifiable timestamp allows nodes to verify transactions, after the partition, in the right order.

Consensus
Solana is a semi-synchronous network. To ensure fast verification of transactions, each verifier has a limited amount of time to sign transactions. The Proof of History (PoH) consensus, implemented by Solana, is based on Proof of Stake (PoS). Members, who wish to participate in the voting process of transactions, have to lock up a specific amount of stake. The nodes with the highest stake are chosen to be verifiers for the next consensus round. After processing all transaction up to a specific state, the verifier has to sign the hash of that state. Nodes have, for each consensus round, only a limited amount of time.

If the network is partitioned, validators will not be able to reach consensus because the transaction history will not be consistent across all nodes. While the validation process will slow down or halt, nodes will still be able to broadcast transactions to the network. However, to enable availability, it is crucial that all validator nodes are able to agree on the sequential order of all transactions, which have been appended to the network during the partition. Otherwise, validator nodes would not be able to know which transactions they have to sign next. Proof of History creates a record that shows that an event has occurred at a specific moment in time. Solana’s “implementation uses a sequential preimage resistant hash that runs over itself continuously with the previous output used as the next input. Periodically, the count and the current output are recorded.” (12) The main benefit of the hash function is that its output cannot be possibly predicted without actually running the last function. A record is kept for each time the function output has been called, which leads to a verifiable timestamp. Based on this timestamp, validator nodes will know in what order transactions have to be processed after a partition. This allows them to return to consistency after a partition and thus, maintain constant availability.

Summary
Solana prioritises availability over consistency. The implementation of Proof of History enables nodes to broadcast transactions to the network, even if the network is partitioned and validator nodes do not share a consistent view on the network. By using a hash function, a verifiable transaction is generated for every transaction, which allows validators to know the order in which transactions have to be signed.

Consistency over Availability: Algorand

Algorand is a decentralised transaction platform, which allows for fast and secure consensus, regardless of the number of transactions or participants. The network prioritises consistency over availability in a semi-synchronous environment.

Consensus
Similar to Dfinity and Solana, in Algorand, all messages have to be propagated within a specific time bound, called a step. A weighted fraction of at least ⅔ of the network participants have to be honest in order to reach consensus. Honest users send the messages at the start of a step and receive messages at the end of the step. Note that users do not have synchronised clocks, but every user has the same time speed. Therefore, each step requires that all users have the same amount of time. In other words, it doesn’t matter if your watch is ten minutes too fast and mine is on time, as long as we start the timer at the same time, we’ll remain in synchrony. In case of a network partition, malicious nodes might have full control over the messages sent. Otherwise, all messages should be received within a fixed period of time. Thus, because it sets time bounds like Solana, Algorand is a semi-synchronous network.

Consistency
By dividing transactions into final and tentative consensus, Algorand provides a distinction between transactions that are consistent across the network, and transactions which have not been verified by the majority of validators. If a user reaches final consensus on a block within one consensus round, all other users must reach final consensus on the same block. Furthermore, all subsequent blocks, including final or tentative consensus, must be built on the block, which already reached final consensus. This ensures Algorand’s consistency, because all future transactions will be chained to this final block (and, transitively, to its predecessors). “Thus, Algorand confirms a transaction when the transaction’s block (or any successor block) reaches final consensus.” (9) Nodes can be sure that the majority of nodes in the network will have seen all the blocks that have reached final consensus. This is very similar to Dfinity’s use of notarisation to ensure network consistency.

Summary
In Algorand, transactions have to be propagated within a specific time frame, whereby nodes do not have to follow a common clock but the speed of time has to be the same for each node. By dividing consensus into final and tentative consensus, the network can agree on the sets of nodes, which should be consistent across the majority of nodes. During final consensus, the majority of network participants will have agreed on the same block for the given block height. In contrast, in tentative consensus, several blocks may reach final consensus.

Comparison

HashGraph is the only network between the four analysed projects which has both asynchronous messaging properties and prioritises consistency. The network is only able to reach consistency because of its predefined set of verifier nodes. To update other nodes on the current network state, nodes have to create a message overhead to ensure messages are received by the other nodes in the network.

In contrast, Dfinity, Solana, and Algorand are all classified as semi-synchronous networks, because the consensus is constrained by fixed consensus rounds, whereby verifier nodes have a predefined amount of time to reach consensus. While Solana focuses on availability, both Algorand and Dfinity prioritise consistency. If a network prioritises availability, like Solana, it has to indicate a universal transaction order. To achieve this, Solana relies heavily on timestamps, which are generated through its Proof of History consensus. Timestamps indicate the order of Solana’s transaction history and enable transactions even in the case of a network partition.

In comparison to Solana, Algorand and Dfinity experience a network halt in the case of a network partition, whereby the network can only agree on messages which have been marked consistent across nodes. Algorand’s division between tentative and final consensus has the same purpose as Dfinity’s block notarisation. Every block that has reached final consensus in Algorand should be consistent across the majority of nodes. The same holds true for notarised blocks in Dfinity.

 

Sources