public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: "Ryan X. Charles" <ryan@bitpay.com>
To: bitcoin-development@lists.sourceforge.net
Subject: [Bitcoin-development] sorting public keys for p2sh multisig transactions
Date: Wed, 12 Mar 2014 13:10:36 -0400	[thread overview]
Message-ID: <5320950C.5050107@bitpay.com> (raw)

[-- Attachment #1: Type: text/plain, Size: 1770 bytes --]

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

[-- Attachment #2: 0xA11B4DDE.asc --]
[-- Type: application/pgp-keys, Size: 5718 bytes --]

             reply	other threads:[~2014-03-12 17:10 UTC|newest]

Thread overview: 2+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2014-03-12 17:10 Ryan X. Charles [this message]
2014-03-12 19:42 ` [Bitcoin-development] sorting public keys for p2sh multisig transactions devrandom

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=5320950C.5050107@bitpay.com \
    --to=ryan@bitpay.com \
    --cc=bitcoin-development@lists.sourceforge.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox