Finney Attack against SatoshiDice or how to get 250 BTC per solved block.

[Sergio_Demian_Lerner]

There has been some discussion regarding Double Spend against a Satoshidice loss, but it seems that no one has seriously considered Finney Attack against SatoshiDice. This attack is both simple and (IMHO) very easy to mount by an attacker-miner.

The idea is simple: Suppose a miner has any percentage of the network hashing power, say 1%.
Suppose a miner has 241 BTC in an previous output X.
This miner creates a block containing ONLY a single transaction TxWhenLost that pays 241 from X to a new address he owns.

Then the attacker starts mining as normal (and updates the special block to a new parent whenever a new block is solver by the network).
After 16.6 hours on average, his solves a block. Then instead of broadcasting it, he first creates a transaction TxTest that bets the 241 BTC in X against SatoshiDice. Suppose the bet is:

TxTest bets 241 BTC against less than 6000
(address 1dice6wBxymYi3t94heUAG6MpG5eceLG1).
The winning probability is 9.1553% and the multiplier is 10.666x.
That means that approximately every 7 days the attacker wins SatoshiDice.

Now he sends TxTest to SatoshiDice. SatoshiDice replies broadcasting the result TxResult (they say this is almost instantaneously).  Now the attacker decides:

if he has won, he discards the solved block without broadcasting.
If he has lost, he broadcasts the block as soon as possible. Since the block has very few bytes, it will propagate fast. The attacker may also have many nodes in the network to propagate faster the block.

Analysis

9.1553% of the times the attacker wins 241*10.666-25=2545.506 BTC
90.8447% of the times the attacker wins 25 BTC

So the expected income PER SOLVED BLOCK is 233.04+22.71=255.75 BTC !!

That 10x more the 25 BTC a miner normally receives.

Even if 1/10 times the attack fails, the expected income is notably higher than normal.
This is not the best possible attack: if the attacker has greater hashing power or doesn't mind to wait more, he can try bets to "lessthan 1500". In this case the earnings 3 times more (750 BTC per solved block).

The only assumption I'm making is that SatoshiDice responds with TxResult within a short time interval (say 30 seconds).

The only way I think SatoshiDice can protect from this attack is by waiting for 1 confirmation from the transactions they receive or by delaying TxResult 5 minutes or so.

I haven't  contacted the owner of SatoshiDice since there is no contact information in the web page. If you know who the owner is, please tell him to follow this thread.

Disclaimer: as always, I haven't test the attack, so I may be wrong.
Think for yourself.

Best regards,
 Sergio

[1714202194]

1714202194

[1714202194]

1714202194

[1714202194]

1714202194

[1714202194]

1714202194

[misterbigg]

How can someone not know that evoorhees owns Satoshi Dice?

[gmaxwell]

The only assumption I'm making is that SatoshiDice responds with TxResult within a short time interval (say 30 seconds).
The only way I think SatoshiDice can protect from this attack is by waiting for 1 confirmation from the transactions

They wait for 1 confirmation on bets over a couple BTC. This has been discussed before, and a variation (that doesn't require hash power) of it performed in the past.

[Sergio_Demian_Lerner]

They wait for 1 confirmation on bets over a couple BTC. This has been discussed before, and a variation (that doesn't require hash power) of it performed in the past.

Ohh! It's a pity they don't said that on the web page, it would have saved me and you time. They clearly said the response is immediate, probably for  marketing.

[gmaxwell]

Ohh! It's a pity they don't said that on the web page, it would have saved me and you time. They clearly said the response is immediate, probably for  marketing.

Indeed, and I wasn't actually able to tell you what the exact threshold is— since it doesn't even appear to be documented!

One of the reasons they have to do this is that its really really easy to double spend against SD because some pools will not mine transactions paying them. So you can make a bet, if it loses, make a double spend to a non-sd address and give it to miners that ignore SD transactions. They may not solve the next block— but it still makes your expected return positive.  Another variation is to make the txn paying SD have an input that is part of a really long unconfirmed chain which will take a long time to confirm... and double spend that, giving more time for the conflict to get confirmed. etc.

[misterbigg]

its really really easy to double spend against SD because some pools will not mine transactions paying them.

Why would miners drop transactions for SD? That makes no sense. Sure they might de-prioritize them but no need to drop them, especially if they have fees (do they?)

[Peter Todd]

its really really easy to double spend against SD because some pools will not mine transactions paying them.

Why would miners drop transactions for SD? That makes no sense. Sure they might de-prioritize them but no need to drop them, especially if they have fees (do they?)

Fees are still pretty tiny in comparison to the block reward, and some people are willing to pay that small price because they don't like Satoshidice.

Don't assume everyone is a perfectly rational economic actor, or even that perfectly rational actors are using the same set of assumptions that you are.

[gmaxwell]

Why would miners drop transactions for SD? That makes no sense. Sure they might de-prioritize them but no need to drop them, especially if they have fees (do they?)

They have tiny fees, which likely don't pay for the marginal increase in the odds that the block gets orphaned due to its increase propagation/validation time.

Those transactions are insanely inefficient— half of them are pure messaging and not really a monetary transaction— they make it much more costly to run a Bitcoin node— they're burning up our technical startup capital without adding new users to the bitcoin economy (or at least not many). The bitdust outputs they create will likely never be rational to spend and are rapidly inflating the UTXO set— unprunable data. Across the board they're bad they're bad for the ecosystem... and they're ever so easily blocked, basically a one line patch.  So, even if it wasn't net-profitable to block them I'm sure some would.

[Sergio_Demian_Lerner]

Have you considered that maybe SatoshiDice is a government sponsored attack on Bitcoin ? 

[wtfvanity]

Have you considered that maybe SatoshiDice is a government sponsored attack on Bitcoin ? 

And they suckered thousands of people into buying shares in the company, thus attacking themselves!

[niko]

Excuse my ignorance, but please explain "...updates the special block to a new parent whenever a new block is solver by the network)."  All the subsequent blocks are not aware of this special block, how can the miner just broadcast it later and get the txwhenlost confirmed?

[Sergio_Demian_Lerner]

Excuse my ignorance, but please explain "...updates the special block to a new parent whenever a new block is solver by the network)."  All the subsequent blocks are not aware of this special block, how can the miner just broadcast it later and get the txwhenlost confirmed?

It was an awkward way to say that the block is disposed and a new block is created (on top of the best chain), containing the same transaction  txwhenlost. Obviously the parent block will be different.

[Sergio_Demian_Lerner]

Have you considered that maybe SatoshiDice is a government sponsored attack on Bitcoin ? 

And they suckered thousands of people into buying shares in the company, thus attacking themselves!

That's the best part of the attack.. the community is sponsoring it! 

[evoorhees]

Those transactions are insanely inefficient— half of them are pure messaging and not really a monetary transaction— they make it much more costly to run a Bitcoin node— they're burning up our technical startup capital without adding new users to the bitcoin economy (or at least not many). The bitdust outputs they create will likely never be rational to spend and are rapidly inflating the UTXO set— unprunable data. Across the board they're bad they're bad for the ecosystem... and they're ever so easily blocked, basically a one line patch.  So, even if it wasn't net-profitable to block them I'm sure some would.

SatoshiDice is "burning up your technical startup capital without adding new users to the bitcoin economy?"  Are you serious?

First, SD has paid more mining fees than everyone else in the world, combined.

Second, I'll just leave these here...

http://calvinayre.com/2013/02/01/business/why-bitcoin-can-no-longer-be-ignored/
http://www.businessweek.com/articles/2013-01-03/bitcoin-making-online-gambling-legal-in-the-u-dot-s-dot
http://www.npr.org/blogs/alltechconsidered/2013/02/06/171182974/is-online-gambling-legal-if-bitcoins-not-dollars-are-at-stake (was on national radio)
http://www.forbes.com/sites/jonmatonis/2013/01/22/bitcoin-casinos-release-2012-earnings/
http://www.wired.co.uk/news/archive/2013-01/23/bitcoin
http://arstechnica.com/business/2013/01/bitcoin-based-casino-rakes-in-over-500000-profit-in-six-months/
http://www.gambling911.com/gambling-news/bitcoin-casino-satoshidice-results-raise-eyebrows-online-gambling-sector-012313.html
http://techcrunch.com/2013/01/23/online-casino-makes-over-500k-skirting-laws-with-legally-gray-digital-currency-bitcoin/

SatoshiDice achieves all this publicity, demonstrates the power of Bitcoin and provably fair gaming to the masses, and brings Bitcoin to the attention of casino operators around the world, and yet still people complain because it "makes too many transactions" and for their antagonism decide to block SD transactions from their mining pools 

[Luke-Jr]

First, SD has paid more mining fees than everyone else in the world, combined.

Just because you pay the fine for vandalism, does not mean it's acceptable to vandalize, or that it covers the expense in cleaning up the mess you made.
Even with the "standard" transaction fees, miners are still subsidizing transactions at their own (direct) expense in hopes of improving their (indirect) gains from the increased value of Bitcoin as adoption increases (which depends a large part on lower fees right now).

<meaningless propaganda>

SatoshiDice achieves all this publicity, demonstrates the power of Bitcoin and provably fair gaming to the masses, and brings Bitcoin to the attention of casino operators around the world, and yet still people complain because it "makes too many transactions" and for their antagonism decide to block SD transactions from their mining pools  

SatoshiDice does nothing beneficial for Bitcoin.
What little adoption it brings is from irrational gamblers and the casinos out to exploit them; these are not the kind of people who improve the value of Bitcoin at all, just make it more likely to be banned.
What it does do is flood the network with abusive "transactions" conveying more information than finances ("I bet x BTC", "you win", "you lose" are information), using more activity than any payment network today could handle (relative to actual usage). Other reasons aside, this alone would get your attack blocked by VISA et al. Bitcoin attempts to block this attack as well: even in the original paper, miners are expected to deal with flooding attacks. Obviously the original suggestion of using merely fees is not sufficient, since SatoshiDice uses social engineering to fool gamblers into paying 100% of the cost to bypass this anti-flood measure. While we could simply increase fees until the flood stops, the extent we would need to do so would effectively kill adoption of Bitcoin. Blocking SD directly is the only known viable method of Bitcoin surviving this attack.

Note that Bitcoin is a lot of things, but it is not meant to ever be more efficient than other processing networks like VISA. Centralized services are by nature more efficient, so that is unavoidable.

You refuse to stop flooding the network, and insist we deal with it ourselves. Blocking SD outright is how Bitcoin deals with this kind of attack. Deal with that.

Of course, the best way forward is for you to stop attacking Bitcoin. There is nothing inherent in SD's design that necessitates the flooding by any means. A similar service (that I would setup myself, if it weren't illegal) could be done very easily:

• Use compressed public keys for everything. There is no need to waste 2x the space for no gain by using uncompressed keys.
• When a user visits your site, prompt for a withdrawl/cashout address immediately, so there is no opportunity to lose bitcoins. This fixes your bug whereby SD is assuming the first input's previous destination happens to be a valid return address - this bug causes bitcoins to be lost in all cases it isn't true, and creates real security problems when Bitcoin implements post-quantum cryptography upgrades (currently, post-quantum crypto requires that addresses never be used more than once).
• After users provide their cashout address, give them a deposit address. They send however many bitcoins they want to gamble with.
• Display the gambling game(s). Let the user play as much as they want, with instant feedback. RageCoin has an example of just one way to have easier and instantly-verifiable provably fair gaming.
• When the user is done (leaves the site, clicks a button, or just stops doing anything for N minutes), send whatever balance is left to their cashout address.

Edit: And in case anyone thinks SD would somehow be less "popular" with these changes, note that they could very well support both ways of using it and find out for sure. (not that there's any doubt in my mind)

[Technomage]

I believe S.DICE is one of the top 5 services in the Bitcoin economy and it has brought a massive amount of publicity and new users. I also think it's plain wrong to somehow say it's a "lesser service" because it is gambling. It's a service that has demand and adults should be free to play with their money if they want to.

The problem it causes for the blockchain can be solved by simply smoking it out with fees. I mean, services such as S.DICE will be hurt more than anything by higher tx fees, which would be a certainty if the block size max is kept untouched. They would be the first to consider an alternative way which doesn't use the blockchain, or doesn't use the Bitcoin blockchain at least.

This is very off topic and I'm already tired that we have 100 threads in this forum about this same issue, but I'm starting to agree that we actually should smoke out certain services by not touching the block size max until it hurts them. I mean, let's see if users of S.DICE truly want to pay for it, or not.

This would most likely not be a problem for the rest of Bitcoin users since S.DICE should be much more vulnerable to higher fees than regular users. There are spammy methods (martingale bots) of playing S.DICE and a major amount of their transactions consist of these methods. The spammy methods would reduce if fees were increased, which is good. Bitcoin needs a fee structure that reduce all spammy uses of the blockchain, but still allows regular usage.

[Luke-Jr]

I believe S.DICE is one of the top 5 services in the Bitcoin economy and it has brought a massive amount of publicity and new users. I also think it's plain wrong to somehow say it's a "lesser service" because it is gambling. It's a service that has demand and adults should be free to play with their money if they want to.

Sure, that's fine with me (though I bet not the State of New York), but he can't justify attacking the network with "publicity" that only brings a few fools and government crackdown. There is no evidence there are any "massive" amounts of new users involved of any sort.

The problem it causes for the blockchain can be solved by simply smoking it out with fees. I mean, services such as S.DICE will be hurt more than anything by higher tx fees, which would be a certainty if the block size max is kept untouched. They would be the first to consider an alternative way which doesn't use the blockchain.

Did you even read my post? The problem is that increasing the fees to "smoke it out" would kill Bitcoin adoption. Do you really want that? The reality is there already are alternative ways that don't use the blockchain; SD just refuses to do things efficiently.

This is very off topic and I'm already tired that we have 100 threads in this forum about this same issue, but I'm starting to agree that we actually should smoke out certain services by not touching the block size max until it hurts them. I mean, let's see if users of S.DICE truly want to pay for it, or not.

They almost certainly will. Gamblers are psychologically inclined to tolerate a higher fee than rational transactors.

[Technomage]

I don't think that trying to ban S.DICE is a proper solution to anything. Higher fees are a solution, even if it does affect regular usage somewhat. As far as I know, majority of S.DICE transactions come from martingale bots which would be very much affected by higher fees. For the martingale strategy even small differences make it much more suicidal. It's exactly these kinds of spammy gambling transactions that should be deincentivized.

[Luke-Jr]

I don't think that trying to ban S.DICE is a proper solution to anything. Higher fees are a solution, even if it does affect regular usage somewhat. As far as I know, majority of S.DICE transactions come from martingale bots which would be very much affected by higher fees. For the martingale strategy even small differences make it much more suicidal. It's exactly these kinds of spammy gambling transactions that should be deincentivized.

Transaction fees are just another form of a ban, one that is suicidal to Bitcoin in this scenario.

[Technomage]

I don't think that trying to ban S.DICE is a proper solution to anything. Higher fees are a solution, even if it does affect regular usage somewhat. As far as I know, majority of S.DICE transactions come from martingale bots which would be very much affected by higher fees. For the martingale strategy even small differences make it much more suicidal. It's exactly these kinds of spammy gambling transactions that should be deincentivized.

Transaction fees are just another form of a ban, one that is suicidal to Bitcoin in this scenario.

You do understand that Bitcoin either suffers from higher fees at some point or weakens and dies completely? Those 2 options are the only possible options if we continue to use proof of work. Option 1 is achieved by limiting the block size and letting scarcity come in, with the goal of retaining sufficient hashing power, leading to higher fees. Option 2 would be achieved by removing the block size limit entirely, which would let us keep non-existent fees but that would weaken Bitcoin to the point of easy destruction.

The only question with option 1 is how much the fees will rise, not if they will rise. Debating about if they rise or not is not a debate because it's a certainty. I'm concerned about them rising in a way that still keeps Bitcoin competitive with mainstream money transfer mechanisms. If they rise beyond that, Bitcoin adoption will die, as you said.