[Cryptography] BitCoin bug reported

[Bear]

On Mon, 2014-02-10 at 08:03 -0500, Phillip Hallam-Baker wrote:
> The MtGox people are claiming that the reason they have been offline
> is a bug in the BitCoin protocol:
> 
> 
> https://www.mtgox.com/press_release_20140210.html
> 
> 
> Does anyone with deep knowledge of the protocol know if this is a
> credible explanation?

Summary:  The protocol is secure in terms of protecting against 
double payments actually taking effect, but someone is injecting 
bogus transactions (fiddled copies of real transactions) onto the
network. The clients in use at Gox are unable to distinguish bogus
copies from real, and other clients in use are still *SHOWING* the 
copies (which will never confirm) as "pending unconfirmed" payments
leading to confusion.  


Details:  Bitcoin transactions have an "ID number" derived from a 
hash of the transaction.  The problem is that the transaction may 
be expressed in any of several ways, resulting in different hashes. 
This problem is called transaction malleability, and work to 
eliminate it has been underway for months.

What is cryptographically secured about a transaction is which 
unspent coins are being spent, what public key they are being spent
to, the fact that the correct privkey (whose pubkey they were 
previously spent to) has signed off on the spend, etc.  This set
of information is globally unique.  But the "ID number" itself 
could be any of several values depending on details about how 
these things are expressed.  It has never been possible for more 
than one version of the same transaction to confirm; that is 
prevented as a double spend of the same inputs.  

The problem of issuing noncanonical forms of transactions was 
fixed months ago in the Bitcoin clients themselves - the standard 
tools now emit transactions in a "canonical form" that can only 
have a single hash/ID number.  But until quite recently the 
network still accepted transactions having other forms, and if 
multiple forms of the same transaction somehow got on the network
at the same time, it was essentially a cointoss as to which one 
would be accepted.  

And Mt.Gox, which had failed to update its own software when the 
rest of the network updated, was still occasionally emitting such 
noncanonical transactions.  Less than one-thousandth of Mt.Gox's 
payments were noncanonical, but they still existed.  Recently, 
after many warnings, the network reached a threshold and stopped
accepting noncanonical transactions in new blocks, which resulted 
in occasional payments made by Mt.Gox failing to confirm.  Gox 
was "confused" by its outdated software into thinking that it 
had made these payments, but because such payments were not 
accepted by the network, the coins were still at Gox.  Or, one of
the miners would be accepting their noncanonical transaction, 
transforming it into canonical form, and including it in a block, 
whereupon it would have a different ID number than the ID number
Gox was looking for a confirmation of.  

That was bad enough for Gox, but it was a relatively minor problem; 
Gox was reviewing these on a case-by-case basis, discovering that 
the transactions had in fact never been accepted by the network (or 
had been accepted with a different ID number), and issuing new
transactions or updating accounts with the corrected ID numbers.

Then someone started a DDoS attack on the Bitcoin network. There's 
some botnet now that's taking transactions off the network, fiddling
them into a noncanonical form, and re-emitting them onto the network.

The standard clients of course are refusing to accept these
transactions, and whenever a miner who has failed to update software
attempts to put one or more of them into a block that block is 
rejected.  But they're causing confusion and load, and the standard
clients are still seeing them as "pending" payments that haven't 
been accepted into a block yet.  For this reason, people are seeing
multiple copies of payments in their clients, with different ID 
numbers.  Only one copy of a payment will ever confirm, but for a 
while (until the payment confirms and the noncanonical version of 
it is then dropped as a double spend of the same coins) it looks 
as though multiple copies of payments have been sent.

Gox, which had relied on the "ID numbers" instead of more stable 
cryptographically secured identifying information about the
transactions, has been completely crippled by this attack.  

Some users, seeing "unconfirmed" payments in addition to the ones
they expected or made, are being confused into issuing more 
transactions to try to "correct" the multiple copies of payments.