Reshaping the scalability of blockchains: separation of state and time

Foreword: Regarding the scalability of the blockchain, we have various consensus mechanisms, such as Tendermint, and fragmentation mode. The new scheme solves the time and status updates and proposes the solution of asynchronous processing. Solution, can it redefine the scalability of the blockchain? Let us see what happens in the future. The author of this article is Ryan Gentry, translated by "SIEN" of "Blue Fox Notes".

In the next one or two years, many smart contract platforms will be available (ETH 2.0, Boca, etc.) and every team is looking for a different expansion strategy. (Blue Fox notes translation note: EOS has been released).

However, most of these methods do not address a fundamental problem with distributed computing systems in the Byzantine environment: clock issues. To achieve consensus, at least 51% of the machines in the network must execute the same transaction at the same time and in the same order. To achieve this, the machine needs to agree on a globally consistent clock.

Letting many machines that don't trust each other agree on the global clock in the Byzantine environment, the "clock problem" is a challenge. Once everyone agrees on the global clock, the transaction ordering becomes much simpler because each transaction uses the same global clock plus timestamp.

• Ethereum is becoming more vulnerable, and its power has fallen more than 42% from its highest point in history.
• The Digital Dimension of RMB Internationalization: What is the anchor of sovereign currency internationalization?
• Bitcoin will reach $100,000 in 2019? Claiming to be a "time traverser" from 2025

Prior to the modern era of encryption, clock problems have emerged in other large-scale networks, especially in the field of wireless communications. Cell phone towers must support tens of thousands of phones at the same time. This results in insufficient bandwidth for each handset to transmit at its own radio frequency. Therefore, telecommunications companies need "multiple access technologies" to make multiple calls on the same frequency.

In the Second World War, the technology of code division multiple access, which is 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 on several frequencies simultaneously with other phones, relying on the tower to separate the combined signals into separate calls. This mode efficiency optimization is synchronized with the complexity of the encryption mode. For networks that are to be adopted on a large scale, it must support inexpensive low-end devices, and the speed of this optimization appears to be slow and stable.

Since the birth of the 2G network, telecom companies have achieved faster efficiency gains by implementing Time Division Multiple Access (TDMA) technology, and TDMA has become the standard solution for clocking problems. TDMA specifies these towers, divides each radio frequency into time segments, and assigns these time periods to each telephone call.

In this way, the tower provides a globally available clock for the network. By allowing each frequency to support multiple simultaneous data channels and reducing interference from multiple telephony broadcasts on the same frequency at the same time, this greatly increases scalability over a limited bandwidth.

In this article, I will explore how different blockchains can cope with clock problems in a Byzantine environment. Finally, I will argue that building a blockchain with the most efficient clock will successfully separate time and state and scale in a secure and decentralized way to support millions of users.

Decentralized consensus with clock

Google's Spanner database is one of the world's best performing global distributed databases, with 18 instances, all of which are synchronized. It supports 50,000+ TPS and ends up in less than 1 second. Spanner used the Paxos consensus algorithm, which was first released in 1989. Spanner is a trusted database that requires a license. Paxos allows Spanner to run in the face of power outages, server failures, malicious errors, and countless other failures.

How does Paxos achieve this performance when there are only 21 instances of the highest throughput blockchain and still struggling to achieve 5,000+ TPS? Google has a full-time engineer to maintain a high degree of accuracy by periodically synchronizing the atomic clocks into each data center.

Providing a globally available trusted clock allows time stamping of transactions so that each instance can receive transactions without order, but can process them in the correct order. This is the separation of time and state. Because each instance updates the state without having to check its peers to make sure they handle the same operations in the same order.

What can I learn from Spanner? If there is a globally available clock in a non-byzantine environment, it is easy to reach a consensus.

Unfortunately, there are two additional restrictions on today's smart contract platforms that Spanner doesn't have:

1. To ensure that the platform has anti-review ability, it is not required to be a verifier;

2. Even if up to 1/3 of the nodes are malicious, the blockchain must ensure the security of the user's funds.

If anyone can launch a certifier instance anywhere in the world, the consensus algorithm must be designed to accommodate different hardware and network configurations, as well as the need to manage malicious nodes. In addition, in order to be truly resistant to review, you cannot trust out-of-band information (that is, Oracle issues).

After 20 years of invention by Paxos, it was conceived how to agree on a standardized transaction order in a computing network without a license. This person is Nakamoto, and the solution is the PoW consensus.

PoW+ time chain = clock

It is worth noting that Nakamoto's pre-release bitcoin code actually refers to the familiar blockchain data structure as a "time chain." This time chain is designed to tickle every 10 minutes on average (by cleverly combining PoW, difficulty adjustment, and longest chain rules), with each tick being in the form of a trading block that updates the global state.

After a node executes a trading block, it locks without any state updates until it generates its own valid new block or receives a valid new block from the network. In PoW, time and state are coupled together and always travel in unison. Without a status update, time cannot be advanced.

What makes the block "effective" is a heated debate. The transaction format and block size are just two of the many aspects that need to be considered. However, one aspect is not controversial, the valid block must contain a hash of the previous block, so that the network knows to place it after the previous block in the time chain.

(Each block in the blockchain contains the hash of the previous block as evidence behind it)

The purpose of the time chain is to address the requirements mentioned above: it is not required to be a certifier. The only way to verify that the current state of the Bitcoin network is valid is to start each transaction from the creation block to the current state, starting with the state of the creation block. The time chain provides an audit trail for the new verifier, which is provided by demonstrating that the transaction in block height 12 occurs and must be executed after the block transaction at block height 11.

Since block 12 must contain a hash of block 11, block 12 can only be created after block 11. The hash's time chain produces a logical, monotonous, although irregular, and not very fine clock, and any verifier in the network can independently verify without any out-of-band information.

In an open, unlicensed environment, the production of this globally usable and credible clock is the greatest innovation of Nakamoto. Because the global state is locked, until the global clock is ticking, a new block is generated. Therefore, the math of extensibility is 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 is not conducive to the decentralization of the block producers, and reducing the block time will increase the chain fork probability.

This is because time and state are coupled, so there is no way to solve this problem.

Going back to the example of wireless communication, you can compare this problem with CDMA. In CDMA, a radio tower has a fixed frequency bandwidth that can be monitored, which is similar to a fixed block size that a block producer can handle.

Increasing the scalability of CDMA means creating more complex coding schemes to accommodate more phone calls in a limited bandwidth. This is similar to Segwit isolation verification, lightning network, Schnorr signature, which are more complex coding schemes that can improve performance.

Bitcoin has a 1MB block with a block time of 600 seconds and a minimum transaction size of 250B. The theoretical maximum throughput is 7TPS. (Blue Fox note: 1024 * 1024 / 250 / 600 = 6.99, about equal to 7)

Compared to Spanner, this means that Bitcoin's throughput has been reduced by more than 7,000 times, 3,600 times slower than TTF (because it takes 6 blocks to achieve a probabilistic irreversible finality).

Obviously, there is room for improvement in Bitcoin.

PoS+ time chain = faster clock

The growth of Bitcoin has brought about a revival of consensus algorithm research. The CAP theorem tells us that in the case of network partitioning, distributed database systems must choose between consistency (network stop) or availability (network fork). Nakamoto's algorithm is the first non-licensed, BFT consensus algorithm, and all of these algorithms choose availability over consistency. There are many consensus algorithms in the Nakamoto family.

Leslie Lamport's Paxos algorithm is the first in a family of classical consensus algorithms that favor consistency rather than usability.

In Paxos and many other algorithms from the family of classical consensus algorithms, each node participating in the consensus must communicate with each other verification node in the network for each status update. This makes the communication complexity O(n^2) (where n is the number of verifiers), which means that the time required between each status update will grow exponentially as the verifier increases.

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

Tendermint, like the Sakamoto consensus, bundles time and status updates, so either increase the block size or reduce block time and throughput will increase. When Bitcoin was born in 2009, the block time of about 10 minutes was reasonable. However, from then until now, bandwidth has grown exponentially, which allows Tendermint to reduce block time to a few seconds.

Bifurcation is impossible because Tendermint prefers consistency. Block time can be reduced until the network throughput of a given number of certifiers reaches the limit of the system performance bottleneck. Today, Tendermint allows the network to securely limit its number of certifiers to 100, which filters out nodes with poor bandwidth and allows for larger blocks.

Tendermint is running. Cosmos Hub is the first Tendermint instance to go live with a block time of 6 seconds and a block size of 150kb, allowing a maximum throughput of 100TPS (assuming a single transaction of 250 bytes). However, it is only a few months old and it will quickly mature.

A Tendermint network, if 5 seconds of block time, 5MB block size, it can theoretically reach 4,000 TPS (Blue Fox Note: (5 * 1024 * 1024) / 250 / 5 = 4194.4, about 4,000 TPS) At the same time, compared with Bitcoin, the sacrifice is minimal in terms of anti-censorship and no-licensing, especially considering that it has 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 a detrimental effect on the system's anti-examination and non-permitted attributes. Larger blocks will inevitably take longer to propagate within the network, and the verifier will take longer to verify, so that a lower limit is set for the time of the block.

To increase the clock speed, the number of verifiers needs to be greatly reduced, and they all need to be directly connected to the same fiber network. This will increase the likelihood of verifier collusion, increase the entry barrier for new certifiers, and make fiber network operators a central point.

The next generation of blockchain consensus evolution has taken an important step in the resolution of time and state, with a huge increase in throughput, but at the same time it has also incurred huge costs.

Slice + time chain = independent clock

With BPoS, Tendermint tied the anti-censorship and certifier numbers, which allowed the network clock to tickle once from 600 seconds to 5 seconds, greatly improving performance. However, between clock ticks, the entire global shape is still locked to maintain a globally consistent state.

One way to alleviate this problem is to divide the global state into a bunch of smaller segments, each with its own independent clock, which can advance transactions independently of each other. (Blue Fox note: that is, sharding) As long as these shards do not need to interact with each other, the performance of each shard remains unchanged, and the cumulative throughput of all shards increases with the number of shards. Linear increase.

Cosmos envisages that there are many independent blockchain networks in parallel that can pass values ​​to each other, but most transactions take place within their own systems. If each network can handle 4,000 TPS, with 13 separate networks, the system as a whole can surpass Spanner's performance, reaching 52,000 TPS. However, there are two problems with this approach:

1. The security of the PoS blockchain is measured by the cost of obtaining a 33% collateral token and approving invalid transactions. If there is not a single token supply and there are 13 separate networks, the cost of acquiring a 33% collateral token for a given network will be greatly reduced. This is not only far from being safe, but it also seriously damages the value proposition of the blockchain, where security is an attribute of network value.

2. The TTF used for inter-network transmission is increased by at least 4 times compared to intra-network transmission. The network must communicate back and forth to synchronize their clocks and ensure that if Alice is sending tokens to Bob, Bob successfully receives the value in his network before Alice's tokens are burned on her network.

Although Cosmos envisions a world with many independent networks that are inherently secure, Ethereum 2.0, Poca, Algorand, etc. are building systems to address the shared security issues mentioned above.

Each team's solution has subtle differences, but the basic architecture involves a single beacon chain that clocks the rest of the network while simultaneously re-shuffling the verifiers across the shards, thereby You can share a common security pool. Similar to Cosmos, increasing throughput is easy: just add more slices.

(Ethernet 2.0 single-chain and fragmented state)

Unfortunately, the second problem, the high TTF problem between networks, still exists. Even though the beacon chain can provide a global clock, each slice only periodically synchronizes the local clock with the beacon chain. In order for Alice to send tokens from slice A to Bob of slice B, the verifier of slice A must prove that they have burned before the verifier in slice B dug up the same amount of tokens to Bob. Alice sent Bob's token. According to the current design of Ethereum 2.0, the process will take 6 minutes, 60 times the time across the tile.

While sharding can help, the basic scalability limitations are still predictable because the time and status updates for each shard are coupled. Given the block size and block time, each slice is still subject to the same limitations that Tendermint faces.

Fragments are similar to certain elements of TDMA; states are divided into separate slices with their own independent clocks in a manner comparable to how the tower divides its bandwidth into independent radio frequencies and time periods. The benefits of this approach are obvious, but they are not fully utilized. For example, there is a delay across the shards to prove this.

But what if the time and status updates are completely resolved in an unlicensed environment?

Separate time and state

So far, we have discussed how Nakamoto has created a time-chain data structure to provide a trustless clock for the Bitcoin network; discusses how Kwon and Buchman apply BPoS to the Paxos consensus algorithm to safely reduce the verifier. Counting and speeding up Tendermint's network clock; it also discusses dividing the network into multiple shards with independent clocks, which can greatly increase throughput (as long as cross-sharding transactions are minimized).

However, each of these advancements, their state updates and time are still coupled, state updates only occur with the tick of their network clock, and this creates a fundamental limitation on throughput, the ultimateity for anti-censorship Time, a computing network that does not require a license.

Separating time and state requires a globally available clock that is fast, accurate, and minimizes trust. With such a global clock, state updates can be made continuously and asynchronously, as Spanner did. As long as everyone agrees to the global clock and the transaction is time stamped, the transaction can continue to flow between networks.

Solana builds a trust-minimized clock for its smart contract platform by separating the hash-based time chain from state updates. Instead of linking the hashes of each block together, the verifiers in their network continue to hash the hashes themselves within the block. This mechanism, called PoH (Proof of History), generates a globally available, minimally trusted time chain for all nodes in the network.

(How does PoH weave standardized timestamps into blockchains)

The existence of an independent time chain allows the leader to broadcast to the committee as soon as possible when a time stamp transaction is received. Timestamps provide a canonical order, not an order arbitrarily determined by the block producer. The double flower problem is now easy to solve because the entire network is able to agree on the order of transactions.

This changed everything.

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

Instead of waiting to listen to acknowledgments from every other node (as is the case with other blockchains), Solana can use a new fan-out mechanism to keep the communication complexity O(log(n)). Not O(n^2), it is called Turbine, and is inspired by BitTorrent. This allows Solana to process more than 50,000 TPS in a single global state with fast end-of-life and no fragmentation.

This means that the verifier pool size is comparable to Tendermint, on the order of 100-1000, but allows the chain to fork. A proactive fork management policy is required to ensure that as soon as the chain forks appear, the system is quickly merged into a single chain, which is a necessary trade-off between asynchronous processes and continuous availability.

Comparing wireless communication to a complete loop, the meaning of PoH for blockchain is like the meaning of TDMA for cellular networks. Think of Solana's 1000 certifiers as radio towers, using their synchronized clocks to subdivide their bandwidth into time periods.

They continuously receive the latest transactions, each with a signed PoH hash attached by the sender and forwarded to the neighbor nodes, which can immediately sort the transactions using these PoH hashes.

Since the leader's rotation is based on the global clock, each leader selects an ordered set of transactions to execute and sends the "entry entry" to the network. The verifier returns their vote for each "entry" and confirms the finality of the transaction when they see that 2/3 of the majority of the verifiers agree.

The network as a whole continuously processes transactions and processes transactions in the same order with high capacity. However, each verifier is handled independently. This is a subtle and profound change compared to other blockchains. At Solana, the verifier will never stop processing transactions, regardless of their network conditions and consensus.

There are other related issues that are not very important, such as rapid chain growth, new programming models, unbiased timelines, parallelism, etc. This new design has many issues beyond the scope of this article, which are answered in the Solana documentation. . Currently, Solana's test network consisting of 200 certifiers on five continents handles transactions over 50,000 TPS with an average TTF of 1.5 seconds. This is basically comparable to Spanner, but it has more substantial decentralization.

It is possible to achieve this level of performance in a world of computers with minimal trust and no license, because Solana separates time and state. The globally available clock for the Solana network allows each node to update state without having to communicate 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 addressed distributed clocking issues. After years of PoS research, Tendermint+BPoS is finally the best result, and many fragmentation schemes basically surround the beacon chain + state fragmentation architecture, while the granular time chain that allows asynchronous state updates will be non-sliced. The system provides the best performance, and these systems prefer availability for consistency.

Providing a globally available clock allows the Solana team to take advantage of more than 40 years of distributed system research that would otherwise be unusable. Concepts like OCC (Optimistic Concurrency Control, Blue Fox Note: aka Optimistic Lock) were invented in 1981 and have been used in large computing projects for many years, but when time and state must advance simultaneously It cannot be applied.

Parallel processing with GPUs has been around since 1995. But until Nvidia released the CUDA development environment in 2007, it was basically limited to graphics cards. However, it cannot be fully utilized by the blockchain system, and the blockchain system pessimistically locks all states except for the account that is processing the transaction.

Understanding the passage of time is critical to understanding the performance of distributed systems in licensed and unlicensed environments. Time is everything, a new way of coding time passing through the form of PoH (Proof of History), a system that does not require a license comparable to the performance provided by a proven centralized cloud computing.

——

Risk Warning: All articles in Blue Fox Notes do not constitute investment recommendations . Investment is risky . Investment should consider individual risk tolerance . It is recommended to conduct in-depth inspections of the project and carefully make your own investment decisions.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!