diff options
| author | Kristov Atlas <kristovatlas.lists@gmail.com> | 2015-06-10 19:36:22 -0400 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2015-06-10 23:36:30 +0000 |
| commit | b658fd1044e47f31685d9174dc3aa385dc64496d (patch) | |
| tree | 65f9f209685e04aa4c2942652faeba61ab6e0a8a /7c | |
| parent | 907cc638c40fad6d5415e7875d09434db9b9256d (diff) | |
| download | pi-bitcoindev-b658fd1044e47f31685d9174dc3aa385dc64496d.tar.gz pi-bitcoindev-b658fd1044e47f31685d9174dc3aa385dc64496d.zip | |
Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs
Diffstat (limited to '7c')
| -rw-r--r-- | 7c/16a382a32133f3b289a5c1c0b9660412446cbe | 376 |
1 files changed, 376 insertions, 0 deletions
diff --git a/7c/16a382a32133f3b289a5c1c0b9660412446cbe b/7c/16a382a32133f3b289a5c1c0b9660412446cbe new file mode 100644 index 000000000..759593488 --- /dev/null +++ b/7c/16a382a32133f3b289a5c1c0b9660412446cbe @@ -0,0 +1,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-- + + |