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
|
Return-Path: <pieter.wuille@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 86369F3F
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 13 Nov 2019 06:30:32 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ot1-f52.google.com (mail-ot1-f52.google.com
[209.85.210.52])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id BEEB9CF
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 13 Nov 2019 06:30:31 +0000 (UTC)
Received: by mail-ot1-f52.google.com with SMTP id w24so193995otk.6
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Nov 2019 22:30:31 -0800 (PST)
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
:cc; bh=ET6G1QSqmB+hR2tsbURvjfCnrZDEFO7w+vSuESwDfAM=;
b=cNEUt49VIjEBQNG9LmoYjoYUw7k0KNkz/xNW/zbGE2s4Jxp4N97P4fp5O/HtPpNL+R
n5lAr1cGs8LOYfMN78RPSvGZKrZA+4WGQVlOMq8i3spIO19y6EFCAacnviqK0zevwGP/
W93fXfePHU5myN4G54hbT/197ME6GVy/Fi7rtUrmGoDjyksGWr1YT4eMPlVj1U40alpC
TnRad1KIyduDjKThU+v3ph0DD1CJs2J5OWFbOhhILmm8ivQ4WyFbIlzNj1k8JcOAaJ7e
05rsE5WtvcnJcgGq49f8ts1qI+vkTbrhIW3jHJy5xZDoXJRzrkyjaGP0SZDBCptRBq1v
eISQ==
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:cc;
bh=ET6G1QSqmB+hR2tsbURvjfCnrZDEFO7w+vSuESwDfAM=;
b=Xybw4lurVVOQKUa7qSEyKKhnybSHBaYFtB4zipOMhNRLSTe7BQ/BrtEbU5M/vn2z2K
RHhCT/DSMgVgy2SPykNfMJH4TBG4Z1dnLmzeqRawHb4ur474Kl3M/1/Y9coPgpjm/RYs
q+YaNPR7wmeTLKobZjn08XXbgiDU4h8x3EHLqm88HV2BvfaOOtAgInkJeEG7q3VENroI
RZSbq8uC/W0Aqo9REfohu47LQ2IDDuMCsBUYxi9GWilv5TQ/uUeHT8K8ZfUYJm8uafrd
wkaMiDc107fgUdTCw9yHcurShdyjK0LYTVyujcZk3JvNI7EOD16cWKbsJVPQ5fHdgxwi
YQeA==
X-Gm-Message-State: APjAAAU/YYgVPR4WBiIa1wh97sahxDedVPgUlioe0J5D0artfakzMdRA
ZlSnMc9MUzulhGlFMjm8s+9AKLYle4IoUwMtGF+aOWKd
X-Google-Smtp-Source: APXvYqwBF8PngqXPFXpUeN4kE43hkY9qcQDUCfb+0OVWRP5vZbe3ZmW/t0MBweYHyJwgtrQ4Ba818Q1a34NXRGIY7J4=
X-Received: by 2002:a05:6830:224c:: with SMTP id
t12mr1278390otd.299.1573626630552;
Tue, 12 Nov 2019 22:30:30 -0800 (PST)
MIME-Version: 1.0
References: <CAPg+sBjC-D2iWYywj_X-evQoWx56nb0YnASLVwCSCzWT6Guu3A@mail.gmail.com>
<20191108021541.n3jk54vucplryrbl@ganymede>
<CAPg+sBgus6HgYPVbXaAx51nO2ArsR3-6=obe2AwkO8kh11fB6Q@mail.gmail.com>
<611b4e5b-e7cf-adc7-31e1-b5ff24b6574b@mattcorallo.com>
<CAHGSxGv_BQAAkdcxsqVsjphqaoE=Xm05jXhdBnGw+m+vRxeQYQ@mail.gmail.com>
<2sU6YozN9nn30cofkAMhffgjDLZwjG3mvF0nBgOsVQQEY9ROmP72GuHWjnBlF_qa8eeQPU8bxleZqcvRGJgS-uJ2xWYmAm9HjrFWWx_9o8k=@protonmail.com>
In-Reply-To: <2sU6YozN9nn30cofkAMhffgjDLZwjG3mvF0nBgOsVQQEY9ROmP72GuHWjnBlF_qa8eeQPU8bxleZqcvRGJgS-uJ2xWYmAm9HjrFWWx_9o8k=@protonmail.com>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Tue, 12 Nov 2019 22:30:18 -0800
Message-ID: <CAPg+sBio_8vT9NNp39rz7m+omfaRs0Mf6JkET1=caoVwvziJSA@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000052c29805973480f6"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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
Subject: Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot
addresses
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Wed, 13 Nov 2019 06:30:32 -0000
--00000000000052c29805973480f6
Content-Type: text/plain; charset="UTF-8"
On Tue, Nov 12, 2019, 21:33 ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> Good morning all,
>
> It seems to me that adding the length for checksumming purposes need not
> require the length to be *actually* added in the address format.
>
Indeed!
This has the following properties:
>
> * The bech32 address format is retained, and no explicit length is added.
> * There are now two checksum formats: one with just the witness program,
> the other which validates with the witness program length.
> * Readers that do not understand the new checksum format will simply
> reject them without mis-sending to the wrong witness program.
>
That's very close to what I was suggesting: create an improved bech32
algorithm and use that for future addresses, rather than working around the
problem in the address encoding while keeping the existing bech32 checksum.
Sorry if that wasn't clear from my previous email.
In this case, there is no need to even implicitly include the length in the
checksum algorithm. Replacing the "xor 1" at the end of the algorithm to
"xor (2^30 - 1)" would reduce the occurrence of this weakness from 1/32 to
1/2^30, and have no downsides otherwise. I'd like to do some analysis to
ascertain it actually will catch any other kind of insertion/deletion
errors with high probability as well before actually proposing it, though.
There are other solutions which do include the length in some fashion
directly in the checksum calculation, which may be preferable (I need to
analyse things...). It's also possible to do this in such a way that for
33-symbol and 53-symbol data parts (corresponding to P2WPKH and P2WSH
lengths) the new algorithm is defined as identical to the old one. That
would simplify upstream users of a bech32 library (which would then
effectively need no changes at all, apart from updating the
checksum/decoder code).
That brings me to Matt's point: there is no need to do this right now. We
can simply amend BIP173 to only permit length 20 and length 32 (and only
length 20 for v0, if you like; but they're so far apart that permitting
both shouldn't hurt), for now. Introducing the "new" address format (the
one using an improved checksum algorithm) only needs to be there in time
for when a non-32-byte-witness-program would come in sight.
Of course, I should update BIP173 to indicate the issue, and have a
suggested improvement for other users of bech32, if they feel this issue is
significant enough.
Cheers,
--
Pieter
--00000000000052c29805973480f6
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto"><div><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D=
"gmail_attr">On Tue, Nov 12, 2019, 21:33 ZmnSCPxj via bitcoin-dev <<a hr=
ef=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank" rel=
=3D"noreferrer">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br></d=
iv><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left=
:1px #ccc solid;padding-left:1ex">Good morning all,<br>
<br>
It seems to me that adding the length for checksumming purposes need not re=
quire the length to be *actually* added in the address format.<br></blockqu=
ote></div></div><div dir=3D"auto"><br></div><div dir=3D"auto">Indeed!</div>=
<div dir=3D"auto"><br></div><div dir=3D"auto"><div class=3D"gmail_quote"><b=
lockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px =
#ccc solid;padding-left:1ex">
This has the following properties:<br>
<br>
* The bech32 address format is retained, and no explicit length is added.<b=
r>
* There are now two checksum formats: one with just the witness program, th=
e other which validates with the witness program length.<br>
=C2=A0 * Readers that do not understand the new checksum format will simply=
reject them without mis-sending to the wrong witness program.<br></blockqu=
ote></div></div><div dir=3D"auto"><br></div><div dir=3D"auto">That's ve=
ry close to what I was suggesting: create an improved bech32 algorithm and =
use that for future addresses, rather than working around the problem in th=
e address encoding while keeping the existing bech32 checksum. Sorry if tha=
t wasn't clear from my previous email.</div><div dir=3D"auto"><br></div=
><div dir=3D"auto">In this case, there is no need to even implicitly includ=
e the length in the checksum algorithm. Replacing the "xor 1" at =
the end of the algorithm to "xor (2^30 - 1)" would reduce the occ=
urrence of this weakness from 1/32 to 1/2^30, and have no downsides otherwi=
se. I'd like to do some analysis to ascertain it actually will catch an=
y other kind of insertion/deletion errors with high probability as well bef=
ore actually proposing it, though.<br></div><div dir=3D"auto"><br></div><di=
v dir=3D"auto">There are other solutions which do include the length in som=
e fashion directly in the checksum calculation, which may be preferable (I =
need to analyse things...). It's also possible to do this in such a way=
that for 33-symbol and 53-symbol data parts (corresponding to P2WPKH and P=
2WSH lengths) the new algorithm is defined as identical to the old one. Tha=
t would simplify upstream users of a bech32 library (which would then effec=
tively need no changes at all, apart from updating the checksum/decoder cod=
e).</div><div dir=3D"auto"><br></div><div dir=3D"auto">That brings me to Ma=
tt's point: there is no need to do this right now. We can simply amend =
BIP173 to only permit length 20 and length 32 (and only length 20 for v0, i=
f you like; but they're so far apart that permitting both shouldn't=
hurt), for now. Introducing the "new" address format (the one us=
ing an improved checksum algorithm) only needs to be there in time for when=
a non-32-byte-witness-program would come in sight.</div><div dir=3D"auto">=
<br></div><div dir=3D"auto">Of course, I should update BIP173 to indicate t=
he issue, and have a suggested improvement for other users of bech32, if th=
ey feel this issue is significant enough.</div><div dir=3D"auto"><br></div>=
<div dir=3D"auto">Cheers,</div><div dir=3D"auto"><br></div><div dir=3D"auto=
">--=C2=A0</div><div dir=3D"auto">Pieter</div><div dir=3D"auto"><br></div><=
div dir=3D"auto"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quot=
e" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
</blockquote></div></div></div>
--00000000000052c29805973480f6--
|
