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; 
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
Content-Type: multipart/mixed; boundary="------------040807090208060101050100"
Subject: [Bitcoin-development] sorting public keys for p2sh multisig
	transactions
Precedence: list

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