This page is the Simplified Technical English version of ZIP 173. The source ZIP is the normative text. Read the writing rules to understand the marked words.
ZIP 173: Bech32 Format
ZIP: 173
Title: Bech32 Format
Owners: Daira-Emma Hopwood <daira@jacaranda.org>
Credits: Pieter Wuille
Greg Maxwell
Rusty Russell
Mark Friedenbach
Status: Final
Category: Standards / Wallet
Created: 2018-06-13
License: MIT
Terminology
On this page, STE words are in the place of the BCP 14 key words of the source. Refer to the key word table.
In this document, the term "network upgrade" has the definition in ZIP 200 [zip-0200].
In this document, the term "Sapling" has the definition in ZIP 205 [zip-0205].
Abstract
This document has a proposal for a checksummed base32 format, "Bech32", and for a standard for Sapling addresses and keys that use it.
Motivation
From its launch, Zcash uses Base58 addresses with a truncated double-SHA256 checksum. Zcash inherited these addresses from Bitcoin. They were part of the original Bitcoin software. Their scope was extended in BIP 13 [bip-0013] for P2SH (Pay-to-Script-Hash) addresses. But both the character set and the checksum algorithm have limitations:
- Base58 uses much space in QR codes, because it cannot use the "alphanumeric mode".
- The mixed case in Base58 makes it inconvenient to do these operations reliably:
- to write a Base58 string down
- to type it on mobile keyboards
- to read it out loud
- The double-SHA256 checksum is slow and has no guarantees of error detection.
- Most of the research on error-detecting codes applies only to character sets of a size that is a prime power. The number 58 is not a prime power.
- Base58 decoding is complicated and relatively slow.
To address these issues, Bitcoin adopted a new encoding, Bech32 [bip-0173]. Bitcoin uses it for the address types that were added by its Segregated Witness proposal. Zcash does not implement Segregated Witness. But Zcash reuses Bech32 with the address and key types that were introduced by the Sapling network upgrade [zip-0205].
The description of Bech32 in [bip-0173] is partially entangled with the Segregated Witness address formats. Thus we found it clearer to write this ZIP to specify Bech32 separately.
We recommend that a reader reads this specification together with two other texts. The first text is section 5.6 ("Encodings of Addresses and Keys") of the Zcash Sapling protocol specification [protocol]. The second text is ZIP 32 [zip-0032]. ZIP 32 contains the specification of additional key types for support of shielded hierarchical deterministic wallets.
Specification
This section has a description of the general checksummed base32 format "Bech32". The Sapling protocol specification [protocol] contains the definition of its use for Sapling payment addresses and keys.
A Bech32 string consists of these parts:
- The human-readable part (HRP)
- The purpose of this part is to convey the type of data, or anything else that is applicable to the reader. This part must contain 1 to 83 US-ASCII characters, and each character must have a value in the range [33-126]. Specific applications can restrict the validity of an HRP further.
- The separator
- The separator is always "1". If the human-readable part can contain "1", the last "1" in the string is the separator.
- The data part
- The data part has a minimum of 6 characters. It consists only of alphanumeric characters, except "1", "b", "i" and "o".
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| +0 | q | p | z | r | y | 9 | x | 8 |
| +8 | g | f | 2 | t | v | d | w | 0 |
| +16 | s | 3 | j | n | 5 | 4 | k | h |
| +24 | c | e | 6 | m | u | a | 7 | l |
Checksum
The last six characters of the data part are a checksum and contain no information. A valid string must pass the criteria for validity in the Python3 code snippet below. The checksum is defined so that the function bech32_verify_checksum returns true when its arguments are:
hrp: the human-readable part as a string.data: the data part as a list of integers. The integers represent the characters after conversion with the table above.
def bech32_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 bech32_hrp_expand(s):
return [ord(x) >> 5 for x in s] + [0] + [ord(x) & 31 for x in s]
def bech32_verify_checksum(hrp, data):
return bech32_polymod(bech32_hrp_expand(hrp) + data) == 1
This snippet is an implementation of a BCH code. If the encoded string has at most 90 characters, this code guarantees detection of any error that has an effect on at most 4 characters. In this case, the code also has less than a 1 in 109 chance of failing to detect more errors. The section Checksum design has more details about the properties.
To process the human-readable part, do these steps:
- Feed the higher 3 bits of the US-ASCII value of each character into the checksum calculation.
- Feed a zero into the checksum calculation.
- Feed the lower 5 bits of the US-ASCII value of each character into the checksum calculation.
To make a valid checksum from the human-readable part and the (non-checksum) values of the data-part characters, the code below can be used:
def bech32_create_checksum(hrp, data): values = bech32_hrp_expand(hrp) + data polymod = bech32_polymod(values + [0,0,0,0,0,0]) ^ 1 return [(polymod >> 5 * (5 - i)) & 31 for i in range(6)]
Error correction
One property of these BCH codes is that they can be used for error correction. Error correction has an unfortunate side effect: error detection becomes weaker. With correction, invalid inputs become valid inputs. But if there are more than a few errors, the valid input can be an input that is not the correct input. Use of an incorrect but valid input can cause an irrecoverable loss of funds.
For this reason, we recommend that implementations not implement correction beyond this limit: a possible suggestion to the user of the place in the string where an error can be, with no suggestion of the correction to make.
Uppercase/lowercase
The lowercase form is used to determine the value of a character for checksum purposes.
Encoders must always output an all-lowercase Bech32 string. If an uppercase version of the encoding result is wanted (for example, for presentation purposes or for QR code use), an uppercasing procedure can be done outside the encoding process.
Decoders must not accept strings where some characters are uppercase and some are lowercase. These strings are mixed-case strings.
For presentation, lowercase is usually better. But inside QR codes, we recommend that uppercase is used. The reason is that the alphanumeric mode can be used with uppercase. This mode is 45% more compact than the byte mode that is used otherwise.
Encoding
- Start with the bits of the raw encoding of the applicable address or key type. Put the most significant bit of each byte first.
- Re-arrange these bits into groups of 5. If necessary, pad with zeroes at the end.
- Translate these bits to characters with the table above. Translate the most significant bit first.
Decoding
An implementation that interprets a Bech32-encoded address must first verify that the human-readable part is the same as that of a specified address type. The same rule applies to keys.
If this check passes, convert the rest of the data to bytes:
- Translate the values to 5 bits with the table above. Put the most significant bit first.
- Re-arrange these bits into groups of 8 bits. Any incomplete group at the end must be 4 bits or fewer and must be all zeroes. Discard this incomplete group.
- Interpret the resulting groups as the raw encoding of the applicable address or key type. The most significant bit is first in each byte.
We recommend that decoders enforce known-length restrictions on address and key types.
For example, in [protocol], the length of the raw encoding of a Sapling payment address is 43 bytes (88 + 256 bits). Thus a Bech32-encoded Sapling payment address is 78 characters long.
Compatibility
Only implementations that support the Sapling network upgrade can use these addresses.
There is no effect on support for transparent addresses and keys, or for Sprout z-addresses and keys. These continue to be encoded with Base58Check, and they must not be encoded with Bech32.
Rationale
Why use base32 at all?
Because base32 has no mixed case, it is more efficient to read it out loud or to put it into QR codes. It has a 15% increase in length. But the length of a Bech32-encoded Sapling payment address stays below 80 characters. Thus line splitting in terminals or email is less likely. Thus the cut and paste of addresses is still reliable.
Why call it Bech32?
"Bech" contains the characters BCH (the error detection algorithm in use) and sounds a bit like "base". The term Bech32 is established for Bitcoin. There was no reason to use a different name for it in Zcash Sapling.
Why not support Bech32 encoding of Sprout or transparent addresses?
Two formats for these address types cause compatibility issues, because pre-Sapling implementations do not support the new format. For this reason, this support was not considered to be sufficiently well-motivated.
Why include a separator in addresses?
The separator is an unambiguous boundary between the human-readable part and the data part. Thus potential collisions with other human-readable parts that share a prefix are avoided. Also, restrictions on the character set of the human-readable part are not necessary. The separator is "1" because, with a non-alphanumeric character, the copy-pasting of addresses is more complicated (in several applications, there is no double-click selection). Thus an alphanumeric character outside the normal character set was selected.
Why not use an existing base32 character set?
Existing character sets for base-32 encodings include RFC 3548 and z-base-32. The set for Bech32 was selected to minimize ambiguity, according to this visual similarity data. The ordering is selected to minimize the number of pairs of similar characters (according to the same data) that differ in more than 1 bit. The checksum is selected to maximize the detection capabilities for low numbers of bit errors. Thus, with this choice, the performance of the checksum is better under some error models.
Why are the high bits of the human-readable part processed first?
This design choice had a rationale for Bitcoin Segregated Witness addresses (refer to [bip-0173]). This rationale does not apply to Zcash Sapling addresses. The design choice is kept for compatibility with Bech32 encoders and decoders that were written for Bitcoin.
Reference implementations
- The encoder/decoder that
zcashduses: - Encoders and decoders that were written specifically for Zcash:
- For C# (Bech32 and Bech32m)
- Encoders and decoders that were written for Bitcoin:
- A fancy decoder that was written for Bitcoin and localizes errors:
The encoders that were written for Bitcoin can make assumptions that are specific to the Segregated Witness address formats. These assumptions do not apply to Zcash. At the time of writing, only the Python encoder was tested with Zcash.
Examples
TODO: add valid Sapling payment addresses and keys, and their corresponding raw encodings.
Test vectors
These strings are valid Bech32:
A12UEL5La12uel5lan83characterlonghumanreadablepartthatcontainsthenumber1andtheexcludedcharactersbio1tt5tgsabcdef1qpzry9x8gf2tvdw0s3jn54khce6mua7lmqqqxw11qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqc8247jsplit1checkupstagehandshakeupstreamerranterredcaperred2y9e3w?1ezyfcl
These strings are not valid Bech32. The reason for the invalidity is after each string:
- 0x20 +
1nwldj5: HRP character out of range - 0x7F +
1axkwrx: HRP character out of range - 0x80 +
1eym55h: HRP character out of range pzry9x0s0muk: No separator character1pzry9x0s0muk: Empty HRPx1b4n0q5v: Invalid data characterli1dgmt3: Too short checksumde1lg7wt+ 0xFF: Invalid character in checksumA1G7SGD8: checksum calculated with uppercase form of HRP10a06t8: empty HRP1qzzfhee: empty HRPbc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t5: Invalid checksumtb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3q0sL5k7: Mixed casebc1zw508d6qejxtdg4y5r3zarvaryvqyzf3du: Zero padding of more than 4 bitstb1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3pjxtptv: Non-zero padding in 8-to-5 conversion
Checksum design
Design choices
BCH codes can be constructed over any prime-power alphabet, and they can be selected to have a good trade-off between size and error-detection capabilities. Unlike Reed-Solomon codes, their length has no restriction to one less than the alphabet size. Efficient error correction is also possible with these codes, but the implementation of only error detection is very simple.
We select 6 checksum characters as a trade-off between the length of the addresses and the error-detection capabilities. The reason is that 6 characters is the lowest number that is sufficient for a random failure chance below 1 per billion. We are most interested in protecting data up to 77 bytes, excluding the separator, for a Sapling payment address. For this length, BCH codes can be constructed that guarantee detection of a maximum of 4 errors. Longer data is also supported, with slightly weaker error detection.
Selected properties
Many of these codes work badly when they deal with more errors than they are designed to detect, but not all of them do. For that reason, we consider codes that are designed to detect only 3 errors, and codes that are designed to detect 4 errors. We analyse how well they work in practice.
The specific code in this document is the result of these steps:
- Start with an exhaustive list of 159605 BCH codes. These codes are designed to detect 3 or 4 errors up to the lengths 93, 151, 165, 341, 1023 and 1057.
- From those, keep only the codes that detect 4 errors up to length 71. This results in 28825 remaining codes.
- From those, select the codes with the best worst-case window for 5-character errors. This results in 310 remaining codes.
- From those, select the code with the lowest chance for not detecting small numbers of bit errors.
A naive search has over 6.5 * 1019 checksum evaluations. Thus a collision-search approach was used for analysis. The code for it is here.
Properties
The table below has a summary of the chances for detection failure (as multiples of 1 in 109).
| Window length | Number of wrong characters | ||||||
|---|---|---|---|---|---|---|---|
| Length | Description | ≤4 | 5 | 6 | 7 | 8 | ≥9 |
| 8 | Longest detecting 6 errors | 0 | 1.127 | 0.909 | n/a | ||
| 18 | Longest detecting 5 errors | 0 | 0.965 | 0.929 | 0.932 | 0.931 | |
| 19 | Worst case for 6 errors | 0 | 0.093 | 0.972 | 0.928 | 0.931 | |
| 39 | Length ≤ 39 characters | 0 | 0.756 | 0.935 | 0.932 | 0.931 | |
| 59 | Length ≤ 59 characters | 0 | 0.805 | 0.933 | 0.931 | ||
| 71 | Length ≤ 71 characters | 0 | 0.830 | 0.934 | 0.931 | ||
| 89 | Longest detecting 4 errors | 0 | 0.867 | 0.933 | 0.931 | ||
TODO: fill in the table for a Sapling payment address, and check the paragraph that follows.
Suppose that 5 changed characters occur at random in the 77 characters of a Sapling payment address (excluding the separator). Then the chance of no detection is at most 0.867 per billion. If those 5 changes occur at random in a 19-character window, that chance decreases to 0.093 per billion. When the number of errors increases, the chance converges towards 1 in 230 = 0.931 per billion.
The selected code works reasonably well up to 1023 characters. It works best for lengths up to 89 characters (excluding the separator). The search for suitable codes was based on the requirements for Bitcoin P2WPKH and P2WSH addresses. Thus the code is not quite optimal for the address lengths of Sapling. But the advantages of compatibility with existing Bitcoin libraries were considered to outweigh this consideration.
Acknowledgements
This document is closely based on BIP 173. Pieter Wuille and Greg Maxwell wrote BIP 173. BIP 173 was inspired by the address proposal by Rusty Russell and the base32 proposal by Mark Friedenbach. BIP 173 also had input from these persons:
- Luke Dashjr
- Johnson Lau
- Eric Lombrozo
- Peter Todd
- various other reviewers
Source errata
The source has one typo in code. This page has the repaired form:
- In
bech32_polymod, the linechk ^= GEN[i] if ((b >> i) & 1) else 0(source line 127) has the same indentation as thefor i in range(5):line above it. Thus Python rejects the source code. On this page, the line is 2 spaces deeper, in the body of that loop.
References
- [BCP14]
- Information on BCP 14 — "RFC 2119: Key words for use in RFCs to Indicate Requirement Levels" and "RFC 8174: Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words"
- [protocol]
- Zcash Protocol Specification, Version 2021.2.16 or later
- [zip-0032]
- ZIP 32: Shielded Hierarchical Deterministic Wallets
- [zip-0200]
- ZIP 200: Network Upgrade Mechanism
- [zip-0205]
- ZIP 205: Deployment of the Sapling Network Upgrade
- [bip-0013]
- BIP 13: Address Format for pay-to-script-hash
- [bip-0173]
- BIP 173: Base32 address format for native v0-16 witness outputs