1 // Copyright (c) 2017 The btcsuite developers
2 // Copyright (c) 2019 The Decred developers
3 // Use of this source code is governed by an ISC
4 // license that can be found in the LICENSE file.
5 6 package bech32
7 8 import (
9 "bytes"
10 "strings"
11 )
12 13 // Charset is the set of characters used in the data section of bech32 strings.
14 // Note that this is ordered, such that for a given charset[i], i is the binary
15 // value of the character.
16 //
17 // This wasn't exported in the original lol.
18 const Charset = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"
19 20 // gen encodes the generator polynomial for the bech32 BCH checksum.
21 var gen = []int{0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3}
22 23 // toBytes converts each character in the string 'chars' to the value of the
24 // index of the corresponding character in 'charset'.
25 func toBytes(chars []byte) ([]byte, error) {
26 decoded := make([]byte, 0, len(chars))
27 for i := 0; i < len(chars); i++ {
28 index := strings.IndexByte(Charset, chars[i])
29 if index < 0 {
30 return nil, ErrNonCharsetChar(chars[i])
31 }
32 decoded = append(decoded, byte(index))
33 }
34 return decoded, nil
35 }
36 37 // bech32Polymod calculates the BCH checksum for a given hrp, values and
38 // checksum data. Checksum is optional, and if nil a 0 checksum is assumed.
39 //
40 // Values and checksum (if provided) MUST be encoded as 5 bits per element (base
41 // 32), otherwise the results are undefined.
42 //
43 // For more details on the polymod calculation, please refer to BIP 173.
44 func bech32Polymod(hrp []byte, values, checksum []byte) int {
45 check := 1
46 // Account for the high bits of the HRP in the checksum.
47 for i := 0; i < len(hrp); i++ {
48 b := check >> 25
49 hiBits := int(hrp[i]) >> 5
50 check = (check&0x1ffffff)<<5 ^ hiBits
51 for i := 0; i < 5; i++ {
52 if (b>>uint(i))&1 == 1 {
53 check ^= gen[i]
54 }
55 }
56 }
57 // Account for the separator (0) between high and low bits of the HRP.
58 // x^0 == x, so we eliminate the redundant xor used in the other rounds.
59 b := check >> 25
60 check = (check & 0x1ffffff) << 5
61 for i := 0; i < 5; i++ {
62 if (b>>uint(i))&1 == 1 {
63 check ^= gen[i]
64 }
65 }
66 // Account for the low bits of the HRP.
67 for i := 0; i < len(hrp); i++ {
68 b := check >> 25
69 loBits := int(hrp[i]) & 31
70 check = (check&0x1ffffff)<<5 ^ loBits
71 for i := 0; i < 5; i++ {
72 if (b>>uint(i))&1 == 1 {
73 check ^= gen[i]
74 }
75 }
76 }
77 // Account for the values.
78 for _, v := range values {
79 b := check >> 25
80 check = (check&0x1ffffff)<<5 ^ int(v)
81 for i := 0; i < 5; i++ {
82 if (b>>uint(i))&1 == 1 {
83 check ^= gen[i]
84 }
85 }
86 }
87 if checksum == nil {
88 // A nil checksum is used during encoding, so assume all bytes are zero.
89 // x^0 == x, so we eliminate the redundant xor used in the other rounds.
90 for v := 0; v < 6; v++ {
91 b := check >> 25
92 check = (check & 0x1ffffff) << 5
93 for i := 0; i < 5; i++ {
94 if (b>>uint(i))&1 == 1 {
95 check ^= gen[i]
96 }
97 }
98 }
99 } else {
100 // Checksum is provided during decoding, so use it.
101 for _, v := range checksum {
102 b := check >> 25
103 check = (check&0x1ffffff)<<5 ^ int(v)
104 for i := 0; i < 5; i++ {
105 if (b>>uint(i))&1 == 1 {
106 check ^= gen[i]
107 }
108 }
109 }
110 }
111 return check
112 }
113 114 // writeBech32Checksum calculates the checksum data expected for a string that
115 // will have the given hrp and payload data and writes it to the provided string
116 // builder.
117 //
118 // The payload data MUST be encoded as a base 32 (5 bits per element) byte slice
119 // and the hrp MUST only use the allowed character set (ascii chars between 33
120 // and 126), otherwise the results are undefined.
121 //
122 // For more details on the checksum calculation, please refer to BIP 173.
123 func writeBech32Checksum(
124 hrp []byte, data []byte, bldr *bytes.Buffer,
125 version Version,
126 ) {
127 128 bech32Const := int(VersionToConsts[version])
129 polymod := bech32Polymod(hrp, data, nil) ^ bech32Const
130 for i := 0; i < 6; i++ {
131 b := byte((polymod >> uint(5*(5-i))) & 31)
132 // This can't fail, given we explicitly cap the previous b byte by the
133 // first 31 bits.
134 c := Charset[b]
135 bldr.WriteByte(c)
136 }
137 }
138 139 // bech32VerifyChecksum verifies whether the bech32 string specified by the
140 // provided hrp and payload data (encoded as 5 bits per element byte slice) has
141 // the correct checksum suffix. The version of bech32 used (bech32 OG, or
142 // bech32m) is also returned to allow the caller to perform proper address
143 // validation (segwitv0 should use bech32, v1+ should use bech32m).
144 //
145 // Data MUST have more than 6 elements, otherwise this function panics.
146 //
147 // For more details on the checksum verification, please refer to BIP 173.
148 func bech32VerifyChecksum(hrp []byte, data []byte) (Version, bool) {
149 checksum := data[len(data)-6:]
150 values := data[:len(data)-6]
151 polymod := bech32Polymod(hrp, values, checksum)
152 // Before BIP-350, we'd always check this against a static constant of
153 // 1 to know if the checksum was computed properly. As we want to
154 // generically support decoding for bech32m as well as bech32, we'll
155 // look up the returned value and compare it to the set of defined
156 // constants.
157 bech32Version, ok := ConstsToVersion[ChecksumConst(polymod)]
158 if ok {
159 return bech32Version, true
160 }
161 return VersionUnknown, false
162 }
163 164 // DecodeNoLimit is a bech32 checksum version aware arbitrary string length
165 // decoder. This function will return the version of the decoded checksum
166 // constant so higher level validation can be performed to ensure the correct
167 // version of bech32 was used when encoding.
168 func decodeNoLimit(bech []byte) ([]byte, []byte, Version, error) {
169 // The minimum allowed size of a bech32 string is 8 characters, since it
170 // needs a non-empty HRP, a separator, and a 6 character checksum.
171 if len(bech) < 8 {
172 return nil, nil, VersionUnknown, ErrInvalidLength(len(bech))
173 }
174 // Only ASCII characters between 33 and 126 are allowed.
175 var hasLower, hasUpper bool
176 for i := 0; i < len(bech); i++ {
177 if bech[i] < 33 || bech[i] > 126 {
178 return nil, nil, VersionUnknown, ErrInvalidCharacter(bech[i])
179 }
180 // The characters must be either all lowercase or all uppercase. Testing
181 // directly with ascii codes is safe here, given the previous test.
182 hasLower = hasLower || (bech[i] >= 97 && bech[i] <= 122)
183 hasUpper = hasUpper || (bech[i] >= 65 && bech[i] <= 90)
184 if hasLower && hasUpper {
185 return nil, nil, VersionUnknown, ErrMixedCase{}
186 }
187 }
188 // Bech32 standard uses only the lowercase for of strings for checksum
189 // calculation.
190 if hasUpper {
191 bech = bytes.ToLower(bech)
192 }
193 // The string is invalid if the last '1' is non-existent, it is the
194 // first character of the string (no human-readable part) or one of the
195 // last 6 characters of the string (since checksum cannot contain '1').
196 one := bytes.LastIndexByte(bech, '1')
197 if one < 1 || one+7 > len(bech) {
198 return nil, nil, VersionUnknown, ErrInvalidSeparatorIndex(one)
199 }
200 // The human-readable part is everything before the last '1'.
201 hrp := bech[:one]
202 data := bech[one+1:]
203 // Each character corresponds to the byte with value of the index in
204 // 'charset'.
205 decoded, err := toBytes(data)
206 if err != nil {
207 return nil, nil, VersionUnknown, err
208 }
209 // Verify if the checksum (stored inside decoded[:]) is valid, given the
210 // previously decoded hrp.
211 bech32Version, ok := bech32VerifyChecksum(hrp, decoded)
212 if !ok {
213 // Invalid checksum. Calculate what it should have been, so that the
214 // error contains this information.
215 //
216 // Extract the payload bytes and actual checksum in the string.
217 actual := bech[len(bech)-6:]
218 payload := decoded[:len(decoded)-6]
219 // Calculate the expected checksum, given the hrp and payload
220 // data. We'll actually compute _both_ possibly valid checksum
221 // to further aide in debugging.
222 var expectedBldr bytes.Buffer
223 expectedBldr.Grow(6)
224 writeBech32Checksum(hrp, payload, &expectedBldr, Version0)
225 expectedVersion0 := expectedBldr.String()
226 var bM bytes.Buffer
227 bM.Grow(6)
228 writeBech32Checksum(hrp, payload, &bM, VersionM)
229 expectedVersionM := bM.String()
230 err = ErrInvalidChecksum{
231 Expected: expectedVersion0,
232 ExpectedM: expectedVersionM,
233 Actual: string(actual),
234 }
235 return nil, nil, VersionUnknown, err
236 }
237 // We exclude the last 6 bytes, which is the checksum.
238 return hrp, decoded[:len(decoded)-6], bech32Version, nil
239 }
240 241 // DecodeNoLimit decodes a bech32 encoded string, returning the human-readable
242 // part and the data part excluding the checksum. This function does NOT
243 // validate against the BIP-173 maximum length allowed for bech32 strings and
244 // is meant for use in custom applications (such as lightning network payment
245 // requests), NOT on-chain addresses.
246 //
247 // Note that the returned data is 5-bit (base32) encoded and the human-readable
248 // part will be lowercase.
249 func DecodeNoLimit(bech []byte) ([]byte, []byte, error) {
250 hrp, data, _, err := decodeNoLimit(bech)
251 return hrp, data, err
252 }
253 254 // Decode decodes a bech32 encoded string, returning the human-readable part and
255 // the data part excluding the checksum.
256 //
257 // Note that the returned data is 5-bit (base32) encoded and the human-readable
258 // part will be lowercase.
259 func Decode(bech []byte) ([]byte, []byte, error) {
260 // The maximum allowed length for a bech32 string is 90.
261 if len(bech) > 90 {
262 return nil, nil, ErrInvalidLength(len(bech))
263 }
264 hrp, data, _, err := decodeNoLimit(bech)
265 return hrp, data, err
266 }
267 268 // DecodeGeneric is identical to the existing Decode method, but will also
269 // return bech32 version that matches the decoded checksum. This method should
270 // be used when decoding segwit addresses, as it enables additional
271 // verification to ensure the proper checksum is used.
272 func DecodeGeneric(bech []byte) ([]byte, []byte, Version, error) {
273 // The maximum allowed length for a bech32 string is 90.
274 if len(bech) > 90 {
275 return nil, nil, VersionUnknown, ErrInvalidLength(len(bech))
276 }
277 return decodeNoLimit(bech)
278 }
279 280 // encodeGeneric is the base bech32 encoding function that is aware of the
281 // existence of the checksum versions. This method is private, as the Encode
282 // and EncodeM methods are intended to be used instead.
283 func encodeGeneric(hrp []byte, data []byte, version Version) ([]byte, error) {
284 // The resulting bech32 string is the concatenation of the lowercase
285 // hrp, the separator 1, data and the 6-byte checksum.
286 hrp = bytes.ToLower(hrp)
287 var bldr bytes.Buffer
288 bldr.Grow(len(hrp) + 1 + len(data) + 6)
289 bldr.Write(hrp)
290 bldr.WriteString("1")
291 // Write the data part, using the bech32 charset.
292 for _, b := range data {
293 if int(b) >= len(Charset) {
294 return nil, ErrInvalidDataByte(b)
295 }
296 bldr.WriteByte(Charset[b])
297 }
298 // Calculate and write the checksum of the data.
299 writeBech32Checksum(hrp, data, &bldr, version)
300 return bldr.Bytes(), nil
301 }
302 303 // Encode encodes a byte slice into a bech32 string with the given
304 // human-readable part (HRP). The HRP will be converted to lowercase if needed
305 // since mixed cased encodings are not permitted and lowercase is used for
306 // checksum purposes. Note that the bytes must each encode 5 bits (base32).
307 func Encode(hrp, data []byte) ([]byte, error) {
308 return encodeGeneric(hrp, data, Version0)
309 }
310 311 // EncodeM is the exactly same as the Encode method, but it uses the new
312 // bech32m constant instead of the original one. It should be used whenever one
313 // attempts to encode a segwit address of v1 and beyond.
314 func EncodeM(hrp, data []byte) ([]byte, error) {
315 return encodeGeneric(hrp, data, VersionM)
316 }
317 318 // ConvertBits converts a byte slice where each byte is encoding fromBits bits,
319 // to a byte slice where each byte is encoding toBits bits.
320 func ConvertBits(data []byte, fromBits, toBits uint8, pad bool) (
321 []byte,
322 error,
323 ) {
324 325 if fromBits < 1 || fromBits > 8 || toBits < 1 || toBits > 8 {
326 return nil, ErrInvalidBitGroups{}
327 }
328 // Determine the maximum size the resulting array can have after base
329 // conversion, so that we can size it a single time. This might be off
330 // by a byte depending on whether padding is used or not and if the input
331 // data is a multiple of both fromBits and toBits, but we ignore that and
332 // just size it to the maximum possible.
333 maxSize := len(data)*int(fromBits)/int(toBits) + 1
334 // The final bytes, each byte encoding toBits bits.
335 regrouped := make([]byte, 0, maxSize)
336 // Keep track of the next byte we create and how many bits we have
337 // added to it out of the toBits goal.
338 nextByte := byte(0)
339 filledBits := uint8(0)
340 for _, b := range data {
341 // Discard unused bits.
342 b <<= 8 - fromBits
343 // How many bits remaining to extract from the input data.
344 remFromBits := fromBits
345 for remFromBits > 0 {
346 // How many bits remaining to be added to the next byte.
347 remToBits := toBits - filledBits
348 // The number of bytes to next extract is the minimum of
349 // remFromBits and remToBits.
350 toExtract := remFromBits
351 if remToBits < toExtract {
352 toExtract = remToBits
353 }
354 // Add the next bits to nextByte, shifting the already
355 // added bits to the left.
356 nextByte = (nextByte << toExtract) | (b >> (8 - toExtract))
357 // Discard the bits we just extracted and get ready for
358 // next iteration.
359 b <<= toExtract
360 remFromBits -= toExtract
361 filledBits += toExtract
362 // If the nextByte is completely filled, we add it to
363 // our regrouped bytes and start on the next byte.
364 if filledBits == toBits {
365 regrouped = append(regrouped, nextByte)
366 filledBits = 0
367 nextByte = 0
368 }
369 }
370 }
371 // We pad any unfinished group if specified.
372 if pad && filledBits > 0 {
373 nextByte <<= toBits - filledBits
374 regrouped = append(regrouped, nextByte)
375 filledBits = 0
376 nextByte = 0
377 }
378 // Any incomplete group must be <= 4 bits, and all zeroes.
379 if filledBits > 0 && (filledBits > 4 || nextByte != 0) {
380 return nil, ErrInvalidIncompleteGroup{}
381 }
382 return regrouped, nil
383 }
384 385 // EncodeFromBase256 converts a base256-encoded byte slice into a base32-encoded
386 // byte slice and then encodes it into a bech32 string with the given
387 // human-readable part (HRP). The HRP will be converted to lowercase if needed
388 // since mixed cased encodings are not permitted and lowercase is used for
389 // checksum purposes.
390 func EncodeFromBase256(hrp, data []byte) ([]byte, error) {
391 converted, err := ConvertBits(data, 8, 5, true)
392 if err != nil {
393 return nil, err
394 }
395 return Encode(hrp, converted)
396 }
397 398 // DecodeToBase256 decodes a bech32-encoded string into its associated
399 // human-readable part (HRP) and base32-encoded data, converts that data to a
400 // base256-encoded byte slice and returns it along with the lowercase HRP.
401 func DecodeToBase256(bech []byte) ([]byte, []byte, error) {
402 hrp, data, err := Decode(bech)
403 if err != nil {
404 return nil, nil, err
405 }
406 converted, err := ConvertBits(data, 5, 8, false)
407 if err != nil {
408 return nil, nil, err
409 }
410 return hrp, converted, nil
411 }
412