|
From February 20th to 22nd, Beijing time, the 2020 Stanford Blockchain Conference hosted by Findora was held at Stanford University. The conference focused on security engineering and risk management methods in blockchain systems, and explored ways to improve the security of blockchain systems through the application of encryption technology, decentralized protocols, formal methods and empirical analysis.
On the second day of the meeting, Ethereum co-founder Vitalik Buterin delivered a speech titled "Beyond the 51% Attack". During the meeting, he first mentioned the different types of 51% attacks, such as the most common rollback attack, as well as censorship attacks, light client attacks, dissuasion attacks, and the most serious spawn camp attack. He believes that proof-of-work (PoW) cryptocurrencies are vulnerable to these attacks, while proof-of-stake (PoS) cryptocurrencies can detect attack chains and censorship attacks through technologies such as 99% fault-tolerant consensus and timeliness detectors (TD), thereby eliminating the threat posed by 51% attacks. (Photo: Vitalik’s speech at the 2020 Stanford Blockchain Conference)
Here is Vitalik’s speech:
What can a 51% attack do? There are different kinds of 51% attacks, and they can do different things to different applications, with different results and consequences. One type of 51% attack you might be familiar with is rolling back a block. You make a transaction, send money to an exchange, then exchange those coins for another coin, you withdraw those coins, and then perform a 51% attack to revert your deposit transaction...
This is the main type of 51% attack we have been discussing for the past 10 years and the one we think about the most.
1. Other Types of 51% Attacks
1.1 Transaction Censorship Attack
In fact, transaction censorship is another type of 51% attack! Given that layer 2 protocols and DeFi are both recent mega trends, transaction censorship has become particularly dangerous. In many layer 2 protocol environments (including plasma, channels, generalized state channels, lightning networks, optimistic rollups, interactive computations, TruBit, etc.), censorship means theft!
So if you can censor challenge transactions, then 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. In the context of DeFi, censorship is particularly dangerous because it's a tool through which you can manipulate the market and then extract value.
If you could censor every single Ethereum blockchain transaction that touched Uniswap and then wait a day, then the price of Ether might fluctuate a bit and I would be able to extract a ton 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 considered equal to theft.
1.2 Light Client Attack
A lot of people are running light clients, and if you are running a light client, a 51% attack could cause those light clients to accept chains that contain blocks with completely invalid transactions. Bad signatures, malformed transactions, unauthorized signatures (stealing funds from one account and moving them to other accounts), and they could get valid blocks accepted by the network.
1.3 Data unavailable attack
Who here is familiar with the data availability problem? Well, not everyone, but a lot of people are familiar with it. The idea here is that you can create a chain where you publish block headers. Light clients can see this chain, but they can't publish some or all of the data in the block bodies. This is bad because if the data is not published, then it may or may not be correct, and there is no way to generate proof to prove to others that it may be correct, and you are denying people information that they may want to create future transactions with. That said, unavailable blocks are also dangerous.
1.4 Dissuade Attack
Discouragement attack is a term that refers to maliciously sabotaging other participants, causing them to lose income and drive them to collude with you or be forced to withdraw. Selfish mining with more than 1/3 of the computing power is an example of this. In other words, a 51% attack is also a very powerful dissuasion attack.
1.5 About the immutability of blockchain
Therefore, a 51% attack is very powerful, and this type of attack is a threat to the immutability of the blockchain.
Who remembers this? An exchange had a bunch of money stolen from them, and they were considering pushing a one-day reversal of the Bitcoin blockchain to get the money back. If something like this were possible, then things inside the blockchain could be reverted, and the blockchain would lose its key properties as a blockchain, which is scary.
Also, 51% attacks are not democratic, they are plutocracy, so as a democratic method, it does them no good.
2. 51% attacks that have occurred in reality, and the worst 51% attack scenarios In reality, 51% attacks can be accomplished. This is a photo from the Hong Kong Bitcoin Scaling Conference in 2015. In this photo, some people who control 90% of Bitcoin's computing power sat together, posing as if they had the power. Haha.
A 51% attack can be accomplished. For example, ETC, Bitcoin Gold, etc. have all experienced 51% attacks. I am sure I missed 1-2, but these attacks have already happened.
Spawn camp attack
The reality is that the 51% attacks we've seen so far are not the worst. The spawn camp attack is the worst nightmare scenario for this type of attack. 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. Eventually, the community will get tired of this torture, they will switch the proof of work (PoW) algorithm, and since they can't build ASICs in a short period of time, you just rent a lot of CPU and GPU computing power to continue attacking, and then the chain will die 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 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, which is different from Proof of Work, where you only have rewards, so your penalty for participating in an attack or not participating in an attack is only the block reward. In a Proof of Stake system, your attack can be detected and you lose a lot more deposit than you can be fined for your stake.
They are put into Casper CBC and a bunch of other proof-of-stake (PoS) algorithms based on security deposits and slashing. The goal of this design is, in theory, to make 51% attacks extremely expensive. Basically, if 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 attacking, you will be slashed, and if you want to attack again, you have to buy more coins, and because you keep buying, the rising coin price will eventually make you bankrupt, so from this perspective, instead of having attackers targeting PoW, our goal is to get the chain to PoS.
What about other types of attacks?
Now let's talk about the first question, how does PoS solve other types of attacks? So far, we have been focusing on finality reversal. This is quite common in Byzantine fault tolerant consensus theory. The basic idea is that if 2/3 of the party is on one side, and the other 1/3 is on the other side... 1/3 of the validators must send two contradictory messages, and you can detect and punish them. However, this is about reversal attacks.
What about other types of attacks? Data invalidation, data unavailability, censorship, and malicious sabotage?
Let's tackle this piece by piece, we're not going to care about the validity of the data, we're going to notice that if you have data availability guarantees and a guarantee that if a block is part of the blockchain, then all the data in that block can be downloaded by a node in the network. If you have censorship resistance, you publish a block, then it will eventually be included, and from these two things, you get validity. The reason is interactive computation, 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 proofs, and guarantee that if some computation is invalid, then you can publish an uncensorable fraud proof and get it processed on-chain. So the validity of the data is not that important, because fraud proofs on layer 1 and layer 2 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. Therefore, as long as the incentives and penalties are effectively controlled, then malicious damage (Griefing) will not be a big problem.
We can boil it down to two things: data availability attacks and censorship attacks.
Invalid data and data unavailable
This is a paper I co-authored with Musalbas et al. in 2017, where I described a scheme that essentially allows blockchain clients to verify the availability of blockchain data without actually downloading all the data.
The simple straw man version of this scheme goes like this: the dumbest way to check if a block is available is to download the whole thing. But here, we're assuming a scalable, possibly sharded blockchain where more than 2 MB/sec of data is being uploaded to the chain, and clients won't be able to download all of it. For a client that wants to check the availability of data, what we do is we do a random sampling test. It'll randomly pick some pieces of data, like 30 pieces, 40 pieces, 80 pieces... It'll randomly pick locations and ask for merkle proofs for those locations, and as long as you get valid replies from all the locations you accept, then you'll accept the block as valid.
If you accept a block using this scheme, then you know with high probability that the block is valid. If less than 50% of the data is available, such as all the data on the left here is available and all the data on the right here is available, then at least one of the checks will most likely fail.
With this scheme, the attacker can fool a few specific clients, but if the attacker fools enough clients so that they download half of the leaf data, then those clients can continue to reconstruct the data from there.
This doesn't prove that the block is fully available, it may be missing parts, but it does prove that at least half of the block is available. It would be great if we had some technique to recover the entire 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, and now, any 50% of the data is enough to recover all of the data. With this scheme, you can verify that blocks are useful and blocks are usable at potentially very large sizes, while individuals are downloading 20-200 KB of data.
That’s part 1. This includes data availability attacks, which is part of the Ethereum 2.0 sharding solution, which allows us to at least 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 didn't jam garbage data in there? You can use fraud proofs, like this 2D one, where if you encode 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 started to be studied in 2017. More recently there's been some stuff about encoding merkle trees, where you encode every level in a merkle tree, which has nice properties. There are also ways that don't rely on fraud proofs, like using STARKs or SNARKs to prove that the computation of the merkle root is correct, and another possibility involves polynomial commitments - you'd take your data, you'd interpret it as the evaluation of a polynomial, you'd compute the polynomial, and then you'd do a bunch of openings of polynomial commitments 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, you can get much higher efficiency.
The benefit of these schemes is that they do not rely on fraud proofs, so the schemes used to verify block data have already been published and they no longer have any additional latency assumptions built in.
Sharding: Beyond the Committee
The sharded blockchains that exist today typically rely on committees, and the idea is that you have a whole bunch of nodes, and you randomly draw some of them, and you need a majority or a supermajority of them to sign off on a block in order for the network to accept that block as valid.
The problem is that any committee-based scheme will be subject to censorship by bad actors above a certain threshold. If we are talking about resistance to 51% attacks, then we are talking about a system where even if the majority starts an attack, the minority should be able to continue operating the system itself.
Sharding schemes with fixed thresholds don’t really help you here. So the solution here is that the protocol needs to rely more fully on a set of data availability checks rather than relying on committees.
About Review
Who in the room wants to prevent censorship? Yes, there are a lot of people, so the status quo is not very good. This is an article by nrryuya, who has done some work on formal verification of Ethereum. He wrote an article saying that in the current Ethereum 2.0 design, there are some strategies that allow the majority to censor blocks. This censorship is indistinguishable from a single block delay, and it is difficult to determine who is responsible.
The attack here is pretty shady, the attacker hacks some validators and gets them to vote for another block, using other validators to vote for their own block which actually includes the content to be censored... but they don't have enough votes themselves to exceed 51%, so the content they are trying to censor, will never actually be included. This is multiple levels of indirection. In both Ethereum 1.0 and Ethereum 2.0, a malicious party with a 51% attack can censor, and when the censorship is strong enough, it is difficult to determine whether or not to do something about it.
Include uncle blocks
This is the most basic thing we can do right now: include uncle blocks. The idea here is that in Ethereum 1.0, blocks that were not part of the blockchain could be included later, but the new scheme is that we add protocol rules that say that transactions in uncle blocks will also be processed.
So, you have a blockchain like this, in which uncle blocks are also included.
Idea: Timeliness Detector (TD)
Imagine if we could at least have clients online, clients on the network that could download stuff and periodically communicate with other clients to check if they saw a block arrive on time.
If they see that a block is arriving on time, and they see that block has not been accepted by a chain for a long period of time, then the block is automatically disqualified. If a block does not arrive on time, then you can use it to do a 51% rollback attack.
The idea is that the client locally detects whether a block arrived when it was supposed to arrive, and uses that as information to determine which chain to follow.
Not every node can follow the protocol because there will be offline nodes. Unless there is a 51% attack going on, if there is no attack happening then the winning blockchain will be the good chain, if an attack is happening and you are offline then you pretty much have to check the social layer to see what is going on but only a few participants will do that and the rest will have a pretty clear consensus.
Problem: Edge Attacks
If you generate a block and it arrives on time, whatever the definition of that block is, some nodes will see it arrive at different times. So nodes may disagree about whether a block was censored for too long, and whether a block was published on time, and they may disagree about those timing parameters.
An attacker could exploit this to cause long-term disagreements among others about whether the attack occurred, and bring about many governance issues.
Therefore, this requires us to have a better timeliness detector (TD)
Improved Timeliness Detector (TD)
We go back to the Byzantine Generals Problem, to a 1982 paper by Leslie Lamport. It turns out that this paper contains an algorithm that people don’t really talk about, but they probably should. It hides this in the abstract with unforgeable written messages (digital signatures). Lamport claims that he has a consensus algorithm that can tolerate up to 99% of bad attackers (i.e. 99% fault tolerant consensus).
This algorithm works, and its advantage is that it works as long as you have assumptions about synchronicity, not just between the miners and validators doing the consensus, but also between miners and clients, and between clients and other clients. It has a stronger assumption about who should be online, and it uses that assumption to get a higher degree of fault tolerance, but it's a very dangerous assumption that we're not willing to make ourselves.
I will describe the single prover version, where we assume that one prover is honest, and then if there are n provers, we only need 1/n of them to be honest.
The idea here is that let's say a block is published and then the client and the prover have a deadline by which they need to receive the block in order to consider the block to be timely. For the client, the deadline is t and for the prover, the deadline is t+δ. So here the proposer will publish a block b and we'll assume the proposer is a bit evil and tries to do an edge attack where node 1 sees it before the deadline and node 2 also sees it before the deadline. The prover sends the block but due to the network synchronicity assumption, if there is one node that accepts the block then that means the prover is guaranteed to accept the block before their deadline because the block can be sent to the prover. If even one client considers a block to be timely then 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 of a signed block.
The way to scale this to multiple provers is simple, you have a lot of provers and the client will be t+δ*k. I have a post on eth.research dedicated to this research, so if you want to know more details, feel free to check it out. The general idea is that you have a set of attackers, each of which can delay the deadline by a little bit, so if one attacker receives a block, then as long as the network latency is below your δ parameter, it will propagate the timeliness of a block to the rest of the network.
Interesting Facts
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 requires very long block times, which can be an interesting protocol if you want to handle deposits, withdrawals, and slashings for validators, but it's not the best protocol for running a blockchain.
Better said, you can use timeliness detectors to detect attack chains as well as censorship attacks.
4. Summary Anti-censorship technology is not as perfect as 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 is related to the level of censorship you are willing to tolerate. You can guarantee consistency between the set of online nodes, and 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 the beginning 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 the attacker publishes an unavailable chain then data availability checks will catch it, if they publish invalid blocks then fraud proofs can catch it, if you censor blocks for a long time then the chain will automatically be ignored by the network, if you censor a block for a medium time then you can use timeliness detectors to handle it cleanly, if the attacker is trying to not participate or subvert the committee then don't use the committee.
So there we have it, a set of tools that basically should make us much less afraid of 51% attacks, or be able to ignore them, or recover from them. Thank you, everyone.
|
