In the Nakamoto consensus protocol (abbreviated as NC in the Nakamoto Consensus picture), in order to solve the bifurcation problem, the miners are required to choose the longest chain if possible; when there is no longest chain, the miners choose the first received Blocks are added to the main chain. In terms of rewards, the main chain blocks will get all rewards, and the orphan blocks will get nothing.

Is this safe enough?

The original analysis of the Nakamoto consensus tends to believe that the blockchain itself has perfect chain quality, that is, attackers with less than 50% of the computing power of the entire network cannot modify the blockchain. However, in fact, an attacker can modify the blockchain with a very high success rate.

There are three types of attacks that modify the blockchain: Selfish Mining, Double Spending, and Censorship Attack. Among them, selfish mining attackers can obtain unfair block rewards that are not proportional to their computing power. They can concentrate mining computing power to obtain higher relative block rewards, thereby destroying the decentralized nature of the blockchain; in a double-spend attack, the attacker can reverse the confirmed transaction and maximize their own interests ; In the case of censorship attacks, the attacker prevents the transaction from being confirmed, causing economic losses to honest miners.

selfish mining

• selfish mining

The red squares indicate when the block was propagated to the network, then the orange circles indicate the attacker's block, and the triangles indicate the block mined by the honest miner. The attacker was lucky enough to find the first block, but instead of publishing it to the network, chose to withhold it.

When an honest miner finds a block, the attacker will broadcast the withheld block before the honest miner at this time, and then all miners will mine on the attacker's block instead of the honest miner's block.

If the attacker is lucky enough to find multiple blocks in a row, the attacker can isolate an honest block with no risk. In this case, the attacker's chain becomes longer, and the computing power of the entire network will go to its chain to mine. In this way, the attacker successfully increases the relative proportion of the overall block reward earned.

• double spend attack

Double-spending attacks are very similar to selfish mining attacks, which are to obtain additional rewards through secret mining. For example, in Bitcoin, according to the convention, there are 6 blocks to confirm the transaction, which is basically completely confirmed. If an attacker secretly withholds 6 blocks and broadcasts them to the network all at once, he can reverse the transaction after receiving the good or service.

• censorship attack

Censorship attacks try to isolate all blocks that don't meet censorship requirements, i.e. I'm going to broadcast these transactions that I want to censor, if you don't follow my orders, I will try to isolate your blocks

two solutions



Let's talk about two ways to solve the Nakamoto consensus security problem.

The first category we call “better chain quality” protocols. There are many protocols in this broad category as shown, which claim that they can improve the quality of the chain. This time I will focus on "Smallest hash tie-breaking protocol (SHTB for short)" and "Unpredictable deterministic tie-breaking protocol (UDTB for short)".



The second broad category is called "Attack-resistant protocols". These protocols claim that they can resist attacks without the quality of the chain being perfect, so they don't need to improve the quality of the chain.

Three Types of Anti-Attack Protocols

The first is the Reward-all protocol. This type of protocol rewards the most recent proof-of-work, and eligible blocks will be rewarded anyway, so that the attacker cannot conduct a selfish mining attack to invalidate the rewards of honest miners, so the attacker has no incentive to be selfish mining attack.

The second is called the "Punishment" protocol. These protocols will forfeit rewards for suspicious blocks. The penalty rule hopes that through loss aversion, everyone has to abide by the agreement.

The third is called the "Reward-lucky" protocol. These protocols reward certain lucky blocks based on the content of the blocks, hoping that these lucky blocks will serve as "anchor points" for a stable network.

Let's take a deeper look at these protocols next.



First of all, we analyze the "better chain quality" type of agreement, and the first is the "minimum hash tie breaking agreement". In this protocol, whenever there is a tie, the protocol requires all miners to choose the block with the smallest hash, regardless of who it received first.

The second is called "Unpredictable Deterministic Tie Breaking Protocol". The protocol states that whenever there is a tie, everyone uses an unpredictable deterministic pseudo-random function to calculate the order of all participating chains, regardless of which block was received first. The rationale behind an unpredictable deterministic protocol is that since an attacker cannot predict whether he will win the block competition with more than 50% chance, it is unwise (and therefore not an option) to conduct a selfish mining attack.



For the anti-attack protocol, I will choose a protocol from each technical method to analyze. For the "all rewards" protocol let's analyze the fruit chain. In Fruitchain, the same mining procedure is used for two different products. If the first k bits of the hash value of a candidate block are less than a certain threshold, it is judged to be a block; if the last k bits of the hash value of a candidate block are smaller than a certain threshold, then it is judged It is fruit. So when you run the hash algorithm, you might get a block, or you might get a fruit.

The protocol, like the Nakamoto consensus, follows the longest chain principle and breaks ties based on the first received block.

For all attack-resistant protocols, we use Nakamoto consensus as the rule for their fork resolution. Therefore, when we analyze their attack resistance, they are put under the same rule.

Fruits are embedded in blocks. You can think of fruit as a transaction in the Nakamoto consensus, which is just embedded in the fruit.




Each fruit has a pointer block, which is the nearest block, and the fruit miner will not be orphaned. The pointer of the banana block in the figure is such a case. If the pointer block is in the main chain, the fruit is valid. If the pointer block is an orphan, like the tomato on the diagram, then the fruit is no longer a valid fruit.

There is an additional rule that the fruit block interval needs to be less than the predefined timeout threshold. Gap is defined as the block height difference between the main block and the pointer block.

For example, the interval of bananas is 2, because the main block is 2 blocks later than the pointer block. So valid fruits get the full reward, while blocks get nothing.



For the punishment protocol, we choose the modified version of the DECOR protocol as a case to explain. In our modified version, we call it the Reward-Splitting (RS) protocol, where, as the name suggests, the reward is divided equally among all competing blocks of the same height. This protocol allows a block to refer to the previous orphan block as an uncle block. If the interval is lower than the timeout threshold, the uncle block is valid (and will also receive certain rewards).

This is similar to the definition of the interval in the reward distribution protocol and the fruit chain. The difference is that in this protocol, the interval is defined as the height difference between the main block and the uncle block, rather than the height difference between the main block and the pointer block. So we don't consider the kinship of the block, only the height of the block itself. Each block reward is evenly distributed between competing blocks and uncle blocks of the same height. For example, in this diagram, blocks B and C each receive half of the block reward, while blocks A and D receive the full block reward.



The last one is the child chain. The sub-chain also uses the same mining procedure, but it is two different products. The block generation rules in the subchain are the same as Bitcoin. If the hash of the candidate block is lower than a certain threshold, the block is judged to be valid. If the hash value of a candidate block is greater than the block threshold but less than another threshold, we consider it a weak block (Weak Block). Weak blocks are also included in the chain length and perform the function of transaction confirmation. However, weak blocks do not receive any block rewards. Only blocks earn block rewards.

Common Metrics for Measuring Protocol Security

I am very excited, because next we will set some common metrics to measure the security of the protocol. You claim that this is the safest protocol. If you want to prove it to me, you need to measure how secure your protocol is from the dimensions of these indicators.

There are four indicators in this study, let's analyze them.




The first metric we call Chain Quality refers to the minimum percentage of honest miners’ blocks on the main chain. In this example, the chain quality is three out of six, because there are six blocks in the main chain, three of which are from honest miners.

The second, called Incentive Compatibility, measures resistance to selfish mining attacks and is defined as the minimum percentage of block rewards for honest miners.

In this case, since three of the six main chain blocks come from honest miners, the incentive compatibility is 50%. In Nakamoto consensus, these two metrics (referring to chain quality and incentive compatibility) are equal. However, for other protocols, these two metrics are not the same. Chain quality is only used to evaluate Byzantine adversaries (aka malicious nodes), but incentive compatibility takes rewards into account.



The third indicator is another indicator of attack resistance, called "Subversion Gain", which measures the performance of anti-double-spending attacks. It is defined as "the average block reward that can be obtained per block interval plus the maximum value of the double-spending reward."

In this case, assuming a block is found every 10 minutes, if there are 8 blocks in total, it will take a total of 80 minutes (of which the attacker has 3 blocks). In this example, on average every 10 minutes, the attacker gets 3/8 block rewards. The double-spend reward is 0 because the double-spend reward requires six blocks to be isolated in a row.

Because there is no full percentage reward in the anti-double-spending attack, the indicator is set to "obtain the maximum block reward per block interval on average". On this graph, there is no double-spend attack reward, because you need to isolate at least 6 blocks in a row to get the double-spend reward.

The last metric is called Censorship Susceptibility, which is the maximum percentage of rewards that honest miners lose due to rejection of censorship requests. Because if I deny the review request, the attacker will start orphaning my blocks. This metric measures the percentage of my blocks that can be orphaned. In this case, there are 5 honest blocks, 2 of which are orphaned, so the censorship sensitivity is 2/5.

evaluation result

Now let's look at the evaluation results. In this sharing, I analyzed 5 protocols, let's take a look at the quality of the first indicator chain.
We first define a variable γ , which is the percentage of honest miners’ computing power mining on the attacker’s chain to all honest miners’ computing power in the event of a tie.

If γ is equal to zero, then all the honest miners' computing power will be used to mine the honest miners' chain, and no honest miners' computing power will mine on the attacker's chain. If γ equals 1, then all honest miners' hashrate will mine on the attacker's chain, and no one will mine on the honest miners' chain.

This is the general parameter used to evaluate Nakamoto consensus. Here are five cases, Nakamoto consensus, minimum hash tie breaking protocol (SHTB) and unpredictable deterministic tie breaking protocol (UDTB) in the case of γ = 0, 0.5, 1 respectively, which one is the most chain quality Good?



Among these five protocols, Minimal Hash Tie Breaker (SHTB) and Unpredictable Deterministic Tie Breaker (UDTB) only focus on how to break ties. So you can't do better than Nakamoto consensus in the case of a tie with γ = 0. Because when γ = 0, all mining power will be on the honest chain. And you can't get any worse than Nakamoto consensus with γ = 1, where the attacker wins all ties.

So among the remaining three protocols (SHTB, UDTB, Nakamoto protocol with γ = 0.5) which one is the worst performer? It is actually the minimum hash tie that breaks the protocol. So which one is better for the remaining two protocols (UDTB, Nakamoto protocol with γ = 0.5)?

I'm here to uncover the answer. Nakamoto consensus with γ = 0.5 is better. Why? For example, in the Unpredictable Deterministic Tie Breaking Protocol (UDTB), when an attacker finds a block, but honest miners package the block and broadcast it before the attacker, Then it is possible that the attacker will calculate the pseudo-random function and realize that if he publishes his block, no one will continue to mine on his block, because he lost the tie in the block competition . So what can this attacker do?

In Nakamoto consensus, the attacker is doomed to failure because the first received block breaks the tie rule, and if you don't publish the block as soon as possible, no one will mine on your block. But it is different in UDTB. Even if the next block has been dug out, the attacker can still continue mining on this block. As long as the attacker can win the right to produce the next block, the attacker will Ability to publish two blocks simultaneously after the honest miner's block.
If this pseudo-random function indicates that the attacker has won the block competition, the attacker can get the block reward. Because UDTB allows a special attack behavior called "post-strike", the security of UDTB will be worse than Nakamoto consensus with γ = 0.5.

So why is the minimum hash tie-breaking protocol so poorly secured? Because when an attacker finds a block and the hash value is indeed very small, the attacker has about 99% probability that he will be able to win the right to produce the block no matter what other people's hash is. No matter which block I broadcast first, I can accurately predict the probability that I can win this tie. This allows an attacker to launch a block attack if he is lucky enough.

When the honest miner finds the next block, because the hash of the attacker's block is small enough, he has a high probability of winning the block right, so he can publish the block and get the block right . The next time when the attacker is not so lucky, he gets a block with a relatively large hash, and the attacker can publish this block and get rewarded directly.

General Conclusions for Better Chain Quality Protocols

Below are some general conclusions from our research on better chain quality protocols.



No protocol can achieve the quality of an ideal blockchain when the attacker's computing power α > 1/4. As long as the attacker's computing power exceeds 1/4 of the entire network's computing power, its income can be higher than its normal income calculated according to its computing power share.

As long as the attacker's computing power exceeds 1/4 of the entire network's computing power, its income can be higher than its normal income calculated according to its computing power share.

For any value of α, with γ = 0, no protocol performs better than Nakamoto consensus in terms of security.

Maybe for a specific situation, a certain protocol is better in security than Nakamoto consensus, but in general Nakamoto consensus is the best in security.

why is that? Because the protocol cannot distinguish between honest blocks and attackers' blocks.

Why can't the protocol distinguish between these blocks?

This is because of information asymmetry. The attacker acts based on all available information, which means he knows how many blocks he has released, how many blocks he has withheld, when I will release these blocks, etc., the attacker knows everything. Honest miners, however, act only on the basis of limited public information.
Why?

This is because PoW has weak security assumptions. They try to operate asynchronously, stipulating that all miners only act/operate on very limited public information.

So now let's analyze their attack resistance for Nakamoto consensus, fruit chain, reward distribution (Reward-Splitting, RS) protocol, and sub-chains, first of all, incentive compatibility.



Among them, the reward distribution protocol (enforcement) performs the best, because punishment is always the most effective way to incentivize correct behavior. The child chain performed the worst.

Fruit chains perform sometimes better and sometimes worse than the Nakamoto consensus. Subchains allow attackers to invalidate honest blocks with weak blocks that are worthless. If everything has value, it is risky for an attacker to withhold blocks. But a weak block is worthless by itself, and an attacker can withhold this weak block without risking losing the block reward. Since there is no risk, why not try a more daring behavior of withholding blocks?

The more weak blocks, the worse the protocol behavior. So more weak blocks actually make things worse. The best case is not to use weak blocks.

When the timeout value of fruit chain is small, it performs worse than Nakamoto consensus. An attacker can use useless blocks to invalidate his fruit. This also has a similar problem, because the block does not have any rewards in the fruit chain, so the attacker has no incentive to publish the block, because there is no risk of withholding the block, and the result is that the attacker can try more bold behavior of withholding the block .

The result is that attackers can attempt more aggressive holding behaviors.



It would be slightly better if there were more fruit. There is a famous Newton-Pepys problem, which is a probability problem, namely

A. 6 normal dice rolled independently, at least 1 6 appears
B. 12 normal dice rolled independently, with at least 2 6s

If you roll 6 dice, the probability of getting 1 6 is greater than if you roll 12 dice and get 2 6s.

There are four mining products in the fruit chain: honest fruit, honest block, attack fruit, and attack block.

We can think of "the attacker has 1 timeout block than the honest miner" - i.e. the attacker can successfully isolate some fruit - as a conditional event. This event is completely independent of fruit generation as it only considers chunks. We can treat it as a condition in Newton-Pepy's problem - since it is independent, we can just throw it away. But when the condition is met, if there are fewer fruits, the probability of "the attacker has more fruits" is very low.

More fruit means more attacker fruit. Because the attacker is a minority, if the total number of fruits is more, it means that the total proportion of the attacker's fruits will be more than it actually is. It is better to use gambling as an analogy here, because we have more fruits, which means that when the attacker has more fruits, then he will participate in gambling less. One is more willing to gamble when he has nothing to lose, but he does not want to gamble if more capital is likely to be lost, which means that more fruit slightly contributes to incentive compatibility.

Next, in the attack resistance, we analyze the "bad profit" of the attack. The smaller the index, the better. As shown in the figure, the reward distribution protocol is better than the Nakamoto consensus, better than the fruit chain, and better than the sub-chain.



We analyzed another interesting measure called "bad bounty". We define it as the minimum double-spend reward to study incentive bias. (That is to say, when the reward for a double-spending attack is greater than the bounty for doing evil, the attacker has the motivation to do evil). (The table in the lower right corner of the figure is the bounty calculated by Nakamoto consensus and reward distribution protocol when the number of block confirmations is 3 or 6, α (when the attacker's computing power ratio is 0.1 to 0.4).

By calculating the "evil bounty" of each protocol, it can be found that the fruit chain and sub-chain can basically be destroyed at zero cost, and even double spending without reward can be attempted, because there is no risk.

We can see that as the number of transaction confirmations increases, for a weak attacker, the growth of the evil bounty grows almost exponentially. This means that more transaction confirmations do help to resist double spending, but the effect is not so obvious for strong attackers.



For censorship resistance, we calculate all the numbers and rank as follows:

For small α, that is, when the proportion of the attacker's computing power is low, the fruit chain is the best, then the Nakamoto consensus, and then the reward distribution protocol and sub-chains.

For large α, that is, when the proportion of the attacker’s computing power is relatively high, the reward distribution protocol becomes the best, followed by the fruit chain, Nakamoto consensus, and sub-chains.

What is obvious is that for Fruitchain, if you want to invalidate other blocks, it is much more difficult than other protocols, because they are rewarded under multiple conditions, even if you are an orphan block.

Why is the reward distribution protocol better than the fruit chain when α is large enough, that is, when the attacker's computing power is relatively high? Because on the fruit chain, the interval is defined as the block height difference between the main block and the pointer block. Whereas in the reward distribution protocol, the interval is defined as the difference in block height between the main block and the block itself.

Therefore, in the fruit chain, if the attacker wins in the long-term block competition, the rewards of honest fruits will be taken away because their pointer blocks are all isolated. That is, if you isolate their pointers, it's game over for them. However, in the reward distribution protocol, the last few honest blocks can still get some rewards. For honest miners to lose all rewards, it is not enough to orphan their pointers, you need to orphan a large number of consecutive blocks. (This adds an obstacle to the attacker).



These pictures illustrate these issues.

In the fruit chain, if you isolate the pointer, then you can get all the rewards with peace of mind. However, in the reward distribution protocol, even if you have isolated these blocks for a long time in the block competition, these blocks will still point back to the main chain. Because the key relationship is not taken into account, this block still takes half of the attacker's block reward, which makes it more resistant to censorship attacks. (Because honest miners can still get part of the reward even if they are censored.)

General Conclusions for Attack Resistant Protocols

Let's talk about some general conclusions about the anti-attack protocol in the research.




Reasonably setting longer block confirmation time and larger bandwidth will increase security.

There is a dilemma, a mechanism we call "reward the bad guys, punish the good guys". This subverts everyone's understanding of protocol rewards. Because even if you fork here, you can still get block rewards, and there is no risk for you to fork. So this instead motivates attackers to fork and launch double-spending attacks.

In a punitive protocol, because censorship attackers don't care about their own block rewards, your penalty rules instead give attackers another tool to get honest miners to forego block rewards.

And for the lucky reward protocol, if you don't break the information asymmetry, then lucky doesn't mean good. Sometimes a lucky block turns out to be a bad block, making things worse.

The conclusion is that to address all attacks, we need to go beyond rewards in the underlying rules. (The reward rule does not solve the attack problem very well)

How to do it? I propose some ideas to discuss with you.



We should not design a protocol that is too complex and too difficult to analyze. We need to design a protocol that the designer can analyze. Simplicity is good, complexity is the enemy of security.

Security analysis aimed only at a single attack strategy is dangerous. For many protocols, their designers have simulated that their protocol can resist a specific attack method, but such a protocol has inspired attackers to study other attack strategies. Security analysis aimed at only a single attack motive is also dangerous.

Attackers may focus on short-term interests, long-term interests, or harm the interests of other miners. In order to resist one attack, you may inspire the attacker to launch another form of attack based on another target. You need to account for all attackers with different motivations in your model.