summaryrefslogtreecommitdiff
path: root/4f/4cd4f0b147204b848ea7a0210b3ac2a545e53f
blob: cc21b9a3213aba74126a70f4e440b09990908dba (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
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
	helo=mx.sourceforge.net)
	by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <decker.christian@gmail.com>) id 1YsrHy-0001tS-7Q
	for bitcoin-development@lists.sourceforge.net;
	Thu, 14 May 2015 11:26:54 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.215.54 as permitted sender)
	client-ip=209.85.215.54;
	envelope-from=decker.christian@gmail.com;
	helo=mail-la0-f54.google.com; 
Received: from mail-la0-f54.google.com ([209.85.215.54])
	by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1YsrHv-0001h9-Tk
	for bitcoin-development@lists.sourceforge.net;
	Thu, 14 May 2015 11:26:54 +0000
Received: by labbd9 with SMTP id bd9so62877909lab.2
	for <bitcoin-development@lists.sourceforge.net>;
	Thu, 14 May 2015 04:26:45 -0700 (PDT)
X-Received: by 10.112.189.102 with SMTP id gh6mr2722577lbc.115.1431602805482; 
	Thu, 14 May 2015 04:26:45 -0700 (PDT)
MIME-Version: 1.0
References: <CALxbBHUnt7ToVK9reH6W6uT4HV=7NbxGHyNWWa-OEHg+Z1+qOg@mail.gmail.com>
	<CAPg+sBggj382me1ATDx4SS9KHVfvX5KH7ZhLHN6B+2_a+Emw1Q@mail.gmail.com>
	<CAE-z3OV1WEDEV+X7gNVx+qBMt4jpSHFKXm3dxUrUyBEJrCNDSQ@mail.gmail.com>
	<CAE-z3OU-fdTrKRkni4xmmY5uBVWS0KJ_2NVh6k1tcMSGTPp+4Q@mail.gmail.com>
	<CAPg+sBixpKQfsazHyhiF60HYTk9_U0aBAqU=4P+R+HDMA2jWKg@mail.gmail.com>
	<CAE-z3OU7nCJSGk-Mx_2gmpUjQ1gXeSNDiWfhPe-5rj5bG5ArWQ@mail.gmail.com>
	<CAPg+sBjiaqsLEMz8Qskz1iWOf3VBgAnX2749uHzeyFf_seLEHQ@mail.gmail.com>
	<CALxbBHV_2NHAvS5GXCsqBR0gO9zZe55kz52geMhG+8=EkKN2KA@mail.gmail.com>
In-Reply-To: <CALxbBHV_2NHAvS5GXCsqBR0gO9zZe55kz52geMhG+8=EkKN2KA@mail.gmail.com>
From: Christian Decker <decker.christian@gmail.com>
Date: Thu, 14 May 2015 11:26:44 +0000
Message-ID: <CALxbBHX-Kkfp0wffH4VKCAp6Zp=JkV99m7Yo8yk9AvSS5bUp+g@mail.gmail.com>
To: Pieter Wuille <pieter.wuille@gmail.com>, Tier Nolan <tier.nolan@gmail.com>
Content-Type: multipart/alternative; boundary=001a11c36dc4ae2b9805160900b0
X-Spam-Score: -0.6 (/)
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
	(decker.christian[at]gmail.com)
	-0.0 SPF_PASS               SPF: sender matches SPF record
	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
X-Headers-End: 1YsrHv-0001h9-Tk
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
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: Thu, 14 May 2015 11:26:54 -0000

--001a11c36dc4ae2b9805160900b0
Content-Type: text/plain; charset=UTF-8

Sorry about that, sometimes I hate keyboard shortcuts :-)


Ok, I think I got the OP_CHECKAWESOMESIG proposal, transactions keep
referencing using hashes of complete transactions (including signatures),
while the OP_CHECKAWESOMESIG looks up the previous transaction (which we
already need to do anyway in order to insert the prevOut pubkeyScript),
normalizes the prevout and calculates its normalized transaction ID. It
then inserts the normalized transaction IDs in the OutPoint before
calculating its own hash which is then signed. Is that correct so far?

Let me try to summarize the discussion so far:

I think we have consensus that transaction malleability needs to be
addressed, and normalized transaction IDs seem to be the way to go forward.

The discussion now is how to use normalized transaction IDs and we have two
approaches to implement them:


   - OP_CHECKAWESOMESIG which continues to use the current hashes to
   reference a specific signed instance of a class of semantically identical
   transactions. Internally only the semantic class is enforced. Transactions
   can be fixed to reference the correct signed instance if the transaction
   has been changed along the way.
   - The second proposal advocates using the normalized transaction IDs
   directly in the transactions, requiring no further intervention to fix an
   eventually malleated transaction.

Both approaches have their own advantages and problems:

OP_CHECKAWESOMESIG is a soft-fork which makes it somewhat less problematic
to roll-out and does not break existing software. The normalized
transaction ID can be computed on the fly (possibly increasing lookup
times) or stored alongside the UTXO (increasing storage needs). If the
normalized transaction IDs really need to be recomputed down to the
coinbase then the increased storage is the only option, and would add 32
byte to every transaction metadata in the UTXO.

My proposal is harder to migrate to, as it requires a hardfork, and will
require more storage (64 byte raw data for a normalized to legacy
transaction ID) for every transaction in the UTXO set. At 6 million
distinct transactions which unspent outputs this boils down to 384 MB
(though this may change in future by introducing an aggregation strategy or
fragment further). Some of that space may be reclaimed. There is absolutely
no interaction required to fix up transactions if a dependency has been
malleated, since we address a semantic class, not the specific instance. We
limit the use of normalized transaction IDs to the OutPoint in
transactions, since there we want to reference the semantic class not the
actual signed instance. At protocol message level (inv, getdata) and blocks
we continue to use the legacy ID. This is not as nice as having one ID for
every transaction that is used everywhere.

Both solutions solve malleability, just with different tradeoffs.

I don't see them as mutually exclusive, if we adopt the OP_CHECKAWESOMESIG
as short term fix, that can be rolled out and applied, then my proposal can
be seen as long-term goal that is semantically cleaner and easier to
implement.

Personally I think hard-forks shouldn't be the dreaded boogeyman everybody
makes them out to be, we have never really tested rolling out a hardfork
and they might just turn out to be possible. I don't thing we loose
anything by attempting this, except maybe reduce the urgency to apply some
perfect future thing.

Regards,
Christian

On Thu, May 14, 2015 at 1:01 PM, Christian Decker <
decker.christian@gmail.com> wrote:

> Ok, I think I got the OP_CHECKAWESOMESIG proposal, transactions keep
> referencing using hashes of complete transactions (including signatures),
> while the OP_CHECKAWESOMESIG looks up the previous transaction (which we
> already need to do anyway in order to insert the prevOut pubkeyScript),
> normalizes the prevout and calculates its normalized transaction ID. It
> then inserts the normalized transaction IDs in the OutPoint before
> calculating its own hash which is then signed. Is that correct so far?
>
> Let me try to summarize the discussion so far:
>
> I think we have consensus that transaction malleability needs to be
> addressed, and normalized transaction IDs seem to be the way to go forward.
>
> The discussion now is how to use normalized transaction IDs and we have
> two approaches to implement them:
>
>    - OP_CHECKAWESOMESIG which continues to use the current hashes to
>    reference a specific signed instance of a class of semantically identical
>    transactions. Internally only the semantic class is enforced. Transactions
>    can be fixed to reference the correct signed instance if the transaction
>    has been changed along the way.is a softfork using the "if I don't
>    know this opcode the TX is automatically valid" trick
>
>
> On Thu, May 14, 2015 at 2:40 AM Pieter Wuille <pieter.wuille@gmail.com>
> wrote:
>
>> On Wed, May 13, 2015 at 1:32 PM, Tier Nolan <tier.nolan@gmail.com> wrote:
>>
>>>
>>> On Wed, May 13, 2015 at 9:31 PM, Pieter Wuille <pieter.wuille@gmail.com>
>>> wrote:
>>>
>>>>
>>>> This was what I was suggesting all along, sorry if I wasn't clear.
>>>>
>>>> That's great.  So, basically the multi-level refund problem is solved
>>> by this?
>>>
>>
>> Yes. So to be clear, I think there are 2 desirable end-goal proposals
>> (ignoring difficulty of changing things for a minute):
>>
>> * Transactions and blocks keep referring to other transactions by full
>> txid, but signature hashes are computed off normalized txids (which are
>> recursively defined to use normalized txids all the way back to coinbases).
>> Is this what you are suggesting now as well?
>>
>> * Blocks commit to full transaction data, but transactions and signature
>> hashes use normalized txids.
>>
>> The benefit of the latter solution is that it doesn't need "fixing up"
>> transactions whose inputs have been malleated, but comes at the cost of
>> doing a very invasive hard fork.
>>
>> --
>> Pieter
>>
>>
>> ------------------------------------------------------------------------------
>> One dashboard for servers and applications across Physical-Virtual-Cloud
>> Widest out-of-the-box monitoring support with 50+ applications
>> Performance metrics, stats and reports that give you Actionable Insights
>> Deep dive visibility with transaction tracing using APM Insight.
>> http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>>
>

--001a11c36dc4ae2b9805160900b0
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Sorry about that, sometimes I hate keyboard shortcuts :-)<=
div dir=3D"ltr"><br><br>Ok, I think I got the OP_CHECKAWESOMESIG proposal, =
transactions keep referencing using hashes of complete transactions (includ=
ing signatures), while the OP_CHECKAWESOMESIG looks up the previous transac=
tion (which we already need to do anyway in order to insert the prevOut pub=
keyScript), normalizes the prevout and calculates its normalized transactio=
n ID. It then inserts the normalized transaction IDs in the OutPoint before=
 calculating its own hash which is then signed. Is that correct so far?<br>=
<br>Let me try to summarize the discussion so far:<br><br>I think we have c=
onsensus that transaction malleability needs to be addressed, and normalize=
d transaction IDs seem to be the way to go forward.<br><br>The discussion n=
ow is how to use normalized transaction IDs and we have two approaches to i=
mplement them:<br><br><ul><li>OP_CHECKAWESOMESIG which continues to use the=
 current hashes to reference a specific signed instance of a class of seman=
tically identical transactions. Internally only the semantic class is enfor=
ced. Transactions can be fixed to reference the correct signed instance if =
the transaction has been changed along the way.</li><li>The second proposal=
 advocates using the normalized transaction IDs directly in the transaction=
s, requiring no further intervention to fix an eventually malleated transac=
tion.</li></ul><div>Both approaches have their own advantages and problems:=
=C2=A0</div><div><br></div><div>OP_CHECKAWESOMESIG is a soft-fork which mak=
es it somewhat less problematic to roll-out and does not break existing sof=
tware. The normalized transaction ID can be computed on the fly (possibly i=
ncreasing lookup times) or stored alongside the UTXO (increasing storage ne=
eds). If the normalized transaction IDs really need to be recomputed down t=
o the coinbase then the increased storage is the only option, and would add=
 32 byte to every transaction metadata in the UTXO.</div><div><br></div><di=
v>My proposal is harder to migrate to, as it requires a hardfork, and will =
require more storage (64 byte raw data for a normalized to legacy transacti=
on ID) for every transaction in the UTXO set. At 6 million distinct transac=
tions which unspent outputs this boils down to 384 MB (though this may chan=
ge in future by introducing an aggregation strategy or fragment further). S=
ome of that space may be reclaimed. There is absolutely no interaction requ=
ired to fix up transactions if a dependency has been malleated, since we ad=
dress a semantic class, not the specific instance. We limit the use of norm=
alized transaction IDs to the OutPoint in transactions, since there we want=
 to reference the semantic class not the actual signed instance. At protoco=
l message level (inv, getdata) and blocks we continue to use the legacy ID.=
 This is not as nice as having one ID for every transaction that is used ev=
erywhere.</div><div><br></div><div>Both solutions solve malleability, just =
with different tradeoffs.</div><div><br></div><div>I don&#39;t see them as =
mutually exclusive, if we adopt the OP_CHECKAWESOMESIG as short term fix, t=
hat can be rolled out and applied, then my proposal can be seen as long-ter=
m goal that is semantically cleaner and easier to implement.</div><div><br>=
</div><div>Personally I think hard-forks shouldn&#39;t be the dreaded booge=
yman everybody makes them out to be, we have never really tested rolling ou=
t a hardfork and they might just turn out to be possible. I don&#39;t thing=
 we loose anything by attempting this, except maybe reduce the urgency to a=
pply some perfect future thing.</div><div><br></div><div>Regards,</div><div=
>Christian</div></div><div dir=3D"ltr"><div class=3D"gmail_extra">
<br><div class=3D"gmail_quote">On Thu, May 14, 2015 at 1:01 PM, Christian D=
ecker <span dir=3D"ltr">&lt;<a href=3D"mailto:decker.christian@gmail.com" t=
arget=3D"_blank">decker.christian@gmail.com</a>&gt;</span> wrote:<br><block=
quote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc=
 solid;padding-left:1ex"><div dir=3D"ltr">Ok, I think I got the OP_CHECKAWE=
SOMESIG proposal, transactions keep referencing using hashes of complete tr=
ansactions (including signatures), while the OP_CHECKAWESOMESIG looks up th=
e previous transaction (which we already need to do anyway in order to inse=
rt the prevOut pubkeyScript), normalizes the prevout and calculates its nor=
malized transaction ID. It then inserts the normalized transaction IDs in t=
he OutPoint before calculating its own hash which is then signed. Is that c=
orrect so far?<div><br></div><div>Let me try to summarize the discussion so=
 far:</div><div><br></div><div>I think we have consensus that transaction m=
alleability needs to be addressed, and normalized transaction IDs seem to b=
e the way to go forward.</div><div><br></div><div>The discussion now is how=
 to use normalized transaction IDs and we have two approaches to implement =
them:</div><div><ul><li>OP_CHECKAWESOMESIG which continues to use the curre=
nt hashes to reference a specific signed instance of a class of semanticall=
y identical transactions. Internally only the semantic class is enforced. T=
ransactions can be fixed to reference the correct signed instance if the tr=
ansaction has been changed along the <a href=3D"http://way.is" target=3D"_b=
lank">way.is</a> a softfork using the &quot;if I don&#39;t know this opcode=
 the TX is automatically valid&quot; trick</li></ul></div><div><br><div cla=
ss=3D"gmail_quote"><div><div>On Thu, May 14, 2015 at 2:40 AM Pieter Wuille =
&lt;<a href=3D"mailto:pieter.wuille@gmail.com" target=3D"_blank">pieter.wui=
lle@gmail.com</a>&gt; wrote:<br></div></div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">=
<div><div><div dir=3D"ltr">On Wed, May 13, 2015 at 1:32 PM, Tier Nolan <spa=
n dir=3D"ltr">&lt;<a href=3D"mailto:tier.nolan@gmail.com" target=3D"_blank"=
>tier.nolan@gmail.com</a>&gt;</span> wrote:<br></div><div dir=3D"ltr"><div =
class=3D"gmail_extra"><div class=3D"gmail_quote"><blockquote class=3D"gmail=
_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:=
1ex"><div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_qu=
ote"><span>On Wed, May 13, 2015 at 9:31 PM, Pieter Wuille <span dir=3D"ltr"=
>&lt;<a href=3D"mailto:pieter.wuille@gmail.com" target=3D"_blank">pieter.wu=
ille@gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div=
 dir=3D"ltr"><span></span><div class=3D"gmail_extra"><span></span><br><div =
class=3D"gmail_quote"><div>This was what I was suggesting all along, sorry =
if I wasn&#39;t clear.<span><font color=3D"#888888"><br></font></span><br><=
/div></div></div></div></blockquote></span><div>That&#39;s great.=C2=A0 So,=
 basically the multi-level refund problem is solved by this?<br></div></div=
></div></div></blockquote><div><br></div></div></div></div><div dir=3D"ltr"=
><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div>Yes. So to be c=
lear, I think there are 2 desirable end-goal proposals (ignoring difficulty=
 of changing things for a minute):<br><br></div><div>* Transactions and blo=
cks keep referring to other transactions by full txid, but signature hashes=
 are computed off normalized txids (which are recursively defined to use no=
rmalized txids all the way back to coinbases). Is this what you are suggest=
ing now as well?<br><br></div><div>* Blocks commit to full transaction data=
, but transactions and signature hashes use normalized txids.<br><br></div>=
<div>The benefit of the latter solution is that it doesn&#39;t need &quot;f=
ixing up&quot; transactions whose inputs have been malleated, but comes at =
the cost of doing a very invasive hard fork.<br><br>-- <br></div></div></di=
v></div><div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quo=
te"><div>Pieter<br><br></div></div></div></div></div></div><span>
---------------------------------------------------------------------------=
---<br>
One dashboard for servers and applications across Physical-Virtual-Cloud<br=
>
Widest out-of-the-box monitoring support with 50+ applications<br>
Performance metrics, stats and reports that give you Actionable Insights<br=
>
Deep dive visibility with transaction tracing using APM Insight.<br>
<a href=3D"http://ad.doubleclick.net/ddm/clk/290420510;117567292;y" style=
=3D"display:none!important" target=3D"_blank">http://ad.doubleclick.net/ddm=
/clk/290420510;117567292;y</a>_____________________________________________=
__<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net" target=3D"_bla=
nk">Bitcoin-development@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
</span></blockquote></div></div></div></blockquote></div><br></div></div></=
div>

--001a11c36dc4ae2b9805160900b0--