String-based Hierarchical Deterministic Keys - Alternative to BIP 32
4 messages, 5 Dec 2012. Started by Mike Koss.
Greg Maxwell (2), Mike Koss, Watson Ladd
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:
Quoted text (42 lines)
> 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 >
On Tue, Dec 4, 2012 at 10:06 PM, Mike Koss <mike@coinlab•com> wrote:
Quoted text (12 lines)
> 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.
On Tue, Dec 4, 2012 at 9:23 PM, Gregory Maxwell <gmaxwell@gmail•com> wrote:
Quoted text (20 lines)
> 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.
Quoted text (11 lines)
> > 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).
On Tue, Dec 4, 2012 at 10:36 PM, Watson Ladd <wbl@uchicago•edu> wrote:
Quoted text (4 lines)
> 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?
Quoted text (6 lines)
> 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.