Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.217.179 as permitted sender)
	client-ip=209.85.217.179;
	envelope-from=kristovatlas.lists@gmail.com;
	helo=mail-lb0-f179.google.com; 
MIME-Version: 1.0
In-Reply-To: <CAGH37SL06R+=pfqY1aHE1XpE7k6jtJSv+CsNiJ3hec6TZvsGAA@mail.gmail.com>
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>
	<CAGH37SL06R+=pfqY1aHE1XpE7k6jtJSv+CsNiJ3hec6TZvsGAA@mail.gmail.com>
Date: Sun, 14 Jun 2015 12:29:37 -0400
Message-ID: <CAGH37S+_6XXpKM5A7FYVtEjABmZ9w_j68Ler8EM7U5=ZXaxouQ@mail.gmail.com>
From: Kristov Atlas <kristovatlas.lists@gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=047d7bf0c7e2eb23bb05187cd809
Cc: Bitcoin development mailing list
	<bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Lexicographical Indexing of Transaction
 Inputs and Outputs
Precedence: list

--047d7bf0c7e2eb23bb05187cd809
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Update: BIP 79 has been implemented in the latest release of Electrum,
v2.3.2:

https://github.com/spesmilo/electrum/blob/master/RELEASE-NOTES

-Kristov

On Fri, Jun 12, 2015 at 5:36 PM, Kristov Atlas <kristovatlas.lists@gmail.co=
m
> wrote:

> Since everyone's busy, I went ahead and made a pull request to add this a=
s
> an informational BIP 79 to the bips directory.
>
> https://github.com/bitcoin/bips/pull/157
>
> Regards,
> Kristov
>
> 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 specialize=
d
>> > > protocols; you haven't taken into account the needs of those
>> protocols.
>> > > For BIP's it's better to stick to the use-cases where the need is
>> clear
>> > > 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 peop=
le
>> > > will use sighash for smart contract type stuff.
>> > >
>> > > You'd be better off presenting the BIP in terms of a generic stateme=
nt
>> > > that "except when otherwise prevented by advanced signature hashing
>> > > requirements, wallet software must emit transactions sorted accordin=
g
>> 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 =
be
>> > >    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 allo=
ws
>> > later parties to update the transaction (e.g. using signature hash typ=
es
>> > SIGHASH_NONE or a variant of SIGHASH_ANYONECANPAY) should emit
>> > lexicographically sorted inputs and outputs, although they may later b=
e
>> > modified. Transactions that have index dependencies between
>> transactions 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 Bitco=
in
>> > > Core yet?
>> > >
>> >
>> > I'm not a frequent C programmer, so I'd prefer to let someone else tak=
e
>> > 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
>> will.
>>
>>
>>
>> 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
>>
>
>

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

<div dir=3D"ltr"><div>Update: BIP 79 has been implemented in the latest rel=
ease of Electrum, v2.3.2: <br><br><a href=3D"https://github.com/spesmilo/el=
ectrum/blob/master/RELEASE-NOTES">https://github.com/spesmilo/electrum/blob=
/master/RELEASE-NOTES</a><br><br></div>-Kristov<br></div><div class=3D"gmai=
l_extra"><br><div class=3D"gmail_quote">On Fri, Jun 12, 2015 at 5:36 PM, Kr=
istov Atlas <span dir=3D"ltr">&lt;<a href=3D"mailto:kristovatlas.lists@gmai=
l.com" target=3D"_blank">kristovatlas.lists@gmail.com</a>&gt;</span> wrote:=
<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-lef=
t:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><div>Since everyon=
e&#39;s busy, I went ahead and made a pull request to add this as an inform=
ational BIP 79 to the bips directory.<br><br><a href=3D"https://github.com/=
bitcoin/bips/pull/157" target=3D"_blank">https://github.com/bitcoin/bips/pu=
ll/157</a><br><br></div>Regards,<br></div>Kristov<br></div><div class=3D"HO=
EnZb"><div class=3D"h5"><div class=3D"gmail_extra"><br><div class=3D"gmail_=
quote">On Tue, Jun 9, 2015 at 4:14 PM, Peter Todd <span dir=3D"ltr">&lt;<a =
href=3D"mailto:pete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>=
&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0=
 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Mon, Jun 08, 2015 a=
t 06:53:54PM -0400, Kristov Atlas wrote:<br>
<br>
Two other things:<br>
<div><div><br>
<br>
<br>
&gt; On Sat, Jun 6, 2015 at 10:35 PM, Peter Todd &lt;<a href=3D"mailto:pete=
@petertodd.org" target=3D"_blank">pete@petertodd.org</a>&gt; wrote:<br>
&gt;<br>
&gt; &gt; Why mention SIGHASH_SINGLE at all? Its use-case is highly special=
ized<br>
&gt; &gt; protocols; you haven&#39;t taken into account the needs of those =
protocols.<br>
&gt; &gt; For BIP&#39;s it&#39;s better to stick to the use-cases where the=
 need is clear<br>
&gt; &gt; and there exists running code that to speculate too much on futur=
e uses.<br>
&gt; &gt; With signature hashing in particular it&#39;s not yet clear at al=
l what<br>
&gt; &gt; future OP_CHECKSIG&#39;s will look like, let alone the various wa=
ys people<br>
&gt; &gt; will use sighash for smart contract type stuff.<br>
&gt; &gt;<br>
&gt; &gt; You&#39;d be better off presenting the BIP in terms of a generic =
statement<br>
&gt; &gt; that &quot;except when otherwise prevented by advanced signature =
hashing<br>
&gt; &gt; requirements, wallet software must emit transactions sorted accor=
ding to<br>
&gt; &gt; the following&quot; You can then specify the two common cases in =
detail:<br>
&gt; &gt;<br>
&gt; &gt; 1) SIGHASH_ALL: input and output order signed, so sort appropriat=
ely<br>
&gt; &gt;<br>
&gt; &gt; 2) SIGHASH_ANYONECANPAY: input order not signed, so software shou=
ld emit<br>
&gt; &gt;=C2=A0 =C2=A0 transactions sorted, recognising that the actual min=
ed order may be<br>
&gt; &gt;=C2=A0 =C2=A0 changed.<br>
&gt; &gt;<br>
&gt;<br>
&gt; That makes sense. I updated the language as follows -- your thoughts? =
Keep<br>
&gt; in mind this BIP is informational, and so people are free to ignore it=
.<br>
&gt;<br>
&gt; &quot;Applicability: This BIP applies to all transactions of signature=
 hash type<br>
&gt; SIGHASH_ALL. Additionally,=C2=A0 software compliant with this BIP that=
 allows<br>
&gt; later parties to update the transaction (e.g. using signature hash typ=
es<br>
&gt; SIGHASH_NONE or a variant of SIGHASH_ANYONECANPAY) should emit<br>
&gt; lexicographically sorted inputs and outputs, although they may later b=
e<br>
&gt; modified. Transactions that have index dependencies between transactio=
ns or<br>
&gt; within the same transaction are covered under the section of this BIP<=
br>
&gt; entitled =E2=80=9CHandling Input/Output Dependencies.=E2=80=9D&quot;<b=
r>
<br>
</div></div>I&#39;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&#39;s a bunch of possible use-cases her=
e<br>
and we just can&#39;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&#39;d change the &quot;Applicability&quot; 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 &quot;handling input/output deps&quot; section.<br>
<span><br>
&gt; &gt; Do you have a patch implementing deterministic tx ordering for Bi=
tcoin<br>
&gt; &gt; Core yet?<br>
&gt; &gt;<br>
&gt;<br>
&gt; I&#39;m not a frequent C programmer, so I&#39;d prefer to let someone =
else take<br>
&gt; care of it, as a frequent committer of code would do a faster and more=
<br>
&gt; 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&#39;d simply say they&#39;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&#39;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&#39;t say &quot;locking script&quot;, say &quot;scriptPubK=
ey&quot;. Secondly,<br>
scriptPubKeys are not in little-endian representation - they have no<br>
endianness to them. With output amount, there&#39;s no need to say that<br>
they&#39;re unsigned or little-endian satoshies, just say they&#39;re sorte=
d<br>
largest/smallest amount first.<br>
<br>
&quot;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).&quot; &lt;- where =
the<br>
heck did you get these numbers from? Amounts are 8 bytes, and P2PKH<br>
scriptPubKeys are 25 bytes.<br>
<br>
<br>
&quot;Backwards Compatibility&quot; &lt;- I&#39;d just remove this whole se=
ction; we&#39;re<br>
unlikely to make this an IsStandard() rule anytime soon.<br>
<span><font color=3D"#888888"><br>
--<br>
&#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org" rel=3D"noreferrer" ta=
rget=3D"_blank">petertodd.org</a><br>
0000000000000000127ab1d576dc851f374424f1269c4700ccaba2c42d97e778<br>
</font></span></blockquote></div><br></div>
</div></div></blockquote></div><br></div>

--047d7bf0c7e2eb23bb05187cd809--