Breaking through the blockchain is impossible triangle (1) – expansion, expansion, and infinite expansion

Written in front of the words:

I have been thinking for a long time, plus the changes in my recent work, this has dragged on for a long time, hesitated, decided to combine this with my own research, to write a hot topic in the field of blockchain – expansion and block Chains are impossible triangles.

I have read many articles about scalability and impossible triangles, both Chinese and English, and even some well-known authors or well-known research institutions, but none of them can fully explain this problem very accurately. Too little to say, there are always a few words in every article that will make me frown: "Wait awkwardly written here." So, I decided to explain this problem in detail with a series here.

So, why is this better than the others?

In fact, the scalability of the blockchain, which is the problem of impossible triangles, is the main direction of my previous research, and what I have always wanted to write. However, in fact, I have been thinking about it for a long time. The main reason for hesitation is that I personally contradict the behavior of holding private goods in popular science articles. In my answer, I will try to distinguish the parts of popular science and personal opinions, and if I want to write a popular science article, I Write more neutral and more tested content, and try to avoid innovative content that is still controversial or not peer-reviewed. Moreover, since it should be said that the current status quo in the field of blockchain is that most people engaged in science and media are not professional enough for blockchain technology, and most professionals are more or less stakeholders, so this The positioning of the column is to create an original technical column that has no “professional perspective of interest.” Therefore, I have been deliberately trying to avoid becoming a “stakeholder” and losing the neutrality of science. (Of course, this is completely personal. Choosing the problem, some blockchain practitioners have done a good job of science.)

• Market Analysis | BTC shocks upwards, is the adjustment over?
• Andreas Antonopoulos: Bitcoin expansion cannot be done once and for all
• Babbitt column | Yuan Yuming: VPIN application in high-volatility market

For the above reasons, I have never introduced my own research and results in my column. On the one hand, the previous results have yet to be perfected. On the other hand, I am also worried that the introduction of immature arguments is contrary to this column. Positioning. However, I finally considered the reason for writing this thing now, mainly because my paper " VAPOR: a Value-Centric Blockchain that is Scale-out, Decentralized, and Flexible by Design " on the just-concluded Financial Crypto 2019 Officially published, therefore, I feel that now I have more confidence to write a question about the impossible triangle, and also introduce my own solution to this problem.

In order to prove that I really have a say in the field of blockchain scalability, I might like to introduce some of my work here:

My first paper on the infinite expansion of the blockchain Implicit Consensus: Blockchain with Unbounded Throughput uploaded arxiv in May 2017, which is one of the earliest papers on scale-out, if the time of submission, In fact, two days before the omniledger, the earliest infinite expansion program, was uploaded. But in fact, there is nothing to say, because it is not officially published in academic conferences or journals. Moreover, from now on, it seems that the idea is not very mature, and the reason for the infinite expansion is not written. Another partial implementation of this article, published in IFIP Networking 2018, is called A Blockchain Consensus Protocol With Horizontal Scalability.

Later, I abstracted the consensus part of this article to a more rigorous proof, and proposed the concept of Spontaneous Sharding (autonomous sharding) and made a laboratory simulation to prove the possibility of infinite expansion, namely: A Scale- Out Blockchain for Value Transfer with Spontaneous Sharding . The paper was published on the Crypto Valley Conference on Blockchain Technology 2018. The conference is said to be the first blockchain conference of the IEEE. Although it is a new conference, its influence is far less than that of related fields. The name sounds very cottage, but this is indeed a serious academic conference, and the review is very strict. The technical committee seems to be an all-star lineup (the chairman includes Professor Emin Gun Sirer of Cornell University), which is also my time. The reason for this meeting.

My main job in the second half of last year was to abstract the reason why this consensus algorithm can reach infinite expansion. For this reason, the concept and theoretical structure of the "Value-centric Blockchain" was proposed and demonstrated. This kind of structure actually realizes "value transfer", in other words, the basic function of virtual currency, has many advantages over the structure of traditional blockchain, and most importantly, it should naturally be infinitely expanded. The paper was eventually received by Financial Cryptography and Data Security 2019 (FC2019) at the end of last year and was published on February 20 this year, the one mentioned above.

Here I will talk about FC. Regarding FC, perhaps people in the field of non-cryptography or even non-application cryptography sound strange, and the ranking in the Chinese Academy of Sciences is only C (I later learned that there is also the Chinese Academy of Sciences ranking…). However, this conference is one of the prestigious top conferences in the field of applied cryptography. And if you want to be specific to the "blockchain" that has just appeared in the academic world, then FC should undoubtedly be the top of the blockchain field. There are two reasons for this. One is historical reasons: FC was one of the first conferences to start accepting papers on bitcoin and blockchain, and it was the first meeting to join the Bitcoin workshop (compared to the two years of the year). There are quite a few conferences in related fields that have joined the workshop on blockchain. FC joined Bitcoin Workshop as early as 2014. Many important papers on bitcoin are published in this conference or on BW, such as selfish mining papers. , consensus algorithm Ghost paper, on the scalability of the position paper: On scaling decentralized blockchain and so on. The deeper reason for this is because the research field of the participants of this conference is highly coincident with the digital currency, so these people have become the first scholars to accept and start researching bitcoin in the academic world. The popularity of the blockchain has risen to become the hottest research issue in the field of financial cryptography, and it is virtually impossible to define which papers should be published in the main meeting and which should be published in BW. Therefore, the organizers have incorporated BW this year. The main meeting. The second reason is in fact complementary to the first reason – so far, FC (and BW) technical committees can be said to be the world's best people who understand the blockchain, and that is why For papers on blockchain, FC is the meeting that receives the most objective and meaningful reviewers' opinions, and is also the place where academic contributions on the blockchain are most easily found and recognized.

This is the website of FC2019: Financial Cryptography 2019

Back to the topic: Scaling and Scaling and Scalable and Scalability

These concepts are undoubtedly hot words in the blockchain field, but if you are a rigorous scholar, or you just like to ask questions, you want to really find out frequently from the media or white papers and even the papers. What is the meaning of Scalability and Scaling? I guess that 80% of you will be mad, because the scaling in many papers is not a single thing. But if you happen to be not an English reader, then this confusion may be exacerbated, because scaling may be turned into expansion or expansion in different contexts. In short, the three words mentioned in the title do not have any exact definition in the blockchain domain. They may have different meanings in different contexts. Even in some white papers, the word may not have any meaning. In other words, when you see "this is an extensible blockchain" or "solve the scalability problem" or "extensible consensus algorithm" on the white paper, without context, You don't know what it means at all.

The reason for this situation, I think, is because the blockchain itself is an area that is not strictly defined, and Scalability has different definitions in various fields. Therefore, when people in different fields come to define according to their own ideas. The problem of Scalability, without a co-recognized authoritative paper or textbook that makes a definition that everyone agrees on, becomes what it is now – everyone can say from their own perspective that their system is expanded. And then, because most people have a hard time understanding the difference between these different schemes about scalability, so many overviews, popular science, and media texts confuse the various extensibility and confuse this confusion.

The first definition of extensibility – scalable POW

Let's talk about what is scalable (scalable). Without any limitation, this refers to the change of a certain performance x with the growth of a certain variable y. If x can grow linearly with the growth of y, we will say that x is linear scalable, or simply Said to be scalable. In other words, if we set a very high target x, if we know that "this kind of thing we only need to use a f method, and then y can be achieved by stacking up", then we say that the f method is scalable.

Then, long ago, people realized that Bitcoin was not scalable – because it wanted to improve Bitcoin's 7TPS, especially if it wanted to increase it to output comparable to traditional payment methods, such as 10,000 TPS. We can do very little. The most natural way is to increase the block size, or reduce the block spacing, because even without rigorous mathematical analysis and proof, people know that this is impossible, because if the block is increased 1000 times to a G then A block of ten minutes, not to mention anything else, is that the speed of the network at that time is not allowed.

However, in fact, restricting the block size and block spacing is far more than the network speed of the transmission block. For quantitative analysis, you can refer to the paper on On Scaling Decentralized Blockchain mentioned above, and the qualitative explanation is –

In Bitcoin's POW algorithm, security relies on the premise that the block synchronization speed is much smaller than the block interval.

The premise of Bitcoin's security is – assuming all miners are profitable, then anyone who wants to cheat needs to lose 50% of the power, because you have to have more computing power than others to dig out A chain longer than others. However, the premise that this competition is fair is that the cheater and everyone else are digging the same chain, that is, the whole network is synchronized for most of the current longest chain. However, for Bitcoin, this is not necessarily the case. This is also the place where the POW of Bitcoin is different from the algorithm of the traditional distributed system. Bitcoin allows short-term inconsistency in the network, that is, bifurcation, that is, two different nodes in the network think of two different ones at the same time. The chain is legal. At this time, if a malicious node wants to dig out the longest chain, he no longer needs to compete for everyone else. Assuming that two chains in a fork are each accepted by 50% of the calculation power, then at this time a malicious node can have more than 50% probability to dig into the next block as long as it has more than 25% of the computing power. So, if there are always two forks in Bitcoin, we can actually think that the security of Bitcoin has dropped by half.

You may not understand it when you see it here – bitcoin is not very bifurcated, and the general fork will soon disappear? Why is there a situation where "bitcoin is mostly forked"?

Here, everyone thinks about how the fork appears. When A digs a block, A will announce the block to the whole network as soon as possible. The more people know, the more people will continue to mine in the back. So the chain is more likely to be longer than others, so the probability that this piece will eventually appear on the longest chain is higher – and in Bitcoin, only the longest chain is the end result. However, if this piece of A has not been received by another point B in the network, B also digs a piece, and B does the same thing without knowing that A has dug this piece, so A fork is created, and the network is split into two parts. If you first receive the block of A, you will think that the chain of A is more promising, and continue to dig later, and vice versa. In the current bitcoin network, a block is 1M, and the transmission and verification are relatively fast, so the time required to synchronize a block to the entire network is very short, only when two nodes are dug at the same time. Blocks can only be forked. Therefore, if the delay is much smaller than the block interval, the probability of the fork will be small, and the probability of a few consecutive forks will be smaller, so the high probability fork will end after a block, leaving a A lone block of depth 1. And if we increase the block size, or shorten the block interval, so that the ratio of the time of the sync block and the block interval is not so disparate, then the time required for synchronization will become longer, so the possibility of bifurcation Will increase. And if the sync block time exceeds the block interval, then the number of forks will never decrease, but will be more and more.

As the block size increases, the block transmission delay increases, so the increase in the block delay/block interval ratio leads to an increase in the probability of bifurcation in the network. Similarly, reducing the block spacing will also produce the same result.

And if there is always a fork in the network, it is difficult to converge, then there is always someone who does not mine in the final longest chain, so the security of the whole network can not reach the 50% level of POW theory; If you can't converge, it's not just a drop in security, but a transaction can never be confirmed.

The latter is not limited to the Bitcoin POW algorithm, but can be said to be a problem that the blockchain cannot be triangular or the distributed system CAP. If the network speed cannot keep up with the block propagation speed, this system is impossible anyway. Guaranteed to be consistent.

But the former is a limitation on the Bitcoin POW algorithm.

From this perspective, Bitcoin is not scalable – because its output cannot be infinitely increased before the boundary of the Internet speed is increased with the expansion of the block size (reduced block interval), but the bit is touched before that. The currency POW algorithm's own security is bounded by synchronization.

So, from the same perspective, we want to improve Bitcoin's POW algorithm so that it can get rid of the dependency of security on synchronization, so that we can simply improve by increasing the block size (reducing the block interval). Output until the boundary of the network speed is encountered. This kind of attempt, we call it "Scaling Bitcoin", and such an algorithm can be called "scalable POW algorithm" because In the bitcoin POW, they are more scalable from this perspective.

Such algorithms are for example Bitcoin-NG, GHOST, Hybrid Consensus and the like. Then, scalability at the same level also includes POSs such as Snow White and Ouroboros that use the Bitcoin-like POW structure, which we will cover in more detail in the next issue.

The second definition of extensibility – unlimited expansion

Seeing this, the extensible definition seems to be no controversy—in fact, when there is no blockchain in the beginning, only bitcoin, when it comes to scalability, is the first definition.

When did the word "extensible" start to have a new meaning?

Probably starting with the research of bitcoin from the people of traditional distributed systems…

In traditional distributed systems, the definition of scalable is usually whether the output of the system can increase linearly with the number of nodes, if it is scalable, or horizontally scalable. So with this definition, if a blockchain system is scalable, then if he has 1000 nodes whose output is x, then if we add 1000 nodes, the output should become 2x. For example, if you double the bitcoin network, then TPS should double.

However, as mentioned above, Bitcoin does not have this property – the Bitcoin algorithm determines that its output is 7TPS.

Therefore, Bitcoin is not scalable.

However, this actually brings up a problem – from this point of view, even the extensible POW in the first definition is not scalable, even though until now, almost no blockchain is scalable, in fact It is also well understood that in a linear scalable distributed system, the reason for adding a corresponding server for each additional server is that the newly added server can independently undertake some tasks.

The blockchain is different from the traditional database. It almost certainly needs multiple nodes to store the same data to a certain extent (the traditional distributed database is called a live, redundant design), otherwise it loses the center. The meaning, so, certainly to some extent, it can't achieve the effect of how much output is increased by a few more nodes. Unless it has to make certain security sacrifices, or credible assumptions, and this is always the "blockchain impossible triangle" that people are relished.

Therefore, many people criticize the pursuit of this scalable – they believe that the sacrifice of security and decentralization and blind pursuit of high output, lost the meaning of the blockchain.

However, even so, the attractiveness of high output is huge – after the blockchain appears, people always benchmark the blockchain against the Internet, and always benchmark the public chain to the future Internet unicorn. However, if the blockchain does not achieve such scalability, its output will eventually be subject to the network, which is nowhere to support the scene of the Internet Unicorn. In order to distinguish this extensibility from the previously described extensibility, in the context of the blockchain consensus algorithm, this is called scale-out, ie infinite expansion.

In general, there are two types of methods that can achieve unlimited expansion. The underlying technology and fragmentation, the former is not in the framework of the impossible triangle. From my point of view, more is a kind of district. The blockchain acts as a trusted intermediary, and then according to different applications and scenarios, and then considers the characteristics of different blockchains, proposes a chain-based solution that can be borrowed from the blockchain. For example, the chain payment channel is actually a mapping of the stored value card solution for small-value high-frequency transactions in the blockchain scenario. In theory, the biggest difference between the under-chain technology and the chain is the consistency in the BFT (see the previous article). The chain technology requires a consensus algorithm to ensure the consistency of the transaction (although it may need to be in security or on the center). Compromise), and the consensus consensus algorithm for transactions in the underlying technology itself does not matter, but depends on the design of the underlying solution itself and the negotiation of the two parties according to the scenario.

However, in academia, the term scale-out is usually not used to describe the algorithm under the chain—because as I said before, the algorithm under the chain is naturally scale-out, so there is no need to use it to describe it. Therefore, generally speaking, scale-out is a fragmentation algorithm, and algorithms that can be attributed to this class include Omniledger, Chainspace, and

@王嘉平

The teacher's Monoxide, as well as the Ethereum segmentation and Rchain of the partial project, my program VAPOR seems to be fragmented from the results, but the principle is different. These, my last part will be detailed.

From this perspective, the two seem to be very similar to the two other concepts that are very hot, namely the definition of “second layer (sub-chain expansion)” and “first layer (chain expansion)”, but in reality, The concepts of the first and second layers are not from the perspective of the infinite expansion we are considering here, but from "do you want to change the main chain algorithm" or "is it through the chain mortgage to move the transaction under the chain? "This angle is defined, so, in fact, in addition to sharding, many can't reach "infinite expansion" but only "expandable", that is, our first definition and the third definition we will talk about next. The scheme is also known as the first layer scheme.

Among them, the most likely confusion is the DAG (Directed Acyclic Graph). Due to the propaganda of some DAG projects and the misconceptions that many people have made about the intuitive impression of DAG structure, DAG is juxtaposed with shards in many review articles, which is considered to be infinitely extended – however, DAG is just a concept, and DAG There are many methods for blockchain, such as GHOST, BLOCKDAG, SPECTRE, PHANTOM, Swirld Hashgraph, IOTA, Byteball, Conflux, and the like. Although DAG theoretically has the possibility of infinite expansion, none of the current DAG schemes with specific algorithms (there is no concept of light), none of them are infinitely extended, but are only extensible.

The third definition of extensibility – scalable BFT

Now, if the first class of extensibility is called "extensible" and the second class is called "infinite extension", it seems that there is no ambiguity in the word "extensible".

However, in fact we still have a third concept, which is the BFT class algorithm I introduced earlier.

In my previous articles, I focused on the Byzantine fault tolerance problem and some important Byzantine fault-tolerant algorithms. Among them, we introduced an important Byzantine fault-tolerant algorithm PBFT (Practical Byzantine Fault Tolerance), and also introduced its message complexity is O ( N^2), that is, to reach a consensus on a message (a transaction), you need to first broadcast the message to each node in the network (O(N) message complexity), and then in order to prevent malicious nodes from cooperating with malicious messages. The publisher intentionally spreads the fake message in the network and causes inconsistency. Each node needs to broadcast the message it receives again, so there is O(N^2) message complexity.

What is the concept of O(N^2)? We use the concept of scalability to analyze – assuming that the bandwidth of each node is c, then the total throughput limit of the whole network is cN. Then, the concept of message complexity is O(N^2). If you double the number of nodes, the bandwidth of the whole network will be twice as large, but the resources needed to be consumed are four times. In other words, the traditional BFT is not scalable, and it is simply the opposite of scalability. Therefore, the consensus nodes of the blockchain using the BFT algorithm are basically only a dozen or dozens.

I also said in the previous article about BFT. At first, we didn't think that the O(N^2) message complexity was a problem, because first, they didn't consider practicality at first, and second, even if there was PBFT is only considered for use in more secure distributed databases, and does not take into account the large network scenario of blockchain.

However, when the blockchain appeared and people began to re-examine the BFT, the O(N^2) message complexity was completely useless. So, people began to consider the BFT algorithm that is more "scalable" (you see, this is the word), the BFT algorithm of O(N) message complexity. There are many such BFT algorithms, including Honeybadger, Byzcoin, Hyperledger- Iroha, Elastico, and even the BFT parts of Algorand and Avalanche fall into this category. They are indeed "blockchains that use (more) scalable BFTs," however, when there are places that simply emphasize their advantages, they say "extensible" or simply call them "expandable." The blockchain is mixed with the first class of extensible POWs. Although, we will introduce later, the actual effect of the two is the same. However, if you want to understand this problem more deeply, you need to know that the extensible POW and the extensible BFT have different origins.

Scalable 3.5th definition – Bitcoin expansion

In addition, there is a Category 3.5 extensibility, which is a bitcoin expansion scheme – such as large blocks and isolated witnesses.

The reason for the 3.5th category is that from any point of view, they only improve some of the output, and there is no solution to the scalability problem. However, the expansion of English itself is also scalable, and historically, these two programs are indeed the first step in the expansion, because –

Large block –> more forks –> GHOST –> expandable POW

Segregation Witness–>Resolve Bitcoin Variability Issues–>Easy-Lite Chain Implementation–>Infinite Extension

So, from this perspective, it is understandable to say that the two options extend Bitcoin – but in the end, the real upgrade on Bitcoin will only stay on this first step.

Relationship between different definitions

Seeing here, is it that many people who thought they had already understood the scalability problem felt that their brains were more chaotic?

Do you have to know what is the origin of this thing if you want to know what is an extensible blockchain? Is there a simpler way to see what it is supposed to do when you see the "extensible blockchain", and what is its performance?

It’s actually very simple –

First of all, there are only two options for the 3.5th category. Large blocks and segregated witnesses can be excluded first, because these two programs will basically only appear under the name of “expansion”, and only very unprofessional places will use “expandable”. "To get it in comparison with other scalable algorithms."

Secondly, at present, it can be advertised as "infinite expansion", and basically will not introduce itself as "expandable". If there are still questions, just remember that fragmentation and sub-chain technologies should not be compared with other "scalable" solutions because they are more scalable, ie in large networks. The output is higher, but there are some compromises in security or centralization. The more basic difference is that looking at these algorithms to ensure consistency, is it required that each node record every transaction, and if so, the message complexity is at least O(N), so when nodes are added to the network At the time, the output must not increase. And if you want to expand indefinitely, there must be some transactions that do not need to be broadcast to the entire network.

Then, all the remaining scalable algorithms, the first and third in our definition, are ultimately the same, reaching the same scalability, namely O(N) message complexity. Then, the output of both ends will only be constrained by the network speed and response delay. Finally, the better algorithm is probably in the laboratory environment, reaching the order of 1000 TPS, and ultimately it will depend on the strengths and weaknesses of the algorithm. The degree of optimization achieved, but the delay of the large network simulated by the laboratory environment is actually much better than the actual level, so in reality, as the network expands, the output does not increase with the increase of the number of nodes is a wonderful imagination. — The output will almost certainly drop as the network grows.

The most confusing of these is the DAG, but in this type of algorithm, we have already introduced it before, whether it is the industrial IOTA, the Swirl Hashgraph is still the academic Phantom and Conflux, whether in some media or articles, or How do they introduce them in their own white papers, remember that they are strictly "extensible" consensus algorithms, not "infinite extensions" .

In the next article, we will highlight the scalable solutions in the first and third definitions here, their commonalities and the challenges they face today. Later, we will introduce some DAG algorithms and fragmentation algorithms, and finally introduce my own work. This time, I will try to update as soon as possible…

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