Bech32m BIP: new checksum, and usage for segwit address

Hello all,

here is a BIP draft for changing the checksum in native segwit addresses for v1 and higher, following the discussion in https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018293.html

Overall, the idea is: * Define a new encoding which is a tweaked variant of Bech32, called Bech32m. It refers to the Bech32 section of BIP173, which remains in effect. * Define a new segwit address encoding which replaces the corresponding section in BIP173. It prescribes using Bech32 for v0 witness addresses, and Bech32m for other versions.

Comments, suggestions, ideas?

Cheers,

On Monday, January 4, 2021 4:14 PM, Pieter Wuille <bitcoin-dev@wuille•net> wrote:

> Hello all,
>
> here is a BIP draft for changing the checksum in native segwit addresses for v1 and higher, following the discussion in https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018293.html
>
> Overall, the idea is:
> * Define a new encoding which is a tweaked variant of Bech32, called Bech32m. It refers to the Bech32 section of BIP173, which remains in effect.
> * Define a new segwit address encoding which replaces the corresponding section in BIP173. It prescribes using Bech32 for v0 witness addresses, and Bech32m for other versions.

Of course I forgot the actual link: https://github.com/sipa/bips/blob/bip-bech32m/bip-bech32m.mediawiki

Cheers,

Perhaps title 'Bech32m address format for native v0-16 segregated witness outputs' should probably be v1-16?

This is a thorough and clear write up; a superb read.

Side note: I am deeply impressed with your mathematical jujitsu that no bech32 string is also a valid bech32m string *even with three errors*.

This sways me even more that this approach is correct.

Untested-Ack.

Thanks, Rusty.

Pieter Wuille via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> writes:

> On Monday, January 4, 2021 4:14 PM, Pieter Wuille <bitcoin-dev@wuille•net> wrote:
>
>> Hello all,
>>
>> here is a BIP draft for changing the checksum in native segwit addresses for v1 and higher, following the discussion in https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018293.html
>>
>> Overall, the idea is:
>> * Define a new encoding which is a tweaked variant of Bech32, called Bech32m. It refers to the Bech32 section of BIP173, which remains in effect.
>> * Define a new segwit address encoding which replaces the corresponding section in BIP173. It prescribes using Bech32 for v0 witness addresses, and Bech32m for other versions.
>
> Of course I forgot the actual link: https://github.com/sipa/bips/blob/bip-bech32m/bip-bech32m.mediawiki
>
> Cheers,
>
> --
> Pieter
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Dear Pieter,

I read the BIP draft of Bech32m and implemented it in Go.

Let me ask you one question. Does Checksum have to be fixed? The 'bech32_verify_checksum' function has hrp and data as parameters, so how about committing Checksum with these two values?

For example, calculate Checksum from hrp and data using hash, chacha20, etc.

Thank you. Takatoshi Nakagawa

2021年1月5日(火) 9:14 Pieter Wuille via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org>:

>
> Hello all,
>
> here is a BIP draft for changing the checksum in native segwit addresses for v1 and higher, following the discussion in https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018293.html
>
> Overall, the idea is:
> * Define a new encoding which is a tweaked variant of Bech32, called Bech32m. It refers to the Bech32 section of BIP173, which remains in effect.
> * Define a new segwit address encoding which replaces the corresponding section in BIP173. It prescribes using Bech32 for v0 witness addresses, and Bech32m for other versions.
>
> Comments, suggestions, ideas?
>
> Cheers,
>
> --
> Pieter
>
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Hi all,

A few updates, in response to comments here and in a few other places:

- Updated several reference implementations (C, C++, Python, Javascript) to support Bech32m: https://github.com/sipa/bech32/tree/bech32m (but contributions to update other languages are welcome!)

- Updated website, including error-locating JS decoder, and demo: http://bitcoin.sipa.be/bech32/demo/demo.html

- Opened a Bitcoin Core PR: https://github.com/bitcoin/bitcoin/pull/20861

- Updates to the BIP draft (https://github.com/sipa/bips/blob/bip-bech32m/bip-bech32m.mediawiki):
  * Made the title clearer (so it doesn't imply Bech32m is used for v0)
  * Added rationale for not permitting both Bech32 and Bech32m for v0
  * Added a section on error location
  * Added links for more reference implementations

On Friday, January 15, 2021 12:01 AM, nakagat <nakagat@gmail•com> wrote:

> I read the BIP draft of Bech32m and implemented it in Go.

Cool! Do feel like contributing it to https://github.com/sipa/bech32/tree/bech32m?

> Let me ask you one question.
> Does Checksum have to be fixed?
> The 'bech32_verify_checksum' function has hrp and data as parameters,
> so how about committing Checksum with these two values?
>
> For example, calculate Checksum from hrp and data using hash, chacha20, etc.

I'm not entirely sure what you mean. Do you mean:

1) Can we use a hash function to compute the checksum instead of Bech32's algorithm?

If you compute the checksum using the HRP and the data using a hash function, you just 2^-30 failure probability for any error. The idea behind Bech32 was doing better than that for common errors: any error that consists of up to 4 substitutions are a failure probability of 0 - far better than a hash can do.

2) Can we keep using Bech32's algorithm, but compute the final xorred-in constant from the HRP and the data using a hash function?

That would be functionally equivalent to (1).

3) Can we keep using Bech32's algorithm, but compute the final xorred-in constant from the HRP (but not the data) using a hash function?

It would mean that some (very) small set of potential HRPs would exhibit much worse behavior than others - including the 'q'-before-'p' that the original Bech32 has.

Does that clarify things?

Cheers,

Dear. Peter,

I'm not good at English, so I'm sorry for the poor explanation.

I thought that BECH32M_CONST could be created from hrp and data instead of constants.

I thought that the error position would be the same as bech32 by recalculating the value created from hrp and data.

If this were possible, I thought I could commit hrp and data to the checksum.

Thank you. Takatoshi Nakagawa

2021年1月18日(月) 13:15 Pieter Wuille <bitcoin-dev@wuille•net>:

>
> Hi all,
>
> A few updates, in response to comments here and in a few other places:
>
> - Updated several reference implementations (C, C++, Python, Javascript) to support Bech32m: https://github.com/sipa/bech32/tree/bech32m (but contributions to update other languages are welcome!)
>
> - Updated website, including error-locating JS decoder, and demo: http://bitcoin.sipa.be/bech32/demo/demo.html
>
> - Opened a Bitcoin Core PR: https://github.com/bitcoin/bitcoin/pull/20861
>
> - Updates to the BIP draft (https://github.com/sipa/bips/blob/bip-bech32m/bip-bech32m.mediawiki):
>   * Made the title clearer (so it doesn't imply Bech32m is used for v0)
>   * Added rationale for not permitting both Bech32 and Bech32m for v0
>   * Added a section on error location
>   * Added links for more reference implementations
>
> On Friday, January 15, 2021 12:01 AM, nakagat <nakagat@gmail•com> wrote:
>
> > I read the BIP draft of Bech32m and implemented it in Go.
>
> Cool! Do feel like contributing it to https://github.com/sipa/bech32/tree/bech32m?
>
> > Let me ask you one question.
> > Does Checksum have to be fixed?
> > The 'bech32_verify_checksum' function has hrp and data as parameters,
> > so how about committing Checksum with these two values?
> >
> > For example, calculate Checksum from hrp and data using hash, chacha20, etc.
>
> I'm not entirely sure what you mean. Do you mean:
>
> 1) Can we use a hash function to compute the checksum instead of Bech32's algorithm?
>
> If you compute the checksum using the HRP and the data using a hash function, you just 2^-30 failure probability for any error. The idea behind Bech32 was doing better than that for common errors: any error that consists of up to 4 substitutions are a failure probability of 0 - far better than a hash can do.
>
> 2) Can we keep using Bech32's algorithm, but compute the final xorred-in constant from the HRP and the data using a hash function?
>
> That would be functionally equivalent to (1).
>
> 3) Can we keep using Bech32's algorithm, but compute the final xorred-in constant from the HRP (but not the data) using a hash function?
>
> It would mean that some (very) small set of potential HRPs would exhibit much worse behavior than others - including the 'q'-before-'p' that the original Bech32 has.
>
> Does that clarify things?
>
> Cheers,
>
> --
> Pieter
>

On Sunday, January 17, 2021 9:59 PM, nakagat <nakagat@gmail•com> wrote:

> I thought that BECH32M_CONST could be created from hrp and data
> instead of constants.
>
> I thought that the error position would be the same as bech32 by
> recalculating the value created from hrp and data.

So, bech32 can be written as:

* checksum = polymod(expand(hrp) + data) xor 1

Bech32m changes that to:

* checksum = polymod(expand(hrp) + data) xor 0x2bc830a3

I believe that your idea is:

* checksum = polymod(expand(hrp) + data) xor hash(hrp, data)

That has exactly the same error detecting capabilities as:

* checksum = hash(hrp, data)

The hashing makes all types of errors uniform, and it doesn't matter what other things are added to the checksum. Once you hash the data, the checksum is uniformly random, and you can't make it "less random" anymore.

In this case, we *want* non-uniformity. The polymod function as a checksum detects some kinds of errors much better than others, and this is what we want.

Does that clarify things?

Cheers,

On Tuesday, January 19, 2021 4:23 PM, nakagat <nakagat@gmail•com> wrote:

> Dear. Pieter,
>
> My idea is exactly what you wrote.
>
> However, I don't think it is the same as "checksum = hash (hrp, data)".

No, it is not the same. But it has the same error-detection properties as just a hash. Hash-based checksums aren't bad, but: * The BCH based checksum that Bech32 uses is better at detecting certain subsets of errors than a hash can be. Once you add in a hash you irrevocably lose these properties. * If we wanted a checksum with error detection properties that are equivalent to a hash, we should just use a hash like Base58Check did. However, that's not the goal of Bech32/Bech32m.

If this isn't clear, I'm afraid I don't know how to continue discussing this. We can take if off this list, if you want.

Cheers,