Topic: Suggestion for merchants accepting 0 confirmations (Read 1340 times)

OK, so an attacked can watch for my trying to pay a merchant, and every time he sees my transaction, he can replace the (r,s) signature with (r,-s) and transmit that new transaction.  It will have exactly the same inputs and outputs, will be just as valid as my transaction, but will have a different txid and so will appear to the naive merchant as a double spend attack.

Thanks for clearing that up.

No, that's the point:  you can take any validly signed bitcoin transactions, tweak the signature(s) in various ways, and create variations that are also validly signed but have a different txid. We've known that for a long time.

You cannot change where the coins came from or where they go or any other information about the transaction that is covered by the signature(s).

And the current reference bitcoin implementation will simply take the first variation it sees and consider it valid. Sergio is saying that if there are any merchants doing their own double-spend detection they should be aware of this issue.

It sounds to me like Sergio is thinking of a situation where I try to send BTC to a merchant, and as I do so an attacker takes my transaction, somehow changes part of it but leaves my payment going to the merchant, and the merchant rejects it as a double spend, whereas he shouldn't because whichever of the two transactions makes it into the blockchain the merchant still gets my payment.  So it's a denial of service attack, causing the merchant to incorrectly reject my payment.

As for how such an attack would be possible, I guess it would need me to use a specific non-default kind of signature on my inputs.  Maybe some "SIGHASH_ANYONECANPAY" type of signature perhaps, which allows the attacker to add his own tiny input, thus changing the txid.

ECDSA signatures are computed from a partial hash of the transaction, I'll call it the sighash.  One very good reason for this is that the signature needs to be inside the transaction, but isn't known yet.  So, at the very least, the place where the signature will be is replaced with all zeros before computing the sighash.  There are opcodes that can change how the sighashes are made.  For example, SIGHASH_SINGLE signs the input, and just one output, but not the rest of the outputs.

When you compute the signature of that hash, you end up with two numbers, a point on the curve specified as (r,s).  Turns out that the math that verifies the signature doesn't work only on (r,s), but it can also work on (r,(-s mod N)) too, and on several other points.  This property is known as malleability, and is well known for DSAs.  Personally, I had no idea, so I learned something cool today.  This isn't a security problem though, since the points are all related, and none of them can be used to reveal the private key, and none of them can be found without knowing the private key.

I'm not entirely sure here, but I think that what Sergio was getting at was that it would be possible to create a transaction that spends an output using the signature (r,s), and a second one that spends the same output with (r,(-s mod N)).  You feed one to the network, and then the other goes to your target.  Both signatures are valid, so the target sees a legitimate transaction, and the sighashes are the same so the target node won't ask for the network's version of that transaction to compare (because it thinks it already has that transaction).

Remember SIGHASH_SINGLE?  You can use it here to sign just the input and the change coming back to your wallet.  That is what lets you create two different versions with the same signature.  Since only your change is signed, the transaction given to the target has their address in it, but the transaction given to the rest of the world has another address that you control in it.  Since they aren't included in the signature, they can be changed at will.

So, why doesn't it work?

Because transactions are identified by the full hash of the entire transaction, including all signatures, and not by the sighash.  The target transaction signed by (r,(-s mod N)) has a different hash from the (r,s) version, and is therefor a totally different transaction.  The target node will see both versions, and since they spend the same txouts, the double spend attempt will be noticed and rejected.

Also note that wallets keep track of things by looking at the contents of transactions, not by recognizing their hashes.  If you run the same wallet on two computers, when you spend from one computer, the second will recognize the txout in the transaction and mark it off based on that.  (This came up in a different thread.)

Sergio, let me know if I'm off target here.  This is an interesting topic, and I wanted to try to clarify it for the people that have been asking about it.  Obviously, I don't want to be putting words in your mouth if you are talking about something different.

AFAIK, most simply do not bother to detect network mischief at all, outside of what bitcoind protects.  No algorithm.

You cannot defend against the "miner spends, while simultaneously withholding a block containing a double-spend"  This is impossible to detect beforehand with any algorithm.

Merchants simply make a business decision to accept the risk of a double-spend, by (a) being well-connected, and (b) only selling inexpensive items where it is not worth the difficulty of an attack.

Edit: and (c) employing external anti-fraud mechanisms to hopefully select customers less likely to double-spend.

If the signature changed, the txid would change, but that isn't necessarily a double spend.  It's just that there are two different transactions both of which send coins to you.

I'm not sure why the signature would change however.  What's the story there?

Transaction hash is everything you need to verify. If you can create two different transactions with same hash, it means SHA256 and anything depending on it (not only bitcoin) are completely collapsed.

Wouldn't the inverted s signature end up with a different hash?  As in, the txID is the hash of the whole transaction, including the signature, right?  So even if there are two valid signatures, won't they end up with different IDs?

Or am I wrong about that?

I don't know exactly what algorithm currently use merchants that are accepting 0 confirmations.

They may be using this algorithm:

After you receive the transaction tx1 sending X coins to my address:

"If a second transaction tx2 is detected (coming from another peer or a "watch" node)  that spends any of the tx1 inputs and has different hash, then it's a double spend attempt"

This algorithm can fail to some attacks, because of possible signature malleability. A possible correct algorithm would be:

"If a second transaction tx2 is detected (coming from another peer or a "watch" node) that spends any of the tx1 inputs and does not have an output sending X coins to my address , then it's a double spend attempt"

Don't check the remaining outputs nor the transaction hash.

Best regards,
 Sergio.