[bitcoin-dev] New BIP: Low S values signatures

[bitcoin-dev] New BIP: Low S values signatures

[Johnson Lau]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

As discussed in the 11 Aug 2016 IRC meeting (https://bitcoincore.org/en/meetings/2016/08/11/#softfork-to-make-low-s-required), a new BIP with implementation is prepared to make low S value signature as a consensus rule:

https://github.com/jl2012/bips/blob/biplows/bip-lows.mediawiki

https://github.com/bitcoin/bitcoin/pull/8514

The softfork is proposed to be deployed with segwit (BIP141), likely in v0.13.1

The text is copied below

  BIP: ?
  Title: Low S values signatures
  Author: Pieter Wuille <pieter.wuille@gmail.com>
          Johnson Lau <jl2012@xbt.hk>
  Status: Draft
  Type: Standards Track
  Created: 2016-08-16

Abstract

This document specifies proposed changes to the Bitcoin transaction validity rules to restrict signatures to using low S values.

Motivation

ECDSA signatures are inherently malleable as taking the negative of the number S inside (modulo the curve order) does not invalidate it. This is a nuisance malleability vector as any relay node on the network may transform the signature, with no access to the relevant private keys required. For non-segregated witness transactions, this malleability will change the txid and invalidate any unconfirmed child transactions. Although the txid of segregated witness (BIP141) transactions is not third party malleable, this malleability vector will change the wtxid and may reduce the efficiency of compact block relay (BIP152).

To fix this malleability, we require that the S value inside ECDSA signatures is at most the curve order divided by 2 (essentially restricting this value to its lower half range). The value S in signatures must be between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive). If S is too high, simply replace it by S' = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 - S.

Specification

Every signature passed to OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG, or OP_CHECKMULTISIGVERIFY, to which ECDSA verification is applied, MUST use a S value between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive) with strict DER encoding (see BIP66).

These operators all perform ECDSA verifications on pubkey/signature pairs, iterating from the top of the stack backwards. For each such verification, if the signature does not pass the IsLowDERSignature check, the entire script evaluates to false immediately. If the signature is valid DER with low S value, but does not pass ECDSA verification, opcode execution continues as it used to, causing opcode execution to stop and push false on the stack (but not immediately fail the script) in some cases, which potentially skips further signatures (and thus does not subject them to IsLowDERSignature).

Deployment

This BIP will be deployed by "version bits" BIP9 using the same parameters for BIP141 and BIP143, with the name "segwit" and using bit 1.

For Bitcoin mainnet, the BIP9 starttime will be midnight TBD UTC (Epoch timestamp TBD) and BIP9 timeout will be midnight TBD UTC (Epoch timestamp TBD).

For Bitcoin testnet, the BIP9 starttime will be midnight 1 May 2016 UTC (Epoch timestamp 1462060800) and BIP9 timeout will be midnight 1 May 2017 UTC (Epoch timestamp 1493596800).

Compatibility

The reference client has produced compatible signatures since v0.9.0, and the requirement to have low S value signatures has been enforced as a relay policy by the reference client since v0.11.1. As of August 2016, very few transactions violating the requirement are being added to the chain. In addition, every non-compliant signature can trivially be converted into a compliant one, so there is no loss of functionality by this requirement. This proposal has the added benefit of reducing transaction malleability.

Implementation

An implementation for the reference client is available at https://github.com/bitcoin/bitcoin/pull/8514

Acknowledgements

This document is extracted from the previous BIP62 proposal which had input from various people.

Copyright

This document is placed in the public domain.

-----BEGIN PGP SIGNATURE-----
Comment: GPGTools - https://gpgtools.org

iQGcBAEBCgAGBQJXsuZLAAoJEO6eVSA0viTSBkIL/RxdKYhfQUcXhWf3wPzJ2rSo
bhxoGOoswf5Npx1ybKvvTRf51IirgO9JkEl8hYfzLr9KSbfTxCKlr2Z/S+snFGDi
Q0bvVPcg8uoK1iBMrFmIqCi/0pW3/lnnpgqt+O5Jup+DfK4S1QbSVNff8uP7ZK9x
NcgXekAbad57JfZ7gki9aERRj4THliTFBlaKkWo4CP+AwCgtKP6BwWvJxnfGpCc5
Esb/7aFvB0OwTWC7bPdS/XSCChxEdK9n5U3LaUH5o1oMQQhaGVHqeR76Wuf2oDvY
YsXX0b1gttpSJhz00ifOhMf7PhFzQuNyI6gM6ee7kMXwHMlrmyvROQh009cUzKeZ
5m7QKiondMsCoyz0zYXncF/MlwoyI7y1M5pQEqF/CHI5yZGu2K3EeDQebEHDzIrd
RyI6j5BbjLQ4w+geswaxzRSJfkoaKTHdh8g49HL7Q7FUj551jExKA8ZM50SbfeRi
T4fAN8BTXWVpfHkeDYdM2fesaqmFuN9wg18/xwTWJA==
=GgxI
-----END PGP SIGNATURE-----

Re: [bitcoin-dev] New BIP: Low S values signatures

[Luke Dashjr]

On Tuesday, August 16, 2016 10:10:01 AM Johnson Lau via bitcoin-dev wrote:
> Specification
> 
> Every signature passed to OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG,
> or OP_CHECKMULTISIGVERIFY, to which ECDSA verification is applied,

Not 20-byte witness v0 programs?

> These operators all perform ECDSA verifications on pubkey/signature pairs,
> iterating from the top of the stack backwards. For each such verification,
> if the signature does not pass the IsLowDERSignature check,

"the IsLowDERSignature check" is not well-defined. Probably intend to 
reference the previous paragraph?

Luke

Re: [bitcoin-dev] New BIP: Low S values signatures

[Johnson Lau]

[-- Attachment #1: Type: text/plain, Size: 897 bytes --]



> On August 16, 2016 at 6:20 AM Luke Dashjr <luke@dashjr.org> wrote:
>
>
> On Tuesday, August 16, 2016 10:10:01 AM Johnson Lau via bitcoin-dev wrote:
> > Specification
> >
> > Every signature passed to OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG,
> > or OP_CHECKMULTISIGVERIFY, to which ECDSA verification is applied,
>
> Not 20-byte witness v0 programs?

That's an implicit CHECKSIG. Will clarify.

>
> > These operators all perform ECDSA verifications on pubkey/signature pairs,
> > iterating from the top of the stack backwards. For each such verification,
> > if the signature does not pass the IsLowDERSignature check,
>
> "the IsLowDERSignature check" is not well-defined. Probably intend to
> reference the previous paragraph?

IsLowDERSignature is the function in Bitcoin Core. That's a bit complicated as the real checking function is not directly called. I'll clarify.


>
> Luke

[-- Attachment #2: Type: text/html, Size: 1224 bytes --]

Re: [bitcoin-dev] New BIP: Low S values signatures

[Johnson Lau]

[-- Attachment #1: Type: text/plain, Size: 357 bytes --]

The BIP146 has been updated to include NULLDUMMY* as part of the softfork:

https://github.com/bitcoin/bips/pull/435

NULLDUMMY is a trivial softfork to fix malleability related to the extra stack element consumed by CHECKMULTISIG(VERIFY). It is probably more important than LOW_S since without that an attacker may replace the stack element with any value.

[-- Attachment #2: Type: text/html, Size: 519 bytes --]

Re: [bitcoin-dev] New BIP: Low S values signatures

[Johnson Lau]

https://github.com/bitcoin/bips/pull/441

The BIP146 is revised the second time:

1. NULLDUMMY is removed from BIP146 and becomes another softfork that will implement at the same time as segwit https://github.com/bitcoin/bips/pull/440

2. A new rule, namely NULLFAIL, is added to require empty signature(s) when a CHECK(MULTI)SIG returns a FALSE

3. NULLFAIL will be implemented as a policy rule in 0.13.1. However, the softfork won't be deployed in 0.13.1.

As we discovered some undocumented behavior in LOW_S, we may want to deploy the LOW_S softfork in a later release. The newly added NULLFAIL rules should cover all the special cases. https://github.com/bitcoin/bitcoin/pull/8533#issuecomment-243973512

--------
BIP: 146
  Title: Dealing with signature encoding malleability
  Author: Johnson Lau <jl2012@xbt.hk>
          Pieter Wuille <pieter.wuille@gmail.com>
  Status: Draft
  Type: Standards Track
  Created: 2016-08-16

Abstract

This document specifies proposed changes to the Bitcoin transaction validity rules to fix signature malleability related to ECDSA signature encoding.

Motivation

Signature malleability refers to the ability of any relay node on the network to transform the signature in transactions, with no access to the relevant private keys required. For non-segregated witness transactions, signature malleability will change the txid and invalidate any unconfirmed child transactions. Although the txid of segregated witness (BIP141) transactions is not third party malleable, this malleability vector will change the wtxid and may reduce the efficiency of compact block relay (BIP152).

Since the enforcement of Strict DER signatures (BIP66), there are 2 remaining known sources of malleability in ECDSA signatures:

Inherent ECDSA signature malleability: ECDSA signatures are inherently malleable as taking the negative of the number S inside (modulo the curve order) does not invalidate it.
Malleability of failing signature: If a signature failed to validate in OP_CHECKSIG or OP_CHECKMULTISIG, a FALSE would be returned to the stack and the script evaluation would continue. The failing signature may take any value, as long as it follows all the rules described in BIP66.
This document specifies new rules to fix the aforesaid signature malleability.
Specification

To fix signature malleability, the following new rules are applied:

LOW_S

We require that the S value inside ECDSA signatures is at most the curve order divided by 2 (essentially restricting this value to its lower half range). Every signature passed to OP_CHECKSIG[1], OP_CHECKSIGVERIFY, OP_CHECKMULTISIG, or OP_CHECKMULTISIGVERIFY, to which ECDSA verification is applied, MUST use a S value between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive) with strict DER encoding (see BIP66).

If a signature passing to ECDSA verification does not pass the Low S value check and is not an empty byte array, the entire script evaluates to false immediately.

A high S value in signature could be trivially replaced by S' = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 - S.

NULLFAIL

If an OP_CHECKSIG is trying to return a FALSE value to the stack, we require that the relevant signature must be an empty byte array.

If an OP_CHECKMULTISIG is trying to return a FALSE value to the stack, we require that all signatures passing to this OP_CHECKMULTISIG must be empty byte arrays, even the processing of some signatures might have been skipped due to early termination of the signature verification.

Otherwise, the entire script evaluates to false immediately.

Examples

The following examples combine the LOW_S and NULLFAIL rules.

Notation:

  CO       : curve order = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  HCO      : half curve order = CO / 2 = 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0
  P1, P2   : valid, serialized, public keys
  S1L, S2L : valid low S value signatures using respective keys P1 and P2 (1 ≤ S ≤ HCO)
  S1H, S2H : signatures with high S value (otherwise valid) using respective keys P1 and P2 (HCO < S < CO)
  F        : any BIP66-compliant non-empty byte array but not a valid signature

These scripts will return a TRUE to the stack as before:

  S1L P1 CHECKSIG
  0 S1L S2L 2 P1 P2 2 CHECKMULTISIG

These scripts will return a FALSE to the stack as before:

  0 P1 CHECKSIG
  0 0 0 2 P1 P2 2 CHECKMULTISIG

These previously TRUE scripts will fail immediately under the new rules:

  S1H P1 CHECKSIG
  0 S1H S2L 2 P1 P2 2 CHECKMULTISIG
  0 S1L S2H 2 P1 P2 2 CHECKMULTISIG
  0 S1H S2H 2 P1 P2 2 CHECKMULTISIG
These previously FALSE scripts will fail immediately under the new rules:

  F P1 CHECKSIG
  0 S2L S1L 2 P1 P2 2 CHECKMULTISIG
  0 S1L F   2 P1 P2 2 CHECKMULTISIG
  0 F   S2L 2 P1 P2 2 CHECKMULTISIG
  0 S1L 0   2 P1 P2 2 CHECKMULTISIG
  0 0   S2L 2 P1 P2 2 CHECKMULTISIG
  0 F   0   2 P1 P2 2 CHECKMULTISIG
  0 0   F   2 P1 P2 2 CHECKMULTISIG

Deployment

This BIP will be deployed by "version bits" BIP9. Details TBD.

For Bitcoin mainnet, the BIP9 starttime will be midnight TBD UTC (Epoch timestamp TBD) and BIP9 timeout will be midnight TBD UTC (Epoch timestamp TBD).

For Bitcoin testnet, the BIP9 starttime will be midnight TBD UTC (Epoch timestamp TBD) and BIP9 timeout will be midnight TBD UTC (Epoch timestamp TBD).

Compatibility

The reference client has produced LOW_S compatible signatures since v0.9.0, and the LOW_S rule has been enforced as relay policy by the reference client since v0.11.1. As of August 2016, very few transactions violating the requirement are being added to the chain. For all scriptPubKey types in actual use, non-compliant signatures can trivially be converted into compliant ones, so there is no loss of functionality by these requirements.

Scripts with failing OP_CHECKSIG or OP_CHECKMULTISIG rarely happen on the chain. The NULLFAIL rule has been enforced as relay policy by the reference client since v0.13.1.

Users MUST pay extra attention to these new rules when designing exotic scripts.

Implementation

Implementations for the reference client is available at:

https://github.com/bitcoin/bitcoin/blob/35fe0393f216aa6020fc929272118eade5628636/src/script/interpreter.cpp#L185

and

https://github.com/bitcoin/bitcoin/pull/8634

Footnotes

^ Including pay-to-witness-public-key-hash (P2WPKH) described in BIP141
Acknowledgements

This document is extracted from the previous BIP62 proposal which had input from various people.

Copyright

This document is placed in the public domain.

--------

> On August 17, 2016 at 8:43 AM Johnson Lau via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> The BIP146 has been updated to include NULLDUMMY* as part of the softfork:
> 
> https://github.com/bitcoin/bips/pull/435
> 
> NULLDUMMY is a trivial softfork to fix malleability related to the extra stack element consumed by CHECKMULTISIG(VERIFY). It is probably more important than LOW_S since without that an attacker may replace the stack element with any value.

> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev