Bitcoin transaction malleability: looking at the bytes

http://www.righto.com/2014/02/bitcoin-transaction-malleability.html

by guan • 12 years ago

136 64 12 years ago

patio118• 12 years 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• 12 years 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.

patio118• 12 years 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.

Xylakant3• 12 years 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...

baby• 12 years ago

So wait, I guess reorganizations are scarce, but if one happens payers of the one that got erased get their money back and the receivers lose their money. That is dangerous!

Also, with the difficulty increasing, block are going to be rarer and you'll have to wait way longer to get a confirmation right?

And what if 3 guys find the same block, at the same time, at 3 very different places in the world? Can't imagine what would happen.

patio118• 12 years ago

Reorganizations are not scarce. They get scarcer with the depth of the reorganization.

Also, with the difficulty increasing, block are going to be rarer and you'll have to wait way longer to get a confirmation right?

Nope. The network adjusts the difficulty dynamically to target plus or minus ten minutes per block. The reason difficulty is increasing is to keep blocks coming in every plus or minus ten minutes rather than having ASICs generating them several thousand times a second, which is what would happen if the difficulty was still where it was when the entire Bitcoin network ran on Satoshi's Macbook.

And what if 3 guys find the same block, at the same time, at 3 very different places in the world? Can't imagine what would happen.

Feel free to reason it out. Miners each pick one of the three to try to build off. (Many Bitcoiners assume they pick randomly but I believe that to be a very problematic assumption.) Eventually, a miner wins the race. "His" ancestor block more than likely becomes the block which history adopts. The other two, more than likely, vanish and are never heard again. If your transaction was in one of them but not in the block which actually got adopted, you wait until it plays pingpong around the network or you retransmit.

This has happened hundreds of times before.

tveita• 12 years ago

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

At least as long as people aren't using the selfish mining strategy.

If one or more large pools were doing selfish mining, you might see long parallel chains with some regularity.

patio118• 12 years ago

This is likely true, and I wanted to try explaining it, but I only had time to write a comment and not a journal article. Suffice it to say that the Bitcoin community widely believes what I wrote, and that interested HNers should look up the actual journal article about selfish mining, which is really accessible (well, by the standard of writing about Bitcoin).

rwmj• 12 years ago

What is the motivation of the attackers?

ChuckMcM• 12 years ago

I can speculate on three motivations:

1) A nation-state activity to destroy the credibility and usefulness of such currencies before such currencies become entrenched and their ability to track criminal activity through money transfer is seriously compromised. (depending on who you ask, 'following the money' is either #1 or #2 on the stop/solve crime toolbox)

2) A crime-syndicate increasing their 'profits' by getting the system to pay out in unanticipated ways. Because, at its heart, crime is all about the benjamins[1] so finding ways to increase profits without increasing risk is an ongoing activity.

3) Idle mathematicians/cryptographers/hackers demonstrating their skillz against what they perceive to be a dangerously flawed system. In the hopes that it will {die|improve|humor them}.

[1] US slang for currency.

VMG2• 12 years ago

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.

I agree that the current system of address management is impractical for some applications.

It should be possible to automatically organize addresses in a way that small amounts are sent from addresses that also have small balances, so that this problem does not occur. Your salary payment provider could split up the payment into 9 + 10 * 0.1 Bitcoin.

But it will take a while until the concept and the UI is there.

weavejester2• 12 years ago

As far as I'm aware, that's a pretty accurate and succinct description of the issue.

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.

A minor nitpick: you can demonstrate the accounts are under your control, just not via a "normal" bitcoin transaction.

patio118• 12 years ago

By signing a message with the private key corresponding to the public key of one of your output transactions? I think someone who accepts that as proof doesn't understand what is happening. I could sign "I totes have 9.99 BTC" with the private key corresponding to the 9.99 BTC change output, and if you were a dab hand with the OpenSSL command line you could verify that the signature matched the public key, but you cannot verify that I have not already broadcast a separate transaction moving those 9.99 coins to another address (either mine or that of another party). At that point I might as well give you a signed message saying "I totes am capable of signing messages. This one is signed with a random number. Go me!"

Did you have a different strategy for demonstrating that I control the Bitcoins that aren't fixed with 6+ confirmations yet?

ashray2• 12 years ago

Well, there's a fairly easy work around to this kind of issue.

#1: What if your client kept your bitcoins spliced over several addresses ? So, each address kept just 10 BTC. Now, when you make a 99BTC transaction, you use up 10 addresses and 1 BTC change gets tied up for further confirmation. (adjust the numbers as convenient of course)

Thus, you basically can't spend your change until 6 confirmations but now it's far lesser than the 9.99 you surmised.

#2: (this one's better!) Or what if you just kept 10 separate addresses and used 1 at a time manually ? You'll tie up 1 address for up to an hour but the likelihood of making 10 transactions an hour is fairly low, and if you did want to do that, you could still split and proceed.

Entropy for BTC addresses is fairly high and each person on the planet can have far more than 10 so this is a non-issue in terms of availability.

Clients could manage these scenarios fairly easily if unconfirmed inputs/outputs were indeed to become a limiting factor.

justusranvier• 12 years ago

Addresses are one-time payment codes and should never be reused at all under any circumstances.

This is how Bitcoin was intended to be used from the beginning, and how it's always been implemented in the reference client, but unfortunately due to a usability bug the most popular wallets these days reuse addresses and are teaching new users this incredibly destructive habit.

The problem started in the original client where it generated new private keys randomly. This meant effectively there was no way to implement a sane backup policy. Later on, they implemented the ability to generate private keys in batches of 100. This is better, but still problematic because your backup have to be refreshed after no more than 100 operations.

Obviously that was a usability disaster, and so wallet designers worked around that by just using the same private key over and over again. Other people worked out secure deterministic address generation so that you could just backup a single seed once, but by the time that got standardized (BIP32) the damage was already done.

Blockchain.info is the most popular wallet, and they've taught about a million newbies to treat single-use payment codes as permanent account numbers. It's a privacy and security catastrophe, but those issues are invisible to most people who only care about ease of use.

Traubert2• 12 years ago

But the mutated version necessarily has the same outputs, right? How does mutating then make your rent payment invalid?

edit: To clarify, once the mutated transaction is on the blockchain even once, the wallet should be able to figure out what the correct transaction is now. True, when it's not on the blockchain at all, the transaction can get rejected.

Groxx2• 12 years ago

I'm still working through the details at the moment, but: your rent payment depends on the previous transaction's signature. Since that was changed, it's no longer valid.

They effectively forked the sandwich payment, and your rent payment is only valid on your branch. The rent money will come back under your control because the transaction will be refused, but you'll have to make a new transaction (on top of the now-valid mutated branch) to actually pay it.

gojomo• 12 years ago

You absolutely can spend change-in-flight – the default client even allowed it, last I checked.

It's just the risk of third-party mutation, as under the current mischief-making malleability attack, plus the compounded risk created by chains of unconfirmed-transactions, that makes this a problem.

Long before the current attacks, I had my own outgoing payments stuck when they were inadvertently arranged as a dependent chain, and the first transaction never confirmed.

But once you (or the people writing your software) know of such risk, mitigating workarounds are easy and automatable:

You arrange for receipts of large amounts to be broken into smaller units, capping the amount of change that might be 'in flight'. (If necessary, you do this break-up yourself upon receipt, knowing there's a period of up to an hour before that completes.)

Or more generally, you keep small working amounts of mixed-size coins ready for short-term use, simply not expecting to spend a large new receipt instantly. (No one who is living 'hand to mouth' should be relying on Bitcoin for all their life's necessities, anyway. It's still beta!)

When the third-party mutated-transactions risk is contained – within a week or two, all major miners will probably blockade tampered transactions – this risk of stuck funds will evaporate... but the lessons and new software practices for handling corner cases will persist, ready for future similar situations.

It's interesting that patio11 is using receipt-of-salary as an example. Until your bank knows you, classic paychecks can be held for a day or more before full funds are available. Until clearing-practices were changed in the US a few years ago, large paychecks often had most of their funds held as unavailable for 7-10 days – even for checks between large American banks in the same city. This situation persisted for decades.

Further, the fraud of "check-kiting", which is vaguely like the interplay-of-timing-bugs that has tricked some bitcoin-payout systems, was possible in the traditional banking system, on and off, for decades.

Compared to that, are Bitcoin's temporary problems, perhaps involving an hour's holdup, and likely fixable within a week via rapid software iteration, that big of a deal?

When patio11 makes people aware of the transient gotchas and rough-edges, so they can adjust their near-term expectations, that's a public service.

But if these things are portrayed as inherent and insurmountable weaknesses that doom the system? That viewpoint is going to look like 1995 Clifford Stoll.

scottcanoni2• 12 years 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.

patio118• 12 years 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• 12 years ago

Satoshi did anticipate that DDoS would be a major problem for BitCoin, which is essentially what this is.

ChristianMarks4• 12 years 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...

scottcanoni2• 12 years ago

Are you saying that these are the modified transaction IDs?

ChristianMarks4• 12 years 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• 12 years ago

Yep, a lot of us have gotten those. There is also another one that starts "1Sochi..."

wmf• 12 years ago

I got those as well. This appears to be completely unrelated to malleability.

ChristianMarks4• 12 years ago

OK. The article mentions an unconfirmed transaction starting with 1Enjoy1...

oscilloscope2• 12 years 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• 12 years ago

People have speculated that this is an attempt by some attacker to correlate ownership of older and newer addresses en masse. Some wallets give the user no control over which address(es) are used as the source for any given payment. When a tiny sum shows up in some old empty address still being tracked by the wallet, those coins will eventually be sent on automatically as part of a larger payment, alongside coins from one of the user's currently active addresses, and suddenly the common ownership of those two addresses becomes public record.

oscilloscope2• 12 years ago

Most wallets only have the crudest tools to prevent identity attacks like this, such as setting a preferred address for the next payment. Frequently, you won't even see what the inputs and outputs of a transaction will be before it's broadcast to the network.

ChristianMarks4• 12 years ago

In that case, maybe publishing the addresses wasn't the most discreet thing imaginable. Still my "holdings" amount to a Starbucks card converted to BTC through an online service mentioned on HN. I wanted to motivate myself to become interested in Bitcoins, and thought that watching a miniscule amount might help, but the mischief around cryptocurrencies is demotivating. Cryptocurrencies should be regulated. Perhaps the Bitcoin will serve in the long run to address some rent-seeking behavior in the banking system. For now it's the Wild West.

codeflo2• 12 years 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• 12 years ago

All of the transaction except the "signature"s is signed. The modifications come from modifying the signatures and/or their encoding.

codeflo2• 12 years 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.

joeyh• 12 years ago

Why is the signature fed through a bitcoin script? Not using a (non-turing-complete-but-still) programming language to encode a signature seems like a good first step to avoiding malleability.

Bitcoin has good/interesting reasons for using scripts inside transactions, but AIUI these are separate from the signature script.

greatsuccess• 12 years ago

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

Bitcoin transaction malleability: looking at the bytes

Related Stories