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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <ryan@bitpay.com>) id 1WNmg0-0005dF-5G
for bitcoin-development@lists.sourceforge.net;
Wed, 12 Mar 2014 17:10:44 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of bitpay.com
designates 209.85.216.49 as permitted sender)
client-ip=209.85.216.49; envelope-from=ryan@bitpay.com;
helo=mail-qa0-f49.google.com;
Received: from mail-qa0-f49.google.com ([209.85.216.49])
by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1WNmfz-0006SS-FD
for bitcoin-development@lists.sourceforge.net;
Wed, 12 Mar 2014 17:10:44 +0000
Received: by mail-qa0-f49.google.com with SMTP id j7so2763793qaq.8
for <bitcoin-development@lists.sourceforge.net>;
Wed, 12 Mar 2014 10:10:37 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to
:subject:content-type;
bh=bV5/pe/hD43QGw9QLXvPNdszbcAzOkCvFbRvpf02M2o=;
b=DWDX3hsgkXCPckCfJVMhMKPuClNq6stOA9HlpPdNBzbrcu2lx4l4i7ac3Wsk2OHJv8
N8OMDQtNmY1xaNisqLlwHwBPBAusrpop36kB19dYVajHx3dZgy5hXZotGq/QTVqgkRuH
mECoFN9b9I9BLgd0DBU6X4fkYduFA2qgbYiilys4sfrkC3bj6mJigOxbneDsFNSUXV7q
rmQPbDs17mv9Gfd9WitZb9dXYgSfhDUDEJIBZUCHP88pcyWX/vo6K+MjTBU1XtVeOR8Z
Na96bcWFib6NIYkQjNup/gDiq0jXxKRe+n6o3fcxNnTVuwFrbfylRKtl0D9TbhYAcG8g
dPyA==
X-Gm-Message-State: ALoCoQn6Lu51ekWpkNQ/TLWCnJErUhd/YUm+8f9ADmP9pWeO/iQAkqPmRggKE24bgj85e5SHYNAO
X-Received: by 10.140.39.212 with SMTP id v78mr53353697qgv.77.1394644237366;
Wed, 12 Mar 2014 10:10:37 -0700 (PDT)
Received: from rxc-h.local ([72.16.218.22])
by mx.google.com with ESMTPSA id w5sm79822877qat.16.2014.03.12.10.10.36
for <bitcoin-development@lists.sourceforge.net>
(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
Wed, 12 Mar 2014 10:10:36 -0700 (PDT)
Message-ID: <5320950C.5050107@bitpay.com>
Date: Wed, 12 Mar 2014 13:10:36 -0400
From: "Ryan X. Charles" <ryan@bitpay.com>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9;
rv:24.0) Gecko/20100101 Thunderbird/24.3.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
X-Enigmail-Version: 1.6
Content-Type: multipart/mixed; boundary="------------040807090208060101050100"
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 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: 1WNmfz-0006SS-FD
Subject: [Bitcoin-development] sorting public keys for p2sh multisig
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: Wed, 12 Mar 2014 17:10:44 -0000
This is a multi-part message in MIME format.
--------------040807090208060101050100
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
For a p2sh multisig transaction, the serialized script looks like this:
m [pubkey] ... [pubkey] n OP_CHECKMULTISIG
The p2sh address is the hash of this script. The public keys can come in
any order, but the hash depends on the order. If you have a list of
public keys, to which address do you send your money? We need a standard
way of sorting the public keys so that the address generated is always
the same for the same public keys and m.
There are two kinds of public keys: compressed and uncompressed.
Uncompressed are longer than compressed.
There are a few obvious ways we could sort the public keys: as strings,
as big endian numbers, as little endian numbers.
The difference is this. Suppose one public key is 59234 (uncompressed),
and the other is 6903 (compressed). If we sort these as strings, then
6903 > 59234. But if we sort them as big endian numbers, then 6903 is
really 06903, and then 06903 < 59234. So it makes a critical difference.
Sorting as little endian is yet another option that is not the same as
the other two.
I noticed Alan Reiner's comment in an earlier message:
"Just like Jean-Pierre mentioned, we'll be using parallel
trees to generate P2SH addresses after sorting the keys
lexicographically."
It sounds like "lexicographically" probably means sorting as strings. I
have made an implementation of public key sorting in javascript where I
sort them as big endian numbers and fill in the 0s. IMO, the simpler
method is to sort them as strings, which has a simpler implementation
since it doesn't require filling in 0s first. However, I don't actually
care what method we use so long as everyone in the bitcoin world uses
the same standard. Which is the best way to sort public keys?
--
Ryan X. Charles
Software Engineer, BitPay
--------------040807090208060101050100
Content-Type: application/pgp-keys;
name="0xA11B4DDE.asc"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
filename="0xA11B4DDE.asc"
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1
mQINBE3TEX0BEAC9RBUQXyHkqa7vZeRdKJp055NrQf90WMwYPSkVid+070kbGUDG
u1enIhRvTK/N89YFMQmReeDoWlYbnNA3/c1ohpOF7xbHt/+zI/EsyhRLO8FdRQY8
Z99+O8lgSMhBKSPa2zKXe7k4D80blrlkVLSsWDyHxpUaI8chzc3oOi8DucJyhjv5
VM6yvwxVcdG/YZAclgl+2H4pp6q6aa0VWygzbOVjbGnrzIBJ+yt8k14n44tOpH2m
My4xRAwa5XI5yqcH8ausSbE8Vyu4IUX04+U3q94TeLCBOneONFYZ1nfXmiY8/A9h
raDwmaZiHUppW/kBrqT6JkD2VXK43K+wlHW+XgCYcpec83PgNrotIXophoPaCyBi
pHBhIp17WOeIJt06d5isuTy09darvyPPNkkMX1RqH9U2/qvTjTP4cRgzTqQXvTae
YqIP96gnjQgMZNqKdBkVv/fN3KyuJJ7FYBNvdqyUpHf3xwV8uz/0XuUY3DcmpSRy
wb5DUa981xNnd/1rcAfO9arLq7jBl0qRpEe36ooJjfvZvS+WGiglBbtyOdK4O5N6
7c7kJxcJbowcatcCBdzZKK9DiuIc6w9lmuH1/QLwBqhSpyYdtI8wI/XssK3JLAGn
iwvzm8/18h18Ti0NpaedGzXQwcMcNOCi3MZ4HaANFlJiOEXops8XQzM0lwARAQAB
tChSeWFuIFguIENoYXJsZXMgPHJ5YW54Y2hhcmxlc0BnbWFpbC5jb20+iQI4BBMB
AgAiBQJRz3afAhsDBgsJCAcDAgYVCAIJCgsEFgIDAQIeAQIXgAAKCRAfqZTioRtN
3p3pD/9HsakeXS+A8vHSExrETTNsWOu2ImFOvecMOiMGCJ1muOkEaNNXenykbTkY
S5uoPkr65W/VNIAzRJaJRK/3eCHaruOr6y2hZg1WOK8YQOOgjuX9TrEuWv9HzH4r
tzbukywidc36UJ5s/hz378s8FvmTeZ1vKfi2NWU95zb2oc9KJ6PgWdWDfstuLuF/
noU+0YzezhGQyC5zDL811G4fTyJlRX9VCILeoMJGHlsurPA+n41PU3zWIZncQewF
e5+qXFuIIxLQL61v8O3mu0Uam1pyfUGalBWl/o8lIZpOmbiWpajvOBWXs4OJTA6F
9F0l55vvJkG+CFeyTen5OKH2BNuUHivFUHtzaZUtmYolziFC7OtIcV+wDdVNALyq
GSUDsqLxgPJ9Ptpo8eH5Pxei/kYTeRvFZIL5SsGFuKA9JCF3aXP8d1sT+/5aDRkv
JHkj6tnFeneuRKdkPexDPiAy7J178DsfU+GqstSwuSIzSr6ejZSz9hF5JoXhqD8o
QzNszjeGeY8+1/ERCZp1gv9q/NHk/qn/V1BEjXWr42N23jEL0YIGUHU2OSY8lDKY
mT9XrGZd3MbN/1EIu3rd9bnrnEZ/qJMPsbkcjxGO8m5Ku0dc1CouSfxbap6OvtmJ
iaYkw22lkakPbJj6j1Xi05+kLZs+njmgvbw5Rwt/4MHagHN8GbQ8UnlhbiBEaWNr
aGVyYmVyIChSeWFuIERpY2toZXJiZXIpIDxyeWFuZGlja2hlcmJlckBnbWFpbC5j
b20+iQI4BBMBAgAiBQJRotpTAhsDBgsJCAcDAgYVCAIJCgsEFgIDAQIeAQIXgAAK
CRAfqZTioRtN3iFCD/9CDsvFhWbPbBXqTLq06K7TtZohsQTVeZboJajdcS+JQY7Q
BPZgLF0QJCaUO6YPxgydI2oHRftqheqPT15U/fGkKMutDqic+SwoTxQZQqafj6fe
qic6ZcZHeXe4wR+hai+UQZDTuHiImQ6sSlEE+0rcQF2hsXmKnlhGySpOFIQYCx9t
tRfFxrMlhoFbx+AuzGPTk8dDIxmWq5iVseVDGhBvYtVlW0PfiOls2fK1Fl1vf5Uc
vS8TPe4Hc/HXOvVprj1uxdAEHzPlk0vMYquDm5pkEIjxSvBG+p70tucvuQzIS/s/
bS90zWgTA0J/KCsIukfqrxWMfzuJK5px5FvOZaATHIxT1ePh7J5n4TfqGwbh2Z6d
tnDrti+WpZy/NKNZoGb7jsJK+E+DKTGTXYOEgVY+v9IiV3G1XEAG6gXNlWl59Czb
RP7d5AqquXeB85RQ3frlD2Ne12B13M+UPy5kc34y9ue3Ud4n2tlRkjw+QS3FhDfh
XNtIvQ3uX772ysQuedpn24wsNVzoc1ynonW3VEFumxErfJdfdU7Kq0Br0N6C5hT0
XE4yIG9VSUxvOlxubBRyqjnXHIcowheKkp6qsjVmh90tqE9ClqVv0amk7gdflaY0
/xbQdNqV7ke8Y/Yo/aGsubVEqQyPiilCtTkrRnQX9zL+HszLS1/zLQXwqfqo7LQ3
QXN0cm9oYWNrZXIgKEFzdHJvaGFja2VyKSA8YXN0cm9oYWNrZXJAYXN0cm9oYWNr
ZXIuY29tPokCOAQTAQIAIgUCTgwEpgIbAwYLCQgHAwIGFQgCCQoLBBYCAwECHgEC
F4AACgkQH6mU4qEbTd6hZhAAirI33FsNa4cXysp6RKhvwUMK3hFRxS0C1kH13h6H
X28gEFTGsi8VfaLGA4O1DaktHzj7oox95SSbMckBqgjCA4ImVFjiKAcA9I4gvFl+
QkCq+oxZ49JlSJ+jnJ+dfIY2thUpw5ZlWv3mguJbCfRGSs2XKTxcKPHAwZUJOa08
10wMbkJdJPh9Avpr0YKc2gDId+RXRHplQOwdMgK7Re9QJwjcrsvPOb9I/YI001QH
EZyJ4x+oQgSDieUP2KQcK0Z4tCrIoomIDt9izRC3Cr1cpFGjY+mRIyQov8mvzhqG
ElDAuyh4uA9OId57VnjSpEfrFfIqqZTslnPwH5RtkRzWAModJ2PbECfBqvSLPpXQ
ZYJvUQcg5avORINuEvapbbJIPKpDCj4axXPiNsMd7U9pMz/e/9iSxgPMH1/QMebY
AW9G1rwhaYT3VXDH2/7X5JhyyRMd+/bT01jhGoarJVWJZQ9bdJ9acpSQPyhr64an
1+x4gKEBtoAJGrwCmZaaEj7f8OPYPehC8QYHTnHvTxKZw38AthyMn43F02iTMpDW
J1ZJc+wFhf/xnFUcGwXcur0k17AimKe91aQJQreEOQxzJlPVBimS8nD9ySq9KA/Y
rdWisv4aaNQUe4+VQyE9wqygTCCU30VmsrGQsZep+kDqSMboWS4kH86HzX5W3z/d
a9G0IVJ5YW4gWC4gQ2hhcmxlcyA8cnlhbkBiaXRwYXkuY29tPokCOAQTAQIAIgUC
UkRKJgIbAwYLCQgHAwIGFQgCCQoLBBYCAwECHgECF4AACgkQH6mU4qEbTd5x8w//
Zy++sbaRB9MWF2RP1rPEb31CdOMFgQxK6hUZ28O+0/8LPR7CFOVlhXS6Q512hoNB
P2pG55h5JONblUQ9WmW3ENWCesCsXBKcqOHhJYMyoyNQw1QkH4qw178rWTCKL9UY
L8qq907QNL1GLuZZL1S3xluRh1hsHTkW90Lb1xl6sGHKFZzEqf/yOInIuIXi9XvI
q+O7nb9/TpHSfnyokm2eF1DqOhBo8NtObVOrO3tNcNtn4vYEKfj3O41ls0N+BpgV
fAQYNZJpAa6k8hNyWqbc+9PwSE01NaHuh28ZahPZisfghb8ikaMpWx6WvrlHUDRX
aZloeX90bkPyjo3fZE+o55qxcC5s61QCRAt2qDNgmA0vAM8Xbjnl0VpTTHFEJOun
PqrTz8zrNndNWfFHJmpuBBlWfKKzgTV0e1NbSJkdI/VdSdSLWP+41ChP1DlDRdFC
0gzzBT8ykCTqHLEwI0PVQ/IBqNi+VYkUktXl3q4MzRrpJB2N4GAwHbJJiP5csHXo
EvYho6BvpvJieQdk2rXuQd6FtpE+TuoPxXEkEMPO/UXMx4Lz5HQZOyymhGOv0Ynz
yMNfVAFQ0UmbGer1b6CJqJGNcdxW1p0YmJX9n5wJSzkzra2GnuNbTH+yTBJxJ18p
9M76MhumAtrnC5Y9lB6ryim+TJrK2M3VQ0iY81R2DX65Ag0ETdMRfQEQAMrDwN6w
MloVYPzREi69vWdLYeDSNarrJ6dgWHiC2Pxp/t8A1mv9POqx1fFzQZyyTqD+ZiJi
ERUUjgGgpTkL/vxjdbqN4d6dAvKciCL0K4+lpsOSN3KEQSjY3LcjtR1mVCMKiMlQ
enxNghxPq09jhZIrS7jT9Eyzj5JLAE2IwanBDGyFHoAi4ACy5G5UHsbNKY/QQIWT
Likd7dwFmaoUR6HYjoiWdqee7MSbpAQJtJptLhsVbj5T4bYg9ETe7b+y0/A9pjIf
yCkjOTcsTlNLkUP728GI4dp42U1hyxW6z2SblAEZvF8kL6RAFcn6zImqy+DYk37L
Rbnrecf39V+rrS2HCFwxQYDDeaaYIgYsrlD1JJs+tQPHmrO/9lj5rrPhAq04/QVX
kqtFTQbK+N60TWStbT5ly1t7fsFzNUxgNEqXwwPr74hAnBhJaboL+ad4x2s2H1+P
2TAIJMWfIOvcS7lJouYO9c1g3nPp4LrQvECEPNAj1ukEqhGeRQxAls8wDPZD7f+u
SDTUSpo78aDa+YBK14CIWU3WX8itpEUJyPOIJCYt0vOpadejDWF2gbLAYdkyiwr4
Bw4MGqu4kjdd8kjZzt77anbezzzJ46inM/uX+3m7LnqnksUFAFU+ZDCUOolExVbC
tlvrZsHdM1dKibqimKE79X4d1bhtROoz2ILdABEBAAGJAh8EGAECAAkFAk3TEX0C
GwwACgkQH6mU4qEbTd7C5BAAqWClD0nUhptpQd0gPxrcOk3yg0K2b1LUKvRIggU0
cK6xXSWopVc4DtMLvQCEJ3CEIKya17vD1dYtD2QceUby0fQRBh0mCBT5kKy3nVQe
VDGENSE9+V6KU8UCWul+ah5tYmLvbQX+p+7HHiGXQ6lF0Q8ynriy07kWTzPPXip0
Cm0nHorf2WsUrVX33UWDVvowl32zW895eTzd7ycPp9OBufR7usCG853A5yiDSvvN
lLJUkw5rTpgL5sMn+oLj1rou5rC1WrWBcBvBnBlsNZe1hU+4AuVTOghqAaGxKNzA
MbQpbScHlKoU8FVZHL9mkUUOKzQr5wM30Zpsq4MGs8yE5pHxg34Ap6B5fgEbd7L+
JLJUSK1hnr8mYAWuF3Oe/uRlkDyrdkeIwSPewOwgu2KSUdqpy9CK1ekGs6hhemV+
OUYHiAg7AI511GHYSuGhncXi712XYyXl+UOgOaj42/++lypy/pN47GW/eQ3jymSG
Gkfba/G7grnRZkzKAovAtXa3cN03DhIS9k4ot9700CCZHPjiEf1oEcOf1cx6i+FI
zSJe6/Z4LBXfIsptQqPRmxPqXFfsGlpnrCEalqfEnaJimAQ6JgVyWAooYHEjx2Hg
1rJRxRN7n4XiVLW1mEmOfKwR7zHs1tlKSitGOawA250zLplUE/s9IJSqB3jXH/SH
afQ=3D
=3DcB+0
-----END PGP PUBLIC KEY BLOCK-----
--------------040807090208060101050100--
|
