Date: Fri, 2 Sep 2016 04:28:14 -0400 (EDT)
From: Johnson Lau <jl2012@xbt.hk>
Reply-To: Johnson Lau <jl2012@xbt.hk>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <702023483.65145.1472804894528@privateemail.com>
In-Reply-To: <212784600.96759.1471437827809@privateemail.com>
References: <835406850.86951.1471342201363@privateemail.com>
	<212784600.96759.1471437827809@privateemail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Importance: Medium
Subject: Re: [bitcoin-dev] New BIP: Low S values signatures
Precedence: list

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=C2=A0https://github.com/bitcoin/bips/p=
ull/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 so=
ftfork 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.=C2=A0The newly added NULLFAIL rules=
 should cover all the special cases.=C2=A0https://github.com/bitcoin/bitcoi=
n/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 validit=
y rules to fix signature malleability related to ECDSA signature encoding.

Motivation

Signature malleability refers to the ability of any relay node on the netwo=
rk to transform the signature in transactions, with no access to the releva=
nt private keys required. For non-segregated witness transactions, signatur=
e malleability will change the txid and invalidate any unconfirmed child tr=
ansactions. Although the txid of segregated witness (BIP141) transactions i=
s 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 remaini=
ng known sources of malleability in ECDSA signatures:

Inherent ECDSA signature malleability: ECDSA signatures are inherently mall=
eable 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 th=
e script evaluation would continue. The failing signature may take any valu=
e, as long as it follows all the rules described in BIP66.
This document specifies new rules to fix the aforesaid signature malleabili=
ty.
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 or=
der divided by 2 (essentially restricting this value to its lower half rang=
e). Every signature passed to OP_CHECKSIG[1], OP_CHECKSIGVERIFY, OP_CHECKMU=
LTISIG, or OP_CHECKMULTISIGVERIFY, to which ECDSA verification is applied, =
MUST use a S value between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D=
576E73 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' =3D 0xFFFFFFF=
F FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 - S.

NULLFAIL

If an OP_CHECKSIG is trying to return a FALSE value to the stack, we requir=
e 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 r=
equire that all signatures passing to this OP_CHECKMULTISIG must be empty b=
yte 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 =3D 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6=
 AF48A03B BFD25E8C D0364141
  HCO      : half curve order =3D CO / 2 =3D 0x7FFFFFFF FFFFFFFF FFFFFFFF F=
FFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0
  P1, P2   : valid, serialized, public keys
  S1L, S2L : valid low S value signatures using respective keys P1 and P2 (=
1 =E2=89=A4 S =E2=89=A4 HCO)
  S1H, S2H : signatures with high S value (otherwise valid) using respectiv=
e keys P1 and P2 (HCO < S < CO)
  F        : any BIP66-compliant non-empty byte array but not a valid signa=
ture

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 tim=
estamp TBD) and BIP9 timeout will be midnight TBD UTC (Epoch timestamp TBD)=
.

For Bitcoin testnet, the BIP9 starttime will be midnight TBD UTC (Epoch tim=
estamp 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 clie=
nt since v0.11.1. As of August 2016, very few transactions violating the re=
quirement are being added to the chain. For all scriptPubKey types in actua=
l use, non-compliant signatures can trivially be converted into compliant o=
nes, so there is no loss of functionality by these requirements.

Scripts with failing OP_CHECKSIG or OP_CHECKMULTISIG rarely happen on the c=
hain. 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 scr=
ipts.

Implementation

Implementations for the reference client is available at:

https://github.com/bitcoin/bitcoin/blob/35fe0393f216aa6020fc929272118eade56=
28636/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@li=
sts.linuxfoundation.org> wrote:
>=20
> The BIP146 has been updated to include NULLDUMMY* as part of the softfork=
:
>=20
> https://github.com/bitcoin/bips/pull/435
>=20
> NULLDUMMY is a trivial softfork to fix malleability related to the extra =
stack element consumed by CHECKMULTISIG(VERIFY). It=C2=A0is probably more i=
mportant than LOW_S since without that an attacker may replace the stack el=
ement with any value.

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