15 ms·

Bitcoin transaction malleability: looking at the bytes

136 points by guan 13y ago

patio11 13y ago
I tried to explain the issue with change on Twitter earlier and got a few Bitcoin advocates hot under the collar, but here it is: Say you receive 10 Bitcoin as, I don't know, your salary. You then spend 0.01 Bitcoin on a sandwitch, leaving you with 9.99 in change. Because you cannot safely spend change until after the sandwitch transaction is fixed in the block chain, this freezes your 9.99 remaining Bitcoin for about an hour. They're still yours, you just can't spend them. If you hypothetically try to spend one after 10 minutes (maybe you need to, I don't know, pay rent or do something people routinely do with actual money), you have two options: 1) If your counterparty is on the ball, they'll say "Nope, you don't have a single Bitcoin to your name right now." (You know you do, but he can't prove it, as 100% of your Bitcoin are currently in flight rather than being in accounts demonstrably under your control.) 2) If your counterparty is not on the ball, two outcomes: a) If your sandwich transaction is mutated and the mutated version makes it onto the block chain first, or if it is mutated and the mutated version loses the race to be confirmed but the confirmation of your original transaction happens on a block that doesn't end up in the block chain due to reorganization [+], then your rent payment fails. Your counterparty will discover later that they don't have the money that they expected, even if they watched you send it. b) If everything goes right, your transaction succeeds, and your counterparty does not realize that you just paid your rent with the Bitcoin equivalent of "The check's in the mail! Honest!" This continues happily until the check is, well, not in the mail. Bitcoin is currently undergoing active attack, causing many transactions by people who don't understand the inner workings of the system to fail. This attack is capable of disrupting (a portion of) transactions worldwide on Bitcoin for about a few tens or hundred dollars a day in botnet renting cost and could be coded by a CS102 student, if you told them where to look and what to do. [+] "What?" Glad you asked. See, the fundamental theory of Bitcoin is that miners throw immense amounts of hashing power to create "blocks" in a sequence. Each block references the last block. Each block also encodes transactions. However, everyone is racing to discover the N+1 block after N is released, so there can actually be multiple N+1 blocks. Only one of them will eventually win. (Bitcoin breaks ties based on height, so if N+1 #1 gets another block concatenated to it before N+1 #2, then it is much more likely to be the block which actually matters. #2 vanishes from consensus history, along with all of the transactions inside of it. That normally isn't a problem if you just rebroadcast your transaction, but if N+1 #2 had "your" transaction and #1 won with the mutated version of your transaction, then the transaction which you actually made is suddenly, retroactively, different from the one you think you made.) The reason everyone keeps talking about "roughly an hour" is because blocks happen at plus or minus every ten minutes, and after N+6 blocks, it is vanishingly unlikely that a transaction in block N will be removed from history by block N being replaced by a totally new chain. You could, for lower risk transactions, count it as "Probably good enough!" after N+2, as long as you're OK with occasionally having your transactions retroactively vanish.
- jimrandomh 13y ago
  The key thing here is that this is strictly about what happens to transactions which don't have confirmations yet. The standard recommendation has always been to wait an hour (6 confirmations) before crediting someone as having sent you Bitcoins, and doing so is an absolute defense against all the shenanigans being talked about.
  - patio11 13y ago
    I have not heard Bitcoiners routinely advise each other "If you buy something with Bitcoins, you probably should not attempt to buy something else for an hour." That's a necessary component of any defense against these shenanigans, at least until the One True Bitcoin Client starts to differentiate between change which is 6+ confirmed and change which isn't yet.
  - Xylakant 13y ago
    > The standard recommendation has always been to wait an hour (6 confirmations) before crediting someone as having sent you Bitcoin Seriously, how should Bitcoin replace real money if that remains true? There's a book store round the corner accepting bitcoin - so I go, select a book, pay and hang around an hour until I get to leave with the book? At least I'd have enough reading material...
    - patio11 13y ago
      The Bitcoin community has two answers to this: #1: "Well if you buy a book with a credit card, the bookstore has no guarantee that that charge actually settles successfully." #2: "Most people won't use Bitcoin directly. They'll keep their Bitcoin with a trusted provider. The trusted provider can verify capability to pay as quickly as a SQL transaction, via any mechanism mutually acceptable to it and the bookstore, which need not involve the blockchain. Providers which routinely allow their customers to steal from other members of the ecosystem won't be trusted for very long, and be forced to transact through the blockchain versus being being extended instantaneous credit." The response to #2 is typically "We could call those providers 'banks'" and the Bitcoin community is, how shall I put this, divided by how much they like that outcome.
scottcanoni 13y ago
Two questions: 1. Do the attackers (users who abuse this), modify all transactions they see or do they target those transactions that only involve their wallet? 2. Even given the relative ease an attacker would have with modifying a transaction, that transaction still needs to be accepted by the majority otherwise their modification is ignored. So given 2 transactions for the same bitcoin transfer, I would guess that 50% of the time their transaction is accepted. I guess that the attacker could modify the transaction, for example, 4 times and then it's an 80% chance that one of their modification is accepted (4 out of 5). Do I have that right? This was a good article, I enjoyed it's breakdown with examples.
- patio11 13y ago
  1) Someone appears to be modifying "a large portion of all transactions." 2) You don't have to make it to a majority, you only have to propagate your transaction to the miner who wins the next block prior to the original broadcaster propagating their transaction to miner of the next block. This is really easy to arrange in a P2P network by, e.g., controlling more nodes than the original party or by e.g. modifying the standard Bitcoin client to not sleep between attempts to propagate transactions or by e.g. communicating preferentially with nodes known to be controlled by or "close to" miners and not bothering to propagate to the 99.X% of nodes which are not. If you control thousands of nodes, which you can trivially do ("rent a botnet"), you will ROFLstomp the propagation capabilities of most people originating transactions. The ease of creating extra nodes is why Satoshi designed Bitcoin as "One CPU one vote" (for a transaction's correctness) rather than "One IP one vote." Unfortunately, it appears that Satoshi did not anticipate that the transaction hash is, effectively, the latter. That wouldn't be problematic except systems which interface with Bitcoin frequently rely on the transaction hash being stable but it is, in effect, written on water for the first hour or so.
  - lockes5hadow 13y ago
    Satoshi did anticipate that DDoS would be a major problem for BitCoin, which is essentially what this is.
ChristianMarks 13y ago
Interesting. I have been "receiving" .00001 BTC from an address beginning with 1Enjoy (1Enjoy1C4bYBr3tN4sMKxvvJDqG8NkdR4Z). This has been ongoing since Feb 10. Another .00001 BTC unconfirmed showed up from another address starting with 1Sochi...
- scottcanoni 13y ago
  Are you saying that these are the modified transaction IDs?
  - ChristianMarks 13y ago
    These are Bitcoin addresses. The hash for the first is 197c054e032f9b6b406625b49fcb2c429c0825633143d082bbbdbcd5fa368bd4 I do not know if it is modified. Neither of them are confirmed. (I converted my Starbucks card balance to a meager fraction of a Bitcoin. Since then my $7.21 has plummeted to $5.69.)
- melarina 13y ago
  Yep, a lot of us have gotten those. There is also another one that starts "1Sochi..."
- wmf 13y ago
  I got those as well. This appears to be completely unrelated to malleability.
  - ChristianMarks 13y ago
    OK. The article mentions an unconfirmed transaction starting with 1Enjoy1...
  - oscilloscope 13y ago
    Have any of these been confirmed? It could be related to malleability if these are test transactions that were invalidated by mutated txids.
- Zidewinder 13y ago
codeflo 13y ago
This post explains the how very well. Now I wonder about the why. Why is there extra data that's part of the transaction hash, but not part of the cryptographic signature? (This fact seems to be the source of the problem.) This is probably not by accident, so what does this design accomplish? Why isn't every bit of the transaction signed?
- nullc 13y ago
  All of the transaction except the "signature"s is signed. The modifications come from modifying the signatures and/or their encoding.
  - codeflo 13y ago
    Well, the signature itself can't be signed (obviously). But that's not a problem for many other uses of cryptographic signatures, there's something about the Bitcoin protocol that makes this an issue, and I'm trying to understand what that is. Why is there any choice in how the signature is encoded? Why is there some sort of "script" (I'm not sure I understand this part) that's important enough to be hashed, but not important enough to be signed? This looks like a very deliberate design decision.
    - gus_massa 13y ago
      I can’t find the exact quote or reference now, but IIRC it was possible to sign a .Net assembly or script, and the signature was in a special block that said “Please ignore this block to calculate the signature”. So you can create the whole thing, calculate the signature and put it in the correct slot without changing the signature.
      - oillio 13y ago
        This is effectively how bitcoin transactions work now. It gets considerably more complicated when you include multi-party signatures. In this case, transactions are signed by multiple private keys, but none of the parties will know the other signatures before they sign the transaction themselves.
greatsuccess 13y ago
Ken is amazing for providing this level of detail. Thanks dude.

136 points by guan 13y ago

I tried to explain the issue with change on Twitter earlier and got a few Bitcoin advocates hot under the collar, but here it is: Say you receive 10 Bitcoin as, I don't know, your salary. You then spend 0.01 Bitcoin on a sandwitch, leaving you with 9.99 in change. Because you cannot safely spend change until after the sandwitch transaction is fixed in the block chain, this freezes your 9.99 remaining Bitcoin for about an hour. They're still yours, you just can't spend them. If you hypothetically try to spend one after 10 minutes (maybe you need to, I don't know, pay rent or do something people routinely do with actual money), you have two options: 1) If your counterparty is on the ball, they'll say "Nope, you don't have a single Bitcoin to your name right now." (You know you do, but he can't prove it, as 100% of your Bitcoin are currently in flight rather than being in accounts demonstrably under your control.) 2) If your counterparty is not on the ball, two outcomes: a) If your sandwich transaction is mutated and the mutated version makes it onto the block chain first, or if it is mutated and the mutated version loses the race to be confirmed but the confirmation of your original transaction happens on a block that doesn't end up in the block chain due to reorganization [+], then your rent payment fails. Your counterparty will discover later that they don't have the money that they expected, even if they watched you send it. b) If everything goes right, your transaction succeeds, and your counterparty does not realize that you just paid your rent with the Bitcoin equivalent of "The check's in the mail! Honest!" This continues happily until the check is, well, not in the mail. Bitcoin is currently undergoing active attack, causing many transactions by people who don't understand the inner workings of the system to fail. This attack is capable of disrupting (a portion of) transactions worldwide on Bitcoin for about a few tens or hundred dollars a day in botnet renting cost and could be coded by a CS102 student, if you told them where to look and what to do. [+] "What?" Glad you asked. See, the fundamental theory of Bitcoin is that miners throw immense amounts of hashing power to create "blocks" in a sequence. Each block references the last block. Each block also encodes transactions. However, everyone is racing to discover the N+1 block after N is released, so there can actually be multiple N+1 blocks. Only one of them will eventually win. (Bitcoin breaks ties based on height, so if N+1 #1 gets another block concatenated to it before N+1 #2, then it is much more likely to be the block which actually matters. #2 vanishes from consensus history, along with all of the transactions inside of it. That normally isn't a problem if you just rebroadcast your transaction, but if N+1 #2 had "your" transaction and #1 won with the mutated version of your transaction, then the transaction which you actually made is suddenly, retroactively, different from the one you think you made.) The reason everyone keeps talking about "roughly an hour" is because blocks happen at plus or minus every ten minutes, and after N+6 blocks, it is vanishingly unlikely that a transaction in block N will be removed from history by block N being replaced by a totally new chain. You could, for lower risk transactions, count it as "Probably good enough!" after N+2, as long as you're OK with occasionally having your transactions retroactively vanish.

jimrandomh 13y ago
The key thing here is that this is strictly about what happens to transactions which don't have confirmations yet. The standard recommendation has always been to wait an hour (6 confirmations) before crediting someone as having sent you Bitcoins, and doing so is an absolute defense against all the shenanigans being talked about.
- patio11 13y ago
  I have not heard Bitcoiners routinely advise each other "If you buy something with Bitcoins, you probably should not attempt to buy something else for an hour." That's a necessary component of any defense against these shenanigans, at least until the One True Bitcoin Client starts to differentiate between change which is 6+ confirmed and change which isn't yet.
- Xylakant 13y ago
  > The standard recommendation has always been to wait an hour (6 confirmations) before crediting someone as having sent you Bitcoin Seriously, how should Bitcoin replace real money if that remains true? There's a book store round the corner accepting bitcoin - so I go, select a book, pay and hang around an hour until I get to leave with the book? At least I'd have enough reading material...
  - patio11 13y ago
    The Bitcoin community has two answers to this: #1: "Well if you buy a book with a credit card, the bookstore has no guarantee that that charge actually settles successfully." #2: "Most people won't use Bitcoin directly. They'll keep their Bitcoin with a trusted provider. The trusted provider can verify capability to pay as quickly as a SQL transaction, via any mechanism mutually acceptable to it and the bookstore, which need not involve the blockchain. Providers which routinely allow their customers to steal from other members of the ecosystem won't be trusted for very long, and be forced to transact through the blockchain versus being being extended instantaneous credit." The response to #2 is typically "We could call those providers 'banks'" and the Bitcoin community is, how shall I put this, divided by how much they like that outcome.

scottcanoni 13y ago

Two questions: 1. Do the attackers (users who abuse this), modify all transactions they see or do they target those transactions that only involve their wallet? 2. Even given the relative ease an attacker would have with modifying a transaction, that transaction still needs to be accepted by the majority otherwise their modification is ignored. So given 2 transactions for the same bitcoin transfer, I would guess that 50% of the time their transaction is accepted. I guess that the attacker could modify the transaction, for example, 4 times and then it's an 80% chance that one of their modification is accepted (4 out of 5). Do I have that right? This was a good article, I enjoyed it's breakdown with examples.

patio11 13y ago
1) Someone appears to be modifying "a large portion of all transactions." 2) You don't have to make it to a majority, you only have to propagate your transaction to the miner who wins the next block prior to the original broadcaster propagating their transaction to miner of the next block. This is really easy to arrange in a P2P network by, e.g., controlling more nodes than the original party or by e.g. modifying the standard Bitcoin client to not sleep between attempts to propagate transactions or by e.g. communicating preferentially with nodes known to be controlled by or "close to" miners and not bothering to propagate to the 99.X% of nodes which are not. If you control thousands of nodes, which you can trivially do ("rent a botnet"), you will ROFLstomp the propagation capabilities of most people originating transactions. The ease of creating extra nodes is why Satoshi designed Bitcoin as "One CPU one vote" (for a transaction's correctness) rather than "One IP one vote." Unfortunately, it appears that Satoshi did not anticipate that the transaction hash is, effectively, the latter. That wouldn't be problematic except systems which interface with Bitcoin frequently rely on the transaction hash being stable but it is, in effect, written on water for the first hour or so.
- lockes5hadow 13y ago
  Satoshi did anticipate that DDoS would be a major problem for BitCoin, which is essentially what this is.

ChristianMarks 13y ago

Interesting. I have been "receiving" .00001 BTC from an address beginning with 1Enjoy (1Enjoy1C4bYBr3tN4sMKxvvJDqG8NkdR4Z). This has been ongoing since Feb 10. Another .00001 BTC unconfirmed showed up from another address starting with 1Sochi...

scottcanoni 13y ago
Are you saying that these are the modified transaction IDs?
- ChristianMarks 13y ago
  These are Bitcoin addresses. The hash for the first is 197c054e032f9b6b406625b49fcb2c429c0825633143d082bbbdbcd5fa368bd4 I do not know if it is modified. Neither of them are confirmed. (I converted my Starbucks card balance to a meager fraction of a Bitcoin. Since then my $7.21 has plummeted to $5.69.)
melarina 13y ago
Yep, a lot of us have gotten those. There is also another one that starts "1Sochi..."
wmf 13y ago
I got those as well. This appears to be completely unrelated to malleability.
- ChristianMarks 13y ago
  OK. The article mentions an unconfirmed transaction starting with 1Enjoy1...
- oscilloscope 13y ago
  Have any of these been confirmed? It could be related to malleability if these are test transactions that were invalidated by mutated txids.
Zidewinder 13y ago

codeflo 13y ago

This post explains the how very well. Now I wonder about the why. Why is there extra data that's part of the transaction hash, but not part of the cryptographic signature? (This fact seems to be the source of the problem.) This is probably not by accident, so what does this design accomplish? Why isn't every bit of the transaction signed?

nullc 13y ago
All of the transaction except the "signature"s is signed. The modifications come from modifying the signatures and/or their encoding.
- codeflo 13y ago
  Well, the signature itself can't be signed (obviously). But that's not a problem for many other uses of cryptographic signatures, there's something about the Bitcoin protocol that makes this an issue, and I'm trying to understand what that is. Why is there any choice in how the signature is encoded? Why is there some sort of "script" (I'm not sure I understand this part) that's important enough to be hashed, but not important enough to be signed? This looks like a very deliberate design decision.
  - gus_massa 13y ago
    I can’t find the exact quote or reference now, but IIRC it was possible to sign a .Net assembly or script, and the signature was in a special block that said “Please ignore this block to calculate the signature”. So you can create the whole thing, calculate the signature and put it in the correct slot without changing the signature.
    - oillio 13y ago
      This is effectively how bitcoin transactions work now. It gets considerably more complicated when you include multi-party signatures. In this case, transactions are signed by multiple private keys, but none of the parties will know the other signatures before they sign the transaction themselves.

greatsuccess 13y ago

Ken is amazing for providing this level of detail. Thanks dude.