There are other forms of mutation involving alterations to the script. There have been proposals to prohibit obviously-mutated scripts (like scripts with a bunch of no-ops stuck on the end), but going beyond the obviously-mutated scripts risks accidentally banning useful scripts or future uses of the script system not currently foreseen.
I don't understand. Isn't the script signed? Or are you talking about something other than the output scripts?
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:
Some stuff here
Inputs (including the signatures crammed in but obviously not signed because that would be impossible)
Some random stuff here
Outputs
Some more random stuff here
an alt-coin could use a more logical structure like:
Tx Body (Tx hash = hash of entire tx body)
------------------------
Tx header
Tx Input(s)
Tx Output(s)
------------------------
Tx Signatures -signatures are not part of tx body, they are simply appended to the tx to allow verification.
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]
