Majority is not Enough: Bitcoin Mining is Vulnerable

[hannesnaude]

Ideally I'd like to think about it carefully, read the paper a few times, and run some simulations before commenting, but I'll likely be tied up at the IETF all week and people are already panicking and pushing for hasty changes in response to this which may be ill-advised, so I'm going to offer some preliminary comments here.

Please do run your simulations.  When you do, make sure that you faithfully simulate a network with latency.  The word latency exists in their paper exactly one time, as a casual aside in the solution section, which should immediately set alarm bells ringing in all of our heads.  In addition, they seem to suffer from the strange notion that work in bitcoin can be wasted. 

If I boot up my multi TH mining rig and start mining blocks from the genesis block onward, is my work not wasted? Does it contribute to network security? Will I earn any block rewards for the blocks I mine? As far as the rest of the network is concerned, I might as well not exist.

Let me start with latency.  As far as I can tell from the paper, their "simulation" (and here you should imagine me doing very sarcastic air quotes) involves a network where the evil miners have magically found a way to detect the competing block in the honest miner's memory, before it has begins to spread on the network.  Gamma seems to play some sort of role here, but the meaning of it seems to change from page to page.  Or at the very least between pages 8 and 11.  Can anyone give me a good justification for abusing this poor variable in this way?

I have taken a look and cannot for the life of me understand what is confusing you. Gamma is defined quite clearly:"We denote by gamma
the ratio of honest miners that choose to mine on the [selfish] pool's block, and the other (1-gamma) of the non-pool miners mine on the other branch." The variable is consistently used with this meaning. And your assertion that "the evil miners have magically found a way to detect the competing block in the honest miner's memory, before it has begins to spread on the network." is plainly false. The situation that you describe would correspond to a gamma of 0 (the worst case). But even when gamma is 1 (i.e. "the honest miners have magically found a way to always work on the honest block in the case of a tie") the attack works for an attacker with >33% of network hash power. I find the researchers' claim that a gamma of 1 is attainable by an attacker in the current bitcoin network to be tenuous at best, but this is not that important, since the attack works even for the best case where gamma=0.

The charts are very illuminating.  In figure 2, each of the simulation points is exactly on the calculated line.  This is a dead giveaway.  The only way that can happen is if their model is fully deterministic except for mining function.

BS I replicated this result and I can guarantee you that the mining function is not deterministic. Besides, your premise is laughable. How accurately can you really read that chart? Enough to say that the simulated results are within 1% of the predicted values? 0.1%? You can easily get simulation results accurate to a fraction of that in a modest amount of time on a dated single core machine. I know because I tried.

The real gold of this paper comes on page 13.  On page 13 they handwave over the latency issue by pointing out that an attacker could insert itself between every other node on the network.  Let me just sum up a few years of discussion on this topic...

Strawman. Nowhere on page 13 do they suggest that or anything that I can interpret as being equivalent to an attacker being required to "insert itself between every other node on the network". If you disagree please post the relevant quote. As stated earlier, I find their assertion that gamma close to 1 is attainable to be tenuous, but this is just a misrepresentation of their position.

Of course, everyone instantly sees how silly that is, so they had to dress it up in pseudo-scientific gibberish so that people would click on their crappy website and check out the douchebag's glamour shot.

Real mature. This is peer-review, is it?

[1713898710]

1713898710

[1713898710]

1713898710

[hannesnaude]

This process runs away and leads any pool  that starts with >33% to end up with >50%, at which point the classic 51% attack becomes possible.

So that's the 51% attack mentioned in Satoshi's paper. I can't see any originality here

No, you don't need to get to 51%. IF you do then you can control the network. But even if you just have 40% of the hashing power, you can make outsize profits and push other miners into loss making territory, which very likely gets you to 50%. But recruiting/buying 33% of the network hash power and relying on economies of scale to get you to 50% is very different from simply recruiting/buying 50% of network hashpower.

[hannesnaude]

You need to model this as a dynamic game with entry and exit. They do not do this. The methodology is inappropriate to the problem at hand. They are not qualified for this. This is an industrial organization problem, not a computer science problem.
Done appropriately you would almost certiainly end up with multiple equilibria and sensitivity to assumptions about entry costs for pools and switching costs for individual miners. Game theory tells you very little of use for these types of problems.

It may indeed be possible to build a better mathematical model of this than they did. It may indeed be a much better use of the time of someone who is "qualified for it", than bashing the model that they put forth. But the model that they put on the table is vastly better than what we had before to describe this strategy, namely some hand-waving. Disagree? Was the 33% figure known before?

You need to model this as a dynamic game with entry and exit. They do not do this. The methodology is inappropriate tIn any case, this is all artificial since there are ways of achieving the same aim without any upfront cost. It is hard to sensibly analyze a costly attack approach when cost-free attack approaches that achieve the same aim are available.

Consider a loyalty program where you record each worker's cumulative contribution to the pool. In the event the pool acquires 51%, you divide the 50% of surplus attack revenue according to some function of current hashing power and historical contributions. The loyalty program has no upfront cost at all. As long as the attack has a nonzero chance of succeeeing, the dominant strategy is to always join the pool. The more people join the more attractive joining becomes.

And if the pool doesn't reach 51%? The selfish mining pool provides larger payouts from day 1 (or at least from the first time that 33% is exceeded. So there is no need to trust the operator for anything beyond your next payment. And what exactly are the upfront costs of the selfish mining strategy that you refer to? BTC-Guild could implement this today with a few lines of code. To be clear, I don't think it would work. If they tried that it would probably destroy their business. But I don't see the up-front cost.

[cunicula]

If it were an interesing problem, yes. But it is not an interesting or relevant problem.

The upfront cost comes from yielding fewer blocks than average and either driving rational miners to PPS pools (and thus losing revenue as an honest pool operaror and failing as an attacker) or subsidizing miners by offering PPS yourself. Even if no PPS pool exists, people would create one. It would not be difficult to coordinate movement to such a pool. Coordination is almost costless in this setting. It is not reasonable to assume that everyone will be stuck receiving substandard block reward and just accept that. It is such a simple problem to fix.

The real and relevant problem is the 51% attack itself. This attack immediately doubles revenue for participants.

About what if the attack fails or you don't trust the pool op, etc. This is irrelevant.  The pool payouts are identical to a standard pool except in the case that the pool accumulates 51%. If you trust the pool with nonzero probability and believe the pool's attack has a nonzero probability of succeeding, then the strictly dominant strategy is to join the attacking pool.

These are extremely weak conditions. Basically, except in the edge case where everyone is 100% sure that an attack will never occur the unique equilibrium is a successful 51% attack. Even in the edge case a successful 100% attack is still an equilibrium. There is just also an unstable non attack equilibrium in this instance.

 This sybil attack, on the other hand, requires a whole host of assumptions about entry and switching costs in order for it to be a legitimate nash equilibrium. It is never going to be a robust prediction and would never be worth wasting money on experimenting with.

Let's put it this way: the attackers are currently armed with handgunds. The researcher is investigated harm that attackers could do if they chose to use knives instead of handguns. Such research is a waste of time.

[hannesnaude]

If it were an interesing problem, yes. But it is not an interesting or relevant problem.

.Yeah, I feel the same about NP!=P. I could probably solve it in an afternoon if I put my mind to it.

The upfront cost comes from yielding fewer blocks than average and either driving rational miners to PPS pools (and thus failing) or subsidizing miners by offering PPS yourself. 

As stated earlier, I agree that the existence of PPS pools makes this attack much less viable. But the existence of (reasonably priced) PPS pools is an assumption. Nothing in the protocol requires or guarantees it.

[cunicula]

As stated earlier, I agree that the existence of PPS pools makes this attack much less viable. But the existence of (reasonably priced) PPS pools is an assumption. Nothing in the protocol requires or guarantees it.

It is allowed by the protocol. That is all that is needed. I don't understand the use of game theory in computer science. It is always an attacker vs. A bunch of honest chaps who sit by and let themselves get fleeced. If someone can pop up and say "hey, honest chaps, let's take shelter in that cave. We will be better off and safe if we all go together." Then it's reasonable to guess that this is actually what will happen.

The problem is when there is an attack with no effective countermeasures. As in the true 51% attack. You know, the one that is actually a real problem.

[Meni Rosenfeld]

Lear, who has independently done much higher-quality research on the same issue, has posted a sample of his results:
https://bitcointalk.org/index.php?topic=325824

I recommend staying tuned for his complete work, which can serve as a more fertile ground for further discussion on the topic.

[hannesnaude]

As stated earlier, I agree that the existence of PPS pools makes this attack much less viable. But the existence of (reasonably priced) PPS pools is an assumption. Nothing in the protocol requires or guarantees it.

It is allowed by the protocol. That is all that is needed. I don't understand the use of game theory in computer science. It is always an attacker vs. A bunch of honest chaps who sit by and let themselves get fleeced. If someone can pop up and say "hey, honest chaps, let's take shelter in that cave. We will be better off and safe if we all go together." Then it's reasonable to guess that this is actually what will happen.

The problem is when there is an attack with no effective countermeasures. As in the true 51% attack. You know, the one that is actually a real problem.

And the "cave" or the countermeasure in this case is that one or more of the honest guys should bleed money operating a PPS pool at a loss until the attacker goes away. Errrm, yes that sounds like it will work.

[kjj]

Ideally I'd like to think about it carefully, read the paper a few times, and run some simulations before commenting, but I'll likely be tied up at the IETF all week and people are already panicking and pushing for hasty changes in response to this which may be ill-advised, so I'm going to offer some preliminary comments here.

Please do run your simulations.  When you do, make sure that you faithfully simulate a network with latency.  The word latency exists in their paper exactly one time, as a casual aside in the solution section, which should immediately set alarm bells ringing in all of our heads.  In addition, they seem to suffer from the strange notion that work in bitcoin can be wasted. 

If I boot up my multi TH mining rig and start mining blocks from the genesis block onward, is my work not wasted? Does it contribute to network security? Will I earn any block rewards for the blocks I mine? As far as the rest of the network is concerned, I might as well not exist.

Well done, you got me.  Work can be wasted if done at the wrong end of the chain.  If you read on to the end though, I clarify that expression.

Let me start with latency.  As far as I can tell from the paper, their "simulation" (and here you should imagine me doing very sarcastic air quotes) involves a network where the evil miners have magically found a way to detect the competing block in the honest miner's memory, before it has begins to spread on the network.  Gamma seems to play some sort of role here, but the meaning of it seems to change from page to page.  Or at the very least between pages 8 and 11.  Can anyone give me a good justification for abusing this poor variable in this way?

I have taken a look and cannot for the life of me understand what is confusing you. Gamma is defined quite clearly:"We denote by gamma the ratio of honest miners that choose to mine on the [selfish] pool's block, and the other (1-gamma) of the non-pool miners mine on the other branch." The variable is consistently used with this meaning. And your assertion that "the evil miners have magically found a way to detect the competing block in the honest miner's memory, before it has begins to spread on the network." is plainly false. The situation that you describe would correspond to a gamma of 0 (the worst case). But even when gamma is 1 (i.e. "the honest miners have magically found a way to always work on the honest block in the case of a tie") the attack works for an attacker with >33% of network hash power. I find the researchers' claim that a gamma of 1 is attainable by an attacker in the current bitcoin network to be tenuous at best, but this is not that important, since the attack works even for the best case where gamma=0.

What may have tripped me up was the way they describe gamma on the various pages.  When I was reading the paper, I was struggling to find a unifying theme for all of the ways they use gamma.  It seems to be a choice on one page, and then an expression of the natural race between competing blocks on the next.

In regards to latency, you seem to be missing a very important aspect of reality on the bitcoin network.  If you are sitting on a block, waiting for the rest of the network to find one so that you can publish yours, the signal that you need to act is also the signal that you have already lost.  Don't feel bad, this entire paper was written because of the same misunderstanding.  You can not win races by waiting for the rest of the network to pass you.

The charts are very illuminating.  In figure 2, each of the simulation points is exactly on the calculated line.  This is a dead giveaway.  The only way that can happen is if their model is fully deterministic except for mining function.

BS I replicated this result and I can guarantee you that the mining function is not deterministic. Besides, your premise is laughable. How accurately can you really read that chart? Enough to say that the simulated results are within 1% of the predicted values? 0.1%? You can easily get simulation results accurate to a fraction of that in a modest amount of time on a dated single core machine. I know because I tried.

I agree with you so much that I traveled back in time to do it.  What is fully deterministic in their model is everything else.  When a new block is found, gamma of the network switches to it, while 1-gamma switches to the attack block.  This is not reality.

The real gold of this paper comes on page 13.  On page 13 they handwave over the latency issue by pointing out that an attacker could insert itself between every other node on the network.  Let me just sum up a few years of discussion on this topic...

Strawman. Nowhere on page 13 do they suggest that or anything that I can interpret as being equivalent to an attacker being required to "insert itself between every other node on the network". If you disagree please post the relevant quote. As stated earlier, I find their assertion that gamma close to 1 is attainable to be tenuous, but this is just a misrepresentation of their position.

But a savvy pool operator can perform a sybil attack on honest miners by adding
a signicant number of zero-power miners to the Bitcoin miner network. These
virtual miners act as advance sensors by participating in data dissemination,
but do not mine new blocks.

"every other node" was hyperbole, but not far off from what it would really take.  If the bitcoin network was laid out like an efficient mesh on a flat sheet, you wouldn't need many sensors.  But the bitcoin network is tangled up like a wad of Christmas lights.

Of course, everyone instantly sees how silly that is, so they had to dress it up in pseudo-scientific gibberish so that people would click on their crappy website and check out the douchebag's glamour shot.

Real mature. This is peer-review, is it?

When you run to the press, you tell the world that you are no longer interested in civil peer review.  

[cunicula]

Lear, who has independently done much higher-quality research on the same issue, has posted a sample of his results:
https://bitcointalk.org/index.php?topic=325824

I recommend staying tuned for his complete work, which can serve as a more fertile ground for further discussion on the topic.

Thanks for pointing this out Meni. Based on the post, it looks like he is taking a more thoughtful approach to the topic.

[hannesnaude]

Well done, you got me.  Work can be wasted if done at the wrong end of the chain.  If you read on to the end though, I clarify that expression.

Work can be wasted whenever orphan blocks are produced. Orphan blocks do not contribute to network security, they do not pay their creators, and they are not relayed to the rest of the network.

What may have tripped me up was the way they describe gamma on the various pages.  When I was reading the paper, I was struggling to find a unifying theme for all of the ways they use gamma.  It seems to be a choice on one page, and then an expression of the natural race between competing blocks on the next.

In regards to latency, you seem to be missing a very important aspect of reality on the bitcoin network.  If you are sitting on a block, waiting for the rest of the network to find one so that you can publish yours, the signal that you need to act is also the signal that you have already lost.  Don't feel bad, this entire paper was written because of the same misunderstanding.  You can not win races by waiting for the rest of the network to pass you.

If you are trying to achieve gamma=1 then yes, the signal that you need to act is also the signal that you have already lost. But unless I am the VERY LAST node on the network to receive this block, it may be possible for me to get my block to other nodes that have not yet seen the honest block and in this way recruit at least some of the honest miners to work on my chain. Even if you do not agree with this seemingly obvious statement, it DOESN'T MATTER. Because as I am getting tired of pointing out, the attack still works for gamma=0. This is the case where we assume that I was indeed the very last node to receive the block and not a single honest node will compute a single hash on my block in the case of a tie. In this magical case I need 33% of network hash-power to earn excess rewards.

The charts are very illuminating.  In figure 2, each of the simulation points is exactly on the calculated line.  This is a dead giveaway.  The only way that can happen is if their model is fully deterministic except for mining function.

BS I replicated this result and I can guarantee you that the mining function is not deterministic. Besides, your premise is laughable. How accurately can you really read that chart? Enough to say that the simulated results are within 1% of the predicted values? 0.1%? You can easily get simulation results accurate to a fraction of that in a modest amount of time on a dated single core machine. I know because I tried.

I agree with you so much that I traveled back in time to do it.  What is fully deterministic in their model is everything else.  When a new block is found, gamma of the network switches to it, while 1-gamma switches to the attack block.  This is not reality.

Nope still wrong. In my simulation, nodes get allocated to mine on one block or the other with a probability of gamma of being assigned to the attacking block (you've got the logic of gamma reversed by the way) and I replicated their results perfectly. What is more, for the interesting cases gamma=0 and gamma=1, the two approaches are exactly the same.

"every other node" was hyperbole, but not far off from what it would really take.  If the bitcoin network was laid out like an efficient mesh on a flat sheet, you wouldn't need many sensors.  But the bitcoin network is tangled up like a wad of Christmas lights.

I don't really want to argue this point. As I have repeatedly stated I think that gamma->1 is extremely pessimistic and probably not achievable in the current network. But that is a red herring. The fact is that gamma->0 is extremely optimistic and even under those circumstances, the attack works. No Sybil attack is needed, so I wish we could stop discussing whether the Sybil attack is possible.

[runeks]

And the "cave" or the countermeasure in this case is that one or more of the honest guys should bleed money operating a PPS pool at a loss until the attacker goes away. Errrm, yes that sounds like it will work.

I'm not convinced by the PPS pool-argument either. As far as I can see - given that the selfish mining thing actually works - a PPS pool operator has two choices:

1. Investing in something that can, in a best case scenario, give him zero profit (an honest mining pool), and in a worst case scenario make him lose money (if the selfish pool wins)

2. Creating a selfish mining pool that can actually earn a positive profit, but also make him lose money

Which will he choose?

[David Rabahy]

What can I do to help?  I've tried to understand the topic.  To me it seems like there's a pretty small window (if any?) through which delayed block announcing can gain any advantage.  Clearly delaying too long is nonsense.  When is the block chain considered fixed?  Is 6 blocks the number of blocks required to be considered immutable?  Even with 100% of the hashing power no one can go back and rewrite the chain before some point, right?  If a new very fast miner comes along and picks some historic point in the chain and computes a longer fork, i.e. they catch up to the rest of the miners (an impressive amount of computing power), are the rest of us obliged to accept it?

What I do see is the need for a reliable and vigorous development community to respond/handle each and every threat.  How can we ensure that community is and remains reliable and isn't compromised?  I am willing to run a variant of the client if it would help secure Bitcoin against delayed block announcing.  Or I will ignore the threat if the consensus of the development community points in that direction.  How can we be sure what the consensus is?

[cunicula]

And the "cave" or the countermeasure in this case is that one or more of the honest guys should bleed money operating a PPS pool at a loss until the attacker goes away. Errrm, yes that sounds like it will work.

I'm not convinced by the PPS pool-argument either. As far as I can see - given that the selfish mining thing actually works - a PPS pool operator has two choices:

1. Investing in something that can, in a best case scenario, give him zero profit (an honest mining pool), and in a worst case scenario make him lose money (if the selfish pool wins)

2. Creating a selfish mining pool that can actually earn a positive profit, but also make him lose money

Which will he choose?

Ehh, if an honest mining pool earns zero profit, then there is free entry in the creation of mining pools and miners switch between pools readily. In this case the selfish pool can't earn a profit either. Someone else can just establish another selfish pool that offers a slightly better deal to miners. Miners will all migrate to the new selfish pool. Repeat until profits reach zero.

The selfish pool would have to undercut PPS pools' margins to enter in the beginning (otherwise it couldn't attract any miners). Since the selfish pool has lower mining output, this requires an upfront investment. The selfish pool has to take a loss to begin with. If there are no profits to be had and you have to take a loss upfront, then you would never see a selfish pool in practice. It is just money down the drain.

If an honest mining pool earns positive profit, then there are some barriers to entry and that probably means miners are more reluctant to switch between pools. In this case, you have a lock-in affect. Just having an event that causes everyone to switch to your pool is a substantial gain for the PPS pool operator. It is worth taking a loss to establish yourself as the dominant pool. If you were the dominant pool to begin with, it is also worth taking a loss to defend this position. I do not think such a lock-in would apply to the selfish pool (the lock-in is probably mostly about trust and people would quite reasonably distrust this entity)

Finally, there is no reason to assume that the honest mining pool plays honest. The PPS pool could also just perform a 51% attack on the selfish mining pool. I think a temporary retaliation would be accepted by the community. Such a tit-for-tat sets a good precedent. In this case, the PPS pool can earn large profits from conducting the attack. These could be split between the PPS miners and everyone else.

The real problem is if someone malicious does a 51% attack, but this has always been a problem and it has nothing to do with selfish mining. There have always been ways of using pools to create a 51% mass of hashing power to execute such an attack (see the loyalty program discussed above). The selfish pool business is an irrelevant non-issue. If you are not concerned about the loyalty program (which is a dominant strategy under extremely general assumptions), then you should definitely not be concern about the sibyl attack (which would cost the attacker money upfront and probably fail in practice)

[kjj]

I'm calling for (and have pledged a bounty for) a network simulator with latency.

I don't believe for a minute that this is economically efficient based on the output of an iterated finite state machine.  Gamma is not a property of the network, it emerges unpredictably during each race from the chaos of the network.

[revans]

I'm calling for (and have pledged a bounty for) a network simulator with latency.

I don't believe for a minute that this is economically efficient based on the output of an iterated finite state machine.  Gamma is not a property of the network, it emerges unpredictably during each race from the chaos of the network.

Surely it would be simpler and more empirical to simply create a selfish miner and let it loose and see what happens

[kjj]

I'm calling for (and have pledged a bounty for) a network simulator with latency.

I don't believe for a minute that this is economically efficient based on the output of an iterated finite state machine.  Gamma is not a property of the network, it emerges unpredictably during each race from the chaos of the network.

Surely it would be simpler and more empirical to simply create a selfish miner and let it loose and see what happens

Agreed.  The image that comes to mind is the guy selling his method for beating the stock market.  If it worked, he wouldn't need to sell it.

[gyverlb]

What can I do to help?  I've tried to understand the topic.  To me it seems like there's a pretty small window (if any?) through which delayed block announcing can gain any advantage.  Clearly delaying too long is nonsense.

Time isn't really an issue, the only condition behind the decision in withholding an alternate chain is the difference in block height. See below for checkpoints but they don't change this much.

  When is the block chain considered fixed?  Is 6 blocks the number of blocks required to be considered immutable?

No: Bitcoin nodes accept to rewind the chain by any length if the replacement chain is longer.
That said the official Bitcoin client has checkpoints to avoid arbitrary long rewrites: you can't rewind past the last checkpoint. New versions of the official Bitcoin client often come with new, more recent checkpoints.

[runeks]

The selfish pool would have to undercut PPS pools' margins to enter in the beginning (otherwise it couldn't attract any miners). Since the selfish pool has lower mining output, this requires an upfront investment. The selfish pool has to take a loss to begin with. If there are no profits to be had and you have to take a loss upfront, then you would never see a selfish pool in practice. It is just money down the drain.

I'm not sure I follow. Yes, the selfish mining pool needs an upfront investment. But - again, if we assume this attack is valid - it has the prospect of earning more than it pays to its miners, because it's using the selfish approach.

The most any mining pool can pay per share is block_rewards/num_shares, which would mean it's paying out all its income to the miners - zero profit. If a selfish mining pool can earn 50% of the block rewards while only needing 40% of the network hashrate (which the paper claims), it can afford to pay more per share than an honest mining pool (which only gets 40% of the block rewards with 40% of the network hashrate).

As far as I can see, an honest PPS pool somehow "fighting" selfish mining pools by paying out more than it earns, only means that the selfish pool needs to wait until the honest pool has no more money.

[cunicula]

The selfish pool would have to undercut PPS pools' margins to enter in the beginning (otherwise it couldn't attract any miners). Since the selfish pool has lower mining output, this requires an upfront investment. The selfish pool has to take a loss to begin with. If there are no profits to be had and you have to take a loss upfront, then you would never see a selfish pool in practice. It is just money down the drain.

I'm not sure I follow. Yes, the selfish mining pool needs an upfront investment. But - again, if we assume this attack is valid - it has the prospect of earning more than it pays to its miners, because it's using the selfish approach.


As far as I can see, an honest PPS pool somehow "fighting" selfish mining pools by paying out more than it earns, only means that the selfish pool needs to wait until the honest pool has no more money.

The selfish mining pool makes an upfront investment and gets what exactly for this? Is there some state authority protecting the selfish pool from competition?

If you pay money to do X and I can not pay money and still capture the benefit from X, then you will never pay money to do X. The existence of the PPS pools implies that the selfish pool has to front some cash at the outset to retain miners.

If you are going to tell me that other selfish pools cannot enter and steal miners from selfish pool (1), then I am going to tell you that this implies that it is worth operating an honest PPS pool to fight a selfish mining pool by paying out more than it earns. You are essentially saying that the game is dynamic and that it is valuable to retain miners and carry them into the next period. If so, it can be worthwhile to do so at a loss.


Honestly, though I think the free entry into pools scenario is more realistic.