Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

[Pieter Wuille <bitcoin-dev@wuille.net>]

On Wednesday, October 7, 2020 5:21 PM, Rusty Russell via bitcoin-dev <bitcoin-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 point) a new checksum scheme, we don't just care about the new scheme's own error 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 + error being misinterpreted as a new-style address, as problems will only occur when entering a new address with errors in old software that supports the old scheme (which this thread shows, is not very common). Still, all other 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 = 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 substitution errors, and obtain an old-style address.
* If a new-style address ends with '7', inserting 'g78u' just before it will 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 switching 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 fixed characters (which, assuming uniformly random characters, implies a probability of 2^-30).

It seems M=0x3ffeffff has both these properties.

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

Cheers,

--
Pieter