path: root/62/3d7c3e9b6293fdfd9ec9171a0ed59a919e6a26

Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
	helo=mx.sourceforge.net)
	by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <etotheipi@gmail.com>) id 1Wdssn-0000wd-Az
	for bitcoin-development@lists.sourceforge.net;
	Sat, 26 Apr 2014 03:02:29 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.216.44 as permitted sender)
	client-ip=209.85.216.44; envelope-from=etotheipi@gmail.com;
	helo=mail-qa0-f44.google.com; 
Received: from mail-qa0-f44.google.com ([209.85.216.44])
	by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1Wdssl-0006cN-Lr
	for bitcoin-development@lists.sourceforge.net;
	Sat, 26 Apr 2014 03:02:29 +0000
Received: by mail-qa0-f44.google.com with SMTP id hw13so4428341qab.31
	for <bitcoin-development@lists.sourceforge.net>;
	Fri, 25 Apr 2014 20:02:22 -0700 (PDT)
X-Received: by 10.224.47.8 with SMTP id l8mr16805831qaf.24.1398481342240;
	Fri, 25 Apr 2014 20:02:22 -0700 (PDT)
Received: from [192.168.1.85] (c-76-111-96-126.hsd1.md.comcast.net.
	[76.111.96.126])
	by mx.google.com with ESMTPSA id v9sm17980803qav.28.2014.04.25.20.02.21
	for <bitcoin-development@lists.sourceforge.net>
	(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
	Fri, 25 Apr 2014 20:02:21 -0700 (PDT)
Message-ID: <535B21BD.1080503@gmail.com>
Date: Fri, 25 Apr 2014 23:02:21 -0400
From: Alan Reiner <etotheipi@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
	rv:24.0) Gecko/20100101 Thunderbird/24.4.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <CABQSq2Q98K5zbUbQAqSE4OYez2QuOaWTt+9n5iZmSR2boynf_Q@mail.gmail.com>
In-Reply-To: <CABQSq2Q98K5zbUbQAqSE4OYez2QuOaWTt+9n5iZmSR2boynf_Q@mail.gmail.com>
X-Enigmail-Version: 1.6
Content-Type: multipart/alternative;
	boundary="------------050600020908080809070701"
X-Spam-Score: -0.6 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
	See http://spamassassin.org/tag/ for more details.
	-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
	sender-domain
	0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
	(etotheipi[at]gmail.com)
	-0.0 SPF_PASS               SPF: sender matches SPF record
	1.0 HTML_MESSAGE           BODY: HTML included in message
	-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
	author's domain
	0.1 DKIM_SIGNED            Message has a DKIM or DK signature,
	not necessarily valid
	-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1Wdssl-0006cN-Lr
Subject: Re: [Bitcoin-development] New BIP32 structure for P2SH multisig
	wallets
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Sat, 26 Apr 2014 03:02:29 -0000

This is a multi-part message in MIME format.
--------------050600020908080809070701
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

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


--------------050600020908080809070701
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

<html>
  <head>
    <meta content="text/html; charset=ISO-8859-1"
      http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    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.&nbsp; I think you covered most of what is needed.&nbsp;&nbsp; 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.&nbsp; It's not necessary, but it follows more
    closely the three-level scheme that BIP 32 originally envisioned.&nbsp; I
    also concluded that the chain indices are ordered by lexicographical
    sorting of root public keys, but resorting each individual address.&nbsp;
    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.<br>
    <br>
    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.&nbsp; 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.&nbsp; This allows
    lightweight devices like hardware wallets, to recognize their own
    keys.&nbsp; 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.&nbsp; If so, it can sign it.&nbsp; If not, it must be
    someone else's.<br>
    <br>
    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.&nbsp;
    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.&nbsp; <br>
    <br>
    -Alan<br>
    <br>
    <br>
    <br>
    <br>
    <div class="moz-cite-prefix">On 04/25/2014 06:27 PM, Manuel Araoz
      wrote:<br>
    </div>
    <blockquote
cite="mid:CABQSq2Q98K5zbUbQAqSE4OYez2QuOaWTt+9n5iZmSR2boynf_Q@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div>Hi, I'm part of the team building <a
            moz-do-not-send="true"
            href="https://github.com/bitpay/copay" target="_blank">copay</a>,
          a multisignature P2SH HD wallet.&nbsp;We've been following the
          discussion regarding standardizing the structure for branches
          both on this list and on github (<a moz-do-not-send="true"
            href="https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki"
            target="_blank">1</a>, <a moz-do-not-send="true"
            href="https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki"
            target="_blank">2</a>, <a moz-do-not-send="true"
            href="https://github.com/bitcoin/bips/blob/master/bip-0043.mediawiki"
            target="_blank">3</a>, <a moz-do-not-send="true"
            href="https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki"
            target="_blank">4</a>, <a moz-do-not-send="true"
            href="https://github.com/bitcoin/bips/pull/52"
            target="_blank">5</a>). 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)</div>
        <div><br>
        </div>
        <div>These are our assumptions:&nbsp;</div>
        <div>&nbsp;- N parties want to share an m-of-n wallet.</div>
        <div>&nbsp;- Each party must generate their master private keys
          independently.</div>
        <div>&nbsp;- Use multisig P2SH for all addresses.</div>
        <div>&nbsp;- Use BIP32 to derive public keys, then create a multisig
          script, and use the P2SH address for that.</div>
        <div>&nbsp;- The address generation process should not require
          communicating with other parties. (Thus, all parties must be
          able to generate all public keys)</div>
        <div>&nbsp;- Transaction creation + signing requires communication
          between parties, of course.</div>
        <div><br>
        </div>
        <div>-------------------------------------------------</div>
        <div><br>
        </div>
        <div>Following BIP43, we're be using:</div>
        <div>
          <pre style="font-family:Consolas,'Liberation Mono',Courier,monospace;font-size:13px;margin-top:15px;margin-bottom:15px;background-color:rgb(248,248,248);border:1px solid rgb(221,221,221);line-height:19px;overflow:auto;padding:6px 10px;border-top-left-radius:3px;border-top-right-radius:3px;border-bottom-right-radius:3px;border-bottom-left-radius:3px;word-wrap:normal;color:rgb(51,51,51)">
m / purpose' / *</pre>
        </div>
        where <i>purpose</i> is the hardened derivation scheme based on
        the new BIP number.<br>
        <div>We then define the following levels:</div>
        <div>
          <pre style="font-family:Consolas,'Liberation Mono',Courier,monospace;font-size:13px;margin-top:15px;margin-bottom:15px;background-color:rgb(248,248,248);border:1px solid rgb(221,221,221);line-height:19px;overflow:auto;padding:6px 10px;border-top-left-radius:3px;border-top-right-radius:3px;border-bottom-right-radius:3px;border-bottom-left-radius:3px;word-wrap:normal;color:rgb(51,51,51)">
m / purpose' / cosigner_index / change / address_index</pre>
        </div>
        <div>Each level has a special meaning detailed below:</div>
        <div><br>
        </div>
        <div><a moz-do-not-send="true"
            href="http://en.wikipedia.org/wiki/Co-signing"
            target="_blank"><i>cosigner_index</i></a>: the index of the
          party creating this address. The indices can be determined
          independently by lexicographically sorting the master public
          keys of each cosigner.</div>
        <div><br>
        </div>
        <div><i>change</i>: 0 for change, 1 for receive address.</div>
        <div><br>
        </div>
        <div><i>address_index</i>:&nbsp;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, <a moz-do-not-send="true"
href="https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki#address-gap-limit"
            target="_blank">as discussed in BIP44</a>. We feel 20 might
          be too low though.&nbsp;</div>
        <div><br>
        </div>
        <div><b>Wallet high-level description:</b></div>
        <div>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.&nbsp;</div>
        <div><br>
          <div><b>General address generation procedure:</b></div>
          <div>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.</div>
          <div><br>
          </div>
          <div><b>Receive address case:</b></div>
          <div>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.&nbsp;</div>
          <div><br>
          </div>
          <div><i>Example: </i>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.</div>
          <div><br>
          </div>
          <div><b>Change address case:</b></div>
          <div>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.&nbsp;</div>
          <div><i><br>
              Example:&nbsp;</i>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.</div>
          <div><br>
          </div>
          <div><br>
          </div>
          <div><b>Transaction creation and signing:</b></div>
          <div>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.&nbsp;</div>
          <div><br>
          </div>
          <div><b>Final comments:</b></div>
          <div>- 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).</div>
          <div>- 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')</div>
        </div>
        <div>- 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.&nbsp;</div>
        <div><br>
        </div>
        <div><br>
        </div>
        <div>Thoughts?<br>
          Manuel</div>
      </div>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">------------------------------------------------------------------------------
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
<a class="moz-txt-link-freetext" href="http://p.sf.net/sfu/ExoPlatform">http://p.sf.net/sfu/ExoPlatform</a></pre>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">_______________________________________________
Bitcoin-development mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-development@lists.sourceforge.net</a>
<a class="moz-txt-link-freetext" href="https://lists.sourceforge.net/lists/listinfo/bitcoin-development">https://lists.sourceforge.net/lists/listinfo/bitcoin-development</a>
</pre>
    </blockquote>
    <br>
  </body>
</html>

--------------050600020908080809070701--