summaryrefslogtreecommitdiff
path: root/59/4db42c6602b3164addd4af59643a71bf5c89b7
blob: 292372a8965f4246a48dcd8d5ef5765056da83b8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
Return-Path: <jl2012@xbt.hk>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 71BE5892
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>; 
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  2 Sep 2016 08:28:14 +0000 (UTC)
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
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <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