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

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

[Pieter Wuille]

Hello all,

A while ago it was discovered that bech32 has a mutation weakness (see
https://github.com/sipa/bech32/issues/51 for details). Specifically,
when a bech32 string ends with a "p", inserting or erasing "q"s right
before that "p" does not invalidate it. While insertion/erasure
robustness was not an explicit goal (BCH codes in general only have
guarantees about substitution errors), this is very much not by
design, and this specific issue could have been made much less
impactful with a slightly different approach. I'm sorry it wasn't
caught earlier.

This has little effect on the security of P2WPKH/P2WSH addresses, as
those are only valid (per BIP173) for specific lengths (42 and 62
characters respectively). Inserting 20 consecutive "p"s in a typo
seems highly improbable.

I'm making this post because this property may unfortunately influence
design decisions around bip-taproot, as was brought up in the review
session (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017427.html)
past tuesday. 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.

Thoughts?

Cheers,

-- 
Pieter

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

[Greg Sanders]

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

Could the softer touch of just making them non-standard apply as a future
preparation for an accepted softfork? Relaxations could easily be done
later if desired.

On Thu, Nov 7, 2019, 5:37 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello all,
>
> A while ago it was discovered that bech32 has a mutation weakness (see
> https://github.com/sipa/bech32/issues/51 for details). Specifically,
> when a bech32 string ends with a "p", inserting or erasing "q"s right
> before that "p" does not invalidate it. While insertion/erasure
> robustness was not an explicit goal (BCH codes in general only have
> guarantees about substitution errors), this is very much not by
> design, and this specific issue could have been made much less
> impactful with a slightly different approach. I'm sorry it wasn't
> caught earlier.
>
> This has little effect on the security of P2WPKH/P2WSH addresses, as
> those are only valid (per BIP173) for specific lengths (42 and 62
> characters respectively). Inserting 20 consecutive "p"s in a typo
> seems highly improbable.
>
> I'm making this post because this property may unfortunately influence
> design decisions around bip-taproot, as was brought up in the review
> session (
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017427.html
> )
> past tuesday. 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.
>
> Thoughts?
>
> 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: 2793 bytes --]

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

[Matt Corallo]

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

Given the issue is in the address format, not the consensus/standardness layer, it does seem somewhat strange to jump to addressing it with a consensus/standardness fix. Maybe the ship has sailed, but for the sake of considering all our options, we could also redefine bech32 to not allow such addresses.

Matt

>> On Nov 7, 2019, at 17:47, Greg Sanders via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> Could the softer touch of just making them non-standard apply as a future preparation for an accepted softfork? Relaxations could easily be done later if desired.
> 
>>> On Thu, Nov 7, 2019, 5:37 PM Pieter Wuille via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> Hello all,
>> 
>> A while ago it was discovered that bech32 has a mutation weakness (see
>> https://github.com/sipa/bech32/issues/51 for details). Specifically,
>> when a bech32 string ends with a "p", inserting or erasing "q"s right
>> before that "p" does not invalidate it. While insertion/erasure
>> robustness was not an explicit goal (BCH codes in general only have
>> guarantees about substitution errors), this is very much not by
>> design, and this specific issue could have been made much less
>> impactful with a slightly different approach. I'm sorry it wasn't
>> caught earlier.
>> 
>> This has little effect on the security of P2WPKH/P2WSH addresses, as
>> those are only valid (per BIP173) for specific lengths (42 and 62
>> characters respectively). Inserting 20 consecutive "p"s in a typo
>> seems highly improbable.
>> 
>> I'm making this post because this property may unfortunately influence
>> design decisions around bip-taproot, as was brought up in the review
>> session (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017427.html)
>> past tuesday. 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.
>> 
>> Thoughts?
>> 
>> Cheers,
>> 
>> -- 
>> Pieter
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

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

[David A. Harding]

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.

-Dave

[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-November/017444.html
[2] https://github.com/bitcoin/bitcoin/pull/15846

P.S. My thanks as well to the people who asked the question during
     review that lead to this discussion:

     http://www.erisian.com.au/meetbot/taproot-bip-review/2019/taproot-bip-review.2019-11-05-19.00.log.html#l-88

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

[Eric Voskuil]

> On Nov 8, 2019, at 11:16, David A. Harding via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.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.

As an implementer of both the address encoding and script validation, I agree.

e

> -Dave
> 
> [1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-November/017444.html
> [2] https://github.com/bitcoin/bitcoin/pull/15846
> 
> P.S. My thanks as well to the people who asked the question during
>     review that lead to this discussion:
> 
>     http://www.erisian.com.au/meetbot/taproot-bip-review/2019/taproot-bip-review.2019-11-05-19.00.log.html#l-88
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[ZmnSCPxj]

Good morning Pieter, and all,

Can we modify Bech32 SegWit address format for version 1 and above as below?

      * The data-part values:
      ** 1 byte: the witness version
    + ** If the witness version is non-zero, 1 byte: the length of the witness program.
      ** A conversion of the 2-to-40-byte witness program (as defined by [https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141]) to base32:
      *** Start with the bits of the witness program, most significant bit per byte first.
      *** Re-arrange those bits into groups of 5, and pad with zeroes at the end if needed.
      *** Translate those bits to characters using the table above.

This retains the ability of a bech32 address to specify any valid witness length and allows future version 1 addresses with lengths other than 32, while closing this malleation.

Older software being given the modified v1 address format would mis-send it to the wrong witness program, however.

Alternately we could just keep using version 0 in the address format forever.
The requirement would be to ensure that SegWit vN (N >= 1) output witness programs would have a data-part value encoded as below:

    * The data-part values:
    ** 1 byte: legacy witness version, which must always be 0.
    ** 1 byte: actual witness version, which must be non-zero.
    ** 1 byte: padding length: 0 or 1.
    ** If padding length is 1, 1 byte: padding, which must be 0.
    ** 1 byte: witness program length.
    ** variable: witness program.

A writer for a v1 or later address would initially set an empty padding, then compute:

      1 // actual witness version
    + 1 // padding length
    + 1 // witness length
    + witness_length

If the above sum is 20 or 32, then the writer selects a non-zero padding and inserts the padding byte so that the above sum is now 21 or 33.

To a reader that understands only bech32 v0, such an encoding would look like a SegWit v0 invalid-program-length, and be rejected.
A reader which understands the above protocol would, instead of rejecting a SegWit v0 invalid-program-length, instead attempt to parse it as above first, and consider it as SegWit v1 or higher if it was parsed correctly as above.

The above proposal is of course ridiculous and I am now currently running diagnostics on my processing units to see if further glitches occur in test reasoning skills.

Regards,
ZmnSCPxj

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

[Russell O'Connor]

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

I do like the idea of length prefixing the witness program.  I will note
that the 1 byte witness version is really more like a 1 character witness
version.  There are 17 different segwit versions and there are 32
characters in the bech32 alphabet.  That leaves 15 unused characters that
we can use for assigning new meanings too.

That said, it is probably most sensible to define a new
human-readable-prefix for length prefixed bitcoin witness programs.  "btc1"
anyone?

On Fri, Nov 8, 2019 at 12:12 AM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Pieter, and all,
>
> Can we modify Bech32 SegWit address format for version 1 and above as
> below?
>
>       * The data-part values:
>       ** 1 byte: the witness version
>     + ** If the witness version is non-zero, 1 byte: the length of the
> witness program.
>       ** A conversion of the 2-to-40-byte witness program (as defined by [
> https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141])
> to base32:
>       *** Start with the bits of the witness program, most significant bit
> per byte first.
>       *** Re-arrange those bits into groups of 5, and pad with zeroes at
> the end if needed.
>       *** Translate those bits to characters using the table above.
>
> This retains the ability of a bech32 address to specify any valid witness
> length and allows future version 1 addresses with lengths other than 32,
> while closing this malleation.
>
> Older software being given the modified v1 address format would mis-send
> it to the wrong witness program, however.
>
> Alternately we could just keep using version 0 in the address format
> forever.
> The requirement would be to ensure that SegWit vN (N >= 1) output witness
> programs would have a data-part value encoded as below:
>
>     * The data-part values:
>     ** 1 byte: legacy witness version, which must always be 0.
>     ** 1 byte: actual witness version, which must be non-zero.
>     ** 1 byte: padding length: 0 or 1.
>     ** If padding length is 1, 1 byte: padding, which must be 0.
>     ** 1 byte: witness program length.
>     ** variable: witness program.
>
> A writer for a v1 or later address would initially set an empty padding,
> then compute:
>
>       1 // actual witness version
>     + 1 // padding length
>     + 1 // witness length
>     + witness_length
>
> If the above sum is 20 or 32, then the writer selects a non-zero padding
> and inserts the padding byte so that the above sum is now 21 or 33.
>
> To a reader that understands only bech32 v0, such an encoding would look
> like a SegWit v0 invalid-program-length, and be rejected.
> A reader which understands the above protocol would, instead of rejecting
> a SegWit v0 invalid-program-length, instead attempt to parse it as above
> first, and consider it as SegWit v1 or higher if it was parsed correctly as
> above.
>
> The above proposal is of course ridiculous and I am now currently running
> diagnostics on my processing units to see if further glitches occur in test
> reasoning skills.
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

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

[Damian Mee]

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

> a new human-readable-prefix for length prefixed bitcoin witness
programs.  "btc1" anyone?

Yes, please!

On Fri, Nov 8, 2019 at 2:04 PM Russell O'Connor via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I do like the idea of length prefixing the witness program.  I will note
> that the 1 byte witness version is really more like a 1 character witness
> version.  There are 17 different segwit versions and there are 32
> characters in the bech32 alphabet.  That leaves 15 unused characters that
> we can use for assigning new meanings too.
>
> That said, it is probably most sensible to define a new
> human-readable-prefix for length prefixed bitcoin witness programs.  "btc1"
> anyone?
>
> On Fri, Nov 8, 2019 at 12:12 AM ZmnSCPxj via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Good morning Pieter, and all,
>>
>> Can we modify Bech32 SegWit address format for version 1 and above as
>> below?
>>
>>       * The data-part values:
>>       ** 1 byte: the witness version
>>     + ** If the witness version is non-zero, 1 byte: the length of the
>> witness program.
>>       ** A conversion of the 2-to-40-byte witness program (as defined by [
>> https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141])
>> to base32:
>>       *** Start with the bits of the witness program, most significant
>> bit per byte first.
>>       *** Re-arrange those bits into groups of 5, and pad with zeroes at
>> the end if needed.
>>       *** Translate those bits to characters using the table above.
>>
>> This retains the ability of a bech32 address to specify any valid witness
>> length and allows future version 1 addresses with lengths other than 32,
>> while closing this malleation.
>>
>> Older software being given the modified v1 address format would mis-send
>> it to the wrong witness program, however.
>>
>> Alternately we could just keep using version 0 in the address format
>> forever.
>> The requirement would be to ensure that SegWit vN (N >= 1) output witness
>> programs would have a data-part value encoded as below:
>>
>>     * The data-part values:
>>     ** 1 byte: legacy witness version, which must always be 0.
>>     ** 1 byte: actual witness version, which must be non-zero.
>>     ** 1 byte: padding length: 0 or 1.
>>     ** If padding length is 1, 1 byte: padding, which must be 0.
>>     ** 1 byte: witness program length.
>>     ** variable: witness program.
>>
>> A writer for a v1 or later address would initially set an empty padding,
>> then compute:
>>
>>       1 // actual witness version
>>     + 1 // padding length
>>     + 1 // witness length
>>     + witness_length
>>
>> If the above sum is 20 or 32, then the writer selects a non-zero padding
>> and inserts the padding byte so that the above sum is now 21 or 33.
>>
>> To a reader that understands only bech32 v0, such an encoding would look
>> like a SegWit v0 invalid-program-length, and be rejected.
>> A reader which understands the above protocol would, instead of rejecting
>> a SegWit v0 invalid-program-length, instead attempt to parse it as above
>> first, and consider it as SegWit v1 or higher if it was parsed correctly as
>> above.
>>
>> The above proposal is of course ridiculous and I am now currently running
>> diagnostics on my processing units to see if further glitches occur in test
>> reasoning skills.
>>
>> Regards,
>> ZmnSCPxj
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

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

[Pieter Wuille]

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

On Thu, Nov 7, 2019, 18:16 David A. Harding <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

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

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

[Matt Corallo]

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
> 

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

[Clark Moody]

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

I agree on all points. The address space already brings enough confusion to
users out there. As it stands, we can use script version and program length
for address validity. Sneaking an alternate checksum into the mix for
different length programs lets us lean on our parsing libraries and not
increase cognitive load for users.


-Clark


On Sun, Nov 10, 2019 at 7:02 PM Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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
> >
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

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

[ZmnSCPxj]

Good morning all,

It seems to me that adding the length for checksumming purposes need not require the length to be *actually* added in the address format.

So, currently, below is my understanding of bech32 validation:

* Run BCH checksum on witness program.
* Compare checksum to checksum in address.
  * If the checksum matches:
    * If version is 0, validate that the witness program is length 20 or 32.
    * Else accept.
  * If the checksum does not match:
    * Reject

Let me propose then:

* Run BCH checksum on witness program.
* Compare checksum to checksum in address.
  * If the checksum matches:
    * If version is 0, validate that the witness program is length 20 or 32.
    * Else validate that the witness program is length 32.
  * If the checksum does not match:
    * Get the length of the witness program.
    * Prepend the length to the witness program.
    * Run BCH checksum on concatenated length | witness program.
    * Compare checksum to checksum in address.
      * If the checksum matches:
        * Accept.
      * Else reject.

A writer of bech32 addresses would then:

* If the witness program is length 32, or witness version is 0 and witness program length is 20, use a non-length-prefixed checksum.
* Otherwise, use a length-prefixed checksum (but not include the length in the address, just change the BCH checksum).

This has the following properties:

* The bech32 address format is retained, and no explicit length is added.
* There are now two checksum formats: one with just the witness program, the other which validates with the witness program length.
  * Readers that do not understand the new checksum format will simply reject them without mis-sending to the wrong witness program.

Is the above acceptable?

Regards,
ZmnSCPxj

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

[Pieter Wuille]

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

On Tue, Nov 12, 2019, 21:33 ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning all,
>
> It seems to me that adding the length for checksumming purposes need not
> require the length to be *actually* added in the address format.
>

Indeed!

This has the following properties:
>
> * The bech32 address format is retained, and no explicit length is added.
> * There are now two checksum formats: one with just the witness program,
> the other which validates with the witness program length.
>   * Readers that do not understand the new checksum format will simply
> reject them without mis-sending to the wrong witness program.
>

That's very close to what I was suggesting: create an improved bech32
algorithm and use that for future addresses, rather than working around the
problem in the address encoding while keeping the existing bech32 checksum.
Sorry if that wasn't clear from my previous email.

In this case, there is no need to even implicitly include the length in the
checksum algorithm. Replacing the "xor 1" at the end of the algorithm to
"xor (2^30 - 1)" would reduce the occurrence of this weakness from 1/32 to
1/2^30, and have no downsides otherwise. I'd like to do some analysis to
ascertain it actually will catch any other kind of insertion/deletion
errors with high probability as well before actually proposing it, though.

There are other solutions which do include the length in some fashion
directly in the checksum calculation, which may be preferable (I need to
analyse things...). It's also possible to do this in such a way that for
33-symbol and 53-symbol data parts (corresponding to P2WPKH and P2WSH
lengths) the new algorithm is defined as identical to the old one. That
would simplify upstream users of a bech32 library (which would then
effectively need no changes at all, apart from updating the
checksum/decoder code).

That brings me to Matt's point: there is no need to do this right now. We
can simply amend BIP173 to only permit length 20 and length 32 (and only
length 20 for v0, if you like; but they're so far apart that permitting
both shouldn't hurt), for now. Introducing the "new" address format (the
one using an improved checksum algorithm) only needs to be there in time
for when a non-32-byte-witness-program would come in sight.

Of course, I should update BIP173 to indicate the issue, and have a
suggested improvement for other users of bech32, if they feel this issue is
significant enough.

Cheers,

-- 
Pieter

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

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

[Russell O'Connor]

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

On Wed, Nov 13, 2019 at 1:31 AM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> That brings me to Matt's point: there is no need to do this right now. We
> can simply amend BIP173 to only permit length 20 and length 32 (and only
> length 20 for v0, if you like; but they're so far apart that permitting
> both shouldn't hurt), for now. Introducing the "new" address format (the
> one using an improved checksum algorithm) only needs to be there in time
> for when a non-32-byte-witness-program would come in sight.
>

As a prerequisite to taproot activation, I was looking into amending BIP173
as stated above.  However after reviewing
https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb#detection-of-insertion-errors
it seems that insertions of 5 characters or more is "safe" in the sense
that there is low probability of creating a valid checksum by doing so
randomly.

This means we could safely allow witness programs of lengths *20*, 23, 26,
29, *32*, 36, and 40 (or 39).  These correspond to Bech32 addresses of
length *42*, 47, 52, 57, *62*, 68, and 74 (or 73).  We could also support a
set of shorter addresses, but given the lack of entropy in such short
addresses, it is hard to believe that such witness programs could be used
to secure anything.  I'm not sure what the motivation for allowing such
short witness programs was, but I'm somewhat inclined to exclude them from
the segwit address format.

Given that we would only be able to support one of 39 or 40 byte witness
programs, it is sensible to choose to allow 40 byte witness programs to be
addressable.  This is the maximum witness program size allowed by BIP 141.

So my proposal would be to amend BIP173 in such a way to restrict "bc" and
"tb" segwit address formats to require witness programs be of size *20*,
23, 26, 29, *32*, 36, or 40.  Witness programs of other sizes (between 2
and 40) would, of course, still be legal in accordance with BIP 141;
however they would be unaddressable by using this "bc" and "tb" prefix.
Another address format would be needed to support other witness sizes,
should the need ever arise.

-- 
Russell O'Connor

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

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

[Greg Sanders]

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

Can you make it clear what the bold vs not-bold numbers mean?

On Wed, Jul 15, 2020 at 4:56 PM Russell O'Connor via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Wed, Nov 13, 2019 at 1:31 AM Pieter Wuille via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>>
>> That brings me to Matt's point: there is no need to do this right now. We
>> can simply amend BIP173 to only permit length 20 and length 32 (and only
>> length 20 for v0, if you like; but they're so far apart that permitting
>> both shouldn't hurt), for now. Introducing the "new" address format (the
>> one using an improved checksum algorithm) only needs to be there in time
>> for when a non-32-byte-witness-program would come in sight.
>>
>
> As a prerequisite to taproot activation, I was looking into amending
> BIP173 as stated above.  However after reviewing
> https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb#detection-of-insertion-errors
> it seems that insertions of 5 characters or more is "safe" in the sense
> that there is low probability of creating a valid checksum by doing so
> randomly.
>
> This means we could safely allow witness programs of lengths *20*, 23,
> 26, 29, *32*, 36, and 40 (or 39).  These correspond to Bech32 addresses
> of length *42*, 47, 52, 57, *62*, 68, and 74 (or 73).  We could also
> support a set of shorter addresses, but given the lack of entropy in such
> short addresses, it is hard to believe that such witness programs could be
> used to secure anything.  I'm not sure what the motivation for allowing
> such short witness programs was, but I'm somewhat inclined to exclude them
> from the segwit address format.
>
> Given that we would only be able to support one of 39 or 40 byte witness
> programs, it is sensible to choose to allow 40 byte witness programs to be
> addressable.  This is the maximum witness program size allowed by BIP 141.
>
> So my proposal would be to amend BIP173 in such a way to restrict "bc" and
> "tb" segwit address formats to require witness programs be of size *20*,
> 23, 26, 29, *32*, 36, or 40.  Witness programs of other sizes (between 2
> and 40) would, of course, still be legal in accordance with BIP 141;
> however they would be unaddressable by using this "bc" and "tb" prefix.
> Another address format would be needed to support other witness sizes,
> should the need ever arise.
>
> --
> Russell O'Connor
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

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

[Russell O'Connor]

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

The bold values are the witness program lengths and address lengths of the
segwit v0 programs (BIP-141), which clearly need to be covered in my
proposed amendment.  32 bytes is also the proposed witness program length
for segwit v1 that would correspond to a taproot (BIP-341) program.

On Wed, Jul 15, 2020 at 5:05 PM Greg Sanders <gsanders87@gmail.com> wrote:

> Can you make it clear what the bold vs not-bold numbers mean?
>
> On Wed, Jul 15, 2020 at 4:56 PM Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> On Wed, Nov 13, 2019 at 1:31 AM Pieter Wuille via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>>
>>> That brings me to Matt's point: there is no need to do this right now.
>>> We can simply amend BIP173 to only permit length 20 and length 32 (and only
>>> length 20 for v0, if you like; but they're so far apart that permitting
>>> both shouldn't hurt), for now. Introducing the "new" address format (the
>>> one using an improved checksum algorithm) only needs to be there in time
>>> for when a non-32-byte-witness-program would come in sight.
>>>
>>
>> As a prerequisite to taproot activation, I was looking into amending
>> BIP173 as stated above.  However after reviewing
>> https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb#detection-of-insertion-errors
>> it seems that insertions of 5 characters or more is "safe" in the sense
>> that there is low probability of creating a valid checksum by doing so
>> randomly.
>>
>> This means we could safely allow witness programs of lengths *20*, 23,
>> 26, 29, *32*, 36, and 40 (or 39).  These correspond to Bech32 addresses
>> of length *42*, 47, 52, 57, *62*, 68, and 74 (or 73).  We could also
>> support a set of shorter addresses, but given the lack of entropy in such
>> short addresses, it is hard to believe that such witness programs could be
>> used to secure anything.  I'm not sure what the motivation for allowing
>> such short witness programs was, but I'm somewhat inclined to exclude them
>> from the segwit address format.
>>
>> Given that we would only be able to support one of 39 or 40 byte witness
>> programs, it is sensible to choose to allow 40 byte witness programs to be
>> addressable.  This is the maximum witness program size allowed by BIP 141.
>>
>> So my proposal would be to amend BIP173 in such a way to restrict "bc"
>> and "tb" segwit address formats to require witness programs be of size
>> *20*, 23, 26, 29, *32*, 36, or 40.  Witness programs of other sizes
>> (between 2 and 40) would, of course, still be legal in accordance with BIP
>> 141; however they would be unaddressable by using this "bc" and "tb"
>> prefix.  Another address format would be needed to support other witness
>> sizes, should the need ever arise.
>>
>> --
>> Russell O'Connor
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

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