* [Bitcoin-development] [RFC] Canonical input and output ordering in transactions
@ 2015-06-06 4:42 Rusty Russell
2015-06-06 4:46 ` Mark Friedenbach
` (2 more replies)
0 siblings, 3 replies; 18+ messages in thread
From: Rusty Russell @ 2015-06-06 4:42 UTC (permalink / raw)
To: Bitcoin Dev
Title: Canonical Input and Output Ordering
Author: Rusty Russell <rusty@rustcorp•com.au>
Discussions-To: "Bitcoin Dev" <bitcoin-development@lists•sourceforge.net>
Status: Draft
Type: Standards Track
Created: 2015-06-06
Abstract
This BIP provides a canonical ordering of inputs and outputs when
creating transactions.
Motivation
Most bitcoin wallet implementations randomize the outputs of
transactions they create to avoid trivial linkage analysis (especially
change outputs), however implementations have made mistakes in this area
in the past.
Using a canonical ordering has the same effect, but is simpler, more
obvious if incorrect, and can eventually be enforced by IsStandard() and
even a soft-fork to enforce it.
Specification
Inputs should be ordered like so:
index (lower value first)
txid (little endian order, lower byte first)
Outputs should be ordered like so:
amount (lower value first)
script (starting from first byte, lower byte first, shorter wins)
Rationale
Any single wallet is already free to implement this, but if other
wallets do not it would reduce privacy by making those transactions
stand out. Thus a BIP is appropriate, especially if this were to
become an IsStandard() rule once widely adopted.
Because integers are fast to compare, they're sorted first, before the
lexographical ordering.
The other input fields do not influence the sort order, as any valid
transactions cannot have two inputs with the same index and txid.
Reference Implementation
https://github.com/rustyrussell/bitcoin/tree/bip-in-out-ordering
^ permalink raw reply [flat|nested] 18+ messages in thread* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-06 4:42 [Bitcoin-development] [RFC] Canonical input and output ordering in transactions Rusty Russell @ 2015-06-06 4:46 ` Mark Friedenbach 2015-06-06 6:44 ` Rusty Russell 2015-06-06 8:24 ` Wladimir J. van der Laan 2015-06-08 21:25 ` Danny Thorpe 2015-06-14 23:02 ` Gregory Maxwell 2 siblings, 2 replies; 18+ messages in thread From: Mark Friedenbach @ 2015-06-06 4:46 UTC (permalink / raw) To: Rusty Russell; +Cc: Bitcoin Development [-- Attachment #1: Type: text/plain, Size: 2199 bytes --] Rusty, this doesn't play well with SIGHASH_SINGLE which is used in assurance contracts among other things. Sometimes the ordering is set by the signing logic itself... On Jun 5, 2015 9:43 PM, "Rusty Russell" <rusty@rustcorp•com.au> wrote: > Title: Canonical Input and Output Ordering > Author: Rusty Russell <rusty@rustcorp•com.au> > Discussions-To: "Bitcoin Dev" <bitcoin-development@lists•sourceforge.net> > Status: Draft > Type: Standards Track > Created: 2015-06-06 > > Abstract > > This BIP provides a canonical ordering of inputs and outputs when > creating transactions. > > Motivation > > Most bitcoin wallet implementations randomize the outputs of > transactions they create to avoid trivial linkage analysis (especially > change outputs), however implementations have made mistakes in this area > in the past. > > Using a canonical ordering has the same effect, but is simpler, more > obvious if incorrect, and can eventually be enforced by IsStandard() and > even a soft-fork to enforce it. > > Specification > > Inputs should be ordered like so: > index (lower value first) > txid (little endian order, lower byte first) > > Outputs should be ordered like so: > amount (lower value first) > script (starting from first byte, lower byte first, shorter wins) > > Rationale > > Any single wallet is already free to implement this, but if other > wallets do not it would reduce privacy by making those transactions > stand out. Thus a BIP is appropriate, especially if this were to > become an IsStandard() rule once widely adopted. > > Because integers are fast to compare, they're sorted first, before the > lexographical ordering. > > The other input fields do not influence the sort order, as any valid > transactions cannot have two inputs with the same index and txid. > > Reference Implementation > > https://github.com/rustyrussell/bitcoin/tree/bip-in-out-ordering > > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 3027 bytes --] ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-06 4:46 ` Mark Friedenbach @ 2015-06-06 6:44 ` Rusty Russell 2015-06-06 8:24 ` Wladimir J. van der Laan 1 sibling, 0 replies; 18+ messages in thread From: Rusty Russell @ 2015-06-06 6:44 UTC (permalink / raw) To: Mark Friedenbach; +Cc: Bitcoin Development Mark Friedenbach <mark@friedenbach•org> writes: > Rusty, this doesn't play well with SIGHASH_SINGLE which is used in > assurance contracts among other things. Sometimes the ordering is set by > the signing logic itself... Ah, I forgot about that particular wart. Yech. Implies that you can order inputs or outputs, not both. Something like "outputs must be in order, inputs which do not CHECK(MULTI)SIG_(VERIFY) a SIGHASH_SINGLE sig must be in order with respect to each other". But that's much less trivial since it implies script evaluation. In other news, I noticed Kristov Atlas's concurrent proposal just after I posted this (via reddit). He used far more words, but didn't note this issue either AFAICT. Thanks! Rusty. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-06 4:46 ` Mark Friedenbach 2015-06-06 6:44 ` Rusty Russell @ 2015-06-06 8:24 ` Wladimir J. van der Laan 2015-06-06 9:45 ` Mark Friedenbach 1 sibling, 1 reply; 18+ messages in thread From: Wladimir J. van der Laan @ 2015-06-06 8:24 UTC (permalink / raw) To: Mark Friedenbach; +Cc: Bitcoin Development On Fri, Jun 05, 2015 at 09:46:17PM -0700, Mark Friedenbach wrote: > Rusty, this doesn't play well with SIGHASH_SINGLE which is used in > assurance contracts among other things. Sometimes the ordering is set by > the signing logic itself... But in that case (unconstrained) randomization can't be used either. This is posed as an alternative to randomization. So in that regard, the proposal still makes sense. I think this move to verifyable, deterministic methods where possible is good. Wladimir ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-06 8:24 ` Wladimir J. van der Laan @ 2015-06-06 9:45 ` Mark Friedenbach 0 siblings, 0 replies; 18+ messages in thread From: Mark Friedenbach @ 2015-06-06 9:45 UTC (permalink / raw) To: Wladimir; +Cc: Bitcoin Development [-- Attachment #1: Type: text/plain, Size: 675 bytes --] Certainly, but I would drop discussion of IsStandard or consensus rules. On Jun 6, 2015 1:24 AM, "Wladimir J. van der Laan" <laanwj@gmail•com> wrote: > On Fri, Jun 05, 2015 at 09:46:17PM -0700, Mark Friedenbach wrote: > > Rusty, this doesn't play well with SIGHASH_SINGLE which is used in > > assurance contracts among other things. Sometimes the ordering is set by > > the signing logic itself... > > But in that case (unconstrained) randomization can't be used either. This > is posed as an alternative to randomization. So in that regard, the > proposal still makes sense. > I think this move to verifyable, deterministic methods where possible is > good. > > Wladimir > [-- Attachment #2: Type: text/html, Size: 954 bytes --] ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-06 4:42 [Bitcoin-development] [RFC] Canonical input and output ordering in transactions Rusty Russell 2015-06-06 4:46 ` Mark Friedenbach @ 2015-06-08 21:25 ` Danny Thorpe 2015-06-08 21:36 ` Peter Todd 2015-06-14 23:04 ` Gregory Maxwell 2015-06-14 23:02 ` Gregory Maxwell 2 siblings, 2 replies; 18+ messages in thread From: Danny Thorpe @ 2015-06-08 21:25 UTC (permalink / raw) To: Rusty Russell; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2589 bytes --] FWIW, The Open Assets colored coin protocol (CoinPrism) places special significance on the zeroth input and the position of the OP_RETURN colored coin marker output to distinguish colored coin issuance outputs from transfer outputs. Reordering the inputs or the outputs breaks the colored coin representation. Recommending sorting of the inputs and outputs as a best practice is fine (and better than random, IMO), but not as part of IsStandard() or consensus rules. There are cases where the order of the inputs and outputs is significant. -Danny On Fri, Jun 5, 2015 at 9:42 PM, Rusty Russell <rusty@rustcorp•com.au> wrote: > Title: Canonical Input and Output Ordering > Author: Rusty Russell <rusty@rustcorp•com.au> > Discussions-To: "Bitcoin Dev" <bitcoin-development@lists•sourceforge.net> > Status: Draft > Type: Standards Track > Created: 2015-06-06 > > Abstract > > This BIP provides a canonical ordering of inputs and outputs when > creating transactions. > > Motivation > > Most bitcoin wallet implementations randomize the outputs of > transactions they create to avoid trivial linkage analysis (especially > change outputs), however implementations have made mistakes in this area > in the past. > > Using a canonical ordering has the same effect, but is simpler, more > obvious if incorrect, and can eventually be enforced by IsStandard() and > even a soft-fork to enforce it. > > Specification > > Inputs should be ordered like so: > index (lower value first) > txid (little endian order, lower byte first) > > Outputs should be ordered like so: > amount (lower value first) > script (starting from first byte, lower byte first, shorter wins) > > Rationale > > Any single wallet is already free to implement this, but if other > wallets do not it would reduce privacy by making those transactions > stand out. Thus a BIP is appropriate, especially if this were to > become an IsStandard() rule once widely adopted. > > Because integers are fast to compare, they're sorted first, before the > lexographical ordering. > > The other input fields do not influence the sort order, as any valid > transactions cannot have two inputs with the same index and txid. > > Reference Implementation > > https://github.com/rustyrussell/bitcoin/tree/bip-in-out-ordering > > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 3512 bytes --] ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-08 21:25 ` Danny Thorpe @ 2015-06-08 21:36 ` Peter Todd 2015-06-14 23:04 ` Gregory Maxwell 1 sibling, 0 replies; 18+ messages in thread From: Peter Todd @ 2015-06-08 21:36 UTC (permalink / raw) To: Danny Thorpe; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 969 bytes --] On Mon, Jun 08, 2015 at 02:25:40PM -0700, Danny Thorpe wrote: > FWIW, The Open Assets colored coin protocol (CoinPrism) places special > significance on the zeroth input and the position of the OP_RETURN colored > coin marker output to distinguish colored coin issuance outputs from > transfer outputs. Reordering the inputs or the outputs breaks the colored > coin representation. > > Recommending sorting of the inputs and outputs as a best practice is fine > (and better than random, IMO), but not as part of IsStandard() or consensus > rules. There are cases where the order of the inputs and outputs is > significant. Timestamping is another case where order matters: if you put the digest in the last vout you can use SHA256 midstate's to reduce the size of the timestamp proof. Anyway, there's no reason to rush re: changes to IsStandard() -- 'peter'[:-1]@petertodd.org 0000000000000000127ab1d576dc851f374424f1269c4700ccaba2c42d97e778 [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 650 bytes --] ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-08 21:25 ` Danny Thorpe 2015-06-08 21:36 ` Peter Todd @ 2015-06-14 23:04 ` Gregory Maxwell 1 sibling, 0 replies; 18+ messages in thread From: Gregory Maxwell @ 2015-06-14 23:04 UTC (permalink / raw) To: Danny Thorpe; +Cc: Bitcoin Dev On Mon, Jun 8, 2015 at 9:25 PM, Danny Thorpe <danny.thorpe@gmail•com> wrote: > Recommending sorting of the inputs and outputs as a best practice is fine > (and better than random, IMO), but not as part of IsStandard() or consensus > rules. There are cases where the order of the inputs and outputs is > significant. Is it your opinion that its fine if the result is that it makes the usage trivially distinguishable e.g. where it might be subjected to higher tx fees, or might break some software which incorrectly expects all transactions to be ordered since most are? ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-06 4:42 [Bitcoin-development] [RFC] Canonical input and output ordering in transactions Rusty Russell 2015-06-06 4:46 ` Mark Friedenbach 2015-06-08 21:25 ` Danny Thorpe @ 2015-06-14 23:02 ` Gregory Maxwell 2015-06-15 2:29 ` Rusty Russell 2015-06-15 4:01 ` [Bitcoin-development] " Kristov Atlas 2 siblings, 2 replies; 18+ messages in thread From: Gregory Maxwell @ 2015-06-14 23:02 UTC (permalink / raw) To: Rusty Russell; +Cc: Bitcoin Dev On Sat, Jun 6, 2015 at 4:42 AM, Rusty Russell <rusty@rustcorp•com.au> wrote: > Title: Canonical Input and Output Ordering > Author: Rusty Russell <rusty@rustcorp•com.au> > Discussions-To: "Bitcoin Dev" <bitcoin-development@lists•sourceforge.net> > Status: Draft > Type: Standards Track > Created: 2015-06-06 > > Abstract > > This BIP provides a canonical ordering of inputs and outputs when > creating transactions. > > Motivation > > Most bitcoin wallet implementations randomize the outputs of > transactions they create to avoid trivial linkage analysis (especially > change outputs), however implementations have made mistakes in this area > in the past. > > Using a canonical ordering has the same effect, but is simpler, more > obvious if incorrect, and can eventually be enforced by IsStandard() and > even a soft-fork to enforce it. > > Specification > > Inputs should be ordered like so: > index (lower value first) > txid (little endian order, lower byte first) > > Outputs should be ordered like so: > amount (lower value first) > script (starting from first byte, lower byte first, shorter wins) > > Rationale > > Any single wallet is already free to implement this, but if other > wallets do not it would reduce privacy by making those transactions > stand out. Thus a BIP is appropriate, especially if this were to > become an IsStandard() rule once widely adopted. > > Because integers are fast to compare, they're sorted first, before the > lexographical ordering. > > The other input fields do not influence the sort order, as any valid > transactions cannot have two inputs with the same index and txid. > > Reference Implementation > > https://github.com/rustyrussell/bitcoin/tree/bip-in-out-ordering Sorry I wasn't a part of the IRC conversation where this was first discussed, though I'm very happy to see a concrete implementation along with the proposal. I'm not a great fan of this proposal for two reasons: The first is that the strict ordering requirements is incompatible with future soft-forks that may expose additional ordering constraints. Today we have _SINGLE, which as noted this interacts with poorly, but there have been other constraints proposed that this would also interact with poorly. The second is that even absent consensus rules there may be invisible constraints in systems-- e.g. hardware wallets that sign top down, or future transaction covenants that have constraints about ordering, or proof systems that use (yuck) midstate compression for efficiency. Right now, with random ordering these applications are fairly indistinguishable from other random uses (since their imposed order could come about by chance) but if everyone else was ordered, even if wasn't enforced.. these would be highly distinguishable. Which would be unfortunate. Worse, if most transactions are ordered the few that aren't could be mishandled (which is, I assume, part of why you propose requiring the ordering-- but I think the soft fork constraints there hurt it more). [Sorry for the delay in stating my views here; I wanted to talk them over with a few other people to see if I was just being stupid and misunderstanding the proposal] I think perhaps the motivations here are understated. We have not seen any massive deployments of accidentally broken ordering that I'm aware of-- and an implementation that got this wrong in a harmful way would likely make far more fatal mistakes (e.g. non random private keys). As an alternative to this proposal the ordering can be privately derandomized in the same way DSA is, to avoid the need for an actual number source. If getting the randomness right were really the only motivation, I'd suggest we propose a simple derandomized randomization algorithm--- e.g. take the order from (H(input ids||client secret)). I think there is actually an unstated motivation also driving this (and the other) proposal related to collaborative transaction systems like coinjoins or micropayment channels; where multiple clients need to agree on the same ordering. Is this the case? If so we should probably talk through some of the requirements there and see if there isn't a better way to address it. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-14 23:02 ` Gregory Maxwell @ 2015-06-15 2:29 ` Rusty Russell 2015-06-15 2:33 ` Gregory Maxwell 2015-06-15 4:01 ` [Bitcoin-development] " Kristov Atlas 1 sibling, 1 reply; 18+ messages in thread From: Rusty Russell @ 2015-06-15 2:29 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev Gregory Maxwell <gmaxwell@gmail•com> writes: > I'm not a great fan of this proposal for two reasons: The first is > that the strict ordering requirements is incompatible with future > soft-forks that may expose additional ordering constraints. Today we > have _SINGLE, which as noted this interacts with poorly, but there > have been other constraints proposed that this would also interact > with poorly. Yes, I hit this when I implemented an IsStandard change; upon input evaluation the scriptsigs which used _SINGLE get disregarded from ordering. > The second is that even absent consensus rules there may be invisible > constraints in systems-- e.g. hardware wallets that sign top down, I think that one's pretty easy to fix (and they should fix it anyway, to avoid leaking information due to ordering): they can receive an unordered tx and sign it as if it were ordered canonically. > or > future transaction covenants that have constraints about ordering, or > proof systems that use (yuck) midstate compression for efficiency. The softfork argument I find the most compelling, though it's tempting to argue that every ordering use (including SIGHASH_SINGLE) is likely a mistake. > I think perhaps the motivations here are understated. We have not seen > any massive deployments of accidentally broken ordering that I'm aware > of-- and an implementation that got this wrong in a harmful way would > likely make far more fatal mistakes (e.g. non random private keys). I was prompted to propose something by this: https://blog.blocktrail.com/2015/05/getting-your-change-in-order/ If that's the only one though, it's less compelling. > As an alternative to this proposal the ordering can be privately > derandomized in the same way DSA is, to avoid the need for an actual > number source. If getting the randomness right were really the only > motivation, I'd suggest we propose a simple derandomized randomization > algorithm--- e.g. take the order from (H(input ids||client secret)). > > I think there is actually an unstated motivation also driving this > (and the other) proposal related to collaborative transaction systems > like coinjoins or micropayment channels; where multiple clients need > to agree on the same ordering. Is this the case? If so we should > probably talk through some of the requirements there and see if there > isn't a better way to address it. Indeed. I was implementing deterministic permutations for lightning (signature exchange requires both sides agree on ordering). Cheers, Rusty. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-15 2:29 ` Rusty Russell @ 2015-06-15 2:33 ` Gregory Maxwell 2015-06-15 2:47 ` Mark Friedenbach 0 siblings, 1 reply; 18+ messages in thread From: Gregory Maxwell @ 2015-06-15 2:33 UTC (permalink / raw) To: Rusty Russell; +Cc: Bitcoin Dev On Mon, Jun 15, 2015 at 2:29 AM, Rusty Russell <rusty@rustcorp•com.au> wrote: > The softfork argument I find the most compelling, though it's tempting > to argue that every ordering use (including SIGHASH_SINGLE) is likely > a mistake. Oh. Hm. It is the case that the generalized sighash flag design I was thinking about was actually completely neutral about ordering, and yet still replaced SINGLE. I need to think a bit on that. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-15 2:33 ` Gregory Maxwell @ 2015-06-15 2:47 ` Mark Friedenbach 2015-06-15 21:01 ` Rusty Russell 0 siblings, 1 reply; 18+ messages in thread From: Mark Friedenbach @ 2015-06-15 2:47 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 1578 bytes --] There's another important use case which you mentioned Greg, that also requires special exemption: compact commitments via mid-state compression. The use case is an OP_RETURN output sorted last, whose last N bytes are a commitment of some kind. A proof of the commitment can then use mid state compression to elide the beginning of the transaction. How do you make a special exemption for this category of outputs? I can't think of a very clean way of doing so that doesn't require an ugly advertising of sort-order exemptions. The fact that we have two different existing use cases which conflict with soft-fork enforcement, I'm quiet concerned that there are either other things we aren't thinking of or haven't invented yet which would be affected. On Sun, Jun 14, 2015 at 7:33 PM, Gregory Maxwell <gmaxwell@gmail•com> wrote: > On Mon, Jun 15, 2015 at 2:29 AM, Rusty Russell <rusty@rustcorp•com.au> > wrote: > > The softfork argument I find the most compelling, though it's tempting > > to argue that every ordering use (including SIGHASH_SINGLE) is likely > > a mistake. > > Oh. > > Hm. > > It is the case that the generalized sighash flag design I was thinking > about was actually completely neutral about ordering, and yet still > replaced SINGLE. > > I need to think a bit on that. > > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 2305 bytes --] ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-15 2:47 ` Mark Friedenbach @ 2015-06-15 21:01 ` Rusty Russell 2015-06-16 7:10 ` Jorge Timón 0 siblings, 1 reply; 18+ messages in thread From: Rusty Russell @ 2015-06-15 21:01 UTC (permalink / raw) To: Mark Friedenbach, Gregory Maxwell; +Cc: Bitcoin Dev Mark Friedenbach <mark@friedenbach•org> writes: > There's another important use case which you mentioned Greg, that also > requires special exemption: compact commitments via mid-state compression. > > The use case is an OP_RETURN output sorted last, whose last N bytes are a > commitment of some kind. A proof of the commitment can then use mid state > compression to elide the beginning of the transaction. > > How do you make a special exemption for this category of outputs? I can't > think of a very clean way of doing so that doesn't require an ugly > advertising of sort-order exemptions. Yes, we can suit any one use case, but not all of them. For example, outputs shall be sorted by: 1. First byte (or 0 if script is zero length) minus 107. 2. The remainder of the script in lexographical order. This would put OP_RETURN outputs last. Though Peter Todd's more general best-effort language might make more sense. It's not like you can hide an OP_RETURN transaction to make it look like something else, so that transaction not going to be distinguished by non-canonical ordering. Cheers, Rusty. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-15 21:01 ` Rusty Russell @ 2015-06-16 7:10 ` Jorge Timón 2015-06-16 8:06 ` Rusty Russell 0 siblings, 1 reply; 18+ messages in thread From: Jorge Timón @ 2015-06-16 7:10 UTC (permalink / raw) To: Rusty Russell; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 993 bytes --] On Jun 15, 2015 11:43 PM, "Rusty Russell" <rusty@rustcorp•com.au> wrote: > Though Peter Todd's more general best-effort language might make more > sense. It's not like you can hide an OP_RETURN transaction to make it > look like something else, so that transaction not going to be > distinguished by non-canonical ordering. What about commitments that don't use op_return (ie pay2contract commitments)? In any case, if the motivation is ordering in multi-party transactions there should be ways to do it without any consequences for other transaction types' privacy. For example you could have a deterministic method that depends on a random seed all parties in the transaction previously share. That way the ordering is deterministic for all parties involved in the transaction (which can use whatever channel they're using to send the parts to also send this random seed) while at the same time the order looks random (or at least not cannonical in a recognisable way) to everyone else. [-- Attachment #2: Type: text/html, Size: 1185 bytes --] ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-16 7:10 ` Jorge Timón @ 2015-06-16 8:06 ` Rusty Russell [not found] ` <CABm2gDpkwHvrsB8Dh-hsO6H9trcweEX9XGB5Jh5KLPsPY5Z1Sw@mail.gmail.com> 0 siblings, 1 reply; 18+ messages in thread From: Rusty Russell @ 2015-06-16 8:06 UTC (permalink / raw) To: Jorge Timón; +Cc: Bitcoin Dev Jorge Timón <jtimon@jtimon•cc> writes: > On Jun 15, 2015 11:43 PM, "Rusty Russell" <rusty@rustcorp•com.au> wrote: > >> Though Peter Todd's more general best-effort language might make more >> sense. It's not like you can hide an OP_RETURN transaction to make it >> look like something else, so that transaction not going to be >> distinguished by non-canonical ordering. > > What about commitments that don't use op_return (ie pay2contract > commitments)? I have no idea what they are? :) > In any case, if the motivation is ordering in multi-party transactions > there should be ways to do it without any consequences for other > transaction types' privacy. For example you could have a deterministic > method that depends on a random seed all parties in the transaction > previously share. That way the ordering is deterministic for all parties > involved in the transaction (which can use whatever channel they're using > to send the parts to also send this random seed) while at the same time the > order looks random (or at least not cannonical in a recognisable way) to > everyone else. Yes, my plan B would be an informational bip with simple code, suggesting a way to permute a transaction based on some secret. No point everyone reinventing the wheel, badly. Cheers, Rusty. ^ permalink raw reply [flat|nested] 18+ messages in thread
[parent not found: <CABm2gDpkwHvrsB8Dh-hsO6H9trcweEX9XGB5Jh5KLPsPY5Z1Sw@mail.gmail.com>]
* [Bitcoin-development] Fwd: Re: [RFC] Canonical input and output ordering in transactions [not found] ` <CABm2gDpkwHvrsB8Dh-hsO6H9trcweEX9XGB5Jh5KLPsPY5Z1Sw@mail.gmail.com> @ 2015-06-21 7:27 ` Jorge Timón 0 siblings, 0 replies; 18+ messages in thread From: Jorge Timón @ 2015-06-21 7:27 UTC (permalink / raw) To: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 1340 bytes --] ---------- Forwarded message ---------- From: "Jorge Timón" <jtimon@jtimon•cc> Date: Jun 17, 2015 6:59 PM Subject: Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions To: "Rusty Russell" <rusty@rustcorp•com.au> Cc: On Tue, Jun 16, 2015 at 10:06 AM, Rusty Russell <rusty@rustcorp•com.au> wrote: > Jorge Timón <jtimon@jtimon•cc> writes: >> On Jun 15, 2015 11:43 PM, "Rusty Russell" <rusty@rustcorp•com.au> wrote: >> >>> Though Peter Todd's more general best-effort language might make more >>> sense. It's not like you can hide an OP_RETURN transaction to make it >>> look like something else, so that transaction not going to be >>> distinguished by non-canonical ordering. >> >> What about commitments that don't use op_return (ie pay2contract >> commitments)? > > I have no idea what they are? :) Here's a short explanation and the code: https://github.com/Blockstream/contracthashtool Here's a longer explanation with a concrete use case (the contract is the invoice): https://www.youtube.com/watch?v=qwyALGlG33Q > Yes, my plan B would be an informational bip with simple code, > suggesting a way to permute a transaction based on some secret. No > point everyone reinventing the wheel, badly. Great. Well, then all I'm saying is that I like this as plan A. [-- Attachment #2: Type: text/html, Size: 2002 bytes --] ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-14 23:02 ` Gregory Maxwell 2015-06-15 2:29 ` Rusty Russell @ 2015-06-15 4:01 ` Kristov Atlas 2015-06-24 22:09 ` [bitcoin-dev] " Kristov Atlas 1 sibling, 1 reply; 18+ messages in thread From: Kristov Atlas @ 2015-06-15 4:01 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2913 bytes --] On Sun, Jun 14, 2015 at 7:02 PM, Gregory Maxwell <gmaxwell@gmail•com> wrote: > I'm not a great fan of this proposal for two reasons: The first is > that the strict ordering requirements is incompatible with future > soft-forks that may expose additional ordering constraints. Today we > have _SINGLE, which as noted this interacts with poorly, but there > have been other constraints proposed that this would also interact > with poorly. > I'm not clear on why this is a problem, so long as the canonical ordering BIP is *optional*. Unless there is a specific plan to soft fork a change that would break the BIP and it is fairly imminent, I see this only as a reason not to integrate it into isStandard(). > The second is that even absent consensus rules there may be invisible > constraints in systems-- e.g. hardware wallets that sign top down, or > future transaction covenants that have constraints about ordering, or > proof systems that use (yuck) midstate compression for efficiency. Right > now, with random ordering these applications are fairly > indistinguishable from other random uses (since their imposed order > could come about by chance) but if everyone else was ordered, even if > wasn't enforced.. these would be highly distinguishable. Which would > be unfortunate. Maybe they shouldn't be doing that. :-P > I think perhaps the motivations here are understated. We have not seen > any massive deployments of accidentally broken ordering that I'm aware > of-- and an implementation that got this wrong in a harmful way would > likely make far more fatal mistakes (e.g. non random private keys). > In my reading of various wallet client sources, it is common that wallet clients will use cryptographically weak sources of randomness to sort outputs -- that is, the ones that actually bother to randomly sort. I can hunt down some examples if this would substantially contribute to the discussion. As an alternative to this proposal the ordering can be privately > derandomized in the same way DSA is, to avoid the need for an actual > number source. If getting the randomness right were really the only > motivation, I'd suggest we propose a simple derandomized randomization > algorithm--- e.g. take the order from (H(input ids||client secret)). > This sounds similar to an idea that Sergio pitched to me privately, which was for wallets to have a private sorting key that they can use to sort inputs and outputs. However, I suspect that adding yet another key which will necessarily require special key rotation rules and maybe special backup procedures will mean that this standard will not be widely adopted any time soon. Ideally, I'd like to see someone write a different BIP with the sorting key idea and let them compete in the wallet client market rather than trying to anticipate what is best for all clients and distilling two good ideas into one artificially. -Kristov [-- Attachment #2: Type: text/html, Size: 3860 bytes --] ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [bitcoin-dev] [Bitcoin-development] [RFC] Canonical input and output ordering in transactions 2015-06-15 4:01 ` [Bitcoin-development] " Kristov Atlas @ 2015-06-24 22:09 ` Kristov Atlas 0 siblings, 0 replies; 18+ messages in thread From: Kristov Atlas @ 2015-06-24 22:09 UTC (permalink / raw) To: Gregory Maxwell; +Cc: bitcoin-dev [-- Attachment #1: Type: text/plain, Size: 6597 bytes --] Following up on this topic... gmaxwell has reserved BIP 69 for my proposal. It has been implemented by Electrum in v2.3.2: https://github.com/spesmilo/electrum/blob/master/RELEASE-NOTES Rusty has kindly tweaked his original canonical ordering proposal implementation for Bitcoin Core's wallet client to fit my proposal: https://github.com/rustyrussell/bitcoin/tree/bip-69 (needs testing) Outstanding objections appear to me to boil down to two points: 1) Some transactions cannot comply with this BIP because there are input and/or put index dependencies. My response: No big deal, it's informational. They simply won't be compliant with the BIP, and that's fine with me. 2) If we set a standard now for transactions that is not apparently random ordering from the perspective of passive blockchain observers, transactions that can't comply with this BIP will stand out. Also, if we change our collective minds in the future about how ordering should be handled, those future transactions would stand out. Therefore, the "safe" course of action is to come up with another scheme that appears to be random ordering from the perspective of a passive blockchain observer. My response: Apparently-random but owner-verifiable ordering is doable. Discussion of this has revolved around what I have called a "sorting key" -- sort lexicographically, and then reorder according to the bits in a sorting key that is impossible to predict by an attacker. This means passive observers cannot determine anything meaningful about the transaction (e.g. which output is change, information leaked based on utxo selection algorithm for inputs, etc.) but the owner of the funds and the sorting key can verify that his transaction matches the canonical specification. Ideally, I think the key should rotate for each transaction to avoid the possibility that a static key can link multiple transactions together. The key should be rotated in such a fashion that the next iteration is not predictable to anyone except the key holder (e.g. put the key through a secure pseudo-random function for each new iteration). This could be done by generating a few bytes of entropy upon wallet creation and keeping track of the current iteration of rotation. HD wallets could derive the initial state of the sorting key by deriving it from the HD seed. There are a variety of schemes that could work here. My main objection to this family of approaches at present is complexity. I suspect that many wallet clients will not want to implement the BIP if they have to maintain a sorting key. A second objection is that no one will be able to detect anomalies in BIP compliance except for the sorting key holder. Most users probably will not bother to verify this. For code reviewers, this means that the sorting key is yet another aspect of the code base that must be scrutinized to ensure it is not being used as a covert channel or has been underhandedly weakened in some fashion. Also, I will mention an ancillary benefit of a non-random canonical ordering: it makes unit testing of transactions for Bitcoin wallets simpler. Given all of the above, I will reiterate my preference to keep the proposal as it is now. The pull request is here: https://github.com/bitcoin/bips/pull/157 If there is market demand for it, a separate sorting key-based proposal could be written which can compete with this BIP and over time successfully deprecate it. I would currently envision that as an HD BIP with a new purpose code. -Kristov On Mon, Jun 15, 2015 at 12:01 AM, Kristov Atlas < kristovatlas.lists@gmail•com> wrote: > On Sun, Jun 14, 2015 at 7:02 PM, Gregory Maxwell <gmaxwell@gmail•com> > wrote: > >> I'm not a great fan of this proposal for two reasons: The first is >> that the strict ordering requirements is incompatible with future >> soft-forks that may expose additional ordering constraints. Today we >> have _SINGLE, which as noted this interacts with poorly, but there >> have been other constraints proposed that this would also interact >> with poorly. >> > > I'm not clear on why this is a problem, so long as the canonical ordering > BIP is *optional*. Unless there is a specific plan to soft fork a change > that would break the BIP and it is fairly imminent, I see this only as a > reason not to integrate it into isStandard(). > > >> The second is that even absent consensus rules there may be invisible >> constraints in systems-- e.g. hardware wallets that sign top down, or >> future transaction covenants that have constraints about ordering, or >> proof systems that use (yuck) midstate compression for efficiency. Right >> now, with random ordering these applications are fairly >> indistinguishable from other random uses (since their imposed order >> could come about by chance) but if everyone else was ordered, even if >> wasn't enforced.. these would be highly distinguishable. Which would >> be unfortunate. > > > Maybe they shouldn't be doing that. :-P > > >> I think perhaps the motivations here are understated. We have not seen >> any massive deployments of accidentally broken ordering that I'm aware >> of-- and an implementation that got this wrong in a harmful way would >> likely make far more fatal mistakes (e.g. non random private keys). >> > > In my reading of various wallet client sources, it is common that wallet > clients will use cryptographically weak sources of randomness to sort > outputs -- that is, the ones that actually bother to randomly sort. I can > hunt down some examples if this would substantially contribute to the > discussion. > > As an alternative to this proposal the ordering can be privately >> derandomized in the same way DSA is, to avoid the need for an actual >> number source. If getting the randomness right were really the only >> motivation, I'd suggest we propose a simple derandomized randomization >> algorithm--- e.g. take the order from (H(input ids||client secret)). >> > > This sounds similar to an idea that Sergio pitched to me privately, which > was for wallets to have a private sorting key that they can use to sort > inputs and outputs. However, I suspect that adding yet another key which > will necessarily require special key rotation rules and maybe special > backup procedures will mean that this standard will not be widely adopted > any time soon. Ideally, I'd like to see someone write a different BIP with > the sorting key idea and let them compete in the wallet client market > rather than trying to anticipate what is best for all clients and > distilling two good ideas into one artificially. > > -Kristov > > [-- Attachment #2: Type: text/html, Size: 8608 bytes --] ^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2015-06-24 22:09 UTC | newest]
Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-06-06 4:42 [Bitcoin-development] [RFC] Canonical input and output ordering in transactions Rusty Russell
2015-06-06 4:46 ` Mark Friedenbach
2015-06-06 6:44 ` Rusty Russell
2015-06-06 8:24 ` Wladimir J. van der Laan
2015-06-06 9:45 ` Mark Friedenbach
2015-06-08 21:25 ` Danny Thorpe
2015-06-08 21:36 ` Peter Todd
2015-06-14 23:04 ` Gregory Maxwell
2015-06-14 23:02 ` Gregory Maxwell
2015-06-15 2:29 ` Rusty Russell
2015-06-15 2:33 ` Gregory Maxwell
2015-06-15 2:47 ` Mark Friedenbach
2015-06-15 21:01 ` Rusty Russell
2015-06-16 7:10 ` Jorge Timón
2015-06-16 8:06 ` Rusty Russell
[not found] ` <CABm2gDpkwHvrsB8Dh-hsO6H9trcweEX9XGB5Jh5KLPsPY5Z1Sw@mail.gmail.com>
2015-06-21 7:27 ` [Bitcoin-development] Fwd: " Jorge Timón
2015-06-15 4:01 ` [Bitcoin-development] " Kristov Atlas
2015-06-24 22:09 ` [bitcoin-dev] " Kristov Atlas
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox