Date: Wed, 28 Oct 2020 00:20:40 +0000
To: Rusty Russell <rusty@rustcorp.com.au>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: Pieter Wuille <bitcoin-dev@wuille.net>
Reply-To: Pieter Wuille <bitcoin-dev@wuille.net>
Message-ID: <p6i6YqXjOBastpss12gNUcJGGqomgPiLXOIyob71VptqVwJwcFwrd4m8Mad4RDnAhSyFXAZqsD67fW0kS3NayQ6k6dB-h2_V7vl7RBxmvvA=@wuille.net>
In-Reply-To: <87imblmutl.fsf@rustcorp.com.au>
References: <87imblmutl.fsf@rustcorp.com.au>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions
	(BIP-173)
Precedence: list

On Wednesday, October 7, 2020 5:21 PM, Rusty Russell via bitcoin-dev <bitco=
in-dev@lists.linuxfoundation.org> wrote:

> I propose an alternative to length restrictions suggested by
> Russell in https://github.com/bitcoin/bips/pull/945: use the
> https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb variant,
> unless the first byte is 0.

Hi all,

starting a slight side-thread here.

The discussion here made me realize that as we're introducing (at some poin=
t) a new checksum scheme, we don't just care about the new scheme's own err=
or detection capabilities, but also about the probability that a new style =
address + errors is incorrectly accepted as an old style address.


Clearly these properties are less of a priority than just the new-style + e=
rror being misinterpreted as a new-style address, as problems will only occ=
ur when entering a new address with errors in old software that supports th=
e old scheme (which this thread shows, is not very common). Still, all othe=
r things being equal, it can't hurt to see if some choices are better than =
others.

https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb suggested the=
 use of constant M =3D 0x3FFFFFFF. It turns out this is slightly suboptimal=
 in two ways:

* It's possible to take a new-style address with that constant, make 3 subs=
titution errors, and obtain an old-style address.
* If a new-style address ends with '7', inserting 'g78u' just before it wil=
l result in a valid old-style address (ignoring length constraints).

I don't think either of these is serious, but it's possible to improve upon=
 them:

* Guaranteeing that 4 substitution errors are always detected while switchi=
ng schemes seems impossible, but a constant can be picked that guarantees 3=
 errors always are.
* Insertion/deletion errors can be restricted to patterns that require 6 fi=
xed characters (which, assuming uniformly random characters, implies a prob=
ability of 2^-30).

It seems M=3D0x3ffeffff has both these properties.

I'm going to do some more analysis (swapping, and insertion/erasure near th=
e start), and then update my gist, but so far it seems this is a strictly (=
albeit only slightly) better choice.

Cheers,

--
Pieter