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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
|
Return-Path: <lloyd.fourn@gmail.com>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
by lists.linuxfoundation.org (Postfix) with ESMTP id C6EBCC0051
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 5 Oct 2020 02:50:40 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by fraxinus.osuosl.org (Postfix) with ESMTP id ADB0F84078
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 5 Oct 2020 02:50:40 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from fraxinus.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id vK7by22JIDMl
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 5 Oct 2020 02:50:39 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-io1-f41.google.com (mail-io1-f41.google.com
[209.85.166.41])
by fraxinus.osuosl.org (Postfix) with ESMTPS id 30ADF84070
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 5 Oct 2020 02:50:13 +0000 (UTC)
Received: by mail-io1-f41.google.com with SMTP id 67so4248309iob.8
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 04 Oct 2020 19:50:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=5+DwuXU0ZD1kmKzbnXoOpGkjPaQaF3xrd4tInOQuY4s=;
b=b7GXaru9+nbI+PNkQ+jIInoFzeOMxUzY6BXTYTFsZCGgHkiBq2E475M2LxvOhWyFJW
bZHbZYkLNT23xJbCu8typLu3K2IY4fggWwl2dbX3CSDyECU7lyoHRvxvYbjJD8QdMmr6
DfM5/c1NQZeSAWOzwltcAHhcdzKupHZ8UDywwip3tsk3iqLjASybV31/DTW3vqN1fMva
xrE48yA8xvazv3goMqRPQ4E+VSR6AeiI/5nvfxQW2OC0R5Z3rLTyBhmbhrXMGm+YaSOa
GxiiEQgsuuAljSfFUb5y46ih5xlnQhBhjbGnP9BGaFJE+4D20ITw63lqejQTtGPoiWzY
ZFrA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to;
bh=5+DwuXU0ZD1kmKzbnXoOpGkjPaQaF3xrd4tInOQuY4s=;
b=ChNq+UIVIt7LI0oVpuRYcpPoxyLyDl0dQhN9F/GA+O9XI9TgJ4NA/nzmKBLQB5fpar
v741JD3/z6gT1rtjF/phC46qGTo300NhVwAlHz3JM3E2NdaLsoehmFK4d8lsY6BIzUiO
brNhjLcgMQRIeTuGbKTu7InUh/YZI46zCaDz6bP0Yhl0CMpiEFtbQWvK4Feoqh8bCayx
AL0U7GWj1sdfv6+2ZmBL9mDSG5S32peN+iRujZzuiDpOZ2e8+Y6v+WRL/SX57hWfIJ1V
qdo+t2SGAteeZrTMzTPUz0+DO11q34OKe7tgHzJ9SB8ng60Mvgtb6H2Md6wnZIg7pO6C
6QAQ==
X-Gm-Message-State: AOAM530kBY2/G+7ZDtjlPT8n1jnr0oMuLM4U2/BJeewcVitx8mMX6vbM
K+y0OJChxqQjeC3VKk9oHOZdOUcL8v0PD3iZ0Lg=
X-Google-Smtp-Source: ABdhPJxYkTGtDQfSFhU6u28QRmG3rmAxDE+RYdyNLn3bwoywZUZDuCgbQkJslUFA8yiZZgieGzzZ4uQHEvNp1t1sRws=
X-Received: by 2002:a05:6638:24d1:: with SMTP id
y17mr10932701jat.3.1601866212179;
Sun, 04 Oct 2020 19:50:12 -0700 (PDT)
MIME-Version: 1.0
References: <CACmzyU-XVNxLQ8o5CQrhmxGocK6yAX1nCFT2WQ-si157y=dfwQ@mail.gmail.com>
In-Reply-To: <CACmzyU-XVNxLQ8o5CQrhmxGocK6yAX1nCFT2WQ-si157y=dfwQ@mail.gmail.com>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Mon, 5 Oct 2020 13:49:48 +1100
Message-ID: <CAH5Bsr2FKJoroxnv+TLh6gs7KeaHT2fJDEA8JByrSTTLFf0_5A@mail.gmail.com>
To: Leonardo Comandini <leonardocomandini@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
X-Mailman-Approved-At: Mon, 05 Oct 2020 08:23:09 +0000
Subject: Re: [bitcoin-dev] Is BIP32's chain code needed?
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol 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: Mon, 05 Oct 2020 02:50:40 -0000
Hi Leonardo,
I can't tell you what the BIP32 author was thinking but if I put
myself in their shoes these are the reasons I might have done it this
way:
1. Use HMAC rather than normal SHA2 -- this is just best practice for
key derivation (even though I don't think it would make a difference
to security if you are strictly following the spec).
2. Use 512-bit rather than 256-bit -- Probably something to do with
(1) -- since I'm using an HMAC I've gotta put something as the key. I
don't want re-use the 256-bits for the secp256k1 secret key for this
since an integer mod q is not the same as 256 random bits (or I don't
want to have to make the argument in the design doc that it actually
is; plus what if someone starts using this for different curve and I'm
not around to tell them no). So I split the 512-bits and use the last
256bits as the key for the child derivation.
I don't think there is any fundamental flaw with what you suggest (I
am doing something similar for a project). I guess the issues you
pointed out with the scheme were probably not on the author's mind. To
me they don't seem too severe but I haven't spent much time developing
wallets.
LL
On Wed, Sep 30, 2020 at 4:02 AM Leonardo Comandini via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> Hi all,
>
> BIP32 [1] says: "In order to prevent these from depending solely on the key
> itself, we extend both private and public keys first with an extra 256 bits of
> entropy. This extension, called the chain code...".
>
> My argument is that the chain code is not needed.
> To support such claim, I'll show a schematic of BIP32 operations to be compared
> with an alternative proposal and discuss the differences.
>
> I have two main questions:
> - Is this claim false?
> - Has anyone shared this idea before?
>
> ## BIP32 schematic
>
> Let `G` be the secp256k1 generator.
> Let `i` be the child index.
> Let `(p, P=pG)` and `(p_i, P_i=p_iG)` be the parent and i-th child keypairs
> respectively.
> Let `c` and `c_i` be the corresponding chain codes.
> Let `h1, h2, h3, h4` be hash functions so that the formulae below match the
> definitions given in BIP32 [2].
> Define private and public child derivation as follow:
>
> p_i(p, c, i) = (i < 2^31) p + h1(c, pG, i)
> (i >= 2^31) p + h2(c, p, i)
>
> c_i(p, c, i) = (i < 2^31) h3(c, pG, i)
> (i >= 2^31) h4(c, p, i)
>
> P_i(P, c, i) = (i < 2^31) P + h1(c, P, i)G
> (i >= 2^31) not possible
>
> c_i(P, c, i) = (i < 2^31) h3(c, P, i)
> (i >= 2^31) not possible
>
> The above formula for unhardened public derivation resembles a pay-to-contract
> [3] scheme.
>
> ## Alternative proposal
>
> Let `h` be an adequately strong hash function which converts its output to
> integer.
> Consider the following derivation scheme:
>
> p_i(p, i) = (i < 2^31) p + h(pG, i)
> (i >= 2^31) h(p, i)
>
> P_i(P, i) = (i < 2^31) P + h(P, i)G
> (i >= 2^31) not possible
>
> Which is basically the above one without the chaincode.
>
> ## Considerations
>
> I claim that this has the same properties as BIP32 [4]:
> - The problem of finding `p` given `p_i, i` relies on brute-forcing `h` in the
> same way the analogous problem relies on brute-forcing `h2` in BIP32.
> - The problem of determining whether `{p_i, i}_i=1..n` are derived from a common
> parent `p` relies on brute-forcing `h` in the same way the analogous problem
> relies on brute-forcing `h2` in BIP32.
> - Given `i < 2^31, p_i, P`, an attacker can find `p`. This is analogous to
> BIP32, where the parent extended pubkey is needed (`P, c`). One could argue
> that `c` is never published on the blockchain, while `P` may be. On the other
> hand most wallets either use hardened derivation (so the attack does not work)
> or derive scriptpubkeys from keys at the same depth (so the parent key is
> never published on the blockchain).
> Anyway, if the parent public key is kept as secret as BIP32 extended keys are,
> then the situation is analogous to BIP32's.
>
> _If_ these claims are correct, the proposed derivation scheme has two main
> advantages:
>
> 1) Shorter backups for public and private derivable keys
>
> Backups are especially relevant for output descriptors. For instance, when using
> a NofM multisig, each participant must backup M-1 exteneded public keys and its
> extended private key, which can be included in an output descriptor. Using the
> proposed derivation reduces the backup size by `~M*32` bytes.
>
> 2) User-friendly backup for child keys
>
> Most wallets use user-friendly backups, such as BIP39 [5] mnemonics. They map
> 16-32 bytes of entropy to 12-24 words. However BIP32 exteneded keys are at least
> 64(65) bytes (key and chain code), so they cannot be mapped back to a
> mnemonic.
>
> A common wallet setup is (`->` one-way derivation, `<->` two-way mapping):
>
> entropy (16-32 bytes) <-> user-friendly backup
> -> BIP32 extended key (64-65 bytes)
> -> BIP32 extended child keys (64-65 bytes)
>
> With the proposed derivation, it would be possible to have:
>
> derivable private key (32 bytes) <-> user-friendly backup
> -> derivable public key (33 bytes) <-> user-friendly backup
> -> derivable child keys (32-33 bytes) <-> user-friendly backup
>
> This would allow having mnemonics for subaccount keys.
>
> ## References
>
> [1] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
>
> [2] h1, h2, h3 and h4 can be defined as follows
>
> Ip(c, p, i) = (i >= 2^31) HMAC-SHA512(c, 0x00 || ser256(p) || ser32(i))
> (i < 2^31) HMAC-SHA512(c, pG || ser32(i))
>
> IP(c, P, i) = (i >= 2^31) not possible
> (i < 2^31) HMAC-SHA512(c, P || ser32(i))
>
> h1(c, P, i) = parse256(IP(c, P, i)[:32])
> h2(c, p, i) = parse256(Ip(c, p, i)[:32])
> h3(c, P, i) = IP(c, P, i)[32:]
> h4(c, p, i) = Ip(c, p, i)[32:]
>
> [3] https://blockstream.com/sidechains.pdf Appendix A
>
> [4] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#security
>
> [5] https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
>
>
> --
> Leonardo
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
|
