Defects of the heaviest chain rule: "The Crown Prince" in the "Public Ancestral Blocks"

In the previous issue of "The Advantages and Hidden Troubles of the Most Heavy Chain Rules," we introduced the strong potential of the heaviest chain rules in shortening the confirmation time.

But we also mentioned that when the most heavy chain rule judges whether a block is confirmed, one of the preconditions is that the block is a "public ancestor" (Note: If the honest miner agrees that a block is in his own chain) Then we call this the "public ancestor" of all honest miners).

In the tree diagram structure, we do not require the block to be confirmed to be a common ancestor, but the main chain block in the epoch where the block to be confirmed is located is a common ancestor.

Ethereum uses a variant of the most heavy chain rule, and we use Ethereum as an example of a practical deployment of the most heavy chain rules.

In Ethereum, we can see that most of the blocks have entered the main chain, and then just wait a few minutes or even less, and all newly generated honest blocks will appear in the subtree of this block. In other words, this block becomes a public ancestor. Then all new honest blocks work together to increase the weight of its subtrees. This makes it impossible for an attacker with a small amount of computing power to "support" a brother as a competitor.

After the public ancestor block has accumulated enough advantages, the block is confirmed.

In Conflux's experiment, in the absence of an attack, each block can become a common ancestor within ten seconds or enter the epoch of a common ancestor. If the block rate is very fast, it can be confirmed in a short time.

It seems that everything is fine, however, some attack strategies can prevent new blocks from becoming "public ancestors." That is to say, for a block that has become a public ancestor and has been confirmed, the attacker has no ability to reverse.

However, the attacker has the ability to make the honest node who is the next public ancestor block, and does not reach a unified opinion, thus causing the honest node to fall into the prolonged "king of the crown". After that, any newly generated block cannot be confirmed by all honest nodes.

This type of attack, which is not intended to be a confirmed transaction, to prevent new transactions from being identified, is called a "survival attack."

So far, there has been a lot of publicly discussed tools that are publicly discussed, which we call "balanced attacks."

The idea of ​​a balanced attack is simple. The attacker, under the last common ancestor block, "fosters" two evenly matched children, trying to maintain two subtrees of the same size.

The attacker's influence on the block network transmission allows almost half of the computing power to contribute to one of the subtrees, and the other half contributes to the other subtree.

If the powers on the two subtrees are close but not exactly equal, the attacker can use his or her own power to balance the gap and ultimately achieve equal power on the two subtrees.

The honesty of being divided into two parts becomes the two opposing camps.

Two subtrees of similar size grow subtree weights at the same average speed.

Under the deliberate influence of the attacker, each block will be seen by the nodes of its own camp in a short period of time after it is generated, but it will take some time to be seen by the nodes of another camp. Every camp feels The weight of his own subtree is slightly larger, and then continues to contribute power in the subtree of his camp.

This is a dilemma created by attackers.

If the attacker only balances the power and network of the two subtrees and does not perform the "block" operation, the honest node still has the ability to break the dilemma.

Because the mining process always has some randomness, one of the camps will dig out more blocks in a period of time.

However, assuming that there are an average of n blocks in the network that are broadcasting, but have not yet propagated through all the nodes, the time required for the honest node to break this dilemma is n square.

Under a given network delay, each time the speed of the block is doubled, n will double, and the time for the honest node to break the dilemma will increase by a square.

And if the attacker still digs some blocks on each branch, then each time the honest node is about to break the dilemma, the attacker can "actively intervene" and release some blocks hidden in the weak branch to continue. Maintain balance (just like the traitors in the Three Kingdoms).

Through some analysis, it can be obtained that even when the speed of the block is fast enough, even an attacker with a small amount of power has a certain probability that the honest node can never break the dilemma.

As a designer of the consensus mechanism, how should this problem be solved?

Very simple, like Bitcoin, let the block speed slow down and let the value of n decrease. If it takes 10 seconds to spread a block over the entire network, and the block time is 10 minutes, when the attacker does not perform the "block" operation, a new honest block is generated with a probability of 59/60. There are no other blocks in the transmission, the local tree structure of all honest nodes is consistent, there is no honest node in the two camps.

Even if the attacker has a stronger attack ability, he will find that the number of times he needs to "intervene" greatly increases when the block rate is slow, and his own calculation power is already inadequate.

We constructed a theoretical model.

In this model, the power of the honest node is an average of n blocks per second, and all honest nodes are divided into two groups, and the power of the two groups is equal. There is no delay in block propagation within the group, and block propagation between groups has a delay of d seconds.

In this way, the blocks received in each group are the same, and the blocks seen by the two groups are not exactly the same.

At the beginning, the two groups selected two different children's blocks under the same father block as the main chain blocks, and contributed weights below them. The initial weights of the two child blocks were the same.

If at some point, the child block selected by one of the groups is not dominant in their local view, that is, the team is going to "tweak" according to the most heavy chain rules, the attacker needs to release some blocks to avoid This matter, thus maintaining the two groups can not agree on who is the next "public ancestor". If the attacker cannot release the block, then the attack fails.

If the attacker wants the attack to never fail with a probability greater than zero, then the attacker needs to meet a minimum computing power requirement.

The figure below shows the lowest computational power requirements for different d*n cases.

It can be seen that when the value of d*n is very small, the required computing power is close to n blocks per second, that is, the block generation rate of all good people. At this point, the requirement for a balanced attack is no lower than a double-flower attack. When the value of d*n is very large, the required computing power approaches zero.

If we reduce the speed of the block to a low enough value so that the value of d*n is lower than 0.1, then it is difficult for the attacker to launch the attack with a lower computing power. (Bitcoin is not the most heavy chain rule, but we can Take the example of the parameters of Bitcoin. In Bitcoin, d*n is about 0.02.)

However, slowing down the attacking block and violating our original intention – to create a PoW public chain with a very short confirmation time. This has created a dilemma.

1. Blocking speed: Blocks that have been confirmed are not safe. When no one attacks, the speed is very fast, and someone can never confirm when attacking.

2. The speed of the block is slow: the security can also be guaranteed, and the transaction can be confirmed after a period of time when someone attacks, but the confirmation time will be very slow even if no one attacks.

So far, the "heavy" rule of the most heavy chain rule (survival attack when the block rate is fast) almost completely obscures the "jade" of the most heavy chain rule (the confirmation speed is fast when the block speed is fast).

So in this dilemma, do we have a way to achieve both, both fast and safe, and fast and efficient?

Official website