Test LowS in standardness, removes nuisance malleability vector. #6769

This adds SCRIPT_VERIFY_LOW_S to STANDARD_SCRIPT_VERIFY_FLAGS which will make the node require the canonical 'low-s' encoding for ECDSA signatures when relaying or mining.

Consensus behavior is unchanged.

The rational is explained in a81cd96805ce6b65cca3a40ebbd3b2eb428abb7b: Absent this kind of test ECDSA is not a strong signature as given a valid signature {r, s} both that value and {r, -s mod n} are valid. These two encodings have different hashes allowing third parties a vector to change users txids. These attacks are avoided by picking a particular form as canonical and rejecting the other form(s); in the of the LOW_S rule, the smaller of the two possible S values is used.

If widely deployed this change would eliminate the last remaining known vector for nuisance malleability on boring SIGHASH_ALL p2pkh transactions. On the down-side it will block most transactions made by sufficiently out of date software.

Unlike the other avenues to change txids on boring transactions this one was randomly violated by all deployed bitcoin software prior to its discovery. So, while other malleability vectors where made non-standard as soon as they were discovered, this one has remained permitted. Even BIP62 did not propose applying this rule to old version transactions, but conforming implementations have become much more common since BIP62 was initially written.

Bitcoin Core has produced compatible signatures since a28fb70e in September 2013, but this didn't make it into a release until 0.9 in March 2014; Bitcoinj has done so for a similar span of time. Bitcoinjs and electrum have been more recently updated.

This does not replace the need for BIP62 or similar, as miners can still cooperate to break transactions. Nor does it replace the need for wallet software to handle malleability sanely[1]. This only eliminates the cheap and irritating DOS attack.

[1] On the Malleability of Bitcoin Transactions Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek http://fc15.ifca.ai/preproceedings/bitcoin/paper_9.pdf

For discussion.

Recent measurements have suggested that somewhere between 85-95% of all transactions are already conforming. I've subsequently gone around and caused several parties (like electrum) to update their behavior.

This could also be coupled with a change that automatically 'fixes' failing transactions by mutating them instead of causing them to be be rejected completely (I understand code for this already exists, but isn't public)-- a prospect which is much less unappealing now that malleability attacks are already going on. However, if LowS becomes even more widespread quickly this change alone may be enough.

If anyone wants to do some sleuthing on which software is still producing HighS signatures, here is a list of addresses recently (but before the recent spate of attacks) involved in a HighS signature: https://people.xiph.org/~greg/high-s-reusecnt.log ...

ACK

I had thought we had switched this on years ago, tbh, and was only corrected a month or so ago. At some point you just have to turn it on given that clients will never otherwise be conformant. Concept ACK.

On October 5, 2015 9:00:23 PM PDT, Patrick Strateman notifications@github.com wrote:

ACK

---

Reply to this email directly or view it on GitHub: #6769 (comment)

ACK

ACK

utACK

should also be backported imo

@btcdrak trivial, of course, though I wonder if we should also backport lowS production to 0.8, I'm kind of disappointed that we didn't previously.

concept ACK, utACK

I wonder if we should also backport lowS production to 0.8

What percentage of nodes are 0.8?

Backporting to 0.10/0.11 is trivial as it already has the SCRIPT_VERIFY_LOW_S flag <=0.9, if still relevant, will also need IsLowDERSignature etc.

ACK, but should be announced with instructions for non-compliant wallets and users whose transactions may be rejected. (but this doesn't seem strictly related the actual PR)

utACK

This could also be coupled with a change that automatically 'fixes' failing transactions by mutating them instead of causing them to be be rejected completely

As that's non-consensus code, I think I'd be willing to ACK such a change in principle. Though I'd want the code to be fairly self-contained, and of course, configurable via CLI switch.

This could also be coupled with a change that automatically 'fixes' failing transactions by mutating them instead of causing them to be be rejected completely

This would also have the behaviour of acting as a nuisance malleability attack on incompatible wallets, but I guess that is better than not being relayed.

NBitcoin is also producing sigs with LowS, we just updated the STANDARD flags to include LowS for transaction verification.

In an observation bracket between height 376000 and 376500 more than 95% of transactions pass the BIP62 stated low-s requirement. This count only includes transactions where every vin is a standard P2SH scriptPubKey, a type which would be made effectively immutable by this modification.

More recent blocks as of the time of writing are affected heavily by mutated signatures, with very large portions of some blocks (60%) containing transactions that have at least one high-s signature.

Historically we see only a few abnormalities per block, some earlier spikes of unknown origin and more recently most recently due to well publicized mutated signatures .

non-canonical-addresses-sorted.txt contains a sample of P2PKH addresses involved in non-mutated transactions where at least one signature violated low-s. This may be useful in identifying services which need to make upgrades to their wallet software in order to produce compliant signatures.

ACK, but should be announced with instructions for non-compliant wallets and users whose transactions may be rejected. (but this doesn't seem strictly related the actual PR)

Should definitely be in the release notes, also for the backport minor releases. But yes no need to have it hold up this PR.

Backported to 0.10 as 1cea6b0dee0b0f10d5f41433e27c70213a4c531f, and to 0.11 as 71cc9d9fe829efd9c9b012c4cd1ece1d988b4869

Probably we should do a new release on both branches soon.

Is there any discussion about making Bitcoin Core malleate HighS sigs to LowS instead of just not relaying them ?

@NicolasDorier I believe some miners are planning on doing this.

@NicolasDorier There seems to be some agreement that its best to not do that by default, but instead to do that temporarily by having devs and miners run a patch to do that on the network first, then slowly transition to making high-S entirely non-standard over time.

would this ever become part of consensus or is it more likely that we'll move torwards the suggested normalized transaction ID ?