1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
Return-Path: <elombrozo@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 649D0E88
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 21 Apr 2016 15:28:45 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pa0-f48.google.com (mail-pa0-f48.google.com
[209.85.220.48])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 96C69126
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 21 Apr 2016 15:28:44 +0000 (UTC)
Received: by mail-pa0-f48.google.com with SMTP id er2so30136373pad.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 21 Apr 2016 08:28:44 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=user-agent:in-reply-to:references:mime-version
:content-transfer-encoding:subject:from:date:to:message-id;
bh=mvhQGfX6mwgKgjQziXPxkGz+sbPF3vRvXYWxH8rELO4=;
b=fEkBmmcaRYeuhOtCBTLOJrR7qokqL75PYpCzeJioOBlPyTRCWltXxE/vCkwTlOV6vn
4Q0+uYQnCcuOf5H8C/r9qo7Lttigr3BSsQL/8W0l8slAifmmhTxwYRUd5iLaTTjvQHn2
6R00n2uWGhD7UpYdxu0tHJEhhiAlSeA01D+liE8eCqjZWQlkq/KyHjqvVIZ6LQoOn4FC
5K8lSNI4V7FJMyizKXztCAd3HWa0YR2fZDf8sumPj49wPKxDk4EVLPd6GvuUql44utw/
oyxWGkKE8ruq3THQX2zWxgiekLrNGAubztk9oV6t6foDbca6IRbMWUVC/X4/pRhn0r33
0dpQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:user-agent:in-reply-to:references:mime-version
:content-transfer-encoding:subject:from:date:to:message-id;
bh=mvhQGfX6mwgKgjQziXPxkGz+sbPF3vRvXYWxH8rELO4=;
b=GHhGavYrnqv2vZ8m7n9udgQvcsdJyekDAgv7KdLN7M++VDSgDG5ahEH1+UU6J8N26e
xsww9s/4nLQ5GCIG0g6R5Hen9Xaa7WUu152PaXAk0HM9IsO+pKU3F8Y7XxqbGNchmQyQ
TAIl8YHpLZM88/JXKosSQuz77I83RmyLsn0ncAC3kdCcI3mehUMIyHxw14IJOe55bK/5
1Z3gEMe0MY3KVykdjEnLCMyTER1JTtX8ikIRSgR0r8W0e/ZxHaMAu62n4QLDWA6yvY1f
j+WrS5R9EDU/ZZOthUTAedeuPuX2zSAMzLCTphVF59bwiof4EX2M4Fl0DkrenOwKV3qY
w7gA==
X-Gm-Message-State: AOPr4FVDcNIMWL28l5qGHjg+YM1QGiT9LvbkBzYd8QxaPj2/GHvsAuWfMUk8l2rts7R74Q==
X-Received: by 10.66.199.66 with SMTP id ji2mr21487956pac.34.1461252524266;
Thu, 21 Apr 2016 08:28:44 -0700 (PDT)
Received: from [192.168.1.102] (cpe-70-95-80-239.san.res.rr.com.
[70.95.80.239])
by smtp.gmail.com with ESMTPSA id h5sm3086473pat.0.2016.04.21.08.28.43
(version=TLSv1/SSLv3 cipher=OTHER);
Thu, 21 Apr 2016 08:28:43 -0700 (PDT)
User-Agent: K-9 Mail for Android
In-Reply-To: <5717AF19.1030102@gmail.com>
References: <5717AF19.1030102@gmail.com>
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary="----CCEJDCBECU3MOBG155768L2I6HEFYX"
Content-Transfer-Encoding: 8bit
From: Eric Lombrozo <elombrozo@gmail.com>
Date: Thu, 21 Apr 2016 08:28:45 -0700
To: Jochen Hoenicke <hoenicke@gmail.com>, bitcoin-dev@lists.linuxfoundation.org
Message-ID: <CF7E1C6B-F52F-4658-AB24-553AC3493A86@gmail.com>
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW
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 15:30:39 +0000
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 15:28:45 -0000
------CCEJDCBECU3MOBG155768L2I6HEFYX
Content-Transfer-Encoding: 8bit
Content-Type: text/plain;
charset=UTF-8
In practice the probability of this case triggering is on the order of 2^-128 or something astronomically tiny. I've been using BIP32 for a few years already as have many others...I don't think we've ever had to handle this case. Justifiably, many app developers feel like the additional complexity of properly handling this case is not worth the effort.
Having said that, if the handling of this case is simple to implement and easy to isolate in the program flow, I am in favor of doing something along the lines of what you propose.
- Eric
On April 20, 2016 9:32:25 AM PDT, 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
------CCEJDCBECU3MOBG155768L2I6HEFYX
Content-Type: text/html;
charset=utf-8
Content-Transfer-Encoding: 8bit
<html><head></head><body>In practice the probability of this case triggering is on the order of 2^-128 or something astronomically tiny. I've been using BIP32 for a few years already as have many others...I don't think we've ever had to handle this case. Justifiably, many app developers feel like the additional complexity of properly handling this case is not worth the effort.<br>
<br>
Having said that, if the handling of this case is simple to implement and easy to isolate in the program flow, I am in favor of doing something along the lines of what you propose.<br>
<br>
- Eric<br><br><div class="gmail_quote">On April 20, 2016 9:32:25 AM PDT, Jochen Hoenicke via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<pre class="k9mail">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). 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. This has<br />several unfortunate consequences:<br /><br />- All callers of CKDpriv or CKDpub have to check for errors and handle<br /> them appropriately. This shifts the burden to the application<br /> 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 /> missing. E.g. for the default wallet layout, if m/i_H/0 is missing<br /> shou
ld
m/i_H/1 be used for external chain and m/i_H/2 for internal<br /> chain? This would make the wallet handling much more difficult.<br /><br />- It gets even worse with standards like BIP-44. If m/44' is missing<br /> should we use m/45' instead? If m/44'/0' is missing should we use<br /> m/44'/1' instead, using the same addresses as for testnet?<br /> One could also restart with a different seed in this case, but this<br /> wouldn't work if one later wants to support another BIP-43 proposal<br /> and still keep the same wallet.<br /><br />I think the first point alone is reason enough to change this. I am<br />not aware of a BIP-32 application that handles errors like this<br />correctly in all cases. 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 fo
und.
This would<br />be in the same spirit as RFC-6979. This way, the library will always<br />return a valid node for all paths. Of course, in the case where the<br />node is valid according to the current standard the behavior should be<br />unchanged.<br /><br />I think the backward compatibility issues are minimal. The chance<br />that this affects anyone is less than 10^-30. Even if it happens, it<br />would only create some additional addresses (that are not seen if the<br />user downgrades). 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? Is it still possible to<br />change the existing BIP-32 even though it is marked as final? Or<br />should I make a new BIP for this that obsoletes BIP-32?<br /><br />What algorithm is preferred? (bike-shedding) My suggestion:<br /><br />---<br /><br />Change the la
st step
of the private -> private derivation functions to:<br /><br /> . In case parse(I_L) >= n or k_i = 0, the procedure is repeated<br /> at step 2 with<br /> I = HMAC-SHA512(Key = c_par, Data = 0x01 || I_R || ser32(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. I use I_R, since I_L is obviously not very random if I_L >= 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 >= n more likely, the chance is still less than 1 in 2^256). In<br />theory, this loop can be avoided by incrementing i in every iteration,<br />but this would make an implementation error in the "hard to test" path<br />of the program more likely.<br /><br />The other derivati
on
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 /> Jochen<br /><hr /><br />bitcoin-dev mailing list<br />bitcoin-dev@lists.linuxfoundation.org<br /><a href="https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev</a><br /></pre></blockquote></div></body></html>
------CCEJDCBECU3MOBG155768L2I6HEFYX--
|
