BIP 0350

This page describes a BIP (Bitcoin Improvement Proposal). Please see BIP 2 for more information about BIPs and creating them. Please do not just create a wiki page.

Please do not modify this page. This is a mirror of the BIP from the source Git repository here.

  BIP: 350
  Layer: Applications
  Title: Bech32m format for v1+ witness addresses
  Author: Pieter Wuille <pieter@wuille.net>
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0350
  Status: Final
  Type: Standards Track
  Created: 2020-12-16
  License: BSD-2-Clause
  Replaces: 173
  Post-History: 2021-01-05: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-January/018338.html [bitcoin-dev] Bech32m BIP: new checksum, and usage for segwit address

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.

Copyright

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 Bech32 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:

• If its witness version is 0, encode it using Bech32.
• If its witness version is 1 or higher, encode it using Bech32m.

To decode an address, client software should either decode with both a Bech32 and a Bech32m decoder, 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 locating 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:

• Report the one that needs fewer corrections (if they differ).
• Eliminate the response(s) that are inconsistent. Any symbol that isn't on an error location can be checked. For example, if the witness version symbol is not an error location, and it doesn't correspond to the specification used (0 for Bech32, 1+ for Bech32m), that response can be eliminated.

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

• Reference encoder and decoder:
  • Reference Python implementation
  • Reference C implementation
  • Reference C++ implementation
  • Bitcoin Core C++ implementation
  • Reference Javascript implementation

• Fancy decoder that localizes errors:
  • For JavaScript (demo website)

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:

• A1LQFN3A
• a1lqfn3a
• an83characterlonghumanreadablepartthatcontainsthetheexcludedcharactersbioandnumber11sg7hg6
• abcdef1l7aum6echk45nj3s0wdvt2fg8x9yrzpqzd3ryx
• 11llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllludsr8
• split1checkupstagehandshakeupstreamerranterredcaperredlc445v
• ?1v759aa

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):

• 0x20 + 1xj0phk: HRP character out of range
• 0x7F + 1g6xzxy: HRP character out of range
• 0x80 + 1vctc34: HRP character out of range
• an84characterslonghumanreadablepartthatcontainsthetheexcludedcharactersbioandnumber11d6pts4: overall max length exceeded
• qyrz8wqd2c9m: No separator character
• 1qyrz8wqd2c9m: Empty HRP
• y1b0jsk6g: Invalid data character
• lt1igcx5c0: Invalid data character
• in1muywd: Too short checksum
• mm1crxm3i: Invalid character in checksum
• au1s5cgom: Invalid character in checksum
• M1VUXWEZ: checksum calculated with uppercase form of HRP
• 16plkw9: empty HRP
• 1p2gdwpf: empty HRP

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.

• BC1QW508D6QEJXTDG4Y5R3ZARVARY0C5XW7KV8F3T4: 0014751e76e8199196d454941c45d1b3a323f1433bd6
• tb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sl5k7: 00201863143c14c5166804bd19203356da136c985678cd4d27a1b8c6329604903262
• bc1pw508d6qejxtdg4y5r3zarvary0c5xw7kw508d6qejxtdg4y5r3zarvary0c5xw7kt5nd6y: 5128751e76e8199196d454941c45d1b3a323f1433bd6751e76e8199196d454941c45d1b3a323f1433bd6
• BC1SW50QGDZ25J: 6002751e
• bc1zw508d6qejxtdg4y5r3zarvaryvaxxpcs: 5210751e76e8199196d454941c45d1b3a323
• tb1qqqqqp399et2xygdj5xreqhjjvcmzhxw4aywxecjdzew6hylgvsesrxh6hy: 0020000000c4a5cad46221b2a187905e5266362b99d5e91c6ce24d165dab93e86433
• tb1pqqqqp399et2xygdj5xreqhjjvcmzhxw4aywxecjdzew6hylgvsesf3hn0c: 5120000000c4a5cad46221b2a187905e5266362b99d5e91c6ce24d165dab93e86433
• bc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vqzk5jj0: 512079be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

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

• tc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vq5zuyut: Invalid human-readable part
• bc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vqh2y7hd: Invalid checksum (Bech32 instead of Bech32m)
• tb1z0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vqglt7rf: Invalid checksum (Bech32 instead of Bech32m)
• BC1S0XLXVLHEMJA6C4DQV22UAPCTQUPFHLXM9H8Z3K2E72Q4K9HCZ7VQ54WELL: Invalid checksum (Bech32 instead of Bech32m)
• bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kemeawh: Invalid checksum (Bech32m instead of Bech32)
• tb1q0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vq24jc47: Invalid checksum (Bech32m instead of Bech32)
• bc1p38j9r5y49hruaue7wxjce0updqjuyyx0kh56v8s25huc6995vvpql3jow4: Invalid character in checksum
• BC130XLXVLHEMJA6C4DQV22UAPCTQUPFHLXM9H8Z3K2E72Q4K9HCZ7VQ7ZWS8R: Invalid witness version
• bc1pw5dgrnzv: Invalid program length (1 byte)
• bc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7v8n0nx0muaewav253zgeav: Invalid program length (41 bytes)
• BC1QR508D6QEJXTDG4Y5R3ZARVARYV98GJ9P: Invalid program length for witness version 0 (per BIP141)
• tb1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vq47Zagq: Mixed case
• bc1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7v07qwwzcrf: zero padding of more than 4 bits
• tb1p0xlxvlhemja6c4dqv22uapctqupfhlxm9h8z3k2e72q4k9hcz7vpggkg4j: Non-zero padding in 8-to-5 conversion
• bc1gmk9yu: Empty data section

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:

• errors The maximum number of individual errors considered
• of type What type of errors are considered (either "subst. only" for just substitutions, or "any" to also include deletions, swaps, insertions, and duplications)
• window The maximum size of the window in which the errors have to occur
• code/verifier Whether this line is about Bech32 or Bech32m encoded strings, and whether those are evaluated regarding their probability of being accepted by either a Bech32 or a Bech32m verifier.
• error patterns with failure probability For each probability (0, 2^-30, 2^-25, 2^-20, 2^-15, and 2^-10) this reports what percentage of error patterns restricted by the constraints in the previous columns have those probabilities of being incorrectly accepted.

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

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:

• Start with the set of all 2³⁰-1 constants different from Bech32's 1. All of these satisfy the properties marked ^(a) in the table above.
• Through exhaustive analysis, reject all constants that do not exhibit the properties marked ^(b) in the table above (e.g. all constants that permit any error pattern of 2 errors or less in a window of 68 characters or less with a detection probability ≥ 2^-20). This selection leaves us with 12054 candidates.
• Reject all constants that do not exhibit the ^(c) properties in the table above. This leaves us with 79 candidates.
• Finally, select the candidate that minimizes the number of error classes matching ^(d) in the table above as a final tiebreaker. The result is the single constant 0x2bc830a3.

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.