MIME-Version: 1.0
In-Reply-To: <5717AF19.1030102@gmail.com>
References: <5717AF19.1030102@gmail.com>
From: Marek Palatinus <marek@palatinus.cz>
Date: Thu, 21 Apr 2016 14:08:26 +0200
Message-ID: <CAJna-HiG5Nq_c0nZ28bTV4ZQKaU-zY1YiSEEaRK9ZvFO7LH-EA@mail.gmail.com>
To: Pieter Wuille <sipa@ulyssis.org>, Pieter Wuille <pieter.wuille@gmail.com>
Content-Type: multipart/alternative; boundary=94eb2c07b5160a90f60530fd9398
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] Proposal to update BIP-32
Precedence: list

--94eb2c07b5160a90f60530fd9398
Content-Type: text/plain; charset=UTF-8

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
>

--94eb2c07b5160a90f60530fd9398
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Sipa, you are probably the most competent to answer this. =
Could you please tell us your opinion? For me, this is straightforward, bac=
kward compatible fix and I like it a lot. Not sure about the process of cha=
nging &quot;Final&quot; BIP though.<div><br></div><div>Slush</div><div clas=
s=3D"gmail_extra"><br><div class=3D"gmail_quote">On Wed, Apr 20, 2016 at 6:=
32 PM, Jochen Hoenicke via bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mai=
lto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@li=
sts.linuxfoundation.org</a>&gt;</span> wrote:<br><blockquote class=3D"gmail=
_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:=
1ex">Hello Bitcoin Developers,<br>
<br>
I would like to make a proposal to update BIP-32 in a small way.<br>
<br>
TL;DR: BIP-32 is hard to use right (due to its requirement to skip<br>
addresses).=C2=A0 This proposal suggests a modification such that the<br>
difficulty can be encapsulated in the library.<br>
<br>
#MOTIVATION:<br>
<br>
The current BIP-32 specifies that if for some node in the hierarchy<br>
the computed hash I_L is larger or equal to the prime or 0, then the<br>
node is invalid and should be skipped in the BIP-32 tree.=C2=A0 This has<br=
>
several unfortunate consequences:<br>
<br>
- All callers of CKDpriv or CKDpub have to check for errors and handle<br>
=C2=A0 them appropriately.=C2=A0 This shifts the burden to the application<=
br>
=C2=A0 developer instead of being able to handle it in the BIP-32 library.<=
br>
<br>
- It is not clear what to do if an intermediate node is<br>
=C2=A0 missing. E.g. for the default wallet layout, if m/i_H/0 is missing<b=
r>
=C2=A0 should m/i_H/1 be used for external chain and m/i_H/2 for internal<b=
r>
=C2=A0 chain?=C2=A0 This would make the wallet handling much more difficult=
.<br>
<br>
- It gets even worse with standards like BIP-44.=C2=A0 If m/44&#39; is miss=
ing<br>
=C2=A0 should we use m/45&#39; instead?=C2=A0 If m/44&#39;/0&#39; is missin=
g should we use<br>
=C2=A0 m/44&#39;/1&#39; instead, using the same addresses as for testnet?<b=
r>
=C2=A0 One could also restart with a different seed in this case, but this<=
br>
=C2=A0 wouldn&#39;t work if one later wants to support another BIP-43 propo=
sal<br>
=C2=A0 and still keep the same wallet.<br>
<br>
I think the first point alone is reason enough to change this.=C2=A0 I am<b=
r>
not aware of a BIP-32 application that handles errors like this<br>
correctly in all cases.=C2=A0 It is also very hard to test, since it is<br>
infeasible to brute-force a BIP-32 key and a path where the node does<br>
not exists.<br>
<br>
This problem can be avoided by repeating the hashing with slightly<br>
different input data until a valid private key is found.=C2=A0 This would<b=
r>
be in the same spirit as RFC-6979.=C2=A0 This way, the library will always<=
br>
return a valid node for all paths.=C2=A0 Of course, in the case where the<b=
r>
node is valid according to the current standard the behavior should be<br>
unchanged.<br>
<br>
I think the backward compatibility issues are minimal.=C2=A0 The chance<br>
that this affects anyone is less than 10^-30.=C2=A0 Even if it happens, it<=
br>
would only create some additional addresses (that are not seen if the<br>
user downgrades).=C2=A0 The main reason for suggesting a change is that we<=
br>
want a similar method for different curves where a collision is much<br>
more likely.<br>
<br>
#QUESTIONS:<br>
<br>
What is the procedure to update the BIP?=C2=A0 Is it still possible to<br>
change the existing BIP-32 even though it is marked as final?=C2=A0 Or<br>
should I make a new BIP for this that obsoletes BIP-32?<br>
<br>
What algorithm is preferred? (bike-shedding)=C2=A0 My suggestion:<br>
<br>
---<br>
<br>
Change the last step of the private -&gt; private derivation functions to:<=
br>
<br>
=C2=A0. In case parse(I_L) &gt;=3D n or k_i =3D 0, the procedure is repeate=
d<br>
=C2=A0 =C2=A0at step 2 with<br>
=C2=A0 =C2=A0 I =3D HMAC-SHA512(Key =3D c_par, Data =3D 0x01 || I_R || ser3=
2(i))<br>
<br>
---<br>
<br>
I think this suggestion is simple to implement (a bit harder to unit<br>
test) and the string to hash with HMAC-SHA512 always has the same<br>
length.=C2=A0 I use I_R, since I_L is obviously not very random if I_L &gt;=
=3D n.<br>
There is a minimal chance that it will lead to an infinite loop if I_R<br>
is the same in two consecutive iterations, but that has only a chance<br>
of 1 in 2^512 (if the algorithm is used for different curves that make<br>
I_L &gt;=3D n more likely, the chance is still less than 1 in 2^256).=C2=A0=
 In<br>
theory, this loop can be avoided by incrementing i in every iteration,<br>
but this would make an implementation error in the &quot;hard to test&quot;=
 path<br>
of the program more likely.<br>
<br>
The other derivation functions should be updated in a similar matter.<br>
Also the derivation of the root node from the seed should be updated<br>
in a similar matter to avoid invalid seeds.<br>
<br>
If you followed until here, thanks for reading this long posting.<br>
<br>
=C2=A0 Jochen<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div><br></div></div>

--94eb2c07b5160a90f60530fd9398--