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
|
Return-Path: <jameson.lopp@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 52E22CA2
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 6 Mar 2016 20:04:35 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lb0-f179.google.com (mail-lb0-f179.google.com
[209.85.217.179])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6677BEC
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 6 Mar 2016 20:04:34 +0000 (UTC)
Received: by mail-lb0-f179.google.com with SMTP id xr8so13391020lbb.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 06 Mar 2016 12:04:34 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:date:message-id:subject:from:to;
bh=Qb3FKjKIPlMFcJuBd7roX3KM0W74BnjANnBebfWJrcU=;
b=ur38RwsfxHZ05MwHQyIjF8COmfker6qrtSnZw18++MDNzZoL+9Vd8as2T7Yx4v5wYD
M3xrFHs+B67pYslrx4lNokLC1oXLERQ+mRQaS26ABCU6bsT509rXio6XFf8xEK1F42yN
C8k+12w2xDq42tGISWlVsiMNWPAgUO+DeOWy8OzdiCRmZhRTkrOdgWXEnBgvEZa0ZE6O
faFi+7hZVQLdnw9XAUkHvqi7+ayQckhEJvgpERTcTB8UXERYPuqneYeqn229n3MC0cK4
RqJj5oKKvdxyI4cNRl1PkxZ++Jap7hy9GfLfmmzkQ9vtW4cW7PY1nB9D2VY3rdTcAOve
eYsA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:date:message-id:subject:from:to;
bh=Qb3FKjKIPlMFcJuBd7roX3KM0W74BnjANnBebfWJrcU=;
b=J8pyDZkU7hJ7jNERnCtk0fwoELTfXlWxTU4xQKat8LePoqeYKhlKvC8ep+WeUYiLuI
HhbWvdqSTLmfronzwKXvpOS87XMyM+5hyp/IUx6nhiDU2kAlh9AN62nvdI7dF2+gMQOO
XKPj4sf/gohvFDmpHhD1ao8nKKRtI4+vP3DuDuf/HuLDtbpPCvkyg2Mcd3AeSZpFbP6M
JK/zlHK9VSWbgyLSwisHgNeLJKd1EruN9K+E58/T8nZZDIxUwXp3sGhY/G6Mjg9I3334
8itDxk9ZWtM8PB3Z9CVho9AN77VjI9SvrnrqYGp7dcsVNLmKewy/6zpl+z+BtdZsCRnu
XWXA==
X-Gm-Message-State: AD7BkJIiY+qWf2H2B9uQgszdsA8t8SznAOawBClbgjfBH1EAVmoYSqO1BH6Lc8G9NhiQWcnwNylcnkvjNsUe7g==
MIME-Version: 1.0
X-Received: by 10.112.125.9 with SMTP id mm9mr5024243lbb.113.1457294672524;
Sun, 06 Mar 2016 12:04:32 -0800 (PST)
Received: by 10.25.83.139 with HTTP; Sun, 6 Mar 2016 12:04:32 -0800 (PST)
Date: Sun, 6 Mar 2016 15:04:32 -0500
Message-ID: <CADL_X_cFOknYejoQPRarwRxpFz5D8ffqfohh799NR7e2_Jgx4w@mail.gmail.com>
From: Jameson Lopp <jameson.lopp@gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=089e0112c0224a0185052d66db27
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: Mon, 07 Mar 2016 20:59:06 +0000
Subject: [bitcoin-dev] BIP44 & BIP32 chain address look-ahead limits
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: Sun, 06 Mar 2016 20:04:35 -0000
--089e0112c0224a0185052d66db27
Content-Type: text/plain; charset=UTF-8
I recently ran into an issue while importing a Mycelium HD wallet where it
was not finding all of my funds - upon further investigation with Mycelium
devs we realized that the wallet was following the BIP44 spec correctly,
but BIP44 may have a flaw.
The problem was a result of my creating 16 transactions in Mycelium in a
fairly short timeframe, but the first 15 transactions ended up never
confirming while the 16th was confirmed. As a result, when I later
reimported the account from the master seed, the chain derivation stopped
upon hitting this large gap of unused addresses on the internal / change
chain.
BIP44 recommends that there need not be a lookahead on internal chains
"because internal chains receive only coins that come from the associated
external chains."
https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki#Address_gap_limit
BIP32 also notes that "the look-ahead for internal chains can be very
small, as no gaps are to be expected here."
https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#Full_wallet_sharing_m
It seems to me that there /is/ an edge case that can result in significant
gaps in internal chain address usage and as such, the recommendation should
be to look ahead on both external and internal chains when performing
account discovery. On a related note, the recommended look-ahead of 20 may
not be safe enough - perhaps it should be raised to 100 if not higher.
In addition to recommending a larger look-ahead, it may also be advisable
for BIP44 to recommend that wallets "fill in" gaps of unused chain
addresses by "looking back" from the current tip of the internal chain's
index when the wallet decides to create a new change address. This could
help mitigate the size of gaps caused by failed transactions.
- Jameson
--089e0112c0224a0185052d66db27
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div><div><div><div>I recently ran into an issue while imp=
orting a Mycelium HD wallet where it was not finding all of my funds - upon=
further investigation with Mycelium devs we realized that the wallet was f=
ollowing the BIP44 spec correctly, but BIP44 may have a flaw.<br><br></div>=
The problem was a result of my creating 16 transactions in Mycelium in a fa=
irly short timeframe, but the first 15 transactions ended up never confirmi=
ng while the 16th was confirmed. As a result, when I later reimported the a=
ccount from the master seed, the chain derivation stopped upon hitting this=
large gap of unused addresses on the internal / change chain.<br><br></div=
>BIP44 recommends that there need not be a lookahead on internal chains &qu=
ot;because
internal chains receive only coins that come from the associated external c=
hains." <a href=3D"https://github.com/bitcoin/bips/blob/master/bip-004=
4.mediawiki#Address_gap_limit">https://github.com/bitcoin/bips/blob/master/=
bip-0044.mediawiki#Address_gap_limit</a><br><br></div>BIP32 also notes that=
"the look-ahead for internal chains can be very small, as no gaps are=
to be expected here." <a href=3D"https://github.com/bitcoin/bips/blob=
/master/bip-0032.mediawiki#Full_wallet_sharing_m">https://github.com/bitcoi=
n/bips/blob/master/bip-0032.mediawiki#Full_wallet_sharing_m</a><br><br></di=
v><div>It seems to me that there /is/ an edge case that can result in signi=
ficant gaps in internal chain address usage and as such, the recommendation=
should be to look ahead on both external and internal chains when performi=
ng account discovery. On a related note, the recommended look-ahead of 20 m=
ay not be safe enough - perhaps it should be raised to 100 if not higher.<b=
r><br></div><div>In addition to recommending a larger look-ahead, it may al=
so be advisable for BIP44 to recommend that wallets "fill in" gap=
s of unused chain addresses by "looking back" from the current ti=
p of the internal chain's index when the wallet decides to create a new=
change address. This could help mitigate the size of gaps caused by failed=
transactions.<br></div><div><br></div>- Jameson<br></div>
--089e0112c0224a0185052d66db27--
|
