Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.215.68 as permitted sender)
	client-ip=209.85.215.68;
	envelope-from=kristovatlas.lists@gmail.com;
	helo=mail-la0-f68.google.com; 
MIME-Version: 1.0
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: Fri, 12 Jun 2015 17:36:56 -0400
Message-ID: <CAGH37SL06R+=pfqY1aHE1XpE7k6jtJSv+CsNiJ3hec6TZvsGAA@mail.gmail.com>
From: Kristov Atlas <kristovatlas.lists@gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=001a11c36c9647547c051858e806
Cc: Bitcoin development mailing list
	<bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Lexicographical Indexing of Transaction
 Inputs and Outputs
Precedence: list

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

Since everyone's busy, I went ahead and made a pull request to add this as
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 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
>

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

<div dir=3D"ltr"><div><div>Since everyone&#39;s busy, I went ahead and made=
 a pull request to add this as an informational BIP 79 to the bips director=
y.<br><br><a href=3D"https://github.com/bitcoin/bips/pull/157">https://gith=
ub.com/bitcoin/bips/pull/157</a><br><br></div>Regards,<br></div>Kristov<br>=
</div><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:pet=
e@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-lef=
t:1px #ccc solid;padding-left:1ex">On Mon, Jun 08, 2015 at 06:53:54PM -0400=
, Kristov Atlas wrote:<br>
<br>
Two other things:<br>
<div><div class=3D"h5"><br>
<br>
<br>
&gt; On Sat, Jun 6, 2015 at 10:35 PM, Peter Todd &lt;<a href=3D"mailto:pete=
@petertodd.org">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 class=3D""><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 class=3D"HOEnZb"><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>

--001a11c36c9647547c051858e806--