From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 71BE5892 for ; Fri, 2 Sep 2016 08:28:20 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from erelay3.ox.registrar-servers.com (erelay3.ox.registrar-servers.com [192.64.117.2]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 417FCAA for ; Fri, 2 Sep 2016 08:28:18 +0000 (UTC) Received: from localhost (unknown [127.0.0.1]) by erelay1.ox.registrar-servers.com (Postfix) with ESMTP id ED95E22080F4 for ; Fri, 2 Sep 2016 08:28:17 +0000 (UTC) Received: from erelay1.ox.registrar-servers.com ([127.0.0.1]) by localhost (erelay.ox.registrar-servers.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id tkRL1YSbf5yA for ; Fri, 2 Sep 2016 04:28:14 -0400 (EDT) Received: from MTA-10.privateemail.com (unknown [10.20.150.200]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by erelay1.ox.registrar-servers.com (Postfix) with ESMTPS id AE06A22080F9 for ; Fri, 2 Sep 2016 04:28:14 -0400 (EDT) Received: from APP-06 (unknown [10.20.147.156]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by MTA-10.privateemail.com (Postfix) with ESMTPSA id 8525B60038 for ; Fri, 2 Sep 2016 08:28:14 +0000 (UTC) Date: Fri, 2 Sep 2016 04:28:14 -0400 (EDT) From: Johnson Lau Reply-To: Johnson Lau To: Bitcoin Protocol Discussion 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 X-Priority: 3 Importance: Medium X-Mailer: Open-Xchange Mailer v7.8.1-Rev19 X-Originating-Client: open-xchange-appsuite X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] New BIP: Low S values signatures X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 02 Sep 2016 08:28:20 -0000 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 Pieter Wuille 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 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