path: root/68/6352fd27fd1f95978b2fdd81a9d51301697438

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 D8779A5E
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 10 Nov 2019 21:52:01 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ot1-f54.google.com (mail-ot1-f54.google.com
	[209.85.210.54])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id ACCB5FE
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 10 Nov 2019 21:52:00 +0000 (UTC)
Received: by mail-ot1-f54.google.com with SMTP id t4so9732707otr.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 10 Nov 2019 13:52:00 -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; 
	bh=Oy+/E/JM6WDJaUkneRbizCsEWefSXocReS6yvkcDwSw=;
	b=B8bjwHBjdTGf3HxL67NGaZa8kvvfCicBkMYUGp4rux87EzFNKLZkOb903SqnpEhhKQ
	NnlR3cj9VBwZNggoUHu3huz/SdlB2FTIpQVOVcWrsyWKI6LYMofSjEJ4IC6cwOrUTyim
	QavMTBQ1BKXoQa875eOLqt8l4BxLzJJCovuNkxS/uE7RgTd1enFzCA4JPs7NCcE//FAp
	JcwgclSrekEnDGhzxv+EapX4kAJWYLieGh8d0jpuyW/n3cQasiYLshDq3Y/cNMmyohd8
	CExKnlGJryV0EwOD8No6wBywOU6u+nRWfhpC00Hmh0YKFuG4pZgTZiUALZ4wpheKjpfe
	N2Ww==
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=Oy+/E/JM6WDJaUkneRbizCsEWefSXocReS6yvkcDwSw=;
	b=JBevrFnHzi/3mxkO3A8wpPwKqe0B3YOpa+gqqrCZbBJWWOapK008s8FtfSB0KHbKuG
	29j94IH6xUH+9v1/0TDSCDvjoApGIYgG/vRRsYMz4PpyQWr7aW4EJI2OEC/4wBFxC5gs
	+6aFghmrWJCJJAQ64FIJePtGliIn+hfpnwRLOuLlAiFABuWlOdNIFZ+26hxv5aBY6HOL
	zPdQjskmVmXY6aof50V35MW6UJ9Mcy9FCAcXa5yrxowp8m28f9ZBkqE2ifIZv0OyOJHa
	Ll2Nv03ceYuZYm38qX9CUSSH3iir8A+jw3yyzqH6Iw46TBSjwPSdXyYSg24We/CgCkdx
	tXHQ==
X-Gm-Message-State: APjAAAVZbew0sE3MhdrWo+M3WK++491mrAgkHT1EvYBTAVwG1e26uRpu
	fC88MKsuzsEtChAqkxrV8rDDvqlUntyG8OTOPnwe0w==
X-Google-Smtp-Source: APXvYqxWeyH37ClgzWaHGwmgXBMVdcPZPn2UfG7bdIwXEAnkHoIsKys+kCx+yjtZs4G/IBleq6asjfbNwIAQkLLd6ss=
X-Received: by 2002:a9d:4604:: with SMTP id y4mr16330664ote.10.1573422719558; 
	Sun, 10 Nov 2019 13:51:59 -0800 (PST)
MIME-Version: 1.0
References: <CAPg+sBjC-D2iWYywj_X-evQoWx56nb0YnASLVwCSCzWT6Guu3A@mail.gmail.com>
	<20191108021541.n3jk54vucplryrbl@ganymede>
In-Reply-To: <20191108021541.n3jk54vucplryrbl@ganymede>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Sun, 10 Nov 2019 13:51:48 -0800
Message-ID: <CAPg+sBgus6HgYPVbXaAx51nO2ArsR3-6=obe2AwkO8kh11fB6Q@mail.gmail.com>
To: "David A. Harding" <dave@dtrt.org>,
	Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000047e77405970506f1"
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: Sun, 10 Nov 2019 21:52:02 -0000

--00000000000047e77405970506f1
Content-Type: text/plain; charset="UTF-8"

On Thu, Nov 7, 2019, 18:16 David A. Harding <dave@dtrt.org> wrote:

> On Thu, Nov 07, 2019 at 02:35:42PM -0800, Pieter Wuille via bitcoin-dev
> wrote:
> > In the current draft, witness v1 outputs of length other
> > than 32 remain unencumbered, which means that for now such an
> > insertion or erasure would result in an output that can be spent by
> > anyone. If that is considered unacceptable, it could be prevented by
> > for example outlawing v1 witness outputs of length 31 and 33.
>
> Either a consensus rule or a standardness rule[1] would require anyone
> using a bech32 library supporting v1+ segwit to upgrade their library.
> Otherwise, users of old libraries will still attempt to pay v1 witness
> outputs of length 31 or 33, causing their transactions to get rejected
> by newer nodes or get stuck on older nodes.  This is basically the
> problem #15846[2] was meant to prevent.
>
> If we're going to need everyone to upgrade their bech32 libraries
> anyway, I think it's probably best that the problem is fixed in the
> bech32 algorithm rather than at the consensus/standardness layer.
>

Admittedly, this affecting development of consensus or standardness rules
would feel unnatural. In addition, it also has the potential downside of
breaking batched transactions in some settings (ask an exchange for a
withdrawal to a invalid/nonstandard version, which they batch with other
outputs that then get stuck because the transaction does not go through).

So, Ideally this is indeed solved entirely on the bech32/address encoding
side of things. I did not initially expect the discussion here to go in
that direction, as that could come with all problems that rolling out a new
address scheme in the first place has. However, there may be a way to
mostly avoid those problems for the time being, while also not having any
impact on consensus or standardness rules.

I believe that most new witness programs we'd want to introduce anyway will
be 32 bytes in the future, if the option exists. It's enough for a 256-bit
hash (which has up to 128-bit collision security, and more than 128 bits is
hard to achieve in Bitcoin anyway), or for X coordinates directly. Either
of those, plus a small version number to indicate the commitment structure
should be enough to encode any spendability condition we'd want with any
achievable security level.

With that observation, I propose the following. We amend BIP173 to be
restricted to witness programs of length 20 or 32 (but still support
versions other than 0). This seems like it may be sufficient for several
years, until version numbers run out. I believe that some wallet
implementations already restrict sending to known versions only, which
means effectively no change for them in addition to normal deployment.

In the mean time we develop a variant of bech32 with better
insertion/erasure detecting properties, which will be used for witness
programs of length different from 20 or 32. If we make sure that there are
never two distinct valid checksum algorithms for the same output, I don't
believe there is any need for a new address scheme or a different HRP. The
latter is something I'd strongly try to avoid anyway, as it would mean
additional cognitive load on users because of another visually distinct
address style, plus more logistical overhead (coordination and keeping
track of 2 HRPs per chain).

I believe improving bech32 itself is preferable over changing the way
segwit addresses use bech32, as that can be done without making addresses
even longer. Furthermore, the root of the issue is in bech32, and it is
simplest to fix things there. The easiest solution is to simply change the
constant 1 that is xor'ed into the checksum before encoding it to a 30-bit
number. This has the advantage that a single checksum is never valid for
both algoritgms simultaneously. Another approach is to implicitly including
the length into the checksummed data.

What do people think?

Cheers,

-- 
Pieter

--00000000000047e77405970506f1
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 Thu, Nov 7, 2019, 18:16 David A. Harding &lt;<a href=3D"mai=
lto:dave@dtrt.org">dave@dtrt.org</a>&gt; wrote:<br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd=
ing-left:1ex">On Thu, Nov 07, 2019 at 02:35:42PM -0800, Pieter Wuille via b=
itcoin-dev wrote:<br>
&gt; In the current draft, witness v1 outputs of length other<br>
&gt; than 32 remain unencumbered, which means that for now such an<br>
&gt; insertion or erasure would result in an output that can be spent by<br=
>
&gt; anyone. If that is considered unacceptable, it could be prevented by<b=
r>
&gt; for example outlawing v1 witness outputs of length 31 and 33.<br>
<br>
Either a consensus rule or a standardness rule[1] would require anyone<br>
using a bech32 library supporting v1+ segwit to upgrade their library.<br>
Otherwise, users of old libraries will still attempt to pay v1 witness<br>
outputs of length 31 or 33, causing their transactions to get rejected<br>
by newer nodes or get stuck on older nodes.=C2=A0 This is basically the<br>
problem #15846[2] was meant to prevent.<br>
<br>
If we&#39;re going to need everyone to upgrade their bech32 libraries<br>
anyway, I think it&#39;s probably best that the problem is fixed in the<br>
bech32 algorithm rather than at the consensus/standardness layer.<br></bloc=
kquote></div></div><div dir=3D"auto"><br></div><div dir=3D"auto">Admittedly=
, this affecting development of consensus or standardness rules would feel =
unnatural. In addition, it also=C2=A0<span style=3D"font-family:sans-serif"=
>has the potential downside of breaking batched transactions in some settin=
gs (ask an exchange for a withdrawal to a invalid/nonstandard version, whic=
h they batch with other outputs that then get stuck because the transaction=
 does not go through).</span></div><div dir=3D"auto"><span style=3D"font-fa=
mily:sans-serif"><br></span></div><div dir=3D"auto"><span style=3D"font-fam=
ily:sans-serif">So, Ideally this is indeed solved entirely on the bech32/ad=
dress encoding side of things. I</span>=C2=A0did not initially expect the d=
iscussion here to go in that direction, as that could come with all problem=
s that rolling out a new address scheme in the first place has. However, th=
ere may be a way to mostly avoid those problems for the time being, while a=
lso not having any impact on consensus or standardness rules.</div><div dir=
=3D"auto"><div dir=3D"auto"><br></div><div dir=3D"auto">I believe that most=
 new witness programs we&#39;d want to introduce anyway will be 32 bytes in=
 the future, if the option exists. It&#39;s enough for a 256-bit hash (whic=
h has up to 128-bit collision security, and more than 128 bits is hard to a=
chieve in Bitcoin anyway), or for X coordinates directly. Either of those, =
plus a small version number to indicate the commitment structure should be =
enough to encode any spendability condition we&#39;d want with any achievab=
le security level.</div><div dir=3D"auto"><br></div><div dir=3D"auto">With =
that observation, I propose the following. We amend BIP173 to be restricted=
 to witness programs of length 20 or 32 (but still support versions other t=
han 0). This seems like it may be sufficient for several years, until versi=
on numbers run out. I believe that some wallet implementations already rest=
rict sending to known versions only, which means effectively no change for =
them in addition to normal deployment.</div><div dir=3D"auto"><br></div><di=
v dir=3D"auto">In the mean time we develop a variant of bech32 with better =
insertion/erasure detecting properties, which will be used for witness prog=
rams of length different from 20 or 32. If we make sure that there are neve=
r two distinct valid checksum algorithms for the same output, I don&#39;t b=
elieve there is any need for a new address scheme or a different HRP. The l=
atter is something I&#39;d strongly try to avoid anyway, as it would mean a=
dditional cognitive load on users because of another visually distinct addr=
ess style, plus more logistical overhead (coordination and keeping track of=
 2 HRPs per chain).</div><div dir=3D"auto"><br></div><div dir=3D"auto">I be=
lieve improving bech32 itself is preferable over changing the way segwit ad=
dresses use bech32, as that can be done without making addresses even longe=
r. Furthermore, the root of the issue is in bech32, and it is simplest to f=
ix things there. The easiest solution is to simply change the constant 1 th=
at is xor&#39;ed into the checksum before encoding it to a 30-bit number. T=
his has the advantage that a single checksum is never valid for both algori=
tgms simultaneously. Another approach is to implicitly including the length=
 into the checksummed data.</div><div dir=3D"auto"><br></div><div dir=3D"au=
to">What do people think?</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><div dir=3D=
"auto"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
</blockquote></div></div></div>

--00000000000047e77405970506f1--