Vitalik's latest speech: 51% of nested attacks become a deadly threat to PoW blockchain, PoS is the only way out

From February 20th to 22nd, Beijing time, the 2020 Stanford Blockchain Conference hosted by Findora was held at Stanford University. This meeting focused on security engineering and risk management methods in blockchain systems, and explored the application of encryption technology. , Decentralized protocols, formal methods, and empirical analysis to improve the security of blockchain systems.

On the second day of the conference, Ethereum co-founder Vitalik Buterin gave a speech entitled "Crossing 51% Attacks". In the conference, he first mentioned the different types of 51% attacks, such as the most common rollback transactions. Attacks, in addition to censorship attacks, light client attacks, discouragement attacks, and the most severe Spawn camp attack, he believes that Proof-of-Work (PoW) cryptocurrencies are easily affected by these attacks, and the rights and interests Proof-of-stake (PoS) cryptocurrencies can detect attack chains and review attacks through technologies such as 99% fault-tolerant consensus and timeliness detector (TD), thereby eliminating the threat posed by 51% attacks.

(Photo: Vitalik speaks at the 2020 Stanford Blockchain Conference)

• How is the value logic of Bitcoin different from Buffett's stock logic?
• Babbitt Column | Understanding the Decentralization of Cryptocurrencies
• SheKnows 丨 Bitcoin halves wealth not halved! Miner's "Operation Guide" gives you directions

Here's what Vitalik said:

What can a 51% attack do? There are different types of 51% attacks. They can perform different operations on different applications and produce different results and consequences. A 51% attack you may be familiar with is rolling back a block. You make a transaction, send the money to an exchange, and then exchange these coins for another currency. You withdraw these exchanged coins, and then perform a 51% attack to restore your deposit transaction …

This is the main type of 51% attack that we have been discussing for the past 10 years, and it is also the one we think about most.

I. Other types of 51% attacks

1.1 Transaction Review Attack

In fact, transaction review is another 51% attack! Given that both the layer 2 protocol and DeFi are recent megatrends, transaction review has become particularly dangerous . In many layer 2 protocol environments (including plasma, channels, general state channels, Lightning Network, Optimistic Rollup, interactive computing, TruBit, etc.), censorship means theft!

So if you can review the challenge transactions, then you can steal money from people. This does not apply to zk Rollup, but this attack does work for most protocols that people are now considering . In the context of DeFi, censorship is particularly dangerous because it is a tool through which you can manipulate the market and then gain value.

If you can review every Ethereum blockchain transaction that comes into contact with Uniswap and wait a day, then the price of Ethereum may fluctuate a little and I can extract a lot of arbitrage value from this attack.

It can be said that censorship is dangerous. In the DeFi agreement and the layer 2 agreement, transaction censorship can also be regarded as equal to theft .

1, 2 light client attacks

Many people are running light clients. If you are running light clients, then a 51% attack may cause these light clients to accept a chain containing completely invalid transaction blocks. Wrong signatures, malformed transactions, unauthorized signatures (stealing funds from one account and transferring them to other accounts), they can get the available blocks accepted by the network.

Data Unavailable Attack

Who is familiar with data availability here? Well, although not everyone, many people understand it. The idea here is that you can create a chain where the block header is published. Light clients can see this chain, but cannot publish some or all data in block bodies. This is bad because if the data is not published, it may or may not be correct and there is no way to generate evidence to prove to others that it may be correct and you reject that people may want to create future transactions Information. In other words, unusable blocks are also dangerous .

1.4 Dissuade Attack

Discouragement attack is a term that refers to maliciously damaging other participants, causing them to lose their income, driving them to conspire with you, or being forced to quit. Selfish mining with more than 1/3 of the computing power is one such example . In other words, a 51% attack is also a very powerful discouragement attack.

1.5 Tamper-resistant modification of blockchain

Therefore, 51% attacks are very powerful, and such attacks are a threat to the non-tamperable modification of the blockchain.

Who remembers this? A bunch of money was stolen from an exchange and they were considering pushing a one-day reversal of the Bitcoin blockchain in order to get the money back. If such a thing is possible, then something inside the blockchain may be restored, and the blockchain loses its key attribute of becoming a blockchain, which is terrible.

In addition, 51% of attacks are not democratic, they are ruled by the rich, so as a democratic method, it is not good for them.

Second, the 51% attacks that have occurred in the real world, and the worst 51% attack scenarios

In reality, 51% of attacks can be completed. This is a photo from the 2015 Bitcoin Expansion Conference in Hong Kong. In this photo, some people who control 90% of Bitcoin's computing power sit together and pose a gesture of "I have power", haha.

51% attacks can be completed. For example, ETC, Bitcoin Gold, etc. have all encountered 51% attacks. I am sure I missed 1-2. These attacks have already occurred.

Spawn camp attack

In fact, the 51% attack we are seeing is not the worst. For this type of attack, the Spawn camp attack is the worst nightmare scenario. Basically, you need to get enough hardware to attack a chain, wait for it to recover, and then attack again, because you still have the hardware. In the end, the community will be fed up with this kind of torture. They will replace the proof-of-work (PoW) algorithm. Since they have no way to build an ASIC in a short time, you only need to rent a large amount of CPU and GPU computing power to continue the attack. Then, This chain is dead unless they switch to proof of stake (PoS) or become completely centralized.

3. Can the Proof-of-Stake (PoS) algorithm break this cycle?

This is a blog post I wrote in 2016. I am trying to describe what is the philosophy behind Proof of Stake (PoS) and why this is what we should expect to exist and why it is a meaningful thing. There is an asymmetry in Proof of Stake (PoS), which is different from Proof of Work (PoW). In Proof of Work (PoW), you only have rewards, so you are punished for participating in the attack or not participating in the attack. Only the block reward part. In a Proof-of-Stake (PoS) system, your attack can be detected, and your lost deposit is much larger than the pledged deposit you can be forfeited.

They are incorporated into Casper CBC and a range of other Proof-of-Stake (PoS) algorithms based on secure deposits and forfeiture. Theoretically, the goal of this design is to make 51% attacks extremely expensive. Basically, you want to attack a PoS chain, you need to buy a bunch of coins, you need to control more than 50% of the coins in the system, and then when you are caught to attack, you will be punished if you want to attack again To launch an attack, you have to buy more coins, because you have been buying, then the rising currency price will eventually cause you to go bankrupt, so from this perspective, instead of letting attackers target PoW, our goal is to make The chain turns to PoS.

What about other types of attacks?

Now let's discuss the first question. How does PoS solve other types of attacks? So far, we have been focusing on the final reversal. This is quite common in Byzantine's fault-tolerant consensus theory. The basic idea is that if 2/3 of the side is on one side and the other 1/3 is on the other side … 1/3 of the validators must send two conflicting messages, you can detect and punish them. However, this is about a reversal attack.

What about other types of attacks? Invalid data, unavailable data, censorship, and malicious destruction?

Let's solve it little by little, we will not care about the validity of the data, we will notice that if you have a guarantee of data availability, and if a block is part of a blockchain, then all The data can be downloaded by a node in the network. If you have censorship resistance and you publish a block, then it will eventually be included, and from these two things, you get validity. The reason is interactive computing, rollups, and these existing protocols. Basically, for Rollup, you publish all the data on the chain, then the chain guarantees its availability, you have some fraud proofs, and guarantee that if some calculations are invalid, then you can issue an unreviewable fraud proof and get it processed on the chain . So the validity of the data is not so important, because the fraud proof of the first layer (layer 1) and the second layer (layer 2) can solve this problem.

If you cannot censor other people's blocks, then you cannot prevent them from being included in the blockchain. Therefore, as long as the punishment of incentive measures is effectively controlled, grieving will not be a big problem.

We can boil down to two things: data availability attacks and censorship attacks.

Invalid and unavailable data

This is a paper I co-authored with musalbas and others in 2017, in which I describe a scheme that basically allows blockchain clients to verify the availability of blockchain data without actually downloading all the data.

A simple Scarecrow version of this scheme looks like this: The dumbest way to check if a block is available is to download the complete thing. But here, we assume a scalable, possibly sharded blockchain, in which more than 2 MB / s of data will be uploaded to the chain, and the client will not be able to download all content. For a client who wants to check the availability of data, all we have to do is a random sampling test. It will randomly select some data fragments, such as 30 fragments, 40 fragments, 80 fragments … It will randomly select locations and ask for merkle proof of these locations, as long as you receive valid responses from all locations you accept, then You will accept the block as valid.

If you accept a block using this scheme, then you most likely know that the block is valid. If less than 50% of the data is available, for example, all data on the left is available here, and all data on the right is available here, then at least one check will most likely fail.

With this approach, an attacker can spoof a few specific clients. However, if an attacker tricked enough clients that they downloaded half of the cotyledon data, then those clients could continue to reconstruct data from there.

This does not prove that the block is fully usable, it may be missing a part, but it does prove that at least half of the block is available. It would be great if we had some techniques to recover entire blocks from 50% of the data.

Erasure coding

This is where erasure coding comes in, so we need to take the data, assuming it is a polynomial evaluation, we will evaluate the same polynomial at more points, and now, any 50% of the data is enough to recover all the data . With this solution, you can verify that the blocks are useful, and that the blocks are available at potentially very large sizes, while individuals are downloading 20-200 KB of data.

This is the first part. This includes data availability attacks, which are part of the Ethereum 2.0 sharding solution, which at least allows us to give sharded blockchains the same availability guarantees.

Prove correctness

So how do you prove that a root is the root of this erasure code? How do you prove that you are not stuck with junk data? You can use a fraud proof, such as this 2D, if you code it wrong, then someone can make a short fraud proof, you can broadcast it to the network, and then the network can reject the block. This 2D scheme was started in 2017. Recently there is something about encoding merkle trees. You encode each level in the merkle tree, which has very good characteristics. There are also methods that do not rely on fraud proofs, such as using STARK or SNARK to prove that the calculation of the merkle root is correct, while another may involve polynomial commitments-you will get your data and you will interpret it as polynomial Evaluate, you calculate the polynomial, and then you make a bunch of polynomial promise openings at a bunch of points. Your data availability check will require 80 positions instead of 80 openings, or You use smart algebra to get some kind of multi-opening, and you get higher efficiency.

The advantage of these schemes is that they do not rely on proof of fraud, so schemes for verifying block data have been published, and they no longer have any additional built-in latency assumptions.

Sharding: Crossing the Committee

The existing sharded blockchains usually rely on the committee. The idea is that you have a lot of nodes and you randomly select some nodes. You need most or most of them to sign a certain block in order to It is valid for the network to accept the block.

The problem is that any committee-based approach is subject to review by bad actors who exceed a certain threshold . If we are talking about resisting a 51% attack, then we are talking about a system in which even if most people start to attack, then a few people should be able to continue the operating system itself.

A sharding scheme with a fixed threshold does not really help you. So the solution here is that the protocol needs to rely more fully on a set of data availability checking schemes than on committees .

About review

Anyone here who wants to stop censorship? Yes, there are many people, so the status quo is not very good. This is an article by nrryuya. He did some work on formal verification of Ethereum. He wrote an article saying that in the current Ethereum 2.0 design, there are some strategies for most people to review the blocks. This review is indistinguishable from a single block delay, and it is difficult to determine who is responsible.

The attack here is quite despicable, the attacker attacks some validators and makes them vote for another block, using other validators to vote for their own block, which actually contains the content to be reviewed … But their own votes are not enough to exceed 51%, so what they are trying to censor is never actually included. This is a multi-level indirect effect. In Ethereum 1.0 and Ethereum 2.0, a malicious party conducting a 51% attack can conduct censorship. When the censorship is strong enough, it is difficult to determine whether measures need to be taken.

Include Uncle Block

This is the most basic thing we can do at the moment: include uncle blocks. The idea here is that in Ethereum 1.0, blocks that do not belong to the blockchain can be included later, and the new solution is that we have added protocol rules, which means that transactions in uncle blocks will also be blocked. deal with.

Therefore, you have such a blockchain, in which uncle blocks are also included.

Idea: Timelyness Detector (TD)

Imagine if we could have at least an online client, then a client on the network could download things and communicate with other clients on a regular basis. Let them check to see if a block arrived on time.

If they see that a block arrived on time, and they see that the block has not been accepted by a link for a long time, then the block will be automatically disqualified. If a block does not arrive on time, then you can use it for a 51% rollback attack.

The idea is that the client locally detects whether a block arrives when it should, and uses it as information to determine the chain to follow.

Not every node can follow the protocol, because offline nodes will also exist. Unless a 51% attack is in progress, if no attack occurs, the winning blockchain will be a good chain. If the attack is happening and you are offline, then you almost have to check the social layer to see what happens What happened, but only a few participants will do so, others will have a fairly clear consensus.

Problem: Edge Attack

If you generate a block, no matter what the definition of the block is, it will arrive on time, and some nodes will see it arrive at different times. Therefore, nodes may not agree with a block "whether it has been reviewed too long" and a block "is it released on time", they may not agree with these time parameters.

Attackers can take advantage of this, leading to long-term disagreements over whether attacks occur, and bring many governance issues.

So this requires us to have a better timeliness detector (TD)

Improved Timeliness Detector (TD)

We return to the question of General Byzantium, back to a 1982 paper by Leslie Lamport. It turns out that this paper contains an algorithm, and people don't really talk about this algorithm, but they should probably talk more about it. It hides this sentence abstractly with unforgeable written information (referring to a digital signature). Lambert claims that he has a consensus algorithm that can tolerate up to 99% of erroneous attackers (that is, 99% of fault-tolerant consensus).

This algorithm is effective, and its advantage is that as long as you have synchronization assumptions, it can work, not only between consensus miners and validators, but also between miners and clients, and between clients and Between other clients. It has a stronger assumption about who should be online, and it uses this assumption to achieve a higher degree of fault tolerance, but it is a very dangerous assumption, and we are not willing to do it ourselves.

I will describe the version of a single prover. Here, assuming that one prover is honest, and then there are n provers in total, we only need 1 / n provers to be honest.

The idea here is that suppose a block is published, then the client and the prover have a deadline, and they need to receive the block before this deadline in order to consider the block to be on time. For the client, the deadline is t , and for the prover, the deadline is t+δ . So the proposer here will publish a block b. Let's assume that the proposer is a bit evil and tries to perform an edge attack. Node 1 sees it before the deadline, and node 2 sees it before the deadline. The prover sent the block, but due to network synchronization assumptions, if a node accepts the block, it means that the prover guarantees to accept the block before their deadline, because the block can be sent to Prover. If even one client thinks a block is timely, the prover will guarantee to see it before their deadline, so the prover will add their own signature, and due to network synchronization, the other client You will see a block with a signature before its expiration date.

The way to extend it to multiple provers is simple, you have many provers and the client will be t + δ * k. I have an article on eth.research dedicated to this research, so if you want to know more details, please feel free to check it out. Talk about the general idea, you have a group of attackers, and each attacker can delay the deadline a bit, so if an attacker receives a block, as long as the network delay is lower than your δ parameter, it will The timeliness of a block is propagated to the rest of the network.

Interesting facts

If you have such a timeliness detector, you will process all timely blocks in self-declared chronological order, and that's it. The only problem is that it takes a long block time. If you want to deal with deposits, withdrawals and forfeiture of validators, this may be an interesting protocol, but it is not the best protocol to run a blockchain.

To put it better, you can use the timeliness detector to detect attack chains and review attacks.

Summary

Anti-censorship is less perfect than other technologies because it does rely on the assumption of synchronization between the network and the client. You can set this duration to any time you want, but it has something to do with the level of censorship you are willing to tolerate. You can guarantee the consistency between the online node set. In the event of an attack, you can reach a consensus on whether a chain is an attack chain, and everything else. You can use this as a starting point for some social consensus to determine how to recover, which can help you assign stronger penalties to attackers because you can more reliably determine who the attackers are.

Generally, if an attacker publishes an unavailable chain, then the data availability check will catch it, if it publishes an invalid block, then a fraud proof can catch it, and if you conduct a long review of the block, then This chain will be automatically ignored by the network. If you review a medium-time block, then you can use the timeliness detector to deal with it cleanly, and if an attacker tries not to participate or destroy the committee, then the committee is not used accordingly.

Well, we have a series of tools that can basically reduce our fear of 51% attacks, or be able to ignore them, or recover from them. thank you all.

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