[Bitcoin-development] BIP0032

[Bitcoin-development] BIP0032

[Michael Gronager]

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

Re: [Bitcoin-development] BIP0032

[Michael Gronager]

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

Re: [Bitcoin-development] BIP0032

[Michael Gronager]

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

Re: [Bitcoin-development] BIP0032

[Amir Taaki]

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

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



------------------------------------------------------------------------------
Try New Relic Now & We'll Send You this Cool Shirt
New Relic is the only SaaS-based application performance monitoring service 
that delivers powerful full stack analytics. Optimize and monitor your
browser, app, & servers with just a few lines of code. Try New Relic
and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may
_______________________________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

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

Re: [Bitcoin-development] BIP0032

[Pieter Wuille]

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

-- 
Pieter

Re: [Bitcoin-development] BIP0032

[Tamas Blummer]

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

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

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 495 bytes --]