Breaking through the blockchain is impossible triangle (2) – an attempt on top of Bitcoin POW

The recent rise in Bitcoin seems to remind everyone that Bitcoin seems to have a vigorous vitality after ten years. This is a very magical thing from the perspective of software and information technology – the same product from 2009, Windows 7 has entered the final time, iphone 3 has long since disappeared, and Many of us are now accustomed to it, as if things that have existed long ago, such as millet, such as ipad, or even WeChat, have not yet been born.

However, in fact, whether it is ipad or WeChat, it is not the same as it used to be. But bitcoin doesn't, from performance to function, it's just a little prudent improvement in functionality compared to the original version. The reason for this is that although there is a decentralization of the blockchain itself, there are also political and route disputes mentioned in the first part of the column of the column, but the bottom line is that –

The POW design of Bitcoin is actually very subtle.

I personally don't think this is what Nakamoto is interested in, or that Nakamoto is very clever about the design of the POW, but because of his non-class background (see my answer to his analysis of identity)

• The second phase of the fire coin Prime project led the disputed person to claim that two exchanges were “strong”
• After entering Ali and receiving the stock market crash, "Hang Seng Electronics" "Sword Finger" blockchain
• The transparency of the Ethereum Foundation raises questions and the official weak response

Https://www.zhihu.com/question/305973025/answer/628460658

Https://www.zhihu.com/question/67192203/answer/251020050

He can't use rigorous mathematics to prove the validity of this algorithm. However, he needs the simplest logic to convince himself and others that the algorithm is indeed effective. Therefore, he gives the algorithm enough redundancy. For example, a 10-minute block interval allows the reader to intuitively believe that "this time is enough for everyone to synchronize this block" without tangling what happens if this assumption is not true.

So, this is the ingenious place of the Bitcoin POW – its algorithm is extremely simple, simple enough to be convincing its feasibility without the need for rigorous inference and proof. But on the other hand, it can't help but think about it – there seems to be so much room for improvement here, as long as it is modified, you can…

However, most of the brain-improving solutions for Bitcoin actually introduce additional mechanisms that ultimately prove to introduce additional security risks—because, in fact, the mechanism of Bitcoin, though simple, It is precisely in line with the basic principles of information security – the more complex the mechanism, the more error-prone.

For this, Zhang Ren’s paper has a very wonderful discussion.

Https://www.esat.kuleuven.be/cosic/publications/article-3005.pdf

Of course, this does not mean that the POW of Bitcoin has no room for improvement. On the contrary, the space for POW changes is quite large, but the person making the change needs to know what he is changing, or rather, very small. The changes will cause some chain reaction, so the corresponding mechanism needs to be repaired. Therefore, if a change seems to be as simple as the original POW, then it is mostly problematic. As a result, there are not many places left for non-professional personnel operations. To improve the Bitcoin POW, you need to understand POW and distributed systems from a deeper perspective.

Here, we introduce some classic POW extensions from a scalable perspective.

As mentioned earlier, the bottleneck of blockchain bitcoin scalability is that any transaction needs to be sent to all nodes.

Among them, the Bitcoin POW has an additional limitation, that is, the validity of the POW is based on the fact that everyone is mining on the same longest chain, so, roughly speaking, only the last block is dug out and After synchronizing to the entire network, the consensus algorithm, mine mining, can begin.

Here, everyone has seen it – this is basically a synchronous system.

At this time, someone may raise an objection – the Bitcoin POW is known to be an asynchronous Byzantine fault-tolerant algorithm. What we are in is an asynchronous environment. Why do you say Bitcoin POW is a synchronization algorithm?

This is a common misunderstanding for Bitcoin POW. In fact, POW is only valid in a network that is basically synchronized. However, the Bitcoin POW encourages 1, the node does not do malicious behavior; 2, the node tries to keep in sync with other nodes to ensure that the system is basically synchronized. The reason why it is said to be "basically" is because we do not need absolute synchronization. Our requirement is that the time of the POW, that is, the block interval, needs to be much longer than the time required for synchronization, and the system can be considered to be basically synchronized. of. in other words,

The Bitcoin consensus algorithm must take some time to execute and must be started after all nodes are synchronized, ie, all transactions are transmitted and verified.

In other words, Bitcoin's consensus algorithm looks like this:

However, we want all bandwidth* time to be used to transmit transactions over the network, rather than having to do a time t1 synchronization first, to ensure that everyone has a consensus on the longest chain before starting a PW calculation for a period of time t2 consensus. In the period of t2, it is impossible to synchronize, because without consensus, we do not know which block is correct, so the bandwidth is wasted at this time.

Ideally, can we synchronize while doing consensus? The first step that needs to be done is that we need to decouple the consensus and the transaction (block content) in the Bitcoin POW.

For distributed system experts, the most successful thing is to put the Byzantine fault-tolerant state-of-the-art, the PBFT. Why do you want to set up PBFT? Because from the perspective of traditional distributed systems, the most intolerable aspect of Bitcoin is not his output or scalability, but a) delay of up to 6 blocks (one hour); b) no final Finality, that is, the consensus cannot always be confirmed. Then, the wheel gets a small problem, that is, c) the output is too low. But at the same time, distributed system experts have also seen a clear benefit of POW, which is non-permitted. Thus, naturally and in unison, Hybrid consensus and Byzcoin made a simple method of using POW as an admission mechanism and then performing (class) PBFT.

The principle of both algorithms is basically to preserve all the characteristics of the Bitcoin POW, such as block rewards, such as block time and so on. However, the POW no longer decides on the transaction, but only the committee elections. For example, we stipulate that the last 100 outliers are the current committee, and then they will make the BFT decision transaction. The transaction here is final and absolute. There is no problem of forking, and then broadcast to the whole network. Then we can think that the transaction decided in this way is the final result, so we solved the two problems (a) and (b), and then, incidentally, because the consensus of the POW only determines the blocker, the output of the transaction is no longer limited by the POW. It is only limited by the output of the BFT. Whether it is doing BFT or BFT to broadcast the transaction to the whole network, it will not affect the POW to continue the next round of consensus.

In this way, we are equivalent to making such changes to the Bitcoin POW:

Here, the committee's verification is carried out almost at the same time as the consensus (BFT algorithm), and the results of the consensus reached by the committee will be broadcast directly to the whole network. This process is also decoupled from the election of the next round of committees.

And these two ideas are similar from the perspective of expansion, but the route is different from Bitcoin-NG.

Bitcoin-NG is actually better understood – first of all, it is still based on the commonly used Bitcoin POW, except that the block that comes out at this time does not need to contain all the transactions, just announced – I am a legitimate player who wins the competition. Then, within ten minutes, the blocker can send "micro-blocks" at a faster rate (shorter block interval), which only contains transactions without having to do POW again, because he has already competed for this. One time the right to block. In this case, we achieved the same effect as Hybrid Consensus and Byzcoin – using POW to select the blocker instead of the block, so the deal itself was decoupled from the consensus.

But there is a problem here – what if the micro-block has an illegal transaction? At first glance, we can solve the problem directly with the POW method – "If you find a problem with the micro-block, ignore the block that has fallen out of the problem, and then let the next person who calculates the POW out of the block." However, this method is equivalent to linking the transaction synchronization speed to the consensus, so there will be the same problem as the Bitcoin POW—that is, nodes that are too late to receive and verify all transactions may waste their computing power in the final abandoned. On the chain.

Therefore, Bitcoin-NG needs a mechanism that does not replace the blocker or transaction block (in case the computing power is wasted), but can invalidate the illegal transaction and punish the blocker. This mechanism is called "toxic trading". Simply put, when an illegal transaction is discovered, the latter node can invalidate the transaction and then take the block reward obtained before the agent who submitted the illegal transaction.

In this case, we can compare the similarities and differences between Hybrid Consensus (Byzcoin) and Bitcoin-NG:

The same thing : Both decouple the consensus from the transaction by using the POW to select the blocker instead of the block (transaction) itself.

The difference : in Hybrid Consensus (Byzcoin), the transaction is determined by BFT, so we believe the transaction is already believable. The transactions issued by the blockpers in Bitcoin-NG are still unverified and may be illegal. Therefore, all nodes in Bitcoin-NG need to verify the validity of the transaction after the simultaneous transaction, and then Bitcoin-NG designs another set of incentive (penalty) model according to game theory to ensure the security of transactions in the micro-block.

So, in fact, Bitcoin-NG can be expressed as:

Here, consensus 0 refers to some initial consensus, and then the resulting consensus is after the transmission. If the final consensus is always inconsistent with the initial consensus, the algorithm will actually fall back into the bitcoin POW. However, as long as the final consensus and the initial consensus are consistent most of the time, the algorithm can be extended.

However, although both seem to be a simple variant of POW, it is important to note that:

Both have changed the security model of Bitcoin – the latter we have said that transactions in micro-blocks need to be penalized by "toxic transactions", while the former needs to be BFT, so the security assumption needs to be changed to "no More than one-third of the computing power is mastered by malicious nodes, which is not the same as the security of no more than 50% of Bitcoin's assumptions. Moreover, although in theory, Hybrid Consensus did not change the last 100 out of the block, it is just to turn the round out of the block into everyone to discuss the block. However, this change will still give people a sense of centralization, especially when more than 90% of the computing power is concentrated in the hands of big miners – in the bitcoin POW, small miners can still come out, but if on the committee Among them, the opinions of small miners will be submerged among 90% of the miners. Moreover, the committee election will fall into such a dilemma—for example, if the committee is too small, people who know the probability know that the probability that more than three of the 10 nodes are malicious is not small, so security cannot be guaranteed. And if this committee is too large, then the complexity and delay of the BFT itself will become very large, making the algorithm lose the meaning of expansion.

But in fact, these are some theoretical issues that need attention, but they are not defects. In terms of security, although the two change the security assumptions, it is not unsafe. It is not that the two must be insecure than the Bitcoin POW. After all, the Bitcoin POW also has such selfish mining. problem. However, whether it is the unique political factors of Bitcoin, the community willingness of the entire Bitcoin and concerns about security, and the difficulty of Bitcoin hard fork, will not allow Bitcoin to make such a big change to the algorithm. . After that, the popularity of POW in the academic world also cooled rapidly (see the development history of BFT in the previous article), so only a very few systems eventually adopted these two POW algorithms (there was a well-known project using Bitcoin). -NG). But the idea of ​​both – first select the committee and then carry out the BFT and select the block publisher first. The complete land preparation is inherited by the POS algorithm such as Algorand and Snow-white or Ouroboros. speak.

In addition, there is a third method.

Let us bring ourselves into Bitcoin miners to rethink why forks can cause bitcoin security to drop.

When you receive a block, you start verifying the block, and after confirming the legitimacy of the block, you start mining on it. However, after receiving the first block for 10 seconds, you received another block, and then, after passing the verification, you find that it is also legal…

At this time, you will face a dilemma – you can choose to continue mining in the first block, because you think that since you received it first, maybe many other nodes are the same. However, you also know that there is another possibility, that is, maybe you just received the second block later, and the other nodes in the network actually received the second one… but anyway, You can only choose one. The consequence of choosing the wrong one is that the piece you dig is not in the longest chain, and your calculations are wasted.

At the same time, all the nodes in the network are making such choices, and they also face the risk of wasted power. This is the reason why the forks cause the security of Bitcoin to decline.

At this time, we will think of a picture – why can't we both?

So, we got GHOST, which was later used in the Ethereum algorithm. In this algorithm, several blocks of the same height that are seen are allowed to be marked as the previous block at the same time, and then one of them is the "parent block" and the others are "uncle blocks". The transaction in the parent block is treated the same as the parent block of the Bitcoin POW, while the uncle block only records the block header, and the remaining transaction parts are discarded after verification. Then, the most important part is to change the longest chain consensus of bitcoin POW to the most heavy chain consensus, that is, the depth of the fork is also included in the statistics of the longest chain, so we get such a calculation method. .

This picture is taken from the Ghost paper, the link below.

Https://link.springer.com/chapter/10.1007%2F978-3-662-47854-7_32

In this way, even in a network with a lot of forks, a malicious node will not gain an advantage, because the computational power of a fork with a depth of 1 will also contribute to the security of the system, rather than being wasted.

In this way, we can slightly increase the output of the Bitcoin POW, because our requirements for synchronization are not as high as before, as long as all transactions in the block can be synchronized before the next consensus phase begins, it still does not affect the system. safety.

However, this practice is still limited – we still can't really expand, because we can't increase the block size or reduce the block interval without limit. The problem is that the fork with depth >1 is still Can not be included in the consensus, so it will still cause waste of computing power. Or, we have paralleled consensus and transmission to some extent, but not completely parallel.

And if GHOST is extended according to this idea, the fork with depth >1 is also included, that is, when the new block is dug, it does not have to point to the block of the previous height, pointing to the previous zone. Blocks are also available. In other words, there is no longer a time limit for trading synchronization. Even we can consider not discarding the transactions in the unblock, but letting them all be part of the ledger, and then using a consistent algorithm to determine conflicting transactions and duplicate transactions, so that we get the Inclusive Blockchain Protocol, Spectre, and even Phantom and Conflux. In other words, the Bitcoin POW has been transformed into a DAG that is now popular.

In an ideal state of DAG, miners do not need to manage the mining area behind which blocks to waste the power, nor do they need to control whether their own blocks contain transactions that have already occurred or conflicted – just need to be casual Connect a few blocks you know about the nearest block and then make a POW to send out the block. In the end, the system will reach a consensus on its own, and this consensus can make use of the power of all miners in the network to ensure that the cost of malicious nodes wanting to make double payments is still 50% of the total network computing power.

That is, we got the system shown below – bandwidth can be used to transfer data, and consensus can be done in parallel – this is another way to extend POW.

This time, we mainly introduced the reason why the Bitcoin POW is not expandable and the idea of ​​two scalable POWs.

In the next issue, we will introduce the basic principles and challenges of POS and DAG from a scalable perspective, and introduce some star projects, such as the POS class Ouroboros, Algorand, Dfinity, and the DAG class Phantom and Conflux.

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