Ok, got the answers now. So there are two sources of malleability; the signature itself and the scriptSig (there's a scriptSig per input). The scriptSig is not (and cannot be) part of the signature, so you can come up with all kinds of malleability issues here. Therefore, my arguments above are applicable to scriptSig, but it is very important that you can prove you have the "smallest" scriptSig because otherwise an attacker would be able to exploit that. I talked to gmaxwell and (2)-(4) are already deployed since a while back. (5) is checked in but not shipped. So (1) and (6) remain. They are slowly closing the malleability gaps, but it will take some time. Meanwhile, if you're a wallet provider, you should just ensure that malleability is a possibility and write code that is robust enough, i.e. look at the outputs to see if a transaction got through; never use the transaction hash for tracking. 7-8 are not big issues, because they are under the original tx broadcaster's control.

Correct. I found a summary here:

https://gist.github.com/sipa/8907691

If I understand this correctly, (1)-(2) in this list should prevent evil* malleability. (It's only interesting to protect the signature itself, as all the other stuff cannot be modified as that would invalidate the signature.) Can someone confirm this?

*evil = eavesdropping and then modify transaction by someone who does not have access to private key

True, and I know what's wrong with my solution (after some discussion on #bitcoin-dev): The final signature by itself is malleable, because for every ECDSA signature (r,s), the signature (r, -s (mod N)) is also a valid signature (of the same message.)

And since you can put a "random" number as a signature, it would be impossible to prove that you'll get the "smallest number" (who knows what kind of mathematical tricks you can pull.)

It's that final signature causing grief and I think it would be very difficult to fix that.

But does this stop malleable transactions? Even if the transaction size is the same you can create malleable transactions by shuffling inputs/outputs around, right?

However, I had an idea last night and just still grabs my head and I need to get this falsified, because it is stupidly simple so I must likely be wrong. So help me out proving this wrong.

First, let's define a total order on all transactions,

Tx(A) < Tx(B)     if     SerializedByteSeq(Tx(A)) < SerializedByteSeq(Tx(B))

Where '<' operator in SerializedByteSeq(X) < SerializedByteSeq(Y) is the lexicographically byte string comparison.
Furthermore, there's always smallest element in this total order. I'm not sure what the smallest possible transaction looks like, but there's definitely one. Note that if two transactions are of equal size (in bytes) we still apply the lexicographic rule ('AA' < 'AB').

Because we have a total order, any subset of Tx(A) < Tx(B) is also a total order.

Now let's consider all possible transactions for a given set of inputs + outputs.
Fixing the inputs and outputs will give us a subset of Tx(A) < Tx(B).
And there must be a smallest possible such transaction (again using the lexicographically definition).

Now for each Bitcoin node in the network, we'll from now on apply this for unconfirmed transactions:

* If we receive a transaction Tx(A) with inputs+outputs IO(Tx(A)) = <{Inputs},{Outputs}>, then if we haven't seen that transaction before then add it to our pool of unconfirmed transactions.
* If we receive a transaction Tx(A) with inputs+outputs IO(Tx(A)) = <{Inputs},{Outputs}> AND we have an existing IO(Tx(B)) = <{Inputs},{Outputs}> (same inputs and outputs) AND Tx(A) < Tx(B), then replace existing Tx(B) with Tx(A). Otherwise we just drop Tx(A).

The only thing an original broadcaster of a transaction needs to do is to pick the smallest (w.r.t. to total order) transaction and it will be impossible for an attacker to create a malleable transaction.

The pros with this solution is:

* It doesn't require any data structure changes
* Nodes can smoothly update to the new version (using the above rules) to gradually block malleable transactions and DoS attempts.
* It's 100% backwards compatible what we have today. I'm not saying that a Tx(B) in Tx(A) < Tx(B) is an invalid transaction, just that Tx(B) has less precedence.

So how hard is it to pick the smallest lexicographically transaction for an original Tx broadcaster?
It shouldn't be that hard. Everything reminds me of how you sign a set of strings in X.509 ceritificates that use ASN.1 DER encoding.
What you normally do (to ensure a unique hash) is to lexicographically sort the strings first. If you look at all the sub-sequences of data in a Tx string, it shouldn't be that hard to prove the best order (at least not for simple transactions).

As this is way too simple, now shoot me in the head and prove me wrong

In Bitcoin <0.8 The ECDSA signature was allowed to be padded with leading zeros, but in Bitcoin 0.8+ it is no longer allowed. MtGox sometimes issued transactions with leading zeros, and those transactions got stuck (because they were refused by the majority who are running Bitcoin 0.8+). However, MtGox published their failed transactions through an accessible API (https://data.mtgox.com/api/0/bitcoin_tx.php, the signatures are now redacted). Therefore, you could apply withdrawals on purpose until you got a ECDSA signature with leading zeros. Then you take that transaction and remove the leading zeros and rebroadcast the (modified) transaction. This would now be accepted by the network but with a different transaction hash. MtGox however thinks that the transaction never gets through because it is listening for its own transaction hash. Finally MtGox gives up, cancels the transaction, and returns the funds to the customer. Rinse, lather and repeat. In theory you can empty MtGox BTC vault, but they were quick enough to see what was going on and cancelled BTC withdrawals. Now they have to fix their client to listen for malleable transactions.

This malleability thing can be handled and I'm sure Bitstamp will fix it (a lot faster than MtGox).

The problem, I suspect, is how change is being handled. As outputs need to be fully spent, you normally produce a transaction with 2 outputs; the desired target address and an address with change that goes back to the exchange itself. However, that change needs to be frozen until the transaction becomes confirmed. Most exchanges probably thought that since it owns the private keys it should be safe to instantly reuse the transaction hash of the change for some other withdrawal, but due to malleability it is not possible to do so.

To get good throughput the coins at an exchange probably needs to be split up in reasonable chunks. It all reminds me of how you implement malloc() in C with free lists for each bucket size. Instead of using a stack (for each free list) you should probably use a round robin strategy.

Anyone being an expert in Bitcoin programming who wants to chime in here?

This is standard procedure by MtGox. If a transaction gets stuck and doesn't get processed MtGox will refund you. Has happened to me 2 times personally.

UPDATE 2:

Given the current turmoil I felt I needed to write something more. MtGox is being bashed, and rightly so, but there's one thing that nobody has been talking about. If this issue has been known since 2011, why does suddenly all this happen to MtGox _now_? Isn't that a legitimate question to ask? Because, that will reveal something else that MtGox hasn't mentioned in their press release (blaming the Bitcoin protocol).

So here comes the answer:

1) The Bitcoin core dev team has been addressing this malleability by gradually tightening what counts as a valid signature. For example, this is one of those changes: https://github.com/bitcoin/bitcoin/commit/58bc86e37fda1aec270bccb3df6c20fbd2a6591c
(look at IsCanonicalSignature())

2) MtGox hasn't bothered to keep themselves up to date with the latest Bitcoin client software, so suddenly some transactions will get stuck because they are not complying with these harsher rules in Bitcoin 0.8+.

3) MtGox publishes all failed transactions (used to be with the raw transaction data; now redacted) at
https://data.mtgox.com/api/0/bitcoin_tx.php

4) Someone looking at this tx list will spot some of the failed transactions and modify them so they become bitcoin-0.8+ compliant. This gives a new tx and the transactions get through. MtGox fails to spot its own tx in the blockchain; gives up and returns funds to the customer.

It is correct that MtGox is right that you can never be 100% sure for malleability because the hacker can listen to the Bitcoin network and forward modified tx directly to miners (and out compete MtGox), and although this window has been open since 2011, this is a much harder problem with race conditions. It is because of the steps 1-4 above that made it much easier to apply a malleability attack on MtGox.

MtGox is now claiming that it has to wait until the malleability problem is fixed by the Bitcoin core dev _before_ it will allow BTC withdrawals. That's how I interpret their statement in their press release:

"We have discussed this solution with the Bitcoin core developers and will allow Bitcoin withdrawals again once it has been approved and standardized. "

But this is utterly absurd. It's most likely never going to happen, or it will take a very long time. And this is a very strange statement because it isn't that hard for MtGox to fix this problem. To check whether a transaction has got through or not is not using the transaction id, but instead compute a hash of:

inputs (lexicographically sorted) + outputs (lexicographically sorted)

This will uniquely identify a transaction regardless of the transaction id and it is fast to compute.

So what are they waiting for?

UPDATE:

So MtGox has finally gone public with this information which is good, but I need to say a few words because people are totally panicking on all exchanges.

First, MtGox is exaggerating the problem. It is not as bad as it seems really. This exploit, of modifying transactions but keeping the signatures intact, is quite difficult to begin with. MtGox made it worse by publishing their transactions through an accessible API (but now the signatures have been redacted).

The worst thing that can happen is that the exchange may get stuck with transactions and what all the exchanges need to do is not automatically return the user's balance without doing some investigations first. For example, if some of the inputs (of the transaction) have already been spent, then further investigations are required. That is all.

You cannot steal someones else's coins, and there's nothing wrong with the bitcoin protocol per se.

What the Bitcoin core development team is trying to do, long-term, is to ensure that the byte encoding is unique for a given transaction. If you look at ASN.1 DER encodings, the whole point is to ensure that there's only one way to encode something so there's no ambiguity when to compute digital signatures. Otherwise we have this problem of two chunks of data that are equivalent but syntactically different.

Anyway, all this is just unnecessary panic. And if you have access to fiat I would consider this as an enormous buying opportunity.

You may be right as I cannot be sure how other exchanges work, but I do know MtGox has a problem with "double refunding." This is the reason why they halted all BTC withdrawals. They are currently going through all the transactions to check which ones did go through.

nullc has access to the same facts as me. His post is more into the actual technical details of the exploit. The intention of my post is to bring this topic to higher level because the concept itself is a real problem that exchanges should be aware of.

You don't touch the actual signature, but there are meta-data around it. In a recent version of the official bitcoin client the format of that meta-data has been tightened so the transaction data provided by MtGox is now being rejected by the latest official version. A hacker can then take the rejected raw txdata provided from MtGox, patch it and rebroadcast it. It will get through, but MtGox still thinks it is invalid and returns balance.

I don't have any information on that. Even if that's true this particular issue is unrelated to that.

It's not impossible of course, but I believe that the hacker attacks have caused limited damage. The main reason is that MtGox only allows 100 BTC withdrawals per day. Each unsuccessful withdrawal takes a week (before the balance is returned). This started two weeks ago and MtGox got warned early enough and took countermeasures before everything got out of control. This is the reason why they frozen all BTC withdrawals. I believe they'll be able to clean up everything, but it will take some time. It's certainly a very interesting situation. There are multiple different problems that magnifies the situation. Again, other exchanges could suffer from the same problem. As far as I understand, all the exchanges are currently being contacted and warned about the current situation.

I'm pretty sure that this is the case. Once they resolved all the transactions everything will return to normal. However, I fully understand people who lost faith in MtGox; it's a very natural reaction.
 

Thanks for your support. Unfortunately, I cannot reveal my sources.

Currently, there's too much Fear Uncertainty and Doubt.

TL;DR version:

1) The withdrawal problems at MtGox are technical.
2) It is likely that a hacker exploit has taken place.
3) Any damage is likely to be limited.
4) Other exchanges need a heads up and could also be vulnerable.
5) MtGox is going through all erroneous transactions and will update all balances. This is the reason why BTC withdrawals are frozen.
6) Countermeasures need to be taken (for all exchanges)

BTC Withdrawal Problems
------------------------
A couple of weeks ago (around January 26-28) I noticed that things at MtGox were not the way it supposed to be. Normally, withdrawing BTC is an instant process. This time my withdrawals went stuck. MtGox provides an API so that transactions that didn't get through were available for public scrutiny: https://data.mtgox.com/api/0/bitcoin_tx.php.
I took my stuck transactions which were available in raw format and try to rebroadcast them manually. (MtGox no longer publishes the raw format; they are now redacted for a very good reason.) To my surprise it complained that some of the transaction inputs were already spent. Furthermore, this happened to many of my friends as well. I investigated their transactions as well and tried to rebroadcast them manually, but without luck due to complaints of double spending.
My immediate (now wrong) conclusion was that MtGox F-d up big time and couldn't handle a simple concurrency problem. If several people are withdrawing BTC at the same time it is important to ensure that this is counted as an atomic operation so that coins from the wallet pool are not double spent. It turns out that it was much more interesting than I've first anticipated. Another (wrong) conspiracy theory of mine that MtGox did this intentionally to cover up the fact that they were running low on BTC as they use "fractional reserve bitcoin".

Exchanges and Custom Wallet Software
--------------------------------------
Most exchanges have completely custom bitcoin software. Either they are heavily modified source code of the official client, or everything is written from scratch. To my best knowledge MtGox has written their client completely from scratch. Some people critize them for that, but the standard client is not scalable to an exchange with a million of customers. You must modify the original source so at least the wallet part is going through a more suitable database, and also the built-in security only works for a single customer.
The cons with writing your own custom bitcoin client are of course that you would from time to time become out of sync with the official client. It turns out that this is very problematic.

Erroneous Transactions and Fatal Consequences
----------------------------------------------
Suppose there's something that is inconsistent with MtGox client software with the rest of the bitcoin network. What would be the outcome of that? MtGox would broadcast the transaction to the bitcoin network and miners would reject it, so the transaction becomes stuck. After a couple of days, MtGox gives up because it can't get the transaction published in the blockchain so it returns the balance to the customer. This turns out to be VERY dangerous. BTC should not be returned to a customer without proper investigation.
You may ask why?  A hacker can exploit the erroneous transactions broadcasted by MtGox by modifying them manually (so they become consistent with the official bitcoin software) and then rebroadcast them manually her/him-self. If this happens, then the stuck transaction (at MtGox) gets actually through and at the same time the balance is returned to the customer's account. Therefore, the customer has doubled her/his BTC withdrawal attempt. If you repeat this process a couple of times then you can empty MtGox BTC vault without having to hack into their computers.
So what about all those erroneous transactions with "double spending", surely this has nothing to do with the erroneous transactions mentioned recently? At the time the hacker broadcasts the modified (correct) transaction based on MtGox erroneous one, the transaction gets through, but MtGox still thinks the coins are still unspent. After all, it is only MtGox that has the private keys, so it is impossible (in general) that someone else can spend them. Therefore, MtGox still thinks those coins are unspent and trying to reuse them as fresh coins for other transactions. This explains why we had so many transactions that tried to double spend coins.

What is MtGox Doing Now?
-------------------------
First, the hackers that tried to modify the erroneous transactions and rebroadcast them manually are likely identified (MtGox surely knows the name of every customer). Their accounts will likely to be frozen.
Second, MtGox has an accounting mess to clean up. There are many transactions registered as unsuccessful at MtGox that need to be checked whether they actually went through or not. Then MtGox needs to update all the BTC balances. This will likely take a couple of days and this is the main reason why all BTC withdrawals are blocked at this time. Once this is done MtGox will open for BTC withdrawals again.

Lessons Learned and Countermeasures
-------------------------------------
What happened at MtGox can happen at other exchanges as well.  So how do we prevent these disasters from happening again in future?  I have some proposals,
1) Try to stay close to the official bitcoin client and merge in new changes as soon as possible. Stay updated.
2) Bitcoin Foundation could setup some public servers that always run the latest official version of the bitcoin client. Exchanges should then be able to verify that the transaction is legitimate to the latest bitcoin client before broadcasting them.
3) At an exchange, when a transaction becomes stuck for whatever reason, always check if some other transaction with the same inputs and outputs has already been accepted by the network before returning the customers' balance.

I'm guessing that you see that there are many sources to your transaction? There's nothing wrong with this.
When you want to transfer BTC from one address to another and the output doesn't match the exact amount you want to transfer, you'll always have a transaction with two outputs. One output which contains the desired sum and the other output is the change. MtGox typically creates a new address for every change, so it means that there will be plenty of addresses which contains change. When another person makes a withdrawal I assume that MtGox wants to get rid of all "change" addresses (that contains small amounts) first which is the reason why you see so many sources.

https://www.youtube.com/watch?v=4_yzUvkML3o

Bing Gordyn coin to the MOON!

This is INSANE!

Look at https://data.mtgox.com/api/0/bitcoin_tx.php

I found my stuck transaction in there:

b2ab0930acbc18e9ba4d5415025ed6022ad8b0c657b4ec51edbf5caa628c5295

which decoded looks like this:

"hash": "b2ab0930acbc18e9ba4d5415025ed6022ad8b0c657b4ec51edbf5caa628c5295",
            "tx_p": {
                "hash": "b2ab0930acbc18e9ba4d5415025ed6022ad8b0c657b4ec51edbf5caa628c5295",
                "ver": 1,
                "size": 257,
                "in": [
                    {
                        "prev_out": {
                            "hash": "2a9085d5476aa3965e498af7245d9271d632ce01f159a6d5f445b91404927070",
                            "n": 0
                        },
                        "scriptSig": "(redacted)",
                        "addr": null
                    }
                ],
                "out": [
                    {
                        "value_int": 200000000,
                        "value": 2,
                        "scriptPubKey": "OP_DUP OP_HASH160 fbee2a88bccf3cffa026d3cc7f10da6526293262 OP_EQUALVERIFY OP_CHECKSIG",
                        "addr": "fbee2a88bccf3cffa026d3cc7f10da6526293262"
                    },
                    {
                        "value_int": 587623433,
                        "value": 5.87623433,
                        "scriptPubKey": "OP_DUP OP_HASH160 90433401824d03160d00b4e5f3a5f1a133c46e50 OP_EQUALVERIFY OP_CHECKSIG",
                        "addr": "90433401824d03160d00b4e5f3a5f1a133c46e50"
                    }
                ]
            }

The only input to my transaction is:

2a9085d5476aa3965e498af7245d9271d632ce01f159a6d5f445b91404927070 (and it wants to use output 0 of that transaction)

Looking up this on blockchain it shows a current balance of: 7.87723433 BTC
And 2 + 5.876 is pretty close to that balance but not quite (any difference is going to be miner's fee)

However, there are 6 other transactions also claiming from the same output!

So currently, I have 1/6 chance of getting this output. WHY is MtGox doing this? The Bitcoin protocol clearly says that you have to consume the whole output and now there are 6 transactions claiming the same output!

Argh!