New BIP32 structure for P2SH multisig wallets
18 messages, 25 Apr 2014 to 5 Oct 2015. Started by Manuel Araoz.
Jean-Pierre Rupp (5), Mike Hearn (3), Manuel Araoz (2), Alan Reiner (2), Matias Alejo Garcia (2), Thomas Voegtlin, Jeff Garzik, Thomas Kerin, +1 more
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
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
On 04/25/2014 06:27 PM, Manuel Araoz wrote:
Quoted text (140 lines)
> 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 > > > ------------------------------------------------------------------------------ > 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 > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
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?
On Sat, Apr 26, 2014 at 12:27 AM, Manuel Araoz <manu@bitpay•com> wrote:
Quoted text (139 lines)
> 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 > > > ------------------------------------------------------------------------------ > 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 > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > >
Le 26/04/2014 11:43, Mike Hearn a écrit :
Quoted text (7 lines)
> 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.
On Apr 26, 2014 6:43 AM, "Mike Hearn" <mike@plan99•net> wrote:
Quoted text (2 lines)
> > 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.
Quoted text (5 lines)
> > 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.
On 04/26/2014 04:33 PM, Mike Hearn wrote:
Quoted text (10 lines)
> > 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.
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.
On Sat, Apr 26, 2014 at 6:08 AM, Thomas Voegtlin <thomasv1@gmx•de> wrote:
Quoted text (3 lines)
> 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.
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
On 25/04/14 23:27, Manuel Araoz wrote:
Quoted text (146 lines)
> 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 > > > ------------------------------------------------------------------------------ > 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 > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development >
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.
On 03/10/15 13:42, Jean-Pierre Rupp via bitcoin-dev wrote:
Quoted text (27 lines)
> 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
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
On 04/10/15 16:18, Jean-Pierre Rupp via bitcoin-dev wrote:
Quoted text (48 lines)
> 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. > > On 03/10/15 13:42, Jean-Pierre Rupp via bitcoin-dev wrote: >> 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 > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
- -- My PGP key can be found here: <https://thomaskerin.io/me.pub.asc>
Hi,
Sorry the late response. Going back to the original message:
Quoted text (10 lines)
> > On 03/10/15 13:42, Jean-Pierre Rupp via bitcoin-dev wrote: > >> 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
Let’s do this.
On 04/10/15 18:24, Thomas Kerin wrote:
Quoted text (5 lines)
> 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"
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.
On 05/10/15 07:57, Matias Alejo Garcia wrote:
Quoted text (40 lines)
> > Hi, > > Sorry the late response. Going back to the original message: > > > > On 03/10/15 13:42, Jean-Pierre Rupp via bitcoin-dev wrote: > >> 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 > > > > -- > BitPay.com
Quoted text (5 lines)
> 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:
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.
On Mon, Oct 5, 2015 at 9:18 AM, Jean-Pierre Rupp <root@haskoin•com> wrote:
Quoted text (9 lines)
> > 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... >
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.
Quoted text (43 lines)
> > On 05/10/15 07:57, Matias Alejo Garcia wrote: > > > > Hi, > > > > Sorry the late response. Going back to the original message: > > > > > > > On 03/10/15 13:42, Jean-Pierre Rupp via bitcoin-dev wrote: > > >> 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 > > > > > > > > -- > > BitPay.com >
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
On 05/10/15 13:32, Jonas Schnelli wrote:
Quoted text (8 lines)
> 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.