7 ms·

Not a protocol fault: MtGox and transaction malleability

146 points by oleganza 13y ago

adv0r 13y ago
I want to donate all the money I got to this guy
Kenji 13y ago
"MtGox remembers a hash of that transaction (unique fingerprint of its contents)" Technically, there might be collisions with hashes, they're in no way unique... Though the probability is rather low. Anyways, this is a nice explanation of the real issue.
- oleganza 13y ago
  For all practical purposes it's unique. Otherwise, Bitcoin is broken and useless.
n1c 13y ago
> they instead should watch if the address X (specified by user) got amount N (specified by user) from outputs Y, Z and W (used by MtGox). This doesn't seem ideal.
- jnbiche 13y ago
  Why? In order to be running an exchange like Gox, you have to be monitoring arbitrary addresses anyway. It's a simple solution to a simple problem, and it's pretty telling that Gox had this problem to begin with (but doesn't surprise me at all).
  - rout39574 13y ago
    Because if this mode of transfer ever becomes more than a toy, then there will be massive overloading of those values. Can you come up with circumstances in which someone might choose to make successive transactions of the same value? Especially if that might confuse the issue? You want to be able to tell if _this_ transaction completed, not if, say "A transaction that really looks like this one" completed.
    - haakon 13y ago
      Two transactions with the same inputs and the same outputs can safely be considered the same transaction. You don't just compare the transaction value.
    - SEMW 13y ago
      No. "successive transactions of the same value [between the same people]" will not have the same transaction inputs. A 'transaction input' in bitcoin isn't the originator's pubkey, it's the output of a previous transaction. A second transaction which literally had the same inputs as a first would be a doublespend attempt.
wfunction 13y ago
Utter nonsense: > If you need a quick answer: there’s no bug in the Bitcoin itself. > Is it a design issue in Bitcoin to allow slight changes in the transactions? Yes, probably is.
- kubiiii 13y ago
  A design issue is not a bug is it? This design issue seems to have lead to the bug in Mt Gox implementation though.
  - wfunction 13y ago
    That's like saying "it's only illegal if you get caught".
- oleganza 13y ago
  This is known design "issue", but it's a part of the protocol and thus not a bug which must be fixed. Bitcoin has many odd facets and all of them must be understood by anyone making bitcoin software.
- jnbiche 13y ago
  It's only an "issue" to the extent that someone who is not familiar with the protocol might be misled by it. After 4 years running an exchange, one would hope that Gox would have someone familiar enough with the protocol to avoid this, but I guess not. This page has been there for at last 1 year: https://en.bitcoin.it/wiki/Transaction_Malleability https://en.bitcoin.it/wiki/Transaction_Malleability
- corresation 13y ago
  It does sound like a bug in Bitcoin, and it's one that people have to specifically work around. It does not sound deadly, but nor does it sound ideal. And it does seem likely that someone figured out that Gox was doing what they were doing and exploited it, the question being to what extent. But it is interesting evaluating the commentary given that people who have a vested interest in Bitcoin will naturally have a very strong reason to defend the protocol and fundamentals (the linked submission even encourages readers to go buy into the hype at a "huge discount"). This is something you see on equity trading boards, the guy deep underwater on the penny stock loudly defending all fundamentals of his choice.
bjourne 13y ago
That explanation is so simple it just can't be right. :) Usually if two objects are equal their hashes should be identical too. That's the whole point of hashing since otherwise O(1) lookups aren't possible. Apparently the bitcoin protocol breaks that expectation since two semantically equal transactions can have different hashes.
- pmorici 13y ago
  It doesn't break that expectation it's just a misunderstanding of what data is included in the hash.
- makomk 13y ago
  The main and most important use of transaction hashes in Bitcoin is to ensure that, when blocks are mined, the transactions contained within those blocks are locked in and any modification of those transactions can be detected and rejected. Transaction malleability is meant to change the hash of the transaction, because that ensures no-one can mutate transactions after they're in a block. If you really need to track transactions in the way MtGox is doing, you should construct your own transaction ID that hashes everything except the scriptSigs (which are malleable).
  - bjourne 13y ago
    > Transaction malleability is meant to change the hash of the transaction, because that ensures no-one can mutate transactions after they're in a block. Huh? > If you really need to track transactions in the way MtGox is doing, you should construct your own transaction ID that hashes everything except the scriptSigs (which are malleable). Yeah. Except the Bitcoin network also apparently produces its own hashes of transactions and those hashes include mutable data leading to undesirable situations like hash(txn1) != hash(txn2) even though txn1 == txn2. It's like hashing people by their name and age instead of name and date of birth. Next year you won't find them in your table because their age is different.
joosters 13y ago
How on earth can this 'fix' scale? Let's imagine a future world where all monetary transactions go through Bitcoin. So the only way for me to find out if my transaction took place is to search the list of every worldly transaction to spot mine?
- StavrosK 13y ago
  Don't you already have to do that? You have to download the entire blockchain to see if a transaction happened. The fix is just to look for a different attribute on the data you're already looking at.
  - jnbiche 13y ago
    Precisely. If you're offering any type of merchant services (and Gox does), then you already have to monitor all incoming transactions. All this means is that you have to keep a small list of the addresses of people with pending withdrawals, along with the corresponding Gox outputs, and then remove those addresses from the list as each block rolls in (at however many confirmations they determine they need).
- vertex-four 13y ago
  If you're running a full node - basically, Bitcoin-Qt or bitcoind - your client goes over every single transaction and verifies it as it is. In Bitcoin-Qt/bitcoind, the client does not depend on transaction hashes to verify that a transaction took place, instead depending on the input/output lists. Any competently written "light" client does the same. Obelisk, written by the libbitcoin people, provides an address/transaction tracking system over the network that could be used if bitcoind does not meet requirements. Basically, this fix has been in place for a long time everywhere aside from MtGox.
- maxerickson 13y ago
  A service could watch addresses for you. (blockchain.info essentially does this for every address appearing in the blockchain) But yeah, bitcoin as implemented is way to complicated to want to deal with all the time, everyday.
baby 13y ago
Can someone link to a better explanation? I'm not really satisfied by this blog post.
- wcoenen 13y ago
  This is a good start: https://en.bitcoin.it/wiki/Transaction_Malleability https://en.bitcoin.it/wiki/Transaction_Malleability
- Anderkent 13y ago
  From the older thread: http://www.reddit.com/r/Bitcoin/comments/1x93tf/some_irc_chatter_about_what_is_going_on_at_mtgox/cf99yac http://www.reddit.com/r/Bitcoin/comments/1x93tf/some_irc_cha...
tempodox 13y ago
What Mount?
- RankingMember 13y ago
  Magic: The Gathering Online Exchange
- donpdonp 13y ago
  Mount Gox is a malapropism of the acronym MTGOX (which is expanded in other comments on this thread)
ck2 13y ago
On a side note, if you believe in BTC, I cannot remember the last time you could buy it for less than $600 like today.
- gst 13y ago
  You mean like 2 months ago?
  - ck2 13y ago
    Had to look at the exchange charts - I guess there was a two day dip around December 18th but it quickly corrected.
    - ErsatzVerkehr 13y ago
      "corrected" I love this teleological market-speak.
      - ck2 13y ago
        Ha, yeah I watch NBR before the PBS Newshour some days so unfortunately I've picked up on some of the terminology. I jokingly refer to NBR as PBS's dark little corner.
  - dopamean 13y ago
    The BTC believers have very short memories.
    - oleganza 13y ago
      BTC believers know there was never a year without at least 200% price increase.
- beedogs 13y ago
  Hard to tell whether that was someone fucking up their sell order or someone dumping a whole lot of (ill-gotten?) bitcoins onto BTC-e.
patio11 13y ago
"It's a protocol bug!" "It's not a protocol bug!" is sort of a moot point. Bitcoin is a protocol in the sense that the IE6 rendering engine is a protocol: yes, rigorously examining what the client monoculture does and does not emit does allow you to describe some set-of-rules. Trying to create another Bitcoin client which attempts to agree with that set of rules is, ahem, fraught. You have to be bug-for-bug compatible with the Satoshi client implementation, not with the Satoshi client's declared behavior, design intent, or whatever constellation of PDFs and Wiki posts that the Bitcoin community anoints as "the protocol."
- oleganza 13y ago
  Satoshi never had any "whitepaper spec" which proclaims "intended" behaviour. The protocol is whatever 100% of users agree with. It started with one implementation, today we have many of them. And we already had the protocol changed in a hard way ("hardfork") at least 4 times: 1. In 2009 when they fixed OP_RETURN and OP_CODESEPARATOR bug allowing to spend anyone's coins. 2. In 2010 when integer overflow created billions of BTC in one tx. 3. In 2012 when "OP_HASH160 <hash> OP_EQUAL" script was redefined to be interpreted as a hash of a script (see BIP16, Pay-to-Script-Hash aka "P2SH"). 4. In 2013 when v0.8/v0.7 difference in database engines caused half of the network mine parallel blockchain due to obscure limit on number of file handles. The fix which was gradually introduced after reverting "incompatible" (although, longer) chain, was changing the protocol in a hard way. The takeway from this: there's no parallel universe where a clearly defined spec in English is how all software operates to produce exactly the same blockchain. The most precise description would be a computer code itself running on the same hardware everyone uses. Anyone coming up with a "spec" of Bitcoin will only have a "description", not a "prescription".
  - gus_massa 13y ago
    The protocol is whatever 51% of users agree with.
    - deleted 13y ago
      [deleted]
DennisP 13y ago
Interesting comment from the lead dev of Ethereum (a new cryptocurrency): > aside from cryptocurrencies, there really is no other situation where the fact that you can take a valid signature and turn it into another valid signature with a different hash is a significant problem, and yet here it’s fatal. http://blog.ethereum.org/2014/02/09/why-not-just-use-x-an-instructive-example-from-bitcoin/ http://blog.ethereum.org/2014/02/09/why-not-just-use-x-an-in...
angryasian 13y ago
I've been through the other thread of another article declaring mt.gox is wrong, but I still don't see the solution. What is the recommended solution by bitcoin implementers to verify a transaction succeeded, with transaction malleability existing ?
- greyman 13y ago
  I am not bitcoin implementer, but I believe you need to maintain the list of pending withdrawal addresses, and monitor that the transactions with mtgox outputs sent to those addresses received at least 6 confirmations.
  - angryasian 13y ago
    Where would those 6 confirmations come from ?
    - greyman 13y ago
      From the network. Or, at least as I understand it, Transaction Malleability basically means, that the "final" transaction can have different txid, so you shouldn't rely on it. But you can check if the transaction went through the same way as the bitcoin-qt does it, which is what BTC developer Gregory Maxwell recommends here: http://sourceforge.net/mailarchive/message.php?msg_id=31956576 http://sourceforge.net/mailarchive/message.php?msg_id=319565...
donpdonp 13y ago
"Or, MtGox themselves see that they’ve been watching for transaction for too long and could automatically re-send another transaction" There is no amount of time to wait until a bitcoin transaction is considered dead. Once its been communicated over the network, one has to assume it can be redeemed (incorporated into the blockchain) anywhere from never to a thousand years from now. Checking for txid even without malleable transactions is not helpful. If a bitcoin payment has been issued, and a customer wishes it to be re-issued, the (only?) safe approach is to move the entire address contents to a new address, wait for that to hit the blockchain, and reissue the payment from the new address. When different customer's balances are mixed in the same address, things get more difficult, and seeing as how its customary to pull balances from multiple addresses to satisfy the inputs a single transaction, I think mtgox has a claim to complexity beyond their ability to fix without help from the protocol itself. As far as being affected by malleable transactions, an exchange should have a value on their 'books' for each customer and a value in the 'bank'/wallet for each customer. By keeping track of each set of addresses for each customer, like bitcoind does in its wallet, the two can be audited with each new block on the chain.

146 points by oleganza 13y ago

adv0r 13y ago

I want to donate all the money I got to this guy

Kenji 13y ago

"MtGox remembers a hash of that transaction (unique fingerprint of its contents)" Technically, there might be collisions with hashes, they're in no way unique... Though the probability is rather low. Anyways, this is a nice explanation of the real issue.

oleganza 13y ago
For all practical purposes it's unique. Otherwise, Bitcoin is broken and useless.

n1c 13y ago

> they instead should watch if the address X (specified by user) got amount N (specified by user) from outputs Y, Z and W (used by MtGox). This doesn't seem ideal.

jnbiche 13y ago
Why? In order to be running an exchange like Gox, you have to be monitoring arbitrary addresses anyway. It's a simple solution to a simple problem, and it's pretty telling that Gox had this problem to begin with (but doesn't surprise me at all).
- rout39574 13y ago
  Because if this mode of transfer ever becomes more than a toy, then there will be massive overloading of those values. Can you come up with circumstances in which someone might choose to make successive transactions of the same value? Especially if that might confuse the issue? You want to be able to tell if _this_ transaction completed, not if, say "A transaction that really looks like this one" completed.
  - haakon 13y ago
    Two transactions with the same inputs and the same outputs can safely be considered the same transaction. You don't just compare the transaction value.
  - SEMW 13y ago
    No. "successive transactions of the same value [between the same people]" will not have the same transaction inputs. A 'transaction input' in bitcoin isn't the originator's pubkey, it's the output of a previous transaction. A second transaction which literally had the same inputs as a first would be a doublespend attempt.

wfunction 13y ago

Utter nonsense: > If you need a quick answer: there’s no bug in the Bitcoin itself. > Is it a design issue in Bitcoin to allow slight changes in the transactions? Yes, probably is.

kubiiii 13y ago
A design issue is not a bug is it? This design issue seems to have lead to the bug in Mt Gox implementation though.
- wfunction 13y ago
  That's like saying "it's only illegal if you get caught".
oleganza 13y ago
This is known design "issue", but it's a part of the protocol and thus not a bug which must be fixed. Bitcoin has many odd facets and all of them must be understood by anyone making bitcoin software.
jnbiche 13y ago
It's only an "issue" to the extent that someone who is not familiar with the protocol might be misled by it. After 4 years running an exchange, one would hope that Gox would have someone familiar enough with the protocol to avoid this, but I guess not. This page has been there for at last 1 year: https://en.bitcoin.it/wiki/Transaction_Malleability https://en.bitcoin.it/wiki/Transaction_Malleability
corresation 13y ago
It does sound like a bug in Bitcoin, and it's one that people have to specifically work around. It does not sound deadly, but nor does it sound ideal. And it does seem likely that someone figured out that Gox was doing what they were doing and exploited it, the question being to what extent. But it is interesting evaluating the commentary given that people who have a vested interest in Bitcoin will naturally have a very strong reason to defend the protocol and fundamentals (the linked submission even encourages readers to go buy into the hype at a "huge discount"). This is something you see on equity trading boards, the guy deep underwater on the penny stock loudly defending all fundamentals of his choice.

bjourne 13y ago

That explanation is so simple it just can't be right. :) Usually if two objects are equal their hashes should be identical too. That's the whole point of hashing since otherwise O(1) lookups aren't possible. Apparently the bitcoin protocol breaks that expectation since two semantically equal transactions can have different hashes.

pmorici 13y ago
It doesn't break that expectation it's just a misunderstanding of what data is included in the hash.
makomk 13y ago
The main and most important use of transaction hashes in Bitcoin is to ensure that, when blocks are mined, the transactions contained within those blocks are locked in and any modification of those transactions can be detected and rejected. Transaction malleability is meant to change the hash of the transaction, because that ensures no-one can mutate transactions after they're in a block. If you really need to track transactions in the way MtGox is doing, you should construct your own transaction ID that hashes everything except the scriptSigs (which are malleable).
- bjourne 13y ago
  > Transaction malleability is meant to change the hash of the transaction, because that ensures no-one can mutate transactions after they're in a block. Huh? > If you really need to track transactions in the way MtGox is doing, you should construct your own transaction ID that hashes everything except the scriptSigs (which are malleable). Yeah. Except the Bitcoin network also apparently produces its own hashes of transactions and those hashes include mutable data leading to undesirable situations like hash(txn1) != hash(txn2) even though txn1 == txn2. It's like hashing people by their name and age instead of name and date of birth. Next year you won't find them in your table because their age is different.

joosters 13y ago

How on earth can this 'fix' scale? Let's imagine a future world where all monetary transactions go through Bitcoin. So the only way for me to find out if my transaction took place is to search the list of every worldly transaction to spot mine?

StavrosK 13y ago
Don't you already have to do that? You have to download the entire blockchain to see if a transaction happened. The fix is just to look for a different attribute on the data you're already looking at.
- jnbiche 13y ago
  Precisely. If you're offering any type of merchant services (and Gox does), then you already have to monitor all incoming transactions. All this means is that you have to keep a small list of the addresses of people with pending withdrawals, along with the corresponding Gox outputs, and then remove those addresses from the list as each block rolls in (at however many confirmations they determine they need).
vertex-four 13y ago
If you're running a full node - basically, Bitcoin-Qt or bitcoind - your client goes over every single transaction and verifies it as it is. In Bitcoin-Qt/bitcoind, the client does not depend on transaction hashes to verify that a transaction took place, instead depending on the input/output lists. Any competently written "light" client does the same. Obelisk, written by the libbitcoin people, provides an address/transaction tracking system over the network that could be used if bitcoind does not meet requirements. Basically, this fix has been in place for a long time everywhere aside from MtGox.
maxerickson 13y ago
A service could watch addresses for you. (blockchain.info essentially does this for every address appearing in the blockchain) But yeah, bitcoin as implemented is way to complicated to want to deal with all the time, everyday.

baby 13y ago

Can someone link to a better explanation? I'm not really satisfied by this blog post.

wcoenen 13y ago
This is a good start: https://en.bitcoin.it/wiki/Transaction_Malleability https://en.bitcoin.it/wiki/Transaction_Malleability
Anderkent 13y ago
From the older thread: http://www.reddit.com/r/Bitcoin/comments/1x93tf/some_irc_chatter_about_what_is_going_on_at_mtgox/cf99yac http://www.reddit.com/r/Bitcoin/comments/1x93tf/some_irc_cha...

tempodox 13y ago

What Mount?

RankingMember 13y ago
Magic: The Gathering Online Exchange
donpdonp 13y ago
Mount Gox is a malapropism of the acronym MTGOX (which is expanded in other comments on this thread)

ck2 13y ago

On a side note, if you believe in BTC, I cannot remember the last time you could buy it for less than $600 like today.

gst 13y ago
You mean like 2 months ago?
- ck2 13y ago
  Had to look at the exchange charts - I guess there was a two day dip around December 18th but it quickly corrected.
  - ErsatzVerkehr 13y ago
    "corrected" I love this teleological market-speak.
    - ck2 13y ago
      Ha, yeah I watch NBR before the PBS Newshour some days so unfortunately I've picked up on some of the terminology. I jokingly refer to NBR as PBS's dark little corner.
- dopamean 13y ago
  The BTC believers have very short memories.
  - oleganza 13y ago
    BTC believers know there was never a year without at least 200% price increase.
beedogs 13y ago
Hard to tell whether that was someone fucking up their sell order or someone dumping a whole lot of (ill-gotten?) bitcoins onto BTC-e.

patio11 13y ago

"It's a protocol bug!" "It's not a protocol bug!" is sort of a moot point. Bitcoin is a protocol in the sense that the IE6 rendering engine is a protocol: yes, rigorously examining what the client monoculture does and does not emit does allow you to describe some set-of-rules. Trying to create another Bitcoin client which attempts to agree with that set of rules is, ahem, fraught. You have to be bug-for-bug compatible with the Satoshi client implementation, not with the Satoshi client's declared behavior, design intent, or whatever constellation of PDFs and Wiki posts that the Bitcoin community anoints as "the protocol."

oleganza 13y ago
Satoshi never had any "whitepaper spec" which proclaims "intended" behaviour. The protocol is whatever 100% of users agree with. It started with one implementation, today we have many of them. And we already had the protocol changed in a hard way ("hardfork") at least 4 times: 1. In 2009 when they fixed OP_RETURN and OP_CODESEPARATOR bug allowing to spend anyone's coins. 2. In 2010 when integer overflow created billions of BTC in one tx. 3. In 2012 when "OP_HASH160 <hash> OP_EQUAL" script was redefined to be interpreted as a hash of a script (see BIP16, Pay-to-Script-Hash aka "P2SH"). 4. In 2013 when v0.8/v0.7 difference in database engines caused half of the network mine parallel blockchain due to obscure limit on number of file handles. The fix which was gradually introduced after reverting "incompatible" (although, longer) chain, was changing the protocol in a hard way. The takeway from this: there's no parallel universe where a clearly defined spec in English is how all software operates to produce exactly the same blockchain. The most precise description would be a computer code itself running on the same hardware everyone uses. Anyone coming up with a "spec" of Bitcoin will only have a "description", not a "prescription".
- gus_massa 13y ago
  The protocol is whatever 51% of users agree with.
  - deleted 13y ago
    [deleted]

DennisP 13y ago

Interesting comment from the lead dev of Ethereum (a new cryptocurrency): > aside from cryptocurrencies, there really is no other situation where the fact that you can take a valid signature and turn it into another valid signature with a different hash is a significant problem, and yet here it’s fatal. http://blog.ethereum.org/2014/02/09/why-not-just-use-x-an-instructive-example-from-bitcoin/ http://blog.ethereum.org/2014/02/09/why-not-just-use-x-an-in...

angryasian 13y ago

I've been through the other thread of another article declaring mt.gox is wrong, but I still don't see the solution. What is the recommended solution by bitcoin implementers to verify a transaction succeeded, with transaction malleability existing ?

greyman 13y ago
I am not bitcoin implementer, but I believe you need to maintain the list of pending withdrawal addresses, and monitor that the transactions with mtgox outputs sent to those addresses received at least 6 confirmations.
- angryasian 13y ago
  Where would those 6 confirmations come from ?
  - greyman 13y ago
    From the network. Or, at least as I understand it, Transaction Malleability basically means, that the "final" transaction can have different txid, so you shouldn't rely on it. But you can check if the transaction went through the same way as the bitcoin-qt does it, which is what BTC developer Gregory Maxwell recommends here: http://sourceforge.net/mailarchive/message.php?msg_id=31956576 http://sourceforge.net/mailarchive/message.php?msg_id=319565...

donpdonp 13y ago

"Or, MtGox themselves see that they’ve been watching for transaction for too long and could automatically re-send another transaction" There is no amount of time to wait until a bitcoin transaction is considered dead. Once its been communicated over the network, one has to assume it can be redeemed (incorporated into the blockchain) anywhere from never to a thousand years from now. Checking for txid even without malleable transactions is not helpful. If a bitcoin payment has been issued, and a customer wishes it to be re-issued, the (only?) safe approach is to move the entire address contents to a new address, wait for that to hit the blockchain, and reissue the payment from the new address. When different customer's balances are mixed in the same address, things get more difficult, and seeing as how its customary to pull balances from multiple addresses to satisfy the inputs a single transaction, I think mtgox has a claim to complexity beyond their ability to fix without help from the protocol itself. As far as being affected by malleable transactions, an exchange should have a value on their 'books' for each customer and a value in the 'bank'/wallet for each customer. By keeping track of each set of addresses for each customer, like bitcoind does in its wallet, the two can be audited with each new block on the chain.