Topic: What the "average user" needs to know about Transaction Mutability (Read 38935 times)

The thing is... such behavior was already known since 2011. People writing software to handle large BTC amount should at least have read the specs, and known that txid cannot be used for tracking purpose.


You should keep track of the spent/unspent status of the outputs you used as an input of your transaction. Whatever is the version of the transaction that gets included in the blockchain, the input will appear "spent" if the transaction goes trough.

Additionnally, if you reissue a transaction, you should ALWAYS re-use at least one of the input. So that only one of the two transactions can ever confirm, even if the first one finally gets confirmed after you issued the second.

Ok, this make so much more sense. Thank you DaT.

So if I set up a trading system, and
* someone makes a withdraw
* I have a log of the transaction id A of that withdraw
* They make another duplicate transaction B which has a different transaction id of A
* I see that A didn't make it into the blockchain (though untracked transaction B did make it in)
* Upon the user's request I make another transaction C to remedy that A failed.
* Rinse and repeat.

Wow, that is a problem. I now have more sympathy for gox and others as this could easily happen, though they should have had some basic human powered fail-safes to prevent a run-away situation.

So as a provider, what information should I keep as the unique identifier for the transaction that would prevent this issue. I guess it would be something easily searchable in the blockchain.

Thank you DeathAndTaxes. You always write good stuff.

So simple way for mtgox to remain solvent and patch the lost coins.

Trap all users from moving their btc out.
Buy the coins from it's own members at depressed prices...now $100++ and sell on the other exchange at $600++.....repeat...till earn enough to patch the hole.

Put all the earned coins and money into the central fund again. And mtgox is good to go!

I wouldn't say it is "too late".  I am fairly certain with the plan laid out by sipa ( https://gist.github.com/sipa/8907691 ) there is a road to immutable tx ids in bitcoins future.   It won't however happen overnight.  It probably is going to be the better part of a year as it will need support of users and miners, provide a way forward without splitting the network, will require extensive testing and rolled out in phases.

Short term "patch": make clients handle mutable tx ids in a more consistent and cautious manner.
Long term "solution": ensure tx ids are immutable (or at least immutable by third parties).

It is the same thing.  See the bottom of the OP.

That's the point: NOBODY loses. It's more of a nuisance, because the id of transactions is changed before being accepted. But the coins get accepted. If people rely on those id to know if a transaction was accepted, they might be lead to believe that the transaction failed, EVEN if the transaction in fact went trough.

That is a minor nuisance in case of the standart client, because the client sometimes used the "change" of an unconfirmed transaction you sent as an input of another transaction. If the transaction is mutated before it is accepted, then the second transaction will fail, and you'll have to send it again. Also the standart client may be confused by mutated transactions, and show a given transaction twice. But it is a display error, not a protocol error. And it sorts itself out when the transaction confirms.

---

NOW, if people act stupid, THEN it might be more of a problem.

MtGox relied on transaction ID to check if a user withdrawal went trough. Some users complained that their withdrawal failed (even if it had not), and because it had mutated, MtGox tought that the transaction failed too. So they sent the coins again, and NOW lost some coins. IF they had checked their balance, IF they had checked the spent status of the inputs, they would have noticed the user lied, and should not send the coin.

MtGox lost coins, but it is their fault. It was not a protocol failure, not a double spend; it was a double send.

---

ALSO, it -might- have happened that a merchant accepting unconfirmed transactions as payment might have lost some coins. Merchants should never do that, but many did for small amounts. For most cases, it is not a problem: even if the transaction mutates, the merchant gets the money. HOWEVER, if the merchant was foolish enough to accept an unconfirmed transaction taking as input the output of another unconfirmed transaction, THEN if the first transaction mutates, the second fails.

THERE IS NO REPORT of someting like that having happened. But it is a theorical possibility.

---

It must be repeated: The protocol is OK. There is no bug. It was NEVER build with txid immutability in mind. NOBODY should have relied on that. It was a design choice. A bad choice? yes. If they "re-did" the protocol today, the txid would be immutable. But it is too late for that, we must work around it.

Thanks for the good information, but I still didn't get who loses?

Does it have something to do with transaction malleability or they are completely different issues without any connection ?

Heh.  I wonder if this means that Mark will be giving Ver his coins back

from mtgox

"Thanks to our friends at Blockchain.info, MtGox now has a workaround that will
use a unique identifier created by Blockchain to show whether transactions have
been modified or not. This will prevent any fraudulent use of the malleability
issue and protect the assets of our customers"

Blockchain was definitely down several times recently, doing "maintenance"

That said, all exchanges should be subjected to the same issue. Like a vulnerability that was exploited in mtgox but other exchanges should have their turn if they din fix it up.

blockchain.info, not blockchain
and from what little I know, it sounds like a bit of a kluge

gox says blockchain fixed up something on that

That certainly is an alternative solution.  The tx id just needs to be a unique way to identify each transaction.  It doesn't necessarily have to include the signature.  It is possible that in the future there will be new tx types (extending the protocol) with different inputs but that isn't an impossible obstacle.   Client support can be added before the switch in the same manner as it will be for any change.  

It would however require clients to compute tx ids "one way" for existing tx in the blockchain (v1 txs) and a different way for future tx (v3 txs).  I think that break with backwards compatibility is what the developers are looking to avoid.

Still if you wanted to compute the tx hash differently and there was consensus for such a breaking change there is a lot that can be done to improve the bitcoin transaction structure.  The signature should not be in the input.  The signature is of the tx, it should be outside the tx.  The input should just deal with the input.  You could also explicitly define the tx fee to avoid issues with implicit fees.  You could use pubkey reconstruction to remove pubkeys from inputs.  The S value could be computed deterministically from the tx hash to bypass the issue of poor PRNG implementation.

So if we are going to do a breaking change well there is a lot of cleanup which can be done.  It would be possible to reduce the size of the average tx by 30% while keeping the same functionality and improving mutability and security.  I don't think that is the route that we will go though as it would involve a breaking change.

Would it help if the protocol was changed so that, from a certain future block onwards, all transactions must identify any previous transaction they're spending one or more outpoint(s) of, not by the hash of the whole previous tx, as is required today, but instead just by the hash of the core parts of the previous tx? (its inputs/outputs/values, not its signatures.) After all, the purpose of a txid is merely to identify a tx, not to "bless" it as valid. That blessing has already happened when either the free-floating transaction was checked (including signature-checked of course!) and accepted into one's mempool, or a block containing the transaction was checked and found to be valid, or both.

This has the wonderful consequence of rendering unnecessary the endless "arms race" of finding sources of malleability and shutting them down one by one - inventing endless new rules (relay ["standardness"] rules or, eventually, validity rules) about how to write an integer, how many OP_DROPs to put here or there, what syntax to use for ECDSA signatures, etc etc ad nauseum. None of this would matter any more. The new-style txid would stay the same.

Validating nodes would need to do a re-indexing of their UTXO database as the switch moment approached, re-labelling all entries as "outpoint #n of [new-style txid for that tx]" rather than "outpoint #n of [old-style txid for that tx]", in order to be ready to do quick lookups from the switch moment onwards. However, this is a purely private matter for each node, to help with its efficiency. Publicly, the stream of new transactions and blocks would simply, seamlessly, switch to using the new-style txids.

Does this break anything?

Yes it is empirically the case.  A node will become aware of both copies of the transaction.  If you create a given tx (assuming it is otherwise valid) the tx or a copy of it will eventually be confirmed and an attacker can't use this to block transactions, freeze transactions, or destroy transactions.  No core element of a tx can be changed (the inputs used, the number of outputs, the address (well PubKeyHash) of each output, any part of the output script, the value of each output, or the tx fee).

Right now the bitcoin client will display both copies although that is more a reporting issue than an issue with the network itself.  There are pull requests being considered to handle this in a more logical manner (only show one copy of duplicates to the user, only include one copy in the wallet balance).




Then you should have no issue with the issue of broken unconfirmed change outputs.   There are pull requests being considered which will give you the ability to require 1 (or more) confirmations on change before spending in order to avoid even accidentally spending unconfirmed change.  Once confirmed the tx id is immutable baring a re-org of the network.

Thanks for the input.  Are you quite sure that that is empirically the case, or is it more theoretical?  (That is, transactions work as always whether attacked or not, but one must rely on confirmation rather than transaction hash?)

For my part, I rarely make more than one spend per block cycle.  I'd be totally fine not spending unconfirmed outputs and would be totally fine doing my planning to adhere to such a policy.  I typically only make a handful of transactions per month (if that)  and feel pretty guilty about every spend I make since they are highly subsidized.  I voluntarily pay an unusually high transaction fee.

I'd be delighted to do a bulk of my petty spending work in an off-chain solutions which avoided spamming the global block-chain.  As soon as one which is reliable and trustworthy appears, I'll jump eeen it!

The script being modified is the input script.  It contains the signature and thus the entire input script can't be signed (a signature can't be an input for its own signature).  

There are lots of ways they input side of the tx can be modified in such a way which doesn't change the inputs or outputs but does result in a slightly "different" tx and when that is hashed produces a slightly different hash.

A concrete example might help:

ECDSA signatures require a random nonce (S) for security.   If you remember the talk about broken RNG and stolen bitcoins this was because a few wallets reused the same S on mutiple tx and this allows one to compute the private key used for signing.  The pubkey, signature (R) and nonce (S) are stored in the input script for later verification.

ECDSA has a property that for a given payload and private key both S and -S will produce the same signature.  Thus an attacker could take any tx and invert the sign of S and the signature will still verify. This isn't unique to Bitcoin, it is true of any application using ECDSA.   The problem becomes that the "same" tx using S and -S will produce different tx hashes.  Same signature, different hashes.

To prevent mutability of the tx hash requires creating new rules for Bitcoin that limit the scope of a valid transaction.  For example if going forward clients ONLY used an +S value, then -S values could be considered non-standard (and eventually invalid).  This would prevent an attacker from changing the S value to produce the same signature.  Bitcoin would be more restrictive then the underlying ECDSA.  All Bitcoin signatures would be valid ECDSA signatures, but not all valid ECDSA signatures would be valid Bitcoin signatures.

This is just one example there are other elements of the tx protocol which allow similar mutability (without changing the core tx itself, inputs used, outputs used, value to each output, and tx fees).  All of these will have be the restricted to a single valid version to make tx ids immutable.

Sipa has done a lot of good work in outlining the problem and based on what I have read I believe it is only a matter of when not if, tx ids are immutable.


A side note (only read if interested in an alternative).  There is no chance this will be adopted by Bitcoin but it would be a cleaner change which makes sense if starting from a blank sheet of paper.

Anyone designing an alternative to Bitcoin would be best served by moving the signature outside of the tx body.  This is how most cryptographic systems work.

So instead of:

an alt-coin could use a more logical structure like:

The Tx body would consist of the header, list of input(s), and list of output(s).   The input would not contain the signature (neither R or S) and wouldn't even need to contain the pubkey (it could be reconstructed from the signature).  If the same format as Bitcoin was used the input would be only (input_txid, input_index).  The entire tx would be hashed.  That is the tx id.  The same hash would be fed to each of the private keys to produce a signature.  The signatures would be appended to the tx body.

To verify a node would take the tx message, remove the signatures (they are just appended after the end of the tx body).  The tx node would hash the tx body (header + input list + output list).  The hash + each signature would be used to reconstruct the public key(s).  The signature(s) would be verified using the tx hash and public key(s).  If the sigantures are valid and the tx is otherwise valid it is now valid.  Tx mutability would not be an issue. [/size]

Before there were griefers on the network mutating transactions it was safe to spend your own unconfirmed change, because you could reasonably assume that you weren't going to invalidate your own transaction.

Now it's no longer safe. because you don't know what version of your transaction is going to make it into the blockchain, therefore any transactions you make that reference  unconfirmed change will fail.

This is bad news for wallets that do not manage their outputs well. I'm interested in seeing how these single-key wallets like blockchain.info are affected. Any wallet that tries to keep its entire balance in a single utxo is going to only be usable for spends once per block.

I don't understand. Isn't the script signed? Or are you talking about something other than the output scripts?