1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <gmaxwell@gmail.com>) id 1Z4Gva-0005AG-9B
for bitcoin-development@lists.sourceforge.net;
Sun, 14 Jun 2015 23:02:58 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.223.178 as permitted sender)
client-ip=209.85.223.178; envelope-from=gmaxwell@gmail.com;
helo=mail-ie0-f178.google.com;
Received: from mail-ie0-f178.google.com ([209.85.223.178])
by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1Z4GvZ-00021N-3I
for bitcoin-development@lists.sourceforge.net;
Sun, 14 Jun 2015 23:02:58 +0000
Received: by iebmu5 with SMTP id mu5so52119683ieb.1
for <bitcoin-development@lists.sourceforge.net>;
Sun, 14 Jun 2015 16:02:51 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.50.4.66 with SMTP id i2mr17367758igi.40.1434322971809; Sun,
14 Jun 2015 16:02:51 -0700 (PDT)
Received: by 10.107.147.213 with HTTP; Sun, 14 Jun 2015 16:02:51 -0700 (PDT)
In-Reply-To: <87k2vhfnx9.fsf@rustcorp.com.au>
References: <87k2vhfnx9.fsf@rustcorp.com.au>
Date: Sun, 14 Jun 2015 23:02:51 +0000
Message-ID: <CAAS2fgRgWZX_O_2O1bgdFd_04xVp5Lnpw4hf=v6RSTXmsbdzPQ@mail.gmail.com>
From: Gregory Maxwell <gmaxwell@gmail.com>
To: Rusty Russell <rusty@rustcorp.com.au>
Content-Type: text/plain; charset=UTF-8
X-Spam-Score: -1.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
(gmaxwell[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
-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: 1Z4GvZ-00021N-3I
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] [RFC] Canonical input and output ordering
in transactions
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: Sun, 14 Jun 2015 23:02:58 -0000
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.
|
