[Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Kristov Atlas]

[-- Attachment #1: Type: text/plain, Size: 1238 bytes --]

Hello all,

I have written a draft of a BIP to standardize the sorting of tx inputs and
outputs for privacy and security reasons. A few colleagues have reviewed
this and provided feedback privately, but now it's ready for feedback from
a wider audience.

If there is positive sentiment about the proposal after feedback is
integrated, I aim for a bip number to be assigned and have it accepted into
https://github.com/bitcoin/bips

Link:
https://github.com/kristovatlas/rfc/blob/master/bips/bip-li01.mediawiki

For your convenience, here's the abstract:

"Currently there is no standard for bitcoin wallet clients when ordering
transaction inputs and outputs. As a result, wallet clients often have a
discernible blockchain fingerprint, and can leak private information about
their users. By contrast, a standard for non-deterministic sorting could be
difficult to audit. This document proposes deterministic lexicographical
sorting, using hashes of previous transactions and output indices to sort
transaction inputs, as well as value and locking scripts to sort
transaction outputs."

Thanks,

Kristov Atlas
Open Bitcoin Privacy Project Contributor, Blockchain.info Security
Engineer, etc.
Twitter: @kristovatlas
Blog: kristovatlas.com

[-- Attachment #2: Type: text/html, Size: 1592 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Stephen]

[-- Attachment #1: Type: text/plain, Size: 2734 bytes --]

Hi Kristov,

I like the idea. Mainly because having a standard reminds developers to consider this issue. In addition, we would have visibility into the portion of the network that adopts this strategy to enhance privacy. A few points of feedback:

 - I think your explanation of sorting could be significantly shortened and clarified by simply saying that the TXIDs of inputs should be compared as uint256 integers. 
 - The malleability of input TXIDs, as mentioned in the proposal, could cause inputs to be ordered in a non-standard way. Reordering then them would invalidate the signatures (assuming SIGHASH_ALL), so the transaction would be left with improperly ordered inputs. While not a huge issue, it's not ideal. I think the best way to get around this would be to use normalized TXIDs, but you might also be able to sort based on the previous outputs that each of the inputs are spending? These both require information that may not be readily available, however, and use of normalized transaction IDs is not fully developed yet. 

Best,
Stephen 



> On Jun 5, 2015, at 8:12 PM, Kristov Atlas <kristovatlas.lists@gmail.com> wrote:
> 
> Hello all,
> 
> I have written a draft of a BIP to standardize the sorting of tx inputs and outputs for privacy and security reasons. A few colleagues have reviewed this and provided feedback privately, but now it's ready for feedback from a wider audience.
> 
> If there is positive sentiment about the proposal after feedback is integrated, I aim for a bip number to be assigned and have it accepted into https://github.com/bitcoin/bips 
> 
> Link: https://github.com/kristovatlas/rfc/blob/master/bips/bip-li01.mediawiki
> 
> For your convenience, here's the abstract:
> 
> "Currently there is no standard for bitcoin wallet clients when ordering transaction inputs and outputs. As a result, wallet clients often have a discernible blockchain fingerprint, and can leak private information about their users. By contrast, a standard for non-deterministic sorting could be difficult to audit. This document proposes deterministic lexicographical sorting, using hashes of previous transactions and output indices to sort transaction inputs, as well as value and locking scripts to sort transaction outputs."
> 
> Thanks,
> 
> Kristov Atlas
> Open Bitcoin Privacy Project Contributor, Blockchain.info Security Engineer, etc.
> Twitter: @kristovatlas
> Blog: kristovatlas.com
> ------------------------------------------------------------------------------
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[-- Attachment #2: Type: text/html, Size: 3685 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Kristov Atlas]

[-- Attachment #1: Type: text/plain, Size: 998 bytes --]

Hey Stephen,

Thanks for your feedback

On Fri, Jun 5, 2015 at 11:20 PM, Stephen <stephencalebmorse@gmail.com>
wrote:

>  - I think your explanation of sorting could be significantly shortened
> and clarified by simply saying that the TXIDs of inputs should be compared
> as uint256 integers.
>

I considered defining the comparison of txids in terms of integers;
however, I am concerned that this definition may be ambiguous when applied
to a variety of languages and platforms without a similar amount of
explanation as currently exists. For example, if a web wallet uses an API
to receive transaction information, this is traditionally expressed in
terms tx id strings rather than 256-bit integers. My intent is that wallets
can implement the algorithm however they wish, but should ensure that their
output is compliant with the BIP definition. IMHO the algorithm stated in
the BIP should target test cases rather than implementation, and should
leave as little room for ambiguity as possible.

[-- Attachment #2: Type: text/html, Size: 1369 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Kristov Atlas]

[-- Attachment #1: Type: text/plain, Size: 2676 bytes --]

I've updated the draft BIP in two ways:
-Making it clear that sorting is algorithmically agnostic, but should
conform to the output of the example algorithms written in python
-The BIP now handles schemes that create an input/output dependency, such
as SIGHASH_SINGLE:

Handling Input/Output Dependencies

Some uncommon forms of transactions create an ordering dependency between
inputs and outputs of a transaction. Wallets forming these transactions
should first sort inputs according to the methodology outlined in section
“Transaction Inputs” of this BIP. Then, they should fix the output indices
that depend on the input order, and sort the remaining outputs around them.
If there are no outputs that do not depend on input order, then all outputs
will simply be ordered based on the expected scheme. The following are the
known cases of input/output dependency that must be handled specially:

* SIGHASH_SINGLE hash type. [5] Clients seeking to verify LI01 compliance
for a transaction must inspect the last byte of the scriptSig of each input
to determine the signature hash type. In the case of SIGHASH_SINGLE (0x03)
for input “n”, the verifier should expect that output “n” will be fixed
when considering output ordering.

https://github.com/kristovatlas/rfc/blob/master/bips/bip-li01.mediawiki

I'm satisfied with this adjustment, as it is unlikely that any software
that wants to verify compliance with the BIP will not have access to the
scriptSig of each input.

-Kristov

On Sat, Jun 6, 2015 at 2:24 AM, Kristov Atlas <kristovatlas.lists@gmail.com>
wrote:

> Hey Stephen,
>
> Thanks for your feedback
>
> On Fri, Jun 5, 2015 at 11:20 PM, Stephen <stephencalebmorse@gmail.com>
> wrote:
>
>>  - I think your explanation of sorting could be significantly shortened
>> and clarified by simply saying that the TXIDs of inputs should be compared
>> as uint256 integers.
>>
>
> I considered defining the comparison of txids in terms of integers;
> however, I am concerned that this definition may be ambiguous when applied
> to a variety of languages and platforms without a similar amount of
> explanation as currently exists. For example, if a web wallet uses an API
> to receive transaction information, this is traditionally expressed in
> terms tx id strings rather than 256-bit integers. My intent is that wallets
> can implement the algorithm however they wish, but should ensure that their
> output is compliant with the BIP definition. IMHO the algorithm stated in
> the BIP should target test cases rather than implementation, and should
> leave as little room for ambiguity as possible.
>

[-- Attachment #2: Type: text/html, Size: 3472 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 3616 bytes --]

On Sat, Jun 06, 2015 at 08:06:56PM -0400, Kristov Atlas wrote:

In general I think this is a good idea, and should be implemented; we've
had a depressing number of wallets fail to implement randomization
properly, if at all.

> I've updated the draft BIP in two ways:
> -Making it clear that sorting is algorithmically agnostic, but should
> conform to the output of the example algorithms written in python
> -The BIP now handles schemes that create an input/output dependency, such
> as SIGHASH_SINGLE:
> 
> Handling Input/Output Dependencies
> 
> Some uncommon forms of transactions create an ordering dependency between
> inputs and outputs of a transaction. Wallets forming these transactions
> should first sort inputs according to the methodology outlined in section
> “Transaction Inputs” of this BIP. Then, they should fix the output indices
> that depend on the input order, and sort the remaining outputs around them.
> If there are no outputs that do not depend on input order, then all outputs
> will simply be ordered based on the expected scheme. The following are the
> known cases of input/output dependency that must be handled specially:
> 
> * SIGHASH_SINGLE hash type. [5] Clients seeking to verify LI01 compliance
> for a transaction must inspect the last byte of the scriptSig of each input
> to determine the signature hash type. In the case of SIGHASH_SINGLE (0x03)
> for input “n”, the verifier should expect that output “n” will be fixed
> when considering output ordering.

Why mention SIGHASH_SINGLE at all? Its use-case is highly specialized
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 people
will use sighash for smart contract type stuff.

You'd be better off presenting the BIP in terms of a generic statement
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 be
   changed.

As for IsStandard() rules - let alone soft forks - better to leave
discussion of them out for now. In particular, for the soft-fork case
mandating certain transaction orders will very likely cause problems in
the future for future OP_CHECKSIG upgrades. For SIGHASH_ANYONECANPAY, it
might be appropriate for nodes to enforce a certain ordering, but that
can be a separate BIP. (actually implementing that in Bitcoin Core would
be annoying and ugly right now; without replace-by-fee ANYONECANPAY has
a silly DoS attack (adding low-fee inputs) so I can't recommend wallets
use it in the general case yet)

"and a sequence number currently set to 0xFFFFFFFF." <- Actually, this
will be changed in Bitcoin Core as of v0.11.0, which implements
anti-fee-sniping w/ nLockTime.(1) (I need to write up a full BIP
describing it)


Do you have a patch implementing deterministic tx ordering for Bitcoin
Core yet?

1) https://github.com/bitcoin/bitcoin/pull/2340

-- 
'peter'[:-1]@petertodd.org
0000000000000000079693d8d175b476081a04af9c1d00ea2dbe0efb011bd79e

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Kristov Atlas]

[-- Attachment #1: Type: text/plain, Size: 3110 bytes --]

Hey Peter, thanks for your experienced feedback.

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 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 people
> will use sighash for smart contract type stuff.
>
> You'd be better off presenting the BIP in terms of a generic statement
> 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 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 allows
later parties to update the transaction (e.g. using signature hash types
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 transactions or
within the same transaction are covered under the section of this BIP
entitled “Handling Input/Output Dependencies.”"


> As for IsStandard() rules - let alone soft forks - better to leave
> discussion of them out for now. In particular, for the soft-fork case
> mandating certain transaction orders will very likely cause problems in
> the future for future OP_CHECKSIG upgrades. For SIGHASH_ANYONECANPAY, it
> might be appropriate for nodes to enforce a certain ordering, but that
> can be a separate BIP. (actually implementing that in Bitcoin Core would
> be annoying and ugly right now; without replace-by-fee ANYONECANPAY has
> a silly DoS attack (adding low-fee inputs) so I can't recommend wallets
> use it in the general case yet)
>
> "and a sequence number currently set to 0xFFFFFFFF." <- Actually, this
> will be changed in Bitcoin Core as of v0.11.0, which implements
> anti-fee-sniping w/ nLockTime.(1) (I need to write up a full BIP
> describing it)
>

Thanks for the heads-up; removed.


> Do you have a patch implementing deterministic tx ordering for Bitcoin
> 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 will.

-Kristov

[-- Attachment #2: Type: text/html, Size: 4199 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Kristov Atlas]

[-- Attachment #1: Type: text/plain, Size: 233 bytes --]

>
> As for IsStandard() rules - let alone soft forks - better to leave
> discussion of them out for now.


Removed that bit as well.

 Latest version:
https://github.com/kristovatlas/rfc/blob/master/bips/bip-li01.mediawiki

-Kristov

[-- Attachment #2: Type: text/html, Size: 580 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 5189 bytes --]

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 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 people
> > will use sighash for smart contract type stuff.
> >
> > You'd be better off presenting the BIP in terms of a generic statement
> > 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 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 allows
> later parties to update the transaction (e.g. using signature hash types
> 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 transactions or
> within the same transaction are covered under the section of this BIP
> entitled “Handling Input/Output Dependencies.”"

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 Bitcoin
> > 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 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

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Kristov Atlas]

[-- Attachment #1: Type: text/plain, Size: 5676 bytes --]

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 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 people
> > > will use sighash for smart contract type stuff.
> > >
> > > You'd be better off presenting the BIP in terms of a generic statement
> > > 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 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 allows
> > later parties to update the transaction (e.g. using signature hash types
> > 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 transactions
> or
> > within the same transaction are covered under the section of this BIP
> > entitled “Handling Input/Output Dependencies.”"
>
> 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 Bitcoin
> > > 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 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
>

[-- Attachment #2: Type: text/html, Size: 6852 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Kristov Atlas]

[-- Attachment #1: Type: text/plain, Size: 5669 bytes --]

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 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 people
> > > will use sighash for smart contract type stuff.
> > >
> > > You'd be better off presenting the BIP in terms of a generic statement
> > > 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 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 allows
> > later parties to update the transaction (e.g. using signature hash types
> > 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 transactions
> or
> > within the same transaction are covered under the section of this BIP
> > entitled “Handling Input/Output Dependencies.”"
>
> 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 Bitcoin
> > > 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 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
>

[-- Attachment #2: Type: text/html, Size: 6867 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Kristov Atlas]

[-- Attachment #1: Type: text/plain, Size: 6071 bytes --]

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.com
> wrote:

> 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
>> 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 people
>> > > will use sighash for smart contract type stuff.
>> > >
>> > > You'd be better off presenting the BIP in terms of a generic statement
>> > > 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 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 allows
>> > later parties to update the transaction (e.g. using signature hash types
>> > 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
>> transactions or
>> > within the same transaction are covered under the section of this BIP
>> > entitled “Handling Input/Output Dependencies.”"
>>
>> 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 Bitcoin
>> > > 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
>> 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
>>
>
>

[-- Attachment #2: Type: text/html, Size: 7560 bytes --]

Re: [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs

[Rusty Russell]

Kristov Atlas <kristovatlas.lists@gmail.com> writes:
> Hello all,
>
> I have written a draft of a BIP to standardize the sorting of tx inputs and
> outputs for privacy and security reasons. A few colleagues have reviewed
> this and provided feedback privately, but now it's ready for feedback from
> a wider audience.
>
> If there is positive sentiment about the proposal after feedback is
> integrated, I aim for a bip number to be assigned and have it accepted into
> https://github.com/bitcoin/bips

OK, I've modified my implementation to match your proposal:

        https://github.com/rustyrussell/bitcoin/tree/bip-69

It compiles, and is fairly trivial, but will need some testing.

Cheers,
Rusty.