Bitcoin Book of BIPs

BIP 350

Introduction

Abstract

This document defines an improved variant of Bech32 called Bech32m, and amends BIP173 to use Bech32m for native segregated witness outputs of version 1 and later. Bech32 remains in use for segregated witness outputs of version 0.

This BIP is licensed under the 2-clause BSD license.

Motivation

BIP173 defined a generic checksummed base 32 encoded format called Bech32. It is in use for segregated witness outputs of version 0 (P2WPKH and P2WSH, see BIP141), and other applications.

Bech32 has an unexpected weakness: whenever the final character is a ‘p’, inserting or deleting any number of ‘q’ characters immediately preceding it does not invalidate the checksum. This does not affect existing uses of witness version 0 BIP173 addresses due to their restriction to two specific lengths, but may affect future uses and/or other applications using the Bech32 encoding.

This document addresses that by specifying Bech32m, a variant of Bech32 that mitigates this insertion weakness and related issues.

Specification

We first specify the new checksum algorithm, and then document how it should be used for future Bitcoin addresses.

Bech32m

Bech32m modifies the checksum of the Bech32 specification, replacing the constant 1 that is xored into the checksum at the end with 0x2bc830a3. The resulting checksum verification and creation algorithm (in Python, cf. the code in Bech32 section):

BECH32M_CONST = 0x2bc830a3

def bech32m_polymod(values):
  GEN = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]
  chk = 1
  for v in values:
    b = (chk >> 25)
    chk = (chk & 0x1ffffff) << 5 ^ v
    for i in range(5):
      chk ^= GEN[i] if ((b >> i) & 1) else 0
  return chk

def bech32m_hrp_expand(s):
  return [ord(x) >> 5 for x in s] + [0] + [ord(x) & 31 for x in s]

def bech32m_verify_checksum(hrp, data):
  return bech32m_polymod(bech32m_hrp_expand(hrp) + data) == BECH32M_CONST

def bech32m_create_checksum(hrp, data):
  values = bech32m_hrp_expand(hrp) + data
  polymod = bech32m_polymod(values + [0,0,0,0,0,0]) ^ BECH32M_CONST
  return [(polymod >> 5 * (5 - i)) & 31 for i in range(6)]

All other aspects of Bech32 remain unchanged, including its human-readable parts (HRPs).

A combined function to decode both Bech32 and Bech32m simultaneously could be written using:

class Encoding(Enum):
    BECH32 = 1
    BECH32M = 2

def bech32_bech32m_verify_checksum(hrp, data):
    check = bech32_polymod(bech32_hrp_expand(hrp) + data)
    if check == 1:
        return Encoding.BECH32
    elif check == BECH32M_CONST:
        return Encoding.BECH32M
    else:
        return None

which returns either None for failure, or one of the BECH32 / BECH32M enumeration values to indicate successful decoding according to the respective standard.

Addresses for segregated witness outputs

Version 0 outputs (specifically, P2WPKH and P2WSH addresses) continue to use Bech32Why not permit both Bech32 and Bech32m for v0 addresses? Permitting both encodings reduces the error detection capabilities (it makes it equivalent to only have 29 bits of checksum). as specified in BIP173. Addresses for segregated witness outputs version 1 through 16 use Bech32m. Again, all other aspects of the encoding remain the same, including the ‘bc’ HRP.

To generate an address for a segregated witness output:

To decode an address, client software should either decode with both a Bech32 and a Bech32m decoderCan a single string simultaneously be valid as Bech32 and Bech32m? No, a valid Bech32 and Bech32m string will always differ by at least 3 characters if they are the same length., or use a decoder that supports both simultaneously. In both cases, the address decoder has to verify that the encoding matches what is expected for the decoded witness version (Bech32 for version 0, Bech32m for others).

The following code demonstrates the checks that need to be performed. Refer to the Python code linked in the reference implementation section below for full details of the called functions.

def decode(hrp, addr):
    hrpgot, data, spec = bech32_decode(addr)
    if hrpgot != hrp:
        return (None, None)
    decoded = convertbits(data[1:], 5, 8, False)
    # Witness programs are between 2 and 40 bytes in length.
    if decoded is None or len(decoded) < 2 or len(decoded) > 40:
        return (None, None)
    # Witness versions are in range 0..16.
    if data[0] > 16:
        return (None, None)
    # Witness v0 programs must be exactly length 20 or 32.
    if data[0] == 0 and len(decoded) != 20 and len(decoded) != 32:
        return (None, None)
    # Witness v0 uses Bech32; v1 through v16 use Bech32m.
    if data[0] == 0 and spec != Encoding.BECH32 or data[0] != 0 and spec != Encoding.BECH32M:
        return (None, None)
    # Success.
    return (data[0], decoded)

Error locating

Bech32m, like Bech32, does support locatingWhat about error correction? As explained in BIP173, introducing error correction reduces the ability to detect errors. While it is technically possible to correct a small number of errors due to Bech32(m)’s nature as a BCH code, implementations should refrain from using this for more than indicating where an error may be present. the positions of a few substitution errors. To combine this functionality with the segregated witness addresses proposed by this document, simply try locating errors for both Bech32 and Bech32m. If only one finds error locations, report that one. If both do (which should be very rare), there are a number of options:

See the fancy Javascript decoder below for example of the above.

Compatibility

This document introduces a new encoding for v1 segregated witness outputs and higher versions. There should not be any compatibility issues on the receiver side; no wallets are creating v1 segregated witness addresses yet, as the output type is not usable on mainnet.

On the other hand, the Bech32m proposal breaks forward-compatibility for sending to v1 and higher version segregated witness addresses. This incompatibility is intentional. An alternative design was considered where Bech32 remained in use for certain subsets of future addresses, but ultimately discarded. By introducing a clean break, we protect not only new software but also existing senders from the mutation issue, as new addresses will be incompatible with the existing Bech32 address validation. Experiments by Taproot proponents had shown that hardly any wallets and services supported sending to higher segregated witness output versions, so little is lost by breaking forward-compatibility. Furthermore, those experiments identified cases in which segregated witness implementations would have caused wallets to burn funds when sending to version 1 addresses. In case it is still in use, the chosen approach will prevent such software from destroying funds when attempting to send to a Bech32m address.

Reference implementations

Test vectors

Implementation advice Experiments testing BIP173 implementations found that many wallets and services did not support sending to higher version segregated witness outputs. In anticipation of the proposed Taproot soft fork introducing v1 segregated witness outputs on the network, we emphatically recommend employing the complete set of test vectors provided below as well as ensuring that your implementation supports sending to v1 and higher versions. All higher versions of native segregated witness outputs should be recognized as valid recipients. As higher versions are not defined on the network, no wallet should ever create them and no recipient should ever provide them to a sender. Nor should a recipient ever want to falsely provide them as the recipient would simply see a payment intended to themselves burned instead. However, by defining higher versions as valid recipients now, future soft forks introducing higher versions of native segwit outputs will be forward-compatible to all wallets correctly implementing the Bech32m specification.

Test vectors for Bech32m

The following strings are valid Bech32m:

No string can be simultaneously valid Bech32 and Bech32m, so the above examples also serve as invalid test vectors for Bech32.

The following string are not valid Bech32m (with reason for invalidity):

Test vectors for v0-v16 native segregated witness addresses

The following list gives valid segwit addresses and the scriptPubKey that they translate to in hex.

The following list gives invalid segwit addresses and the reason for their invalidity.

Appendix: checksum design & properties

Checksums are used to detect errors introduced into data during transfer. A hash function-based checksum such as Base58Check detects any type of error uniformly, but not all classes of errors are equally likely to occur in practice. Bech32 prioritizes detection of substitution errors, but improving detection of one error class inevitably worsens detection of other error classes. During the design of Bech32, it was assumed that other simple error patterns beside substitutions would have a similar detection rate as in a hash function-based design, and detection would only be worse for complex, impractical errors. The discovered insertion weakness shows that this is not the case.

For Bech32m, we aim to retain Bech32’s guarantees for substitution errors, but make sure that other common errors don’t perform worse than a hash function-based checksum would. To make sure the new standard is easy to implement, we restrict the design space to only amending the final constant that is xored in, as it was observed that is sufficient to mitigate the ‘q’ insertion issue while retaining the intended substitution error detection. In what follows, we explain how the new constant 0x2bc830a3 was chosen.

Error patterns & detection probability

We define an error pattern as a sequence of first one or more deletions, then swaps of adjacent characters, followed by substitutions, insertions, and duplications, in that order, all in specific positions, applied to a string with valid checksum that is otherwise randomly chosen. For insertions and substitutions we assume a uniformly random new character. For example, “delete 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 43rd through 48th character with ‘aardvark’” is not a valid error pattern, because the new characters are not random and there is no reason why this particular string is more likely than any other to be substituted.

A hash function-based checksum design with a 30-bit hash would have a probability of incorrectly accepting equal to 2-30, for every error pattern. Bech32 has a probability of 0 to incorrectly accept error patterns consisting of up to 4 substitutions—they are always detected. The ‘q’-insertion issue shows that for Bech32 a simple error pattern (“insert a random character in the penultimate position”) with probability 2-10 exists: it requires the final character to be ‘p’ (leaving only 1 in 32 strings), and requires the inserted character to be ‘q’ (permitting only 1 of 32 possible inserted characters).

Note that the choice of what the error pattern is (which types of errors, 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 cannot easily model which ones.

Detection properties of Bech32m

The table below shows the error detection properties of Bech32m, and a comparison with Bech32. The code used for this analysis can be found here. Every row specifies one error pattern via the constraints in the left four columns. The remaining columns report what percentage of those patterns have certain probabilities of not being detected. The columns are:

The properties are divided into two classes: those that hold over all strings when averaged over all possible HRPs (human readable parts), and those specific to the “bc1” HRP with the length restrictions imposed by segregated witness addressesWhat restrictions were taken into account for the “bc1”-specific analysis? The minimum length (due to witness programs being at least 2 bytes), the maximum length (due to witness programs being at most 40 bytes), and the fact that the witness programs are a multiple of 8 bits. The fact that the first data symbol cannot be over 16, or that the padding has to be 0, is not taken into account..

errors of type window code/verifier error patterns with failure probability
0 2-30 2-25 2-20 2-15 2-10
Properties averaged over all HRPs
≤ 4 only subst. any Bech32m/Bech32m 100.00% none(a)
any any ≤ 4 56.16% 43.84% none(b)
≤ 2 any ≤ 68 7.71% 92.28% none(b)
≤ 2 any any 7.79% 92.20% 0.004% none(b)
≤ 3 any ≤ 69 7.73% 92.23% 0.033%(d) none(b)
≤ 3 any any 7.77% 92.19% 0.034% 0.000065% none(b)
≤ 4 only subst. any Bech32/Bech32 100.00% none
any any ≤ 4 54.00% 43.84% 1.08% 0.90% 0.17% 0.0091%
≤ 2 any ≤ 68 4.59% 92.29% 1.09% 1.01% 0.99% 0.039%
≤ 2 any any 4.58% 92.21% 1.11% 1.04% 1.02% 0.038%
≤ 3 any ≤ 69 6.69% 92.23% 0.56% 0.48% 0.041% 0.00055%
≤ 3 any any 6.66% 92.19% 0.59% 0.52% 0.041% 0.00053%
0 - - Bech32m/Bech32 100.00% none(a)
1 any - 46.53% 53.46% none(b)
≤ 2 any any 22.18% 77.77% 0.048% none(b)
Properties for segregated witness addresses with HRP “bc”
≤ 4 only subst. any Bech32m/Bech32m 100.00% none(a)
1 any - 24.34% 75.66% none(c)
≤ 2 any ≤ 28 16.85% 83.15% none(c)
any any ≤ 4 74.74% 25.25% 0.0016% none(c)
≤ 2 any any 15.72% 84.23% 0.039% 0.0053% none(c)
≤ 3 any any 13.98% 85.94% 0.078% 0.00063% none(c)
≤ 4 only subst. any Bech32/Bech32 100.00% none
1 any - 14.63% 75.71% 2.43% 2.43% 2.43% 2.38%
≤ 2 any ≤ 28 14.22% 83.15% 0.94% 0.84% 0.79% 0.054%
any any ≤ 4 73.23% 25.26% 0.76% 0.63% 0.12% 0.0064%
≤ 2 any any 12.79% 84.24% 1.06% 0.95% 0.92% 0.041%
≤ 3 any any 13.00% 85.94% 0.57% 0.45% 0.044% 0.00067%
≤ 3 only subst. any Bech32m/Bech32 100.00% none(c)
1 any - 70.89% 29.11% none(c)
≤ 2 any any 36.12% 63.79% 0.092% 0.00049% none(c)

The numbers in this table, as well as a comparison with the numbers for the ‘’1’’ constant and earlier proposed improved constants, can be found here.

Selection process

The details of the selection process can be found here, but in short:

Footnotes

Acknowledgements

Thanks to Greg Maxwell for doing most of the computation for code selection and analysis, and comments. Thanks to Mark Erhardt for help with writing and editing this document. Thanks to Rusty Russell and others on the bitcoin-dev list for the discussion around intentionally breaking compatibility with existing senders, which is used in this specification.

  BIP: 321
  Layer: Applications
  Title: URI Scheme
  Authors: Matt Corallo <bip21@bluematt.me>
  Status: Complete
  Type: Specification
  Assigned: 2024-11-15
  License: BSD-2-Clause
  Replaces: 21