[SUCCESS] Double Spend against a satoshidice loss

[Yuhfhrh]

DISCLAIMER: The following post shows the risk with accepting bitcoin transactions with no confirmations. This could not have been done if the transaction had a confirmation.

Second attempt: This time I started with twenty 0.01BTC imputs, to create a "spammy" transaction.

Here are the two transactions:
(Lost bet against satoshidice of 0.2BTC with no fee paid)https://blockchain.info/tx/7d6ce09ff0d013e9d59760857339c59b107d3e5c80437a9f5ea79d9a6ca32861
http://satoshidice.com/lookup.php?tx=7d6ce09ff0d013e9d59760857339c59b107d3e5c80437a9f5ea79d9a6ca32861&limit=100&min_bet=0&status=ALL
(Double spend with 0.004BTC fee paid)https://blockchain.info/tx/be585cd7c6e9a0a6f48502e5d3adde2588fe55bcb7b27964968e6ddce4701e1a

Edit: And the second transaction with the fee got the confirmation from BTC Guild, so the original bet against satoshidice will never confirm.


Failed first attempt:

EclipseMC picked up the 0 fee transaction.

Conclusion: The miner must be using a custom set of rules when picking transactions for this to work. I got lucky in the practice round.

Okay here is my attempt to double spend against a satoshidice loss: (Sorry it got a little sloppy)
This is the address I am using, which started with 0.5BTC:
https://blockchain.info/address/1PvsMBVx1tVrX4q5Ef2NfMjsB6qUF9G9q2
Here is the 0.25BTC bet against satoshidice, which I lost (No fees paid):
https://blockchain.info/tx-index/36578058
http://satoshidice.com/lookup.php?tx=dff6f55049a534855115d3efb76a6d1955b223a0d73bcbe95a0d74ba3f4445cc&limit=100&min_bet=0&status=ALL
Here is the double spend (0.001 fee paid), which included the whole balance of 0.5, and also a separate 0.1 input:
https://blockchain.info/tx-index/36578900

I then moved the double spend around twice, just as before, paying a 0.001 fee each time:
https://blockchain.info/tx/cd7ba48d2d0816dcf13c1be38eb434fcc02ef470198a5f6a5ef841be5e3ddbf4
https://blockchain.info/tx/acfd7095934893105b2fa4941e02d9b8fa28cd8a2bf47f550a15620747c70e88

Successful practice round:

Out of curiosity, I wondered what would happen if I tried to double spend some coins. So I did.

I started with a balance of 0.85037754 BTC at this address: https://blockchain.info/address/1NBSySCggyahxu5F3LHnFwT7MvJycfamuG

I then sent the 0.85037754 without a miner's fee to this address:
https://blockchain.info/address/1HPapF7cemm7Erat11LEsi461gVL2EWdWb
Then I sent the same 0.85037754 again with 0.05256613 from another address to the same address above, this time including a miner's fee.
https://blockchain.info/address/1HPapF7cemm7Erat11LEsi461gVL2EWdWb
From the transaction with the miner's fee, I sent the coins two more times including fees, and they finally rest here:
https://blockchain.info/address/1HJ18q1tsZCqgD4jtCeYvmtB3Sb9KMhN5R

So what I end up with is two unconfirmed balances.
0.85037754 at https://blockchain.info/address/1HPapF7cemm7Erat11LEsi461gVL2EWdWb (No fees paid),
0.9 at https://blockchain.info/address/1HJ18q1tsZCqgD4jtCeYvmtB3Sb9KMhN5R (Fees paid)

Will the transaction with miner fees get confirmed over the transaction without the miner fees? As I understand it after a few hours/days eventually one of them will be confirmed, but how do miners decide which one?

Edit: The transaction with the fees that was placed an hour later got confirmed over the transaction with no fees.

If you learned something new or enjoyed reading this post, please send donations to 1Donate3AJvrk5kNEoyR6qNFCuTdHsBsmr. I lost a few BTC in this process  

[1715695850]

1715695850

[adamstgBit]

miners will look at the blockchain and see you already spent the coins your trying to send and never confirm them

if one of these fraudulent tx gets confirmed bitcoin dies tonight.

[Yuhfhrh]

miners will look at the blockchain and see you already spent the coins your trying to send and never confirm them

if both of those transactions get confirmed bitcoin dies tonight.

FTFY
I expect either one of the final outputs to confirm, or neither of them confirming. Both transactions have 0 confirmations at the moment.

[adamstgBit]

miners will look at the blockchain and see you already spent the coins your trying to send and never confirm them

if both of those transactions get confirmed bitcoin dies tonight.

FTFY
I expect either one of the final outputs to confirm, or neither of them confirming. Both transactions have 0 confirmations at the moment.

right.

my guess is its random a bit, and which ever one gets included in the block chain first will be valid, it probably doesn't matter which tx was sent first...
I put my money on the one with a fee.

cool test.

[Stephen Gornick]

Will the transaction with miner fees get confirmed over the transaction without the miner fees? As I understand it after a few hours/days eventually one of them will be confirmed, but how do miners decide which one?

The pools may use customized clients that behave different from the stock bitcoin.org client, but how the Bitcoin.org client handles it is the first transaction a node receives goes into the memory pool (only if it is a valid transaction, of course) and the second one is rejected as the inputs have already been spent by a valid transaction.

That is likely to be what will happen here.    The first one (without the fee) got propagated fast enough that most nodes never even knew about the second one (with the fee paid).

The transaction without the miners fee hadn't hit many nodes yet,

Well, blockchain.info shows the first transaction (without the fee) as being "first relayed by" 127.0.0.1.    I was thinking that meant that it was a transaction sent from blockchain.info/wallet, but maybe I'm wrong there.  But that is a well connected node and likely that is the transaction that will be included in a block and the second transaction will never confirm.

 - https://blockchain.info/tx/e860c52cd705d398abac710dc9a1df81ca153267dea7857f34fada2cedbc8409  <-- First / No fee pad.
 - https://blockchain.info/tx/41a08e5afede7698f368d2516c6cb85134e158ae9bbf340d5382383b3d3b6183  <-- Second / Fee paid.

[adamstgBit]

looks like both have been labeled double spend

[Yuhfhrh]

Will the transaction with miner fees get confirmed over the transaction without the miner fees? As I understand it after a few hours/days eventually one of them will be confirmed, but how do miners decide which one?

The pools may use customized clients that behave different from the stock bitcoin.org client, but how the Bitcoin.org client handles it is the first transaction a node receives goes into the memory pool and the second one is rejected (assuming the first one was valid) .  

That is likely to be what will happen here.    The first one (without the fee) got propagated fast enough that most nodes never even knew about the second one (with the fee paid).

The transaction without the miners fee hadn't hit many nodes yet,

Well, blockchain.info shows the first transaction (without the fee) as being "first relayed by" 127.0.0.1.    I was thinking that meant that it was a transaction sent from blockchain.info/wallet, but maybe I'm wrong there.  But that is a well connected node and likely that is the transaction that will be included in a block and the second transaction will never confirm.

 - https://blockchain.info/tx/e860c52cd705d398abac710dc9a1df81ca153267dea7857f34fada2cedbc8409  <-- First / No fee pad.
 - https://blockchain.info/tx/41a08e5afede7698f368d2516c6cb85134e158ae9bbf340d5382383b3d3b6183  <-- Second / Fee paid.

Thanks for the response, I was pretty sure the first transaction (no fee) did come from a satoshi client, not the blockchain.info/wallet. I might have messed up here so I might try again: How about the scenario where the transactions are placed less than a second apart? Is there a way to effectively double spend with >50% probability (on 0 confirmations) this way?

[Stephen Gornick]

How about the scenario where the transactions are placed less than a second apart? Is there a way to effectively double spend with >50% probability (on 0 confirmations) this way?

That's why the recommendation is that a merchant running its own node should not have any support for incoming connections and to explicitly have an outgoing connection to a well-connected nodes.   In that scenario, presumably the well connected node will have the same transactions as the mining pools and thus the chance of a double spend (via race attack) is substantially less than 50%.

And if you have the ability to connect to the merchant's node you can double spend on 0/unconfirmed with at a success rate approaching 100%.

Because of this risk, those trading on OTC or in-person for cash with someone who doesn't have a good history of trust should consider verifying that no double-spend occurred by looking at the transaction on Blockchain.info (or using a service like a "LocalBitcoins Transaction" / escrow).

[Yuhfhrh]

The second transaction I placed an hour later with the fee got confirmed. Not what was expected. I will try to replicate this.

[Stephen Gornick]

The second transaction I placed an hour later with the fee got confirmed. Not what was expected.

I'ld be curious to know the path between you and that node that mined it because if you were peered only to bitcoin.org clients that transaction would not have made it far. 

Because Blockchain.info considers transactions even when it is a double spend maybe they even relay these transactions regardless.  (and thus a well connected node that you reached somehow and then that it propagated the transaction to a node used by a miner.)

But the block was not mined by an address of any known pools, so that it is using a custom client would not be surprising.

[Yuhfhrh]

The second transaction I placed an hour later with the fee got confirmed. Not what was expected.

But the block was not mined by an address of any known pools, so that it is using a custom client would not be surprising.

This was kind of my theory in the first place, by not paying a fee on the first transaction, it would take a long time to confirm. By paying the fee on the second one, a miner who maybe accepts transactions only with fees could come by and sweep it up.

Anyways I'm preparing for round two. Waiting for a block...

Waiting for blockchain to pick up the double spend...

[Yuhfhrh]

Okay here is my attempt to double spend against a satoshidice loss: (Sorry it got a little sloppy)
This is the address I am using, which started with 0.5BTC:
https://blockchain.info/address/1PvsMBVx1tVrX4q5Ef2NfMjsB6qUF9G9q2
Here is the 0.25BTC bet against satoshidice, which I lost (No fees paid):
https://blockchain.info/tx-index/36578058
Here is the double spend (0.001 fee paid), which included the whole balance of 0.5, and also a separate 0.1 input:
https://blockchain.info/tx-index/36578900

I then moved the double spend around twice, just as before, paying a 0.001 fee each time:
https://blockchain.info/tx/cd7ba48d2d0816dcf13c1be38eb434fcc02ef470198a5f6a5ef841be5e3ddbf4
https://blockchain.info/tx/acfd7095934893105b2fa4941e02d9b8fa28cd8a2bf47f550a15620747c70e88

So lets see what happens.

[Stephen Gornick]

So lets see what happens.

I see you updated the original post.

FAILED

EclipseMC picked up the 0 fee transaction.

Conclusion: The miner must be using a custom set of rules when picking transactions for this to work. I got really lucky in the practice round.

One big difference between your first trial and your second was that the second transaction was under 1K bytes, and the first was something like 2K.   So it would make sense that a "spam-like" transaction wouldn't confirm for many hours leaving the opportunity for a mining node with a "higher fee trumps a lower fee" customization to have the chance to mine a block.  

I see that in the second trial the "Relayed by IP" is again 127.0.0.1.   Had you sent that from Blockchain.info?

[Yuhfhrh]

So lets see what happens.

I see you updated the original post.

FAILED

EclipseMC picked up the 0 fee transaction.

Conclusion: The miner must be using a custom set of rules when picking transactions for this to work. I got really lucky in the practice round.

One big different between your first trial and your second was that the second transaction was under 1K bytes, and the first was something like 2K.   So it would make sense that a "spam-like" transaction wouldn't confirm for many hours leaving the opportunity for a mining node with a "higher fee trumps a lower fee" customization to have the chance to mine a block.  

I see that in the second trial the "Relayed by IP" is again 127.0.0.1.   Had you sent that from Blockchain.info?

Yes I had sent it from blockchain.info. I was considering sending many 0.01 transactions to an address and trying again, but it's a lot of effort (the whole double spending process). I may get around to trying it again tonight. But also something different about the second trial, the payment from satoshidice includes a fee.

[Yuhfhrh]

I'm trying again.

[Yuhfhrh]

Success.

[paybitcoin]

Wow. Nice. Also, from looking at the timestamps, 10 minutes went by from the unlucky dice roll to the included double spend transaction, if I'm seeing it correctly!

Hopefully they get around to patching it to wait before people start abusing this...

[Yuhfhrh]

Wow. Nice. Also, from looking at the timestamps, 10 minutes went by from the unlucky dice roll to the included double spend transaction, if I'm seeing it correctly!

It took ten minutes before the rest of the bitcoin network picked up the double spend apparently, I don't know why, but the same thing happened with my practice round.

[Stephen Gornick]

Wow. Nice. Also, from looking at the timestamps, 10 minutes went by from the unlucky dice roll to the included double spend transaction, if I'm seeing it correctly!

It took ten minutes before the rest of the bitcoin network picked up the double spend apparently, I don't know why, but the same thing happened with my practice round.

Can you provide the transaction IDs?   At a minimum, I'm curious which mining pool (if any) was responsible for the block in which this occurred.

[Yuhfhrh]

Wow. Nice. Also, from looking at the timestamps, 10 minutes went by from the unlucky dice roll to the included double spend transaction, if I'm seeing it correctly!

It took ten minutes before the rest of the bitcoin network picked up the double spend apparently, I don't know why, but the same thing happened with my practice round.

Can you provide the transaction IDs?   At a minimum, I'm curious which mining pool (if any) was responsible for the block in which this occurred.

OP^^ Another question is, would the transaction with no fees get confirmed at all considering it should have had 0.004BTC in fees?

I will test again, this time seeing how long it takes for a spammy transaction to confirm without fees, if at all.

[Yuhfhrh]

Another loss I am trying to double spend on
https://blockchain.info/tx/f4c76f4c2f906e08b8f7392285bfc8d5b593378c3e2a1b570887502c05b8f547
http://satoshidice.com/lookup.php?tx=f4c76f4c2f906e08b8f7392285bfc8d5b593378c3e2a1b570887502c05b8f547&limit=100&min_bet=0&status=ALL

Waiting for blockchain.info to pick up the double spend...

Double spend has been broadcast now:
https://blockchain.info/tx/0ddd5d48d880116eac5c361268f3fb5e069c0e059fe6b08f77db9039493de452

Waiting to see which one gets confirmed...

The amount of time this takes almost makes it not worth doing in the first place, then again I'm doing everything manually. I guess a bot could be set up to do this, which would give you an edge over the house even if only 1/4 of the double spends work.

FAILED

EclipseMC included the original transaction without the fee. This seems to be a luck of the draw game depending on who mines the block. Either way I'm done messing with this for now.

[fireduck]

Thanks to everyone how has been looking at this and reporting their findings.

I tried this earlier this year and couldn't get it to work, but I might have simply not tried hard enough or things have changed.

While I investigate I've set Satoshidice to only allow confirmed bets.  I'll bring up our test site and post the url in a little in case anyone wants to use a casino to continue to test this.  It has real funds, just not nearly as much.

[fireduck]

Anyone who wants to test double spends is free to try it on the test site:

http://1209k.com/testdice/

I'll be doing some of my own testing.

[piuk]

This should be a pretty reliable method.

1) Create a long chain of unconfirmed transactions (lots of free low priority transactions which depend on each other).
2) Send the final transaction in the chain to SatoshiDICE, including one input which isn't part of the unconfirmed chain. If the bet wins, great, keep rebroadcasting all the transactions in the chain and eventually they will confirm.
3) If the bet looses. Double spend the input from the betting transaction which is not part of the unconfirmed chain.

Because the chain will take a long time to confirm it gives a much larger window of opportunity for miners to pickup the double spending transaction. As miners join and leave the network they are much more likely to pickup the single double spend transaction, rather than the full chain of unconfirmed transactions (which you are no longer broadcasting). This technique was used to successfully double spend the blockchain.info mixer.

[Yuhfhrh]

I've set it to allow unconfirmed as long as they have a fee and are based on confirmed inputs.

New rules! I'll test some more tonight.

[HostFat]

Can this idea be a solution?

In the test code I have just implemented what I call the "Boomerang Rule" - see below:



It enables change to be spendable immediately as long as the transaction propagates through the network ok.

I will spend a little while testing it and then produce another test release (beta) with it in.
It would be very useful if a few people could test it out to make sure it works as expected before I put it into the live code.

[Fjordbit]

I just want to be clear, because the title is a little inaccurate. A double spend was not achieved. If that were true, then the bitcoin network would be in trouble. This is more of a Finney attack.

[DeathAndTaxes]

I just want to be clear, because the title is a little inaccurate. A double spend was not achieved. If that were true, then the bitcoin network would be in trouble. This is more of a Finney attack.

Um no it is a double spend.  A Finney attack is a type of double spend in which the attacker "reverses" a 0-confirm tx by submitting a replacement which is already in a block HE MINED.  There is nothing in the OP attack which makes it is a Finney attack.

[Syke]

I just want to be clear, because the title is a little inaccurate. A double spend was not achieved. If that were true, then the bitcoin network would be in trouble. This is more of a Finney attack.

Double-spends have always been possible. That's why we count "confirmations". The number of confirmations reduces the risk of double-spends.

[Gavin Andresen]

Double-spends have always been possible. That's why we count "confirmations". The number of confirmations reduces the risk of double-spends.

Yes -- 0/1-confirmation double spends are certainly possible. A successful 2-confirmation double-spend would be more interesting. I would love to see if real-network experience matches the theoretical results from Meni's paper.

[nevafuse]

If double spends are really this easy, I can only imagine shady clients that come out in the future that do this automatically.  Obviously someone willing to wait for confirmations will be fine, but how are people going to be expected to wait 10+ minutes at the convenience store for a candy bar purchase?

Is this when green addresses come into play?  The convenience store trusts transactions from mtgox addresses not to attempt double spending so they accept a 0 confirmation payment?

[DannyHamilton]

If double spends are really this easy, I can only imagine shady clients that come out in the future that do this automatically . . .

I'm already working on one.  Hope to have it working properly in a few months.

[nevafuse]

If double spends are really this easy, I can only imagine shady clients that come out in the future that do this automatically . . .

I'm already working on one.  Hope to have it working properly in a few months.

I actually support this.  The sooner people realize this can happen, the sooner people will be educated about the risk of 0 confirmation transactions.  I can't technically conceive a way to prevent this, but ideas like green addresses or physical coins could certainly help reduce the risk for people who rely on instant transactions.

[Yuhfhrh]

If the proper fee was paid to the miners and the payment is based on confirmed imputs, this type of double spend doesn't work. So, like satoshidice has done, simply check these two things before accepting a 0 confirmation payment. Otherwise wait for 1 confirmation. I'll work on wording this better and presenting it more effectively in the future.

[nevafuse]

If the proper fee was paid to the miners and the payment is based on confirmed imputs, this type of double spend doesn't work. So, like satoshidice has done, simply check these two things before accepting a 0 confirmation payment. Otherwise wait for 1 confirmation. I'll work on wording this better and presenting it more effectively in the future.

You could still double spend a transaction with a fee.  You just need your 2nd transaction to be a larger fee.  If someone was successfully pulling this off on satoshidice, they could have definitely raised the chances for themselves & screwed everyone else.  Maybe dooglus can do an analysis on the luckiest players of satoshidice.

[Yuhfhrh]

If the proper fee was paid to the miners and the payment is based on confirmed imputs, this type of double spend doesn't work. So, like satoshidice has done, simply check these two things before accepting a 0 confirmation payment. Otherwise wait for 1 confirmation. I'll work on wording this better and presenting it more effectively in the future.

You could still double spend a transaction with a fee.  You just need your 2nd transaction to be a larger fee.  If someone was successfully pulling this off on satoshidice, they could have definitely raised the chances for themselves & screwed everyone else.  Maybe dooglus can do an analysis on the luckiest players of satoshidice.

That only works if the miner who mines the block has special rules determining what transactions he includes. You are right, and this will probably get worse in the future. But for now most of the miners follow the standard protocol, so only ~1/8 IMO of these type of double spends would actually work.

[nibor]

But to beat satoshi dice you only need 1/50 (to overcome the 2% house advantage).

[Yuhfhrh]

But to beat satoshi dice you only need 1/50 (to overcome the 2% house advantage).

Very true, so I expect some bots are going to be hitting satoshidice with this now that it has been brought up.

[Stephen Gornick]

Is this when green addresses come into play?  The convenience store trusts transactions from mtgox addresses not to attempt double spending so they accept a 0 confirmation payment?

Well, SatoshiDICE did exactly what a merchant that accepts on 0/unconfirmed will likely need to do ... become discriminating on 0/unconfirmed.  Fireduck changed which 0/unconfirmed bets will be processed:

I've set it to allow unconfirmed as long as they have a fee and are based on confirmed inputs.

So the "spam-like" payment that was originally sent to SatoshiDICE will no longer be processed (it will sit unprocessed until it gets one confirmation).

Just to be clear, it isn't easy for one to send a payment and then "accidentally" spend the same funds to somewhere else except with the second time include a fee that happens to cause the second transaction to get included in a block over the first.  That is fraud -- which might be why Fireduck offered to let people test this approach against a version of the service for testing purposes:

Anyone who wants to test double spends is free to try it on the test site:

http://1209k.com/testdice/

So the chances of getting caught double spending to defraud SatoshiDICE are low, as bitcoin has user-definable anonymity (hat tip to Jon Matonis for defining it that way).    But buying a candy bar and double spending those funds is probably not something you can do anonymously.

I don't know that Green Addresses are the approach to get behind.   What I think this proves though is that a merchant that likes to DIY will be more at risk than one using a payment processor that can figure out how to combat these types of risks.

I wonder what would happen though ... where let's say I'm at a merchant and I pay with bitcoin but the payment processor flags it as a high risk payment because it included 2K of data and I didn't pay a fee.     The Bitcoin.org client doesn't let me do that but with Blockchain.info/wallet, for example, I could do that.

[Mike Hearn]

This should be a pretty reliable method.

1) Create a long chain of unconfirmed transactions (lots of free low priority transactions which depend on each other).
2) Send the final transaction in the chain to SatoshiDICE, including one input which isn't part of the unconfirmed chain. If the bet wins, great, keep rebroadcasting all the transactions in the chain and eventually they will confirm.
3) If the bet looses. Double spend the input from the betting transaction which is not part of the unconfirmed chain.

Because the chain will take a long time to confirm it gives a much larger window of opportunity for miners to pickup the double spending transaction. As miners join and leave the network they are much more likely to pickup the single double spend transaction, rather than the full chain of unconfirmed transactions (which you are no longer broadcasting). This technique was used to successfully double spend the blockchain.info mixer.

If I understood correctly, that attack can be solved by just having your own software periodically rebroadcast all unconfirmed transactions that are relevant to your wallet. Alternatively, by having miners sync their memory pools with their peers at startup (should be more reliable). This would ensure that it's much harder to repeatedly announce a double spend and have it take precedence due to natural miner churn.

Jeff has a patch to make nodes sync their mempools at startup already. I guess there are a few other mempool handling issues we'd need to fix first before it lands, but that specific way of double spending doesn't seem very hard to solve.

HostFat: no Jims "boomerang rule" (I'll not be using this term when I reimplement the code in bitcoinj) is handling a different issue that's only relevant to SPV clients. It's not connected to this.

[Vitalik Buterin]

One idea I had to help mitigate this is that SatoshiDice could immediately re-send the output of any transaction that they receive to themselves with a fee, encouraging miners to quickly confirm both the new transaction and its parent over any conflicting transactions.

Two questions:

1. Can a transaction reference an unconfirmed transaction as an input? If so, can the two appear in the same block? I'm pretty sure the answer is yes to the first, but I'm not sure about the second.

2. Do miners actually work that way? Does a fee on a transaction also encourage miners to include its (possibly feeless and even non-standard/bloated) parent? If not, are there any obstacles / reasons not to implement such a strategy (with appropriate rules so you can't use one transaction to force miners to include 1000 bad ones, obviously)?

[Yuhfhrh]

One idea I had to help mitigate this is that SatoshiDice could immediately re-send the output of any transaction that they receive to themselves with a fee, encouraging miners to quickly confirm both the new transaction and its parent over any conflicting transactions.

Two questions:

1. Can a transaction reference an unconfirmed transaction as an input? If so, can the two appear in the same block? I'm pretty sure the answer is yes to the first, but I'm not sure about the second.

2. Do miners actually work that way? Does a fee on a transaction also encourage miners to include its (possibly feeless and even non-standard/bloated) parent? If not, are there any obstacles / reasons not to implement such a strategy (with appropriate rules so you can't use one transaction to force miners to include 1000 bad ones, obviously)?

First off, thanks for writing an article on this! I appreciate it!
Also for others, I added a donation address to the OP since I lost about 1.5 BTC in this process.   If I receive more than 1.5BTC, further funds will be used for more double spending attempts.

1. The answer is yes to both.
2. I don't believe it works that way. As long as miners are following the standard rules, sending a transaction 999 times with no fee and then sending the last with a 1BTC fee will not affect the previous 999 transactions. Each transaction is based on it's own fees.

[Mike Hearn]

1. Can a transaction reference an unconfirmed transaction as an input? If so, can the two appear in the same block? I'm pretty sure the answer is yes to the first, but I'm not sure about the second.

Yes and yes.

2. Do miners actually work that way? Does a fee on a transaction also encourage miners to include its (possibly feeless and even non-standard/bloated) parent? If not, are there any obstacles / reasons not to implement such a strategy (with appropriate rules so you can't use one transaction to force miners to include 1000 bad ones, obviously)?

Fees are not considered recursively at the moment. They should be and there are patches open to do that. I think Gavin is planning to merge some of that work soon (i hope?)

[nibor]

Also for others, I added a donation address to the OP since I lost about 1.5 BTC in this process.   If I receive more than 1.5BTC, further funds will be used for more double spending attempts.

I think Satoshidice owe you a reward. I am surprised that they do not offer a standard 10 BTC reward to anyone who posts a proven double spend on this forum.

[Yuhfhrh]

Also for others, I added a donation address to the OP since I lost about 1.5 BTC in this process.   If I receive more than 1.5BTC, further funds will be used for more double spending attempts.

I think Satoshidice owe you a reward. I am surprised that they do not offer a standard 10 BTC reward to anyone who posts a proven double spend on this forum.

Well they don't owe me a reward. Also I could have won BTC instead of losing during these tests.

[paybitcoin]

Also for others, I added a donation address to the OP since I lost about 1.5 BTC in this process.   If I receive more than 1.5BTC, further funds will be used for more double spending attempts.

I think Satoshidice owe you a reward. I am surprised that they do not offer a standard 10 BTC reward to anyone who posts a proven double spend on this forum.

Well they don't owe me a reward. Also I could have won BTC instead of losing during these tests.

Funny that you mention that, since in the process of testing your method I ended up 5 BTC ahead... I think I'm obligated now to cover your loss, so I'll share the winnings.

I couldn't pull off the double spend, but I only got 1 or 2 reasonable tests in. They do take quite a long time to execute.

[Yuhfhrh]

Also for others, I added a donation address to the OP since I lost about 1.5 BTC in this process.   If I receive more than 1.5BTC, further funds will be used for more double spending attempts.

I think Satoshidice owe you a reward. I am surprised that they do not offer a standard 10 BTC reward to anyone who posts a proven double spend on this forum.

Well they don't owe me a reward. Also I could have won BTC instead of losing during these tests.

Funny that you mention that, since in the process of testing your method I ended up 5 BTC ahead... I think I'm obligated now to cover your loss, so I'll share the winnings.

I couldn't pull off the double spend, but I only got 1 or 2 reasonable tests in. They do take quite a long time to execute.

Thanks, I really appreciate it! 

[Gyrsur]

Anyone who wants to test double spends is free to try it on the test site:

http://1209k.com/testdice/

I'll be doing some of my own testing.

this testdice is located in prodnet?? what it the sense of that?

a testdice should be located in testnet with exactly the same parameters as in prodnet.

[etotheipi]

Anyone who wants to test double spends is free to try it on the test site:

http://1209k.com/testdice/

I'll be doing some of my own testing.

this testdice is located in prodnet?? what it the sense of that?

a testdice should be located in testnet with exactly the same parameters as in prodnet.

I agreed with this statement at first, but I think it will be difficult to trigger on testnet -- the makeup of the network and the miners is significantly different.  You probably don't have the same density and diversity of peers needed to do it -- you need significant propagation of each tx in the subnetworks of nodes that are willing to accept it and mine it.

Not to say it can't be done, I just think the attack will manifest differently on testnet.  

On the upside, anyone succeeding on the test site might make a few tenths of a BTC for their effort.

[usagi]

DISCLAIMER: The following post shows the risk with accepting bitcoin transactions with no confirmations. This could not have been done if the transaction had a confirmation.

This was pure genius. Thank you for your contribution to science.

[Yuhfhrh]

I still haven't confirmed if sending a spammy transaction with the standard 0.0005 BTC fee where a normal fee of ~0.01 would be required and double spending it would work or not. I haven't had the time to try, but this should theoretically work under their new rules unless satoshidice checks to make sure the standard fee is paid, and not just the 0.0005.

[etotheipi]

I can't believe I posted in the wrong thread!  

A couple days ago, I observed a pretty large, successful, double spend against SD (25 BTC).  Please see my post in the statistics thread.  I have raw data if anyone wants to analyze it.  

It is not related to the vulnerability retep posted.  But it does look like a miner may have helped them.

tl;dr:  

The original bet, B, was made using an input from transaction A.  A was 7 kB and had 43 inputs.  I don't know what the transaction fee was (but I all zero-conf tx I received that entire day with timestamps, so all this information could be reconstructed... I can make it available to anyone who wants to dig into it).

Transaction A never made it past zero-conf, and was replaced by a block with transaction A'.  Thus, bet B was invalidated.  The curious part is that A' was 14 kB, with 83 inputs, and paid zero fee!.  14kB is clearly over the allowFree limit, thus it would only be accepted (even without a conflicting tx in the memory pool) by a miner with non-standard rules.  Now given that there was a public, conflicting transaction... hmmm

[mskwik]

The original bet, B, was made using an input from transaction A.  A was 7 kB and had 43 inputs.  I don't know what the transaction fee was (but I all zero-conf tx I received that entire day with timestamps, so all this information could be reconstructed... I can make it available to anyone who wants to dig into it).

Transaction A never made it past zero-conf, and was replaced by a block with transaction A'.  Thus, bet B was invalidated.  The curious part is that A' was 14 kB, with 83 inputs, and paid zero fee!.  14kB is clearly over the allowFree limit, thus it would only be accepted (even without a conflicting tx in the memory pool) by a miner with non-standard rules.  Now given that there was a public, conflicting transaction... hmmm

It seems possible that A' was submitted first (directly to any miner that would accept it) and didn't propagate over the rest of the network because of the lack of fee.  Then A and B could be submitted normally and make it to the rest of the network (except for any miners that already had the conflicting transaction).  The tricky part would be trying to affect who found the next block after seeing the bet outcome.  With enough hashing power you could point at one pool or another you could push the odds around somewhat but it would seem to be far from a sure thing, it wouldn't however necessarily require collusion from any mining pools directly.

[Mike Hearn]

OK, a Finney attack against SD, nice.

BTW does anyone know if Eclipse publishes the list of blocks they solved anywhere? I couldn't find such a list on their site. If Eclipse did solve it, then I guess Inaba needs to examine how A' got into his memory pool.

Miners that are accepting direct submissions of transactions that would normally fail to relay really should be ensuring those transactions don't conflict with any in the memory pool, and if they see a broadcast transaction that would double spend a direct submission, should take the broadcast transaction as having priority.

Is it possible to send a tx that wouldn't normally relay to a node, but still get it accepted into the nodes memory pool? I thought the code did not allow that, but maybe I'm wrong.

It seems worth investigating this in more detail.

[mskwik]

Is it possible to send a tx that wouldn't normally relay to a node, but still get it accepted into the nodes memory pool? I thought the code did not allow that, but maybe I'm wrong.

Well if the tx was accepted by the pool in the first place it would have to be running some custom software.  I assume it would try and relay it normally but it would only be accepted by peers that were following the same relaxed rules as itself.  I have played with nonstandard transactions in the past sending them through Eligius to get mined and it does seem that though they are accepted and eventually end up in a block that I do not see them get propagated very far elsewhere on the network before being mined.  I assume that it would work fairly similarly for transactions with fees below minimum.

[Mike Hearn]

I turns out the issue is that Inaba excluded 1dice transactions from the memorypool on his node due to some crashing issue. I'm not sure if he realized this opens SD to double spends or not, but at any rate, it's not deliberate collusion so actually exploiting it is difficult.

Edit: the issue was apparently fixed and it was actually a deadlock, not a crash.

This is one aspect of using fixed addresses I suspect fireduck did not consider. Using static addresses like that not only makes his books entirely open, but allows people to selectively exclude his traffic. I'm not sure what the crash issue was, but if it wasn't possible to isolate his transactions there may have been more motivation to find a real fix.

[World]

something is wrong to many double spend addresses
https://blockchain.info/double-spends

[etotheipi]

I was doing some Armory testing last night and shutdown Bitcoin-Qt ... meaning my double-spend detection script was disconnected... What timing!  <facepalm>

However, I turned it on this morning and was able to catch some excitement at 2:44pm EST -- a bunch of bets total 613 BTC was invalidated (at least from where I'm sitting in the network).

This invalidation was a straight zero-conf replacement (no replacing tx on which it was depending).  This is all the information I have... the first one is the transaction that was invalidated (containing 613 BTC to SD), and the second one is the one that replaced it, looks to be similar... probably just a "re-roll":

Code:

Transaction:
   TxHash:    54825a1963a0fc4b566cd415690986c835a84974ceb00ae3649ed311a39d2a2e (BE)
   Version:   1
   nInputs:   15
   nOutputs:  9
   LockTime:  0
   Inputs: 
      PyTxIn:
         PrevTxHash: e7b58ff78217d9c2dbf1241caf5fe4fcd92e0d2513377a172fd045549fcdc98f (BE)
         TxOutIndex: 0
         Script:     (493046022100c9f4ebda0ef6a9cdfbec47395f6f9003db03fa6a1e988f6cf6c6)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 73ed5c2ebb46b065ce60e8032dbb302ca35844a422efe97c4e51a899b0f7b5d4 (BE)
         TxOutIndex: 0
         Script:     (483045022100eed323557e4c64468bbc6ea29127d7cc32174040abb1fad80e6f)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 7b22d93449f68c77e983e3293a9f7e2ff1d168cd38fe583e59fcb9f48920c2ee (BE)
         TxOutIndex: 0
         Script:     (47304402200b219204a17742c08b33f010273d8587d92e4250b785c20c202ada)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 3b3d950b16804433a6c51ee20b7f2cbf960c29d4f4f807d4401cf7ecbd129b5d (BE)
         TxOutIndex: 0
         Script:     (483045022100fb3c5b09df5f7ee08fd67a48f100bab72b98caca0627d38f27c5)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 0f2e75cd762a29e99833cd74cfb0146e8e0c9da154c28e3fe3f93b4ae07fb6ff (BE)
         TxOutIndex: 0
         Script:     (493046022100ef1b39f1c8e9a9cfea3078a9b84b14aa28e767f8d68e4f0350e1)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: d4bb36bc35374261d09fa9f1b32c30be42eeb7a1b6e065ad49f69ca90f82c9e3 (BE)
         TxOutIndex: 0
         Script:     (483045022048cdb8f317f34cd1ed2aa0f70233ed900ba09b530b7c45fb1756bd)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 673523e82a5522e43495806675fd55827551d19967717de7614a7cb1604ae11c (BE)
         TxOutIndex: 0
         Script:     (483045022100aac3d77c8aea7226d4ce907f3545d1c45dfa3b0e0218679a52df)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: d28f2ab759e302242c3364e2b3942b4f8726db582305df80deb5933ede6cb3ec (BE)
         TxOutIndex: 0
         Script:     (47304402201d26918c38b1200b3b8e3902fdc91ad0adc578b6d5cda1f30c94a7)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: b43aed06284a97a1977bc6f5f523e175dae220a7e3ea2bae79350279df2e396d (BE)
         TxOutIndex: 0
         Script:     (493046022100d461c1df9eb08a237f7fac396ed5ff4497ed2a6019b00a10b282)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: b593b0e4f026f0fa384dc821ffe4a70f567f55696ff509f4b0fa7e148b354815 (BE)
         TxOutIndex: 0
         Script:     (493046022100f35d2b1e7a695df93402d3dcdce356bc0e6d510d2fc437726508)
         Sender:     1MxgyKiKiHEemMUTJuq9NAbjmhKnUL5Ric
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 747969dcc31ea6c3ed01bf7a1c970d50d7dacb885068f8e03b464a5abdfa5e44 (BE)
         TxOutIndex: 0
         Script:     (4730440220704b975e73a8ceb2cff37580ea867a7a792b61b3762bae34092237)
         Sender:     1MxgyKiKiHEemMUTJuq9NAbjmhKnUL5Ric
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: e15cddae2f36bbf27045bba9aa0eede24e30e733a83bb4a2214d31a74731cdbd (BE)
         TxOutIndex: 0
         Script:     (47304402205be446e867d43b884756217bc6e1bd414354ad7d1ffbb6ae0b9f51)
         Sender:     1MxgyKiKiHEemMUTJuq9NAbjmhKnUL5Ric
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 3865e1176077e06eca8089bcc49691d22c285a7499564723041104baff1de558 (BE)
         TxOutIndex: 8
         Script:     (48304502206cedfbaf681a98c827445ef33851154dc16dda797a906cd2732e3e)
         Sender:     1Di6ux3CQBNXCZLD76BsnYWDo6XnFGzQah
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 204f7599883588e752578988bc43cb7572010ecd25fe8a34dba7ffdaadf592db (BE)
         TxOutIndex: 8
         Script:     (493046022100d2e46f587078fd6de62172908b5eb2962ea64dae3b6eb96e0a3e)
         Sender:     1Di6ux3CQBNXCZLD76BsnYWDo6XnFGzQah
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 30a8ed895212e2f7f18e67526ae37fbbdf9562017892f79ff8459226be627994 (BE)
         TxOutIndex: 8
         Script:     (493046022100bc7b0681e2ba82ad4f89e83fd21e1a94c6fb402de13cea22fb55)
         Sender:     1A3z7M6GhpUejQ5eqgSyjVWRuezeepdKKV
         Seq:        4294967295
   Outputs: 
      TxOut:
         Value:    10000000000 ( 100.0 )
         Script:   OP_DUP OP_HASH (1dice97ECuByXAvqXpaYzSaQuPVvrtmz6) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    10000000000 ( 100.0 )
         Script:   OP_DUP OP_HASH (1dice8EMZmqKvrGE4Qc9bUFf9PX3xaYDp) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    25000000000 ( 250.0 )
         Script:   OP_DUP OP_HASH (1dice7W2AicHosf5EL3GFDUVga7TgtPFn) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    10000000000 ( 100.0 )
         Script:   OP_DUP OP_HASH (1dice7fUkz5h4z2wPc1wLMPWgB5mDwKDx) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    5000000000 ( 50.0 )
         Script:   OP_DUP OP_HASH (1dice7EYzJag7SxkdKXLr8Jn14WUb3Cf1) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    1000000000 ( 10.0 )
         Script:   OP_DUP OP_HASH (1dice6YgEVBf88erBFra9BHf6ZMoyvG88) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    200000000 ( 2.0 )
         Script:   OP_DUP OP_HASH (1dice6DPtUMBpWgv8i4pG8HMjXv9qDJWN) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    100000000 ( 1.0 )
         Script:   OP_DUP OP_HASH (1dice5wwEZT2u6ESAdUGG6MHgCpbQqZiy) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    15215213996 ( 152.15213996 )
         Script:   OP_DUP OP_HASH (1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ) OP_EQUAL OP_CHECKSIG

Code:

Transaction:
   TxHash:    47bfb18624d0f1ed09e895fe427dcd9a3cef709d92ccedd48528b7774e8f7e23 (BE)
   Version:   1
   nInputs:   15
   nOutputs:  9
   LockTime:  0
   Inputs: 
      PyTxIn:
         PrevTxHash: e7b58ff78217d9c2dbf1241caf5fe4fcd92e0d2513377a172fd045549fcdc98f (BE)
         TxOutIndex: 0
         Script:     (00493046022100c9f4ebda0ef6a9cdfbec47395f6f9003db03fa6a1e988f6cf6)
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 73ed5c2ebb46b065ce60e8032dbb302ca35844a422efe97c4e51a899b0f7b5d4 (BE)
         TxOutIndex: 0
         Script:     (483045022100eed323557e4c64468bbc6ea29127d7cc32174040abb1fad80e6f)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 7b22d93449f68c77e983e3293a9f7e2ff1d168cd38fe583e59fcb9f48920c2ee (BE)
         TxOutIndex: 0
         Script:     (47304402200b219204a17742c08b33f010273d8587d92e4250b785c20c202ada)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 3b3d950b16804433a6c51ee20b7f2cbf960c29d4f4f807d4401cf7ecbd129b5d (BE)
         TxOutIndex: 0
         Script:     (483045022100fb3c5b09df5f7ee08fd67a48f100bab72b98caca0627d38f27c5)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 0f2e75cd762a29e99833cd74cfb0146e8e0c9da154c28e3fe3f93b4ae07fb6ff (BE)
         TxOutIndex: 0
         Script:     (493046022100ef1b39f1c8e9a9cfea3078a9b84b14aa28e767f8d68e4f0350e1)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: d4bb36bc35374261d09fa9f1b32c30be42eeb7a1b6e065ad49f69ca90f82c9e3 (BE)
         TxOutIndex: 0
         Script:     (483045022048cdb8f317f34cd1ed2aa0f70233ed900ba09b530b7c45fb1756bd)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 673523e82a5522e43495806675fd55827551d19967717de7614a7cb1604ae11c (BE)
         TxOutIndex: 0
         Script:     (483045022100aac3d77c8aea7226d4ce907f3545d1c45dfa3b0e0218679a52df)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: d28f2ab759e302242c3364e2b3942b4f8726db582305df80deb5933ede6cb3ec (BE)
         TxOutIndex: 0
         Script:     (47304402201d26918c38b1200b3b8e3902fdc91ad0adc578b6d5cda1f30c94a7)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: b43aed06284a97a1977bc6f5f523e175dae220a7e3ea2bae79350279df2e396d (BE)
         TxOutIndex: 0
         Script:     (493046022100d461c1df9eb08a237f7fac396ed5ff4497ed2a6019b00a10b282)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: b593b0e4f026f0fa384dc821ffe4a70f567f55696ff509f4b0fa7e148b354815 (BE)
         TxOutIndex: 0
         Script:     (493046022100f35d2b1e7a695df93402d3dcdce356bc0e6d510d2fc437726508)
         Sender:     1MxgyKiKiHEemMUTJuq9NAbjmhKnUL5Ric
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 747969dcc31ea6c3ed01bf7a1c970d50d7dacb885068f8e03b464a5abdfa5e44 (BE)
         TxOutIndex: 0
         Script:     (4730440220704b975e73a8ceb2cff37580ea867a7a792b61b3762bae34092237)
         Sender:     1MxgyKiKiHEemMUTJuq9NAbjmhKnUL5Ric
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: e15cddae2f36bbf27045bba9aa0eede24e30e733a83bb4a2214d31a74731cdbd (BE)
         TxOutIndex: 0
         Script:     (47304402205be446e867d43b884756217bc6e1bd414354ad7d1ffbb6ae0b9f51)
         Sender:     1MxgyKiKiHEemMUTJuq9NAbjmhKnUL5Ric
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 3865e1176077e06eca8089bcc49691d22c285a7499564723041104baff1de558 (BE)
         TxOutIndex: 8
         Script:     (48304502206cedfbaf681a98c827445ef33851154dc16dda797a906cd2732e3e)
         Sender:     1Di6ux3CQBNXCZLD76BsnYWDo6XnFGzQah
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 204f7599883588e752578988bc43cb7572010ecd25fe8a34dba7ffdaadf592db (BE)
         TxOutIndex: 8
         Script:     (493046022100d2e46f587078fd6de62172908b5eb2962ea64dae3b6eb96e0a3e)
         Sender:     1Di6ux3CQBNXCZLD76BsnYWDo6XnFGzQah
         Seq:        4294967295
      PyTxIn:
         PrevTxHash: 30a8ed895212e2f7f18e67526ae37fbbdf9562017892f79ff8459226be627994 (BE)
         TxOutIndex: 8
         Script:     (493046022100bc7b0681e2ba82ad4f89e83fd21e1a94c6fb402de13cea22fb55)
         Sender:     1A3z7M6GhpUejQ5eqgSyjVWRuezeepdKKV
         Seq:        4294967295
   Outputs: 
      TxOut:
         Value:    10000000000 ( 100.0 )
         Script:   OP_DUP OP_HASH (1dice97ECuByXAvqXpaYzSaQuPVvrtmz6) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    10000000000 ( 100.0 )
         Script:   OP_DUP OP_HASH (1dice8EMZmqKvrGE4Qc9bUFf9PX3xaYDp) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    25000000000 ( 250.0 )
         Script:   OP_DUP OP_HASH (1dice7W2AicHosf5EL3GFDUVga7TgtPFn) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    10000000000 ( 100.0 )
         Script:   OP_DUP OP_HASH (1dice7fUkz5h4z2wPc1wLMPWgB5mDwKDx) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    5000000000 ( 50.0 )
         Script:   OP_DUP OP_HASH (1dice7EYzJag7SxkdKXLr8Jn14WUb3Cf1) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    1000000000 ( 10.0 )
         Script:   OP_DUP OP_HASH (1dice6YgEVBf88erBFra9BHf6ZMoyvG88) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    200000000 ( 2.0 )
         Script:   OP_DUP OP_HASH (1dice6DPtUMBpWgv8i4pG8HMjXv9qDJWN) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    100000000 ( 1.0 )
         Script:   OP_DUP OP_HASH (1dice5wwEZT2u6ESAdUGG6MHgCpbQqZiy) OP_EQUAL OP_CHECKSIG
      TxOut:
         Value:    15215213996 ( 152.15213996 )
         Script:   OP_DUP OP_HASH (1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ) OP_EQUAL OP_CHECKSIG

[dooglus]

I mentioned these apparently double spends here.  The guy owing these transactions had a pretty unlikely winning streak overnight.

the first one is the transaction that was invalidated (containing 613 BTC to SD), and the second one is the one that replaced it, looks to be similar... probably just a "re-roll":

The two transactions are apparently almost identical.  All the inputs and outputs are the same (except for the first input script, which starts with an extra 0 byte in the 2nd transaction).  It looks like the same transaction was just slightly modified, re-signed and re-sent.

As a result, your formatting of the transactions shows no 'sender' for the 1st input of the 2nd transaction:

Code:

Transaction:
   TxHash:    54825a1963a0fc4b566cd415690986c835a84974ceb00ae3649ed311a39d2a2e (BE)
[...]
   Inputs: 
      PyTxIn:
         PrevTxHash: e7b58ff78217d9c2dbf1241caf5fe4fcd92e0d2513377a172fd045549fcdc98f (BE)
         TxOutIndex: 0
         Script:     (493046022100c9f4ebda0ef6a9cdfbec47395f6f9003db03fa6a1e988f6cf6c6)
         Sender:     1EP4rM8hLZCRSWPNZDWJp9zdvmoWYkkgbQ
         Seq:        4294967295
[...]

Code:

Transaction:
   TxHash:    47bfb18624d0f1ed09e895fe427dcd9a3cef709d92ccedd48528b7774e8f7e23 (BE)
[...]
   Inputs: 
      PyTxIn:
         PrevTxHash: e7b58ff78217d9c2dbf1241caf5fe4fcd92e0d2513377a172fd045549fcdc98f (BE)
         TxOutIndex: 0
         Script:     (00493046022100c9f4ebda0ef6a9cdfbec47395f6f9003db03fa6a1e988f6cf6)
         Seq:        4294967295
[...]

Edit: http://blockchain.info/tx-index/47564468 confirms that the first input script starts with an OP_FALSE, but of course that doesn't matter because the rest of the script is pushed on top of it on the stack.  The OP_FALSE will still be on the stack when the script finishes executing, but, according to the wiki, "A transaction is valid if nothing in the combined script triggers failure and the top stack item is true", so the buried OP_FALSE doesn't matter.

[dooglus]

I see three more pairs of double-spends from the same wallet:

75c39711ab8dee9fd6c6b166c17b6a12209d472990b230c0bb2ce0d8bd0fb248 and c651661bbe39c1dabe52892fce8eeef8932ba349392b64b5848167e683128cd4,

87d222fcee789576195fd524b22f84e1562d241e67bbc3e971b4d6659da0be91 and c97a74b8ba7edacc72f2be39a05a0ff2b8821ec87e16fb400458d8d6ff8086d4

28be43a55c9a88e11254094be7486e6c6db9d6c73bd352bbfea0f9abc5e33170 and 5a9c49c118e1655b511b76a0cb2978f4b5ebe7773a938664ecf304b5c35a9ee7.

In each pair, the two transactions are identical except that the first input script is one byte longer in the 2nd of the pair.  For instance, in the first pair we see input scripts:

30 46 02 21    00da2f0d0925960b1c8cb87fc04e02ddfd8cb6cfa947c656e652d1fb315ef66db5022100a494956 71a1f6f86520a126780f980a6fee0e22943143527cca38b3f489704f401 04090871c9bb80ebcd923d8e8b76194085afc9d417831545b4380cacc02dc2214966eea799a3d04 a2098c12d76aab3bbd95d94ec985094a71830e2bb739a255788

and

30 47 02 22 00 00da2f0d0925960b1c8cb87fc04e02ddfd8cb6cfa947c656e652d1fb315ef66db5022100a494956 71a1f6f86520a126780f980a6fee0e22943143527cca38b3f489704f401 04090871c9bb80ebcd923d8e8b76194085afc9d417831545b4380cacc02dc2214966eea799a3d04 a2098c12d76aab3bbd95d94ec985094a71830e2bb739a255788

So the input wasn't even re-signed.  The old signature was simply left-padded with an extra zero byte, changing the txid.

[Peter Todd]

So the input wasn't even re-signed.  The old signature was simply left-padded with an extra zero byte, changing the txid.

Just to re-iterate: this kind of modification, transaction malleability, is something that can be done by miners without the person who submitted the transaction even knowing. In other words that "high-roller" may not have had anything to do with the double-spend at all.

It's especially ugly because an evil miner can simply watch the mempool for all losing satoshi-dice transactions, and then modify every one of them and attempt to mine a block filled with now-modified transactions. Of course the miner doesn't know satoshidice's secret, so they can't pick winners or losers - they are essentially rolling the dice again - but for every game with a win probability of p your new win probability will be p + p^2. For instance if you bet on a 50% chance game, you'll now have a 75% chance of winning. On a 25% chance, you'll now have 37.5% chance.

In fact, it can be done by a non-miner who is well connected too: again, watch for satoshidice wins, and this time use a form of transaction malleability that is a standard transaction and thus will be relayed by other nodes. Now immediately broadcast the modified transaction to as many nodes as you can. The vast majority of the time nothing will happen - the modified tx won't be accepted because nodes already have the original - but every once in awhile it will happen to be accepted by a miner and get confirmed.

A simple way to fix this issue would be to first only accept bet transactions whose inputs are confirmed, and secondly change the lucky number algorithm from hmac_sha512(secert,txid:out_idx) to hmac_sha512(secert,txin_1:out_idx | txin_2:out_idx ... | txin_n:out_idx) This works because the betting transaction refers to the txin's by hash, so if you change the betting transaction hash, the lucky number doesn't change, on the other hand the txin's are already confirmed in the chain and can't be changed. Note that you'll need to ensure the SIGHASH bits in the signatures are their standard value; ANYONECANPAY still allows changing the txin set without invalidating the signatures. Of course regular double-spends are still possible, but at least they can't be done by a third party.

Note that having the txin's be confirmed is essential: if they aren't you can pull an even worse version of the same trick by modifying the txin hash, thus invalidating the bet transaction.

EDIT: While we're at it, I also noticed that satoshidice is accepting transactions with non-default SIGHASH's for the signatures. For instance I just made bde69c82fa0870bb156edb334da4a8013d5d385e93608110313a8695184d6365 with the signature using SINGLE|ANYONECANPAY, which means any node on the network is free to add their own inputs and outputs to the transaction provided they do not modify the one input and one output I signed, again changing the tx hash. It's a more minor issue, but it would allow people to setup co-operating decentralized double-spenders without even having to communicate what transactions to double-spend too.

EDIT2: The really interesting thing would be to come up with a form of malleability that is undetectable after the fact. Satoshidice could also just not transmit wins when the second, winning, transaction gets mined. They can prove their honestly by just pointing out that the second tx was modified, and the first was normal. However if you can come up with a form of malleability where both transactions are indistinguishable there will be know way of knowing if the miner turned a win to a loss or vice-versa, and hence satoshidice doesn't have much choice other than paying out the wins. At this point they simply have to change the way wins are calculated.

[dooglus]

Just to re-iterate: this kind of modification, transaction malleability, is something that can be done by miners without the person who submitted the transaction even knowing. In other words that "high-roller" may not have had anything to do with the double-spend at all.

That is a very good point!  Anybody at all can create modified versions of any transaction in that manner and change its txid arbitrarily.  This presents a way for satoshidice to cheat their players too, by transmitting modified versions of winning bets before they confirm.

[apetersson]

That is a very good point!  Anybody at all can create modified versions of any transaction in that manner and change its txid arbitrarily.

If i understand that correctly, that means SD will be exploited soon by players, well-connected hosts or miners?

[Peter Todd]

That is a very good point!  Anybody at all can create modified versions of any transaction in that manner and change its txid arbitrarily.

If i understand that correctly, that means SD will be exploited soon by players, well-connected hosts or miners?

Not at all. Remember that the modified transaction still goes to the same place, so SD still gets their money. SD just needs to stop paying out twice when it sees two transactions spending the same input.

Re-read my last point at the bottom about undetectable forms of malleability, and keep in mind it's only an issue because players communicate with SD via the blockchain, and the blockchain is public.

[SRoulette]

A simple way to fix this issue would be to first only accept bet transactions whose inputs are confirmed, and secondly change the lucky number algorithm from hmac_sha512(secert,txid:out_idx) to hmac_sha512(secert,txin_1:out_idx | txin_2:out_idx ... | txin_n:out_idx)

That is an excellent proposal, one which we will be implementing shortly

[Peter Todd]

A simple way to fix this issue would be to first only accept bet transactions whose inputs are confirmed, and secondly change the lucky number algorithm from hmac_sha512(secert,txid:out_idx) to hmac_sha512(secert,txin_1:out_idx | txin_2:out_idx ... | txin_n:out_idx)

That is an excellent proposal, one which we will be implementing shortly

Good to hear!

One last thing, you also need to mandate that at least one txin signature uses SIGHASH_ALL so the txin list can't be changed after the fact. Once you've taken that step you'll only be vulnerable to regular, miner-supported, double-spends.

EDIT: fixed SIGHASH_NONE brainfart.

[Mike Hearn]

You meant SIGHASH_ALL, right? SIGHASH_NONE is not generated by any client today and makes a wildcard transaction that can have any outputs.

[Peter Todd]

You meant SIGHASH_ALL, right? SIGHASH_NONE is not generated by any client today and makes a wildcard transaction that can have any outputs.

Good catch, fixed.

[SRoulette]

Say if you connected to a 1 well connected node (eg slushpool) and used -nolisten, would this also prevent seeing modified versions of the same txid ?
Or is it possible for a non malicious node to rebroadcast the same spending of inputs a 2nd time using a diff signature ?

In fact, it can be done by a non-miner who is well connected too: again, watch for satoshidice wins, and this time use a form of transaction malleability that is a standard transaction and thus will be relayed by other nodes. Now immediately broadcast the modified transaction to as many nodes as you can. The vast majority of the time nothing will happen - the modified tx won't be accepted because nodes already have the original - but every once in awhile it will happen to be accepted by a miner and get confirmed.

re-reading this I appreciate it a bit more, so by connecting to trusted peers "should" eliminate risk of a re-roll.

Something my code monkey suggested

Code:

# just testing and brain storming alt solutions to this issue on the test engine
hmac_sha512(secret(join(sort(@all_vout_txids)))

[Peter Todd]

Say if you connected to a 1 well connected node (eg slushpool) and used -nolisten, would this also prevent seeing modified versions of the same txid ?
Or is it possible for a non malicious node to rebroadcast the same spending of inputs a 2nd time using a diff signature ?

In fact, it can be done by a non-miner who is well connected too: again, watch for satoshidice wins, and this time use a form of transaction malleability that is a standard transaction and thus will be relayed by other nodes. Now immediately broadcast the modified transaction to as many nodes as you can. The vast majority of the time nothing will happen - the modified tx won't be accepted because nodes already have the original - but every once in awhile it will happen to be accepted by a miner and get confirmed.

re-reading this I appreciate it a bit more, so by connecting to trusted peers "should" eliminate risk of a re-roll.

No, the re-roll there happens because the tx gets mined, and thus the first tx gets removed from your mempool, and you see the second one. After the fact it will look like you received a bet but never paid out.

Something my code monkey suggested

Code:

# just testing and brain storming alt solutions to this issue on the test engine
hmac_sha512(secret(join(sort(@all_vout_txids)))

If sorting the txin's makes it easier to code, that's fine, but remember that regardless you must ensure at least one of the signatures uses SIGHASH_ALL or anyone can add extra txin's and change the lucky number.

[SRoulette]

I see, so the unconfirmed gets broadcasted, then the modified tx double spends it successfully it gets 1 confirmation and is relayed after 1 or more confirmations by all nodes regardless of the first unconfirmed (now invalid) tx.

Very very cool, code monkey and I are looking @ bitcoin Script now, might have to hack up a parser for perl - fortunately it is extremely well documented in the wiki .
Another suggestion he made is to keep a list of inputs spent against the casino and decline any bets that attempt to reuse the inputs.

edit: seems a perl bitcoin Script implementation already exists https://github.com/grondilu/libbitcoin-perl/blob/master/Bitcoin/Script.pm

[Mike Hearn]

SIGHASH_ALL is the default so it should work fine.

[Peter Todd]

SIGHASH_ALL is the default so it should work fine.

It may be the default, but if you don't make sure SIGHASH_ALL is actually being used an attacker can make bets and use the malleability as a way of recovering their loses while denying that they did it. I also explained elsewhere how people could agree to help each other recover their loses using this method, and that cooperation can happen without any central co-ordination at all.

[dooglus]

Another suggestion he made is to keep a list of inputs spent against the casino and decline any bets that attempt to reuse the inputs.

How about just rejecting transactions with non-canonical signatures.  The bot that is making the double-spends is simply adding an extra 00 to the front of one of the signatures.  If you filter out all such transactions you'll be OK.

In the event that the bot's cloned transaction gets mined and the original bet transaction doesn't, it will look as if you ignored a bet, but you can point out that the bet has a non-standard signature which is why you didn't accept it.