Wouldn't the "malleable transaction" attack be foiled by common sense?

Question

I'm trying to understand the malleable transaction attack, as it seems to me that only a rather careless operator would be vulnerable in the first place, as described below.

---

Mainly to clarify my own thoughts, let me describe the attack as I understand it. Dramatis personae: Alice is the attacker, and Bob is a "banker" (exchange operator, web wallet; someone who is holding coins on account for Alice.)

Alice: Hi Bob, I have 1 BTC in my account and I'd like to withdraw it. Please send it to address 1Alice1.

Bob: Okay, I've generated a transaction, its hash is 123abc. I've just posted it to the p2p network. It spends output 3 of prior transaction 987def and sends 1 BTC to 1Alice1. Your account has been debited for 1 BTC and your new balance is 0.

Alice: Thanks, I see the transaction. I'll wait for it to be confirmed.

Now Alice constructs a "mutant" transaction, with the same effect as 123abc; it still spends output 3 of 987def and sends 1 BTC to 1Alice1, and the signature still verifies, but the mutant has a different hash 456bca. Somehow, Alice gets 456bca into the blockchain instead of 123abc. Maybe she's just better connected on the p2p network than Bob is, or maybe she bribes Polly, a mining pool operator, to give priority to 456bca. Since 123abc conflicts with 456bca, 123abc will never be confirmed.

Some time passes.

Alice: Hey Bob, remember that 1 BTC I was supposed to get? The transaction never confirmed.

Bob: Let me check. Yes, I see, there's no such transaction as 123abc in the blockchain. Well, I guess you never got your coins; sorry about that. I'll recredit your account; your new balance is 1 BTC.

Alice: Thanks. Now that I have 1 BTC back in my account, I'd like to try again to withdraw it. Send it to 1Alice2.

Bob: Okay, I've generated a transaction, its hash is 246fed. I've just posted it to the p2p network. It spends output 7 of prior transaction 369dbc. Your account has been debited and has balance 0 again.

Transaction 246fed is confirmed normally.

Alice: Gotcha, Bob! Your original transaction went through after all, just in mutant form as 456bca. Now I have both it and the new transaction, and I've just stolen 1 BTC from you. Mwa ha ha!

Bob: Oh, woe is me!

---

However, it seems to be that this attack requires some rather careless bookkeeping on Bob's part. Even if Bob has no idea there is such a thing as a malleable transaction, he knows he generated 123abc and put it on the network, and for all he knows it is still floating around out there. So I would think that before recrediting Alice's account, common sense should dictate that Bob ensure that 123abc cannot be confirmed at some future date, perhaps by making a new transaction (963dad) that spends the same input (trans 987def output 3) to one of his own addresses (1Bob1), and waiting for 963dad to confirm. Of course, in the current scenario, 963dad never will confirm (because 456bca supersedes it), and Bob will eventually get tired of waiting and investigate further.

Or, alternatively, when Alice asks to withdraw 1 BTC for the second time, Bob's new transaction (678bbb) to Alice should again spend the same input (987def:3), ensuring that Alice can't somehow get 123abc confirmed later. This foils the attack also, because 678bbb has been invalidated by 456bca.

Furthermore, since Alice's mutant transaction 456bca did in fact spend Bob's input (987def:3), shouldn't Bob's client software inform him that this input is no longer available to him, and adjust his balance accordingly? Bob apparently believes 123abc failed and so he still controls that input, and therefore this should throw his books out of balance and alert him that something is wrong.

My understanding is that the Bobs of the world have responded to the issue by complaining that "malleable transactions" are an obscure protocol bug that they couldn't have been expected to anticipate. Whether that's true or not, it seems to me that in order to have been vulnerable, Bob's accounting practices already had to be negligent, so he really has no defense either way.

Or, if Bob saw the red flags but failed to understand the situation, and credited Alice's account anyway in the interests of customer service, it's still hard to feel much sympathy for him.

Is this account essentially accurate, or have I missed some crucial details?

Thanks, and sorry for the length.

Answer 1

Whilst most of the process you describe is accurate, there are a few details where I believe your assumptions do not match reality, and may hence lead you to be (slightly) more critical of Bob than indeed deserved:

1. The fact that tx 123abc is known to the network does not necessarily mean Bob, even if unaware of 456bca, would have to fear 123abc could be respent. Somehow, his transactions have, after all, continued, which for a high transaction volume like a centralized wallet will typically mean that the unspent transaction 987def entering 123abc has meanwhile been otherwise spent (and confirmed). Bob can tell this even without investigating what transaction took the place of 123abc by just seeing any later transactions confirm. But of course the action one would hope Bob to take, investigating what tx replaced 123abc (rather than albeit also naturally assuming only other valid tx could have been generated by his hot wallet software), should have prevented the fraud.

2. What with other reasons potentially preventing a transaction to go through----maybe you didn't include enough fees or were forming a transaction that peers otherwise didn't like enough to propagate or miners to include---it isn't unreasonable to have a hot wallet automatically resort to resynchronizing to what did get included in the blockchain, essentially double-spending the prior tx 987def such that at least other customers can be handled. Of course, proper handling would then internally flag this occurance, for manual handling of the failed transaction, which in this exploit by Alice would be absent and in an ideal process wold alert Bob that something was amiss.

3. In distributed systems, a common global state does not always exist. What must seem natural if there was, say, a one hour break in hot wallet operation, comparing actual Bitcoin balance and own acounting, isn't quite as trivial as that when the system is continually in the state of having many as yet unconfirmed transactions. That should not be an excuse because a well-designed audit and account reconciliation process should be able to deal with that, but, again, it is conceivable that a previously working less elaborate process can't deal with the issue of lots of not confirming transactions.

I agree that in retrospect, Bob handled the situation rather poorly and not with the kind of diligence you would hope for from someone entrusted with others' bitcoins. But it is really hard to draw up processes, especially in a multi-people 24/7 operation, to deal with what a misconception makes you think of as utterly impossible. Bob may indeed have been operating with some kind of work-around process to deal with his hot wallet implementation not giving adequate logging of normally not propagating transactions.

Answer 2

In essence, you've replicated the argument that nobody needs to worry about this problem, which we now know is false. It's because of that very belief that we have the mess we have now.

One crucial detail you missed is that when spending the outputs of a prior transaction, you must specify its transaction ID in your new transaction. So there are many other possible failure scenarios.

For example, say you form only transactions that spend your own outputs, so you might assume that your transactions will definitely succeed eventually and thus you can chain transactions without waiting for confirmations. Until recently, this was considered the correct way to generate high volumes of transactions.

But we now understand that you can't because the chain can break entirely if any transaction in the chain has its ID changed. The next transaction that refers to any of those outputs will never confirm since it will have the wrong transaction ID specified in one of its inputs. Later transactions that spend from that transaction will also fail and you'll have an unholy mess.

Answer 3

I was originally going to phrase this as a comment but I'm confident enough to risk the downvotes with an answer:

What Bob should have done was spend the original inputs again (possibly by simply re-broadcasting his original txn). If the alternative txn was already in the blockchain the new txn would be correctly rejected as a double-spend, alerting Bob that the coins had in fact changed hands.

Looking forward to learning how my simple explanation is incorrect :)

Answer 4

Check out this video supposedly demonstrating a malleability hack on mtgox:

https://www.youtube.com/watch?v=WfKy3DEiOwY

Looks like gox automatically recredited his account after the failed transaction - which would explain both the fiat discrepancy ( sell your hacked coins for fiat) and the coin discrepancy.

Now the real question is:

How did those idiots at Gox not notice?