[Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 4584 bytes --]

_*Goal*_:  An alternative address format made possible by BIP 32, which
allows one to specify a "Wallet ID" and "One-time payment" code, instead
of the standard one-use Base58-Hash160 addresses.   This allows parties
with a persistent relationship to be able to prove that payment
addresses they provide each other are linked to a particular wallet,
reducing exposure to MitM attacks without the need for SSL or a web of
trust, and without compromising the privacy of either party.    For
instance, this could be used between businesses that frequently do
business, by exchanging and verifying public keys beforehand, or could
be used by an exchange to identify if a customer withdrawal address is
related to their last deposit address, and if not enforce extra
authentication measures.

_*Background*__:_
I haven't been following the payment protocol discussions/development
much, so I apologize if this has already been addressed.   I'm calling
it "wallet-linkable" addresses, which would be an optional second form
for sending someone your address.   With BIP 32, the address is computed
by the payee (the person sending the address to receive money):

   Standard Address ~ Base58(0x00 || hash160(PubKeyParent *
Multiplier[i]) || checksum)

What I'd like to do is have the option, when specifying an address
through the payment protocol, to send *just* the {PublicKeyParent,
Multiplier[i]} and let the receiver of that address compute the address
on their own.  This is no significant burden on the receiver, but it
does provide the useful property that they can recognize when addresses
specified in this way come from the same wallet -- because the
PubKeyParent will be the same.  Remember, this is _optional_ for the
person providing the address.

One nice, accidental feature of BIP 32 is that the Multiplier[i] used
above does not actually reveal the "chaincode" (I think Pieter started
calling it the "tweak").   It is derived from the chaincode but doesn't
reveal it.  Therefore, the payer sees the parent public key, but that's
not useful to derive any of the other addresses unless they also have
the chaincode.  But they can verify that the PublicKeyParent is
identical between transactions, and thus is accessible only to that
wallet.  It allows them validate a specific address provided by the
payee, but not generate or identify any other addresses.

*_Use Cases:_*
(1)  So, just like with PGP/GPG, when two parties decide they will start
a relationship, they can start by exchanging the public keys of their
wallet and verify them in a reliable manner.  After that, when one party
requests a payment address from the other, they can optionally send
{PubKey, Multiplier}, and the payer's software will identify the owner
of that address, or let you select who you think the address belongs to
and it will verify it.  If the payee's system is compromised and address
is replaced, the address received by the payer won't validate.  This
doesn't help if the side sending the money is compromised.

(2)  When a customer first provides a deposit to an exchange, it will
send money from an address in their wallet and the software will provide
the exchange the {PubKey,Mult}.  When the customer later provides a
withdrawal address, the site can automatically trust the address as long
it is provided in the alternate form and the public keys match.  If they
don't, it might be the same customer just requesting a withdrawal to a
different wallet, which is fine, but they'll have to go through an extra
verification step to do so. 


_*Downsides:*_ 
Multi-sig/P2SH  - The only way this works with P2SH, violates one of the
goals of P2SH slightly, but may not matter much if it's all done under
the hood by the software.  Instead of providing a 20-byte hash of a
script, you provide all the public keys and multipliers for the
individual addresses.  The payer's software automatically verifies all
addresses and creates the P2SH script itself (after a divine decree that
public keys will always be sorted lexicographically in the multi-sig
script).  The blockchain still benefits from the "compression" of moving
the bulky scripts to the TxIn, but it does require revealing more
information than is necessary for the payer to pay the payee.  But it
may not /really/ be a problem, given the benefits.  It might just be
slightly longer strings to exchange during initialization and for each
transaction.

I have various reasons I'd like to use this, and it'd be nice to have
some community backing, so I don't have to twist anyone's arm to trust
me that it's legit.

-Alan





[-- Attachment #2: Type: text/html, Size: 5513 bytes --]

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Melvin Carvalho]

[-- Attachment #1: Type: text/plain, Size: 5648 bytes --]

On 18 June 2013 05:48, Alan Reiner <etotheipi@gmail.com> wrote:

>  *Goal*:  An alternative address format made possible by BIP 32, which
> allows one to specify a "Wallet ID" and "One-time payment" code, instead of
> the standard one-use Base58-Hash160 addresses.   This allows parties with a
> persistent relationship to be able to prove that payment addresses they
> provide each other are linked to a particular wallet, reducing exposure to
> MitM attacks without the need for SSL or a web of trust, and without
> compromising the privacy of either party.    For instance, this could be
> used between businesses that frequently do business, by exchanging and
> verifying public keys beforehand, or could be used by an exchange to
> identify if a customer withdrawal address is related to their last deposit
> address, and if not enforce extra authentication measures.
>
> *Background**:*
> I haven't been following the payment protocol discussions/development
> much, so I apologize if this has already been addressed.   I'm calling it
> "wallet-linkable" addresses, which would be an optional second form for
> sending someone your address.   With BIP 32, the address is computed by the
> payee (the person sending the address to receive money):
>
>    Standard Address ~ Base58(0x00 || hash160(PubKeyParent * Multiplier[i])
> || checksum)
>
> What I'd like to do is have the option, when specifying an address through
> the payment protocol, to send *just* the {PublicKeyParent, Multiplier[i]}
> and let the receiver of that address compute the address on their own.
> This is no significant burden on the receiver, but it does provide the
> useful property that they can recognize when addresses specified in this
> way come from the same wallet -- because the PubKeyParent will be the
> same.  Remember, this is *optional* for the person providing the address.
>
> One nice, accidental feature of BIP 32 is that the Multiplier[i] used
> above does not actually reveal the "chaincode" (I think Pieter started
> calling it the "tweak").   It is derived from the chaincode but doesn't
> reveal it.  Therefore, the payer sees the parent public key, but that's not
> useful to derive any of the other addresses unless they also have the
> chaincode.  But they can verify that the PublicKeyParent is identical
> between transactions, and thus is accessible only to that wallet.  It
> allows them validate a specific address provided by the payee, but not
> generate or identify any other addresses.
>
> *Use Cases:*
> (1)  So, just like with PGP/GPG, when two parties decide they will start a
> relationship, they can start by exchanging the public keys of their wallet
> and verify them in a reliable manner.  After that, when one party requests
> a payment address from the other, they can optionally send {PubKey,
> Multiplier}, and the payer's software will identify the owner of that
> address, or let you select who you think the address belongs to and it will
> verify it.  If the payee's system is compromised and address is replaced,
> the address received by the payer won't validate.  This doesn't help if the
> side sending the money is compromised.
>
> (2)  When a customer first provides a deposit to an exchange, it will send
> money from an address in their wallet and the software will provide the
> exchange the {PubKey,Mult}.  When the customer later provides a withdrawal
> address, the site can automatically trust the address as long it is
> provided in the alternate form and the public keys match.  If they don't,
> it might be the same customer just requesting a withdrawal to a different
> wallet, which is fine, but they'll have to go through an extra verification
> step to do so.
>
>
> *Downsides:*
> Multi-sig/P2SH  - The only way this works with P2SH, violates one of the
> goals of P2SH slightly, but may not matter much if it's all done under the
> hood by the software.  Instead of providing a 20-byte hash of a script, you
> provide all the public keys and multipliers for the individual addresses.
> The payer's software automatically verifies all addresses and creates the
> P2SH script itself (after a divine decree that public keys will always be
> sorted lexicographically in the multi-sig script).  The blockchain still
> benefits from the "compression" of moving the bulky scripts to the TxIn,
> but it does require revealing more information than is necessary for the
> payer to pay the payee.  But it may not *really* be a problem, given the
> benefits.  It might just be slightly longer strings to exchange during
> initialization and for each transaction.
>
> I have various reasons I'd like to use this, and it'd be nice to have some
> community backing, so I don't have to twist anyone's arm to trust me that
> it's legit.
>

Generally in favour of hierarchical deterministic wallets.

Will this new style of address make it into the block chain?  I'd be less
keen on that.

I'm finding BIP0032 quite hard to read right now, but perhaps that's
because I'm less familiar with the material than some.  However, there's
little things like it never actually defines a deterministic wallet in the
Abstract.  But, I'll keep trying to understand and see if I can use the
test vectors.


>
> -Alan
>
>
>
>
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Windows:
>
> Build for Windows Store.
>
> http://p.sf.net/sfu/windows-dev2dev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>

[-- Attachment #2: Type: text/html, Size: 7320 bytes --]

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 1281 bytes --]

On 06/19/2013 08:19 AM, Melvin Carvalho wrote:
>
> Generally in favour of hierarchical deterministic wallets.
>
> Will this new style of address make it into the block chain?  I'd be
> less keen on that.
>
> I'm finding BIP0032 quite hard to read right now, but perhaps that's
> because I'm less familiar with the material than some.  However,
> there's little things like it never actually defines a deterministic
> wallet in the Abstract.  But, I'll keep trying to understand and see
> if I can use the test vectors.
>  
>
>

This has nothing to do with the blockchain.  This is simply an alternate
way to encode an address, in the event that you want to prove that this
address is linked to another address.  The same thing ends up in the
blockchain, either way.

Either:
(1) I give you a Hash160 address which shows up in the blockchain
or
(2) I give you {PubKey, Mult}, then you compute PubKey*Mult then hash it
to get the same Hash160 I would've given you in (1)

I can always give you version #1, and that's what everyone does right
now.  Version #2 is essentially the same, but used if you want to give
the other party extra information (such as the root public key, so that
the next time you send a version#2 address they can see they are from
the same root public key). 

[-- Attachment #2: Type: text/html, Size: 2415 bytes --]

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Pieter Wuille]

On Mon, Jun 17, 2013 at 11:48:22PM -0400, Alan Reiner wrote:
> _*Goal*_:  An alternative address format made possible by BIP 32, which
> allows one to specify a "Wallet ID" and "One-time payment" code, instead
> of the standard one-use Base58-Hash160 addresses.   This allows parties
> with a persistent relationship to be able to prove that payment
> addresses they provide each other are linked to a particular wallet,
> reducing exposure to MitM attacks without the need for SSL or a web of
> trust, and without compromising the privacy of either party.    For
> instance, this could be used between businesses that frequently do
> business, by exchanging and verifying public keys beforehand, or could
> be used by an exchange to identify if a customer withdrawal address is
> related to their last deposit address, and if not enforce extra
> authentication measures.

Have you seen Timo Hanke's pay-to-contract presentation at the San Jose
conference? It seems very related:

  http://www.youtube.com/watch?v=qwyALGlG33Q

-- 
Pieter

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Timo Hanke]

Since you mention to use this in conjunction with the payment protocol,
note the following subtlety. Suppose the payer has to paid this address
called "destination": 
>    Standard Address ~ Base58(0x00 || hash160(PubKeyParent * Multiplier[i]) ||
> checksum)
Also suppose the payee has spent the output, i.e. the pubkey
corresponding to "destination", which is PubKeyParent * Multiplier[i],
is publicly known. Then anybody can (in retrospect) create arbitrary
many pairs {PublicKeyParent, Multiplier} (in particular different
PublicKeyParent) that lead to the same "destination".

Depending on what you have in mind that the transaction should "prove"
regarding its actual receiver or regarding the receiver's PubKeyParent,
this could be an unwanted feature (or it could be just fine). If it is
unwanted then I suggest replacing
PubKeyParent * Multiplier[i] by 
PubKeyParent * HMAC(Multiplier[i],PubKeyParent)
which eliminates from the destination all ambiguity about PubKeyParent.

This modification would not be directly compatible with BIP32 anymore
(unfortunately), but seems to be better suited for use in conjunction
with a payment protocol. 

Timo

On Mon, Jun 17, 2013 at 11:48:22PM -0400, Alan Reiner wrote:
> Goal:  An alternative address format made possible by BIP 32, which allows one
> to specify a "Wallet ID" and "One-time payment" code, instead of the standard
> one-use Base58-Hash160 addresses.   This allows parties with a persistent
> relationship to be able to prove that payment addresses they provide each other
> are linked to a particular wallet, reducing exposure to MitM attacks without
> the need for SSL or a web of trust, and without compromising the privacy of
> either party.    For instance, this could be used between businesses that
> frequently do business, by exchanging and verifying public keys beforehand, or
> could be used by an exchange to identify if a customer withdrawal address is
> related to their last deposit address, and if not enforce extra authentication
> measures.
> 
> Background:
> I haven't been following the payment protocol discussions/development much, so
> I apologize if this has already been addressed.   I'm calling it
> "wallet-linkable" addresses, which would be an optional second form for sending
> someone your address.   With BIP 32, the address is computed by the payee (the
> person sending the address to receive money):
> 
>    Standard Address ~ Base58(0x00 || hash160(PubKeyParent * Multiplier[i]) ||
> checksum)
> 
> What I'd like to do is have the option, when specifying an address through the
> payment protocol, to send *just* the {PublicKeyParent, Multiplier[i]} and let
> the receiver of that address compute the address on their own.  This is no
> significant burden on the receiver, but it does provide the useful property
> that they can recognize when addresses specified in this way come from the same
> wallet -- because the PubKeyParent will be the same.  Remember, this is
> optional for the person providing the address.
> 
> One nice, accidental feature of BIP 32 is that the Multiplier[i] used above
> does not actually reveal the "chaincode" (I think Pieter started calling it the
> "tweak").   It is derived from the chaincode but doesn't reveal it.  Therefore,
> the payer sees the parent public key, but that's not useful to derive any of
> the other addresses unless they also have the chaincode.  But they can verify
> that the PublicKeyParent is identical between transactions, and thus is
> accessible only to that wallet.  It allows them validate a specific address
> provided by the payee, but not generate or identify any other addresses.
> 
> Use Cases:
> (1)  So, just like with PGP/GPG, when two parties decide they will start a
> relationship, they can start by exchanging the public keys of their wallet and
> verify them in a reliable manner.  After that, when one party requests a
> payment address from the other, they can optionally send {PubKey, Multiplier},
> and the payer's software will identify the owner of that address, or let you
> select who you think the address belongs to and it will verify it.  If the
> payee's system is compromised and address is replaced, the address received by
> the payer won't validate.  This doesn't help if the side sending the money is
> compromised.
> 
> (2)  When a customer first provides a deposit to an exchange, it will send
> money from an address in their wallet and the software will provide the
> exchange the {PubKey,Mult}.  When the customer later provides a withdrawal
> address, the site can automatically trust the address as long it is provided in
> the alternate form and the public keys match.  If they don't, it might be the
> same customer just requesting a withdrawal to a different wallet, which is
> fine, but they'll have to go through an extra verification step to do so. 
> 
> 
> Downsides: 
> Multi-sig/P2SH  - The only way this works with P2SH, violates one of the goals
> of P2SH slightly, but may not matter much if it's all done under the hood by
> the software.  Instead of providing a 20-byte hash of a script, you provide all
> the public keys and multipliers for the individual addresses.  The payer's
> software automatically verifies all addresses and creates the P2SH script
> itself (after a divine decree that public keys will always be sorted
> lexicographically in the multi-sig script).  The blockchain still benefits from
> the "compression" of moving the bulky scripts to the TxIn, but it does require
> revealing more information than is necessary for the payer to pay the payee. 
> But it may not really be a problem, given the benefits.  It might just be
> slightly longer strings to exchange during initialization and for each
> transaction.
> 
> I have various reasons I'd like to use this, and it'd be nice to have some
> community backing, so I don't have to twist anyone's arm to trust me that it's
> legit.
> 
> -Alan
> 
> 
> 
> 

-- 
Timo Hanke
PGP 1EFF 69BC 6FB7 8744 14DB  631D 1BB5 D6E3 AB96 7DA8

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Alan Reiner]

On 06/19/2013 10:25 AM, Timo Hanke wrote:
> Since you mention to use this in conjunction with the payment protocol,
> note the following subtlety. Suppose the payer has to paid this address
> called "destination": 
>>    Standard Address ~ Base58(0x00 || hash160(PubKeyParent * Multiplier[i]) ||
>> checksum)
> Also suppose the payee has spent the output, i.e. the pubkey
> corresponding to "destination", which is PubKeyParent * Multiplier[i],
> is publicly known. Then anybody can (in retrospect) create arbitrary
> many pairs {PublicKeyParent, Multiplier} (in particular different
> PublicKeyParent) that lead to the same "destination".
>
> Depending on what you have in mind that the transaction should "prove"
> regarding its actual receiver or regarding the receiver's PubKeyParent,
> this could be an unwanted feature (or it could be just fine). If it is
> unwanted then I suggest replacing
> PubKeyParent * Multiplier[i] by 
> PubKeyParent * HMAC(Multiplier[i],PubKeyParent)
> which eliminates from the destination all ambiguity about PubKeyParent.
>
> This modification would not be directly compatible with BIP32 anymore
> (unfortunately), but seems to be better suited for use in conjunction
> with a payment protocol. 
>
> Timo

It's an interesting observation, but it looks like the most-obvious
attack vector is discrete log problem:  spoofing a relationship between
a target public key and one that you control.   For instance, if you see
{PubA, Mult} produces PubB and you have PubC already in your control
that you want to "prove" [maliciously] is related to PubB, then you have
to find the multiplier, M that solves:  M*PubC = PubB.  That's a
discrete logarithm problem.

I'm not as familiar as you are, with the available operations on
elliptic curves, but it sounds like you can produce essentially-random
pairs of {PubX, Mult} pairs that give the same PubB, but you won't have
the private key associated with those public keys.  It's an interesting
point, and there may be a reason to be concerned about it.  Though, I
don't see it yet.

-Alan

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Adam Back]

I think Timo's point is that while you cant do discrete log, you can do y-th
root.  So if P = xG is a parent public key (x private key, G base point),
then your proposed multiplier address is hash of Q=yP.  However its easy to
find another P such that Q=zP'.  ie just "divide by z" (EC multiply by z^-1
mod n, n the order of the curve).  So P'=z^-1.Q, which will work because
Q=zP', substituting P' you get Q=z.z^-1.Q, Q=Q.

Of course the attacker has just performed an unspenable DoS (maybe, or maybe
a useless collision) because he wont know the discrete log of Q, nor P, nor
P'.  So thats the question, does the protocol have any reliance on knowing
the discrete log - is it a problem if someone can find different multipliers
of different (unknown, uncomputable discrete log) parent keys.

If it was a concern I guess you could require a proof of knowledge of
discrete log.  ie as well as public key parent, multiplier the address must
include ECDSA sig or Schnorr proof of knowledge (which both demonstrate
knowledge of the discrete log of Q to base G.)

So his defense could probably be more simply viewed as hash rather than MAC
(same thing approximately) you provide the pre-image of the multiplier.  So
provide P (public parent), x' (mutiplier pre-image).  And compute Q=xP where
x=H(x',P).  You cant use just x=H(x') because I could choose random x',
compute x=H(x') compute x^-1 and multiply Q to find P'=x^-1.Q=H(x')^-1.Q as
before.  Because x includes P as well, I would have to simultaneously choose
a P' such that Q=H(x',P').P' which requires a birthday attack on the hash
(or MAC).

Adam

On Wed, Jun 19, 2013 at 10:39:04AM -0400, Alan Reiner wrote:
>
>On 06/19/2013 10:25 AM, Timo Hanke wrote:
>> Since you mention to use this in conjunction with the payment protocol,
>> note the following subtlety. Suppose the payer has to paid this address
>> called "destination":
>>>    Standard Address ~ Base58(0x00 || hash160(PubKeyParent * Multiplier[i]) ||
>>> checksum)
>> Also suppose the payee has spent the output, i.e. the pubkey
>> corresponding to "destination", which is PubKeyParent * Multiplier[i],
>> is publicly known. Then anybody can (in retrospect) create arbitrary
>> many pairs {PublicKeyParent, Multiplier} (in particular different
>> PublicKeyParent) that lead to the same "destination".
>>
>> Depending on what you have in mind that the transaction should "prove"
>> regarding its actual receiver or regarding the receiver's PubKeyParent,
>> this could be an unwanted feature (or it could be just fine). If it is
>> unwanted then I suggest replacing
>> PubKeyParent * Multiplier[i] by
>> PubKeyParent * HMAC(Multiplier[i],PubKeyParent)
>> which eliminates from the destination all ambiguity about PubKeyParent.
>>
>> This modification would not be directly compatible with BIP32 anymore
>> (unfortunately), but seems to be better suited for use in conjunction
>> with a payment protocol.
>>
>> Timo
>
>It's an interesting observation, but it looks like the most-obvious
>attack vector is discrete log problem:  spoofing a relationship between
>a target public key and one that you control.   For instance, if you see
>{PubA, Mult} produces PubB and you have PubC already in your control
>that you want to "prove" [maliciously] is related to PubB, then you have
>to find the multiplier, M that solves:  M*PubC = PubB.  That's a
>discrete logarithm problem.
>
>I'm not as familiar as you are, with the available operations on
>elliptic curves, but it sounds like you can produce essentially-random
>pairs of {PubX, Mult} pairs that give the same PubB, but you won't have
>the private key associated with those public keys.  It's an interesting
>point, and there may be a reason to be concerned about it.  Though, I
>don't see it yet.
>
>-Alan
>
>------------------------------------------------------------------------------
>This SF.net email is sponsored by Windows:
>
>Build for Windows Store.
>
>http://p.sf.net/sfu/windows-dev2dev
>_______________________________________________
>Bitcoin-development mailing list
>Bitcoin-development@lists.sourceforge.net
>https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Adam Back]

This maybe simpler and trivially compatible with existing type2 public keys
(ones that are multiples of a parent public key): send an ECDSA signature of
the multiplier, and as we know you can compute ("recover") the parent public
key from an the ECDSA signature made using it.

Adam

On Wed, Jun 19, 2013 at 05:28:15PM +0200, Adam Back wrote:
>[q-th root with unknown no discrete log artefact]
>
>If it was a concern I guess you could require a proof of knowledge of
>discrete log.  ie as well as public key parent, multiplier the address must
>include ECDSA sig or Schnorr proof of knowledge (which both demonstrate
>knowledge of the discrete log of Q to base G.)

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 2825 bytes --]

On 06/19/2013 02:36 PM, Adam Back wrote:
> This maybe simpler and trivially compatible with existing type2 public
> keys
> (ones that are multiples of a parent public key): send an ECDSA
> signature of
> the multiplier, and as we know you can compute ("recover") the parent
> public
> key from an the ECDSA signature made using it.
>
> Adam
>
> On Wed, Jun 19, 2013 at 05:28:15PM +0200, Adam Back wrote:
>> [q-th root with unknown no discrete log artefact]
>>
>> If it was a concern I guess you could require a proof of knowledge of
>> discrete log.  ie as well as public key parent, multiplier the
>> address must
>> include ECDSA sig or Schnorr proof of knowledge (which both demonstrate
>> knowledge of the discrete log of Q to base G.)

It's a cool trick but requiring a signature on each multiplier defeats
one of the purposes of a deterministic wallet.  I don't want to have to
explicitly export a whole bunch of signatures from my offline system
just to exercise this address option.  The "observer wallet" should be
able to do anything it needs to on its own, without help from the
offline wallet. 

Unless you mean that there is a one-time signature from the offline
computer that works for all addresses, that can be exported with the
observer wallet...?  If all you want to do is prove that /someone/ owns
that private key, you could send {Sign(MagicString), Multiplier}.   So
it becomes one signature operation *per wallet*, but creating new
wallets would require going back to the offline computer for that
one-time signature.  That's better than the alternative, but it's still
extra bloat for the wallet apps.

Either way, I'm not convinced that these are a problem for the specified
use cases I outlined.   In cases where you have a persistent business
relationship, they need to verify the parent public key exchange
anyway.  After that, the software doesn't technically require the
transmission of the PubKey, it only needs the Name/ID of the party and
the multiplier and it will fetch the PubKey from its data store.  Or it
is transmitted and the payer verifies it's correct.  Computing an
alternate {PubKey', Mult'} that produces the same address and then using
it in a MitM attack doesn't work here if the two parties pre-verified
the public keys. 

In the case that a business is checking whether the cashout address of a
customer is the same as the last time:  if the first payout was not
replaced by an attacker, then the business already has the correct
public key in their DB and a replacement of further payout requests will
fail validation.  If the first payout was replaced... well that could've
been done anyway (with or without this alternate form), and the customer
wouldn't have received their money and the whole process would be
flagged and terminated before further transactions.

-Alan



[-- Attachment #2: Type: text/html, Size: 3707 bytes --]

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Timo Hanke]

On Wed, Jun 19, 2013 at 10:39:04AM -0400, Alan Reiner wrote:
> On 06/19/2013 10:25 AM, Timo Hanke wrote:
> > Since you mention to use this in conjunction with the payment protocol,
> > note the following subtlety. Suppose the payer has to paid this address
> > called "destination": 
> >>    Standard Address ~ Base58(0x00 || hash160(PubKeyParent * Multiplier[i]) ||
> >> checksum)
> > Also suppose the payee has spent the output, i.e. the pubkey
> > corresponding to "destination", which is PubKeyParent * Multiplier[i],
> > is publicly known. Then anybody can (in retrospect) create arbitrary
> > many pairs {PublicKeyParent, Multiplier} (in particular different
> > PublicKeyParent) that lead to the same "destination".
> >
> > Depending on what you have in mind that the transaction should "prove"
> > regarding its actual receiver or regarding the receiver's PubKeyParent,
> > this could be an unwanted feature (or it could be just fine). If it is
> > unwanted then I suggest replacing
> > PubKeyParent * Multiplier[i] by 
> > PubKeyParent * HMAC(Multiplier[i],PubKeyParent)
> > which eliminates from the destination all ambiguity about PubKeyParent.
> >
> > This modification would not be directly compatible with BIP32 anymore
> > (unfortunately), but seems to be better suited for use in conjunction
> > with a payment protocol. 
> >
> > Timo
> 
> It's an interesting observation, but it looks like the most-obvious
> attack vector is discrete log problem:  spoofing a relationship between
> a target public key and one that you control.   For instance, if you see
> {PubA, Mult} produces PubB and you have PubC already in your control
> that you want to "prove" [maliciously] is related to PubB, then you have
> to find the multiplier, M that solves:  M*PubC = PubB.  That's a
> discrete logarithm problem.

Correct, for a given PubC in advance you can't create such a "malicious"
relation to PubB. You can only "reversely" construct new PubC from given
PubB.

> I'm not as familiar as you are, with the available operations on
> elliptic curves, but it sounds like you can produce essentially-random
> pairs of {PubX, Mult} pairs that give the same PubB, but you won't have
> the private key associated with those public keys.  

Depends on who is "you". The arbitrary person who produces {PubX, Mult}
won't have the private key, but the person who knows the private key for
PubA will have it (assuming that PubB was computed from {PubA, Mult} in
the first place).

In the end, it all depends on your application. What proves enough for
one party doing repeated transactions with another may not suffice for a
third party doing auditing. On the other hand, ambiguity about PubA may
just as well be a wanted feature for deniability reasons.

Timo

-- 
Timo Hanke
PGP 1EFF 69BC 6FB7 8744 14DB  631D 1BB5 D6E3 AB96 7DA8

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Timo Hanke]

On Wed, Jun 19, 2013 at 05:28:15PM +0200, Adam Back wrote:
> I think Timo's point is that while you cant do discrete log, you can do y-th
> root.  So if P = xG is a parent public key (x private key, G base point),
> then your proposed multiplier address is hash of Q=yP.  However its easy to
> find another P such that Q=zP'.  ie just "divide by z" (EC multiply by z^-1
> mod n, n the order of the curve).  So P'=z^-1.Q, which will work because
> Q=zP', substituting P' you get Q=z.z^-1.Q, Q=Q.
> 
> Of course the attacker has just performed an unspenable DoS (maybe, or maybe
> a useless collision) because he wont know the discrete log of Q, nor P, nor
> P'.  So thats the question, does the protocol have any reliance on knowing
> the discrete log - is it a problem if someone can find different multipliers
> of different (unknown, uncomputable discrete log) parent keys.
> 
> If it was a concern I guess you could require a proof of knowledge of
> discrete log.  ie as well as public key parent, multiplier the address must
> include ECDSA sig or Schnorr proof of knowledge (which both demonstrate
> knowledge of the discrete log of Q to base G.)

The "concern" (if there is any) would be that the owner of the parent
P=xG, i.e. the person knowing x, in addition to y creates another pair
(P',z) such that yP=Q=zP' and uses that second pair maliciously later on
(such as claiming the payment went to identity P' not P). Since the
owner of P knows the private key for P' (x*y*z^-1) he can also produce
proof of knowledge for discrete log for P'. I think adding proof of
knowledge or signatures on the multiplier don't help to eliminate all
possible concerns, which could involve proving something to a third
party that has not seen the communication between payer and payee. 

If you consider only payer and payee then Alan's original proposal is
just fine, as far as I can tell. Only if you start using it in a payment
protocol or, more precisely, if you start interpreting P as an identity
(as Alan suggested in subsequent posts) _and_ this identity is a
public/global one rather than a local one that only the payer uses, then
reasons can pop up to eliminate ambiguity about which identity each
payment went to.

Timo

ps the fact that this post used the multiplicative rather than additive
derivation scheme doesn't change the argument.

-- 
Timo Hanke
PGP 1EFF 69BC 6FB7 8744 14DB  631D 1BB5 D6E3 AB96 7DA8

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Jeremy Spilman]

> which could involve proving something to a third party that has not seen 
> the communication between payer and payee.

OK - I think I follow now.  So a third-party who does not see any of the 
communication between the payer and payee only knows the HASH160.  Let's say 
the payee denies receipt of the funds....

It's easy to prove what public key it was sent to (it's the preimage), but 
you can't prove the parent of that public key. You can provide any number of 
ParentPubKey * Multiplier that could have been used, so the 3rd party is 
unconvinced by a "matching" ParentPubKey * Multiplier.

However, if you calculated the destination using: PubKeyParent * 
HMAC(Multiplier,PubKeyParent) as Timo said, now if you give the 3rd party a 
PubKeyParent and Multiplier (or Addend) that produces the destination 
address, you've proven the payment is in fact spendable by PubKeyParent, and 
they can't deny receipt. Very cool.

Sorry for "echoing" this back, it took me a little while to work it out, so 
I thought I'd write it down. Hope I got it right...

If you give {PubKey, ChainCode} you do get this feature. If you give 
{ParentPubKey, Addend} or {ParentPubKey, Addend, ChainCode} you're back to 
having plausible deniability.

If BIP32's CKD'((Kpar, cpar), i) was actually HMAC(HMAC(cpar, i), Kpar) you 
could give HMAC(cpar, i) instead of Addend, and then you would get this 
feature; a way to 'skip down' a level in the wallet hierarchy, keep the 
'chain of custody' so to speak back to the ParentPubKey intact, without 
having to disclose the ChainCode. Meh...

Thanks,
--Jeremy

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 2793 bytes --]


On 06/20/2013 05:10 AM, Jeremy Spilman wrote:
>> which could involve proving something to a third party that has not seen 
>> the communication between payer and payee.
> OK - I think I follow now.  So a third-party who does not see any of the 
> communication between the payer and payee only knows the HASH160.  Let's say 
> the payee denies receipt of the funds....
>
> It's easy to prove what public key it was sent to (it's the preimage), but 
> you can't prove the parent of that public key. You can provide any number of 
> ParentPubKey * Multiplier that could have been used, so the 3rd party is 
> unconvinced by a "matching" ParentPubKey * Multiplier.
>
> However, if you calculated the destination using: PubKeyParent * 
> HMAC(Multiplier,PubKeyParent) as Timo said, now if you give the 3rd party a 
> PubKeyParent and Multiplier (or Addend) that produces the destination 
> address, you've proven the payment is in fact spendable by PubKeyParent, and 
> they can't deny receipt. Very cool.
>
> Sorry for "echoing" this back, it took me a little while to work it out, so 
> I thought I'd write it down. Hope I got it right...
>
> If you give {PubKey, ChainCode} you do get this feature. If you give 
> {ParentPubKey, Addend} or {ParentPubKey, Addend, ChainCode} you're back to 
> having plausible deniability.
>
> If BIP32's CKD'((Kpar, cpar), i) was actually HMAC(HMAC(cpar, i), Kpar) you 
> could give HMAC(cpar, i) instead of Addend, and then you would get this 
> feature; a way to 'skip down' a level in the wallet hierarchy, keep the 
> 'chain of custody' so to speak back to the ParentPubKey intact, without 
> having to disclose the ChainCode. Meh...
>
>

I agree, if we used Timo's suggestion, that seems to clean up the
remaining uncertainties with this recommendation.   I'm not convinced
those uncertainties matter in this situation, where there is no question
about the parent public key.  That is the part of the process that was
already verified, per my previous examples.  But certainly, for this to
be more versatile it would need that. 

If I modify my request to match Timo's recommendation, then it loses the
benefit of being a simple, non-disruptive extension of BIP 32.   I'm not
fond of deviating from BIP 32, as it kind of defeats one of the benefits
of BIP 32:  standardization.   And I'm not inclined to make an
Armory-specific wallet variant.

But I can't tell if the benefits are lost on you, or you just don't
think they are worth it (or I'm overstating them).  I'm strongly opposed
to bring extra wallets/chains into this equation /*just*/ to get a
benefit that can be had with a simple alternative encoding.  This isn't
a question of which is better, it's a matter of recognizing that both
forms have usefulness and should both be supported. 

-Alan

[-- Attachment #2: Type: text/html, Size: 3376 bytes --]

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 9597 bytes --]

Although I'd still prefer my original request, I get much of what I want
from your guys' recommendation.  It complicates the wallet design,
because it requires tracking and associating a matrix of addresses for
each wallet, instead of a single linear list.  But if this is what it's
going to take then I will go along. 

Right now BIP 32 defines, m/i'/j/k, where j=0 is the "external" chain
used for distributing addresses, and j=1 is the "internal" chain for
sending change.  The CONOPs (concept of operations) for the extended
wallet would be like Jeremy described:

- Chains with j>=2 would be independent address chains carved out for
individuals relationships
- Add wallet code to individually associate each j-value with a
particular identity
- Update the wallet code to pool all the addresses in all j-chains when
calculating the balance of the wallet and/or creating transactions
- When choosing to generically "Receive Bitcoins", will pick the next
address from the j=0 chain
- Will have to add extra function to "Receive Bitcoins" button to allow
creation of new contacts/identities.
- Change will always go to the next address in j=1, no matter which
chains are used to provide inputs.
- Add code to figure out lookaheads for each alternate chain.  Not just
each chain, but looking ahead a couple chains, too.  Luckily, the
lookahead doesn't have to be very big for chains j>=1 
- Add an interface to display and choose the different chains in your
wallet, and export the pubkey&chaincode in some soon-to-be-standardized
format. 
- Add code and interface to receive and track alternate j-chains from
other clients/users, and maintain those.  Should we try associating
incoming and outgoing chains?  What happens if they do it wrong?  Meh...

Just as one final swipe at this idea, you can see that I gotta do quite
a bit of work to support the multi-chain idea, and adds a little extra
burden on the user to maintain the organization of the wallet.  This
would all be totally unnecessary with a simple alternate encoding. 
Granted, I think the multi-chain idea is good, and one that I will
probably implement anyway, but it seems like overkill in terms of
developer complexity, and interface complexity to achieve something much
simpler.  Developers of much simpler/lightweight clients would probably
find this prohibitive.

On another note:  I thought we weren't encouraging automatic payments
without requesting from the other party...?  It makes me uneasy, but it
sounds like group thought has converged on that being acceptable.  I
bring it up, because there are situations where it makes sense, but it
sounds unsafe for general users.   Alice will give Bob his own chain for
sending Alice money, then a year later Bob will send money automatically
to Alice not realizing that the wallet was lost, retired or
compromised.  It's not that Bob can't ask for a new address, it's that
if the interface says "Send Money to Alice", that looks legit enough
that Bob may not feel it necessary to check with Alice first.   That's
more of an interface issue though.  We can add a warning to "check with
the recipient that they still have access to wallet 3cQ398x", etc.   But
I just know someone is going to lose money anyway...

-Alan





On 06/20/2013 03:32 AM, Mike Hearn wrote:
> Agree with Jeremy and once the payment protocol work is further along
> I'd like to see us define an extension that lets you send payment
> requests containing public keys+chain codes, so further payments can
> be made push-style with no recipient interaction (e.g. for repeated
> billing). How apps choose to arrange their chains internally seems
> like an area for experimentation. I definitely want to implement HD
> wallets in bitcoinj to allow this and if that means not using the same
> tree structure as in the BIP then so be it.
>
>
> On Thu, Jun 20, 2013 at 5:54 AM, Jeremy Spilman <jeremy@taplink.co
> <mailto:jeremy@taplink.co>> wrote:
>
>     > BIP 32 already specifies how to use the first three tree levels:
>      M/i/j/k,
>     > i~wallet, j~Internal/External, k~address.  The first level is
>     actually
>     > type-1 derived, and thus we cannot create an arbitrary number of
>     them
>     > without pre-computing them from the offline wallet.  So it's not
>     "free" to
>     > create new wallets unless we redefine how the levels work.
>
>     Initially I was thinking that you would share the public key and
>     chain code
>     from [m/i'/0] so that you can receive payments at [m/i'/0/k], for
>     a unique
>     value of 'i' for each receive chain.
>
>     For the case of generating new receive chains from a *watch-only*
>     wallet, as
>     you say, the options are to either keep a cache of
>     PubKey/ChainCode for
>     unused [m/i'] or simply increment 'j' past 1 for an existing
>     [m/i'/j] -- the
>     concept of 'internal/'external' and change addresses at Depth=2
>     don't make
>     sense for handing out receive chains to lots of people anyway, and
>     certainly
>     BIP32 doesn't *require* 0 <= j <= 1.  So I think incrementing 'j'
>     is the way
>     to go here...
>
>     The "default" layout of BIP32 does NOT mean that implementations
>     should not
>     check for transactions with j > 1. That would be a useless
>     constraint and
>     obviously self-limiting. It might be helpful to add to the
>     'Compatibility'
>     section some minimum expectations about how a wallet should be
>     'probed' when
>     imported. If you don't feel completely free to monotonically
>     increment 'j'
>     to your hearts content to achieve major usability benefits, then I
>     say BIP32
>     could use some clarifying.
>
>     BTW - the spec calls for addition not multiplication now, so we
>     should call
>     it the 'Addend' not the 'Multiplier' :-)
>
>     > Do these extra wallet chains behave as different wallets, or
>     sub-wallets?
>
>     They could, but they certainly don't need to!  A single-wallet
>     implementation treats this merely as an address-generation
>     algorithm, and
>     does not expose any hierarchy to the user interface.  The user just
>     "magically" gets the ability to send multiple payments to their
>     contacts
>     without immediately sacrificing their privacy
>     (http://www.wired.com/wiredenterprise/2013/06/bitcoin_retai/).
>     Everything
>     goes into the same ledger, balance, coin pool, etc. Most of the
>     code base is
>     unaware BIP32 is even in use.
>
>     While it is *possible* to support separate ledgers, balances, etc.
>     it is
>     certainly not required, and you get all the benefits either way.
>
>     I think, since your proposal generates and receives payments into
>     BIP32-style addresses, we both need similar underlying wallet
>     code. The only
>     difference is that you are passing the Kpar for [m/i'/0/k] and the
>     *result*
>     of CKD'((Kpar, cpar), k), and instead I proposed passing Kpar and
>     cpar, and
>     leaving 'k' out of it, letting the receive choose 'k'.
>
>     > For instance, maybe there's a benefit to using the same parent
>     pubkey
>     > across multiple services, as a form of identity.   If I don't
>     want that, I
>     > use your method.  If I do want that, I use my method.
>
>     I think it's a interesting idea using static public keys as a
>     means for
>     persistent identity and hence security from MitM. If you want a shared
>     public key across multiple services we could just combine both
>     ideas and get
>     all the benefits, by making the data structure { ParentPubKey, Addend,
>     ChainCode }:
>
>        ParentPubKey: Public key of m/i' -- 33 bytes
>        Addend: I[L]*G from CDK'(m/i', j) -- 33 bytes
>        ChainCode: I[R] from CDK'(m/i', j) -- 32 bytes
>
>     All that remains secret is the ChainCode from [m/i'] -- and of
>     course the
>     private keys.  The ParentPubKey is a common value across multiple
>     services,
>     corresponding to user's identity rooted in [m/i'].  Each service
>     gets their
>     own 'j'.  ParentPubKey + Addend gives you the PubKey of [m/i'/j].
>      With the
>     ChainCode, the receiver then can generate [m/i'/j/k] for monotonically
>     increasing 'k'. Again, from the user perspective all transactions
>     under
>     [m/i'] can be presented in a single ledger, or not.
>
>     Anyway, fundamentally my feedback is if you are designing for
>     persistent
>     long-term relationships, you could build in a mechanism for generating
>     address chains so you don't need any further communication after
>     the initial
>     exchange, and it need not complicate the wallet.
>
>     Thanks,
>     --Jeremy
>
>
>
>     ------------------------------------------------------------------------------
>     This SF.net email is sponsored by Windows:
>
>     Build for Windows Store.
>
>     http://p.sf.net/sfu/windows-dev2dev
>     _______________________________________________
>     Bitcoin-development mailing list
>     Bitcoin-development@lists.sourceforge.net
>     <mailto:Bitcoin-development@lists.sourceforge.net>
>     https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Windows:
>
> Build for Windows Store.
>
> http://p.sf.net/sfu/windows-dev2dev
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


[-- Attachment #2: Type: text/html, Size: 13644 bytes --]

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 5430 bytes --]

Agree with Jeremy and once the payment protocol work is further along I'd
like to see us define an extension that lets you send payment requests
containing public keys+chain codes, so further payments can be made
push-style with no recipient interaction (e.g. for repeated billing). How
apps choose to arrange their chains internally seems like an area for
experimentation. I definitely want to implement HD wallets in bitcoinj to
allow this and if that means not using the same tree structure as in the
BIP then so be it.


On Thu, Jun 20, 2013 at 5:54 AM, Jeremy Spilman <jeremy@taplink.co> wrote:

> > BIP 32 already specifies how to use the first three tree levels:
>  M/i/j/k,
> > i~wallet, j~Internal/External, k~address.  The first level is actually
> > type-1 derived, and thus we cannot create an arbitrary number of them
> > without pre-computing them from the offline wallet.  So it's not "free"
> to
> > create new wallets unless we redefine how the levels work.
>
> Initially I was thinking that you would share the public key and chain code
> from [m/i'/0] so that you can receive payments at [m/i'/0/k], for a unique
> value of 'i' for each receive chain.
>
> For the case of generating new receive chains from a *watch-only* wallet,
> as
> you say, the options are to either keep a cache of PubKey/ChainCode for
> unused [m/i'] or simply increment 'j' past 1 for an existing [m/i'/j] --
> the
> concept of 'internal/'external' and change addresses at Depth=2 don't make
> sense for handing out receive chains to lots of people anyway, and
> certainly
> BIP32 doesn't *require* 0 <= j <= 1.  So I think incrementing 'j' is the
> way
> to go here...
>
> The "default" layout of BIP32 does NOT mean that implementations should not
> check for transactions with j > 1. That would be a useless constraint and
> obviously self-limiting. It might be helpful to add to the 'Compatibility'
> section some minimum expectations about how a wallet should be 'probed'
> when
> imported. If you don't feel completely free to monotonically increment 'j'
> to your hearts content to achieve major usability benefits, then I say
> BIP32
> could use some clarifying.
>
> BTW - the spec calls for addition not multiplication now, so we should call
> it the 'Addend' not the 'Multiplier' :-)
>
> > Do these extra wallet chains behave as different wallets, or sub-wallets?
>
> They could, but they certainly don't need to!  A single-wallet
> implementation treats this merely as an address-generation algorithm, and
> does not expose any hierarchy to the user interface.  The user just
> “magically” gets the ability to send multiple payments to their contacts
> without immediately sacrificing their privacy
> (http://www.wired.com/wiredenterprise/2013/06/bitcoin_retai/). Everything
> goes into the same ledger, balance, coin pool, etc. Most of the code base
> is
> unaware BIP32 is even in use.
>
> While it is *possible* to support separate ledgers, balances, etc. it is
> certainly not required, and you get all the benefits either way.
>
> I think, since your proposal generates and receives payments into
> BIP32-style addresses, we both need similar underlying wallet code. The
> only
> difference is that you are passing the Kpar for [m/i'/0/k] and the *result*
> of CKD'((Kpar, cpar), k), and instead I proposed passing Kpar and cpar, and
> leaving 'k' out of it, letting the receive choose 'k'.
>
> > For instance, maybe there's a benefit to using the same parent pubkey
> > across multiple services, as a form of identity.   If I don't want that,
> I
> > use your method.  If I do want that, I use my method.
>
> I think it's a interesting idea using static public keys as a means for
> persistent identity and hence security from MitM. If you want a shared
> public key across multiple services we could just combine both ideas and
> get
> all the benefits, by making the data structure { ParentPubKey, Addend,
> ChainCode }:
>
>    ParentPubKey: Public key of m/i' -- 33 bytes
>    Addend: I[L]*G from CDK'(m/i', j) -- 33 bytes
>    ChainCode: I[R] from CDK'(m/i', j) -- 32 bytes
>
> All that remains secret is the ChainCode from [m/i'] -- and of course the
> private keys.  The ParentPubKey is a common value across multiple services,
> corresponding to user's identity rooted in [m/i'].  Each service gets their
> own 'j'.  ParentPubKey + Addend gives you the PubKey of [m/i'/j].  With the
> ChainCode, the receiver then can generate [m/i'/j/k] for monotonically
> increasing 'k'. Again, from the user perspective all transactions under
> [m/i'] can be presented in a single ledger, or not.
>
> Anyway, fundamentally my feedback is if you are designing for persistent
> long-term relationships, you could build in a mechanism for generating
> address chains so you don't need any further communication after the
> initial
> exchange, and it need not complicate the wallet.
>
> Thanks,
> --Jeremy
>
>
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Windows:
>
> Build for Windows Store.
>
> http://p.sf.net/sfu/windows-dev2dev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

[-- Attachment #2: Type: text/html, Size: 6613 bytes --]

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Jeremy Spilman]

> BIP 32 already specifies how to use the first three tree levels:  M/i/j/k, 
> i~wallet, j~Internal/External, k~address.  The first level is actually 
> type-1 derived, and thus we cannot create an arbitrary number of them 
> without pre-computing them from the offline wallet.  So it's not "free" to 
> create new wallets unless we redefine how the levels work.

Initially I was thinking that you would share the public key and chain code 
from [m/i'/0] so that you can receive payments at [m/i'/0/k], for a unique 
value of 'i' for each receive chain.

For the case of generating new receive chains from a *watch-only* wallet, as 
you say, the options are to either keep a cache of PubKey/ChainCode for 
unused [m/i'] or simply increment 'j' past 1 for an existing [m/i'/j] -- the 
concept of 'internal/'external' and change addresses at Depth=2 don't make 
sense for handing out receive chains to lots of people anyway, and certainly 
BIP32 doesn't *require* 0 <= j <= 1.  So I think incrementing 'j' is the way 
to go here...

The "default" layout of BIP32 does NOT mean that implementations should not 
check for transactions with j > 1. That would be a useless constraint and 
obviously self-limiting. It might be helpful to add to the 'Compatibility' 
section some minimum expectations about how a wallet should be 'probed' when 
imported. If you don't feel completely free to monotonically increment 'j' 
to your hearts content to achieve major usability benefits, then I say BIP32 
could use some clarifying.

BTW - the spec calls for addition not multiplication now, so we should call 
it the 'Addend' not the 'Multiplier' :-)

> Do these extra wallet chains behave as different wallets, or sub-wallets?

They could, but they certainly don't need to!  A single-wallet 
implementation treats this merely as an address-generation algorithm, and 
does not expose any hierarchy to the user interface.  The user just 
“magically” gets the ability to send multiple payments to their contacts 
without immediately sacrificing their privacy 
(http://www.wired.com/wiredenterprise/2013/06/bitcoin_retai/). Everything 
goes into the same ledger, balance, coin pool, etc. Most of the code base is 
unaware BIP32 is even in use.

While it is *possible* to support separate ledgers, balances, etc. it is 
certainly not required, and you get all the benefits either way.

I think, since your proposal generates and receives payments into 
BIP32-style addresses, we both need similar underlying wallet code. The only 
difference is that you are passing the Kpar for [m/i'/0/k] and the *result* 
of CKD'((Kpar, cpar), k), and instead I proposed passing Kpar and cpar, and 
leaving 'k' out of it, letting the receive choose 'k'.

> For instance, maybe there's a benefit to using the same parent pubkey 
> across multiple services, as a form of identity.   If I don't want that, I 
> use your method.  If I do want that, I use my method.

I think it's a interesting idea using static public keys as a means for 
persistent identity and hence security from MitM. If you want a shared 
public key across multiple services we could just combine both ideas and get 
all the benefits, by making the data structure { ParentPubKey, Addend, 
ChainCode }:

   ParentPubKey: Public key of m/i' -- 33 bytes
   Addend: I[L]*G from CDK'(m/i', j) -- 33 bytes
   ChainCode: I[R] from CDK'(m/i', j) -- 32 bytes

All that remains secret is the ChainCode from [m/i'] -- and of course the 
private keys.  The ParentPubKey is a common value across multiple services, 
corresponding to user's identity rooted in [m/i'].  Each service gets their 
own 'j'.  ParentPubKey + Addend gives you the PubKey of [m/i'/j].  With the 
ChainCode, the receiver then can generate [m/i'/j/k] for monotonically 
increasing 'k'. Again, from the user perspective all transactions under 
[m/i'] can be presented in a single ledger, or not.

Anyway, fundamentally my feedback is if you are designing for persistent 
long-term relationships, you could build in a mechanism for generating 
address chains so you don't need any further communication after the initial 
exchange, and it need not complicate the wallet.

Thanks,
--Jeremy 

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 2679 bytes --]

On 06/19/2013 05:58 PM, Jeremy Spilman wrote:
> Hi Alan,
>
>> “BIP 32 does not prescribe a way to use multiple chains like you described 
>> with the convenient type-2 derivation (though we could create a variant 
>> that does)”
> What do you think is missing from BIP32 for this? A wallet creates a 
> child-node using the public / type-2 CDF, hands out the PubKey/ChainCode, 
> and then generally expects transactions to come in starting at /0 and 
> incrementing monotonically.
>


You are suggesting that creating new wallet chains are the only
operation needed to achieve the functionality I'm requesting.  I
disagree.  I am okay with using different wallets for different parties
*/if the user wants to/*.  But there are orthogonal use-cases to having
a single wallet serve as a single identity that can be used across
multiple transactions or services.  And doing so is much simpler
conceptually for the user, and simpler in implementation for the app
developer.

BIP 32 already specifies how to use the first three tree levels: 
M/i/j/k, i~wallet, j~Internal/External, k~address.  The first level is
actually type-1 derived, and thus we cannot create an arbitrary number
of them without pre-computing them from the offline wallet.  So it's not
"free" to create new wallets unless we redefine how the levels work. 
Even if we assume the simplest case where the first level is actually
type-2 derived and it costs nothing to create separate wallets for each
contact/party:
 
-- Do these extra wallet chains behave as different wallets, or
sub-wallets? 
-- Should their balances be bundled into a single wallet or displayed
separately?
-- When a user tries to spend, does he have to specify which wallet(s)
he's spending from?
-- Should the app developer be required to implement a multiple-wallet
interface, and handle cross-wallet spending just to achieve this simple
mechanism?  Sure, they could instead implement a tiered wallet hierarchy
with primary wallets and sub-wallets... wait this just got complicated.

All that complexity just to support this identity mechanism that can be
included purely as an alternative address encoding with a single
wallet.  With my request, the user can't have one wallet and distribute
most of his addresses the normal/anonymous way, but certain apps would
choose to use the alternate encoding as a form of identity.  If the user
feels the need to create a separate wallet for certain operations to
separate his identities, that is his option if the software supports
multiple wallets.  But it's not the only way.

To achieve what I'm suggesting is useful and trivial to implement even
in the simplest wallet applications. 

-Alan

[-- Attachment #2: Type: text/html, Size: 3339 bytes --]

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Jeremy Spilman]

Hi Alan,

> “BIP 32 does not prescribe a way to use multiple chains like you described 
> with the convenient type-2 derivation (though we could create a variant 
> that does)”

What do you think is missing from BIP32 for this? A wallet creates a 
child-node using the public / type-2 CDF, hands out the PubKey/ChainCode, 
and then generally expects transactions to come in starting at /0 and 
incrementing monotonically.

Also, I'm not sure I follow your point about the 128kB hardware wallet --  
it's a signing device, so assuming it's even validating output amounts, at 
worst it cares about the number of inputs to the outputs being spent, but in 
many cases you're just handing it a sighash and the BIP32 "path" 
(/1/54/27/0) to generate the right private key for signing. The hardware 
wallet is not actually listening on the P2P network and detecting payments, 
so it's unaffected by dedicating child-nodes to each contact.

Consider the benefits of gaining critical mass of support for a technique 
which [I think] can be used in all cases, and increases security and privacy 
for everyone. I think there are huge benefits to leaving the age of 'single 
address generation' behind us...

Thanks,
--Jeremy 

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 2545 bytes --]

On 06/19/2013 03:29 PM, Jeremy Spilman wrote:
> If you have two parties who want to form a persistent relationship, by
> exchanging and verifying public keys beforehand, then I think the
> canonical way to do this with BIP32 is for the parties to exchange
> PubKey and *ChainCode*.
>  
> I don't understand the use case for handing out individual
> multipliers, if what you desire is a persistent relationship. If each
> party dedicates a child-wallet for receiving coins, and saves a
> PubKey/ChainCode for sending coins, the two parties can transaction
> securely forever without ever exchanging any more information, and
> without any address reuse.
>  
> I think ideally, the default behavior is that wallets always dedicate
> a new child node {PubKey, ChainCode} to each party they transact with.
> At the presentation layer, you have a "contact" and each contact has a
> transaction history. You can send coins to a contact at any time, and
> internally the wallet picks the next address in their sequence. Any
> funds received on pubkeys from contact's sequence are attributed to
> that contact. The wallet can organize the contacts, and roll-up the
> transaction history into 'ledgers' and 'balances' however they want --
> it could be based on the underlying BIP32 hierarchy or perhaps not.
> The cost of watching large a number of pubkeys, even if you 'look
> ahead' 100 pubkeys for each contact, is relatively small versus the
> benefits.
>  
>

What you just described is complimentary to what I am proposing.  There
is nothing stopping you from doing it that way, except that it may be
inconvenient in some circumstances.  BIP 32 does not prescribe a way to
use multiple chains like you described with the convenient type-2
derivation (though we could create a variant that does).  And all
separate chains with their 100-address look-aheads may be fine for your
desktop or mobile device, but maybe not a HW signing device with 128 kB
of memory. 

So, some use cases might prefer having a different parent public key
[and chaincode] per contact, some may prefer to synchronize across many
contacts.  For instance, maybe there's a benefit to using the same
parent pubkey across multiple services, as a form of identity.   If I
don't want that, I use your method.  If I do want that, I use my
method.  Given its simplicity, I don't know why both can't be options.

Actually, it doesn't have to be specific to the payment protocol, it can
just be alternative address encoding that some apps would use if they
have a need for it.

-Alan

[-- Attachment #2: Type: text/html, Size: 4241 bytes --]

Re: [Bitcoin-development] Optional "wallet-linkable" address format - Payment Protocol

[Jeremy Spilman]

[-- Attachment #1: Type: text/plain, Size: 2497 bytes --]

If you have two parties who want to form a persistent relationship, by exchanging and verifying public keys beforehand, then I think the canonical way to do this with BIP32 is for the parties to exchange PubKey and *ChainCode*.

I don’t understand the use case for handing out individual multipliers, if what you desire is a persistent relationship. If each party dedicates a child-wallet for receiving coins, and saves a PubKey/ChainCode for sending coins, the two parties can transaction securely forever without ever exchanging any more information, and without any address reuse.

I think ideally, the default behavior is that wallets always dedicate a new child node {PubKey, ChainCode} to each party they transact with. At the presentation layer, you have a “contact” and each contact has a transaction history. You can send coins to a contact at any time, and internally the wallet picks the next address in their sequence. Any funds received on pubkeys from contact’s sequence are attributed to that contact. The wallet can organize the contacts, and roll-up the transaction history into ‘ledgers’ and ‘balances’ however they want – it could be based on the underlying BIP32 hierarchy or perhaps not. The cost of watching large a number of pubkeys, even if you ‘look ahead’ 100 pubkeys for each contact, is relatively small versus the benefits.

What might be nice is a ‘Contact Request’ protocol, basically the same as a PaymentRequest but no actual payments are sent, just child wallets created:

message Contact {
    optional uint32 contact_version = 1 [default = 1];
    optional string pki_type = 2 [default = "none"];
    optional bytes pki_data = 3;
    required bytes serialized_contact_details = 4;
    optional bytes signature = 5;
}

message ContactDetails {
    optional string network = 1 [default = "main"];
    required bytes pubkey = 2;
    required bytes chaincode = 3;
    optional string memo = 4;
    optional string response_url = 5;
}

Alice sends a Contact+ContactDetails to Bob.  If Bob accepts, he sends his own Contact+ContactDetails (without a response_url) back to Alice. Basically just like adding a contact to your IM contacts.

Alice could send a Contact+ContactDetails to Bob without a response_url, in which case after accepting the contact, Bob could send funds to Alice, but not receive funds.

You could probably pack the whole message inside a bitcoin:// URI if you wanted to.

Thanks,
--Jeremy

[-- Attachment #2: Type: text/html, Size: 3617 bytes --]