Want to get the blockchain out of the chain of time? A brief history of the time to read the blockchain together

The significance of time for distributed ledger technology is self-evident. Any book needs to be "ordered". In a clock system with separate time and state, time and state are not coupled, and the timestamp of the chain transaction will be Being coded, transactions flow through the network like water.

Solana separates the hash-based timeline from state updates by first providing a license-free, globally available, trust-minimized clocking system for its smart contract platform, and optimizing network operations before consensus is reached. Solana calls this core innovation It is the "Proof of History" (POH).

Written by: Xiao Mao Ge, Special thanks to Dr. Dong Xinshu, the co-founder of RockX, for his review and suggestions.

"Today is August 16, 2019. It is late, and today it is a dull day."

Years, months, mornings, days, and tomorrow are our concepts of time. The time can come from any trusted third party such as iPhone, toy watch, and the most accurate atomic clock. What's important is that we The term "time" seems to be a concept given by a human society. Einstein's general theory of relativity attempts to explore the true definition of time from a more scientific perspective. Of course, people still understand their time with the most intuitive definition of their own.

Counter-intuitively, in a completely open distributed system, because of the loss of a third party that can be completely trusted, it is difficult to rely on the concept of time that is used for several months, early and late to determine the sequence of events. In a distributed system, the "time" we need is not the time granularity we are used to, but rather a mechanism by which we can verify that an event occurs before, after, or at the same time as another event.

Why is time the fundamental problem of the blockchain?

Timestamp concept

Imagine a situation: You read the New York Times on a certain day, and a photo was taken by a reporter. After a few days, you found that your photo was published in the new issue of The New York Times.

Assuming that the New York Times information is correct, because of this coincidence, even after many years, although you have forgotten the date of the photo taken, with this information, you can also accurately determine the date the photo was taken: Between October 12, 2014 and October 14, 2014.

This coincidence constructs a time mechanism, we have established two credible points in time, and the information provided by the New York Times in the case is the timestamp in this mechanism.

As we mentioned above, to determine the context of an event, what is needed is not a trusted physical clock, but rather a time mechanism with a trusted point in time. According to Einstein's theory of relativity, the time in different spaces in the universe is not uniformly synchronized. Bitcoin solves this problem by creating its own concept of time, proving that implementing distributed ledger technology is feasible.

Basic problems in distributed systems: clock problems

According to the original source code of Bitcoin, Nakamoto first described the data structure of Bitcoin, the familiar "Blockchain", as "Timechain".

The significance of time for distributed ledger technology is self-evident. Any book needs to be "ordered". People can't spend the money they don't receive, nor can they spend the money they have already spent. The blockchain technology itself must explicitly sort the ledgers without the need for a third party. Although there are many other technical details in the blockchain, time is of the essence. Without time and order, there is no blockchain.

The American computer scientist Leslie Lamport published the paper "Time, Clocks, and the Ordering of Events in a Distributed System" in 1978 for the first time to compare the timing in distributed systems with the concept of time in relativity and propose a work that can be used for " A distributed algorithm that synchronizes the logic clock's system to globally sort events. In 1982, he published a classic paper on the fault-tolerant computer system, The Byzantine Generals Problem, which is the source of the famous Byzantine general.

The Byzantine general problem is a hallmark problem in the development of distributed systems. For this type of problem solution, the concept behind it is basically the ordering of parallel operations that may lead to inconsistencies. On November 13, 2008, Nakamoto wrote at the beginning of an early letter explaining bitcoin that the workload proof mechanism was one of the solutions to the Byzantine general problem.

How to determine the time and sequence of events is a fundamental problem in distributed systems. Introducing the global clock is one of the ways to achieve Linearisability Consistency in the Byzantine General. The global clock allows a number of mutually untrusted nodes to have a globally synchronized time source, plus a timestamp, which makes it possible to achieve a globally consistent orderly transaction. In order for distributed systems to achieve consistent results of strength and weakness, many blockchain consensuses based on this idea have emerged as solutions.

Globally consistent clock + timestamp = ordered transactions

Understanding time and state – deconstructing blockchain clocks

PoW clock system: workload proof mechanism + time chain / blockchain

In order to understand this embarrassing cryptography problem, we may wish to imagine Bitcoin's PoW workload proof mechanism as a clock, and repeatedly calculate the qualified hash value (ie mining) equivalent to participate in a person can participate and will Go to the clock system that meets the result:

Time value

The significance of time for the proof of work mechanism is to protect the security of the network by continually consuming kinetic energy. We can use "stock & flow" to describe time-based energy and value accumulation, and use the following three formulas to briefly summarize the time value of the PoW clock system:

Time flow / stock = kinetic energy that has been consumed / will be consumed Time stock value (past) = kinetic energy already consumed by mining (general ledger) + inventory value of mining hardware Time flow value (future) = kinetic energy consumed by mining ( Expected ledger) + potential profit from mining hardware

Status update

The status update is actually determined by the block, and each new block reflects a new status. This time chain structure is designed to be averaged every 10 minutes, that is, the PoW clock rotates once every 10 minutes. At the same time, each pointer rotation means that the clock completes a non-backtrackable, memoryless global state update.

Pointer rotation, tick once = Ordered block, status update Tick ​​time = Block time (average about 10 minutes) Speed adjustment = Mining difficulty adjustment Final status update = Longest chain principle

Time and state: tight coupling

In the workload proof mechanism, after a block is generated, the entire chain is locked, and there is no state update until the next valid new block is generated or received. Each new block contains a hash of the previous block as evidence of validity in that block. In short, in the PoW time system, time and state are coupled together, always bound to each other and consistently. Without a status update, time cannot be advanced.

PoW clock system features

The PoW clock system is a groundbreaking solution to the problem of time and state in distributed systems. The PoW system is a secure, mature, unlicensed, globally shared network facility. It is worth noting that the PoW clock system costs are transparent. However, the clock performance and scalability are insufficient, and there is still room for improvement.

PoS clock system: equity proof mechanism + time chain / blockchain

The PoS clocking system combines consensus mechanisms with cryptographic economic incentives, sometimes by limiting the number of verifications to improve system performance. This paper uses the best-performing, high-performance, unlicensed BFT consensus algorithm Tendermint + BPoS (Bonded Proof of Stake) as an example to understand the clock system.

Time value

The significance of time for the proof of entitlement mechanism is generated around the core behavior of the PoS mechanism, staking. We can extend the understanding of the PoW time value system to the PoS clock system.

Time flow / stock = pledge / capital cost to be pledged Time stock value (past) = opportunity cost of pledge funds + pledge cumulative income Time flow value (future) = expected pledge of long-term holders + expected pledge income

Status update

The PoS clock system state is similar to the PoW clock system.

Pointer rotation, tick once = Ordered block, status update Tick ​​time = Block time (Tendermint about 6 seconds)

Time and state: loose coupling

In the proof of rights mechanism, time and state are still coupled. Therefore, the improved idea of ​​the performance of the distributed system is still to choose between time and state, either to increase the block size, or to reduce the block time to increase the performance of the clock, that is, the throughput of the system (TPS), using the formula To represent:

Throughput (TPS)) = block size (txs per block) / block time (block interval)

If the Tendermint network reaches a 5 second block time, the 5MB block size can theoretically achieve a throughput of 4000 TPS.

PoS clock system features

The PoS clocking system has taken an important step in deconstructing the time and state of distributed systems, and has achieved tremendous improvements in system throughput, but at the same time it has also incurred huge costs, such as the length of pledge time around staking. Contains uncertainties that affect the security of the PoS system.

Slice clock system: state slice architecture + time chain / blockchain

Fragmentation architecture, although there are differences in solutions for different projects, the basic architecture basically includes a Beacon Chain, which provides a time source for the rest of the network. The improved performance of this clock system is very simple, that is, adding more small clock systems under the clock system.

Time value

The fragmented clocking system extends the time inventory and traffic of a single blockchain, thereby quantifying and extending the time value

Status update

The beacon chain can provide a global clock of the fragmentation architecture, but each fragment only periodically synchronizes its respective independent clock system with the clock system of the beacon chain. Periodically, the periodic update of the state is required when the slices interact. The time required may cause delays.

Time and state: split the time and state of the coupling simultaneously

The state fragmentation architecture divides the entire clock system into a bunch of separate clocking systems, splitting the global state into a bunch of smaller individual slices, each with its own independent clocking system, independent of each other but propelling together.

The characteristics of the slice clock system

Ideally, if the fragmentation interaction between slices is minimal, the performance of each slice remains the same, and the cumulative throughput of all slices will increase linearly as the number of slices increases. The concept of fragmentation significantly improves system performance, but it is foreseeable that since the time and state of each individual fragment are still coupled, there are technical problems such as fragmentation security, cross-slice transactions, and network communication. The reality of the fragmented clocking system will still be limited by the basic blockchain, including the beacon chain and the scalability of the backbone itself.

Jump off clock frame system: separation time and state

Let's review the clock system discussed above. The PoW clock system pioneered the creation of a trust-minimized clock for Bitcoin. In the PoS clock system, we use the Tendermint + BPoS consensus as an example to illustrate how to reduce the certifier to improve the clock. System performance; the slice clock divides the overall clock system into a single set of clocking systems, significantly increasing throughput.

It is worth noting that all of these clock systems are still built within the framework of time and state coupling and are bound to be limited. It seems that every clock system has its own uniqueness, but it is not perfect. Let us continue to think about ways to continue to optimize the blockchain clocking system:

  1. Must time be bound to the state?
  2. Can we separate time and state if we can "prove history" and "code time"?
  3. What would this clock system look like if it was technically possible to separate time and state?

First, the clock system still requires a globally available, unlicensed source of time, and state updates can be sustained and asynchronous only under the globally available clocking architecture. Second, to improve communication between nodes, you need to be fast, accurate, and keep trust to a minimum. In a clock system where time and state are separated, the time and state are not coupled, the timestamp of the chain transaction will be encoded, and the transaction flows between the networks like water.

Based on this idea, Solana separates the hash-based time chain from the state update. First, it provides a license-free, globally available, trust-minimized clock system for its smart contract platform, and optimizes network operation before reaching a consensus.

Solana calls this core innovation "Proof of History" (POH). The PoH historical proof mechanism is an optimized solution for network operation before reaching consensus. It provides a new concept of clock. POH acts as a special clock before consensus is reached, allowing various unique timing assumptions such as optimizing data propagation to memory pool management to occur in the upper layer design.

This core innovation opens up a comprehensively enhanced design space. In addition to providing a clock with a time stamp of "coding time", PoH also enables Solana to optimize the block time (800 ms), block propagation (log200(n)), throughput (50K-80KTPS) and available on the network. Ledger storage (petabytes).

PoH clock system: time source for separation time and state + time chain / blockchain

Time value:

The PoH historical proof mechanism provides a new concept of time, which provides a special time source for the clock system, which plays the role of “clocking” and “sequencing” of the clock system, so that the system time is no longer limited by state.

Status update:

PoH history proves that the clock system separates time and state, and state updates are not limited to every hour hand rotation. That is to say, the clock system separates the clock rotation once (time) and ticks once (status update).

Hour hand rotation ∈ Status update Tick ​​time = Block time (800 microseconds for Solana test network)

Time and state: decoupling / separation

Time Dimension: Based on Verifiable Delay Function (VDF) Coded Timestamp A verifiable delay function (VDF) is a type of mathematical function that enables the calculation of the function to take at least a known time. Other blockchains require verifiers to communicate with each other, synchronize information to confirm that time has elapsed, and the next step can be taken, and each Solana verifier can encode a standard timestamp as a verifiable delay function for a SHA-256 sequence hash. (VDF) Enters the blockchain. Solana uses VDF not for randomness, but for maintaining one of the clock systems.

How Solana encodes standard timestamps into blockchains

State dimension: first select the leader, then complete the epoch. Because each verifier needs to maintain its own clock, choose the leader first and make a complete epoch. Rear. Like the Tendermint mechanism, an epoch's timeline can last for thousands of blocks. However, unlike Tendermint, the Solana network never waits for a node to fail validation. Each verifier runs the VDF to prove that it has obtained the block and screed's slot time and is rewarded.

PoH clock system features

1. Shorten the communication interval between nodes. Other blockchains require the certifiers to communicate with each other, synchronize information to confirm that the time has elapsed, and the status can be updated. While Solana's nodes continue to receive the latest transactions, each transaction has a sender attached. The signed PoH timestamp hash is forwarded to other nodes, and the node can immediately sort the transaction directly through the PoH timestamp hash, shortening the communication time waiting for the confirmation of the corresponding node.

2. There is no need to wait for the leader's rotation. Under the POH historical proof mechanism, the leader's rotation does not affect the network. The network can decide the leader's rotation without any certifiers communicating with each other. The network will continue to process transactions as a whole, and the leader's rotation decisions are invoked asynchronously.

3. The new node only needs the data structure to verify the blockchain integrity . One of the common criticisms of the PoS mechanism is that it is not completely objective, but weakly subjective. However, due to the improvement of Solan by SolH, Solana became objective. Because time is also encoded into the block itself over time. At the same time, since the certifier can verify the POH in parallel by 1000 times faster than the initial speed of the POH, a new node can verify the blockchain from the creation without the external information. To the current integrity.

How to continue to optimize the PoH clock system based on historical consensus?

Tower BFT: Leverage the time source of the PoH clock system to optimize the PBFT consensus

PBFT Practical Byzantine Fault Tolerance Bottleneck

Explain what is Tower BFT. Let's first explain the practical Byzantine Fault Tolerance (PBFT). PBFT was born before the birth of Bitcoin. It has been more than 20 years since it was born. It stems from the well-known consensus problem of distributed systems: The Byzantine General.

A group of Byzantine generals besieged a city, they must reach a consensus on simultaneous attack or retreat at the same time, and the generals can only inform others of their decisions through the messenger. However, there are traitors in this group of generals who send out the opposite message or only inform some of the generals. How do you reach a consensus that is correct and usable in the presence of a traitor?

In a distributed system, we can:

  • General as a node
  • Messenger as communication between nodes
  • The decision to attack/retreat is seen as a consensus
  • The general's random behavior is called Byzantine Fault.
  • The characteristic that can still be agreed in the presence of a traitor node is called Byzantine Fault Tolerance.

From the results, a correctly available consensus must ensure that Byzantine generals (ie, nodes) will reach a unique consensus (ie, consistency), and that consensus will eventually form (active).

PBFT Practical Byzantine Fault Tolerance is a consensus-based solution based on the selection of leaders, communication-based, and consistent. Because PBFT contains a communication mechanism that verifiers need to broadcast their votes to other verifiers, communication complexity and communication are greatly increased. Volume, resulting in bottlenecks that are difficult to scale.

Improved consensus algorithm based on PoH historical proof

Based on PoH's historical proof, Solana improved the operation of Tower BFT, a consensus algorithm similar to PBFT. Tower BFT took advantage of Solin's PoH clocks to synchronize time sources before reaching consensus, reducing communication complexity and communication latency.

Unlike PBFT, Tower Consensus tends to be active rather than consistent. As with PBFT, the node multiplies the time-outs to reach a protocol, but since the clock structure of the clock system itself is also a time-free source of trust, the node can observe and examine all other certifiers in the network. Timeout. We can use an example to make it easier for everyone to understand this:

Imagine you are on an island, a bottle drifting over and a U disk inside. There is a Solana book in the U disk. If you only look at the book itself, you will see that each node can calculate the current number of certifiers, the status of each certifier – and, most importantly, each certifier submits to any block in the network. overtime time. Just based on the data structure, without any peer-to-peer information, the certifier can make a voting decision and the network can reach a consensus.

Credentials and Replicators: Two-node division of labor generates lightweight proofs to optimize data storage

The blockchain network currently generates 4 PB of data per year at a rate of 1 GB per second. At this rate, the storage of blockchain data will quickly become the main centralization vector, which runs counter to the decentralized vision of blockchain implementation.

Solana uses two types of node divisions to generate lightweight proofs that make it more efficient to run on PoS networks.

  • Credential node: Responsible for verifying network data, but PoH history and Tower PBFT help it speed up verification.
  • Replicator node: Gets calculated weights from the certifier node and operates with minimal hardware requirements.

Replicators have low hardware requirements, and all of our daily laptops can execute. However, the role of the replicator node in the network is important to optimize the distributed data storage system to address data availability issues with multi-megabyte (pb) data.

Solana's replicator nodes do not need to participate in consensus and store the entire data history. Instead, they use multiple replicator nodes to store small pieces of data history separately to generate lightweight proofs and perform erasure code functions, thereby making the entire state history Split into many parts. Every once in a while, the network asks the replicator to prove that they are storing the data they should store.

The proof of replication (PoRep) used by Solana is based primarily on Filecoin and uses the timing source provided by the PoH Consensus to create a proof of replication (PoRep). The Replicator node will use PoH historical proof to generate lightweight proofs without participating in the consensus, which will replicate the various parts of the ledger and allow the verifier to be cross-GPU-verified across the GPU.

Conclusion

Understand the meaning of "coding time" and reshape the blockchain Layer 1 scalability

By separating time from state, Solana proves that it is possible to achieve a minimum trust and no need to license the world's computers. In this article we explore the innovations of three Solana:

  • Proof of History (PoH): Solana's other unique architectures are based on PoH. PoH provides time source before consensus, plays the role of timing and sequencing, solves clock problems and reshapes blocks. A deep and ingenious solution for chain expandability.
  • Tower BFT: Optimize the PBFT consensus by leveraging the time source of the PoH clocking system.
  • Replicators: Use PoH historical proof to generate lightweight proofs to optimize distributed data storage.

Understanding the performance of a distributed system from the "time dimension" is essential, time is everything, and the new thinking of "coding time" is proven by PoH history. Unlicensed distributed systems can even be comparable to verified centralized cloud computing. performance.

Currently, Solana's test network consisting of 200 certifiers on 5 continents has a throughput of over 50,000 TPS and an average TTF of 1.5 seconds. This is basically comparable to the best global distributed database Spanner, but Solana is more decentralized.

At the same time, the scalable Layer 1 underlying network with simple logic and minimal trust actually logically abstracts the complexity, allowing future developers to focus on the application logic. The scalable solutions and optimized application scenarios that will be expected to be left to Layer 2 actually increase the complexity and friction of users, developers and service providers.

When Vitalik unveiled the Ethereum in January 2014, he emphasized this: the meaning of the world's computers is to abstract everything that is not application-specific. Over time, on August 21, 2019, Vitalik issued a message on Twitter saying that it is pessimistic about the layer 2 chain expansion scheme, because there are many application layer treatments for the incentives, and it is difficult to apply on a large scale.

For most use cases, developers built on the Solana blockchain do not need to consider scalability at all, because the meaning of Solana layer 1 lies in the abstract complexity, in which the optimization of the upper layer 2 design, the author will The next article discusses this layer of logic in detail.

Reference article

Blockchain Proof-of-Work Is a Decentralized Clock Work is Timeless, Stake is Not Bitcoin, Stock & Flow Classics that can't be ignored if you want to understand the blockchain: PBFT It's the settlement assurances, stupid Vitalik Buterin reveals Ethereum at Bitcoin Miami 2014 Introduction | Ethereum 2.0: Beacon Chain Bandwidth and the Blockchain Reshape the Blockchain 's Scalability: State and Time Separation I understand the verifiable delay function VDF can't be ignored if you want to understand the blockchain: PBFT Cryptography Mailing List Bitcoin P2P e-cash paper