📅 Original date posted:2016-04-21
📝 Original message: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 at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160421/1b0958b3/attachment.html>;
Marek Palatinus [ARCHIVE] /
npub1xt…acz68
2023-06-07 17:50:09
in reply to nevent1q…hlvg
Author Public Key
npub1xtqansnal58rjnnxvyke6kzuvxsz0twg4456awy6ff0525yqgjxqjacz68Published at
2023-06-07 17:50:09Event JSON
{
"id": "b5054400e51af9ca9f29ad3768fca3c393153e8a57685be4a8580ba264daa19d",
"pubkey": "32c1d9c27dfd0e394e66612d9d585c61a027adc8ad69aeb89a4a5f455080448c",
"created_at": 1686160209,
"kind": 1,
"tags": [
[
"e",
"7a09f5b1650d8bf91dee85a09eb46eb6358130e456757f2a5ef707d77b99ebe5",
"",
"root"
],
[
"e",
"d2ceb940d8e685faff395dd75041e7b793c42297d92e1b25d748eaac636cf617",
"",
"reply"
],
[
"p",
"5f325e2a1875039f7993aa44faeaa213e27f236f1388a14ae04289d0c742bc95"
]
],
"content": "📅 Original date posted:2016-04-21\n📝 Original message:Sipa, you are probably the most competent to answer this. Could you please\ntell us your opinion? For me, this is straightforward, backward compatible\nfix and I like it a lot. Not sure about the process of changing \"Final\" BIP\nthough.\n\nSlush\n\nOn Wed, Apr 20, 2016 at 6:32 PM, Jochen Hoenicke via bitcoin-dev \u003c\nbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\n\u003e Hello Bitcoin Developers,\n\u003e\n\u003e I would like to make a proposal to update BIP-32 in a small way.\n\u003e\n\u003e TL;DR: BIP-32 is hard to use right (due to its requirement to skip\n\u003e addresses). This proposal suggests a modification such that the\n\u003e difficulty can be encapsulated in the library.\n\u003e\n\u003e #MOTIVATION:\n\u003e\n\u003e The current BIP-32 specifies that if for some node in the hierarchy\n\u003e the computed hash I_L is larger or equal to the prime or 0, then the\n\u003e node is invalid and should be skipped in the BIP-32 tree. This has\n\u003e several unfortunate consequences:\n\u003e\n\u003e - All callers of CKDpriv or CKDpub have to check for errors and handle\n\u003e them appropriately. This shifts the burden to the application\n\u003e developer instead of being able to handle it in the BIP-32 library.\n\u003e\n\u003e - It is not clear what to do if an intermediate node is\n\u003e missing. E.g. for the default wallet layout, if m/i_H/0 is missing\n\u003e should m/i_H/1 be used for external chain and m/i_H/2 for internal\n\u003e chain? This would make the wallet handling much more difficult.\n\u003e\n\u003e - It gets even worse with standards like BIP-44. If m/44' is missing\n\u003e should we use m/45' instead? If m/44'/0' is missing should we use\n\u003e m/44'/1' instead, using the same addresses as for testnet?\n\u003e One could also restart with a different seed in this case, but this\n\u003e wouldn't work if one later wants to support another BIP-43 proposal\n\u003e and still keep the same wallet.\n\u003e\n\u003e I think the first point alone is reason enough to change this. I am\n\u003e not aware of a BIP-32 application that handles errors like this\n\u003e correctly in all cases. It is also very hard to test, since it is\n\u003e infeasible to brute-force a BIP-32 key and a path where the node does\n\u003e not exists.\n\u003e\n\u003e This problem can be avoided by repeating the hashing with slightly\n\u003e different input data until a valid private key is found. This would\n\u003e be in the same spirit as RFC-6979. This way, the library will always\n\u003e return a valid node for all paths. Of course, in the case where the\n\u003e node is valid according to the current standard the behavior should be\n\u003e unchanged.\n\u003e\n\u003e I think the backward compatibility issues are minimal. The chance\n\u003e that this affects anyone is less than 10^-30. Even if it happens, it\n\u003e would only create some additional addresses (that are not seen if the\n\u003e user downgrades). The main reason for suggesting a change is that we\n\u003e want a similar method for different curves where a collision is much\n\u003e more likely.\n\u003e\n\u003e #QUESTIONS:\n\u003e\n\u003e What is the procedure to update the BIP? Is it still possible to\n\u003e change the existing BIP-32 even though it is marked as final? Or\n\u003e should I make a new BIP for this that obsoletes BIP-32?\n\u003e\n\u003e What algorithm is preferred? (bike-shedding) My suggestion:\n\u003e\n\u003e ---\n\u003e\n\u003e Change the last step of the private -\u003e private derivation functions to:\n\u003e\n\u003e . In case parse(I_L) \u003e= n or k_i = 0, the procedure is repeated\n\u003e at step 2 with\n\u003e I = HMAC-SHA512(Key = c_par, Data = 0x01 || I_R || ser32(i))\n\u003e\n\u003e ---\n\u003e\n\u003e I think this suggestion is simple to implement (a bit harder to unit\n\u003e test) and the string to hash with HMAC-SHA512 always has the same\n\u003e length. I use I_R, since I_L is obviously not very random if I_L \u003e= n.\n\u003e There is a minimal chance that it will lead to an infinite loop if I_R\n\u003e is the same in two consecutive iterations, but that has only a chance\n\u003e of 1 in 2^512 (if the algorithm is used for different curves that make\n\u003e I_L \u003e= n more likely, the chance is still less than 1 in 2^256). In\n\u003e theory, this loop can be avoided by incrementing i in every iteration,\n\u003e but this would make an implementation error in the \"hard to test\" path\n\u003e of the program more likely.\n\u003e\n\u003e The other derivation functions should be updated in a similar matter.\n\u003e Also the derivation of the root node from the seed should be updated\n\u003e in a similar matter to avoid invalid seeds.\n\u003e\n\u003e If you followed until here, thanks for reading this long posting.\n\u003e\n\u003e Jochen\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160421/1b0958b3/attachment.html\u003e",
"sig": "cd0503c709c8a1258a4d26d0eb1de3b43afcd6dffaaabf57e4e06b0aafd21eebfa65542029dd80f7bf0572c9d7215862d3d5adbe9de57b9b0366f81c5ce87f41"
}