A proposal to permemenantly fixing the malleability problem

[jl2012]

I don't really expect this will be implemented, but I hope people will find this interesting.

Transaction structure is the same but an extra field, txSize, is added. Transaction hash is the hash of everything with scriptSig removed, and this is the hash going to the Merkle Root. As the scriptSig will not go to the Merkle Root, it won't be really recorded in the blockchain. People can freely mutate the scriptSig (even after confirmation). Miners will accept a transaction if they see a valid scriptSig and the transaction size is equal to txSize. This will make sure the block size is not mutable.

Payer could opt to sign the txSize or not.

This could be a hardfork, or a softfork with the auxiliary block: https://bitcointalk.org/index.php?topic=283746.0

Any comment?

[thecomputerscientist]

I don't really expect this will be implemented, but I hope people will find this interesting.

Transaction structure is the same but an extra field, txSize, is added. Transaction hash is the hash of everything with scriptSig removed, and this is the hash going to the Merkle Root. As the scriptSig will not go to the Merkle Root, it won't be really recorded in the blockchain. People can freely mutate the scriptSig (even after confirmation). Miners will accept a transaction if they see a valid scriptSig and the transaction size is equal to txSize. This will make sure the block size is not mutable.

Payer could opt to sign the txSize or not.

This could be a hardfork, or a softfork with the auxiliary block: https://bitcointalk.org/index.php?topic=283746.0

Any comment?

But does this stop malleable transactions? Even if the transaction size is the same you can create malleable transactions by shuffling inputs/outputs around, right?

However, I had an idea last night and just still grabs my head and I need to get this falsified, because it is stupidly simple so I must likely be wrong. So help me out proving this wrong.

First, let's define a total order on all transactions,

Tx(A) < Tx(B)     if     SerializedByteSeq(Tx(A)) < SerializedByteSeq(Tx(B))

Where '<' operator in SerializedByteSeq(X) < SerializedByteSeq(Y) is the lexicographically byte string comparison.
Furthermore, there's always smallest element in this total order. I'm not sure what the smallest possible transaction looks like, but there's definitely one. Note that if two transactions are of equal size (in bytes) we still apply the lexicographic rule ('AA' < 'AB').

Because we have a total order, any subset of Tx(A) < Tx(B) is also a total order.

Now let's consider all possible transactions for a given set of inputs + outputs.
Fixing the inputs and outputs will give us a subset of Tx(A) < Tx(B).
And there must be a smallest possible such transaction (again using the lexicographically definition).

Now for each Bitcoin node in the network, we'll from now on apply this for unconfirmed transactions:

* If we receive a transaction Tx(A) with inputs+outputs IO(Tx(A)) = <{Inputs},{Outputs}>, then if we haven't seen that transaction before then add it to our pool of unconfirmed transactions.
* If we receive a transaction Tx(A) with inputs+outputs IO(Tx(A)) = <{Inputs},{Outputs}> AND we have an existing IO(Tx(B)) = <{Inputs},{Outputs}> (same inputs and outputs) AND Tx(A) < Tx(B), then replace existing Tx(B) with Tx(A). Otherwise we just drop Tx(A).

The only thing an original broadcaster of a transaction needs to do is to pick the smallest (w.r.t. to total order) transaction and it will be impossible for an attacker to create a malleable transaction.

The pros with this solution is:

* It doesn't require any data structure changes
* Nodes can smoothly update to the new version (using the above rules) to gradually block malleable transactions and DoS attempts.
* It's 100% backwards compatible what we have today. I'm not saying that a Tx(B) in Tx(A) < Tx(B) is an invalid transaction, just that Tx(B) has less precedence.

So how hard is it to pick the smallest lexicographically transaction for an original Tx broadcaster?
It shouldn't be that hard. Everything reminds me of how you sign a set of strings in X.509 ceritificates that use ASN.1 DER encoding.
What you normally do (to ensure a unique hash) is to lexicographically sort the strings first. If you look at all the sub-sequences of data in a Tx string, it shouldn't be that hard to prove the best order (at least not for simple transactions).

As this is way too simple, now shoot me in the head and prove me wrong

[jl2012]

Shuffling inputs and outputs will make the signature invalid so this is not malleable

[thecomputerscientist]

Shuffling inputs and outputs will make the signature invalid so this is not malleable

True, and I know what's wrong with my solution (after some discussion on #bitcoin-dev): The final signature by itself is malleable, because for every ECDSA signature (r,s), the signature (r, -s (mod N)) is also a valid signature (of the same message.)

And since you can put a "random" number as a signature, it would be impossible to prove that you'll get the "smallest number" (who knows what kind of mathematical tricks you can pull.)

It's that final signature causing grief and I think it would be very difficult to fix that.

[jl2012]

Another obvious solution is to adopt non-malleable signature, such as Lamport Signature, and close all malleability in scriptSig

[uminatsu]

The final signature by itself is malleable, because for every ECDSA signature (r,s), the signature (r, -s (mod N)) is also a valid signature (of the same message.)

This can be solved by requiring that "s" always be an even number. Since N is odd, only one signature is accepted as canonical.

[thecomputerscientist]

The final signature by itself is malleable, because for every ECDSA signature (r,s), the signature (r, -s (mod N)) is also a valid signature (of the same message.)

This can be solved by requiring that "s" always be an even number. Since N is odd, only one signature is accepted as canonical.

Correct. I found a summary here:

https://gist.github.com/sipa/8907691

If I understand this correctly, (1)-(2) in this list should prevent evil* malleability. (It's only interesting to protect the signature itself, as all the other stuff cannot be modified as that would invalidate the signature.) Can someone confirm this?

*evil = eavesdropping and then modify transaction by someone who does not have access to private key

[thecomputerscientist]

The final signature by itself is malleable, because for every ECDSA signature (r,s), the signature (r, -s (mod N)) is also a valid signature (of the same message.)

This can be solved by requiring that "s" always be an even number. Since N is odd, only one signature is accepted as canonical.

Correct. I found a summary here:

https://gist.github.com/sipa/8907691

If I understand this correctly, (1)-(2) in this list should prevent evil* malleability. (It's only interesting to protect the signature itself, as all the other stuff cannot be modified as that would invalidate the signature.) Can someone confirm this?

*evil = eavesdropping and then modify transaction by someone who does not have access to private key

Ok, got the answers now. So there are two sources of malleability; the signature itself and the scriptSig (there's a scriptSig per input). The scriptSig is not (and cannot be) part of the signature, so you can come up with all kinds of malleability issues here. Therefore, my arguments above are applicable to scriptSig, but it is very important that you can prove you have the "smallest" scriptSig because otherwise an attacker would be able to exploit that. I talked to gmaxwell and (2)-(4) are already deployed since a while back. (5) is checked in but not shipped. So (1) and (6) remain. They are slowly closing the malleability gaps, but it will take some time. Meanwhile, if you're a wallet provider, you should just ensure that malleability is a possibility and write code that is robust enough, i.e. look at the outputs to see if a transaction got through; never use the transaction hash for tracking. 7-8 are not big issues, because they are under the original tx broadcaster's control.