Bitcoin Forum

I am running a custom node that does real-time double spend analysis. I took a look at the log file over the last few days to see what was going on now that we have a lot of focus on malleable transactions.

Note that my custom node counts mutations on the same transaction as a double spend, which it isn't.

Detected double spends by date:

2014-01-29 470
2014-01-30 460
2014-01-31 460
2014-01-29 470
2014-01-30 460
2014-01-31 0
2014-02-01 39
2014-02-02 18
2014-02-03 97
2014-02-04 918
2014-02-05 461
2014-02-06 406
2014-02-07 769
2014-02-08 1260
2014-02-09 2618
2014-02-10 14576
2014-02-11 16960
2014-02-12 393
2014-02-13 219
2014-02-14 54

Needless to say that things got hectic yesterday with 14576 "double spends" which I am pretty sure are malled transactions.

We seem to be approaching the total number of transactions which is about 60k a day. So it seems that someone is having a lot of fun.

I will be changing my software to do real malled transaction detection to get some more accurate numbers.

Edit 1: added stats for 2014-02-11
Edit 2: added stats for 2014-02-12
Edit 3: added stats for 2014-02-13
Edit 4: added stats for 2014-02-14

What do you mean by double-spend?

Two transactions with different hashes and with overlapping inputs.
The definition is not entirely correct as a malled tx is not a double spend.

it will result in one though if the user has also tried to spend the change output of the original transaction that was voided by the malleable one. this seems to be happening quite a lot based on network chatter. probably because the client allows spending the change while it's unconfirmed.

Correct. All wallets allowing spending unconfirmed coins-sent-to-self (bitcoin-qt included) are potentially affected.
If this trend continues wallets may have to abandon this practice until mallability issues have been resolved.

Yes, those are very probably "mutated" transactions - I'm getting those "double spend attempts" on every and each transactions I've been transmitting since yesterday.

Pretty useless stuff for the attacker, but I can bet that some novice got scared by seeing two transactions instead of one.

Hey Jan,

thanks for sharing. Is there a way to get those stats without any modifications from bitcoind? Would be nice, if you could keep this thread updated as it looks like the amount of attempted double spends still increases.

These stats are really disconcerting.
The priority of the core devs should be to fix the malleability issue once and for all. It shouldn't be a problem to get a majority of the network to agree to some patch. I think everyone would agree that it would be good for Bitcoin to just disallow transaction malleability.

Also it would solve the problems with mtgox withdrawals. Of course, in principle, it is a bug in the mtgox wallet. But this shouldn't be the time to accuse each other. Just solve the issue in the protocol and everyone will be fine and we would all have a better Bitcoin after all this mess.

2014-01-29 470
2014-01-30 460
2014-01-31 460
2014-01-29 470
2014-01-30 460
2014-01-31 0
2014-02-01 39
2014-02-02 18
2014-02-03 97
2014-02-04 918
2014-02-05 461
2014-02-06 406
2014-02-07 769
2014-02-08 1260
2014-02-09 2618
2014-02-10 14576
                ---------
                23 482 BTC stolen? all from gox?

I don't know how to get the stats from bitcoind, but looking into my debug.log I see a bunch of messages containing "was not accepted into the memory pool"
Many of those may be mutated transactions.
You can get a feel of how many there are by executing this (on a unix box):

In the meantime I can report that it has intensified. For today I have observed 16k "double spends", and there are still 9 hours left of "my today" (CET)

I will continue updating this thread as long as there is something interesting to report.

No. Those numbers are assumed transaction mutations on the bitcoin network over the last few days

Is there a way to calculate how many btcs were stolen through these malled / assumed malled transactions?

I had a similar issue about one year ago. I was using bitcoind offline to issue several transactions, and probably some were taking change from the previous ones.

Afterwards, I took all the generated txs with getrawtransaction and went broadcast them through a connected computer on blockchain.info/pushtx.

I then saw that some were refused due to already spent outpoints, and I think it might be the very problem you are talking about.

But as long as there is no real attack, just rescanning to reference the mutated txid for subsequent spendings should be sufficient right?

I can't think of a way to do that, and frankly I wouldn't care. It seems that someone is trying to mutate all transactions right now, not only those from MtGox.

This is not an useful stat to determine the amount of lost-due-to-whatever-reason coins and you'd need to ask the exchange or service provider for any data.

Don't worry, the amount of attempted double spends is irrelevant.

Just trying to find out if the exchange I am using will go bust  ;D

This did not yield any result, however there are more than 58k appearances of "ERROR: CTxMemPool::accept() : inputs already spent" and 28k for "nonstandard transaction type" since Jan 07, 2014. Maybe I'll give it a try later and group those by date. Thanks. :)

Do you know where these  28k for "nonstandard transactions come from? Normal nodes do not relay them. At least that is what I thought.

following

is this the same issue being discussed about blockchain wallet TM spam?
bitcointalk.org/index.php?topic=459874.0

also this is the same issue?
bitcointalk.org/index.php?topic=459845.0

this spam will hurt credibility of bitcoin and it seems to be related with all the exchange withdrawal slowdowns?

Hm. I'm unable to draw any conclusions based on the debug.log, but I extracted some lines and put it up on pastebin.com:


http://pastebin.com/raw.php?i=qbt1Mgpw (nonstandard transaction type)
http://pastebin.com/raw.php?i=D1xzU0FU (inputs already spent)

It appears that those non standard tx are not relayed, as you mentioned.

Edit:
Spam marketing/advertisement via dust transactions has nothing to do with the mallability spam bot. :)

Malled transactions cannot steal coins.

MtGox is losing coins because they are allowing customers to perform a withdrawal, claim they never received it, and then MtGox manually sends them a new withdrawal!

Does your exchange do that?

Why no one uploaded a video in youtube telling how to receive unlimited bitcoins using the malleability trick on MtGox?  ;D ;D ;D

here is my concern situation:

You have a bitcoin-qt wallet with 3BTC
you send 1BTC to somebody, and the wallet also sends some BTC to a change address within itself
a malled txid repeats this exact same transaction, and is seen by the bitcoin-qt wallet

what happens:
a) your wallet shows a balance of 2BTC and an unconfirmed txid that will never complete
b) your wallet shows a balance of 1BTC because it thinks that there is 1BTC that you sent away waiting on confirmation
c) your wallet shows something else entirely because the change addresses get FUBAR'd

My biggest concern is that while these malled transactions wont cause clients/wallets to report the wrong balance for received transactions (because it never confirms the second deposit), what if it is incorrectly displaying balances after a SENT transaction is malled with a copied txid that the wallet sees in the blockchain and beleives you have asked toi send funds

Any observable correlation with specific mining pool/s? Seems like a large number of successful id mutations

Can we get updated stats thus far today?

None of the a), b) or c) you've suggested is correct, although a) is close. Your wallet will show 2 BTC, and one of the two transactions, original or mutated one, will be confirmed and included in the blockchain permanently. Only thing that is let to be uncertain is the TxID of the confirmed transaction, it can be either one of these, depending on the miner who finds the block which includes the transaction, that miner decides which one will be in the blockchain forever.

Bitcoin-qt wallet is completely unaffected by this problem, so there's zero chance you can lose funds. Unfortunately, exchanges can't use that wallet in a way single persons use it because they serve multiple accounts, so they make their own wallet software implementation. MtGox software is sub-par, and depends on the TxID to account for the payment, which is unacceptable, only inputs and outputs inside the transaction should define if the funds are moved or not.

AFAIK the miner doesn't get to decide either, it takes the first (version of the) transaction it receives from the network.

OK. Get it.



It is my understanding that both Gox and Stamp allowed this scheme - both halted btc withdrawals.



Gox and Stamp are my exchanges. I wanted to find out if there is a way to aproximate the value of double withdrawals from Gox and Stamp up till now.

E.g. someone finds a 7.95757474 BTC transaction from Gox address to a dishonest client's address on a certain day and next finds a corresponding doubled withdrawal of 7.95757474 BTC a few days later.

This is just an idea by a non-techie (me), so don't laugh at me.

Would it be at all possible to estimate the value of double withdrawals (effected through malled transactions)? If the exchanges were tricked into resending 1k BTC then it's no problem. If they were tricked into resending 100k BTC, then we might have a big problem.

Yes, that's what I've meant, "decide" was not the right term. One group of miners will receive original transaction first, the other group will receive the mutated one first. Whichever group submits solved block to the blockchain first "decides" which transaction is committed. Notice that whoever mutates these transaction must be very, very quick to be successful doing this, original transactions move across the network fast, and they have to beat them before they propagate to the majority of the network.

You sure? It's pretty usual practice for Bitcoin merchants to update database upon transaction first seen in the network.

Usually funds are not released until confirmations come in, but I'm willing to bet there are businesses experiencing considerable losses because their bitcoind reports two incoming transfers while only one is valid.

Malled transactions never get even a single confirmation, right?

It's not quite easy to hide your identity from the exchanges, one mistake and you reveal your router's IP to them. After that you are at their mercy not to bring up criminal investigation at you. MtGox maybe will not chase somebody and report him to the authorities for 1 BTC, but for 1k BTC they would surely do everything to put whoever does this in jail.

If you think massive bitcoin network attack is going to be exposed by linking to an IP address, then you greatly underestimate who you're dealing with.

Keep in mind that exchange has in their logs every IP from which you accessed them ever. That data is never erased and regularly log-rotated and backuped for legal purposes. I'm not saying it will be easy for them to catch who's messing with them, but you can bet they will do everything to reveal real identity of that account holder.

I'm no expert on this stuff, but I'm wondering, could this behavior in the reference client be amplifying the effects of the malled TX attack as measured in the OP?  i.e. When a client attempts to spend unconfirmed change that never gets confirmed because its tx got malled, is that also counted as a double-spend attempt?

Not it would simply be an unconfirmed tx and after the parent is dropped it becomes an invalid tx.

However it is a genuine case for concern.  There is no profit in it, but the combination of:
a) malicious user malling all tx
and
b) the QT client using unconfirmed change outputs in new tx

can lead to a lot of confusion and broken transactions.   I am not sure what the immediate fix it.

One option would be to either by default or by a user enabled option don't use change outputs until they have at least 1 confirmation.  That combined with simply "hiding" duplicates would make the mutated spam pretty much invisible to "normal users".  Merchants and service providers not using a payment processor need to understand the mutability of txids but honestly they already should.

Would that require a hard fork or just software update on bitcoin-qt and other wallet software? Im guessing the latter. That sounds like a short term solution at least.

The later.  It would be a client side change only and wouldn't require the support of anyone beyond the user using it.

It really is not that much of a problem IMHO. If those change outputs will eventually confirm or not has nothing to do with mutated TxID. If someone wants to include unconfirmed change outputs as his new inputs that's his problem. His last transaction will eventually confirm if those outputs are regular payment, or fail if it is double-spend attempt. The system is designed to work this way.

I think you are misunderstanding.  

I send you 1 BTC.   It is tx id A.   Someone mutates it so there is a copy with tx id B.

You send a 0.1 BTC to your friend.   As a normal user it isn't you, but the QT client which picks which inputs are used.  The client picks tx id A, index 0 as the input for this new outbound tx.  It can do this because by the QT client right now uses unconfirmed change outputs as inputs in new txs.

Now lets say tx B not A ends up in a block.  Oops. 

The tx to your friend is now invalid, it uses as its input an output which is a double spend (tx a) of a valid confirmed tx (tx b) and thus will never confirm.  There is no user friendly way for you to remove that from your wallet.  Most users may not even know why it didn't work.  They will see the tx to their friend simply never confirms.  It won't be marked as a double spend (because it isn't) it simply will never confirm because it is no longer valid, it became invalid as soon as B not A was included in a block.  It can be solved but it is far from user friendly.  Now imagine that happening for thousands of users every single day forever because some malicious user is intentionally mutating tx to cause chaos.  Nobody ends up losing coins but it makes the system look bad, counterintuitive, and confusion especially for newer users.

If you wait until a tx is confirmed then the txid is immutable (baring a network re-org) and this becomes a non-issue.  Right now there is no way for an average user to force the client to only used confirmed change in new transactions even if they wanted to, other than manually wait and make sure they have no unconfirmed change outputs before sending funds.

I see what you mean, you are right. Would a simple configuration option whether to show unconfirmed inputs in the balance do the trick? No may be the default option, and you can always go to the console and temporarily force the opposite behavior if you want to. It may not even mess up how QT client handles the blockchain, just how it calculates the balance.

Edit: I have to check how it is this done right now in the code. I'm not positive how the balance is calculated.

THIS.

I compared my wallet balance against the transaction export and found that the two DID NOT MATCH. my hot wallet is 'richer' by exactly the amount in the second transaction's change wallet - I am not 100% sure which total is correct, though I imagine the wallet balance is the correct version

EDIT: my client just forced me to undergo 'reindexing blocks on disk', a process that appears to be going to take ~20min

Jan,

Can your programme also calculate / include the information about the value of double spends?

Date           | Number of double spends      | Value of double spends
2014-01-29  | 470                                  | e.g. 59099 BTC

It looks like it's already done, there are GetBalance(), GetUnconfirmedBalance() and GetImmatureBalance() methods in /src/wallet.cpp (https://github.com/bitcoin/bitcoin/blob/master/src/wallet.cpp):


And there's a flag if unconfirmed outputs should be collected in spendable outputs:

So problem witch DeathAndTaxes talked about should not happen at all. If it does happen, there's easily correctable bug somewhere.

it's not a matter of wanting to include unconfirmed change outputs, it's the fact that the satoshi client does this by default and you can't stop it without patching it. so user is vulnerable to getting their wallet messed up.

This might be interesting.

https://github.com/bitcoin/bitcoin/pull/3651

Exactly what we talked above, lol. It really is the most obvious solution. There's already the pull request to make this the default option: https://github.com/bitcoin/bitcoin/pull/3654 (https://github.com/bitcoin/bitcoin/pull/3654)

Whenever I want to receive bitcoins, I give the sender a unique address. I couldn't care less what the TXID is. I think most merchants work the same way. Malled transactions do not change the addresses.

Any indication or chatter on when this patch will be available?

I guess the issue is more often that people do send Bitcoins, then get a TXID from bitcoind after submitting the RPC call and store that TXID in case they need to check later if that transaction really went through.

>it's not a matter of wanting to include unconfirmed change outputs, it's the fact that the satoshi client does this by default
is it a fact?

It seems so, not only unconfirmed change outputs but any unconfirmed outputs. The developers are applying patches to make the opposite the default behavior as we speak, the patch is seven hours old.

Yes.  The QT client (and all other clients AFAIK) does NOT allow spending unconfirmed outputs received from outside the wallet.  Change is treated differently and unconfirmed change is allowed to be spent.  Under normal conditions this is actually a beneficial thing (otherwise you can end up not being able to spend coins until change outputs confirm) but right now that action is undesirable.

The reference client will not allow spending unconfirmed outputs received from outside the wallet.

If I send you 1 BTC right now, the client will indicate you do not have sufficient funds to make a tx if you try to spend it before it confirms.  Change outputs are handled differently though and could break transactions which use them before they are confirmed.

Ah, yes, that's correct, sorry.

Byzantine Candor CNY tea-break

:D good call. The other "features" of this dataset are pretty interesting too, eh? The weird constancy around 460 and the massive ramp up just after the first Gox announcement.

The number of "double spends" (most of which I believe is mutated transactions) for the last 24 hours:
2014-02-11 16960
(will edit OP to reflect this)

It is slightly lower than I anticipated, as it was already above 16k 9 hours before the CET day ended (24 hours). Maybe the attack subsided, or someone is having a break.

Or maybe they went to bed around midnight? It's currently 9am in China...

LOL, isn't it MtGox with their custom client trying to re-submit failed transactions relentlessly?

Can you please post a couple of transactions to check what exactly was mutated? Many trivial mutations are already rejected by most nodes. Just want to see what's going on.

In addition to the above jgarzik is quoted on reddit to have said that one home PC could have done this. One home PC can screw up 25% of transactions!

Hold on. Are there actually any reports of something being screwed, apart from couple of exchanges who stopped withdrawals as a precaution measure?

yes, there are reports (http://www.reddit.com/r/Bitcoin/comments/1xm49o/due_to_active_malleable_transaction_relayers_it/). foundation blog also reports issues (https://bitcoinfoundation.org/blog/?p=422):.

It depends on what you mean by "screwed up".  The attacker can't change the inputs or outputs or fees, however they can change the tx hash of unconfirmed txs.  There were over 16,000 tx "mutated" in the last 24 hours.  I am sure they weren't all withdraws from exchanges. It would appear the attackers are simply mutating in mass all transactions they are able to and broadcasting the mutated version into the network.  If the mutated version of the tx is the one which gets confirmed it can have consequences for any user.

https://bitcointalk.org/index.php?topic=460944.0

someone has proven beyond a shadow of a doubt that bit coin is
capable of being manipulated.

someone would do that who has it in their interests to do that.
certainly many parties would fit that bill.

i agree with the writer who said now is not the time to point fingers.
Fix the present problem. No one will remember it in a month.

But the real problem is 20 million merchants just put Bitcoin on
the back burner for the next year. Not good for Bitcoin at all.

bad press == bad price. bad price == bad investment.

of course, a couple months ago, I suggested Bitcoin should build in the
exchange process into the wallets. Bitcoin touts its "decentralized" nature
but every exchange has an easy bulls-eye on its back for governments to
take aim at. In other words, since Bitcoin's exchanges are centralized,
so therefore is Bitcoin.

Just my two cents. Hope it helps. I would like to see Bitcoin thrive. It can become
the electric car of the monetary system,…. a valuable addition.

Define "screwed up". If your definition of "screwed up" includes a slowed down bitcoin economy because most (if not all) services are having problems with delayed transactions that are not credited to customer's accounts then YES, a single PC can "screw up" 25% of transactions and dramatically slow down the economy.

So, don't deliver until the transaction to you is confirmed, is that....news?

Obviously you didn't read the post or link.  I said nothing about delivering goods before confirmed.

I am not saying you have said anything wrong, I was referring to the panic. And I don't think such consequences can be considered "screwed up", as an end user I would probably not even notice anything other than a slow-up of the network if I don't pay attention.

You wouldn't notice a transaction you made (or someone made to you) that never confirms due to no fault of your own.  By never, I mean never. Not in an hour, or a day, or a year.  :)
Most people would and they probably would consider that "screwed up".

Well, I don't know about you, but when I actually want to see if my tx gets confirmed, I always search for the address and check if there is a new transaction with the correct amount, coming from the right address, probably it's just me though...

I have no idea how do other clients track the txs, but I would be utterly surprised if there are still that many using Bitcoin-Qt.

Once again you might want to read the link. I am not talking about it being confirmed under a new tx id.  I am talking about it NEVER confirming because it now has become invalid due to the inputs being invalid.

Well, you said the mutated one gets confirmed, can I find the one or not? Thanks.

EDIT: Okay, I read your OP, I was awfully unaware of the way the reference client works as I have never actually used it, thanks.

https://bitcointalk.org/index.php?topic=460944.msg5089865#msg5089865

Please actually read the section labeled "Mutable Transaction ids break spending unconfirmed change".

To answer your question.  No.  You can "find it" but a tx created from an unconfirmed change output which is subsequently mutated will never confirm.

I corrected my post, how many clients you know share the same behaviour?

EDIT: I would suggest you somehow also post your OP in the tech discussion board btw.

I am fairly certain that all (or nearly all) clients allow spending unconfirmed change outputs.  Until the "mass mutation attack" it improved the user experience to have this option.  Without the ability to spend unconfirmed change outputs the user could potentially (depending on what other confirmed outputs are available) need to wait for confirmations between spends.  I can't see any wallet intentionally doing that.  Many some minor less tested wallet may have accidentally ended up with that behavior.

AFAIK, Armory automatically send change to a new address, so at least it could have an option to disallow spending unconfirmed change outputs, unless there is nothing else spendable, should work in many cases.

Also, shouldn't the priority of spending be decided by the coin-age? As the fee rule discourages spending "hot" coins.

Manipulated? It can always be manipulated with enough money... Actually, for  a normal person/exchange this doesnt affect the btc, because we always waited for 3 or 6 confirms before delivering. It will clear up

Maybe this is too simple to be right, but...
Would not running rescan in bitcoin-QT from the time "some time before problematic unconfirmed-change-spending transaction" help?

I am certain it does, but since selection of what outputs are used for a new transaction is (mostly, unless you use coin control) out of your hands you can never be sure unconfirmed change has not been used.

It presumably would, and a few options such as last 100 or last 1000 might be sufficient.

The only concern would be that:
a) this would need to be implemented by each client
b) it *could* create weak points for an evil trojan/virus to replace and then rescan a false short blockchain - seems unlikely though

a) this is already implemented in each bitcoin-QT client. Although it would be time consuming to do it regularly.
b) creating "false blockchain" is almost impossible, it needs forking blockchain somewhere and then constructing new "false blocks". This "construction" means in fact mining new alternative and legitimate blocks from this fork. No single entity has enough computational power to do this. And some "easier blockchain" would not be correctly verified by reference client.

Seems we are back to business as usual.
2014-02-12 393
Updating OP.

Any reason to believe it won't happen again tomorrow? I think we'd all like to know when Bitstamp and other exc will start processing withdrawals again ;-)

Really sad that there is no solution to even clean these transactions manually... at least not for official bitcoin-qt client.

For those that have transactions that will never confirm, what is the procedure on QT to clean up the wallet?

Here in Vancouver, several brick-and-mortar businesses accept zero-confirm transactions using BitPay.  If you are buying a coffee, no one is going to wait 10 minutes (or longer) for confirmation;  it is critical that zero-confirm transactions are reasonably secure in order for this business model to work.  

So let me see if I understand the transaction malleability problem in relation to brick-and-mortar stores:

I pay for my coffee at Waves for 4mBTC.  Assume that to avoid "address reuse," my phone uses the full balance in 1AddressA, sends 4mBTC to Waves, and the rest to a new change address 1AddressB.  BitPay accepts this transaction and I get my coffee.  As soon as I finish paying, I realize that I also wanted a donut.  So I pay for this using what are now unconfirmed coins sitting in 1AddressB.  BitPay still approves the transaction and I get my donut too.  

But my first transaction was mutated, and the mutated version was accepted into the blockchain.  This means that the transaction I used to pay for my donut is now invalid, and Waves/BitPay won't get the money (and I've already left the store).  

This seems like a messy problem to deal with.  If we disallow spending unconfirmed change outputs, then there will be certain cases when I can't actually purchase my donut [without a long wait], correct?  Ideally, my wallet would try to break up my coins so that there are always plenty of fully-confirmed outputs ready for spending.  But how do most wallets actually work?  The Blockchain.info mobile wallet [that I use] sends the change back to the same address, so I'd expect that it would be very rare to have exhausted all of the confirmed outputs.  But for mobile wallets that avoid address reuse [do these even exist?], would it be less likely that you'd have confirmed coins available?

And should BitPay do anything to protect itself?

Yes, that is possible, but that's nothing new. Accepting with zero-confirm transactions is risky.

I disagree.  I think the community now sees zero-confirm transactions as more risky than prior to the malleability attack.  I know I do.  Previously, I think most people were under the impression that to invalidate a zero-confirm transaction (e.g., buying my donut at Waves in Vancouver), the customer would be the attacker (and basically had to be in cahoots with a nefarious miner in order to double spend).  The malleability attack has shown that even if both customer and merchant are honest, proper fees are paid, and the transaction propagates across the network, it's still possible (and in some cases probable) that the transaction doesn't go through (and thus D&T's solution to disallow transactions using unconfirmed "change" outputs).  

So I agree with D&T that we need a smarter way to deal with unconfirmed change, until malleability is properly fixed.  My question was if we enforce this new change rule, how often will casual users find themselves unable to pay immediately (such as my donut example)?  How will this impact the experience of say, my mom using her smartphone, who couldn't wrap her head around this?  

I agree, Before this I pretty much trusted each transaction without confirmations if as there was a fee paid. I really hope this Issue wil be fixed soon.

Very good example to think about, but: did I miss something? I think it won't happen, or at least doesn't have to. When you try to pay for the donut, assuming your wallet makes use of the change utxo which has been malled and is not yet confirmed, will bitpay accept it? I don't know whether they would today, but isn't it trivial to just check each utxo used as input and look at the blockchain to see if that transaction has any confirms? That way, they can accept unconfirmed spends, but not accept unconfirmed spends of unconfirmed spends, which is practically absolutely fine. Except you don't get your donut :D

Unless your wallet is coded to not use unconfirmed change...

Today BitPay would accept it.  Unconfirmed change is used rather routinely although probably will be changing soon.  In your scenario though the bad news is not BitPay needs to figure out a way to return your coins.  You can't undo it and eventually it will confirm (unless a duplicate of the prior output is what confirms).  So you are now out the donut and coins.  Of course the shop will have no clue how to get your coins back, and "you" (or a less educated user) might be kinda upset seeing the donut funds deducted from your wallet but not getting the donut and the clueless clerk having no idea how to get your coins back or even where they went.

If this happened enough the store might just not accept Bitcoin in the future.  Now I am not going all doom and gloom and none of this is unsolvable but you can see how all this starts to get really ugly real quick.  Transaction Ids need to be immutable.  Period.   There is no other viable long term option.  However that is going to take some time so things might get a little clunky for service providers before they get better.

Oh yes of course, stupid of me, the customer loses out there. But it still always comes back to the same thing for me: wallets should not attempt to spend unconfirmed change. Yes, I know there are some practical difficulties there with the way wallets are designed, but it doesn't look insurmountable - at worst it just causes a few inconveniences.

Do you realize how confusing and frustrating can be for users to disallow spending of unconfirmed change?

Imagine you received 100 BTC and you spend 1 BTC - suddenly 99 BTC become unspendable for 5,10, 30 minutes... That's very counter intuitive and will confuse a lot many users who do not understand how the protocol works.

Not allowing to spend unconfirmed change is an important steps backwards, and I think that we shouldn't downplay it's effect. I'd probably have it as an optional feature on the client, but if possible I wouldn't make it the default behaviour.

About 0-conf: for small, day by day payments they were absolutely safe. The cost to perform a double spend was simply not worth the cost of a coffee. Now, that changes, 0-conf are not safe even if the buyer is 100% honest and the cost of the product is negligible: again we cannot downplay the effect of that, it's quite serious.

The client could just try to/prompt to respend if after 10 minutes or so if it fails to see the expected change txid, but some outputs summed to the same amount with another txid getting confirmed in a block, and the sum of all outputs doesn't change.

Yes, I do appreciate the problem. But I would say it could/should be attacked from three angles: 1, disallow it by default but allow it to be switched on, 2, make people aware that they sometimes have to wait for confirmations before proceeding and 3, some alterations within wallets, e.g. automatic internal transfers to split up into denominations.

For sure, it is much more convenient if we don't have to worry about this - but if I'm reading things correctly, malleability is with us for some time.

Zero conf payments still work - it's just zero conf payments spending existing  zero confirm payments that don't.

Wallets will need to be "smarter".  A wallet knows how many unique unspent outputs it has.

So in the 100 BTC example it could spend it back to itself as 5x 20 BTC outputs.  Then a user could spend 1, have 19 BTC change confirming and still have 80 BTC available to spend.

Wallets also probably need to use simpler language like:  "Total balance: XXXX (available to spend: XXXX)  Why is this different?" with link/popup to simple user level explanation.

A "smart wallet" can engage in output management to minimize the disruption to a user.  There is no reason a tx must have 1 change output (to the protocol change is simply an output no different than the "intended" output).  If anything multiple change outputs would make blockchain analysis slightlymore difficult.  So when creating an outbound tx the wallet could look at its internal confirmed output pool and if it is "low" make 2 or more change outputs.  How many to make would depend a lot of the amount of the change (in BTC) and the number of unspent outputs (in discrete outputs not value).

Instead of

The wallet could instead do this:


Where * is a random amount such that the sum of the change addresses is 99 BTC.



It is important now with mass mutation attack going on to distinguish between:

0 confirm tx where all inputs are confirmed
vs
0 confirm tx where one or more inputs are also 0 confirm.

The former requires a race attack and malicious intent of the sender for the receiver to lose funds.  So if you trust your customers, or feel only a small % of your customers would attempt an attack you are relatively safe (especially for low value, low risk purchases).   The later however only requires that SOMEONE on the network mutate the prior unconfirmed transaction and that the mutated version ends up confirming.   The risk profile becomes "do you trust the entire world to not mess with your money even though it is painfully easy?"  In most cases that answer should be no.

In the donut shop example up thread, the customer isn't the one doing the mutating. He could be a regular customer and liked by the shopkeeper however his coffee tx gets mutated by a malicious third party.  Now mutated or not the coffee tx will go through, no risk to the shop there.   However if the duplicate is the one which is confirmed, then the change output used for the doughnut becomes invalid.  Now through no fault of either the shopkeeper or the legit customer the donut payment will never confirm.  It gets worse when you consider how confusing this will be to put the shopkeeper and the customer especially if their are "crypto-nerds".

Honestly until tx ids are immutable the use of unconfirmed change outputs is just going to cause mass chaos.  The long term goal should be immutable tx ids but lets be honest that is probably a six to nine month project.  It will most likely require a hard fork of the protocol and there is simply no fast and easy way to do that.    So in the immediate future transactions are mutable (even by third parties) and that means unconfirmed change can be broken by a malicious third party.  For the record the "DDOS attack" against exchanges involves this aspect of mutable transactions. 

I would also point out how nuanced this conversation is.  Now imagine someone who has a "user level" knowledge of Bitcoin.  Many people have no idea that Bitcoin works on the concepts of inputs and outputs.  Their knowledge is no deeper than the "abstraction" of wallet balances.  Now that is fine, the job of good software is to abstract a very complex system into a simple concept.  It isn't the user's fault that they don't know the inner workings, however you can't even start to explain the problem, until you explain how Bitcoin "really works".  That simply isn't a viable scenario for non-enthusiasts.  Case in point my need for a side note here: https://bitcointalk.org/index.php?topic=460944.0

Is this because of the attacker / the exchanges on hold?

Or is it because pools updated their software with the 0.8 fixes?

The attacker stopped.  Why and for long run remains unknown.  A patched client doesn't prevent the duplicates from existing so if tx were still being duplicated they should show up.

Wouldn't a better fix be to change the client behavior such that there is only one correct way to encode a transaction (with enforcement to begin in some future block), removing the possibility of malleability?

That is the long term fix.  You essentially are talking about transaction immutability.  However it can't simply be a client side "feature" as an attacker would just modify their client.  It will need to be enforced by the protocol.   That means (most likely) a hard fork and there just is no way to do that "fast and easy".   The situation is made more complex by the fact that ECDSA signatures are not "unique" it is possible for more than one set of inputs to produce the same signature. 

Simple version:
Long Term Goal (hopefully share unanimously by core developers):  Make unconfirmed tx ids immutable (or at least immutable to third parties).
Short Term Goal: Client behavior in dealing with mutable tx ids needs to be more consistent and expected until we get to the long term goal.

As a historical note.  Adding P2SH was a much simpler fork to the protocol.  From the time that P2SH code was completed to the time P2SH was supported by the protocol was about 8 months.

I thought 0.8+ clients did not relay some (the current?) malled transactions...


It would be fun to try and find the source nodes (given they can be distinguished and it's not a large botnet). Of course this is not a solution (Tor, intermediate node, ...).
1. Get well connected, don't relay malled txs
2. Wait until a malled tx propagates through the network
3. Drop the 50% connections that you receive the malled tx from last
4. goto 1

optional 3b. ddos the #1 node on the list until it stops

The network police 8) might come handy with some types of ddos attacks

I wonder if anybody ever tried homing in on a malicious node like this.

Distinguishing between those two types of transactions is fine from a technical point of view but we'd never be able to explain that difference to a customer.  I'm mostly concerned about the customer service problems this will create.  Alice gets her donut because she spent confirmed inputs.  Bob doesn't get his donut because he spent unconfirmed change.  Neither Alice nor Bob have clue what any of that means.  How do we explain to Bob that he doesn't get his donut without resulting in a fist fight, a discrimination lawsuit, an all day seminar on the technical workings of the blockchain, giving away a free donut, and/or potentially losing Bob as a regular customer?

Are there any ideas on whether a technical solution to this problem will be forthcoming or any suggested workarounds?

What about a soft fork: pools don't include malled txs and clients don't relay them. I think this would very quickly solve the problem.

Seems obvious to me. You don't try and spend what you don't know you have. Maybe that means wallets have to jump through hoops or you just don't get your donut but to my mind, that's what it boils down to. Bitcoin is supposed to be about cold, hard facts not payday loans.

Hey,

I have been working on the idea about trying to find the rogue nodes/pool over the past day or so. Check this thread for more https://bitcointalk.org/index.php?topic=463350.0 (https://bitcointalk.org/index.php?topic=463350.0). Its a simple idea that I have thought about but I cant implement it on my own because I am not a programmer. Maybe you could contribute ?

Cheers

What is a malled tx look like?  There are many ways that a tx can be mutated that makes identifying the "correct" one impossible.  Most nodes and pools already drop the duplicate the issue is the duplicate is getting to the pool before the original.  It wouldn't end up in a block otherwise.

If you have two tx each are equally valid and correct, how do you know which one was mutated after sending?   You can't so you do what you already do.  You keep the one you receive first and you drop the other one.  That means if the mutated tx gets to a miner's memory pool first, it will get included in a block.

You probably won't be able to so the only solution is to prevent it from happening to begin with.


The client waiting until change is confirmed isn't "ideal".  The ideal solution is to make tx ids immutable but that is a long term fix.  In the interim a user (possibly) having to wait for the change to be confirmed is far superior to transactions randomly breaking and non-technical users and merchants trying to figure out why it seems to just fail randomly.  The later is just going to kill adoption. 

I thought it was possible to determine if a tx looks like it was created by the standard client or not. Should this not be possible or there are too many different legitimate tx styles out there then I guess we will have to deal with malled txs.

So basically stop accepting 0-conf transactions for all purposes, even from trusted customers, until all wallet software has been updated to not spend unconfirmed change?  This seems like an extremely severe setback for bitcoin adoption and its utility in general.

https://bitcointalk.org/index.php?topic=463945  [RFC] Detecting Malled Transactions

my bitcoin-qt is virtually useless as it is including mauled transactions in its balance. blockchain wallet is fine though.

however, its been 22 confirmations since i sent a deposit to btc-e, i have no idea why it isnt added to my account yet

The issue isn't 0-conf transactions.  It is 0-confirm tx which use as their inputs the unconfirmed outputs of another transaction.

All Bitcoin clients ALREADY prevent the client from spending unconfirmed outputs for lots of very good reasons.   However since the wallet can "trusts itself" they wallet makes an exception for unconfirmed CHANGE.   Obviously no user is going to double spend themselves.   So the prior tx will eventually confirm and that means the change will eventually confirm as well.

Except if an attack mutates the original tx, then the original will never confirm, the duplicate will.  That means the change output is now invalid and the subsequent tx will never confirm.

Simple version:
This isn't about 0-conf tx.  This is about transactions using the as their input 0-conf outputs.

All that really needs to be done is for transactions to be reformatted to standard format and txids generated from that. Any other txid would be invalid. Surely?

That is a rather large "all" by itself as the input script is rather "loose".  That isn't all you need to do though.  ECDSA signatures are not immutable - Ouch. You also need to restrict signatures to a single "form" (DER) as OpenSSL (which Bitcoin uses) validates a variety of forms - double ouch.

To produce immutable hashes you need to:
a) Limit signatures to DER.  OpenSSL verifies non canonical forms of signatures.  Initially Bitcoin was no more restrictive than OpenSSL.  Since v0.8 Bitcoin, non-DER signatures are non standard and are not relayed by nodes running v0.8+.  This was MtGox problem their "Goxxed v0" custom client was creating non-DER signatures and thus the tx were being dropped by most nodes.

b) Make ECDSA Signatures immutable.  ECDSA signatures are not immutable, they were never designed to be and they never will be.  ECDSA will produce the same signature with both S and -S for a given payload and priv key.  So same tx data, same signature, different hash.  To resolve this "Bitcoin signatures" will need to be more restrictive than ECDSA signatures.  In other words all (future) valid Bitcoin signatures are valid ECDSA signatures, but not all valid ECDSA signatures will be valid Bitcoin signatures.

c) Allow only one form of input script for a given outcome.  The Bitcoin protocol is rather loose when it comes to op-codes in the input script.  It is possible to make some changes to these and still produce the same output (just like 3 + 2 = 3 + 2 +0).  Fixing this aspect will require tighter rules on what is a valid input script.


That is a lot to do, test, and get right.  Think of the "upgrading a plane in flight" analogy.

It can be done is phases to provide a safer path to the hard fork.
First the improved rules would be implemented in new version of clients (i.e. all clients would always use a +S instead of a + or -S) but clients wouldn't treat the "worse" tx any differently.
Next clients would favor "better" form of the transaction (i.e. if a node receives duplicates it will keep the one with the +S).
Next clients would consider the "worse" forms to be non-standard and would refuse to relay them (i.e. -S = non-standard, and tx is dropped by an upgraded node but still valid if in a block).
Finally clients would tx which break the new "better" rules to be invalid (i.e. after block # XXXXXXXXXX a tx with a -S is invalid, a block containing a tx with a -S is invalid).

It isn't going to happen overnight so in the interim mutable transaction ids are just a reality for Bitcoin.

Interesting. More involved than it sounded.

I am curious as to how the client knows in the first place if a transaction has propagated, thus allowing spending uncofirmed changed output? I mean your ISP can MITM you or all the nodes  connected can just drop it, if you put your tinfoil hat on.

Maybe the miners can be configured to respond to queries about if a transaction is in the mempool, but that opens them up to possible DDOS attacks.

It doesn't it will just keep rebroadcasting periodically.  If you are concerned about that scenario, ensure you have a high number of peers and use a vpn tunnel to get "past" your ISP.  No client does this but you could design a client so that it only broadcasts a tx randomly to some of its peers.  If the tx fully propagates the network the other half should inform you about it.  If they don't that would be a warning sign.  The node could also rotate peers to make isolation even more difficult.

For a commercial entity this can be taken a step further by putting a number of geo diverse listening nodes out that which communicate with your main node via an out of band channel.  We use a setup similar to that to troubleshoot customer reports of "transaction not showing up".  The listening nodes can also be used by 0-confirm merchants to look for things like double spend attempts.  If you imagine a 0-confirm merchant who has 8 listening nodes setup around the world each with an average of 2,000 peers connected, there may be some overlap put lets assume that gives the merchant 10,000 or so unique peers.  If any one of those 10,000 unique peers is relayed the double spend, then it would be relayed to one of the listening nodes who would alert the main node.

Nice idea. Is this deployed already? Open source by any chance?

And you can go even further.
- make your transaction confidence depend on the depth and width of the parent chain of unconfirmed transactions
- has any unconfirmed parent been malled
- has any unconfirmed parent been attempted double spent
- have sufficient feed been paid for unconfirmed parents
- do any unconfirmed parents have an nlocktime
- are any unconfirmed parents non-standard

These parameters are what the new Mycelium p2p trading feature uses to determine the 0-99% "transaction confidence".
In the end you can never be 100% certain, not even when a transaction has gotten its first confirmation, but you can use it as a tool and throw in  other circumstances like the value of the goods exchanged, your trust in the peer etc.

2014-02-13 219
Updating OP.

2014-02-14 54
Updating OP.

We haven't seen any large scale malleability attempts for the last few days, so I am going to stop tracking this for a while.
I am however certain that it will come back again until we fix malleability.

Thanks for your updates so far! :)

Until we fix? Developers done that 4 days ago, pull request merged into bitcoin:master
https://github.com/bitcoin/bitcoin/pull/3651 (https://github.com/bitcoin/bitcoin/pull/3651)

It's over. Now on to another "bug in the bitcoin software", whenever it may come :D

Over? Not exactly. The hole has been plugged but there's still a hole in the ship.

Which hole is still there, I don't follow you? If you think protocol should be changed to sign the TxID that will not happen for many reasons, they were explained earlier. This fix removes the possibility your new transactions being rejected because of malleability, so there's 0 chance regular users will be again effected by this issue. When and if will MtGox fix their own implementation is their own problem, they are rapidly becoming irrelevant.

ive heard this to often before

As long as transaction malleability is in the protocol the hole is still there - even though most exchanges will have plugged it.

It is not over until it has been released and enough miners have upgraded + 95% of the last 1000 blocks are version 3.
This will take some time.

Is there a page to track block version # as a % of the net as there was when we went to block version #2?

Will this change be in 0.8.7 and/or 0.9?

That patch doesn't fix malleability. There's still a bunch of things that allows us to alter txid en route. https://gist.github.com/sipa/8907691