[Bitcoin-development] New BIP32 structure for P2SH multisig wallets

[Manuel Araoz]

Hi, I'm part of the team building copay <https://github.com/bitpay/copay>,
a multisignature P2SH HD wallet. We've been following the discussion
regarding standardizing the structure for branches both on this list and on
github (1 <https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki>,
2 <https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki>,
3<https://github.com/bitcoin/bips/blob/master/bip-0043.mediawiki>,
4 <https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki>,
5<https://github.com/bitcoin/bips/pull/52>).
Soon, we realized the assumptions in the discussions were not true for a
multisig hd wallet, so we wanted to share our current approach to that, to
get feedback and see if we can arrive to a new standard (and possibly a new
BIP)

These are our assumptions:
- N parties want to share an m-of-n wallet.
- Each party must generate their master private keys independently.
- Use multisig P2SH for all addresses.
- Use BIP32 to derive public keys, then create a multisig script, and use
the P2SH address for that.
- The address generation process should not require communicating with
other parties. (Thus, all parties must be able to generate all public keys)
- Transaction creation + signing requires communication between parties,
of course.

-------------------------------------------------

Following BIP43, we're be using:


m / purpose' / *

where *purpose* is the hardened derivation scheme based on the new BIP
number.
We then define the following levels:


m / purpose' / cosigner_index / change / address_index

Each level has a special meaning detailed below:

*cosigner_index* <http://en.wikipedia.org/wiki/Co-signing>: the index of
the party creating this address. The indices can be determined
independently by lexicographically sorting the master public keys of each
cosigner.

*change*: 0 for change, 1 for receive address.

*address_index*: Addresses are numbered from index 0 in sequentially
increasing manner. We're currently syncing the max used index for each
branch between all parties when they connect, but we're open to considering
removing the index sync and doing the more elegant used-address discovery
via a gap limit, as discussed in
BIP44<https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki#address-gap-limit>.
We feel 20 might be too low though.

*Wallet high-level description:*
Each party generates their own extended master keypair and shares the
extended purpose' public key with the others, which is stored encrypted.
Each party can generate any of the other's derived public keys, but only
his own private keys.

*General address generation procedure:*
When generating an address, each party can independently generate the N
needed public keys. They do this by deriving the public key in each of the
different trees, but using the same path. They can then generate the
multisig script and the corresponding p2sh address. In this way, each path
corresponds to an address, but the public keys for that address come from
different trees.

*Receive address case:*
Each cosigner generates addresses only on his own branch. One of the n
cosigners wants to receive a payment, and the others are offline. He knows
the last used index in his own branch, because only he generates addresses
there. Thus, he can generate the public keys for all of the others using
the next index, and calculate the needed script for the address.

*Example: *Cosigner #2 wants to receive a payment to the shared wallet. His
last used index on his own branch is 4. Then, the path for the next receive
address is m/$purpose/2/1/5. He uses this same path in all of the cosigners
trees to generate a public key for each one, and from that he gets the new
p2sh address.

*Change address case:*
Again, each cosigner generates addresses only on his own branch. One of the
n cosigners wants to create an outgoing payment, for which he'll need a
change address. He generates a new address using the same procedure as
above, but using a separate index to track the used change addresses.

*Example: *Cosigner #5 wants to send a payment from the shared wallet, for
which he'll need a change address. His last used change index on his own
branch is 11. Then, the path for the next change address is
m/$purpose/5/0/12. He uses this same path in all of the cosigners trees to
generate a public key for each one, and from that he gets the new p2sh
address.


*Transaction creation and signing:*
When creating a transaction, first one of the parties creates a Transaction
Proposal. This is a transaction that spends some output stored in any of
the p2sh multisig addresses (corresponding to any of the copayers'
branches). This proposal is sent to the other parties, who decide if they
want to sign. If they approve the proposal, they can generate their needed
private key for that specific address (using the same path that generated
the public key in that address, but deriving the private key instead), and
sign it. Once the proposal reaches m signatures, any cosigner can broadcast
it to the network, becoming final. The specifics of how this proposal is
structured, and the protocol to accept or reject it, belong to another BIP,
in my opinion.

*Final comments:*
- We're currently lexicographically sorting the public keys for each
address separately. We've read Mike Belshe's comments about sorting the
master public keys and then using the same order for all derived addresses,
but we couldn't think of any benefits of doing that (I mean, the benefits
of knowing whose public key is which).
- We originally thought we would need a non-hardened version of purpose for
the path, because we needed every party to be able to generate all the
public keys of the others. With the proposed path, is it true that the
cosigners will be able to generate them, by knowing the extended purpose
public key for each copayer? (m/purpose')
- The reason for using separate branches for each cosigner is we don't want
two of them generating the same address and receiving simultaneous payments
to it. The ideal case is that each address receives at most one payment,
requested by the corresponding cosigner.


Thoughts?
Manuel

[Alan Reiner]

I will just chime in that I've been working on a similar spec for Armory
to implement P2SH multisig and I came up with basically an identical
scheme. I think you covered most of what is needed. The one thing I
did differently was try to match the BIP 32 structure, by keeping the
original 3 levels (wallet, chain, addresses), and use 2*N chains to
handle the N different parties generating receiving and change
addresses. It's not necessary, but it follows more closely the
three-level scheme that BIP 32 originally envisioned. I also concluded
that the chain indices are ordered by lexicographical sorting of root
public keys, but resorting each individual address. There are use cases
where it will be necessary for parties to know how to combine public
keys into a multi-sig address without knowing the root keys.

Also, for the purposes of one-off types of escrow multi-sig, we have
included a "wallet locator" field in the transaction that must be passed
around. This "wallet locator" is stored with each key (perhaps at the
time public keys are collected and merged), and passed around with
transactions to be signed. This allows lightweight devices like
hardware wallets, to recognize their own keys. It would encoded in a
VAR_STR, and doesn't have to be meaningful to the other participants --
each device would look at all signing slots in a transaction (either
singlesig or each key in a multisig) and would generate a public key
along each path, and see if the result matches. If so, it can sign it.
If not, it must be someone else's.

I bring this up, because this multisig wallet structure you're talking
about has a very simple "wallet locator" scheme -- all parties will use
the same locator for a given receiving address. But that field should
remain part of the data structure for each key, to accommodate all types
of multisig, not just linked/parallel tree schemes.

-Alan

Post by Manuel Araoz
Hi, I'm part of the team building copay
<https://github.com/bitpay/copay>, a multisignature P2SH HD
wallet. We've been following the discussion regarding standardizing
the structure for branches both on this list and on github (1
<https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki>, 2
<https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki>, 3
<https://github.com/bitcoin/bips/blob/master/bip-0043.mediawiki>, 4
<https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki>, 5
<https://github.com/bitcoin/bips/pull/52>). Soon, we realized the
assumptions in the discussions were not true for a multisig hd wallet,
so we wanted to share our current approach to that, to get feedback
and see if we can arrive to a new standard (and possibly a new BIP)
- N parties want to share an m-of-n wallet.
- Each party must generate their master private keys independently.
- Use multisig P2SH for all addresses.
- Use BIP32 to derive public keys, then create a multisig script, and
use the P2SH address for that.
- The address generation process should not require communicating
with other parties. (Thus, all parties must be able to generate all
public keys)
- Transaction creation + signing requires communication between
parties, of course.
-------------------------------------------------
m / purpose' / *
where /purpose/ is the hardened derivation scheme based on the new BIP
number.
m / purpose' / cosigner_index / change / address_index
/cosigner_index/ <http://en.wikipedia.org/wiki/Co-signing>: the index
of the party creating this address. The indices can be determined
independently by lexicographically sorting the master public keys of
each cosigner.
/change/: 0 for change, 1 for receive address.
/address_index/: Addresses are numbered from index 0 in sequentially
increasing manner. We're currently syncing the max used index for each
branch between all parties when they connect, but we're open to
considering removing the index sync and doing the more elegant
used-address discovery via a gap limit, as discussed in BIP44
<https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki#address-gap-limit>.
We feel 20 might be too low though.
*Wallet high-level description:*
Each party generates their own extended master keypair and shares the
extended purpose' public key with the others, which is stored
encrypted. Each party can generate any of the other's derived public
keys, but only his own private keys.
*General address generation procedure:*
When generating an address, each party can independently generate the
N needed public keys. They do this by deriving the public key in each
of the different trees, but using the same path. They can then
generate the multisig script and the corresponding p2sh address. In
this way, each path corresponds to an address, but the public keys for
that address come from different trees.
*Receive address case:*
Each cosigner generates addresses only on his own branch. One of the n
cosigners wants to receive a payment, and the others are offline. He
knows the last used index in his own branch, because only he generates
addresses there. Thus, he can generate the public keys for all of the
others using the next index, and calculate the needed script for the
address.
/Example: /Cosigner #2 wants to receive a payment to the shared
wallet. His last used index on his own branch is 4. Then, the path for
the next receive address is m/$purpose/2/1/5. He uses this same path
in all of the cosigners trees to generate a public key for each one,
and from that he gets the new p2sh address.
*Change address case:*
Again, each cosigner generates addresses only on his own branch. One
of the n cosigners wants to create an outgoing payment, for which
he'll need a change address. He generates a new address using the same
procedure as above, but using a separate index to track the used
change addresses.
/
Example: /Cosigner #5 wants to send a payment from the shared wallet,
for which he'll need a change address. His last used change index on
his own branch is 11. Then, the path for the next change address is
m/$purpose/5/0/12. He uses this same path in all of the cosigners
trees to generate a public key for each one, and from that he gets the
new p2sh address.
*Transaction creation and signing:*
When creating a transaction, first one of the parties creates a
Transaction Proposal. This is a transaction that spends some output
stored in any of the p2sh multisig addresses (corresponding to any of
the copayers' branches). This proposal is sent to the other parties,
who decide if they want to sign. If they approve the proposal, they
can generate their needed private key for that specific address (using
the same path that generated the public key in that address, but
deriving the private key instead), and sign it. Once the proposal
reaches m signatures, any cosigner can broadcast it to the network,
becoming final. The specifics of how this proposal is structured, and
the protocol to accept or reject it, belong to another BIP, in my
opinion.
*Final comments:*
- We're currently lexicographically sorting the public keys for each
address separately. We've read Mike Belshe's comments about sorting
the master public keys and then using the same order for all derived
addresses, but we couldn't think of any benefits of doing that (I
mean, the benefits of knowing whose public key is which).
- We originally thought we would need a non-hardened version of
purpose for the path, because we needed every party to be able to
generate all the public keys of the others. With the proposed path, is
it true that the cosigners will be able to generate them, by knowing
the extended purpose public key for each copayer? (m/purpose')
- The reason for using separate branches for each cosigner is we don't
want two of them generating the same address and receiving
simultaneous payments to it. The ideal case is that each address
receives at most one payment, requested by the corresponding cosigner.
Thoughts?
Manuel
------------------------------------------------------------------------------
Start Your Social Network Today - Download eXo Platform
Build your Enterprise Intranet with eXo Platform Software
Java Based Open Source Intranet - Social, Extensible, Cloud Ready
Get Started Now And Turn Your Intranet Into A Collaboration Platform
http://p.sf.net/sfu/ExoPlatform
_______________________________________________
Bitcoin-development mailing list
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Mike Hearn]

I'm not sure I understand why you need any special structure for this at
all. The way I'd do it is just use regular HD wallets for everyone, of the
regular form, and then swap the watching keys. Why do people need to be
given a cosigner index at all, given that they all have unique root keys
anyway?

Post by Manuel Araoz
Hi, I'm part of the team building copay <https://github.com/bitpay/copay>,
a multisignature P2SH HD wallet. We've been following the discussion
regarding standardizing the structure for branches both on this list and on
github (1 <https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki>,
2 <https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki>, 3<https://github.com/bitcoin/bips/blob/master/bip-0043.mediawiki>,
4 <https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki>, 5<https://github.com/bitcoin/bips/pull/52>).
Soon, we realized the assumptions in the discussions were not true for a
multisig hd wallet, so we wanted to share our current approach to that, to
get feedback and see if we can arrive to a new standard (and possibly a new
BIP)
- N parties want to share an m-of-n wallet.
- Each party must generate their master private keys independently.
- Use multisig P2SH for all addresses.
- Use BIP32 to derive public keys, then create a multisig script, and use
the P2SH address for that.
- The address generation process should not require communicating with
other parties. (Thus, all parties must be able to generate all public keys)
- Transaction creation + signing requires communication between parties,
of course.
-------------------------------------------------
m / purpose' / *
where *purpose* is the hardened derivation scheme based on the new BIP
number.
m / purpose' / cosigner_index / change / address_index
*cosigner_index* <http://en.wikipedia.org/wiki/Co-signing>: the index of
the party creating this address. The indices can be determined
independently by lexicographically sorting the master public keys of each
cosigner.
*change*: 0 for change, 1 for receive address.
*address_index*: Addresses are numbered from index 0 in sequentially
increasing manner. We're currently syncing the max used index for each
branch between all parties when they connect, but we're open to considering
removing the index sync and doing the more elegant used-address discovery
via a gap limit, as discussed in BIP44<https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki#address-gap-limit>.
We feel 20 might be too low though.
*Wallet high-level description:*
Each party generates their own extended master keypair and shares the
extended purpose' public key with the others, which is stored encrypted.
Each party can generate any of the other's derived public keys, but only
his own private keys.
*General address generation procedure:*
When generating an address, each party can independently generate the N
needed public keys. They do this by deriving the public key in each of the
different trees, but using the same path. They can then generate the
multisig script and the corresponding p2sh address. In this way, each path
corresponds to an address, but the public keys for that address come from
different trees.
*Receive address case:*
Each cosigner generates addresses only on his own branch. One of the n
cosigners wants to receive a payment, and the others are offline. He knows
the last used index in his own branch, because only he generates addresses
there. Thus, he can generate the public keys for all of the others using
the next index, and calculate the needed script for the address.
*Example: *Cosigner #2 wants to receive a payment to the shared wallet.
His last used index on his own branch is 4. Then, the path for the next
receive address is m/$purpose/2/1/5. He uses this same path in all of the
cosigners trees to generate a public key for each one, and from that he
gets the new p2sh address.
*Change address case:*
Again, each cosigner generates addresses only on his own branch. One of
the n cosigners wants to create an outgoing payment, for which he'll need a
change address. He generates a new address using the same procedure as
above, but using a separate index to track the used change addresses.
*Example: *Cosigner #5 wants to send a payment from the shared wallet,
for which he'll need a change address. His last used change index on his
own branch is 11. Then, the path for the next change address is
m/$purpose/5/0/12. He uses this same path in all of the cosigners trees to
generate a public key for each one, and from that he gets the new p2sh
address.
*Transaction creation and signing:*
When creating a transaction, first one of the parties creates a
Transaction Proposal. This is a transaction that spends some output stored
in any of the p2sh multisig addresses (corresponding to any of the
copayers' branches). This proposal is sent to the other parties, who decide
if they want to sign. If they approve the proposal, they can generate their
needed private key for that specific address (using the same path that
generated the public key in that address, but deriving the private key
instead), and sign it. Once the proposal reaches m signatures, any cosigner
can broadcast it to the network, becoming final. The specifics of how this
proposal is structured, and the protocol to accept or reject it, belong to
another BIP, in my opinion.
*Final comments:*
- We're currently lexicographically sorting the public keys for each
address separately. We've read Mike Belshe's comments about sorting the
master public keys and then using the same order for all derived addresses,
but we couldn't think of any benefits of doing that (I mean, the benefits
of knowing whose public key is which).
- We originally thought we would need a non-hardened version of purpose
for the path, because we needed every party to be able to generate all the
public keys of the others. With the proposed path, is it true that the
cosigners will be able to generate them, by knowing the extended purpose
public key for each copayer? (m/purpose')
- The reason for using separate branches for each cosigner is we don't
want two of them generating the same address and receiving simultaneous
payments to it. The ideal case is that each address receives at most one
payment, requested by the corresponding cosigner.
Thoughts?
Manuel
------------------------------------------------------------------------------
Start Your Social Network Today - Download eXo Platform
Build your Enterprise Intranet with eXo Platform Software
Java Based Open Source Intranet - Social, Extensible, Cloud Ready
Get Started Now And Turn Your Intranet Into A Collaboration Platform
http://p.sf.net/sfu/ExoPlatform
_______________________________________________
Bitcoin-development mailing list
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Thomas Voegtlin]

Post by Mike Hearn
I'm not sure I understand why you need any special structure for this at
all. The way I'd do it is just use regular HD wallets for everyone, of the
regular form, and then swap the watching keys. Why do people need to be
given a cosigner index at all, given that they all have unique root keys
anyway?

I agree with that.

Perhaps the only thing that needs to be standardized is the order of
public keys in the redeem script: I think they should be sorted, so that
the p2sh address does not depend on the order of pubkeys.

[Jeff Garzik]

Post by Thomas Voegtlin
Perhaps the only thing that needs to be standardized is the order of
public keys in the redeem script: I think they should be sorted, so that
the p2sh address does not depend on the order of pubkeys.

Yes. That solution is already implemented in a few wallets.

[Manuel Araoz]

Post by Mike Hearn
I'm not sure I understand why you need any special structure for this at

all. The way I'd do it is just use regular HD wallets for everyone, of the
regular form, and then swap the watching keys. Why do people need to be
given a cosigner index at all, given that they all have unique root keys
anyway?

I tried to explain that here:

The reason for using separate branches for each cosigner is we don't want
two of them generating the same address and receiving simultaneous payments
to it. The ideal case is that each address receives at most one payment,
requested by the corresponding cosigner.

To clarify, the problem the cosigner_index is trying to solve is race
conditions when receiving payments. Remember that we can't assume all
cosigners to be online at all times. Let's assume we use one shared branch
for everyone. Then two cosigners could need a new receiving address at the
same time, and get the next unused address on that branch. They then each
pass the same address to their payers, and we can get two payments to the
same address. Monitoring balances is not enough in this case because a
cosigner can never know when the others are generating a new address.
Separating branches and having each cosigner only use one branch makes this
problem go away.

[Mike Hearn]

Let's assume we use one shared branch for everyone. Then two cosigners
could need a new receiving address at the same time, and get the next
unused address on that branch.

This is the part I struggle to understand. There is no shared branch
because each user/cosigner has their own unique seed and thus unique key
hierarchy, right? What you described above could be an issue if all
co-signers shared the same seed but then the scheme wouldn't work.

[Alan Reiner]

Let's assume we use one shared branch for everyone. Then two
cosigners could need a new receiving address at the same time, and
get the next unused address on that branch.
This is the part I struggle to understand. There is no shared branch
because each user/cosigner has their own unique seed and thus unique
key hierarchy, right? What you described above could be an issue if
all co-signers shared the same seed but then the scheme wouldn't work.

Consider two people with phones, using 2-of-2, using private seeds k1
and k2. Every address generated by either party is:

2-of-2(K1/a'/b/c, K2/a'/b/c)

So for any a, b and c you end up with a 2-of-2 address. The
seeds/branches will not be used for single-sig receiving... it's always
a multisig 2-of-2. In fact it behaves much like a regular wallet, you
give an a, b, and c value, and you get an address -- it's just that this
wallet always gives you a P2SH multisig address.

The problem is that if you follow BIP32 in the the most obvious way,
both devices will generate receiving addresses along the last index,
i.e. K/a'/b/0, K/a'/b/1, K/a'/b/2,... If I am at one store and my
wife at another, we might both give out 2-of-2(K1/a'/b/382, K2/a'/b/382)
at the same time not realizing the other one has distributed that
address. There's not a good way to coordinate the devices well enough
to avoid it. But we don't have to.

The solution is to use two separate branches -- both phones will
follow/watch both branches, but each only only distributes payment
addresses from one such branch.

The original proposal here suggested adding a level to the tree using
the "cosigner index" as a branch point for doing this... I recommended
simply having 2*N values for "b", so that each participant has a
receiving line and change line, that won't conflict with other devices.
However, all devices will still watch all 2*N branches to know the total
balance of the wallet, and will use UTXOs from those branches when
constructing spending transactions/proposals.

[Mike Hearn]

Ah, I see now. Thanks. And actually now I re-read it, Manuel's explanation
was clear, it just didn't sink in for some reason.

[Jean-Pierre Rupp via bitcoin-dev]

Hello,

I have been reviewing BIP-45 today. There is a privacy problem with it
that should at least be mentioned in the document.

When using the same extended public key for all multisig activity, and
dealing with different cosigners in separate multisig accounts, reuse of
the same set of public keys means that all cosigners from all accounts
will be able to monitor multisig activity from every other cosigner, in
every other account.

Besides privacy considerations, HD wallet's non-reuse of public keys
provide some defence against wallets that do not implement deterministic
signing, and use poor entropy for signature nonces.

Unless users are expected to establish a single cosigning account, this
scheme will result in reuse of public keys, and degradation of privacy.

I understand that for convenience it is useful to have a single extended
public key that can be handed to every cosigner. This makes setting up
accounts or recovering from data loss a easier.

I suggest that privacy & potential security degradation due to increased
public key reuse in the case of users with multiple multisig accounts
should get a mention in the BIP-45 document.

Greetings

Post by Manuel Araoz
Hi, I'm part of the team building copay
<https://github.com/bitpay/copay>, a multisignature P2SH HD
wallet. We've been following the discussion regarding standardizing the
structure for branches both on this list and on github (1
<https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki>, 2
<https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki>, 3
<https://github.com/bitcoin/bips/blob/master/bip-0043.mediawiki>, 4
<https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki>, 5
<https://github.com/bitcoin/bips/pull/52>). Soon, we realized the
assumptions in the discussions were not true for a multisig hd wallet,
so we wanted to share our current approach to that, to get feedback and
see if we can arrive to a new standard (and possibly a new BIP)
- N parties want to share an m-of-n wallet.
- Each party must generate their master private keys independently.
- Use multisig P2SH for all addresses.
- Use BIP32 to derive public keys, then create a multisig script, and
use the P2SH address for that.
- The address generation process should not require communicating with
other parties. (Thus, all parties must be able to generate all public keys)
- Transaction creation + signing requires communication between
parties, of course.
-------------------------------------------------
m / purpose' / *
where /purpose/ is the hardened derivation scheme based on the new BIP
number.
m / purpose' / cosigner_index / change / address_index
/cosigner_index/ <http://en.wikipedia.org/wiki/Co-signing>: the index of
the party creating this address. The indices can be determined
independently by lexicographically sorting the master public keys of
each cosigner.
/change/: 0 for change, 1 for receive address.
/address_index/: Addresses are numbered from index 0 in sequentially
increasing manner. We're currently syncing the max used index for each
branch between all parties when they connect, but we're open to
considering removing the index sync and doing the more elegant
used-address discovery via a gap limit, as discussed in BIP44
<https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki#address-gap-limit>.
We feel 20 might be too low though.
*Wallet high-level description:*
Each party generates their own extended master keypair and shares the
extended purpose' public key with the others, which is stored encrypted.
Each party can generate any of the other's derived public keys, but only
his own private keys.
*General address generation procedure:*
When generating an address, each party can independently generate the N
needed public keys. They do this by deriving the public key in each of
the different trees, but using the same path. They can then generate the
multisig script and the corresponding p2sh address. In this way, each
path corresponds to an address, but the public keys for that address
come from different trees.
*Receive address case:*
Each cosigner generates addresses only on his own branch. One of the n
cosigners wants to receive a payment, and the others are offline. He
knows the last used index in his own branch, because only he generates
addresses there. Thus, he can generate the public keys for all of the
others using the next index, and calculate the needed script for the
address.
/Example: /Cosigner #2 wants to receive a payment to the shared wallet.
His last used index on his own branch is 4. Then, the path for the next
receive address is m/$purpose/2/1/5. He uses this same path in all of
the cosigners trees to generate a public key for each one, and from that
he gets the new p2sh address.
*Change address case:*
Again, each cosigner generates addresses only on his own branch. One of
the n cosigners wants to create an outgoing payment, for which he'll
need a change address. He generates a new address using the same
procedure as above, but using a separate index to track the used change
addresses.
/
Example: /Cosigner #5 wants to send a payment from the shared wallet,
for which he'll need a change address. His last used change index on his
own branch is 11. Then, the path for the next change address is
m/$purpose/5/0/12. He uses this same path in all of the cosigners trees
to generate a public key for each one, and from that he gets the new
p2sh address.
*Transaction creation and signing:*
When creating a transaction, first one of the parties creates a
Transaction Proposal. This is a transaction that spends some output
stored in any of the p2sh multisig addresses (corresponding to any of
the copayers' branches). This proposal is sent to the other parties, who
decide if they want to sign. If they approve the proposal, they can
generate their needed private key for that specific address (using the
same path that generated the public key in that address, but deriving
the private key instead), and sign it. Once the proposal reaches m
signatures, any cosigner can broadcast it to the network, becoming
final. The specifics of how this proposal is structured, and the
protocol to accept or reject it, belong to another BIP, in my opinion.
*Final comments:*
- We're currently lexicographically sorting the public keys for each
address separately. We've read Mike Belshe's comments about sorting the
master public keys and then using the same order for all derived
addresses, but we couldn't think of any benefits of doing that (I mean,
the benefits of knowing whose public key is which).
- We originally thought we would need a non-hardened version of purpose
for the path, because we needed every party to be able to generate all
the public keys of the others. With the proposed path, is it true that
the cosigners will be able to generate them, by knowing the extended
purpose public key for each copayer? (m/purpose')
- The reason for using separate branches for each cosigner is we don't
want two of them generating the same address and receiving simultaneous
payments to it. The ideal case is that each address receives at most one
payment, requested by the corresponding cosigner.
Thoughts?
Manuel
------------------------------------------------------------------------------
Start Your Social Network Today - Download eXo Platform
Build your Enterprise Intranet with eXo Platform Software
Java Based Open Source Intranet - Social, Extensible, Cloud Ready
Get Started Now And Turn Your Intranet Into A Collaboration Platform
http://p.sf.net/sfu/ExoPlatform
_______________________________________________
Bitcoin-development mailing list
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Jean-Pierre Rupp via bitcoin-dev]

I have a possible solution:

Take all public keys encoded in the purpose-specific extended public
keys (m/45') of all cosigners and sort them lexicographically, according
to BIP-45. Serialize this information and calculate its HASH160
(RIPEMD160 ∘ HASH256). Split the output in five 32-bit chunks, setting
the MSB on all of them to 0. Use these 32-bit chunks to build a
derivation path from the purpose-specific extended public keys. Treat
this derivation path as if it was the purpose-specific extended public
key in BIP-45.

This scheme will avoid public key sharing, and as long as you share your
purpose-specific extended public key only with your cosigners, it should
be relatively hard for a passive observer to link activity between
different cosigning accounts.

Post by Jean-Pierre Rupp via bitcoin-dev
Hello,
I have been reviewing BIP-45 today. There is a privacy problem with it
that should at least be mentioned in the document.
When using the same extended public key for all multisig activity, and
dealing with different cosigners in separate multisig accounts, reuse of
the same set of public keys means that all cosigners from all accounts
will be able to monitor multisig activity from every other cosigner, in
every other account.
Besides privacy considerations, HD wallet's non-reuse of public keys
provide some defence against wallets that do not implement deterministic
signing, and use poor entropy for signature nonces.
Unless users are expected to establish a single cosigning account, this
scheme will result in reuse of public keys, and degradation of privacy.
I understand that for convenience it is useful to have a single extended
public key that can be handed to every cosigner. This makes setting up
accounts or recovering from data loss a easier.
I suggest that privacy & potential security degradation due to increased
public key reuse in the case of users with multiple multisig accounts
should get a mention in the BIP-45 document.
Greetings

[Thomas Kerin via bitcoin-dev]

Hi Jean Pierre,

This is a problem I've considered before, though I have to say I prefer
your solution.

The problem is, how can a person who restores his wallet from just a
seed restore
all his multi-signature addresses with other parties?

Your proposal is nice because all participants are equal, and it
minimalizes the data
required for recovery because it's deterministic, and the (extended)
public key is the first
piece of metadata you'll ask for from others.. Let it be the only thing
we need!

Regards amending BIP45 - BIP's are not amended after the fact, however
bad it may be
in retrospect. It might be best to write a BIP specifying a
"pseudorandom & deterministic
path generation for HD/multi-signature accounts"

TK

Post by Jean-Pierre Rupp via bitcoin-dev
Take all public keys encoded in the purpose-specific extended public
keys (m/45') of all cosigners and sort them lexicographically, according
to BIP-45. Serialize this information and calculate its HASH160
(RIPEMD160 ∘ HASH256). Split the output in five 32-bit chunks, setting
the MSB on all of them to 0. Use these 32-bit chunks to build a
derivation path from the purpose-specific extended public keys. Treat
this derivation path as if it was the purpose-specific extended public
key in BIP-45.
This scheme will avoid public key sharing, and as long as you share your
purpose-specific extended public key only with your cosigners, it should
be relatively hard for a passive observer to link activity between
different cosigning accounts.

Post by Jean-Pierre Rupp via bitcoin-dev
Hello,
I have been reviewing BIP-45 today. There is a privacy problem with it
that should at least be mentioned in the document.
When using the same extended public key for all multisig activity, and
dealing with different cosigners in separate multisig accounts, reuse of
the same set of public keys means that all cosigners from all accounts
will be able to monitor multisig activity from every other cosigner, in
every other account.
Besides privacy considerations, HD wallet's non-reuse of public keys
provide some defence against wallets that do not implement deterministic
signing, and use poor entropy for signature nonces.
Unless users are expected to establish a single cosigning account, this
scheme will result in reuse of public keys, and degradation of privacy.
I understand that for convenience it is useful to have a single extended
public key that can be handed to every cosigner. This makes setting up
accounts or recovering from data loss a easier.
I suggest that privacy & potential security degradation due to increased
public key reuse in the case of users with multiple multisig accounts
should get a mention in the BIP-45 document.
Greetings

_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

- --
My PGP key can be found here: <https://thomaskerin.io/me.pub.asc>

[Matias Alejo Garcia via bitcoin-dev]

Hi,

Post by Jean-Pierre Rupp via bitcoin-dev
I have been reviewing BIP-45 today. There is a privacy problem with it
that should at least be mentioned in the document.
When using the same extended public key for all multisig activity, and
dealing with different cosigners in separate multisig accounts, reuse of
the same set of public keys means that all cosigners from all accounts
will be able to monitor multisig activity from every other cosigner, in
every other account.

I am not completely sure what you mean by 'account' and 'mutisig activity'.
You seem to imply
that the same set of extended public keys will be used in more that one
wallet, which it is
not required (and certainly not recommended) by BIP45.

According to BIP45, a singing party, in order to generate a wallet address,
needs the extended public keys of all the other parties, so each party will
be able to see the transaction history of the wallet they are sharing, but
if the party has other wallets with other copayers the xpub should be
completely different.

matías

[Jean-Pierre Rupp via bitcoin-dev]

When I talk about multisig account I mean an arrangement among a set of
cosigners to be signatories of multi-signature transactions requiring a
set number of signatures, as specified in BIP-45.

Example:

Juan: xpub123...
Pedro: xpub456...
José: xpub789...

They all agree to create a 2-of-3 multisig “account” following BIP-45.
Their extended public keys are all path m/45' from their wallet’s master
private key, as per the standard.

Perhaps Pedro wants to also participate in a 2-of-2 cosigning
arrangement with a merchant that will deliver a laptop to him, so Pedro
provides this merchant with the same extended public key derived from
path m/45', and the merchant provides Pedro with his own:

Pedro: xpub456...
ElCheapoPC: xpub987...

Now, suppose that the first cosigner[1] in each of the accounts
generates a set of public keys for a multisig redeem script to obtain a
P2SH address from. The derivation path m/45'/0/0/1 is used as per
BIP-45. Pedro’s public key for that address in each account will be the
same.

Every cosigner’s address public key is obtained following the same
derivation path from the cosigner’s master key, therefore, it is easy to
know what public keys Pedro is likely to use in both 2-of-3 account
{Juan, Pedro, José} and 2-of-2 account {Pedro, ElCheapoPC}, by only
knowing Pedro’s m/45' purpose-specific extended public key. By scanning
the blockchain for Pedro’s public keys, José can see that Pedro had a
2-of-2 multi-signature arrangement with somebody else (ElCheapoPC),
although he does not necessarily know its identity, and how much money
was transacted in that arrangement, without having to know the extended
public key from ElCheapoPC.

By adopting the scheme I proposed earlier as an improvement, cosigners
with Pedro would have to know ElCheapoPC’s extended public key in order
to eavesdrop on any transaction between Pedro and ElCheapoPC.

[1] According to lexicographic order of serialized public keys contained
in each of the xpubs, as per BIP-45 specification.

Post by Jean-Pierre Rupp via bitcoin-dev
Hi,

Post by Jean-Pierre Rupp via bitcoin-dev
I have been reviewing BIP-45 today. There is a privacy problem

with it

Post by Jean-Pierre Rupp via bitcoin-dev
that should at least be mentioned in the document.
When using the same extended public key for all multisig

activity, and

Post by Jean-Pierre Rupp via bitcoin-dev
dealing with different cosigners in separate multisig accounts,

reuse of

Post by Jean-Pierre Rupp via bitcoin-dev
the same set of public keys means that all cosigners from all

accounts

Post by Jean-Pierre Rupp via bitcoin-dev
will be able to monitor multisig activity from every other

cosigner, in

Post by Jean-Pierre Rupp via bitcoin-dev
every other account.

I am not completely sure what you mean by 'account' and 'mutisig
activity'. You seem to imply
that the same set of extended public keys will be used in more that one
wallet, which it is
not required (and certainly not recommended) by BIP45.
According to BIP45, a singing party, in order to generate a wallet
address, needs the extended public keys of all the other parties, so
each party will be able to see the transaction history of the wallet
they are sharing, but if the party has other wallets with other copayers
the xpub should be completely different.
matías
--
BitPay.com

[Jonas Schnelli via bitcoin-dev]

Post by Jean-Pierre Rupp via bitcoin-dev
Perhaps Pedro wants to also participate in a 2-of-2 cosigning
arrangement with a merchant that will deliver a laptop to him, so
Pedro provides this merchant with the same extended public key
derived from path m/45', and the merchant provides Pedro with his

What holds you back from using m/i'/45' where i' is your multisig
"account" number?

Within your BIP45 wallet (lets assume Copay), you would not provide
the xpubkey at m/45', instead you would provide your xpubkey at m/i'/45'
.

It's probably no longer pure BIP45.

[Jean-Pierre Rupp via bitcoin-dev]

Sure,

You always have these alternatives, but the problem is that it starts to
become harder to restore your wallet from the initial mnemonic if
something goes wrong.

Say you lose all your wallet information except for your mnemonic,
extended public keys from all people you established multi-signature
accounts with, and you know which arrangement you had with each of your
cosigners (2-of-3, 2-of-2, etc.). Your software will not have a hard
time rebuilding all accounts from information obtained from the public
blockchain. Adding a new dimension, here the i' derivation, will make
things harder. You would need to know this piece of data too.

Another good thing about using the same derivation always is that you
can give every cosigner only that single piece of information, that
single xpub, in order to establish multisig relationships. There is no
need to use a different one per relationship. This simplifies the
workflow for establishing new multi-signature accounts significantly.

Greetings

Post by Jonas Schnelli via bitcoin-dev
What holds you back from using m/i'/45' where i' is your multisig
"account" number?
Within your BIP45 wallet (lets assume Copay), you would not provide
the xpubkey at m/45', instead you would provide your xpubkey at m/i'/45'
.
It's probably no longer pure BIP45.

[Matias Alejo Garcia via bitcoin-dev]

Post by Jean-Pierre Rupp via bitcoin-dev
Perhaps Pedro wants to also participate in a 2-of-2 cosigning
arrangement with a merchant that will deliver a laptop to him, so Pedro
provides this merchant with the same extended public key derived from
Pedro: xpub456...
ElCheapoPC: xpub987...

Thanks for the explanation. OK, maybe that should be stated on BIP45, but
it was never the idea that you reuse your xpub for different wallet, as I
mention
on the original reply. The only implementation of BIP45 I am aware of
(Copay),
use completely different xprivs for each wallet.

Post by Jean-Pierre Rupp via bitcoin-dev

Post by Jean-Pierre Rupp via bitcoin-dev
Hi,

Post by Jean-Pierre Rupp via bitcoin-dev
I have been reviewing BIP-45 today. There is a privacy problem

with it

Post by Jean-Pierre Rupp via bitcoin-dev
that should at least be mentioned in the document.
When using the same extended public key for all multisig

activity, and

Post by Jean-Pierre Rupp via bitcoin-dev
dealing with different cosigners in separate multisig accounts,

reuse of

Post by Jean-Pierre Rupp via bitcoin-dev
the same set of public keys means that all cosigners from all

accounts

Post by Jean-Pierre Rupp via bitcoin-dev
will be able to monitor multisig activity from every other

cosigner, in

Post by Jean-Pierre Rupp via bitcoin-dev
every other account.

I am not completely sure what you mean by 'account' and 'mutisig
activity'. You seem to imply
that the same set of extended public keys will be used in more that one
wallet, which it is
not required (and certainly not recommended) by BIP45.
According to BIP45, a singing party, in order to generate a wallet
address, needs the extended public keys of all the other parties, so
each party will be able to see the transaction history of the wallet
they are sharing, but if the party has other wallets with other copayers
the xpub should be completely different.
matías
--
BitPay.com

[Jean-Pierre Rupp via bitcoin-dev]

Let’s do this.

Post by Thomas Kerin via bitcoin-dev
Regards amending BIP45 - BIP's are not amended after the fact, however
bad it may be
in retrospect. It might be best to write a BIP specifying a
"pseudorandom & deterministic
path generation for HD/multi-signature accounts"