Is my layman's understanding of transaction malleability correct?

[pythonscript]

I'm trying to build a rough, layman's understanding of how transaction malleability works (just for my own understanding; I'm not doing anything with it). This is the rough outline I have so far based on what I've read; is this correct?

1. In the simplest case, Alice wants to send bitcoins to Bob. This creates a transaction record that consists of a signature, which proves that Alice actually holds the bitcoins she's transferring to Bob, an ID (the txid?) for the previous transaction(s) in which Alice received these coins, Bob's address, and the amount.

2. The transaction record is broadcast to the entire miner network, who verify it, add it to a block, and attempt to "solve" that block.

3. In order for Bob to spend the bitcoins that he receives, he needs to refer to it in the blockchain (using the same type of ID that Alice used in step 1). This ID is created by hashing the pieces of the transaction record.

4. Transaction malleability comes into play because, as the wiki page states, the signature doesn't cover all of the data in a transaction that's hashed to create the transaction hash. Specifically, the signature doesn't cover itself, but the hash *does* include the signature. Therefore, it's possible to change either the format of the signature or the script used to make the signature in a way that won't invalidate the validity of the transaction, but that *will* change the hash.

5. Both transactions are submitted to miners and included in blocks, and whichever block is completed first, the transaction included in that block is considered to have 1 confirmation.

Here's where I'm a little unclear. Transaction malleability isn't a problem after a transaction has at least one confirmation, right? Once a transaction has at least one confirmation, any other identical transactions (identical except for the signature, that is) won't be verified by miners, I don't think. The issue arises if a bitcoin processor/exchange allows someone to spend coins they withdrew before waiting for at least one confirmation?

This means that it's not possible for both transactions to be in the blockchain, so people/organizations affected by this won't have to go through the blockchain to find people who double-withdrew, right?

I'm still getting a grasp on this, but any feedback is most welcome.

[Holliday]

Maybe this thread will help out?

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

[Maged]

Here's where I'm a little unclear. Transaction malleability isn't a problem after a transaction has at least one confirmation, right?

Practically, yes. Theoretically, if there is a reorganization of the block-chain (where a longer chain of blocks overtakes the chain that you currently believe to be correct), transaction malleability can still be a problem for some time after the first confirmation. This is, of course, the same situation with a standard double-spend, which is why it is always recommended to wait for 6 or more confirmations.

Once a transaction has at least one confirmation, any other identical transactions (identical except for the signature, that is) won't be verified by miners, I don't think.

Exactly. Miners will see these identical transactions in the exact same light as they see standard double-spends.

The issue arises if a bitcoin processor/exchange allows someone to spend coins they withdrew before waiting for at least one confirmation?

Depends on the "issue" you are referring to. You see, in the past week, the three major stories you've heard in the media (MtGox, SR 2.0, DDoS) were all unrelated.

For the MtGox issue:
The issue arises if a bitcoin processor/exchange is refunding what appears to be a failed withdrawal back to a user's account. If they look in the blockchain for the transaction ID that corresponds to the withdrawal transaction they issued, they won't find it because their transaction's hash was changed prior to entering the blockchain. This is fundamentally the wrong way to deal with this issue. Once you issue a transaction, you're supposed to always assume that the transaction WILL go through unless you double-spend at least one input to the transaction and wait for that new transaction to confirm. Under no circumstance should you just issue a completely new transaction like MtGox did. That is how they lost some bitcoins.

For the Bitcoin-Qt issue:
The issue arises if you are spending "change" from a transaction you just made that is still unconfirmed. If that original transaction gets mutated and confirmed with that mutation, the transaction that you made using change from the unmutated transaction can no longer go through.

For the Silk Road issue:
They just ran with the money and used the malleability issue as a cover. Don't think too much into their statements.

This means that it's not possible for both transactions to be in the blockchain, so people/organizations affected by this won't have to go through the blockchain to find people who double-withdrew, right?

Yes. Only one can ultimately exist in the blockchain.

[pythonscript]

I'm mostly clear on this, so I just want to make sure I'm 100%.

For the MtGox issue:
The issue arises if a bitcoin processor/exchange is refunding what appears to be a failed withdrawal back to a user's account. If they look in the blockchain for the transaction ID that corresponds to the withdrawal transaction they issued, they won't find it because their transaction's hash was changed prior to entering the blockchain. This is fundamentally the wrong way to deal with this issue. Once you issue a transaction, you're supposed to always assume that the transaction WILL go through unless you double-spend at least one input to the transaction and wait for that new transaction to confirm. Under no circumstance should you just issue a completely new transaction like MtGox did. That is how they lost some bitcoins.

Unlike the unspent change problem, this *did* allow Mt. Gox to lose Bitcoins because they simply issued a new transaction. Now, both the original transaction (or the mutated version of the original) AND the completely new transaction could be confirmed in the blockchain, thus giving the individual who started the withdrawal multiple times the amount of their original withdrawal, right?

Correct me if I'm wrong, but this also relates to whatever accounting practices Mt. Gox was using because they didn't realize that overall, the # of Bitcoin inputs into their wallets wasn't matching the outputs, and that apparently this had been happening over the last few years, right? (It also seems like they just generally had accounting or financial problems independent of this, seeing as they've now declared bankruptcy)

For the Bitcoin-Qt issue:
The issue arises if you are spending "change" from a transaction you just made that is still unconfirmed. If that original transaction gets mutated and confirmed with that mutation, the transaction that you made using change from the unmutated transaction can no longer go through.

I'm still a little unclear on what the problem is in this case. Say you spend change from a transaction that hasn't been confirmed yet. If the transaction is mutated, and that mutated transaction is confirmed, your original transaction won't go through. Is this just a problem because it allows a malicious user to DDOS part of the network (or part of the network) by submitting numerous duplicate transactions that won't cost them anything because the transactions still involve the same inputs and ouputs and only one will go through?

Basically, I'm confused as to how this is a double-spend problem because only one of the transactions will go through, so only that many Bitcoins will be sent/signed over. It's not possible for someone to use this to receive twice the number of Bitcoins that they have as unspent change, right?

For the Silk Road issue:
They just ran with the money and used the malleability issue as a cover. Don't think too much into their statements.

This was (and still is) my assumption, but has any evidence come to light supporting it? I haven't heard much about it since the initial report.

(I know Bitcoin isn't a system of address/wallet balances, and the thread that was linked to in the 2nd post of this thread was super helpful in clarifying that for me, so hopefully my terminology of "supply of outputs", for example, isn't too far off)

On a related note, the DDOS attacks that we've been hearing about are able to occur because malicious users can look at any transactions involving an exchange and create numerous mutated versions of those transactions, thus spamming the network. Is this correct?

[acoindr]

Unlike the unspent change problem, this *did* allow Mt. Gox to lose Bitcoins because when double withdrawals went through, Bitcoins were sent/signed over to the person making the withdrawal from the "overall supply of outputs" in Mt. Gox's wallets, which came from thousands of users, right? Correct me if I'm wrong, but this also relates to whatever accounting practices Mt. Gox was using because they didn't realize that overall, the # of Bitcoin inputs into their wallets wasn't matching the outputs, and that apparently this had been happening over the last few years, right? (It also seems like they just generally had accounting or financial problems independent of this, seeing as they've now declared bankruptcy)

The problem with MtGox wasn't exactly related to the core Bitcoin system. For example, if MtGox had a rogue employee helping an outsider to make duplicate fraudulent withdrawals by erasing prior evidence of them, then that's only an internal problem with MtGox.

Similarly, MtGox was checking to see if withdrawals their system sent were accepted by the Bitcoin network using the transaction ID. However, a documented and known problem is that the transaction ID can change (it's malleable) until there is confirmation of it (and the more the better). If an attacker was aware of malleable transaction IDs and MtGox wasn't, they could successfully trick MtGox into re-issuing new transactions, and get paid repeatedly, since the earlier transaction was valid, just with a changed ID (which MtGox was unaware of). Apparently MtGox had an automated system in place just for re-issuing transactions. They seemed to expect the need for that because they had prior problems from their custom software for making network transactions.

So there is no double-spend within core Bitcoin there. It's only MtGox internally being fooled into doubling (or more) someone's withdrawals.

For the Bitcoin-Qt issue:
The issue arises if you are spending "change" from a transaction you just made that is still unconfirmed. If that original transaction gets mutated and confirmed with that mutation, the transaction that you made using change from the unmutated transaction can no longer go through.

I'm still a little unclear on what the problem is in this case. Say you spend change from a transaction that hasn't been confirmed yet. If the transaction is mutated, and that mutated transaction is confirmed, your original transaction won't go through. Is this just a problem because it allows a malicious user to DDOS part of the network (or part of the network) by submitting numerous duplicate transactions that won't cost them anything because the transactions still involve the same inputs and ouputs and only one will go through?

Basically, I'm confused as to how this is a double-spend problem because only one of the transactions will go through, so only that many Bitcoins will be sent/signed over. It's not possible for someone to use this to receive twice the number of Bitcoins that they have as unspent change, right?

It's not a double-spend problem. It's not a double-spend problem for people that use confirmations, which has always been the way explained for using Bitcoin. With Bitcoin, since it's a trustless system, the only thing you can trust is confirmations. The more confirmations you have the better, but you need at least one to make any real world decision involving more than say a couple dollars of value.

The spent change issue isn't a problem either, again, for people that wait for confirmations. It would only be a problem if many network users simply disregarded confirmations, because they could believe they had been paid money which would eventually vanish when it was finally confirmed.

On a related note, the DDOS attacks that we've been hearing about are able to occur because malicious users can look at any transactions involving an exchange and create numerous mutated versions of those transactions, thus spamming the network. Is this correct?

Yes. It doesn't block or change the transaction in any way except for the txn ID. So any exchange or service relying on txn ID, especially if unwisely doing so before confirmation (as MtGox apparently was) would have their system affected. However, as long as they didn't make any financial decisions based on that it would result in nothing more than the irritation of addressing internal records and customer service.

[Skybuck]

"So there is no double-spend within core Bitcoin there. It's only MtGox internally being fooled into doubling (or more) someone's withdrawals."

I don't agree with this statement. Mt Gox, if story is true, became victim of this problem in bitcoin.

It is bitcoin itself which allows this mallebility to occur. Issueing warnings that this can occur is not enough.

Not being able to find one's one transaction id is also a serious problem.

Furthermore this attack seems to be a man in the middle attack which is a very difficult attack to protect against.

Correct conclusions are therefore:

1. Bitcoin is vunerable to man in the middle attacks and "fooling users of bitcoin".

2. Others can become victim of this type of attack.

Furthermore:

3. It may be difficult to fix this problem, 2 years have passed and no fix ? Could be an indication that this is very difficult to protect against maybe even impossible. Therefore Mt Gox's prediction that this could be the end of bitcoin is not to be taken lightly

[un_ordinateur]

"So there is no double-spend within core Bitcoin there. It's only MtGox internally being fooled into doubling (or more) someone's withdrawals."

I don't agree with this statement. Mt Gox, if story is true, became victim of this problem in bitcoin.

It is bitcoin itself which allows this mallebility to occur. Issueing warnings that this can occur is not enough.

Not being able to find one's one transaction id is also a serious problem.

Furthermore this attack seems to be a man in the middle attack which is a very difficult attack to protect against.

Correct conclusions are therefore:

1. Bitcoin is vunerable to man in the middle attacks and "fooling users of bitcoin".

2. Others can become victim of this type of attack.

Furthermore:

3. It may be difficult to fix this problem, 2 years have passed and no fix ? Could be an indication that this is very difficult to protect against maybe even impossible. Therefore Mt Gox's prediction that this could be the end of bitcoin is not to be taken lightly

I dissagree entirely for 2 reasons.

1. You say that "It is bitcoin itself which allows this mallebility to occur. Issueing warnings that this can occur is not enough.". Many modern cars, planes, etc... have an "autopilot" function. Despite the name, nobody expects that the autopilot will drive the vehicle all by itself. The autopilot will only maintain speed and/or direction, depending on the vehicle.

Names can be misleading. Of course, it is undesirable, as names should always reflect the most precisely what is referenced, but still, sometimes, for historical reasons, "bad" names stick, and there's nothing we can do about it. What we CAN do is educate ourselves before operating with anything dangerous.

In the case of Bitcoin, the malleability "bug" does not cause any problem for the layman. The DDOS attack with mutated transactions may cause some transactions to fails, and that is an inconvenience indeed, but the user may not be tricked into sending money twice. (Anyway, DDOS are a pain in the ass, and are very difficult to deal with, in bitcoin or in http or in anything web related)

The malleability bug is more of a problem to software developpers. And as I expect that my airplane pilot has taken some classes to fly a plane, I'd expect that somebody programming a Bitcoin app that's going to handle hundreds of BTC per day has understood the protocol rules.

Txid might was a "bad" name as it may seem that it is unmutable. But anybody who has seen how this ID is calculated must understand that it cannot be unmutable. And anybody that develops a program that's going to issue transactions must have read these specs, for if he had not, he would not know how to code it.

2. The "bug" was known for a long time, yet nobody pushed for a solution because correctig it would be difficult (as it would require a change in all existing software), and furthermore, BECAUSE THERE ALREADY EXISTS A WAY TO UNIQUELY TRACK TRANSACTIONS.

When I issue a transaction, I spend some output of prior transactions. All I have to check is whether those outputs were spent. Then I'll know that the transaction was confirmed, even if it is the mutated transaction that got accepted.

[Test User]

3. It may be difficult to fix this problem, 2 years have passed and no fix ? Could be an indication that this is very difficult to protect against maybe even impossible. Therefore Mt Gox's prediction that this could be the end of bitcoin is not to be taken lightly

This is not a difficult problem to fix. Instead, it is one that doesn't need fixing. However, there Mt Gox and blockchain.info did develop a workaround for users that want a non-malleable ID.

The transaction hash was used by Mt Gox as a way of tracking transactions. This is calculated from the transaction inputs/outputs and signature. However, it is just as easy to track the transaction inputs in the blockchain. In fact, as the blockchain contains the transaction inputs directly, and the transaction hash must be calculated, it is actually easier to verify the transaction inputs than the hash.

The flaw in bitcoin is that the transaction hash has become known as the "transaction ID", when perhaps it would have been better termed the "transaction hint" or "transaction hash".

Mt Gox in their final days did develop an alternative ID - they called this NTX ID, and at their request blockchain.info implemented it for searches. This is just the hash of the transaction inputs/outputs, which can't be manipulated. For users who are only tracking IDs, not the transactions, then this is a usable option, and it does provide a simple to use reference for support purposes.

[un_ordinateur]

For the Bitcoin-Qt issue:
The issue arises if you are spending "change" from a transaction you just made that is still unconfirmed. If that original transaction gets mutated and confirmed with that mutation, the transaction that you made using change from the unmutated transaction can no longer go through.

I'm still a little unclear on what the problem is in this case. Say you spend change from a transaction that hasn't been confirmed yet. If the transaction is mutated, and that mutated transaction is confirmed, your original transaction won't go through. Is this just a problem because it allows a malicious user to DDOS part of the network (or part of the network) by submitting numerous duplicate transactions that won't cost them anything because the transactions still involve the same inputs and ouputs and only one will go through?

Basically, I'm confused as to how this is a double-spend problem because only one of the transactions will go through, so only that many Bitcoins will be sent/signed over. It's not possible for someone to use this to receive twice the number of Bitcoins that they have as unspent change, right?

As you point out, it does not enable any double spend per say. However, it may cause transactions the user expected to pass to fail randomly, which is an inconvenience.

Furthermore, once a transaction message was broadcast to enough miners, for small transactions, many merchants let the client go. Even if it does not have the same "trust" as a confirmed transaction, as long as you expect most client to be honest, you may be willing to accept to take that risk. Furthermore, once the transaction is broadcast to enough miners, even if a dishonest client tried do broadcast a double-spend of the first transactions, most miners will only include the first transaction they recieved, so the merchant gets his money

This in most of the cases. If the transaction is made with a confirmed output, then even if the mutated version passes, the merchant gets the money and everybody is happy. However, if the transaction is derived from an unconfirmed output, THEN, it's a problem, because if the first transaction mutates, then the second will fail.

The second case can happen with all clients, even if they are honest. Now the merchant cannot take the chance that the client is honest because it can happen anytime. So merchants should NEVER accept unconfirmed transactions derived from unconfirmed output, even under the assumption of trusted client.

However, not that there has been absolutely NO report of this happening in reality. This is a theorical possibility, which can help us take appropriate measures to act safely with Bitcoin.

[acoindr]

"So there is no double-spend within core Bitcoin there. It's only MtGox internally being fooled into doubling (or more) someone's withdrawals."

I don't agree with this statement. Mt Gox, if story is true, became victim of this problem in bitcoin.

When I used the term double-spend I meant use the same money to pay twice. That's not what happened here.

MtGox sent out new transactions because they were fooled into thinking their own transactions had not been accepted. No technical person worth their salt thinks to their self, when something doesn't work, oh well push the button again and see if it works this time! That isn't how it works. The very first time someone told MtGox they didn't receive a transaction their system sent out MtGox should have investigated and corrected the problem, and halted all withdrawals if need be until resolution.

Put transaction malleability aside for a second. Apparently MtGox's horrible software was sending out invalid transactions on it's own, which is why they then automated re-issuing new transactions. Imagine someone fooling around told them they didn't receive a transaction 100 times in a row. Would MtGox re-issue 100 new transactions, hoping one would stick? How does that make one iota of sense?

It is bitcoin itself which allows this mallebility to occur. Issueing warnings that this can occur is not enough.

People that use Bitcoin correctly understand unconfirmed information can change, at least most people seem to understand this.

Not being able to find one's one transaction id is also a serious problem.

I don't think so. Remember, once confirmed the transaction ID will not change (without a re-org) so you only have to check for two possible cases, the ID you're expecting, or an alternate ID which gets confirmed. How is that a serious problem?

[Sindelar1938]

Google for Igor Andreev's blog
Had the most intuitive explanation of tx malleability I have seen