[Bitcoin-development] String-based Hierarchical Deterministic Keys - Alternative to BIP 32

[Bitcoin-development] String-based Hierarchical Deterministic Keys - Alternative to BIP 32

[Mike Koss]

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

I've implemented an alternative to the BIP 32 proposal.  I wanted a system
based on a hierarchical string representation (rather than hierarchy of
integers as BIP 32 proposes).  For example I name keys like this:

[hd1.75491111].store.1. 1D7GM5dkUtxvGeWgn7SYtanBuyj1MD1EZy
[hd1.75491111].store.2. 1QAqDbzpNKViGSjVe1XmnGbmZtvz5hM7t1
[hd1.75491111].store.3. 14XkSN92QLGeorYPpoVbG87DQhowEx3mFn
[hd1.75491111].store.4. 1JLcGdod6Wm33rMZuZZUmAEE6osLhM4QMn

First draft of proposal:

https://gist.github.com/4211704


I envision using this in services, so I've not done any work to recommend
how the keys would be represented directly in the client (I just map from a
seed value and
a hierarchy string in order to deterministic ally derive ECDSA public and
private keys).

I'm happy to release my source code for this (Python).  But I'd first like
to get feedback about any security concerns with my scheme (I note that I
don't introduce the enlarged
key space that BIP 32 does with its "chain code" - I'm wondering if that
represents a weakness of my scheme vs. BIP 32).

On Mon, Dec 3, 2012 at 12:44 PM, Pieter Wuille <pieter.wuille@gmail.com>wrote:

> On Mon, Dec 03, 2012 at 06:48:34AM -0800, Amir Taaki wrote:
> > ok, also what is the reasoning behind serialising points using a
> compressed
> > format before going into the hash function? I'm looking at the
> sec1-v2.pdf
> > and the compression format is a little confusing.
>
> I don't think there is a compelling reason to encourage uncompressed public
> keys anymore on the network. They take more space in the block chain for no
> additional value whatsoever. Software may of course continue supporting
> uncompressed keys if they wish to provide compatibility, but for a new
> standard, I think it makes sense to standardize on just compressed keys.
> And since that software thus needs to support the compressed encoding,
> there is no reason to use a different encoding inside the derivation scheme
> itself.
>
> Regarding the encoding itself, it is not hard: just 0x02 or 0x03 (depending
> on whether Y is even or odd) followed by the 32-byte encoding of X.
> Decoding
> is harder, but is never needed in the derivation. Software internally can
> use
> any representation (and it will), which in almost all circumstances stores
> both X and Y (and even more). Decoding compressed public keys is somewhat
> harder, as Y must be reconstructed (but the algorithm isn't hard) - this is
> only necessary when someone wants to import an extended public key though
> for
> watch-only wallets.
>
> --
> Pieter
>
>
> ------------------------------------------------------------------------------
> Keep yourself connected to Go Parallel:
> BUILD Helping you discover the best ways to construct your parallel
> projects.
> http://goparallel.sourceforge.net
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>



-- 
Mike Koss
CTO, CoinLab
(425) 246-7701 (m)

A Bitcoin Primer <http://coinlab.com/a-bitcoin-primer.pdf> - What you need
to know about Bitcoins.

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

Re: [Bitcoin-development] String-based Hierarchical Deterministic Keys - Alternative to BIP 32

[Gregory Maxwell]

On Tue, Dec 4, 2012 at 10:06 PM, Mike Koss <mike@coinlab.com> wrote:
> I've implemented an alternative to the BIP 32 proposal.  I wanted a system
> based on a hierarchical string representation (rather than hierarchy of
> integers as BIP 32 proposes).  For example I name keys like this:
>
> [hd1.75491111].store.1. 1D7GM5dkUtxvGeWgn7SYtanBuyj1MD1EZy
> [hd1.75491111].store.2. 1QAqDbzpNKViGSjVe1XmnGbmZtvz5hM7t1
> [hd1.75491111].store.3. 14XkSN92QLGeorYPpoVbG87DQhowEx3mFn
> [hd1.75491111].store.4. 1JLcGdod6Wm33rMZuZZUmAEE6osLhM4QMn
>
> First draft of proposal:
>
> https://gist.github.com/4211704

As Pieter pointed out recently— it's not (realistically) possible to
blindly iterate through strings.  This means your proposal loses the
backup recoverablity property which is part the point of a
deterministic wallet:  If you have a backup prior to a new string name
being established you must also have a reliable backup of the string
as well.

Of course, if you're backing up the strings then you can also backup a
map equating the hdwallet indexes to your strings, and in the event of
a catastrophic loss where you are only left with the original ultimate
root you lose no coins (only metadata) with the BIP32 scheme. If,
instead, we have your scheme and the backup of strings is incomplete
then some or all assigned coin may be lost forever.

Your extended hierarchy of multiplers also makes me uncomfortable.
BIP32 uses a HMAC in its construction to obtain strongly unstructured
points.

Re: [Bitcoin-development] String-based Hierarchical Deterministic Keys - Alternative to BIP 32

[Watson Ladd]

On Tue, Dec 4, 2012 at 9:23 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> On Tue, Dec 4, 2012 at 10:06 PM, Mike Koss <mike@coinlab.com> wrote:
>> I've implemented an alternative to the BIP 32 proposal.  I wanted a system
>> based on a hierarchical string representation (rather than hierarchy of
>> integers as BIP 32 proposes).  For example I name keys like this:
>>
>> [hd1.75491111].store.1. 1D7GM5dkUtxvGeWgn7SYtanBuyj1MD1EZy
>> [hd1.75491111].store.2. 1QAqDbzpNKViGSjVe1XmnGbmZtvz5hM7t1
>> [hd1.75491111].store.3. 14XkSN92QLGeorYPpoVbG87DQhowEx3mFn
>> [hd1.75491111].store.4. 1JLcGdod6Wm33rMZuZZUmAEE6osLhM4QMn
>>
>> First draft of proposal:
>>
>> https://gist.github.com/4211704
>
> As Pieter pointed out recently— it's not (realistically) possible to
> blindly iterate through strings.  This means your proposal loses the
> backup recoverablity property which is part the point of a
> deterministic wallet:  If you have a backup prior to a new string name
> being established you must also have a reliable backup of the string
> as well.

I would like to note that BIP32 and this new proposal have a missing
feature: being able to spend
a coin sent to an address generated by this scheme implies being able
to spend any coin generated
by this scheme.

The easiest deterministic wallet construction is simply to use a
stream cipher to generate random
bytes used as the private keys in a wallet. Hierarchical constructions
do not seem to me to add more,
other then distinguishing transactions by sending to unique addresses,
which could be done by other means.

>
> Of course, if you're backing up the strings then you can also backup a
> map equating the hdwallet indexes to your strings, and in the event of
> a catastrophic loss where you are only left with the original ultimate
> root you lose no coins (only metadata) with the BIP32 scheme. If,
> instead, we have your scheme and the backup of strings is incomplete
> then some or all assigned coin may be lost forever.
>
> Your extended hierarchy of multiplers also makes me uncomfortable.
> BIP32 uses a HMAC in its construction to obtain strongly unstructured
> points.

I read BIP32. And while the multipliers at each level are
unstructured, the ones in the next level are products
of the ones before i.e. we have a multiplication tree with random
looking branches.
Note that the order of the basepoint is prime or a small cofactor
times a prime, so this isn't an issue (usually:
the cofactor could be annoying).

--
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

[Bitcoin-development] String-based Hierarchical Deterministic Keys - Alternative to BIP 32

[Gregory Maxwell]

On Tue, Dec 4, 2012 at 10:36 PM, Watson Ladd <wbl@uchicago.edu> wrote:
> being able to spend
> a coin sent to an address generated by this scheme implies being able
> to spend any coin generated
> by this scheme.

If you have the the full extended secret there then you can spend
along the chain— but just the plain ecdsa secret by itself is not
enough to spend anything but that address itself.

Or have I misunderstood you here?

> The easiest deterministic wallet construction is simply to use a
> stream cipher to generate random
> bytes used as the private keys in a wallet. Hierarchical constructions
> do not seem to me to add more,
> other then distinguishing transactions by sending to unique addresses,
> which could be done by other means.

Sadly that construction has no ability to separate address generation
from spending— an important element for merchant applications.  Not
just for their own own distinguishing of transactions but because the
use of fresh addresses is essential to the limited privacy properties
of the Bitcoin system.

I called that a type-1 deterministic wallet in some old forum post
where I wrote about the different derivation schemes as opposed to the
point combining type-2 construction. The hope in BIP32 was that we
could get away just using a single one.