public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Marek Palatinus <marek@palatinus.cz>
To: Pieter Wuille <sipa@ulyssis.org>,
	Pieter Wuille <pieter.wuille@gmail.com>
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] Proposal to update BIP-32
Date: Thu, 21 Apr 2016 14:08:26 +0200	[thread overview]
Message-ID: <CAJna-HiG5Nq_c0nZ28bTV4ZQKaU-zY1YiSEEaRK9ZvFO7LH-EA@mail.gmail.com> (raw)
In-Reply-To: <5717AF19.1030102@gmail.com>

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

Sipa, you are probably the most competent to answer this. Could you please
tell us your opinion? For me, this is straightforward, backward compatible
fix and I like it a lot. Not sure about the process of changing "Final" BIP
though.

Slush

On Wed, Apr 20, 2016 at 6:32 PM, Jochen Hoenicke via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello Bitcoin Developers,
>
> I would like to make a proposal to update BIP-32 in a small way.
>
> TL;DR: BIP-32 is hard to use right (due to its requirement to skip
> addresses).  This proposal suggests a modification such that the
> difficulty can be encapsulated in the library.
>
> #MOTIVATION:
>
> The current BIP-32 specifies that if for some node in the hierarchy
> the computed hash I_L is larger or equal to the prime or 0, then the
> node is invalid and should be skipped in the BIP-32 tree.  This has
> several unfortunate consequences:
>
> - All callers of CKDpriv or CKDpub have to check for errors and handle
>   them appropriately.  This shifts the burden to the application
>   developer instead of being able to handle it in the BIP-32 library.
>
> - It is not clear what to do if an intermediate node is
>   missing. E.g. for the default wallet layout, if m/i_H/0 is missing
>   should m/i_H/1 be used for external chain and m/i_H/2 for internal
>   chain?  This would make the wallet handling much more difficult.
>
> - It gets even worse with standards like BIP-44.  If m/44' is missing
>   should we use m/45' instead?  If m/44'/0' is missing should we use
>   m/44'/1' instead, using the same addresses as for testnet?
>   One could also restart with a different seed in this case, but this
>   wouldn't work if one later wants to support another BIP-43 proposal
>   and still keep the same wallet.
>
> I think the first point alone is reason enough to change this.  I am
> not aware of a BIP-32 application that handles errors like this
> correctly in all cases.  It is also very hard to test, since it is
> infeasible to brute-force a BIP-32 key and a path where the node does
> not exists.
>
> This problem can be avoided by repeating the hashing with slightly
> different input data until a valid private key is found.  This would
> be in the same spirit as RFC-6979.  This way, the library will always
> return a valid node for all paths.  Of course, in the case where the
> node is valid according to the current standard the behavior should be
> unchanged.
>
> I think the backward compatibility issues are minimal.  The chance
> that this affects anyone is less than 10^-30.  Even if it happens, it
> would only create some additional addresses (that are not seen if the
> user downgrades).  The main reason for suggesting a change is that we
> want a similar method for different curves where a collision is much
> more likely.
>
> #QUESTIONS:
>
> What is the procedure to update the BIP?  Is it still possible to
> change the existing BIP-32 even though it is marked as final?  Or
> should I make a new BIP for this that obsoletes BIP-32?
>
> What algorithm is preferred? (bike-shedding)  My suggestion:
>
> ---
>
> Change the last step of the private -> private derivation functions to:
>
>  . In case parse(I_L) >= n or k_i = 0, the procedure is repeated
>    at step 2 with
>     I = HMAC-SHA512(Key = c_par, Data = 0x01 || I_R || ser32(i))
>
> ---
>
> I think this suggestion is simple to implement (a bit harder to unit
> test) and the string to hash with HMAC-SHA512 always has the same
> length.  I use I_R, since I_L is obviously not very random if I_L >= n.
> There is a minimal chance that it will lead to an infinite loop if I_R
> is the same in two consecutive iterations, but that has only a chance
> of 1 in 2^512 (if the algorithm is used for different curves that make
> I_L >= n more likely, the chance is still less than 1 in 2^256).  In
> theory, this loop can be avoided by incrementing i in every iteration,
> but this would make an implementation error in the "hard to test" path
> of the program more likely.
>
> The other derivation functions should be updated in a similar matter.
> Also the derivation of the root node from the seed should be updated
> in a similar matter to avoid invalid seeds.
>
> If you followed until here, thanks for reading this long posting.
>
>   Jochen
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

  reply	other threads:[~2016-04-21 12:09 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-04-20 16:32 [bitcoin-dev] Proposal to update BIP-32 Jochen Hoenicke
2016-04-21 12:08 ` Marek Palatinus [this message]
2016-05-08 10:07   ` Pavol Rusnak
     [not found]     ` <CAAS2fgT17MQbB=Mb0qPTQcZtCY_XTeZa587w-voeeJ-WXxLagA@mail.gmail.com>
2016-05-08 11:09       ` Gregory Maxwell
     [not found]   ` <CAPg+sBiAv7PFWEw5s=BPcOkL-x9GfWqi24pD3xMnfxvz9xQy4g@mail.gmail.com>
2016-05-08 13:48     ` [bitcoin-dev] Fwd: " Marek Palatinus
2016-05-08 22:21       ` Pavol Rusnak
2016-04-21 15:28 ` [bitcoin-dev] " Eric Lombrozo
2016-04-21 17:23   ` Pavol Rusnak
2016-04-22  9:14   ` Jochen Hoenicke

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAJna-HiG5Nq_c0nZ28bTV4ZQKaU-zY1YiSEEaRK9ZvFO7LH-EA@mail.gmail.com \
    --to=marek@palatinus.cz \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=pieter.wuille@gmail.com \
    --cc=sipa@ulyssis.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox