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