Topic: Majority is not Enough: Bitcoin Mining is Vulnerable (Read 51057 times)

1: If the solution were to randomize what chain to work on in a tie, why wouldn't the selfish pool
try to create multiple chains by having subpools work on finding hashes for separate blocks?

2: In general, holding on to a block for some period after finding it, looks like a potential advantage
is working on the next block.  Why not have all the nodes do this as normal operation?

As I understand it, the block reward cannot be spent right away.  There have to be a certain number of blocks built upon it, 6?, before it can be spent.

So this is more of a miners issue right?  How are orphan block rewards handled now?  What I mean is if I solve a block and get the reward and go gamble it at satoshi dice immediately does this "attack" somehow nullify that block reward afterwards and basically I succeeded at a double spend?  Or the block never hits the blockchain and the "attack" is designed for me to waste my hashing power?

I think you mean you don't do that.




This is not a new idea at all.  As far as public postings, it's been on this page on the bitcoin wiki for at least six months, and there was definitely a mention of it on bitcoin-dev about a year ago (I will post the reference when I find it).  And, as I've mentioned, it's pervasive in the modified clients used by large mining operations, although those are not public so you're welcome to shout "liar liar pants on fire" all you like and I won't get upset



I think the people who wrote this paper took Satoshi's original whitepaper too literally:


Mining strategy has evolved and adapted, as it must in any incentive-driven system.  For example, Satoshi's whitepaper predicted that transaction fees would be a meaningful incentive, and it's pretty obvious it hasn't turned out that way.

I don't think even the authors claim this attack can be used to take bitcoins away from those who already have them.

The main problem is the BTC loosers, the people that had a sizeable amount of BTC stored and that now have nothing. It will then be time to steal it or to sell them anything for BTC or to retaliate somehow. So no, Bitcoin mining is not vulnerable. Bitcoins are a risky investment.

I understand how the weight is reset to 0. But I can't understand how signature fees will be distributed.
If there's a thread discussing it, please point it to me. Thanks.

Recently, a dire prediction came out from a couple of computer science researchers about bitcoin's security. Game theory says  'We're all Doomed' or so they claim.

This is eerily similar to what happened when game theory was first applied to the study of nuclear war. Early researchers modeled nuclear war as a winner take all game. In this story, once a nuke drops, one of players is erased from the map. Game over for them. If you face certain and immediate obliteration, the only workable strategy turns out to be a pre-emptive strike. The CIA found this quite alarming!

Later, as the study of games became more advanced, the model was tweaked to add a bit of realism. Instead of obliterating the enemy, the nuke just harms them and they have an opportunity to strike back in the next round. With this simple twist, the game becomes like "Groundhog Day"; there is never any end to it.

When we play a game over and over again new kinds of strategies emerge. The most familiar one is tit for tat retaliation. "If I got nuked last year, I'll nuke back this year. If I didn't get nuked, then I won't nuke back this year."
This strategy is both familiar in everyday life and famous in theory. That's because it works. Under tit for tat, you can avoid getting nuked by maintaining an arsenal, but never using it.

Okay, so what about bitcoin. The authors of "Majority is not enough..." analyze bitcoin as a static one-off game just like early researchers considering nuclear war. Unsurprisingly, they issue dire predictions. In their one-off world, there is never any way of retaliating against bad actors. Players just pick between "attack" and "honest." It should be no surprise that the unconditional pacifist strategy is never successful. Indeed, always attack is the only possible equilibrium in a one-off setting.
Most people can see this intuitively, even if they have never studied game theory.

Let's add in some realism. In particular, let's think about mining every day instead of just as a one-off event. This allows for retaliation. Suppose instead we play, "if some anonymous guy fucked us by playing selfish yesterday, then we will also play selfish because it makes no sense to keep getting fucked." and "if no one played selfish yesterday, then we will play honest."

This strategy (where we condition actions on previous play) is an incentive compatible subgame perfect nash equilibrium. Yes, you heard it, the authors' claimed key contribution is erroneous and stems from a fundamental and elementary misunderstanding of game theory. Cooperation is sustainable as long as we retaliate against the bad guys.

Now, wait you say, we don't know who the bad guys are. How can we retaliate? This is the magic point. We don't need to know who the bad guys are to hurt them. If 25% of hashing power is doing selfish mining, we may not know who the bad guys are, but we do know that they own an ASIC (unless you think 25% of ASICs can be simultaneously liquidated within a single day at fair market value). The ASIC they own is valuable. When we play selfish, we turn into a paperweight. And that is how retaliation works. Players respond to selfish play by turning selfish and this causes all ASIC owners to take capital losses. The market value of their equipment depreciates with bitcoin prices. Ownership of ASICs means that miners cannot help but have a permanent stake in the system. 

Now, wait you say, this will also hurt innocent players who were not involved in the attack. Even though retaliation harms innocent people, it is still the best option for people who have been attacked. War hurts innocent people. But fighting back is the only possible equilibrium response after an attack occurs (one can set a threshold for a response, but there's always a tipping point where rational people have had enough and choose to fight back.)

Okay, so let's review and make things more concrete. Let's see. Say there is some consensus threshold for a 'successful attack.' You can ask Gavin exactly what the threshold is. Maybe we'd allow him to determine this. I would guess it is around the level that makes a short-term attack earn positive profit.

Consider a miner's options:

If I join an attack and the attack succeeds, tomorrow and the day after that and possibly for all days following we will have selfish mining. Should I care? Yes, today, my ASIC is expensive. Not worth a day of profits, if tomorrow all I have left are a day's worth of selfish mining income in USD and a brand new paperweight.

If I join an attack and the attack fails, then tomorrow we will still have happy days, but I will not have gained any short-term profit from participation. In fact I will have lost revenue. So clearly this is also a no go.

That leaves us with the last option: honest mining. Assume that everyone else approached the problem like me. You can see by reading most comments that they do (even if they don't formally understand why).

If I do not join an attack, then I will earn a fair profit and, as long as everyone else has approached the problem rationally, then tomorrow we will have more happy days of honest mining. And the next day too and the day after...

So what's my dominant strategy? Be honest until someone attacks me and then retaliate as necessary. There are many different sustainable ways of organizing retaliation besides tit for tat. Norms on how to retaliate vary across societies. I trust that the community, and Gavin in particular, could make reasonable judgements on this front. And that is all we need to succeed.

tl;dr bitcoin only has to worry about terrorists; rational miners will never attack, ever*. *(as long as there is modest mining reward)

If you'd like to see some math on this topic, then check out:

http://www.scribd.com/doc/182399858/Cunicula-s-game-theory-primer-pdf

PS. I could use help on the authors' site, 
hackingdistributed.com

The author is aware of my critique, but is refusing to respond. In fact, he deleted the link to my pdf the first time I posted it. As a community, I'd appreciate help in demanding a response from him. Go to the blog and ask questions about how repeated play and retaliation affect his results. When you see these questions, upvote them.

If the community will not help, then I will have to go the long route of posting a formal academic comment on arxiv. This is time consuming. Because I am an economist, arxiv has no positive benefits for my reputation or career. I'm asking for some help so that we can get this addressed in the media and blogosphere without a prolonged academic back and forth.

My proposal very clearly and explicitly penalizes stakeholders who try to sign conflicting blocks. This line has been there for 1.5 years - "If an address signs two conflicting blocks, its weight is reset to 0. This is to limit the power of malicious stakeholders. "

I'm not saying this will work perfectly, but to claim that no consideration has been made to this issue is, as cunicula says, dishonest.

Research into PoS methods is still ongoing.

Proof of stake has thus far proven unworkable.

The main problem with Proof of Stake appears to be that is that there is nothing at stake:  In PoW systems you burn energy to mine, and that mining is only worth while if the chain your mining on survives long term, so you are generally incentive mine the chain most likely to survive. In PoS the rational strategy is to mine all possible forks constantly, because doing so costs you nothing.

Probably. But it was never very difficult to begin with. Moreover there are other ways of destroying bitcoin that make much more sense.

Say I'm the US gov't out to destroy bitcoin.

Step 1) Make it illegal and start rounding people up. Watch price plummet.
Step 2) Buy up hardware and conduct 51% attack on the cheap to neutralize remaining participants. [Once price plummets the used ASIC devices will be very, very cheap.]

In my opinion, bitcoin cannot survive if the US gov't decides to take the ax to it. I don't think this is going to happen. I also don't think that it will make sense for a private actor to do this. (many different guys will benefit from burying bitcoin, but they are not going to be able to coordinate an attack aside from lobbying gov't. Going it alone and destroying bitcoin is not going to be sufficiently profitable to any one company to make it worthwhile.)

The bigger danger is the falling block reward. If this is not addressed, it will cause problems in the long term (i.e. say starting 10 or 20 years from now).

Proof of stake has thus far proven unworkable.

The main problem with Proof of Stake appears to be that is that there is nothing at stake:  In PoW systems you burn energy to mine, and that mining is only worth while if the chain your mining on survives long term, so you are generally incentive mine the chain most likely to survive. In PoS the rational strategy is to mine all possible forks constantly, because doing so costs you nothing.

That page is pretty embarrassing.   There is absolutely no mention of the fundamental flaw in PoS consensus which none of your proposals have addressed:  As of yet none of the proof of stake proposals are workable because there is nothing at stake!   If someone is PoS mining it is in their best interest to attempt to concurrently build an honest chain as well as all possible attack forks just in case one of them happens to win.  Under most schemes this is the profit maximizing move, in all I've seen so far its at least neutral.  Mining an attack under PoW actually involves _spending_ something and taking the risk other miners will extend it. PoW works because your work is at stake so even a very small amount of honest miners make mercenary rational miners behave honestly too.

Moreover, I don't see why you argue here that it better aligns incentives. Parties can't mine PoW without having a validating node (or face the extreme risk other miners will toss them off on forks).  All it does is redistribute control, which might be useful— if not for the fact that it makes attacking more attractive for selfish participants.   I was hopeful of these techniques but as of yet I don't see how any can be workable.

I'd like to think that people will agree to proof of stake before surrendering bitcoin to government or corporate management, but you may be right. People are extremely stubborn and consensus is a damned hard thing to obtain.

Probably. But it was never very difficult to begin with. Moreover there are other ways of destroying bitcoin that make much more sense.

Say I'm the US gov't out to destroy bitcoin.

Step 1) Make it illegal and start rounding people up. Watch price plummet.
Step 2) Buy up hardware and conduct 51% attack on the cheap to neutralize remaining participants. [Once price plummets the used ASIC devices will be very, very cheap.]

In my opinion, bitcoin cannot survive if the US gov't decides to take the ax to it. I don't think this is going to happen. I also don't think that it will make sense for a private actor to do this. (many different guys will benefit from burying bitcoin, but they are not going to be able to coordinate an attack aside from lobbying gov't. Going it alone and destroying bitcoin is not going to be sufficiently profitable to any one company to make it worthwhile.)

The bigger danger is the falling block reward. If this is not addressed, it will cause problems in the long term (i.e. say starting 10 or 20 years from now).

I dunno. I guess I expect the EU to go along with whatever the US says.
I expect China to ban bitcoin if/once it gets really big regardless of what happens elsewhere.
I don't fell informed enough to speculate about the rest of the world.

Just to be clear i don't think the us will ban bitcoin. Say what you like i still believe that the us provides the world's leading environment for innovation. They are not so stupid as to fuck this up.

What I said was, "Bitcoin's developer abandoned the project years ago and disappeared into thin air". I think this is a well-established fact.
[/quote

And his replacement went running straight to the CIA