From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 27E88EA8 for ; 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 ; Thu, 21 Apr 2016 12:08:56 +0000 (UTC) Received: by mail-yw0-f179.google.com with SMTP id j74so76062276ywg.1 for ; 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 Date: Thu, 21 Apr 2016 14:08:26 +0200 Message-ID: To: Pieter Wuille , Pieter Wuille 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
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 "Final" BIP though.

Slush

On Wed, Apr 20, 2016 at 6:= 32 PM, Jochen Hoenicke via bitcoin-dev <bitcoin-dev@li= sts.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).=C2=A0 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.=C2=A0 This has several unfortunate consequences:

- All callers of CKDpriv or CKDpub have to check for errors and handle
=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>
- It is not clear what to do if an intermediate node is
=C2=A0 missing. E.g. for the default wallet layout, if m/i_H/0 is missing =C2=A0 should m/i_H/1 be used for external chain and m/i_H/2 for internal =C2=A0 chain?=C2=A0 This would make the wallet handling much more difficult= .

- It gets even worse with standards like BIP-44.=C2=A0 If m/44' is miss= ing
=C2=A0 should we use m/45' instead?=C2=A0 If m/44'/0' is missin= g should we use
=C2=A0 m/44'/1' instead, using the same addresses as for testnet? =C2=A0 One could also restart with a different seed in this case, but this<= br> =C2=A0 wouldn't work if one later wants to support another BIP-43 propo= sal
=C2=A0 and still keep the same wallet.

I think the first point alone is reason enough to change this.=C2=A0 I am not aware of a BIP-32 application that handles errors like this
correctly in all cases.=C2=A0 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.=C2=A0 This would 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 node is valid according to the current standard the behavior should be
unchanged.

I think the backward compatibility issues are minimal.=C2=A0 The chance
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
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
more likely.

#QUESTIONS:

What is the procedure to update the BIP?=C2=A0 Is it still possible to
change the existing BIP-32 even though it is marked as final?=C2=A0 Or
should I make a new BIP for this that obsoletes BIP-32?

What algorithm is preferred? (bike-shedding)=C2=A0 My suggestion:

---

Change the last step of the private -> private derivation functions to:<= br>
=C2=A0. In case parse(I_L) >=3D n or k_i =3D 0, the procedure is repeate= d
=C2=A0 =C2=A0at step 2 with
=C2=A0 =C2=A0 I =3D HMAC-SHA512(Key =3D c_par, Data =3D 0x01 || I_R || ser3= 2(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.=C2=A0 I use I_R, since I_L is obviously not very random if I_L >= =3D 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 >=3D n more likely, the chance is still less than 1 in 2^256).=C2=A0= 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.

=C2=A0 Jochen
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev

--94eb2c07b5160a90f60530fd9398--