Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses

From: Matt Corallo <lf-lists@mattcorallo•com>
To: Pieter Wuille <pieter.wuille@gmail•com>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>,
	"David A. Harding" <dave@dtrt•org>
Subject: Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses
Date: Mon, 11 Nov 2019 01:02:15 +0000	[thread overview]
Message-ID: <611b4e5b-e7cf-adc7-31e1-b5ff24b6574b@mattcorallo.com> (raw)
In-Reply-To: <CAPg+sBgus6HgYPVbXaAx51nO2ArsR3-6=obe2AwkO8kh11fB6Q@mail.gmail.com>

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
> 