From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1WNp3J-0006l9-I6 for bitcoin-development@lists.sourceforge.net; Wed, 12 Mar 2014 19:42:57 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of niftybox.net designates 95.142.167.147 as permitted sender) client-ip=95.142.167.147; envelope-from=c1.sf-bitcoin@niftybox.net; helo=i3.hyper.to; Received: from i3.hyper.to ([95.142.167.147]) by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1WNp3H-0008HJ-NH for bitcoin-development@lists.sourceforge.net; Wed, 12 Mar 2014 19:42:57 +0000 Received: from localhost (localhost [127.0.0.1]) by i3.hyper.to (Postfix) with ESMTP id AD625E0442; Wed, 12 Mar 2014 20:42:49 +0100 (CET) Received: from i3.hyper.to ([127.0.0.1]) by localhost (i3.hyper.to [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id bea4aY4z0EKI; Wed, 12 Mar 2014 20:42:49 +0100 (CET) Received: from [127.0.0.1] (afo2.torproject.afo-tm.org [62.210.129.149]) by i3.hyper.to (Postfix) with ESMTPSA id A7FDBE02BB; Wed, 12 Mar 2014 20:42:47 +0100 (CET) Message-ID: <1394653364.19819.224.camel@mimiz> From: devrandom To: "Ryan X. Charles" Date: Wed, 12 Mar 2014 12:42:44 -0700 In-Reply-To: <5320950C.5050107@bitpay.com> References: <5320950C.5050107@bitpay.com> Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.8.4-0ubuntu1 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-Spam-Score: -1.5 (-) 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 X-Headers-End: 1WNp3H-0008HJ-NH Cc: bitcoin-development@lists.sourceforge.net Subject: Re: [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 19:42:57 -0000 Hi Ryan, Probably the most neutral way to go about this is to lexicographically sort by encoded representation bytes. In java, that would be ECPoint.getEncoded. This is what we currently do in our watchdog Oracle. On Wed, 2014-03-12 at 13:10 -0400, Ryan X. Charles wrote: > 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? > > ------------------------------------------------------------------------------ > Learn Graph Databases - Download FREE O'Reilly Book > "Graph Databases" is the definitive new guide to graph databases and their > applications. Written by three acclaimed leaders in the field, > this first edition is now available. Download your free book today! > http://p.sf.net/sfu/13534_NeoTech > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development