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
271
272
273
274
275
276
277
|
Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <tier.nolan@gmail.com>) id 1Ysb85-0008Nj-Kh
for bitcoin-development@lists.sourceforge.net;
Wed, 13 May 2015 18:11:37 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.192.46 as permitted sender)
client-ip=209.85.192.46; envelope-from=tier.nolan@gmail.com;
helo=mail-qg0-f46.google.com;
Received: from mail-qg0-f46.google.com ([209.85.192.46])
by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1Ysb84-0003DJ-Fc
for bitcoin-development@lists.sourceforge.net;
Wed, 13 May 2015 18:11:37 +0000
Received: by qgfi89 with SMTP id i89so25753682qgf.1
for <bitcoin-development@lists.sourceforge.net>;
Wed, 13 May 2015 11:11:31 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.140.107.165 with SMTP id h34mr196474qgf.63.1431540691058;
Wed, 13 May 2015 11:11:31 -0700 (PDT)
Received: by 10.140.85.241 with HTTP; Wed, 13 May 2015 11:11:30 -0700 (PDT)
In-Reply-To: <CAPg+sBggj382me1ATDx4SS9KHVfvX5KH7ZhLHN6B+2_a+Emw1Q@mail.gmail.com>
References: <CALxbBHUnt7ToVK9reH6W6uT4HV=7NbxGHyNWWa-OEHg+Z1+qOg@mail.gmail.com>
<CAPg+sBggj382me1ATDx4SS9KHVfvX5KH7ZhLHN6B+2_a+Emw1Q@mail.gmail.com>
Date: Wed, 13 May 2015 19:11:30 +0100
Message-ID: <CAE-z3OV1WEDEV+X7gNVx+qBMt4jpSHFKXm3dxUrUyBEJrCNDSQ@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Content-Type: multipart/alternative; boundary=001a1139594e5f62dd0515fa8aae
X-Spam-Score: 2.3 (++)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(tier.nolan[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
1.2 MISSING_HEADERS Missing To: header
1.0 HTML_MESSAGE BODY: HTML included in message
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
1.9 MALFORMED_FREEMAIL Bad headers on message from free email service
-0.2 AWL AWL: Adjusted score from AWL reputation of From: address
X-Headers-End: 1Ysb84-0003DJ-Fc
Subject: Re: [Bitcoin-development] [BIP] Normalized Transaction IDs
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Wed, 13 May 2015 18:11:37 -0000
--001a1139594e5f62dd0515fa8aae
Content-Type: text/plain; charset=UTF-8
On Wed, May 13, 2015 at 6:14 PM, Pieter Wuille <pieter.wuille@gmail.com>
wrote:
> Normalized transaction ids are only effectively non-malleable when all
> inputs they refer to are also non-malleable (or you can have malleability
> in 2nd level dependencies), so I do not believe it makes sense to allow
> mixed usage of the txids at all.
>
The txid or txid-norm is signed, so can't be changed after signing.
The hard fork is to allow transactions to refer to their inputs by txid or
txid-norm. You pick one before signing.
> They do not provide the actual benefit of guaranteed non-malleability
> before it becomes disallowed to use the old mechanism.
>
A signed transaction cannot have its txid changed. It is true that users
of the system would have to use txid-norm.
The basic refund transaction is as follows.
A creates TX1: "Pay w BTC to <B's public key> if signed by A & B"
A creates TX2: "Pay w BTC from TX1-norm to <A's public key>, locked 48
hours in the future, signed by A"
A sends TX2 to B
B signs TX2 and returns to A
A broadcasts TX1. It is mutated before entering the chain to become
TX1-mutated.
A can still submit TX2 to the blockchain, since TX1 and TX1-mutated have
the same txid-norm.
>
> That, together with the +- resource doubling needed for the UTXO set (as
> earlier mentioned) and the fact that an alternative which is only a
> softfork are available, makes this a bad idea IMHO.
>
> Unsure to what extent this has been presented on the mailinglist, but the
> softfork idea is this:
> * Transactions get 2 txids, one used to reference them (computed as
> before), and one used in an (extended) sighash.
> * The txins keep using the normal txid, so not structural changes to
> Bitcoin.
> * The ntxid is computed by replacing the scriptSigs in inputs by the empty
> string, and by replacing the txids in txins by their corresponding ntxids.
> * A new checksig operator is softforked in, which uses the ntxids in its
> sighashes rather than the full txid.
> * To support efficiently computing ntxids, every tx in the utxo set
> (currently around 6M) stores the ntxid, but only supports lookup bu txid
> still.
>
> This does result in a system where a changed dependency indeed invalidates
> the spending transaction, but the fix is trivial and can be done without
> access to the private key.
>
The problem with this is that 2 level malleability is not protected against.
C spends B which spends A.
A is mutated before it hits the chain. The only change in A is in the
scriptSig.
B can be converted to B-new without breaking the signature. This is
because the only change to A was in the sciptSig, which is dropped when
computing the txid-norm.
B-new spends A-mutated. B-new is different from B in a different place.
The txid it uses to refer to the previous output is changed.
The signed transaction C cannot be converted to a valid C-new. The txid of
the input points to B. It is updated to point at B-new. B-new and B don't
have the same txid-norm, since the change is outside the scriptSig. This
means that the signature for C is invalid.
The txid replacements should be done recursively. All input txids should
be replaced by txid-norms when computing the txid-norm for the
transaction. I think this repairs the problem with only allowing one level?
Computing txid-norm:
- replace all txids in inputs with txid-norms of those transactions
- replace all input scriptSigs with empty scripts
- transaction hash is txid-norm for that transaction
The same situation as above is not fatal now.
C spends B which spends A.
A is mutated before it hits the chain. The only change in A is in the
scriptSig.
B can be converted to B-new without breaking the signature. This is
because the only change to A was in the sciptSig, which is dropped when
computing the txid-norm (as before).
B-new spends A mutated. B-new is different from B in for the previous
inputs.
The input for B-new points to A-mutated. When computing the txid-norm,
that would be replaced with the txid-norm for A.
Similarly, the input for B points to A and that would have been replaced
with the txid-norm for A.
This means that B and B-new have the same txid-norm.
The signed transaction C can be converted to a valid C-new. The txid of
the input points to B. It is updated to point at B-new. B-new and B now
have have the same txid-norm and so C is valid.
I think this reasoning is valid, but probably needs writing out actual
serializations.
--001a1139594e5f62dd0515fa8aae
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On W=
ed, May 13, 2015 at 6:14 PM, Pieter Wuille <span dir=3D"ltr"><<a href=3D=
"mailto:pieter.wuille@gmail.com" target=3D"_blank">pieter.wuille@gmail.com<=
/a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:=
0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">=
<p dir=3D"ltr">Normalized transaction ids are only effectively non-malleabl=
e when all inputs they refer to are also non-malleable (or you can have mal=
leability in 2nd level dependencies), so I do not believe it makes sense to=
allow mixed usage of the txids at all.</p></blockquote><div><br></div><div=
>The txid or txid-norm is signed, so can't be changed after signing.=C2=
=A0 <br><br>The hard fork is to allow transactions to refer to their inputs=
by txid or txid-norm.=C2=A0 You pick one before signing.<br></div><div></d=
iv><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bord=
er-left:1px solid rgb(204,204,204);padding-left:1ex"><p dir=3D"ltr"> They d=
o not provide the actual benefit of guaranteed non-malleability before it b=
ecomes disallowed to use the old mechanism.</p></blockquote><div>A signed t=
ransaction cannot have its txid changed.=C2=A0 It is true that users of the=
system would have to use txid-norm.<br><br></div><div>The basic refund tra=
nsaction is as follows.<br></div><div><br></div><div>=C2=A0A creates TX1: &=
quot;Pay w BTC to <B's public key> if signed by A & B"<b=
r>=C2=A0<br>=C2=A0A creates TX2: "Pay w BTC from TX1-norm to <A'=
;s public key>, locked 48 hours in the future, signed by A"<br>=C2=
=A0<br>=C2=A0A sends TX2 to B<br>=C2=A0<br>=C2=A0B signs TX2 and returns to=
A<br><br></div><div>A broadcasts TX1.=C2=A0 It is mutated before entering =
the chain to become TX1-mutated.<br><br></div><div>A can still submit TX2 t=
o the blockchain, since TX1 and TX1-mutated have the same txid-norm.<br></d=
iv>=C2=A0<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex"><p dir=3D"ltr">T=
hat, together with the +- resource doubling needed for the UTXO set (as ear=
lier mentioned) and the fact that an alternative which is only a softfork a=
re available, makes this a bad idea IMHO.</p>
<p dir=3D"ltr">Unsure to what extent this has been presented on the mailing=
list, but the softfork idea is this:<br>
* Transactions get 2 txids, one used to reference them (computed as before)=
, and one used in an (extended) sighash.<br>
* The txins keep using the normal txid, so not structural changes to Bitcoi=
n.<br>
* The ntxid is computed by replacing the scriptSigs in inputs by the empty =
string, and by replacing the txids in txins by their corresponding ntxids.<=
br>
* A new checksig operator is softforked in, which uses the ntxids in its si=
ghashes rather than the full txid.<br>
* To support efficiently computing ntxids, every tx in the utxo set (curren=
tly around 6M) stores the ntxid, but only supports lookup bu txid still.</p=
>
<p dir=3D"ltr">This does result in a system where a changed dependency inde=
ed invalidates the spending transaction, but the fix is trivial and can be =
done without access to the private key.</p></blockquote><div>The problem wi=
th this is that 2 level malleability is not protected against.<br><br></div=
><div>C spends B which spends A.<br></div><br><div></div><div>A is mutated =
before it hits the chain.=C2=A0 The only change in A is in the scriptSig.<b=
r><br>B can be converted to B-new without breaking the signature.=C2=A0 Thi=
s is because the only change to A was in the sciptSig, which is dropped whe=
n computing the txid-norm.<br><br></div><div>B-new spends A-mutated.=C2=A0 =
B-new is different from B in a different place.=C2=A0 The txid it uses to r=
efer to the previous output is changed.<br><br></div><div>The signed transa=
ction C cannot be converted to a valid C-new.=C2=A0 The txid of the input p=
oints to B.=C2=A0 It is updated to point at B-new.=C2=A0 B-new and B don=
9;t have the same txid-norm, since the change is outside the scriptSig.=C2=
=A0 This means that the signature for C is invalid.<br></div><div></div><di=
v><br></div><div>The txid replacements should be done recursively.=C2=A0 Al=
l input txids should be replaced by txid-norms when computing the txid-norm=
for the transaction.=C2=A0 I think this repairs the problem with only allo=
wing one level?<br><br></div><div>Computing txid-norm:<br><br></div><div>- =
replace all txids in inputs with txid-norms of those transactions<br></div>=
<div>- replace all input scriptSigs with empty scripts<br></div><div>- tran=
saction hash is txid-norm for that transaction<br><br></div><div>The same s=
ituation as above is not fatal now.<br><br><div>C spends B which spends A.<=
br></div><br><div>A is mutated before it hits the chain.=C2=A0 The only cha=
nge in A is in the scriptSig.<br><br>B
can be converted to B-new without breaking the signature.=C2=A0 This is=20
because the only change to A was in the sciptSig, which is dropped when=20
computing the txid-norm (as before).<br><br></div><div>B-new spends A mutat=
ed.=C2=A0=20
B-new is different from B in for the previous inputs.=C2=A0 <br><br>The inp=
ut for B-new points to A-mutated.=C2=A0 When computing the txid-norm, that =
would be replaced with the txid-norm for A.<br><br></div><div>Similarly, th=
e input for B points to A and that would have been replaced with the txid-n=
orm for A.<br><br></div><div>This means that B and B-new have the same txid=
-norm.<br></div><div><br></div><div>The signed=20
transaction C can be converted to a valid C-new.=C2=A0 The txid of the
input points to B.=C2=A0 It is updated to point at B-new.=C2=A0 B-new and =
B now have
have the same txid-norm and so C is valid.<br><br></div><div>I think this =
reasoning is valid, but probably needs writing out actual serializations.<b=
r></div></div></div></div></div>
--001a1139594e5f62dd0515fa8aae--
|