Topic: Majority is not Enough: Bitcoin Mining is Vulnerable - page 4. (Read 51020 times)

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.

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


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.

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.

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?


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.

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.

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.


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.



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.



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.


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

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.

In 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.

Why would you pursue a risky convoluted attack strategy that requires upfront investment and only works under arbitrary assumptions about barriers to entry. The strategy I suggest is essentially risk free. No upfront investment needed. Since there is no cost to attempt the loyalty program attack, it is worth attempting even if it has a miniscule chance of succeeding.

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

Don't quite agree with you here.
1)  Agreed
2)  Agreed. But it is important to note that the selfish pool suffers smaller losses than the others. Therefore rational wealth maximising agents who denominate their wealth in BTC would join this pool (were it not for your observation under Fail B which I will get to next).
3) The lower difficulty is open to all, but the other pools are still underperforming relative to the selfish pool. Rational miners still join the selfish pool. It is entirely possible that another selfish pool starts up, but far from being a threat to initial selfish pool operator, it is actually the best thing that could happen to him. Since the gains grow superlinearly both pools will mine more coins by joining forces than they would have otherwise. 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.


THIS is a critical observation, which I have not thought of or seen mentioned elsewhere.  Essentially PPS can invalidate the entire attack, since a rational miner would rather join a PPS pool, where he will earn even more income than from joining the selfish pool. One can reason that the PPS operator, (who takes the hit for all of the orphaned blocks) will cancel the service or put the price up enough to compensate. But this means that the attacker first needs to keep the attack up for long enough to drive all PPS operators out of business. Only when this is complete will rational miners flock to join the selfish pool. This makes PPS operators vulnerable to this attack, but it is not very different from the well known block-withholding attack that they have always been vulnerable to, in fact it is a little less serious since it can easily be detected. Also, if someone with deep pockets (Bitcoin Foundation? BTC guild?) publicly commits to keep at least one PPS operation afloat for the duration of any such attack, then the selfish pool attack suddenly becomes very unattractive indeed, since you need to incur a sustained loss (relative to what you could have earned with the same hashing power at a PPS pool), and only if you can sustain this loss for longer than the PPS operators can sustain the loss you are inflicting on them can the attack actually start recruiting other rational miners to help you. This is somewhat analogous to trying to enter a new market against an entrenched competitor who is committed to a strategy of predatory pricing i.e. they will sell their products at a loss until you eventually go bust or leave the market.


I actually think the paper is quite good. The attack is quite unlikely to work in practice, but the theory is incredibly important. The result  is counterintuitive, but undeniably correct. I've done my own calculations and simulations and arrive at the same results as they do. Some claim that the attack was known before, but I am afraid none of the rather vague hand-waving explanations of a mining cartel attack has managed to convince me that this is possible. The fairly basic math used in the paper convinced me in less than an hour.

Sounds like someone needs to tell coindesk how badly wrong they got this...

Unfortunately, it seems to get many facts wrong too...

• The timestamp in the block header is entirely ignored, and the block-discovered-first isn't reported at all (nodes know which they saw first, and that's all they care about)
• No mention of the fact that there are many better sybil attacks should sybil-ing be possible.
• The proposed solution doesn't limit pools to 25% (this isn't even theoretically possible).

Check, HorseRider is correct.

I would add that there is no guarantee that the selfish pool which invests to lower difficulty is the same selfish pool that reaps the reward from lower difficulty.

Once you treat the game as dynamic (which it is in reality), the attacker faces a free-rider problem.

The researchers just did a massive delete of critical comments from their blog posts.  At this point, they are really embarrassing their institution by overstating their results, and refusing to listen to reason.

It reminds me of the guy at HP, Vinay Deolalikar,  who "proved" NP!=P in August 2010, and then totally closed his mind to any suggestions that his chain of reasoning had some missing links.  His Web page still claims the result.

Some people.

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.  Despite the fancy pedigree of the email address in the page footer, I suspect that their paper has more to do with hubris, ignorance of physics and a serious lack of understanding of how bitcoin really works.

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?

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.  Amusingly, in a universe without latency in any form, which is the only universe where this model is meaningful, their solution is unnecessary, and actually counterproductive (since it causes the problem they aim to solve).

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:  We Know.  If an attacker is able to isolate a single node, they can fuck with that node.  If an attacker is able to isolate every node (lol), they can fuck with every node.  Note to researchers:  If anyone can control the spread of information across the entire network, they don't need whatever crazy scheme you've cooked up; they can already do much worse things.  In particular, if an attacker is capable of creating the conditions necessary for this garbage to work, they can just not forward any blocks but their own, and they multiply whatever skimpy hashing power they have by infinity and they gain total control over all mining.

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.

Sigh.  Is there even any point in addressing point two now?  Work is not cumulative.  Publishing a block does not make the rest of the network "start over".

+1

This is the kind of analysis that I think we need more of before jumping to the conclusion that there is actually a problem that needs to be fixed. I'm not claiming that HorseRider is correct, but his logic looks plausible and I tend to listen harder to reasonable people who say things like "please check whether my logic is right".

+1

http://hackingdistributed.com/2013/11/04/bitcoin-is-broken/


Posted on Monday November 04, 2013 at 03:10 PM by Ittay Eyal and Emin Gün Sirer

Bitcoin is broken. And not just superficially so, but fundamentally, at the core protocol level. We're not talking about a simple buffer overflow here, or even a badly designed API that can be easily patched; instead, the problem is intrinsic to the entire way Bitcoin works. All other cryptocurrencies and schemes based on the same Bitcoin idea, including Litecoin, Namecoin, and any of the other few dozen Bitcoin-inspired currencies, are broken as well.


I wonder if they've already added "broke Bitcoin" to their resumes.

Oh, I just read https://en.bitcoin.it/wiki/Getblocktemplate in more detail and I see what you mean.  At first I thought it only gave miners a read-only view of the pool's block.

This is would be fantastic to roll out.  I suppose a miner bonus scheme would not be enough to attract people to new GBT-based pools because your expected returns would be the same in the long run, in fact it just adds more unwanted variance, but there are other advantages like the small chance of mining one of your own (or your friends') transactions with 0 fees if you somehow integrated your wallet with your mining rig.

I hope miners make a sensible decision and require GBT with full ability to modify the merkle tree + miner bonus to incentivise immediate publishing of blocks.

This is essentially what GBT aims to do.

Would it be possible to reduce the centralised power from large pools through the following method?

- The pool simply provides the miner with the pool's payout address
- The miner can build whatever block they want, so long as it contains a coinbase output which pays the pool with amount (BLOCK_REWARD - MINER_BONUS).
- The miner bonus is a second output added to the coinbase transaction which the miner can pay to him/herself.  It could be 1% of the block reward or something like that.  This gives the miner a direct financial incentive to publish blocks they find immediately.
- The pool accepts the work from the miner so long as it contains the coinbase transaction that pays the pool.

* Possibly there could be some variation on this protocol so that the miner doesn't have to track transactions and build their own merkle tree.  Eg. the pool operator could provide a suggested merkle tree to the miner, and the miner just has to communicate any desired changes back to the pool operator, which reduces the bandwidth required.