path: root/76/36791364c07279799860d2f20569605ad042bc

Return-Path: <clarkmoody@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 101CBC6D
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 13 Nov 2019 02:57:26 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lf1-f49.google.com (mail-lf1-f49.google.com
	[209.85.167.49])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 006E2DF
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 13 Nov 2019 02:57:22 +0000 (UTC)
Received: by mail-lf1-f49.google.com with SMTP id z12so591142lfj.9
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 12 Nov 2019 18:57:22 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=clarkmoody-com.20150623.gappssmtp.com; s=20150623;
	h=mime-version:references:in-reply-to:from:date:message-id:subject:to; 
	bh=K9qVxzHG45cSWdpnQSniuJKYt2Zhy8ePz+q4SGWlA5U=;
	b=CLirjsdpG5/j9ucbgt8XKymkWg13iIIWkARwAXmDHTz4nVDzQFX45c0cmn7hA7b4SL
	5O7eWNJgnbG3So3jFwR0sqdXOF8DjcoOJtabCzTLIVqrSpLZgmdyc0FWzDleTDm3EkWT
	Cx6W4vtiDVJqMRWUC0+bVIag28GcYnVbFpkuNQ7H4Egni523YPlF7xPA6l7gzAd8nQiL
	q27N0zlRy1radsigPnhDimbZyy7MJC0Dk98oX+4qrZlWdJFdKytl9I1nt2b6TQ8j7f/o
	GwvtaxytuoNmXmnltsoMoHwP0bjzlqPO5I5bmpXK8dVg5O8JkKOCDUQBW9kK9tjDSeJ7
	aH+A==
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=K9qVxzHG45cSWdpnQSniuJKYt2Zhy8ePz+q4SGWlA5U=;
	b=fC0pYA9WS9WAMe1coE/9ebYvXGyMO/zm5x1O/QY0KZ5jLVXHkY4EWyDZuyVI9sID+m
	+RW+4iNYDIiaNhWiIaxf+hGxq+iJvO+AhS96wbzz/iJI0Ji5t6/7gntRJJs9LXzKu/d7
	RuhD+PulCcrBvYF/kxBbRXXoeMsv0ITmeduNeKzYAW9Ayy8gP1SO4O8F/Jr2+uCwSjiW
	ufbGNv8DJaGWwr7v1FC/f4X0y/PCzMuWeExQY6yN+uRi0s4thlkVqjwr6HHO4dVad2jo
	sP5b7LR0YB61cd0J0iFcmWcWxlqOJBJ20IoOWtYEfj7OK3RhG/bff0dqnL6zwjj77GwF
	EWPg==
X-Gm-Message-State: APjAAAUnfUcI8wQj3nTaJk9kF0WJ2s2GlP3VohD6mqLtjoYBl+c3AnbU
	UwOZQsG3cobbmSc8dIBepaAeCHHW5fU1v8XRpCTSHfQJ
X-Google-Smtp-Source: APXvYqxLDKfGWTF0NMXkd2Euh9NvNB8U93FLlUaYuSkgZoNAGsRNeWfgHTdqBmN8NoBsqroC75bces2wMlnpeDzKxhk=
X-Received: by 2002:a19:800a:: with SMTP id b10mr727946lfd.15.1573613840596;
	Tue, 12 Nov 2019 18:57:20 -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>
In-Reply-To: <611b4e5b-e7cf-adc7-31e1-b5ff24b6574b@mattcorallo.com>
From: Clark Moody <clark@clarkmoody.com>
Date: Tue, 12 Nov 2019 20:56:54 -0600
Message-ID: <CAHGSxGv_BQAAkdcxsqVsjphqaoE=Xm05jXhdBnGw+m+vRxeQYQ@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000fb834c05973185fc"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, 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
X-Mailman-Approved-At: Wed, 13 Nov 2019 02:59:12 +0000
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 02:57:26 -0000

--000000000000fb834c05973185fc
Content-Type: text/plain; charset="UTF-8"

I agree on all points. The address space already brings enough confusion to
users out there. As it stands, we can use script version and program length
for address validity. Sneaking an alternate checksum into the mix for
different length programs lets us lean on our parsing libraries and not
increase cognitive load for users.


-Clark


On Sun, Nov 10, 2019 at 7:02 PM Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Seems good to me, though I'm curious if we have any (even vaguely)
> immediate need for non-32/20-byte Segwit outputs? It seems to me this
> can be resolved by just limiting the size of bech32 outputs and calling
> it a day - adding yet another address format has very significant
> ecosystem costs, and if we don't anticipate needing it for 5 years (if
> at all)...lets not jump to pay that cost.
>
> Matt
>
> On 11/10/19 9:51 PM, Pieter Wuille via bitcoin-dev wrote:
> > On Thu, Nov 7, 2019, 18:16 David A. Harding <dave@dtrt.org
> > <mailto: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
> >
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--000000000000fb834c05973185fc
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:tahoma,s=
ans-serif;font-size:small;color:#000000">I agree on all=C2=A0points. The ad=
dress space already brings enough confusion
 to users out there. As it=C2=A0stands, we can use script version and progr=
am
 length for address validity. Sneaking an alternate checksum into the=20
mix for different length programs lets us lean on our parsing libraries=20
and not increase cognitive load for users.</div><div><div dir=3D"ltr" class=
=3D"gmail_signature" data-smartmail=3D"gmail_signature"><div><br></div><div=
><br></div><div>-Clark</div><div></div></div></div><br></div><br><div class=
=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sun, Nov 10, 2019=
 at 7:02 PM Matt Corallo via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@=
lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wr=
ote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px=
 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Seems good =
to me, though I&#39;m curious if we have any (even vaguely)<br>
immediate need for non-32/20-byte Segwit outputs? It seems to me this<br>
can be resolved by just limiting the size of bech32 outputs and calling<br>
it a day - adding yet another address format has very significant<br>
ecosystem costs, and if we don&#39;t anticipate needing it for 5 years (if<=
br>
at all)...lets not jump to pay that cost.<br>
<br>
Matt<br>
<br>
On 11/10/19 9:51 PM, Pieter Wuille via bitcoin-dev wrote:<br>
&gt; On Thu, Nov 7, 2019, 18:16 David A. Harding &lt;<a href=3D"mailto:dave=
@dtrt.org" target=3D"_blank">dave@dtrt.org</a><br>
&gt; &lt;mailto:<a href=3D"mailto:dave@dtrt.org" target=3D"_blank">dave@dtr=
t.org</a>&gt;&gt; wrote:<br>
&gt; <br>
&gt;=C2=A0 =C2=A0 =C2=A0On Thu, Nov 07, 2019 at 02:35:42PM -0800, Pieter Wu=
ille via<br>
&gt;=C2=A0 =C2=A0 =C2=A0bitcoin-dev wrote:<br>
&gt;=C2=A0 =C2=A0 =C2=A0&gt; In the current draft, witness v1 outputs of le=
ngth other<br>
&gt;=C2=A0 =C2=A0 =C2=A0&gt; than 32 remain unencumbered, which means that =
for now such an<br>
&gt;=C2=A0 =C2=A0 =C2=A0&gt; insertion or erasure would result in an output=
 that can be spent by<br>
&gt;=C2=A0 =C2=A0 =C2=A0&gt; anyone. If that is considered unacceptable, it=
 could be prevented by<br>
&gt;=C2=A0 =C2=A0 =C2=A0&gt; for example outlawing v1 witness outputs of le=
ngth 31 and 33.<br>
&gt; <br>
&gt;=C2=A0 =C2=A0 =C2=A0Either a consensus rule or a standardness rule[1] w=
ould require anyone<br>
&gt;=C2=A0 =C2=A0 =C2=A0using a bech32 library supporting v1+ segwit to upg=
rade their library.<br>
&gt;=C2=A0 =C2=A0 =C2=A0Otherwise, users of old libraries will still attemp=
t to pay v1 witness<br>
&gt;=C2=A0 =C2=A0 =C2=A0outputs of length 31 or 33, causing their transacti=
ons to get rejected<br>
&gt;=C2=A0 =C2=A0 =C2=A0by newer nodes or get stuck on older nodes.=C2=A0 T=
his is basically the<br>
&gt;=C2=A0 =C2=A0 =C2=A0problem #15846[2] was meant to prevent.<br>
&gt; <br>
&gt;=C2=A0 =C2=A0 =C2=A0If we&#39;re going to need everyone to upgrade thei=
r bech32 libraries<br>
&gt;=C2=A0 =C2=A0 =C2=A0anyway, I think it&#39;s probably best that the pro=
blem is fixed in the<br>
&gt;=C2=A0 =C2=A0 =C2=A0bech32 algorithm rather than at the consensus/stand=
ardness layer.<br>
&gt; <br>
&gt; <br>
&gt; Admittedly, this affecting development of consensus or standardness<br=
>
&gt; rules would feel unnatural. In addition, it also=C2=A0has the potentia=
l<br>
&gt; downside of breaking batched transactions in some settings (ask an<br>
&gt; exchange for a withdrawal to a invalid/nonstandard version, which they=
<br>
&gt; batch with other outputs that then get stuck because the transaction<b=
r>
&gt; does not go through).<br>
&gt; <br>
&gt; So, Ideally this is indeed solved entirely on the bech32/address<br>
&gt; encoding side of things. I=C2=A0did not initially expect the discussio=
n here<br>
&gt; to go in that direction, as that could come with all problems that<br>
&gt; rolling out a new address scheme in the first place has. However, ther=
e<br>
&gt; may be a way to mostly avoid those problems for the time being, while<=
br>
&gt; also not having any impact on consensus or standardness rules.<br>
&gt; <br>
&gt; I believe that most new witness programs we&#39;d want to introduce an=
yway<br>
&gt; will be 32 bytes in the future, if the option exists. It&#39;s enough =
for a<br>
&gt; 256-bit hash (which has up to 128-bit collision security, and more tha=
n<br>
&gt; 128 bits is hard to achieve in Bitcoin anyway), or for X coordinates<b=
r>
&gt; directly. Either of those, plus a small version number to indicate the=
<br>
&gt; commitment structure should be enough to encode any spendability<br>
&gt; condition we&#39;d want with any achievable security level.<br>
&gt; <br>
&gt; With that observation, I propose the following. We amend BIP173 to be<=
br>
&gt; restricted to witness programs of length 20 or 32 (but still support<b=
r>
&gt; versions other than 0). This seems like it may be sufficient for sever=
al<br>
&gt; years, until version numbers run out. I believe that some wallet<br>
&gt; implementations already restrict sending to known versions only, which=
<br>
&gt; means effectively no change for them in addition to normal deployment.=
<br>
&gt; <br>
&gt; In the mean time we develop a variant of bech32 with better<br>
&gt; insertion/erasure detecting properties, which will be used for witness=
<br>
&gt; programs of length different from 20 or 32. If we make sure that there=
<br>
&gt; are never two distinct valid checksum algorithms for the same output, =
I<br>
&gt; don&#39;t believe there is any need for a new address scheme or a diff=
erent<br>
&gt; HRP. The latter is something I&#39;d strongly try to avoid anyway, as =
it<br>
&gt; would mean additional cognitive load on users because of another<br>
&gt; visually distinct address style, plus more logistical overhead<br>
&gt; (coordination and keeping track of 2 HRPs per chain).<br>
&gt; <br>
&gt; I believe improving bech32 itself is preferable over changing the way<=
br>
&gt; segwit addresses use bech32, as that can be done without making<br>
&gt; addresses even longer. Furthermore, the root of the issue is in bech32=
,<br>
&gt; and it is simplest to fix things there. The easiest solution is to<br>
&gt; simply change the constant 1 that is xor&#39;ed into the checksum befo=
re<br>
&gt; encoding it to a 30-bit number. This has the advantage that a single<b=
r>
&gt; checksum is never valid for both algoritgms simultaneously. Another<br=
>
&gt; approach is to implicitly including the length into the checksummed da=
ta.<br>
&gt; <br>
&gt; What do people think?<br>
&gt; <br>
&gt; Cheers,<br>
&gt; <br>
&gt; --=C2=A0<br>
&gt; Pieter<br>
&gt; <br>
&gt; <br>
&gt; _______________________________________________<br>
&gt; bitcoin-dev mailing list<br>
&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bl=
ank">bitcoin-dev@lists.linuxfoundation.org</a><br>
&gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-=
dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org=
/mailman/listinfo/bitcoin-dev</a><br>
&gt; <br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000fb834c05973185fc--