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

2014-04-27 Thread Jeff Garzik
On Sat, Apr 26, 2014 at 6:08 AM, Thomas Voegtlin thoma...@gmx.de wrote:
 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.

-- 
Jeff Garzik
Bitcoin core developer and open source evangelist
BitPay, Inc.  https://bitpay.com/

--
Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
Instantly run your Selenium tests across 300+ browser/OS combos.  Get 
unparalleled scalability from the best Selenium testing platform available.
Simple to use. Nothing to install. Get started now for free.
http://p.sf.net/sfu/SauceLabs
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


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

2014-04-26 Thread 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?


On Sat, Apr 26, 2014 at 12:27 AM, Manuel Araoz m...@bitpay.com wrote:

 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, 
 3https://github.com/bitcoin/bips/blob/master/bip-0043.mediawiki,
 4 https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki, 
 5https://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 
 BIP44https://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 

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

2014-04-26 Thread Thomas Voegtlin


Le 26/04/2014 11:43, Mike Hearn a ├ęcrit :
 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.


--
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


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

2014-04-26 Thread Manuel Araoz
On Apr 26, 2014 6:43 AM, Mike Hearn m...@plan99.net wrote:

 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.
--
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


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

2014-04-26 Thread 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.
--
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


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

2014-04-26 Thread Alan Reiner

On 04/26/2014 04:33 PM, Mike Hearn wrote:

 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.
--
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


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

2014-04-26 Thread 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.
--
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


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

2014-04-25 Thread 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,
3https://github.com/bitcoin/bips/blob/master/bip-0043.mediawiki,
4 https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki,
5https://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
BIP44https://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 

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

2014-04-25 Thread 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




On 04/25/2014 06:27 PM, Manuel Araoz wrote:
 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