In terms of the blockchain scalability, we have kinds of consensus mechanism optimizations, such as Tendermin and Sharding. The new solutions decouple the time and state updates, propose the program for asynchronous processing of transactions. Will the blockchain scalability be redefined therefore?

 

Foreword

Let’s see what may happen in the future.

In the coming years, there will be many smart contract platforms (ETH2.0, Dfinity, Near, Algrorand, Kadena, Spacemesh, Solana etc.) and each team will look for a different expansion strategy.

However, most of these approaches cannot solve the key problem in distributed computing systems in the Byzantine environment: the clock. To achieve consensus, at least 51% of the machines in the network must execute the same transaction in the same time and order. For this purpose, the machines need consensus on the overall clock consistency.

If all the machines without mutual trust reach consensus on the overall clock in the Byzantine environment, the “clock problem” will face a big challenge. Once everyone has agreed on the overall clock, the transaction order will become much simpler because each transaction adopts the same clock with timestamp.

Before the modern era of encryption, the clock problem has emerged in other large-scale networks, especially in the wireless communications. Cell phone towers must support tens of thousands of phones simultaneously, which results in insufficient bandwidth for each handset to transmit at its own radio frequency. Therefore, the telecom companies need “multiple access technology” to make multiple calls on the same frequency.

During the World War II, the technology of Code Division Multiple Access, which is also known as CDMA, was invented. In order to solve the clock problem, CDMA requires each phone to encrypt its data with a unique key and transmit data with other phones on different frequencies simultaneously, which will separate the combined signals into separate calls based on the tower. The mode efficiency optimization is synchronized with the complexity of the encryption mode. For the networks to adopt it on a large scale, it must support cheap low-end devices while the speed of such optimization seems to be slow and stable.

Since the 2G network came into being, telecom companies have achieved faster efficiency by implementing Time Division Multiple Access (TDMA) technology, which has become the standard solution for clock problem. TDMA specifies the towers and divides each radio frequency into time segments before assigning them to each cellphone.

In this way, the tower provides the available clock for the overall network. It allows each frequency to support multiple simultaneous data channels and reduces the interference from multiple telephony broadcasts on the same frequency and time, so as to greatly increase the scalability on a limited bandwidth.

In this article, we will discuss how to cope with the clock problem for different blockchains in the Byzantine environment. In the end, we will demonstrate that building a blockchain with the most efficient clock will successfully separate time and state to realize extension in a secure and decentralized way to support millions of users.

 

Decentralized Consensus with Clock

The Google Spanner database is one of the world’s best distributed databases, whose transactions are all synchronized with 18 instances. It supports 50,000+ TPS with less than one second. Spanner adopts the Paxos consensus algorithm, which was first released in 1989. Spanner is a trusted database based on license. Paxos allows Spanner to run even in the case of power outages, server failures, malicious errors and countless other failures.

When the highest throughput blockchain has only 21 instances and is still struggling to achieve 5,000+ TPS, how can Paxos achieve such a good performance? Google has full-time engineers of maintenance who will synchronize the atomic clocks to each data center on a regular basis to achieve high accuracy.

Providing a trusted clock available allows time stamping of the transactions, so that each instance can receive transactions without being in order but can be processed in the correct order. That’s the separation of time and state. Since each instance will update the state without the necessity of checking the peer nodes to ensure they can handle the same operations in the same order.

What can be learnt from Spanner? If there is an overall clock available in a non-byzantine environment, it is easy to reach a consensus.

Unfortunately, on current smart contract platforms there are two additional restrictions which Spanner doesn’t have:

1. To ensure the platform has anti-review capability, it does not need any license to become a verifier.
2. Even up to 1/3 of the nodes are malicious, the blockchain must ensure the security of users’ funds.

If anyone can start a certifier instance anywhere in the world, the consensus algorithm must be designed to accommodate different hardware and network configurations as well as the management of malicious nodes. In addition, no information out of the band should be trusted for the sake of anti-review capability (the Oracle issue).

About 20 years later after the invention of Paxos, a man started to consider how to reach consensus on standardized transaction order in a license-free computer network. It was Satoshi Nakamoto and his solution was known as the PoW consensus.

 

PoW + Time Chain = Clock

It’s worth noting that the bitcoin codes pre-released by Nakamoto referred the blockchain data structure as the “time chain.” The time chain was designed to ticktock every 10 minutes on average (cleverly combine PoW, difficulty adjustment and the longest chain rules together), and each ticktock appeared in the form of a trading block with update of overall state.

After the node executes a trading block, it will be locked without any state updates until it generates its own valid new block or receives a valid new block from the network. In the PoW, the time and state are coupled together. Without the status update, the time cannot be pushed forward.

It’s a hot topic on what makes the block “effective”. The transaction format and block size are just two of the many aspects to be considered. However, one thing is not controversial. The valid block must contain the hash value of previous block, so that the network knows it should be put after the previous block in the time chain.

The purpose of time chain is to address the aforesaid requirements: to become a certifier needs no certificate. The only way to verify the validity of current state of bitcoin network is to execute each transaction from the genesis block to the current state. The time chain provides an audit trail for the new verifier.

The hash time chain produces a logical, monotonous, irregular and not very precise clock. Any verifier in the network can independently conduct verification without any information out of the band.

In an open and unlicensed environment, the overall available and credible clock is the greatest innovation of Nakamoto. Since the overall state is locked, a new block will not be generated until the ticktock of the clock. Therefore, the math of extensibility is very simple:

Throughput [TPS]=block size [txs per block]/block time [per block second]

To increase throughput, the protocol either increases the block size or reduces the block time. Increasing the block size will not be conducive to the decentralization of block creators while reducing the block time will increase the fork probability in the chain.

Since the time and state are coupled, there is no way to solve such a problem.

Let’ get back to the example of wireless communication and we can compare this problem with CDMA. In CDMA, the radio tower has a fixed frequency bandwidth to be monitored, which is similar to a fixed block size which the block creator can handle.

Increasing the scalability of CDMA means creating more complicated coding schemes to accommodate more calls in a limited bandwidth. It’s similar to Segwit, lightning network, Schnorr signature, which are more complicated coding schemes with better performance.

Bitcoin has a 1MB block with 600 seconds of block time. The minimum transaction is 250B and the maximum throughput is 7TPS theoretically.

Compared to Spanner, it means the bitcoin throughput has been reduced by more than 7,000 times which is 3,600 times slower than TTF (because it takes the time of 6 blocks to achieve the irreversible finality in the probability).

Obviously, there is room for bitcoin to be improved.

 

PoS + Time Chain = Faster Clock

The growth of bitcoin has brought about the revival of consensus algorithm research. The CAP theorem tells us that in the case of network partition, the distributed database system must make a choice between consistency (network stop) or availability (network fork). Nakamoto’s algorithm is the first non-licensed BFT consensus algorithm. All these algorithms put the availability superior to the consistency. There are many consensus algorithms in the Nakamoto algorithms family.

Leslie Lamport’s Paxos algorithm is the first in the family of classical consensus algorithms, which favors consistency rather than usability.

According to Paxos and many other consensus algorithms, each node participating in the consensus must communicate with the verification node in the network on status update. Thus, the complexity of communication will be increased by O(n^2) (where n is the number of verifiers), which means that the time required by each status update will grow exponentially as the verifier increases.

Jae Kwon and Ethan Buchman were the pioneer in classic consensus study for 20 years. They combined it with a cryptographic economic incentive structure called Bonded Proof of Stake to securely limit the number of certifiers. Their achievement was the first high-performance, unlicensed BFT consensus algorithm in the classic consensus family: Tendermint.

Tendermint, like Sakamoto’s consensus mechanism, combines time and status update, so throughput will increase either larger block size or less block time. When bitcoin was created in 2009, the block time of about 10 minutes was reasonable. However, the bandwidth has grown exponentially now, which allows Tendermint to reduce block time to a few seconds.

Since the Tendermint prefers consistency, the fork is impossible. The block time can be reduced until the network throughput with given number of certifiers reaches the bottleneck of system performance. Today, Tendermint allows the network to limit its number of certifiers to 100 securely, so that the nodes with poor bandwidth will be filtered and larger blocks will be allowed.

Tendermint is running. Cosmos Hub is the first online case of Tendermint. The block time is 6 seconds and the block size is 150kb, the allowable maximum throughput is 100TPS (assuming single transaction is 250 bytes). However, it took only a few months to grow mature.

For a Tendermint network, in the case of 5 seconds of block time and 5MB block size, it can theoretically reach 4,000 TPS [(5 * 1024 * 1024) / 250 / 5 = 4194.4, about 4,000 TPS]. Compared with the bitcoin, it sacrifices less in terms of anti-censorship and non-license, especially in the premise of a throughput increase of 570 times and a decrease of 720 times TTF.

Unfortunately, due to the synchronous nature of the classic consensus algorithm, the matching Spanner can have adverse effect on the anti-censorship and non-license attribute of the system. Larger blocks will inevitably spend more time on communication within the network and the verifiers will also spend more time on verification. Hence, a lower limit is set for the block time.

To increase the clock speed, the number of verifiers also needs to be greatly reduced, and they all should be directly connected to the same fiber network, which will make the verifiers more possibly to get colluded, increase the threshold for new certifiers and make the fiber network operators become a focus.

The next generation evolution of blockchain consensus has taken an important step in the decoupling of time and state, which realizes a huge increase in throughput, but at the same time incurs huge costs.

 

Sharding + Time Chain = Independent Clock

With BPoS, Tendermint has untied the anti-censorship and certifier number, which allows the network clock to tick once from 600 seconds to 5 seconds, thus the performance has been greatly improved. However, when the clock is ticking, the entire overall clock is still locked to maintain an overall consistence.

One way to alleviate this problem is to divide the overall state into a bunch of smaller Shardings, each with its own independent clock and can advance transactions independently. So long as these Shardings do not need interaction, the performance of each Sharding will remain unchanged, and the cumulative throughput of all Shardings will increase linearly as the number of Shardings increases.

Cosmos assumes that there are many independent blockchain networks in parallel which can pass values to each other, but most transactions only occur within their own systems. If each network can handle 4,000 TPS with 13 separate networks, the system can surpass Spanner to reach 52,000 TPS. However, there are two problems:

1. The security of PoS blockchain is measured by obtaining 33% of collateral tokens and the cost of approving invalid transactions. If it’s not a single token supply with 13 independent networks, the cost of obtaining 33% of collateral tokens for a given network will be greatly reduced. This is not only far from being safe, but also seriously damages the blockchain value, since the security is an attribute of network value.
2. The TTF for inter-network transmission is increased by at least 4 times compared to intra-network transmission. The networks must communicate back and forth to synchronize their clocks so that Bob can successfully receive the value in his network before Alice’s tokens are burned at her network.

Although Cosmos assumes a world with many independent networks which are inherently secure, Ethereum 2.0, Algorand, etc. are building systems to solve the security issues about sharing mentioned above.

The solutions of every team are slightly different, but the basic framework involves a single beacon chain which provides clock for the rest of the network. At the same time, it securely shuffles the verifiers among the Shardings and thereby shares a common pool of security. Just like the Cosmos, it’s easy to increase the throughput: only add more Shardings.

Unfortunately, the second problem of high TTF between networks still exists. Even though the beacon chain can provide the overall clock, each Sharding only periodically synchronizes the local clock with the beacon chain.

If Alice wants to send tokens from Sharding A to Bob at Sharding B, the verifier of Sharding A must prove the tokens for Bob have burned before the verifier at Sharding B mine the same number of tokens to Bob. According to the current design of Ethereum 2.0, the process will take 6 minutes, 60 times of that at cross Shardings.

Although the Shardings can be of some help, the basic scalability limitations are still predictable because the time and status update for each Sharding are coupled. Taking the block size and time into consideration, each Sharding is still subject to the same limitations which Tendermint is facing.

Shardings are similar to certain elements of TDMA; states are divided into separate Shardings with their own independent clocks in the same manner that the tower divides its bandwidth into independent radio frequencies and time Shardings. The benefits of such an approach are obvious, but they are not fully utilized, for instance, the delay across Shardings can also prove it.

However, how to decouple time and status updates in an unlicensed environment?

 

Separate Time and State

So far, we have discussed how Satoshi Nakamoto has created a time-chain data structure to provide a trustless clock for the bitcoin network; discussed how Kwon and Buchman apply BPoS to the Paxos consensus algorithm to safely reduce the verifier number and expedite Tendermint network clock; discussed dividing the network into multiple Shardings with independent clocks, which can greatly increase throughput (so long as cross Sharding transactions are minimized).

However, in all these improvements, the state updates and time are still coupled, state updates only occur with the tick of network clock, so it brings a fundamental limitation in the following aspects: throughput, the final time for anti-censorship and a non-license computer network.

Separating time and state requires a clock available in overall network, which should be fast and accurate with minimized trust. With such an overall clock, the state updates can be made continuously and asynchronously, as Spanner did. So long as everyone agrees to the overall clock with their transactions time stamped, the transactions can continue to flow between networks.

Solana separates the hash-based time chain from state updates to build a clock with minimized trust for its smart contract platform. Instead of linking the hashes of each block together, the verifiers on the network continue to hash the hashes in the block. Such a kind of mechanism is called PoH (Proof of History), which generates the time chain with minimized trust available for all the nodes in the network.

The existence of independent time chain allows the leader to broadcast to the committee as soon as possible after receiving a time stamp transaction. The timestamps provide a canonical order instead of the order arbitrarily determined by the block producer. The double spending now is easy to be solved because the entire network can reach consensus on the order of transactions.

It has changed everything.

To verify the passage of time instead of forcing the verifiers to reach a consensus every 6 or 600 seconds, the verifiers in Solana can continue to send status updates to their peer nodes in real time.

Instead of waiting for the confirmations from every other node (it’s the same case in other blockchains), Solana can use the new fan-out mechanism to keep the communication complexity O(log(n)) instead of O(n^2), which is also called Turbine due to being inspired by BitTorrent. It allows Solana to process more than 50,000 TPS in a single global state with fast finality without any Sharding.

This means that the verifier pool size is equivalent to Tendermint with the order of magnitude of 100-1000, but it allows the chain to fork. The more proactive fork management policy is required to ensure that the system will be quickly merged into a single chain once the chain fork appears, which is a necessary trade-off between asynchronous process and continuous availability.

The significance of comparing wireless communication to a complete loop as well as the significance of PoH for blockchain are just like that of TDMA for cellular networks. The 1000 Solana verifiers are regarded as radio towers to subdivide the bandwidth into different time Shardings by means of their synchronized clocks.

They continuously receive the latest transactions carrying the signed PoH hash by the sender and send them to the neighbor nodes, so that they can immediately sort these transactions by means of such PoH hashes.

Since the leader rotation is based on the overall clock, each leader selects a set of orderly transactions to execute and shares the “entry” to the network. The verifier returns their votes for each “entry” and confirms the finality of the transaction when they see the agreement of the 2/3 majority of the verifiers.

As a whole, the network continuously processes transactions with high capacity in the same order. However, each verifier handles the transaction independently, so it’s a subtle and profound change compared to other blockchains. As for the Solana, the verifier will never stop processing transactions, regardless of the other network conditions and consensus.

There are other related issues which are not so important, such as rapid chain growth, new programming models, unbiased time chains, parallelism, etc. The new design also has many problems which have been solved in the Solana document. Now, Solana has processed and handled transactions over 50,000 TPS with an average TTF of 1.5 seconds on the test network of 200 verifiers in 5 continents. It’s comparable to Spanner with more substantial decentralization.

It is possible to achieve this level of performance in a world of computers with minimized trust and without license, because Solana separates the time and state. The overall clock available for the Solana network allows each node to update the state without communication with any other node, just like Spanner.

 

Reshape Scalability

Although the cryptographic community has written a lot about scalability and consensus models, no one has specifically discussed the distributed clock. After years of PoS research, Tendermint+BPoS is finally regarded as the best achievement. Many Shardings programs are basically based on the beacon chain + state Sharding framework, which allows the granular time chain for asynchronous state updates to provide best performance for the Sharding system. In comparison with the consistency, these systems more prefer to availability.

Providing the overall clock available allows the Solana team to take advantage of the more than 40 years of research on distributed system, otherwise all these researches would become unusable. Concepts like OCC (Optimistic Concurrency Control, also called Optimistic Lock) were invented in 1981 and have been used in large computing projects for many years. However, it cannot be applied if the time and state must advance simultaneously.

Parallel processing with GPU has always existed since 1995. But until in 2007 when Nvidia released the CUDA development environment, it was basically limited to GPUs and cannot be fully utilized by the blockchain system. The blockchain system pessimistically locks all states except for the accounts whose transactions are being processed.

Understanding the passage of time is crucial to understanding the performance of distributed systems in licensed and unlicensed environments. Time means everything. With the new approach of coding the passage of time through the form of PoH (Proof of History), the unlicensed system is comparable to the performance of the proved and centralized cloud computing.