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
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <kristovatlas.lists@gmail.com>) id 1Z2pXq-00049d-KQ
for bitcoin-development@lists.sourceforge.net;
Wed, 10 Jun 2015 23:36:30 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.215.65 as permitted sender)
client-ip=209.85.215.65;
envelope-from=kristovatlas.lists@gmail.com;
helo=mail-la0-f65.google.com;
Received: from mail-la0-f65.google.com ([209.85.215.65])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1Z2pXo-0006Iv-Sq
for bitcoin-development@lists.sourceforge.net;
Wed, 10 Jun 2015 23:36:30 +0000
Received: by lams18 with SMTP id s18so6763198lam.2
for <bitcoin-development@lists.sourceforge.net>;
Wed, 10 Jun 2015 16:36:22 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.152.225.166 with SMTP id rl6mr6762036lac.36.1433979382232;
Wed, 10 Jun 2015 16:36:22 -0700 (PDT)
Received: by 10.152.163.98 with HTTP; Wed, 10 Jun 2015 16:36:22 -0700 (PDT)
In-Reply-To: <20150609201436.GD28093@muck>
References: <CAGH37SK0k1YUvadetyHcBGjzW+OHNFRmRwqsUDeHBGejUacigQ@mail.gmail.com>
<44BE16F9-AB24-4A8E-BC7F-03A6C590FCE7@gmail.com>
<CAGH37SL3TA7BXd3Y+4F1Fd5N3ZW+LRLvkfppPsPn61ZVbZJOnQ@mail.gmail.com>
<CAGH37SLCc-aEG0t0H7fsUZOv_h+Fiw4xoonmfwNaFWBin_7HcQ@mail.gmail.com>
<20150607023523.GB1570@savin.petertodd.org>
<CAGH37SLyG-g54-gGU5ZrmQsiogOqWNW1iiayHii1nWiWh+Nk=w@mail.gmail.com>
<20150609201436.GD28093@muck>
Date: Wed, 10 Jun 2015 19:36:22 -0400
Message-ID: <CAGH37SLxDeRQi3_rXc7xWmtaJ5zbz1FtnwwZ_4wCPP-Tugn+NQ@mail.gmail.com>
From: Kristov Atlas <kristovatlas.lists@gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=001a1134986cb17be2051832573b
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
(kristovatlas.lists[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: 1Z2pXo-0006Iv-Sq
Cc: Bitcoin development mailing list
<bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Lexicographical Indexing of Transaction
Inputs and Outputs
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, 10 Jun 2015 23:36:30 -0000
--001a1134986cb17be2051832573b
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Thanks for the feedback. I think I have reflected all of your requested
changes in the latest version, in the BIP and sample code:
https://github.com/kristovatlas/rfc/tree/master/bips
-Kr
On Tue, Jun 9, 2015 at 4:14 PM, Peter Todd <pete@petertodd.org> wrote:
> On Mon, Jun 08, 2015 at 06:53:54PM -0400, Kristov Atlas wrote:
>
> Two other things:
>
>
>
> > On Sat, Jun 6, 2015 at 10:35 PM, Peter Todd <pete@petertodd.org> wrote:
> >
> > > Why mention SIGHASH_SINGLE at all? Its use-case is highly specialized
> > > protocols; you haven't taken into account the needs of those protocol=
s.
> > > For BIP's it's better to stick to the use-cases where the need is cle=
ar
> > > and there exists running code that to speculate too much on future
> uses.
> > > With signature hashing in particular it's not yet clear at all what
> > > future OP_CHECKSIG's will look like, let alone the various ways peopl=
e
> > > will use sighash for smart contract type stuff.
> > >
> > > You'd be better off presenting the BIP in terms of a generic statemen=
t
> > > that "except when otherwise prevented by advanced signature hashing
> > > requirements, wallet software must emit transactions sorted according
> to
> > > the following" You can then specify the two common cases in detail:
> > >
> > > 1) SIGHASH_ALL: input and output order signed, so sort appropriately
> > >
> > > 2) SIGHASH_ANYONECANPAY: input order not signed, so software should
> emit
> > > transactions sorted, recognising that the actual mined order may b=
e
> > > changed.
> > >
> >
> > That makes sense. I updated the language as follows -- your thoughts?
> Keep
> > in mind this BIP is informational, and so people are free to ignore it.
> >
> > "Applicability: This BIP applies to all transactions of signature hash
> type
> > SIGHASH_ALL. Additionally, software compliant with this BIP that allow=
s
> > later parties to update the transaction (e.g. using signature hash type=
s
> > SIGHASH_NONE or a variant of SIGHASH_ANYONECANPAY) should emit
> > lexicographically sorted inputs and outputs, although they may later be
> > modified. Transactions that have index dependencies between transaction=
s
> or
> > within the same transaction are covered under the section of this BIP
> > entitled =E2=80=9CHandling Input/Output Dependencies.=E2=80=9D"
>
> I'd keep it even simpler than that, and just say for now that such
> use-cases are out of the scope of this BIP, however those standards
> should come up with some kind of deterministic standard that meets the
> needs of the protocol. Again, there's a bunch of possible use-cases here
> and we just can't predict them; focus on the fact that the *spirit* of
> what this BIP is about is applicable and future standards should be
> developed.
>
> So I'd change the "Applicability" section to:
>
> This BIP applies to all transactions where the order of inputs and
> outputs does not matter. This is true for the vast majority of
> transactions as they simply move funds from one place to another.
>
> Currently this generally refers to transactions where SIGHASH_ALL is
> used, in which case the signatures commit to the exact order of input
> and outputs. In the case where SIGHASH_ANYONECANPAY and/or SIGHASH_NONE
> has been used (e.g. crowdfunds) the order of inputs and/or outputs may
> not be signed, however compliant software should still emit transactions
> with sorted inputs and outputs, even though they may later be modified
> by others.
>
> In the event that future protocol upgrades introduce new signature hash
> types, compliant software should apply the lexographic ordering
> principle analogously.
>
> While out of scope of this BIP, protocols that do require a specified
> order of inputs/outputs (e.g. due to use of SIGHASH_SINGLE) should
> consider the goals of this BIP and how best to adapt them to the
> specifics needs of those protocols.
>
>
> Then remove the "handling input/output deps" section.
>
> > > Do you have a patch implementing deterministic tx ordering for Bitcoi=
n
> > > Core yet?
> > >
> >
> > I'm not a frequent C programmer, so I'd prefer to let someone else take
> > care of it, as a frequent committer of code would do a faster and more
> > stylistically consistent job of it. If no one else will, however, I wil=
l.
>
>
>
> re: the actual ordering algorithm, having txids be sorted by with the
> hex-based algorithm is odd. I'd simply say they're sorted as
> little-endian byte arrays, or in other words, with the bytearr_cmp()
> function, but with the order of bytes reversed. You also should say that
> we're doing that to make the user see them in visually sorted order to
> match expectations because txids are displayed as little-endian.
>
> For outputs, don't say "locking script", say "scriptPubKey". Secondly,
> scriptPubKeys are not in little-endian representation - they have no
> endianness to them. With output amount, there's no need to say that
> they're unsigned or little-endian satoshies, just say they're sorted
> largest/smallest amount first.
>
> "For the sake of efficiency, amounts will be considered first for
> sorting, since they contain fewer bytes of information (7 bytes)
> compared to a standard P2PKH locking script (800 bytes)." <- where the
> heck did you get these numbers from? Amounts are 8 bytes, and P2PKH
> scriptPubKeys are 25 bytes.
>
>
> "Backwards Compatibility" <- I'd just remove this whole section; we're
> unlikely to make this an IsStandard() rule anytime soon.
>
> --
> 'peter'[:-1]@petertodd.org
> 0000000000000000127ab1d576dc851f374424f1269c4700ccaba2c42d97e778
>
--001a1134986cb17be2051832573b
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Thanks for the feedback. I think I have reflected all=
of your requested changes in the latest version, in the BIP and sample cod=
e:<br><br><a href=3D"https://github.com/kristovatlas/rfc/tree/master/bips">=
https://github.com/kristovatlas/rfc/tree/master/bips</a><br><br></div>-Kr<b=
r></div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Tue, J=
un 9, 2015 at 4:14 PM, Peter Todd <span dir=3D"ltr"><<a href=3D"mailto:p=
ete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>></span> wrot=
e:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-l=
eft:1px #ccc solid;padding-left:1ex">On Mon, Jun 08, 2015 at 06:53:54PM -04=
00, Kristov Atlas wrote:<br>
<br>
Two other things:<br>
<div><div class=3D"h5"><br>
<br>
<br>
> On Sat, Jun 6, 2015 at 10:35 PM, Peter Todd <<a href=3D"mailto:pete=
@petertodd.org">pete@petertodd.org</a>> wrote:<br>
><br>
> > Why mention SIGHASH_SINGLE at all? Its use-case is highly special=
ized<br>
> > protocols; you haven't taken into account the needs of those =
protocols.<br>
> > For BIP's it's better to stick to the use-cases where the=
need is clear<br>
> > and there exists running code that to speculate too much on futur=
e uses.<br>
> > With signature hashing in particular it's not yet clear at al=
l what<br>
> > future OP_CHECKSIG's will look like, let alone the various wa=
ys people<br>
> > will use sighash for smart contract type stuff.<br>
> ><br>
> > You'd be better off presenting the BIP in terms of a generic =
statement<br>
> > that "except when otherwise prevented by advanced signature =
hashing<br>
> > requirements, wallet software must emit transactions sorted accor=
ding to<br>
> > the following" You can then specify the two common cases in =
detail:<br>
> ><br>
> > 1) SIGHASH_ALL: input and output order signed, so sort appropriat=
ely<br>
> ><br>
> > 2) SIGHASH_ANYONECANPAY: input order not signed, so software shou=
ld emit<br>
> >=C2=A0 =C2=A0 transactions sorted, recognising that the actual min=
ed order may be<br>
> >=C2=A0 =C2=A0 changed.<br>
> ><br>
><br>
> That makes sense. I updated the language as follows -- your thoughts? =
Keep<br>
> in mind this BIP is informational, and so people are free to ignore it=
.<br>
><br>
> "Applicability: This BIP applies to all transactions of signature=
hash type<br>
> SIGHASH_ALL. Additionally,=C2=A0 software compliant with this BIP that=
allows<br>
> later parties to update the transaction (e.g. using signature hash typ=
es<br>
> SIGHASH_NONE or a variant of SIGHASH_ANYONECANPAY) should emit<br>
> lexicographically sorted inputs and outputs, although they may later b=
e<br>
> modified. Transactions that have index dependencies between transactio=
ns or<br>
> within the same transaction are covered under the section of this BIP<=
br>
> entitled =E2=80=9CHandling Input/Output Dependencies.=E2=80=9D"<b=
r>
<br>
</div></div>I'd keep it even simpler than that, and just say for now th=
at such<br>
use-cases are out of the scope of this BIP, however those standards<br>
should come up with some kind of deterministic standard that meets the<br>
needs of the protocol. Again, there's a bunch of possible use-cases her=
e<br>
and we just can't predict them; focus on the fact that the *spirit* of<=
br>
what this BIP is about is applicable and future standards should be<br>
developed.<br>
<br>
So I'd change the "Applicability" section to:<br>
<br>
This BIP applies to all transactions where the order of inputs and<br>
outputs does not matter. This is true for the vast majority of<br>
transactions as they simply move funds from one place to another.<br>
<br>
Currently this generally refers to transactions where SIGHASH_ALL is<br>
used, in which case the signatures commit to the exact order of input<br>
and outputs. In the case where SIGHASH_ANYONECANPAY and/or SIGHASH_NONE<br>
has been used (e.g. crowdfunds) the order of inputs and/or outputs may<br>
not be signed, however compliant software should still emit transactions<br=
>
with sorted inputs and outputs, even though they may later be modified<br>
by others.<br>
<br>
In the event that future protocol upgrades introduce new signature hash<br>
types, compliant software should apply the lexographic ordering<br>
principle analogously.<br>
<br>
While out of scope of this BIP, protocols that do require a specified<br>
order of inputs/outputs (e.g. due to use of SIGHASH_SINGLE) should<br>
consider the goals of this BIP and how best to adapt them to the<br>
specifics needs of those protocols.<br>
<br>
<br>
Then remove the "handling input/output deps" section.<br>
<span class=3D""><br>
> > Do you have a patch implementing deterministic tx ordering for Bi=
tcoin<br>
> > Core yet?<br>
> ><br>
><br>
> I'm not a frequent C programmer, so I'd prefer to let someone =
else take<br>
> care of it, as a frequent committer of code would do a faster and more=
<br>
> stylistically consistent job of it. If no one else will, however, I wi=
ll.<br>
<br>
<br>
<br>
</span>re: the actual ordering algorithm, having txids be sorted by with th=
e<br>
hex-based algorithm is odd. I'd simply say they're sorted as<br>
little-endian byte arrays, or in other words, with the bytearr_cmp()<br>
function, but with the order of bytes reversed. You also should say that<br=
>
we're doing that to make the user see them in visually sorted order to<=
br>
match expectations because txids are displayed as little-endian.<br>
<br>
For outputs, don't say "locking script", say "scriptPubK=
ey". Secondly,<br>
scriptPubKeys are not in little-endian representation - they have no<br>
endianness to them. With output amount, there's no need to say that<br>
they're unsigned or little-endian satoshies, just say they're sorte=
d<br>
largest/smallest amount first.<br>
<br>
"For the sake of efficiency, amounts will be considered first for<br>
sorting, since they contain fewer bytes of information (7 bytes)<br>
compared to a standard P2PKH locking script (800 bytes)." <- where =
the<br>
heck did you get these numbers from? Amounts are 8 bytes, and P2PKH<br>
scriptPubKeys are 25 bytes.<br>
<br>
<br>
"Backwards Compatibility" <- I'd just remove this whole se=
ction; we're<br>
unlikely to make this an IsStandard() rule anytime soon.<br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
--<br>
'peter'[:-1]@<a href=3D"http://petertodd.org" target=3D"_blank">pet=
ertodd.org</a><br>
0000000000000000127ab1d576dc851f374424f1269c4700ccaba2c42d97e778<br>
</font></span></blockquote></div><br></div>
--001a1134986cb17be2051832573b--
|