Vitalik’s latest speech: Overlapping 51% attack becomes a deadly threat to PoW blockchain, PoS is the only way out

Editor's note: This article is from Babbitt, translated by Free and Easy, authored by Vitalik Buterin (V God), reproduced by Odaily with authorization.

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

image description

(Picture: Vitalik gave a speech at the 2020 Stanford Blockchain Conference)

The following is the content of Vitalik's speech:

What can a 51% attack do? There are different kinds of 51% attacks, and they can perform different operations on different applications and produce different results and consequences. One type of 51% attack you may be familiar with is rolling back a block. You make a transaction, you send money to an exchange, you trade those coins for another coin, you withdraw those coins, and you do a 51% attack, reverting your deposit transaction…

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

1. Other types of 51% attacks

1.1 Transaction review attack In fact, transaction review is another 51% attack! Given that layer 2 protocols and DeFi are both recent megatrends, transaction censorship becomes especially dangerous. In the environment of many layer 2 protocols (including plasma, channel, general state channel, lightning network, Optimistic Rollup, interactive computing, TruBit, etc.), review means theft!

So if you can vet challenge transactions, you can steal money from people. This doesn't apply to zk Rollup, but this attack does apply to the vast majority of protocols people are considering right now. Censorship is especially dangerous in the context of DeFi because it is a tool through which you can manipulate the market and then capture value.

If you could vet every single ethereum blockchain transaction that touched Uniswap, and then wait a day, the price of ether could be a little volatile, and I would be able to extract a lot of arbitrage value from this attack.

It can be said that censorship is dangerous, and in DeFi protocols and layer 2 protocols, transaction censorship can also be regarded as equivalent to theft.

1,2 Light Client Attacks A lot of people are running light clients, and if you're running a light client, a 51% attack could cause those light clients to accept chains that contain completely invalid transaction blocks. False signatures, malformed transactions, unauthorized signatures (stealing funds from one account and transferring them to other accounts), they can get usable blocks accepted by the network. 1.3 Data Unavailability Attacks Who here is familiar with data availability issues? Well, not everyone, but a lot of people got it. The idea here is that you can create a chain where you publish the block header. Light clients can see the chain, but cannot publish some or all of the data in block bodies. This is bad because if the data is not published then it may or may not be true and there is no way to generate proof to others that it might be true and you deny people who might want to create future transactions Information. That said, unusable blocks are also dangerous. 1, 4 Discouragement Attacks Discouragement attacks are a term that refers to maliciously disrupting other actors, causing them to lose income, and driving them to conspire with you, or be forced to quit. Selfish mining with more than 1/3 of computing power is an example of this. That said, a 51% attack is also a very powerful dissuading attack. 1.5 Regarding the non-tamperable modification of the blockchain, 51% attacks are very powerful, and this type of attack is a threat to the non-tamperable modification of the blockchain.

Who remembers this? An exchange has had a bunch of money stolen, and they're considering pushing for a one-day reversal of the Bitcoin blockchain in order to get it back. If something like this is possible, then things inside the blockchain could be reverted, and the blockchain loses its key properties of being a blockchain, which is scary.

Also, 51% attacks are not democratic, they are plutocratic, so as a democratic method, it does them no good.

2. 51% attacks that have occurred in reality, and the worst 51% attack scenario

In reality, a 51% attack can be done. This is a photo from the 2015 Hong Kong Bitcoin Scaling Conference. In this picture, some people who control 90% of Bitcoin's computing power are sitting together, posing an "I have power" posture, haha.

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

Spawn camp attack is actually the 51% attack we have seen so far, not the worst. A spawn camp attack is the worst nightmare scenario for this type of attack. Basically, you need to acquire 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 have had enough of this torture, and they will replace the proof-of-work (PoW) algorithm, since they have no way to build an ASIC in a short period of time, so you just need to rent a lot of CPU and GPU computing power to continue the attack, and then, The chain is dead unless they switch to Proof of Stake (PoS) or become something completely centralized.

3. Can the proof-of-stake (PoS) algorithm break this cycle?

This is a blog post I wrote in 2016 where I tried to describe the philosophy behind what Proof of Stake (PoS) is and why it is something 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), where 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 the proof-of-stake (PoS) system, your attack can be detected, and the deposit you lose is far greater than the pledge you can be fined.

They are put into Casper CBC and a range of other security deposit and slash-based proof-of-stake (PoS) algorithms. In theory, 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 trying to attack, you will be fined, if you want to do it again To launch an attack, you have to buy more coins, because you keep buying, then the rising price of coins will eventually cause you to go bankrupt, so from this perspective, instead of having attackers target PoW, our goal is to make The chain moves 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've been focusing on reversals of finality. This is fairly common in Byzantine fault-tolerant consensus theory. The basic idea is that if 2/3 of the parties are on one side and the other 1/3 are on the other... 1/3 of the validators have to send two conflicting messages, you can detect and penalize them. Still, it's about attacking in reverse.

What about other types of attacks? Invalid data, data unavailable, censorship, vandalism?

Let's work it out bit by bit, we're not going to care about the validity of the data, we're going to notice that if you have a guarantee of data availability and guarantee that if a block is part of the blockchain, then all All data can be downloaded by a node in the network. If you have censorship resistance, you publish a block, then it ends up being included, and from those two things, you get validity. The reason is interactive computing, Rollup, and these existing protocols. Basically, with Rollup, you publish all the data on-chain, and then the chain guarantees its availability, you have some fraud proof, and guarantee that if some computation is invalid, then you can issue an uncensorable fraud proof, and it gets processed on-chain . So the validity of the data is not so important, because the first layer (layer 1) and the second layer (layer 2) fraud proof can solve this problem.

If you can't censor other people's blocks, then you can't prevent them from being included in the blockchain. So Griefing shouldn't be much of a problem as long as the penalties for incentives are kept in check.

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

paperpaper, where I describe a scheme that basically allows blockchain clients to verify the availability of blockchain data without actually downloading all the data.

A simple straw man version of this scheme is this: the dumbest way to check if a block is available is to download the full thing. But here we're assuming a scalable, possibly sharded blockchain, where more than 2 MB/sec of data will be uploaded to the chain, and clients won't be able to download everything. For a client that wants to check data availability, all we have to do is test a random sample. It will randomly select some data fragments, such as 30 fragments, 40 fragments, 80 fragments... It will randomly select locations and ask for merkle proofs for these locations, as long as you receive valid replies from all the locations you accept, then You then 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, like here all the data on the left is available, here all the data on the right is available, then at least one of the checks will most likely fail.

With this scheme, an attacker is able to spoof a few specific clients. However, if an attacker tricks enough clients that they download the cotyledon data as half of the total data, those clients can continue to reconstruct the data from there.

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

Erasure coding This is where erasure coding comes in, so we're going to take the data, let's say it's a polynomial evaluation, we're going to evaluate the same polynomial at more points, now, any 50% of data is sufficient to recover all data. With this scheme, you can verify that the block is useful, and that the block is available at a potentially very large size, while personally 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.

Proving correctness So how to prove that a root is the root of this erasure coding? How do you prove that you didn't get junk data stuck in it? You can use fraud proofs, like this 2D one, and if you code it wrong, then someone can make a short fraud proof, and you can broadcast it to the network, and the network can reject the block. This 2D scheme was studied in 2017. More recently there's something about encoding merkle trees where you encode each level in the merkle tree, which has nice properties. There are also approaches that don't rely on fraud proofs, such as using STARKs or SNARKs to prove that the computation of the merkle root is correct, while another possibility involves polynomial commitments - you'll get your data, and you'll interpret it as a polynomial evaluation, you'd compute the polynomial, and then you'd do a whole bunch of polynomial-committed openings at a bunch of points, and your data availability check would be asking for 80 positions instead of 80 openings, or if You use clever algebra to get some kind of multi-opening, and you can get even more efficiency.

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

Sharding: Sharded blockchains that currently exist beyond committees usually rely on committees, the idea is that you have a bunch of nodes, you randomly pick some nodes, and you need most or most of them to be in a certain zone A block is signed so that the network accepts the block as valid.

The problem with any kind of committee-based scheme is that it will be subject to scrutiny by bad actors above a certain threshold. If we're going to talk about resistance to 51% attacks, then we're talking about a system where even if the majority starts the attack, then the minority should be able to continue the operating system itself.

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

Regarding the censorship, who is here, who wants to stop the censorship? Okay, there are a lot of people, so, the status quo is not very good. Here is an article by nrryuya, who has done some work on formally verifying ethereum, he wrote an article saying that in the current design of ethereum 2.0, there are some strategies for most people to review blocks, Such scrutiny is indistinguishable from single-block delays, making it difficult to determine who is responsible.

The attack here is rather nasty, the attacker hacks 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 censored... But they themselves don't have enough votes to get over 51%, so what they're trying to censor, will never actually be included. This is a multi-layered indirect effect. In Ethereum 1.0 and Ethereum 2.0, a malicious party doing a 51% attack can censor, and when the censorship is strong enough, it is difficult to determine whether something needs to be done about it.

Including uncle blocks This is the most basic thing we can do so far: include uncle blocks. The idea here is that in Ethereum 1.0, blocks that were not part of the blockchain could be included later, whereas the new scheme is that we add protocol rules that say transactions in uncle blocks are also included. deal with.

So, you have a blockchain where uncle blocks are also included.

Idea: Timeliness Detector (TD) Imagine if we could at least have online clients, clients on the network that could download stuff and communicate with other clients periodically. 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 chain for a long time, then the block will be automatically disqualified. If a block doesn't arrive on time, then you can use it for a 51% rollback attack.

The idea is that the client locally detects whether a block arrived when it was supposed to, and uses that 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 going on, if no attack is happening then the winning blockchain will be a good chain, if an attack is happening and you are offline then you pretty much have to check the social layer to see what happened What, but only a few participants will do it, others will have a fairly clear consensus.

Problem: Edge attack If you generate a block and it arrives on time no matter what the definition of the block is, some nodes will see it arrive at a different time. Therefore, nodes may disagree on whether a block "has been reviewed for too long" and whether a block is "published on time", they may disagree on these timing parameters.

And attackers can take advantage of this, causing others to have long-term disagreements about whether or not the attack happened, and bring up a lot of governance issues.

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

Modified Timeliness Detector (TD) We go back to the Byzantine Generals Problem, to the 1982 paper by Leslie Lamport. It turns out that the paper contained an algorithm that people didn't really talk about, but they probably should have talked about more. It hides this statement abstractly with an unforgeable written message (referred to as a digital signature). Lambert claims that he has a consensus algorithm that can tolerate up to 99% of faulty attackers (i.e. 99% Fault Tolerant Consensus).

This algorithm works, and the beauty of it is that it works as long as you have an assumption of synchronicity, not just between miners doing consensus and validators, but also between miners and clients, and 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's a very dangerous assumption that we don't want to make ourselves.

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

The idea here is, suppose a block is published, then clients and provers have a deadline by which they need to receive the block 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 here the proposer will publish a block b, let's say the proposer is kind of evil, trying to do a marginal attack, node 1 sees it before the deadline, node 2 also sees it before the deadline. The prover sent the block, but due to the network synchronicity assumption, if one node accepts the block, then this means that the prover is guaranteed to accept the block before their deadline, because the block can be sent to certifier. If even one client thinks a block is timely, the prover is guaranteed to see it before their deadline, so the prover adds their own signature, and due to network synchronicity, the other client Will see the block plus a signature before the deadline for a signed block.

articlearticleis dedicated to this area of ​​research, so feel free to check it out if you want more details. To give you a rough idea, you have a group of attackers, each of whom can delay the deadline a little bit, so if one attacker receives a block, then as long as the network delay is below your delta parameter, it will delay the The timeliness of a block propagates to the rest of the network.

Fun fact if you have this timeliness detector you process all timely blocks in self-declared chronological order and that's it. The only problem is that it takes a long block time, and if you want to handle validator deposits, withdrawals, and slashing, it might be an interesting protocol, but it's not the best protocol for running a blockchain.

Four. Summary

Four. Summary

The anti-censorship technique is not as perfect as the others because it does rely on a synchronization assumption between the network and the client, you can set this duration to whatever you want, but it's related to the level of censorship you're willing to tolerate. You can guarantee consistency across the set of online nodes, and in the event of an attack, you can agree on whether a chain is an attacking chain or not, and everything else. You can use this as the start of a partial social consensus to determine how to recover, which helps you assign a stronger degree of punishment to the attacker because you can more reliably determine who the attacker is.

In general, if an attacker publishes an unusable chain, then data availability checks will catch it, if they publish an invalid block, fraud proofs can catch it, and if you have a long review of blocks, then This chain will be automatically ignored by the network. If you review a medium-time block, then you can use the timeliness checker to cleanly process it, and correspondingly not use the committee if an attacker tries not to participate or destroy the committee.

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