Message-ID: <54DD2154.5050609@thomaskerin.io>
Date: Thu, 12 Feb 2015 21:55:32 +0000
From: Thomas Kerin <me@thomaskerin.io>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
	rv:31.0) Gecko/20100101 Thunderbird/31.4.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
OpenPGP: url=http://pgp.mit.edu/pks/lookup?op=get&search=0x3F0D2F83A2966155
Content-Type: multipart/mixed; boundary="------------080702080102090504080509"
Subject: [Bitcoin-development] BIP for deterministic multisig addresses
Precedence: list

This is a multi-part message in MIME format.
--------------080702080102090504080509
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Not sure what happened there - I'll drop the PGP.


Hi all,

I have drafted a BIP with Jean Pierre and Ruben after the last
discussion, related to a standard for deriving a canonical
pay-to-script-hash address given a set of public keys and the number of
signatures required. There have been two or three discussions about it
on the mailing list to date, and various services already carry out this
process. I hope a BIP to describe this process will allow services to
declare themselves as BIPXX compliant, working towards interoperability
of services and simplifying the derivation of scripts and their
addresses by all parties.


  BIP: XX
  Title: Deterministic Pay-to-script-hash multi-signature addresses
through public key sorting
  Author: Thomas Kerin, Jean-Pierre Rupp, Ruben de Vries
  Status: Draft
  Type: Standards Track
  Created: 8 February 2015

=3D=3DAbstract=3D=3D

This BIP describes a method to deterministically generate
multi-signature transaction scripts.  It focuses on defining how the
public keys must be encoded and sorted so that the redeem script and
corresponding P2SH address are always the same for a given set of keys
and number of required signatures.

=3D=3DMotivation=3D=3D

Most multi-signature transactions are addressed to P2SH
(pay-to-script-hash) addresses, as defined in BIP-0016.

Multi-signature redeem scripts do not require a particular ordering or
encoding for public keys.  This means that for a given set of keys and
number of required signatures, there are as many as 2(n!) possible
standard redeem scripts, each with its separate P2SH address.  Adhering
to a an ordering scheme and key encoding would ensure that a
multi-signature =E2=80=9Caccount=E2=80=9D (set of public keys and require=
d signature
count) has a canonical P2SH address.

By adopting a sorting and encoding standard, compliant wallets will
always produce the same P2SH address for the same given set of keys and
required signature count, making it easier to recognize transactions
involving that multi-signature account.  This is particularly attractive
for multisignature hierarchical-deterministic wallets, as less state is
required to setup multi-signature accounts:  only the number of required
signatures and master public keys of participants need to be shared, and
all wallets will generate the same addresses.

While most web wallets do not presently facilitate the setup of
multisignature accounts with users of a different service, conventions
which ensure cross-compatibility should make it easier to achieve this.

Many wallet as a service providers use a 2of3 multi-signature schema
where the user stores 1 of the keys (offline) as backup while using the
other key for daily use and letting the service cosign his transactions.
This standard will help in enabling a party other than the service
provider to recover the wallet without any help from the service provider=
.

=3D=3DImplementation=3D=3D

For a set of public keys, ensure that they have been received in
compressed form, sort them lexicographically according to their binary
representation before using the resulting list of keys in a standard
multisig redeem script.  Hash the redeem script according to BIP-0016 to
get the P2SH address.

=3D=3DCompatibility=3D=3D

* Uncompressed keys are incompatible with this specificiation. A
compatible implementation should not automatically compress keys.=20
Receiving an uncompressed key from a multisig participant should be
interpreted as a sign that the user has an incompatible implementation.
* P2SH addressses do not reveal information about the script that is
receiving the funds. For this reason it is not technically possible to
enforce this BIP as a rule on the network.  Also, it would cause a hard
fork.
* Implementations that do not conform with this BIP will have
compatibility issues with strictly-compliant wallets.
* Implementations which do adopt this standard will be cross-compatible
when choosing multisig addressses.
* If a group of users were not entirely compliant, there is the
possibility that a participant will derive an address that the others
will not recognize as part of the common multisig account.

=3D=3DTest vectors=3D=3D
The required number of signatures in each case is 2.

Vector 1
* List
** 02ff12471208c14bd580709cb2358d98975247d8765f92bc25eab3b2763ed605f8
** 02fe6f0a5a297eb38c391581c4413e084773ea23954d93f7753db7dc0adc188b2f
* Sorted
** 02fe6f0a5a297eb38c391581c4413e084773ea23954d93f7753db7dc0adc188b2f
** 02ff12471208c14bd580709cb2358d98975247d8765f92bc25eab3b2763ed605f8
* Script
**
522102fe6f0a5a297eb38c391581c4413e084773ea23954d93f7753db7dc0adc188b2f210=
2ff12471208c14bd580709cb2358d98975247d8765f92bc25eab3b2763ed605f852ae
* Address
** 39bgKC7RFbpoCRbtD5KEdkYKtNyhpsNa3Z

Vector 2 (Already sorted, no action required)
* List:
** 02632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed0
** 027735a29bae7780a9755fae7a1c4374c656ac6a69ea9f3697fda61bb99a4f3e77
** 02e2cc6bd5f45edd43bebe7cb9b675f0ce9ed3efe613b177588290ad188d11b404
* Sorted:
** 02632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed0
** 027735a29bae7780a9755fae7a1c4374c656ac6a69ea9f3697fda61bb99a4f3e77
** 02e2cc6bd5f45edd43bebe7cb9b675f0ce9ed3efe613b177588290ad188d11b404
* Script
**
522102632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed0210=
27735a29bae7780a9755fae7a1c4374c656ac6a69ea9f3697fda61bb99a4f3e772102e2cc=
6bd5f45edd43bebe7cb9b675f0ce9ed3efe613b177588290ad188d11b40453ae
* Address
** 3CKHTjBKxCARLzwABMu9yD85kvtm7WnMfH

Vector 3:
* List:  =20
** 030000000000000000000000000000000000004141414141414141414141414141
** 020000000000000000000000000000000000004141414141414141414141414141
** 020000000000000000000000000000000000004141414141414141414141414140
** 030000000000000000000000000000000000004141414141414141414141414140
* Sorted:
** 020000000000000000000000000000000000004141414141414141414141414140
** 020000000000000000000000000000000000004141414141414141414141414141
** 030000000000000000000000000000000000004141414141414141414141414140
** 030000000000000000000000000000000000004141414141414141414141414141
* Script
**
5221020000000000000000000000000000000000004141414141414141414141414140210=
2000000000000000000000000000000000000414141414141414141414141414121030000=
0000000000000000000000000000000041414141414141414141414141402103000000000=
000000000000000000000000000414141414141414141414141414154ae
* Address
** 32V85igBri9zcfBRVupVvwK18NFtS37FuD

Vector 4: (from bitcore)
* List:
** 022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da
** 03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9
** 021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18
* Sorted:
** 021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18
** 022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da
** 03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9
* Script
**
5221021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18210=
22df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da2103e381=
8b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e953ae
* Address
** 3Q4sF6tv9wsdqu2NtARzNCpQgwifm2rAba

=3D=3DUsage & Implementations=3D=3D
* BIP45 - Structure for Deterministic P2SH Multisignature Wallets -
https://github.com/bitcoin/bips/blob/master/bip-0045.mediawiki#address-ge=
neration-procedure
* Bitcore -
https://github.com/bitpay/bitcore/blob/50a868cb8cdf2be04bb1c5bf4bcc064cc0=
6f5888/lib/script/script.js#L541
* Haskoin -
https://github.com/haskoin/haskoin/blob/master/Network/Haskoin/Script/Par=
ser.hs#L112-122
* Armory -
https://github.com/etotheipi/BitcoinArmory/blob/268db0f3fa20c989057bd4334=
3a43b2edbe89aeb/armoryengine/ArmoryUtils.py#L1441
* Multisignature Brainwallet - http://ms-brainwallet.org/
  =20
For now, the BIP will live here:
https://github.com/afk11/bips/blob/bip0090/bip-0090.mediawiki/

Looking forward to any feedback and discussions that arise!


- --=20
Thomas Kerin


--------------080702080102090504080509
Content-Type: application/pgp-keys;
 name="0xA2966155.asc"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename="0xA2966155.asc"

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1

mQINBFIo7+cBEACr9+6kdQHmlSb8YWhlroBv4yE0opZphlZmX0+1O82oYZItMfIE
q8mY0MTwtiknFQdxUnRxCZj9y/XihqXl9a+z6QF5+YkLXPYCRrQokHkcHKZmHggv
eqogEgUzeYIvnx+FWxD8pXa9T2aQ1DnyRbbAYIcqs9KJFfpE8i8v9tkm3CN8u0iU
9bxObYXOtni2XPoAlEJIM5U0xRftq1+W7Y4Wh8DxgibftcmKPDqrIUpHhJN8uRHj
CQCU9hIwyy7TQXOKCQUyg7yneLyKva+XcrFyndpPC8gx2cbziaHNlq5Oj69ggicl
deC8GDKBFbnEcdSLlvq++HylFbydPPFtbaT0c4gzVKFsYSS4lWaXsCv8Lm6rk41N
h4xloou3qm/9kciLwzHC+RPca+vg+EBh7NLmozxTLm1/zH5yyB1WFEjwl+mbznsh
KbMKQYIdQUnWhwfasiGsBhkUW/C40PhuZQEtloBYLygNYft4KCzlOIo5VVtSapr8
n1wEUGsSmuzmknRzHJPYnt/QAAktVvwolHs1IC/lifhODB4fHX0aiG3qeScauTBO
CUA7PX9lFfqbtnBeqHAr1gC3JQ4jljo/z9OE6hh+T6tekUFH3KRFEIRyxKwQohPx
gr6LOQ19+DxkQLUFzTDkjKhWmWKqhLnAQb3leglthY09+NeEsgL+xxvsMQARAQAB
tB9UaG9tYXMgS2VyaW4gPHRob21hc0ByaWJiaXQubWU+iQI+BBMBAgAoBQJUkcSo
AhsDBQkFo5qABgsJCAcDAgYVCAIJCgsEFgIDAQIeAQIXgAAKCRA/DS+DopZhVdcH
D/9DqaDfvM8k9Yw+VtGgWliPLOmCSvKieiNHBdpKhSlJ/cOc/MDZhnBXZiHH7FN5
ZER3OscfAqNvdMuw+b3zLknNmF4Jl/b47LZv6Z8KB/ra9M3vO9KNpJT3GkSrvzNS
r3tz4ogEvNI0bJd7lDB98Vd9ACcvPhV5rH5uJ5E4cIbcuLQmj7FAQq815oaocrug
2LN2xwPOZKzXDGpyCecoJgrMaGiE4l84OcruEpLkN1mb7of8iDRvj1kQFxF4hCJm
aIvxCHvSCUViH5AJOy4HoMAz810mlzEmptoi1H/h9D6PSi2xeL43e/WRjOys6upt
lLlXsAnEELgUoD/iAHvTqag+53cCkv47/b11TnaiU5ZhF5RLypsFxaI5OCJVolY4
HkUrTbop+1GyUPWf79im6JDDScwxuAUaaBFlYcin23Y92Q4qmjhGNjNjl2/quKBk
K1oqmEnKaX55IAn+xdAMeL828bss57lm62E4od7kPi+44NYNlRrefioNpYJcq6mL
2ISvMPFqgFCKyHzGJDct3jTQ4iQQlodDzV8WXCvTNf7zt83MOUnMR0b9hep34wKT
+lcjYIn3zfPPz/KGetAdxYkMUW+2j13Ilxw0FT6PIy7Sbhh0zEth11SWlgLDjMDK
bbXUAN8D2PnHPYjpDfKaymI1wgMTy9GGqn8Z5cF8sYJqa7Q5VGhvbWFzIEtlcmlu
IChodHRwczovL3Rob21hc2tlcmluLmlvKSA8bWVAdGhvbWFza2VyaW4uaW8+iQJB
BBMBAgArAhsDBQkFo5qABgsJCAcDAgYVCAIJCgsEFgIDAQIeAQIXgAUCVKxt7wIZ
AQAKCRA/DS+DopZhVSrmD/9mj4g6H0j5QPLozzR5tQzc1FRk5p2fusVyldAQ2aR/
ibw9CU13umJcFkCCbm4lckauiuDBZf3UTVxY16QNpaGXj5ZJrSkiLVhPfuPNNwXi
cEi32OOHPoPbH8nSicwOPzdNJCpBv/r7eDkklBtUOfSNOhyUZdQJWg3XHFR/vjM7
wv/GZBGiIT7bmeIGKytP8DHPxONvwZ6k2wjOWzrJkQWkzwIIWFrReC0KzYZ3O6cL
wBEXUlyzP19cbahOj4DSyMtQBefK8Ti8J6nxz6QVY6zZTl60cHU0HYZ+HM9RnpAJ
TD8Nask6G+kwhTsnDRXQqMr/Jgq9sE05pFEorVPgUTzEJWsS6mRxHJ5hEWP0KAq7
k+SkVIb8+/+a5HppuVKsO8e5tn0+UoKHWqJpagHt3A8bBRcen0JTxE8PA/oO8y4f
Lb5fTW5rjKrAz6pQFQh0v8qZNWrAt8a8kmhWEQge3jqMkWcO0IxtDRO+k/DoI/iP
QsmtZuL+GsPKOhLDBkPGtEdoetrKVT6702Nrr5GeBn5iV69FG6z2j9ULGbI+xqNt
a1unS748VfH4sMgnIpUCD+BJ1yKMSUDdHd8qIX7oBzAvuAtI4FcJVf5IyO+s811E
zYVvPHYPpHgeAB2ZGxsRQ+qy1P10KS2JKllyn50lLN0wW72OYzwvXAzzRCODbbQ3
GYkCPgQTAQIAKAUCVHkd6QIbAwUJBaOagAYLCQgHAwIGFQgCCQoLBBYCAwECHgEC
F4AACgkQPw0vg6KWYVVDbxAAnwDZKWiNdMMqPaRVwwkclyB2edlfvV+lppZMksQg
wyZjYedwCSHJ/SnymaZikc+qokeOv8XfvHCPzxLAslSrEe+mc24mrWk2Oy2y/DW9
0s4ZKG5m2vLsdZVQ6li18lHsCub2S/C9uHiU9y2oRWVLmeliFqwKYI1BO53vXYhb
VsHrdh6x485u1z9N8GlkmHlyTrvnOyp77AJ0OeD0xcdnaEGWYJve+Pu9PNGqG+1l
kr7LEZ2toP9n64L3JRjmGBiPQWHtE38DkHQSEA/32RJINcuANrN3Ve+vvqc7Gh+c
jHyHDegDNR1TDEzt69NQZELjH+0kLov3ZS6X5mwdOSns+Y6gO/NHqeNnm5ClPHNc
yHVj5rTE9A67UAyQ5flXLMTJHS4grUwUVk9d8UOOjoJDHrc3QDy2a4mBIc9WaXxe
Jj/y2C5DYF83PNWxqa1RtEjtPfwgCuvX+6lqAMq9BEM3DTrqdsmZlu9zD568ThMT
7LdeE3c91qcg97D4mpqUVWQBnEUKyHV7IQQwa20hUMOWS4OEsQsW+CtmfLjpQVIi
JMMBu9u1cD8pfDzirXyMDurP5uhvJZd/kir0/k7IR0O9vW3b3bu4NHLLrvyuPYHh
RGQQTApYMMUqXtgnyPOyHYCvyKUMSkpfYUmDLyz3AnQ8F0yJhz6ruLTdxlqQS10k
xUq0JVRob21hcyBLZXJpbiA8dGhvbWFzLmtlcmluQGdtYWlsLmNvbT6JAj4EEwEC
ACgFAlIo7+cCGwMFCQWjmoAGCwkIBwMCBhUIAgkKCwQWAgMBAh4BAheAAAoJED8N
L4OilmFVPj4P/3ZIWDgU4x1bkkI53/t43epbiJHLso7urwDoybczOd+RXyB8dzHf
SY/zG+trPuqRIm6wHLlQJy8Mz5S1JoVGa1pEwpBmAlfzoeDxtYIHBAwjr1cQwZLc
zJ/aF63rhu9kS8wSxHoVj0DzpiirbKL0R4EtnyOnRqxmTeDFENOt2pkLhYQAZWLT
dYGSa3y2BvEh/VXT2x7I9RxdNmiSnrVba76+7OX3mp1sMdqfPeSGWj9BDJLOC0lG
8G1wbUBtqJWqZG91/kG/niAqVd3jo9jbUltFMrhhfYa9OER7Umq2qTuMo2X9abdy
I7466ZXiHfpjyfgusDC0xOuj/JHSDVCkVaNB/4AHqQB59geObSpKT76QR5sSwuWv
0GP+p0UgRX48B+Plqe36uIpZDq6jeIz9t/OPy9WeOQZ2qRXaF9AbUmopj6Kc9Tze
4d+a4yI4989RHAsUwm9mjh0zYu6UnhARcvibk2M02BIgxUoACmSv1W+2DnJ3cR2N
XmUz71AKRSLfXLAukO4mziS4OmwJ4ulSgUu9olyWXdsRyLSfLlzXxQvMgxlQP+CW
5lbkAHF2DpR4AksN7giXKKdqgnfRsmJKuMDtU6S+sEIIPtWR5Gid8HuXVqtDqRwI
OhB+UFG9sM/De6LoDS5HihvH1VeYyRGSz2dWvmJfUshsLExMUoOCPB6AiF4EEBEI
AAYFAlQQyUgACgkQZqkwPiW4rVXPnAD+PrTOG+0jhxNOuUSHd4DpYMAc3bz8lbQE
/hqhADAruG4BAKz7Vt5R+LEXizDjA+R3CXXdI1SMmVSb08MIjK/H7/ORuQINBFIo
7+cBEACqk9/vXSO76KZUk76qdAmc6LWh3NnLNdD8vcKZHKMPa/UwU4TNjm5efaJN
3rfH3lVNf9HivZJCvWZ08Y85f3OlhqrMMViNGyHoJqaBsKYebeuKDXoZQyc/keRn
CpGn7oOOIkwiwwGCcUjIa4G2C2XIRm6Jz2S5/3pbNlDLh3h0RkamxeST/Ok1m7oB
fbVmcKKowBXloFiOyaNwf9NusQ59udTvhMm5EQFiRU9p5nVG0XaFITm3KRPaNUpD
grZ+txqcQT46c5+97qV9CRngnT7TqwfnxvSgzwezuub3eINLWKaGus+yVrPuj4iq
sBFeEwaXI//lW8ocs/0Ji8GCcU1bNxM0jvJQYipUsOI+krBpae+c1d0H5JnJw2lf
QdZ/4kc8OZW7GnRGyXJvOxmZL9VExGrLpyfd1J9XEmDeCBMuN+6khTVvQjo0XMTb
xEko5/wsRyh9w7UrvXpSs2bXIEVQL5lYR4RsHVJZkrkf3KvG2ZnghbDa2Zst6ZVH
YfdIiSGtir8BvBfw8gpLSnfl50l65ppUIZA/KuSGVtH6g+YSiX0GeJa0tirJHr7v
u0HWdWh+HWoaIFIENcH7Fel4BDKzFgVCFwbDlil2ZxeA2ffctzMhtX2dwLSfaleV
yTsITdKARWFEfPN+XsQI67j6xLwrzkMHeOrxH7CfXrf3/7D3GQARAQABiQIlBBgB
AgAPBQJSKO/nAhsMBQkFo5qAAAoJED8NL4OilmFVDb4P/i/En9gxNav9shtoMTR+
oQkU5xkHRwbwu0H1FrW2yH0B0ooZkcn6QQ+CxGZsO7fwEzMcok8AqlFyDrJWyYS/
My0PzwYkpBhJ6vyh7SLI9G0hrjOySoAVfPuY2rDkydlbD/Ep4QGrvCUDUN81hLNx
bJrtyqxooJkkYKjUg6LIViRJM5wTDFJCV6/LaNump/tl0dreIdZ8C9p2GBTWqR0U
ouPGpNs5+UXb6DTd6j79QbOy/QpAGssbCHy58ewGV8vtWwCd9InJaeH7yfHcq4tw
+nkT61wNJ/eb5JlX7kmwme8lc+zQobGk3kaYP8stcfhTpl4IkS5Ln8VRbyXUZovx
mK1X9GwlhMXI+SAKCcHgmgj3B2CCj45Mh/AMAqgsBv9FQdGDjk7GR9dYea77kpfm
jrXMX0d6U+Z/0OItSsZMsvxbLulCtyJMcgDx8cVq6WQyMlwGeoKKTfGc7a/9NAFT
cIIqgFpVcSUKNBQnQFFvMWxCkc7f7S/Ep2TxypwNUVBfwJYe658VVi/PRlh4Usza
r69k5TTMQOS/54Hos13y+MYhizjr7PDXFz9HbPQymUd/+OPUPI982AJ1e0QNB/0r
idvufh02N+l6zOzPaVPQAZJ89/MU6ehTo81aYXkG3GB7LQB2FN+gVd4ml4HMa0r+
JDB0hVaFYV98nLJ9V9LtEA9P
=ntkV
-----END PGP PUBLIC KEY BLOCK-----

--------------080702080102090504080509--