path: root/cb/f235031ff5eab8a4be6c5a7f9af9ccf3b2740c

Return-Path: <marek@palatinus.cz>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 27E88EA8
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 21 Apr 2016 12:09:00 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-yw0-f179.google.com (mail-yw0-f179.google.com
	[209.85.161.179])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 2CB9A148
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 21 Apr 2016 12:08:56 +0000 (UTC)
Received: by mail-yw0-f179.google.com with SMTP id j74so76062276ywg.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 21 Apr 2016 05:08:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=palatinus-cz.20150623.gappssmtp.com; s=20150623;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to
	:cc; bh=hAsme9CkmHaN/QzlfCVBkY10ZRSRNJ2d6pXjFnJWElo=;
	b=FKVy4QJrrYLvxtgudPjYmd9v2J3z99EUFC7J/RpodaetvIkrUXgzpTEg9J9Y7SaGtN
	h4GzgILMAOrHiynfQS3OqStSDOr9KJvRSpnuylrOXgnqD+Ye5tg6MbWalYYsXpTNWc6f
	JcmDuquE7AQDLrh8SfTIs80e1e9oPxwejmTRM10NZ3AI+V8kcm9wL71mkyGBiLO57hBB
	J0tdWkiZJ6MOGcijcKettKBIXIxY58FF7pQnq5BiPidndi3oetRul0/2xIk77kI1Ier9
	M7r3Esi1gjIMbAM5qxQcU9zzqpROx+XS0XnRpuXfQRN6B3cIwW5t/2uRPOW2l5sfVlFH
	9kOw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to:cc;
	bh=hAsme9CkmHaN/QzlfCVBkY10ZRSRNJ2d6pXjFnJWElo=;
	b=YNWZ5KfU7DivPH26vnR9V/k0hyh1yjfbZDaIsAV0m/EoGeGpz6eH/sZdrOZ8oy7xJ9
	zNLnIcVCwEMeybYT+4qipVboLystJiyXzaCFjq/lDR/u6v/bjOh9nLgkCELin+zs96Bz
	isI0Wun9pyEtgZObZsZnltItri2jG51XtvRSkENdDX8u0RUa6jn5fN5Po+EMclaTKR0+
	oBkoJdGMouxx49Es9GPx5QNQAyZyjaptjuFnsBt6o4TnIbUFUGT3PS+5GnhHtRs9yWSJ
	sFsxP7lL0UN2mXtzTFMwk7DtHgk9FqyScuVa8mhqcCzqg0VaxzmdgZ5sw1uqcGVyHfz1
	lKGg==
X-Gm-Message-State: AOPr4FWUu/AM/iQbtRUsNi8K0L72rTzTKwxNbpuZxwEiOuCDGPEM52u2pjHrgegd1WgSDKI7HfhBhImhuzWUBA==
X-Received: by 10.129.148.2 with SMTP id l2mr8607311ywg.298.1461240535341;
	Thu, 21 Apr 2016 05:08:55 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.129.92.2 with HTTP; Thu, 21 Apr 2016 05:08:26 -0700 (PDT)
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
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Thu, 21 Apr 2016 12:09:50 +0000
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] Proposal to update BIP-32
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Thu, 21 Apr 2016 12:09:00 -0000

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