common/bech32/bech32.go

   1 package bech32
   2
   3 import (
   4         "fmt"
   5         "strings"
   6 )
   7
   8 const charset = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"
   9
  10 var gen = []int{0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3}
  11
  12 // Decode decodes a bech32 encoded string, returning the human-readable
  13 // part and the data part excluding the checksum.
  14 func Bech32Decode(bech string) (string, []byte, error) {
  15         // The maximum allowed length for a bech32 string is 90. It must also
  16         // be at least 8 characters, since it needs a non-empty HRP, a
  17         // separator, and a 6 character checksum.
  18         if len(bech) < 8 || len(bech) > 90 {
  19                 return "", nil, fmt.Errorf("invalid bech32 string length %d",
  20                         len(bech))
  21         }
  22         // Only ASCII characters between 33 and 126 are allowed.
  23         for i := 0; i < len(bech); i++ {
  24                 if bech[i] < 33 || bech[i] > 126 {
  25                         return "", nil, fmt.Errorf("invalid character in "+
  26                                 "string: '%c'", bech[i])
  27                 }
  28         }
  29
  30         // The characters must be either all lowercase or all uppercase.
  31         lower := strings.ToLower(bech)
  32         upper := strings.ToUpper(bech)
  33         if bech != lower && bech != upper {
  34                 return "", nil, fmt.Errorf("string not all lowercase or all " +
  35                         "uppercase")
  36         }
  37
  38         // We'll work with the lowercase string from now on.
  39         bech = lower
  40
  41         // The string is invalid if the last '1' is non-existent, it is the
  42         // first character of the string (no human-readable part) or one of the
  43         // last 6 characters of the string (since checksum cannot contain '1'),
  44         // or if the string is more than 90 characters in total.
  45         one := strings.LastIndexByte(bech, '1')
  46         if one < 1 || one+7 > len(bech) {
  47                 return "", nil, fmt.Errorf("invalid index of 1")
  48         }
  49
  50         // The human-readable part is everything before the last '1'.
  51         hrp := bech[:one]
  52         data := bech[one+1:]
  53
  54         // Each character corresponds to the byte with value of the index in
  55         // 'charset'.
  56         decoded, err := toBytes(data)
  57         if err != nil {
  58                 return "", nil, fmt.Errorf("failed converting data to bytes: "+
  59                         "%v", err)
  60         }
  61
  62         if !bech32VerifyChecksum(hrp, decoded) {
  63                 moreInfo := ""
  64                 checksum := bech[len(bech)-6:]
  65                 expected, err := toChars(bech32Checksum(hrp,
  66                         decoded[:len(decoded)-6]))
  67                 if err == nil {
  68                         moreInfo = fmt.Sprintf("Expected %v, got %v.",
  69                                 expected, checksum)
  70                 }
  71                 return "", nil, fmt.Errorf("checksum failed. " + moreInfo)
  72         }
  73
  74         // We exclude the last 6 bytes, which is the checksum.
  75         return hrp, decoded[:len(decoded)-6], nil
  76 }
  77
  78 // Encode encodes a byte slice into a bech32 string with the
  79 // human-readable part hrb. Note that the bytes must each encode 5 bits
  80 // (base32).
  81 func Bech32Encode(hrp string, data []byte) (string, error) {
  82         // Calculate the checksum of the data and append it at the end.
  83         checksum := bech32Checksum(hrp, data)
  84         combined := append(data, checksum...)
  85
  86         // The resulting bech32 string is the concatenation of the hrp, the
  87         // separator 1, data and checksum. Everything after the separator is
  88         // represented using the specified charset.
  89         dataChars, err := toChars(combined)
  90         if err != nil {
  91                 return "", fmt.Errorf("unable to convert data bytes to chars: "+
  92                         "%v", err)
  93         }
  94         return hrp + "1" + dataChars, nil
  95 }
  96
  97 // toBytes converts each character in the string 'chars' to the value of the
  98 // index of the correspoding character in 'charset'.
  99 func toBytes(chars string) ([]byte, error) {
 100         decoded := make([]byte, 0, len(chars))
 101         for i := 0; i < len(chars); i++ {
 102                 index := strings.IndexByte(charset, chars[i])
 103                 if index < 0 {
 104                         return nil, fmt.Errorf("invalid character not part of "+
 105                                 "charset: %v", chars[i])
 106                 }
 107                 decoded = append(decoded, byte(index))
 108         }
 109         return decoded, nil
 110 }
 111
 112 // toChars converts the byte slice 'data' to a string where each byte in 'data'
 113 // encodes the index of a character in 'charset'.
 114 func toChars(data []byte) (string, error) {
 115         result := make([]byte, 0, len(data))
 116         for _, b := range data {
 117                 if int(b) >= len(charset) {
 118                         return "", fmt.Errorf("invalid data byte: %v", b)
 119                 }
 120                 result = append(result, charset[b])
 121         }
 122         return string(result), nil
 123 }
 124
 125 // ConvertBits converts a byte slice where each byte is encoding fromBits bits,
 126 // to a byte slice where each byte is encoding toBits bits.
 127 func ConvertBits(data []byte, fromBits, toBits uint8, pad bool) ([]byte, error) {
 128         if fromBits < 1 || fromBits > 8 || toBits < 1 || toBits > 8 {
 129                 return nil, fmt.Errorf("only bit groups between 1 and 8 allowed")
 130         }
 131
 132         // The final bytes, each byte encoding toBits bits.
 133         var regrouped []byte
 134
 135         // Keep track of the next byte we create and how many bits we have
 136         // added to it out of the toBits goal.
 137         nextByte := byte(0)
 138         filledBits := uint8(0)
 139
 140         for _, b := range data {
 141
 142                 // Discard unused bits.
 143                 b = b << (8 - fromBits)
 144
 145                 // How many bits remaining to extract from the input data.
 146                 remFromBits := fromBits
 147                 for remFromBits > 0 {
 148                         // How many bits remaining to be added to the next byte.
 149                         remToBits := toBits - filledBits
 150
 151                         // The number of bytes to next extract is the minimum of
 152                         // remFromBits and remToBits.
 153                         toExtract := remFromBits
 154                         if remToBits < toExtract {
 155                                 toExtract = remToBits
 156                         }
 157
 158                         // Add the next bits to nextByte, shifting the already
 159                         // added bits to the left.
 160                         nextByte = (nextByte << toExtract) | (b >> (8 - toExtract))
 161
 162                         // Discard the bits we just extracted and get ready for
 163                         // next iteration.
 164                         b = b << toExtract
 165                         remFromBits -= toExtract
 166                         filledBits += toExtract
 167
 168                         // If the nextByte is completely filled, we add it to
 169                         // our regrouped bytes and start on the next byte.
 170                         if filledBits == toBits {
 171                                 regrouped = append(regrouped, nextByte)
 172                                 filledBits = 0
 173                                 nextByte = 0
 174                         }
 175                 }
 176         }
 177
 178         // We pad any unfinished group if specified.
 179         if pad && filledBits > 0 {
 180                 nextByte = nextByte << (toBits - filledBits)
 181                 regrouped = append(regrouped, nextByte)
 182                 filledBits = 0
 183                 nextByte = 0
 184         }
 185
 186         // Any incomplete group must be <= 4 bits, and all zeroes.
 187         if filledBits > 0 && (filledBits > 4 || nextByte != 0) {
 188                 return nil, fmt.Errorf("invalid incomplete group")
 189         }
 190
 191         return regrouped, nil
 192 }
 193
 194 // For more details on the checksum calculation, please refer to BIP 173.
 195 func bech32Checksum(hrp string, data []byte) []byte {
 196         // Convert the bytes to list of integers, as this is needed for the
 197         // checksum calculation.
 198         integers := make([]int, len(data))
 199         for i, b := range data {
 200                 integers[i] = int(b)
 201         }
 202         values := append(bech32HrpExpand(hrp), integers...)
 203         values = append(values, []int{0, 0, 0, 0, 0, 0}...)
 204         polymod := bech32Polymod(values) ^ 1
 205         var res []byte
 206         for i := 0; i < 6; i++ {
 207                 res = append(res, byte((polymod>>uint(5*(5-i)))&31))
 208         }
 209         return res
 210 }
 211
 212 // For more details on the polymod calculation, please refer to BIP 173.
 213 func bech32Polymod(values []int) int {
 214         chk := 1
 215         for _, v := range values {
 216                 b := chk >> 25
 217                 chk = (chk&0x1ffffff)<<5 ^ v
 218                 for i := 0; i < 5; i++ {
 219                         if (b>>uint(i))&1 == 1 {
 220                                 chk ^= gen[i]
 221                         }
 222                 }
 223         }
 224         return chk
 225 }
 226
 227 // For more details on HRP expansion, please refer to BIP 173.
 228 func bech32HrpExpand(hrp string) []int {
 229         v := make([]int, 0, len(hrp)*2+1)
 230         for i := 0; i < len(hrp); i++ {
 231                 v = append(v, int(hrp[i]>>5))
 232         }
 233         v = append(v, 0)
 234         for i := 0; i < len(hrp); i++ {
 235                 v = append(v, int(hrp[i]&31))
 236         }
 237         return v
 238 }
 239
 240 // For more details on the checksum verification, please refer to BIP 173.
 241 func bech32VerifyChecksum(hrp string, data []byte) bool {
 242         integers := make([]int, len(data))
 243         for i, b := range data {
 244                 integers[i] = int(b)
 245         }
 246         concat := append(bech32HrpExpand(hrp), integers...)
 247         return bech32Polymod(concat) == 1
 248 }