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 ) 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 ; 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 (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" 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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--