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

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

[Rusty Russell]

Hi all,

        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.

Here's a summary of each proposal:

Length restrictions (future segwits must be 10, 13, 16, 20, 23, 26, 29,
32, 36, or 40 bytes)
  1. Backwards compatible for v1 etc; old code it still works.
  2. Restricts future segwit versions, may require new encoding if we
     want a diff length (or waste chainspace if we need to have a padded
     version for compat).
    
Checksum change based on first byte:
  1. Backwards incompatible for v1 etc; only succeeds 1 in a billion.
  2. Weakens guarantees against typos in first two data-part letters to
     1 in a billion.[1]

I prefer the second because it forces upgrades, since it breaks so
clearly.  And unfortunately we do need to upgrade, because the length
extension bug means it's unwise to accept non-v0 addresses.

(Note non-v0 segwit didn't relay before v0.19.0 anyway, so many places
may already be restricting to v0 segwit).

The sooner a decision is reached on this, the sooner we can begin
upgrading software for a taproot world.

Thanks,
Rusty.
PS. Lightning uses bech32 over longer lengths, but the checksum is less critical; we'd prefer to follow whatever
bitcoin chooses.

[1] Technically less for non-v0: you have a 1 in 8 chance of a typo in the second letter changing the checksum
     algorithm, so it's 1 in 8 billion. 

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

[David A. Harding]

[-- Attachment #1: Type: text/plain, Size: 2148 bytes --]

On Thu, Oct 08, 2020 at 10:51:10AM +1030, Rusty Russell via bitcoin-dev wrote:
> Hi all,
> 
>         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.
> 
> Here's a summary of each proposal:
> 
> Length restrictions (future segwits must be 10, 13, 16, 20, 23, 26, 29,
> 32, 36, or 40 bytes)
>   1. Backwards compatible for v1 etc; old code it still works.
>   2. Restricts future segwit versions, may require new encoding if we
>      want a diff length (or waste chainspace if we need to have a padded
>      version for compat).
>     
> Checksum change based on first byte:
>   1. Backwards incompatible for v1 etc; only succeeds 1 in a billion.
>   2. Weakens guarantees against typos in first two data-part letters to
>      1 in a billion.[1]

Excellent summary!

> I prefer the second because it forces upgrades, since it breaks so
> clearly.  And unfortunately we do need to upgrade, because the length
> extension bug means it's unwise to accept non-v0 addresses.

I don't think the second option forces upgrades.  It just creates
another opt-in address format that means we'll spend another several
years with every wallet having two address buttons, one for a "segwit
address" (v0) and one for a "taproot address" (v1).  Or maybe three
buttons, with the third being a "taproot-in-a-segwit-address" (v1
witness program using the original bech32 encoding).

It took a lot of community effort to get widespread support for bech32
addresses.  Rather than go through that again, I'd prefer we use the
backwards compatible proposal from BIPs PR#945 and, if we want to
maximize safety, consensus restrict v1 witness program size, e.g. reject
transactions with scriptPubKeys paying v1 witness programs that aren't
exactly 32 bytes.

Hopefully by the time we want to use segwit v2, most software will have
implemented length limits and so we won't need any additional consensus
restrictions from then on forward.

-Dave

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 780 bytes --]

On Thu, Oct 8, 2020 at 11:00 AM David A. Harding via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Rather than go through that again, I'd prefer we use the
> backwards compatible proposal from BIPs PR#945 and, if we want to
> maximize safety, consensus restrict v1 witness program size, e.g. reject
> transactions with scriptPubKeys paying v1 witness programs that aren't
> exactly 32 bytes.
>

Adding some kind of relay policy rule would be easier than a consensus
rule, and maybe effective enough.  (This comment is not intended to endorse
any one proposal over another.)


> Hopefully by the time we want to use segwit v2, most software will have
> implemented length limits and so we won't need any additional consensus
> restrictions from then on forward.
>

[-- Attachment #2: Type: text/html, Size: 1284 bytes --]

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

[Rusty Russell]

"David A. Harding" <dave@dtrt.org> writes:
> On Thu, Oct 08, 2020 at 10:51:10AM +1030, Rusty Russell via bitcoin-dev wrote:
>> Hi all,
>> 
>>         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.
>> 
>> Here's a summary of each proposal:
>> 
>> Length restrictions (future segwits must be 10, 13, 16, 20, 23, 26, 29,
>> 32, 36, or 40 bytes)
>>   1. Backwards compatible for v1 etc; old code it still works.
>>   2. Restricts future segwit versions, may require new encoding if we
>>      want a diff length (or waste chainspace if we need to have a padded
>>      version for compat).
>>     
>> Checksum change based on first byte:
>>   1. Backwards incompatible for v1 etc; only succeeds 1 in a billion.
>>   2. Weakens guarantees against typos in first two data-part letters to
>>      1 in a billion.[1]
>
> Excellent summary!
>
>> I prefer the second because it forces upgrades, since it breaks so
>> clearly.  And unfortunately we do need to upgrade, because the length
>> extension bug means it's unwise to accept non-v0 addresses.
>
> I don't think the second option forces upgrades.  It just creates
> another opt-in address format that means we'll spend another several
> years with every wallet having two address buttons, one for a "segwit
> address" (v0) and one for a "taproot address" (v1).  Or maybe three
> buttons, with the third being a "taproot-in-a-segwit-address" (v1
> witness program using the original bech32 encoding).

If we go for option 2, v1 (generated from bitcoin core) will simply fail
the first time you try test it.  So it will force an upgrade.  There
are fewer places generating addresses than accepting them, so this
seems the most likely scenario.

OTOH, with option 1, anyone accepting v1 addresses today is going to
become a liability once v1 addresses start being generated.

> It took a lot of community effort to get widespread support for bech32
> addresses.  Rather than go through that again, I'd prefer we use the
> backwards compatible proposal from BIPs PR#945 and, if we want to
> maximize safety, consensus restrict v1 witness program size, e.g. reject
> transactions with scriptPubKeys paying v1 witness programs that aren't
> exactly 32 bytes.

Yes, I too wish we weren't here.  :(

Deferring a hard decision is not useful unless we expect things to be
easier in future, and I only see it getting harder as time passes and
userbases grow.

The good news it that the change is fairly simple and the reference
implementations are widely used so change is not actually that hard
once the decision is made.

> Hopefully by the time we want to use segwit v2, most software will have
> implemented length limits and so we won't need any additional consensus
> restrictions from then on forward.

If we are prepared to commit to restrictions on future addresses.

We don't know enough to do that, however, so I'm reluctant; I worry that
a future scheme where we could save (e.g.) 2 bytes will impractical due
to our encoding restrictions, resulting in unnecessary onchain bloat.

Cheers,
Rusty.

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

[Pieter Wuille]

Hi Rusty,

thanks for starting this thread. We definitely should make a decision around
this soon.


On Wednesday, October 14, 2020 6:40 PM, Rusty Russell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > > Here's a summary of each proposal:
> > > Length restrictions (future segwits must be 10, 13, 16, 20, 23, 26, 29,
> > > 32, 36, or 40 bytes)
> > >
> > > 1.  Backwards compatible for v1 etc; old code it still works.
> > > 2.  Restricts future segwit versions, may require new encoding if we
> > >     want a diff length (or waste chainspace if we need to have a padded
> > >     version for compat).
> > >
> > > Checksum change based on first byte:
> > >
> > > 1.  Backwards incompatible for v1 etc; only succeeds 1 in a billion.
> > > 2.  Weakens guarantees against typos in first two data-part letters to
> > >     1 in a billion.[1]
> > >

> If we go for option 2, v1 (generated from bitcoin core) will simply fail
> the first time you try test it. So it will force an upgrade. There
> are fewer places generating addresses than accepting them, so this
> seems the most likely scenario.
>
> OTOH, with option 1, anyone accepting v1 addresses today is going to
> become a liability once v1 addresses start being generated.

Today, no witness v1 receivers exist. So it seems to me the only question
is what software/infrastructure exist that supports sending to witness v1,
and whether they (and their userbase) are more or less likely to upgrade
before receivers appear than those that don't.

Clearly if only actively developed software currently supports sending to
v1 right now, then the question of forward compatibility is moot, and I'd
agree the cleanliness of option 2 is preferable.

Does anyone have an up-to-date overview of where to-future-witness sending
is supported? I know Bitcoin Core does.

> > It took a lot of community effort to get widespread support for bech32
> > addresses. Rather than go through that again, I'd prefer we use the
> > backwards compatible proposal from BIPs PR#945 and, if we want to
> > maximize safety, consensus restrict v1 witness program size, e.g. reject
> > transactions with scriptPubKeys paying v1 witness programs that aren't
> > exactly 32 bytes.
>
> Yes, I too wish we weren't here. :(
>
> Deferring a hard decision is not useful unless we expect things to be
> easier in future, and I only see it getting harder as time passes and
> userbases grow.

Possibly, but in the past I think there has existed a pattern where adoption
of new technology is at least partially based on certain infrastructure
and codebases going out of business and/or being replaced with newer ones,
rather than improvements to existing ones.

If that effect is significant, option 1 may be preferable: it means less
compatibility issues in the short term, and longer term all that may be
required is fixing the spec, and waiting long enough for old/unmaintained code
to be replaced.

As for how long: new witness version/length combinations are only rarely needed,
and there are 14 length=32 ones left to pick. We'll likely want to use those
first anyway, as it's the cheapest option with 128-bit collision resistance.
Assuming future constructions have something like BIP341's leaf versioning, new
witness version/length combinations are only required for:

* Changes to the commitment structure of script execution (e.g. Graftroot,
  different hash function for Merkle trees, ...)
* Upgrades to new signing cryptography (EC curve change, PQC, ...).
* Changes to signatures outside of a commitment structure (e.g. new sighash
  modes for the keypath in BIP341, or cross-input aggregation for them).

and in general, not for things like new script opcodes, or even for fairly
invasive redesigns of the script language itself.

> The good news it that the change is fairly simple and the reference
> implementations are widely used so change is not actually that hard
> once the decision is made.

Indeed. Whatever observations we had about adoption of base58 -> bech32 may not
apply because the change to a different checksum is fairly trivial compared to
that. Still, presence of production codebases that just don't update at all
may complicate this.

> > Hopefully by the time we want to use segwit v2, most software will have
> > implemented length limits and so we won't need any additional consensus
> > restrictions from then on forward.
>
> If we are prepared to commit to restrictions on future addresses.
>
> We don't know enough to do that, however, so I'm reluctant; I worry that
> a future scheme where we could save (e.g.) 2 bytes will impractical due
> to our encoding restrictions, resulting in unnecessary onchain bloat.

I'm opposed to consensus-invalidating certain length/version combinations, if
that's what you're suggesting, and I don't think there is a need for it.

TL;DR: what codebases/services/infrastructure exists today that supports
sending to witness v1 BIP173 addresses?

Cheers,

--
Pieter

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

[Rusty Russell]

Pieter Wuille <bitcoin-dev@wuille.net> writes:
> Today, no witness v1 receivers exist. So it seems to me the only question
> is what software/infrastructure exist that supports sending to witness v1,
> and whether they (and their userbase) are more or less likely to upgrade
> before receivers appear than those that don't.
>
> Clearly if only actively developed software currently supports sending to
> v1 right now, then the question of forward compatibility is moot, and I'd
> agree the cleanliness of option 2 is preferable.

If software supports v1 today and doesn't get upgraded, and we persue
option 1 then a trailing typo can make trouble.  Not directly lose money
(since the tx won't get propagated), but for most systems (e.g. hosted
wallets) someone has to go in and figure out the error and fix it up.

Option 2 means they're likely to fix their systems the first time
someone tries a v1 send, not the first time someone makes a trailing
typo (which might be years).

> Does anyone have an up-to-date overview of where to-future-witness sending
> is supported? I know Bitcoin Core does.

Anecdata: c-lightning doesn't allow withdraw to segwit > 0.  It seems
that the contributor John Barboza (CC'd) assumed that future versions
should be invalid:

	if (bip173) {
		bool witness_ok = false;
		if (witness_version == 0 && (witness_program_len == 20 ||
					     witness_program_len == 32)) {
			witness_ok = true;
		}
		/* Insert other witness versions here. */

>> Deferring a hard decision is not useful unless we expect things to be
>> easier in future, and I only see it getting harder as time passes and
>> userbases grow.
>
> Possibly, but in the past I think there has existed a pattern where adoption
> of new technology is at least partially based on certain infrastructure
> and codebases going out of business and/or being replaced with newer ones,
> rather than improvements to existing ones.
>
> If that effect is significant, option 1 may be preferable: it means less
> compatibility issues in the short term, and longer term all that may be
> required is fixing the spec, and waiting long enough for old/unmaintained code
> to be replaced.

Hmm, I'd rather cleanly break zombie infra, since they're exactly the
kind that won't/cant fix the case where someone trailing-typos?

> As for how long: new witness version/length combinations are only rarely needed,
> and there are 14 length=32 ones left to pick. We'll likely want to use those
> first anyway, as it's the cheapest option with 128-bit collision resistance.
> Assuming future constructions have something like BIP341's leaf versioning, new
> witness version/length combinations are only required for:
>
> * Changes to the commitment structure of script execution (e.g. Graftroot,
>   different hash function for Merkle trees, ...)
> * Upgrades to new signing cryptography (EC curve change, PQC, ...).
> * Changes to signatures outside of a commitment structure (e.g. new sighash
>   modes for the keypath in BIP341, or cross-input aggregation for them).
>
> and in general, not for things like new script opcodes, or even for fairly
> invasive redesigns of the script language itself.

Hmm, good point.  These can all be done with version bumps.

The only use for extra bytes I can see is per-UTXO flags, but even then
I can't see why you'd need to know them until their spent (in which case
you stash the flag in the input, not the output).

And fewer bytes seems bad for fungibility, since multisig would be
dangerous.

But the future keeps surprising me, so I'm still hesitant.

>> The good news it that the change is fairly simple and the reference
>> implementations are widely used so change is not actually that hard
>> once the decision is made.
>
> Indeed. Whatever observations we had about adoption of base58 -> bech32 may not
> apply because the change to a different checksum is fairly trivial compared to
> that. Still, presence of production codebases that just don't update at all
> may complicate this.
>
>> > Hopefully by the time we want to use segwit v2, most software will have
>> > implemented length limits and so we won't need any additional consensus
>> > restrictions from then on forward.
>>
>> If we are prepared to commit to restrictions on future addresses.
>>
>> We don't know enough to do that, however, so I'm reluctant; I worry that
>> a future scheme where we could save (e.g.) 2 bytes will impractical due
>> to our encoding restrictions, resulting in unnecessary onchain bloat.
>
> I'm opposed to consensus-invalidating certain length/version combinations, if
> that's what you're suggesting, and I don't think there is a need for it.

This *seems* to leave the option of later removing size restrictions,
but I think this is an illusion.  Upgrading will only get harder over
time: we would instead opt for some kind of backward compatiblity hack
(i.e. 33 byte address, but you can optionally add 3 zero pad bytes)
which *will* have consensus effect.

> TL;DR: what codebases/services/infrastructure exists today that supports
> sending to witness v1 BIP173 addresses?

OK, time to waste some money!

Can you provide a mainnet v1 address, and I'll try to spam it from as
many things as I can find.  If we're really lucky, you can collect it
post-fork and donate it to charity.  Or a miner can steal it pre-fork :)

Thanks!
Rusty.

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

[Pieter Wuille]

On Sunday, October 18, 2020 5:49 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:

> Pieter Wuille bitcoin-dev@wuille.net writes:
>
> > Today, no witness v1 receivers exist. So it seems to me the only question
> > is what software/infrastructure exist that supports sending to witness v1,
> > and whether they (and their userbase) are more or less likely to upgrade
> > before receivers appear than those that don't.
> > Clearly if only actively developed software currently supports sending to
> > v1 right now, then the question of forward compatibility is moot, and I'd
> > agree the cleanliness of option 2 is preferable.
>
> If software supports v1 today and doesn't get upgraded, and we persue
> option 1 then a trailing typo can make trouble. Not directly lose money
> (since the tx won't get propagated), but for most systems (e.g. hosted
> wallets) someone has to go in and figure out the error and fix it up.

It depends. As is, they'd be relayed even as sending to future witness versions
or lengths is standard. If option 1 is chosen there may be reasons to add
safeguards using relay policy, though.

> Option 2 means they're likely to fix their systems the first time
> someone tries a v1 send, not the first time someone makes a trailing
> typo (which might be years).

Possibly, but it's also possible that it won't get fixed at all, and instead
receiver software just has to wait a few years longer before being able to start
giving out v1 addresses and have a reasonable chance the sender supports it.

You're right though that protecting old sender software from being protected
against the insertion bug is a good argument in favor of Option 2.

Strictly speaking it also has an issue, as the error detection properties aren't
guaranteed for new-scheme-address + intended-detected-error interpreted as
old-scheme-address (in particular, you can make 4 substitution errors in
a new-scheme address and have it be a valid old-scheme address). This is much
less of an issue than the insertion bug that remains present with Option 1 in
old senders.

> > As for how long: new witness version/length combinations are only rarely needed,
> > and there are 14 length=32 ones left to pick. We'll likely want to use those
> > first anyway, as it's the cheapest option with 128-bit collision resistance.
> > Assuming future constructions have something like BIP341's leaf versioning, new
> > witness version/length combinations are only required for:
> >
> > -   Changes to the commitment structure of script execution (e.g. Graftroot,
> >     different hash function for Merkle trees, ...)
> >
> > -   Upgrades to new signing cryptography (EC curve change, PQC, ...).
> > -   Changes to signatures outside of a commitment structure (e.g. new sighash
> >     modes for the keypath in BIP341, or cross-input aggregation for them).
> >
> >
> > and in general, not for things like new script opcodes, or even for fairly
> > invasive redesigns of the script language itself.
>
> Hmm, good point. These can all be done with version bumps.
>
> The only use for extra bytes I can see is per-UTXO flags, but even then
> I can't see why you'd need to know them until their spent (in which case
> you stash the flag in the input, not the output).
>
> And fewer bytes seems bad for fungibility, since multisig would be
> dangerous.
>
> But the future keeps surprising me, so I'm still hesitant.

Of course, our thinking here may change significantly over time - still, I expect
it'll be years before something other than 32-byte addresses is desired.

> > TL;DR: what codebases/services/infrastructure exists today that supports
> > sending to witness v1 BIP173 addresses?
>
> OK, time to waste some money!
>
> Can you provide a mainnet v1 address, and I'll try to spam it from as
> many things as I can find. If we're really lucky, you can collect it
> post-fork and donate it to charity. Or a miner can steal it pre-fork :)

Here is a BIP341 witness v1 address, corresponding to just the generator as
inner public key (using TapTweak(pubkey) as tweak, as suggested by the BIP):

bc1pmfr3p9 YOU j00pfxjh WILL 0zmgp99y8zf LOSE tmd3s5pmedqhy MONEY ptwy6lm87hf5ss52r5n8


Cheers,

--
Pieter

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

[Rusty Russell]

Pieter Wuille <bitcoin-dev@wuille.net> writes:
> Here is a BIP341 witness v1 address, corresponding to just the generator as
> inner public key (using TapTweak(pubkey) as tweak, as suggested by the BIP):
>
> bc1pmfr3p9 YOU j00pfxjh WILL 0zmgp99y8zf LOSE tmd3s5pmedqhy MONEY ptwy6lm87hf5ss52r5n8

Here are my initial results:

Rejects
-------

c-lightning: "Could not parse destination address, destination should be a valid address"
Phoenix: "Invalid data.  Please try again."

Accepts
-------
Green: ef1662fd2eb736612afb1b60e3efabfdf700b1c4822733d9dbe1bfee607a5b9b
blockchain.info: 64b0fcb22d57b3c920fee1a97b9facec5b128d9c895a49c7d321292fb4156c21

Will keep exploring (and others are welcome to try too!)

Cheers,
Rusty.

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

[Rusty Russell]

Rusty Russell <rusty@rustcorp.com.au> writes:
> Accepts
> -------
> Green: ef1662fd2eb736612afb1b60e3efabfdf700b1c4822733d9dbe1bfee607a5b9b
> blockchain.info: 64b0fcb22d57b3c920fee1a97b9facec5b128d9c895a49c7d321292fb4156c21

PEBKAC.  Pasted wrong address.  Here are correct results:

Rejects
-------
c-lightning: "Could not parse destination address, destination should be a valid address"
Phoenix: "Invalid data.  Please try again."
blockchain.info: "Your Bitcoin transaction failed to send. Please try again."

Accepts
-------
Green: 9e4ab6617a2983439181a304f0b4647b63f51af08fdd84b0676221beb71a8f21

Cheers,
Rusty.

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

[Riccardo Casatta]

[-- Attachment #1: Type: text/plain, Size: 1299 bytes --]

Here is a mainnet tx done with aqua wallet, which is based on rust-bitcoin
https://blockstream.info/tx/b48a59fa9e036e997ba733904f631b1a64f5274be646698e49fd542141ca9404?expand

I am not sure about the scriptpubkey starting with 51 so I opened this
https://github.com/rust-bitcoin/rust-bitcoin/pull/504


Il giorno mar 20 ott 2020 alle ore 05:32 Rusty Russell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> ha scritto:
>
> Rusty Russell <rusty@rustcorp.com.au> writes:
> > Accepts
> > -------
> > Green: ef1662fd2eb736612afb1b60e3efabfdf700b1c4822733d9dbe1bfee607a5b9b
> > blockchain.info:
64b0fcb22d57b3c920fee1a97b9facec5b128d9c895a49c7d321292fb4156c21
>
> PEBKAC.  Pasted wrong address.  Here are correct results:
>
> Rejects
> -------
> c-lightning: "Could not parse destination address, destination should be
a valid address"
> Phoenix: "Invalid data.  Please try again."
> blockchain.info: "Your Bitcoin transaction failed to send. Please try
again."
>
> Accepts
> -------
> Green: 9e4ab6617a2983439181a304f0b4647b63f51af08fdd84b0676221beb71a8f21
>
> Cheers,
> Rusty.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev



--
Riccardo Casatta - @RCasatta

[-- Attachment #2: Type: text/html, Size: 2054 bytes --]

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

[David A. Harding]

[-- Attachment #1: Type: text/plain, Size: 2520 bytes --]

On Tue, Oct 20, 2020 at 11:12:06AM +1030, Rusty Russell wrote:
> Here are my initial results:

A while ago, around the Bitcoin Core 0.19.0 release that enabled
relaying v1+ segwit addresses, Mike Schmidt was working on the Optech
Compatibility Matrix[1] and tested a variety of software and services
with a v1 address using the original BIP341 specification (33 byte
pubkeys; we now use 32 byte keys).  Here's a summary of his results,
posted with his permission:

- abra: Bech32 not supported.

- binance: Does not pass front end javascript validation

- bitgo: Error occurs during sending process, after validation.

- bitmex: Bech32 not supported.

- bitrefill: Address does not pass validation.

- bitstamp: Address text input doesn’t allow bech32 addresses due to
  character limits.

- blockchain.info: Error occurs during sending process, after
  validation.

- brd: Allows sending workflow to complete in the UI. Transaction stays
  as pending in the transaction list.

- casa: Fails on signing attempt.

- coinbase: Fails address validation client side in the UI.

- conio: Server error 500 while attemping to send.

- copay: Allows v1 address to be entered in the UI. Fails during
  broadcast.

- edge: Allows sending workflow to complete. Transaction stays in
  pending state. Appears to causes issues with the balance calculation
  as well as ability to send subsequent transactions.

- electrum: Error message during broadcasting of transaction.

- green: Fails on validation of the address.

- jaxx: Fails on validation of the address.

- ledger live: Fails when transaction is sent to the hardwave device for
  signing.

- mycelium: Fails during address validation.

- purse: Transaction can be created and broadcast, relayed by peers
  compatible with Bitcoin Core v0.19.0.1 or above.

- river: Transaction can be created and broadcast, relayed by peers
  compatible with Bitcoin Core v0.19.0.1 or above.

- samourai: Fails on broadcast of transaction to the network.

- trezor: Fails on validation of the address.

- wasabi: Fails on validation of the address.

- xapo: Xapo allows users to create segwit v1 transactions in the UI.
  However, the transaction gets stuck as pending for an indeterminate
  period of time

I would guess that some of the failures / stuck transactions might now
be successes if the backend infrastructure has upgraded to Bitcoin Core
>= 0.19.

-Dave

[1] https://bitcoinops.org/en/compatibility/

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Pieter Wuille]

On Tuesday, October 20, 2020 3:29 AM, David A. Harding <dave@dtrt.org> wrote:


> I would guess that some of the failures / stuck transactions might now be successes if the backend infrastructure has upgraded to Bitcoin Core > = 0.19.

Yeah, it would be good to re-test them since a ~year has passed since the 0.19.0 release.

Cheers,

--
Pieter

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

[Mike Schmidt]

[-- Attachment #1: Type: text/plain, Size: 860 bytes --]

I am happy to re-test the services Harding listed previously for v1 send
support next week.

Suggestions of additional services that would be valuable to test are
welcome as well.

Mike


On Tue, Oct 20, 2020 at 3:38 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Tuesday, October 20, 2020 3:29 AM, David A. Harding <dave@dtrt.org>
> wrote:
>
>
> > I would guess that some of the failures / stuck transactions might now
> be successes if the backend infrastructure has upgraded to Bitcoin Core > =
> 0.19.
>
> Yeah, it would be good to re-test them since a ~year has passed since the
> 0.19.0 release.
>
> Cheers,
>
> --
> Pieter
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 1671 bytes --]

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

[Rusty Russell]

Mike Schmidt via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
writes:
> I am happy to re-test the services Harding listed previously for v1 send
> support next week.
>
> Suggestions of additional services that would be valuable to test are
> welcome as well.

Thanks!  I am a little disappointed that I won't get to ask Bitcoin
Twitter to send tips to Pieter[1] though...

I would like to hear from the services who currently support v1+ (who
thus *would* have to change their software) whether they have a
technical preference for option 1 or 2.

Cheers,
Rusty.
[1] Or just maybe, tips to some random miner...

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

[Mike Schmidt]

[-- Attachment #1: Type: text/plain, Size: 1755 bytes --]

Well I sure picked a bad couple weeks to volunteer to send a bunch of
Bitcoin test transactions...

While I tested less than I would have liked, there are some notable results:

- Green wallet segwit v1 send resulted in funds being sent to the wrong
address (bc1qmfr3p9j00pfxjh0zmgp99y8zftmd3s5pmedqhyptwy6lm87hf5sstpn3we
instead of my intended destination, Pieter's r5n8 address. You can see this
with Rusty's test transaction as well:
ef1662fd2eb736612afb1b60e3efabfdf700b1c4822733d9dbe1bfee607a5b9b
Blockstream is aware of the issue and has fixes.
- Blockchain.com's wallet behaved similarly, sending to the same, incorrect
address. Rusty's blockchain.com transaction for reference:
64b0fcb22d57b3c920fee1a97b9facec5b128d9c895a49c7d321292fb4156c21
I will be reaching out to Blockchain's team to let them know about this.
- Blockchain.info's explorer suffers similarly, "Unable to decode output
address" when viewing a tx with v1 output, and inability to display address
details for a v1 address
- Bitgo accepts a v1 send address, but then a “Server error” during send
occurs
- Coinbase (web) reported on final step of sending: Your send failed Please
enter a valid email or Bitcoin address
- brd sends successfully to v1
- bitrefill, casa, xapo, wasabi, all previously failed address validation,
and still fail address validation
- binance, bitmex, kraken, all previously failed address validation, but
now accept v1 addresses. I did not attempt full send with these services,
simply passing initial validations.
- While Riccardo noted that Aqua successfully sent to Pieter's address
(b48a59fa9e036e997ba733904f631b1a64f5274be646698e49fd542141ca9404) Ive been
informed Aqua has disabled send to v1 addresses for now.

[-- Attachment #2: Type: text/html, Size: 2115 bytes --]

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

[Pieter Wuille]

[-- Attachment #1: Type: text/plain, Size: 1112 bytes --]

On Friday, November 6, 2020 11:49 AM, Mike Schmidt via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> Well I sure picked a bad couple weeks to volunteer to send a bunch of Bitcoin test transactions...
>
> While I tested less than I would have liked, there are some notable results:

I think these results really show there is no reason to try to maintain the old-software-can-send-to-future-segwit-versions property, given that more than one not just didn't support it, but actually sent coins into a black hole.

Thus, I agree with Rusty that we should change the checksum for v1+ unconditionally. That also means that old senders are protected from the insertion issue (by failing, as we can guarantee that new-checksum addresses, even after a few errors, are invalid to old software).

I've sent another mail in this thread with details, but the TL;DR is that we should use the constant M=0x2bc830a3 rather than 0x3fffffff as previous suggested. More information on https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e.

Absent objections, I'll write up a BIP soon.

Cheers,

--
Pieter

[-- Attachment #2: Type: text/html, Size: 1605 bytes --]

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

[David A. Harding]

[-- Attachment #1: Type: text/plain, Size: 1427 bytes --]

On Sat, Dec 05, 2020 at 11:10:51PM +0000, Pieter Wuille via bitcoin-dev wrote:
> I think these results really show there is no reason to try to
> maintain the old-software-can-send-to-future-segwit-versions property,
> given that more than one not just didn't support it, but actually sent
> coins into a black hole.

I don't think this is a good criteria to use for making a decision.  We
shouldn't deny users of working implementations the benefit of a feature
because some other developers didn't implement it correctly.

> Thus, I agree with Rusty that we should change the checksum for v1+
> unconditionally. 

I disagreed with Rusty previously and he proposed we check to see how
disruptive an address format change would be by seeing how many wallets
already provide forward compatibility and how many would need to be
updated for taproot no matter what address format is used.  I think that
instead is a good criteria for making a decision.

I understand the results of that survey to be that only two wallets
correctly handled v1+ BIP173 addresses.  One of those wallets is Bitcoin
Core, which I personally believe will unhesitatingly update to a new
address format that's technically sound and which has widespread support
(doubly so if it's just a tweak to an already-implemented checksum
algorithm).

Given that, I also now agree with changing the checksum for v1+.

Thanks,

-Dave


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Pieter Wuille]

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Sunday, December 6, 2020 5:04 AM, David A. Harding <dave@dtrt.org> wrote:

> On Sat, Dec 05, 2020 at 11:10:51PM +0000, Pieter Wuille via bitcoin-dev wrote:
>
> > I think these results really show there is no reason to try to
> > maintain the old-software-can-send-to-future-segwit-versions property,
> > given that more than one not just didn't support it, but actually sent
> > coins into a black hole.
>
> I don't think this is a good criteria to use for making a decision. We
> shouldn't deny users of working implementations the benefit of a feature
> because some other developers didn't implement it correctly.
>
> > Thus, I agree with Rusty that we should change the checksum for v1+
> > unconditionally.
>
> I disagreed with Rusty previously and he proposed we check to see how
> disruptive an address format change would be by seeing how many wallets
> already provide forward compatibility and how many would need to be
> updated for taproot no matter what address format is used. I think that
> instead is a good criteria for making a decision.
>
> I understand the results of that survey to be that only two wallets
> correctly handled v1+ BIP173 addresses. One of those wallets is Bitcoin
> Core, which I personally believe will unhesitatingly update to a new
> address format that's technically sound and which has widespread support
> (doubly so if it's just a tweak to an already-implemented checksum
> algorithm).

Hi Dave,

You're right to point out there is nuance I skipped over.

Let's look at the behavior of different classes of software/services that exist today when trying to send to v1+ addresses:

(A) Supports sending to v1+ today
  * Old proposal: works, but subject to bech32 insertion issue
  * New proposal: fails
(B) Fails to send to v1+ today
  * Old proposal: fails
  * New proposal: fails
(C) Incorrectly sends to v1+ today
  * Old proposal: lost funds
  * New proposal: fails

So the question is how the support for sending to v1+ in (a) software weighs up against protecting both (a) from the insertion issue, and (c) from lost funds. I do think (c) matters in this equation - people may choose to avoid adopting v1+ witnesses if it were to be known that some senders out there would misdirect funds. But the fact that (a) is small also means there is very little to gain from the old proposal.

So perhaps I should have formulated it as: the small number of v1+ compatible senders today (regardless of the reasons for that) shows how futile the attempt to have one address type for all witness versions was, and the fact that there are even some who misdirect(ed) funds is the final nail in the coffin. Changing the checksum unconditionally gives us a new attempt at that.

> Given that, I also now agree with changing the checksum for v1+.

Great.

Cheers,

--
Pieter

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

[Ryan Grant]

It looks like a good strategy for a bech32 library that is external to
Bitcoin Core would be:

  - Default to the new M, under the same bech32 brand.

  - Provide an interface to explicitly use both M=1 and M=0x2bc830a3.

  - If decoding fails, throw an error; but in constructing that error
    inform whether the other M would have succeeded.

  - Provide an interface for a BIP173 implementation to peek at the
    witness version byte of the data part, which may also involve
    sanity-checking that byte for errors using a BIP173-specific
    understanding of the appropriate checksum.

    Return values for this special interface might currently be:
      "it's version zero, based on a clean decoding",
      "it's version one,  based on a clean decoding",
      "it's version zero, based on an auto-corrected byte",
      "it's version one,  based on an auto-corrected byte",
      "no result, due to a decoding error on this byte", and
      "too many errors to say anything more about decoding".

Although the reasoning is clear for doing so, looking into the data
that is supposed to be checksummed to determine which checksum to use
is not very elegant.  There are two trips into a bech32 library for a
BIP173 decoding, and an indeterminate result on the version byte would
require heuristics for deciding what to do with the rest of the data
part to even advise the user on the error.  Because of this, as a
library writer I would be tempted to auto-correct the witness version
byte (against the "SHOULD NOT" advice of BIP173's current version), if
it were the only one corrupted, as per the example return values
above.  Please advise.

Some of the libraries that will be contemplating these steps include:
  https://github.com/topics/bech32?o=desc&s=stars

Here are three existing uses of bech32 that are external to Bitcoin Core:

  https://github.com/lightningnetwork/lightning-rfc/blob/master/11-payment-encoding.md
  https://github.com/btcontract/lnurl-rfc
  https://github.com/bitcoin/bips/blob/master/bip-0136.mediawiki

Of the above, I think BIP136 can be unconditionally moved to
M=0x2bc830a3 due to having little legacy burden.

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

[Pieter Wuille]

On Tuesday, December 8, 2020 9:39 AM, Ryan Grant <bitcoin-dev@rgrant.org> wrote:

> It looks like a good strategy for a bech32 library that is external to
> Bitcoin Core would be:
>
> -   Default to the new M, under the same bech32 brand.
> -   Provide an interface to explicitly use both M=1 and M=0x2bc830a3.
> -   If decoding fails, throw an error; but in constructing that error
>     inform whether the other M would have succeeded.
>
> -   Provide an interface for a BIP173 implementation to peek at the
>     witness version byte of the data part, which may also involve
>     sanity-checking that byte for errors using a BIP173-specific
>     understanding of the appropriate checksum.

I think there are two possible interfaces that make sense:

- Have the caller explicitly specify whether they want bech32 or bech32m (which someone - I think Rusty? - started using in reference to this new code and I'm going to adopt now).

- Have the bech32 decoding function return a tristate (failed, valid as bech32, valid as bech32m). No string is ever valid as both, so there is no loss of information here.

The former is a bit cleaner, and also the only real choice if error location hinting is desired. The second is more efficient if decoding twice is a performance concern.

Cheers,

--
Pieter

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

[ZmnSCPxj]

> Anecdata: c-lightning doesn't allow withdraw to segwit > 0. It seems
> that the contributor John Barboza (CC'd) assumed that future versions
> should be invalid:
>
> if (bip173) {
> bool witness_ok = false;
> if (witness_version == 0 && (witness_program_len == 20 ||
> witness_program_len == 32)) {
> witness_ok = true;
> }
> /* Insert other witness versions here. */

I believe this is actually my code, which was later refactored by John Barboza when we were standardizing the `param` system.

This was intended only as a simple precaution against creating non-standard transaction, and not an assumption that future versions should be invalid.
The intent is that further `else if` branches would be added for newer witness versions and whatever length restrictions they may have, as the `/* Insert other witness versions here.  */` comment implies.

Regards,
ZmnSCPxj

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

[Rusty Russell]

ZmnSCPxj <ZmnSCPxj@protonmail.com> writes:
> I believe this is actually my code, which was later refactored by John Barboza when we were standardizing the `param` system.

Ah, sorry!

> This was intended only as a simple precaution against creating non-standard transaction, and not an assumption that future versions should be invalid.
> The intent is that further `else if` branches would be added for newer witness versions and whatever length restrictions they may have, as the `/* Insert other witness versions here.  */` comment implies.

Yes, I mentioned it here because I've found this to be a common
misconception; the *idea* was that application's segwit code would not
have to be reworked for future upgrades, but that information propagated
poorly.

(Just as well, because of overly strict standardness rules, the overflow
bug, and now the proposed validation changes, turns out this lack of
forward compat is a feature!)

Thanks!
Rusty.

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

[Pieter Wuille]

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

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

[Pieter Wuille]

> 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.

Another update, and a longer write-up.


Introduction
------------

Bech32's checksum algorithm was designed to be strong against substitution
errors, but it also provides some protection against more general classes of
errors. The final constant M that is XOR'ed into the checksum influences that
protection. BIP173 today uses M=1, but it is now known that this has a
weakness: if the final character is a "p", any number of "q" characters can be
inserted or erased right before it, without invalidating the checksum.

As it was recognized that other constants do not have this issue, the obvious
question is whether this is the only possible type of weakness, and if not, if
there is an optimal constant to use that minimizes the largest number of
weaknesses.

Since my last mail I've realized that it is actually possible to analyse the
behavior of these final constants under a wide variety of error classes
(substitutions, deletions, insertions, swaps, duplications) programatically.
Greg Maxwell and I have used this to perform an exhaustive analysis of certain
error patterns for all 2^30 possible M values, selected a number of criteria
to optimize for, and conclude that we should use as constant:

  M = 0x2bc830a3

The code used to do this analysis, as well as the code used to verify some
expected properties of the final result, and more, can be found on
https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e

See results_final.txt to see how this constant compares with the previously
suggested constants 1, 0x3fffffff, and 0x3fefffff.

Properties
----------

If we define an error as a deletion of one position, a swap of adjacent
positions, a substitution in a specific position with a random character, an
insertion of one random character in a specific position, or a duplication of
the character in a specific position, then this M constant above gives us the
following properties:

* For generic HRPs and errors that don't affect the first 6 data characters,
  or alternatively averaged over all HRPs (see details futher):
  * Always detected:
    * (P) Up to 4 substitution errors (true for any constant).
    * (Q) Any valid code with the new constant, fed without modification to
          software that uses the old constant 1 (true for any constant).
  * Any error pattern has failure to detect probability <= 2^-30:
    * (L) Any number of errors restricted to a single window of up to 4
          characters.
    * (B) Up to two errors restricted to a window of up to 68 characters.
    * (D) Any one error made to a valid code with the new constant, and fed to
          software that uses the old constant 1
  * Most error patterns have probability <= 2^-30:
    * (C) Up to two errors in general: out of 23926796 such error patterns,
          0.0040% have probability 2^-25.
    * (N) Up to three errors restricted to a window of up to 69 characters:
          out of 284708444 such patterns, 0.033% have probability 2^-25.
    * (O) Up to three errors in general: out of 295744442 such error patterns,
          0.034% have probability 2^-25; 0.000065% have probability 2^-20.
    * (G) Up to two errors made to a valid code with the new constant, and fed
          to software that uses the old constant 1: out of 2831622 such error
          patterns, 0.048% have probability 2^-25.

* Specifically for the bc1 HRP, with the BIP173 length restrictions:
  * Always detected:
    * (R) Up to 4 substitution errors (true for any constant).
    * (A) Up to 3 substitution errors made to a valid code with the new
          constant, and fed to software that uses the old constant 1.
  * Any error pattern has failure to detect probability <= 2^-30:
    * (E) Any one error.
    * (F) Any one error made to a valid code with the new constant, and fed to
          software that uses the old constant 1.
    * (H) Up to two errors restricted to a window of 28 characters.
  * Most error patterns have probability <= 2^-30:
    * (J) Up to two errors in general: out of 455916 such error patterns,
          0.039% have probability 2^-25; 0.0053% have 2^-20.
    * (K) Any number of errors restricted to a window of 4 characters: out of
          5813139 such error patterns, 0.0016% have probability 2^-25.
    * (M) Up to three errors: out of 50713466 such error patterns, 0.078% have
          probability 2^-25; 0.00063% have 2^-20.
    * (I) Up to two errors made to a valid code with the new constant, and fed
          to software that uses the old constant 1: out of 610683 such error
          patterns, 0.092% have probability 2^-25; 0.00049% have probability
          2^-20.

To give an idea of what these probabilities mean, consider the known BIP173
insertion issue. It admits an error pattern of 1 error (insertion in
penultimate position) that has a failure to detect probability of 2^-10:
it requires the final character to be 'p', and the inserted character to be
'q'. Assuming those are both random, we have a chance of 1 in 32*32 to hit it.
Note that the choice of *what* the error pattern is (whether it's insertion,
and where) isn't part of our probabilities: we try to make sure that *every*
pattern behaves well, not just randomly chosen ones, because presumably humans
make some kinds of errors more than others, and we don't know which ones.

All the analyzed patterns above are guaranteed to be detected with probability
2^-20 or better (and most are 2^-30). Of course, if we'd search for even
larger classes of errors, say any 4 independent errors of any type, we would
probably discover patterns with worse probabilities, but at that point the
probability of the pattern itself being hit should be taken into account.

The selection was made based on these same properties:
* Start with the set of all 2^30 constants.
* The generic properties (L), (B), (D), (C), (N), (O), and (G) were selected
  for by rejecting all constants that left any worse error patterns (e.g.
  all codes for which patterns matching (N) existed with failure probability
  above 2^-25 were removed). All these restrictions are as strong as they
  can be: making them over longer strings, wider windows, or more errors with
  the same restrictions removes all remaining constants. This leaves us with
  just 12054 acceptable constants.
* The same was then done for the bc1/BIP173 specific properties (A), (E), (J),
  (F), (H), (K), (M), and (I). This reduces the set further to 79 acceptable
  constants. The full analysis output for all of these can be found in
  output.txt.
* Finally, the constant with the minimal number of worst-probability patterns
  was chosen for the generic property (N). The single constant 0x2bc830a3
  remains.
* This solution and a few of its expected properties were then validated using
  a simple program that makes random errors (see the monte_carlo.py file).


Technical details
-----------------

For the purpose of this analysis, define an "error pattern" as a starting
length (of a valid string consisting of otherwise randomly chosen characters)
combined with a sequence of the following (in this order):
* 0 or more deletions of characters at specific positions (without
  constraining what those characters are)
* 0 or more swaps of characters at specific positions with the character
  following it
* 0 or more substitutions of characters at specific positions with a uniformly
  randomly selected character
* 0 or more insertions of uniformly randomly selected characters at specific
  positions
* 0 or more duplications of characters at specific positions (including
  duplications of characters inserted/substituted in the previous steps)

Examples:
* "Start with a random valid 58 character string, remove the 17th character,
  swap the 11th character with the 12th character, and insert a random
  character in the 24th position" is an error pattern.
* "Replace the 17th through 24th characters in a 78 character string with
  'aardvark'" is not an error pattern, because substituted characters have to
  be random, and can't be specific values.

Given such a pattern, assign variable names to every input character, and to
every inserted/substituted character. For example, the pattern "Start with
a 6 character string, delete the 1st character, swap the 2nd and 3rd
character, and insert a random character between those" would be represented
as [v0 v1 v2 v3 v4 v5] and [v1 v3 v6 v2 v4 v5]. Treat these variables as
elements of GF(32), and write out the equations that both the first and second
list have a valid checksum. Due to the fact that BCH codes are linear, this is
just a linear set of equations over GF(32), and we can use Gaussian
elimination to find the size of the solution space. If the input and output
are the same length, we need to subtract the number of solutions for which the
input and output are exactly the same, which is easy to find with another set
of equations. Now compute the ratio of this number divided by (32^numvars /
32^6), where the 32^6 is due to the precondition that the input string is
valid. This gives us the probability of failure, assuming input and output are
random, apart from the known relation between the two, and the fact that both
are valid.

This technique has an important limitation: it can only reason about randomly-
chosen input strings, and the presence of the HRP and version numbers at the
start violates that assumption. These are not random, and we're forced to
make one of these concessions:
1) Ignore the problem, and treat the HRP as random. This lets us derive
   properties that hold over all potential HRPs on average, but will thus fail
   to account for the possibility that for a small numbers of potential HRPs
   some error patterns may exist that behave worse. For technical reasons,
   this averaging makes all constants behave identically for error patterns
   that don't change the length of the string. Given that substitution/swap
   only errors are already dealt with well due to the BCH design this is
   perhaps not too important. One exception is frame-shifting errors (a
   deletion in one place compensated with an insertion in another place).
2) Restrict analysis to error patterns that don't affect the first 6 actual
   characters. Doing so "masks" the effect of the HRP completely.
3) Do analysis for specific HRPs only, allowing much more accurate statements,
   but HRP-specific ones that may not hold for every HRP.

Our final selection primarily optimizes for 1) and 2) as those benefit all
potential uses of the encoding, but do optimize for 3) the "bc1" prefix
specifically (and the BIP173 length restriction) as a tiebreaker.

The code for this can be found under the link above, in const_analysis.cpp.

Cheers,

--
Pieter