BIP0032

Pieter,

I was re-reading BIP0032, and checking some of the equations... It seems to me that there is something wrong (or I have missed something).

As I see it there can only be one HMAC function, used for both private and public derivation - I assume that: [1] CKD((k_par, c_par), i) -> (k_i, c_i) [2] CKD'((K_par, c_par), i) -> (K_i, c_i)

Where K_par = k_par*G, will result in K_i = k_i*G (and identical c_i's in both expressions).

Now following your formulas for [1]:
  k_i = I_L + k_par (mod n)
where I_L = {HMACSHA512(c_par, 0x00||k_par||i)}_L (denoting left
256bits). Further c_i = I_R.
This gives a K_i = k_i*G = I_L*G + k_par(mod n)*G

Now follow the formula for [2]:
  K_i = (I_L+k_par)*G = I_L*G + K_par
This is not the same as above, however, if we remove the (mod n) we are
getting closer, but still the value of I_L are different in the two
equations as: HMACSHA512(c_par, 0x00||k_par||i) <> HMAXSHA512(c_par,
X(k_par*G)||i).

We can, however, fix things if we change private child key derivation to:

To define CDK((k_par, c_par), i) -> (k_i, c_i):
* (no difference in deriving public or private):
	I = HMACSHA512(c_par, X(k_par*G)||i)
* Split I into I_L, I_R (256bits each)
* k_i = k_par + I_L
* c_i = I_R
* and, if using public derivation, we use K_i = (k_par + I_L)*G

Now for pure public derivation (i.e. we don't know the private key):
To define CDK'((K_par, c_par), i) -> (K_i, c_i):
* I = HMACSHA512(c_par, X(K_par)||i)
* Split I into I_L and I_R
* K_i = K_par + I_L*G (= k_par*G + I_L*G = (k_par+I_L)*G = k_i*G)
* c_i = I_R

Now we have the right properties, but it required quite some changes, also note that c_i are now equal in both private and public derivation.

Comments ?

Sincerely,

Michael

Commenting on my own mail...

Rereading the BIP, it occurs to me that the private derivation is actually intentional. So: (m/i/j/k)*G = (M/i/j/k), but (m/i'/j/k)*G <> (M/i/j/k) (M/i'/j/k => ERROR)

But: ((m/i')*G)/j/k = (m/i'/j/k)*G

So, the motivation for the private derivation is to avoid the known (K, c) and known k_i => k known too! I fear that many will fall in this trap, though...

/Michael

Which again means that the statement regarding Audits through the Master Public key, M, is wrong - only incoming and outgoing transaction of _publicly_ derived wallets will be part of the audit... Privately derived wallets cannot be obtained, though you could, without loss of security, share also the addition points from privately derived wallets: (m/i')*G, but there is no concept of a single public master key.

== Audits: M In case an auditor needs full access to the list of incoming and outgoing payments, one can share the master public extended key. This will allow the auditor to see all transactions from and to the wallet, in all accounts, but not a single secret key. ==

Yeah, I tried implementing it based on the document there and the code that is available in sipa's repo on GitHub but it's not enough. I'm waiting until there is an implementation of this concept before moving on it.

________________________________ From: Michael Gronager <gronager@ceptacle•com> To: bitcoin-development@lists•sourceforge•net Sent: Monday, May 27, 2013 2:39 PM Subject: Re: [Bitcoin-development] BIP0032

Which again means that the statement regarding Audits through the Master Public key, M, is wrong - only incoming and outgoing transaction of _publicly_ derived wallets will be part of the audit... Privately derived wallets cannot be obtained, though you could, without loss of security, share also the addition points from privately derived wallets: (m/i')*G, but there is no concept of a single public master key.

== Audits: M In case an auditor needs full access to the list of incoming and outgoing payments, one can share the master public extended key. This will allow the auditor to see all transactions from and to the wallet, in all accounts, but not a single secret key. ==

On Mon, May 27, 2013 at 03:10:04PM +0200, Michael Gronager wrote:

> Commenting on my own mail...
>
> Rereading the BIP, it occurs to me that the private derivation is
> actually intentional. So:
> (m/i/j/k)*G = (M/i/j/k), but (m/i'/j/k)*G <> (M/i/j/k) (M/i'/j/k => ERROR)
>
> But: ((m/i')*G)/j/k = (m/i'/j/k)*G
>
> So, the motivation for the private derivation is to avoid the known (K,
> c) and known k_i => k known too! I fear that many will fall in this
> trap, though...

I think the current formulation in the BIP text is a bit confusing, as there is both "public derivation" (namely: derivation that can be done using just the public key), and the "public derivation function" (the one that takes the public key as input). Any suggestion for better terminology is welcome. One possibility is calling it type-1 and type-2 derivation, but that's only enlightening if you of the origin of the concept.

There is current "test vector generation" code on the 'detwallet' branch on my github repo, but this isn't useful for actual deterministic wallets. I'm working on having an implementation that nicely integrates with the key abstraction.

Also, there are already other implementations available, such as this Python one https://github.com/FelixWeis/hdwallet, and Java code in Bits of Proof (with whom the test vectors match, after finding a bug in mine...)

Of course, implementing a determinstic wallet is more than just key derivation. There is dealing with detecting new keys/chains being used, lookahead, how to use accounts (if at all), and internal/external subchains. I think this is much more likely to differ more between different implementations, and perhaps interesting applications

A JSON-ed version of the test vectors is here: https://github.com/bitsofproof/supernode/blob/master/api/src/test/resources/BIP32.json

The Bits of Proof code matching with them is at: https://github.com/bitsofproof/supernode/blob/master/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java

Tamas Blummer