bech32.gno
10.57 Kb · 360 lines
1// Package bech32 implements the Bech32 and Bech32m string formats of BIP-173
2// and BIP-350 as a pure, reusable package.
3//
4// A Bech32 string is a human-readable part ("g", "bc", "cosmos"), the separator
5// '1', and a data part written in a 32-character alphabet that ends in a 6-character
6// BCH checksum. The checksum is the point: it detects every error of up to four
7// characters, and locates a single wrong character well enough for a wallet to say
8// which one it is. That is why a gno.land address, a Bitcoin segwit address and a
9// Cosmos account address all look the way they do.
10//
11// Two variants, differing only in the constant the checksum is xored with:
12//
13// - [Bech32] (constant 1), BIP-173. What gno.land addresses use.
14// - [Bech32m] (constant 0x2bc830a3), BIP-350. Adopted after a length-extension
15// weakness was found in the original: a Bech32 string ending in 'p' keeps its
16// checksum valid when 'q' characters are inserted before that final 'p'.
17//
18// [Decode] accepts either and reports which one it read, so a caller that cares
19// (segwit v1 and later must be Bech32m) can check rather than assume.
20//
21// The data part is a sequence of 5-bit groups. [ConvertBits] regroups an ordinary
22// 8-bit payload into those groups and back, and [EncodeBytes] / [DecodeBytes] are
23// the two wrapped together for the common case:
24//
25// hrp, payload, _, err := bech32.DecodeBytes("g1manfred47kzduec920z88wfr64ylksmdcedlf5")
26// // hrp == "g", payload is the 20-byte address
27//
28// A live demo of this package is at
29// [r/moul/x/daily/bech32demo](/r/moul/x/daily/bech32demo/v0).
30package bech32
31
32import "errors"
33
34// Variant distinguishes the two checksum constants.
35type Variant int
36
37// The two variants.
38const (
39 // Bech32 is BIP-173, checksum constant 1.
40 Bech32 Variant = iota
41 // Bech32m is BIP-350, checksum constant 0x2bc830a3.
42 Bech32m
43)
44
45// String names the variant, "bech32" or "bech32m".
46func (v Variant) String() string {
47 switch v {
48 case Bech32:
49 return "bech32"
50 case Bech32m:
51 return "bech32m"
52 }
53 return "invalid"
54}
55
56func (v Variant) constant() uint32 {
57 if v == Bech32m {
58 return 0x2bc830a3
59 }
60 return 1
61}
62
63var (
64 // ErrTooLong is returned when a string exceeds MaxLen.
65 ErrTooLong = errors.New("bech32: string too long")
66 // ErrTooShort is returned when a string is shorter than the minimum.
67 ErrTooShort = errors.New("bech32: string too short")
68 // ErrMixedCase is returned when a string mixes upper and lower case.
69 ErrMixedCase = errors.New("bech32: mixed case")
70 // ErrNoSeparator is returned when the '1' separator is missing.
71 ErrNoSeparator = errors.New("bech32: no separator")
72 // ErrInvalidHRP is returned for an out-of-range human-readable part.
73 ErrInvalidHRP = errors.New("bech32: invalid human-readable part")
74 // ErrInvalidChar is returned when the data part holds a non-charset byte.
75 ErrInvalidChar = errors.New("bech32: invalid data character")
76 // ErrInvalidData is returned when a group does not fit its bit width.
77 ErrInvalidData = errors.New("bech32: invalid data value")
78 // ErrChecksum is returned when the trailing checksum does not verify.
79 ErrChecksum = errors.New("bech32: bad checksum")
80 // ErrInvalidBits is returned for an unsupported ConvertBits width.
81 ErrInvalidBits = errors.New("bech32: invalid bit width")
82 // ErrInvalidPadding is returned when unpadded conversion leaves bits over.
83 ErrInvalidPadding = errors.New("bech32: invalid padding")
84 // ErrInvalidVariant is returned for a Variant that is neither constant.
85 ErrInvalidVariant = errors.New("bech32: invalid variant")
86)
87
88
89// MaxLen is BIP-173's cap on the whole encoded string, separator and checksum
90// included. It exists so that a wrong character can always be located, and it is
91// what keeps a decode bounded in gas.
92const MaxLen = 90
93
94// ChecksumLen is the number of data characters the checksum occupies.
95const ChecksumLen = 6
96
97// Charset is the 32-character data alphabet. It omits '1', 'b', 'i' and 'o',
98// the four that are easiest to misread.
99const Charset = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"
100
101// Encode builds a Bech32 string from a human-readable part and 5-bit groups.
102func Encode(hrp string, data []byte) (string, error) {
103 return EncodeVariant(hrp, data, Bech32)
104}
105
106// EncodeVariant is [Encode] with an explicit checksum variant.
107//
108// hrp is lowercased; every data byte must be below 32. The result is always
109// lowercase, which is the form BIP-173 requires anything machine-generated to use.
110func EncodeVariant(hrp string, data []byte, v Variant) (string, error) {
111 if v != Bech32 && v != Bech32m {
112 return "", ErrInvalidVariant
113 }
114 hrp = toLower(hrp)
115 if err := checkHRP(hrp); err != nil {
116 return "", err
117 }
118 for _, d := range data {
119 if d >= 32 {
120 return "", ErrInvalidData
121 }
122 }
123 if len(hrp)+1+len(data)+ChecksumLen > MaxLen {
124 return "", ErrTooLong
125 }
126
127 out := make([]byte, 0, len(hrp)+1+len(data)+ChecksumLen)
128 out = append(out, hrp...)
129 out = append(out, '1')
130 for _, d := range data {
131 out = append(out, Charset[d])
132 }
133 for _, d := range checksum(hrp, data, v) {
134 out = append(out, Charset[d])
135 }
136 return string(out), nil
137}
138
139// Decode parses a Bech32 or Bech32m string into its human-readable part, its
140// 5-bit data groups (checksum removed) and the variant whose checksum verified.
141//
142// The input may be all upper or all lower case, never a mix; the returned
143// human-readable part is lowercase.
144func Decode(s string) (string, []byte, Variant, error) {
145 if len(s) > MaxLen {
146 return "", nil, Bech32, ErrTooLong
147 }
148 hasUpper, hasLower := false, false
149 for i := 0; i < len(s); i++ {
150 c := s[i]
151 if c < 33 || c > 126 {
152 return "", nil, Bech32, ErrInvalidChar
153 }
154 if c >= 'A' && c <= 'Z' {
155 hasUpper = true
156 }
157 if c >= 'a' && c <= 'z' {
158 hasLower = true
159 }
160 }
161 if hasUpper && hasLower {
162 return "", nil, Bech32, ErrMixedCase
163 }
164 s = toLower(s)
165
166 sep := lastIndexByte(s, '1')
167 if sep < 0 {
168 return "", nil, Bech32, ErrNoSeparator
169 }
170 hrp := s[:sep]
171 if err := checkHRP(hrp); err != nil {
172 return "", nil, Bech32, err
173 }
174 part := s[sep+1:]
175 if len(part) < ChecksumLen {
176 return "", nil, Bech32, ErrTooShort
177 }
178
179 data := make([]byte, 0, len(part))
180 for i := 0; i < len(part); i++ {
181 idx := indexByte(Charset, part[i])
182 if idx < 0 {
183 return "", nil, Bech32, ErrInvalidChar
184 }
185 data = append(data, byte(idx))
186 }
187
188 v := Bech32
189 got := polymod(append(hrpExpand(hrp), data...))
190 if got != v.constant() {
191 v = Bech32m
192 if got != v.constant() {
193 return "", nil, Bech32, ErrChecksum
194 }
195 }
196 return hrp, data[:len(data)-ChecksumLen], v, nil
197}
198
199// ConvertBits regroups data from one bit width to another, most significant bit
200// first. Going 8 to 5 needs pad set, since the last group is rarely full; coming
201// back 5 to 8 must not pad, so that leftover bits are reported rather than turned
202// into a trailing zero byte.
203func ConvertBits(data []byte, from, to uint8, pad bool) ([]byte, error) {
204 if from < 1 || from > 8 || to < 1 || to > 8 {
205 return nil, ErrInvalidBits
206 }
207 maxv := uint32(1)<<to - 1
208 acc := uint32(0)
209 bits := uint8(0)
210 out := make([]byte, 0, len(data)*int(from)/int(to)+1)
211 for _, b := range data {
212 if from < 8 && uint32(b) >= uint32(1)<<from {
213 return nil, ErrInvalidData
214 }
215 acc = acc<<from | uint32(b)
216 bits += from
217 for bits >= to {
218 bits -= to
219 out = append(out, byte(acc>>bits&maxv))
220 }
221 }
222 if pad {
223 if bits > 0 {
224 out = append(out, byte(acc<<(to-bits)&maxv))
225 }
226 return out, nil
227 }
228 if bits >= from || acc<<(to-bits)&maxv != 0 {
229 return nil, ErrInvalidPadding
230 }
231 return out, nil
232}
233
234// EncodeBytes encodes an 8-bit payload as Bech32, converting to 5-bit groups
235// first. This is the call an address wants.
236func EncodeBytes(hrp string, payload []byte) (string, error) {
237 if err := checkHRP(toLower(hrp)); err != nil {
238 return "", err
239 }
240 // Refuse before regrouping, not after: ConvertBits would otherwise scan and
241 // materialise a payload of any size only for Encode to reject the result.
242 if len(payload) > MaxPayloadLen(hrp) {
243 return "", ErrTooLong
244 }
245 data, err := ConvertBits(payload, 8, 5, true)
246 if err != nil {
247 return "", err
248 }
249 return Encode(hrp, data)
250}
251
252// DecodeBytes decodes a string and converts its data part back to 8-bit bytes.
253func DecodeBytes(s string) (string, []byte, Variant, error) {
254 hrp, data, v, err := Decode(s)
255 if err != nil {
256 return "", nil, Bech32, err
257 }
258 payload, err := ConvertBits(data, 5, 8, false)
259 if err != nil {
260 return "", nil, Bech32, err
261 }
262 return hrp, payload, v, nil
263}
264
265// MaxPayloadLen is the largest 8-bit payload [EncodeBytes] can fit under hrp
266// without passing MaxLen. It is 51 bytes for a gno.land address, whose
267// human-readable part is one character, and 0 when hrp leaves no room at all.
268func MaxPayloadLen(hrp string) int {
269 groups := MaxLen - len(hrp) - 1 - ChecksumLen
270 if groups <= 0 {
271 return 0
272 }
273 // A payload of b bytes needs ceil(8b/5) groups, so b groups fit exactly
274 // while 8b <= 5*groups.
275 return groups * 5 / 8
276}
277
278// checksum returns the six 5-bit groups that terminate the data part.
279func checksum(hrp string, data []byte, v Variant) []byte {
280 values := append(hrpExpand(hrp), data...)
281 values = append(values, 0, 0, 0, 0, 0, 0)
282 mod := polymod(values) ^ v.constant()
283 out := make([]byte, ChecksumLen)
284 for i := 0; i < ChecksumLen; i++ {
285 out[i] = byte(mod>>uint(5*(5-i))) & 31
286 }
287 return out
288}
289
290// polymod is the BCH code of BIP-173 over GF(32).
291func polymod(values []byte) uint32 {
292 gen := [5]uint32{0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3}
293 chk := uint32(1)
294 for _, v := range values {
295 top := chk >> 25
296 chk = (chk&0x1ffffff)<<5 ^ uint32(v)
297 for i := 0; i < 5; i++ {
298 if (top>>uint(i))&1 == 1 {
299 chk ^= gen[i]
300 }
301 }
302 }
303 return chk
304}
305
306// hrpExpand spreads the human-readable part into the 5-bit groups the checksum
307// is computed over: every high 3 bits, a zero, then every low 5 bits.
308func hrpExpand(hrp string) []byte {
309 out := make([]byte, 0, len(hrp)*2+1)
310 for i := 0; i < len(hrp); i++ {
311 out = append(out, hrp[i]>>5)
312 }
313 out = append(out, 0)
314 for i := 0; i < len(hrp); i++ {
315 out = append(out, hrp[i]&31)
316 }
317 return out
318}
319
320// checkHRP rejects an empty human-readable part and any byte outside printable
321// US-ASCII, which is what BIP-173 allows there.
322func checkHRP(hrp string) error {
323 if len(hrp) == 0 {
324 return ErrInvalidHRP
325 }
326 for i := 0; i < len(hrp); i++ {
327 if hrp[i] < 33 || hrp[i] > 126 {
328 return ErrInvalidHRP
329 }
330 }
331 return nil
332}
333
334func toLower(s string) string {
335 out := []byte(s)
336 for i := 0; i < len(out); i++ {
337 if out[i] >= 'A' && out[i] <= 'Z' {
338 out[i] += 32
339 }
340 }
341 return string(out)
342}
343
344func indexByte(s string, c byte) int {
345 for i := 0; i < len(s); i++ {
346 if s[i] == c {
347 return i
348 }
349 }
350 return -1
351}
352
353func lastIndexByte(s string, c byte) int {
354 for i := len(s) - 1; i >= 0; i-- {
355 if s[i] == c {
356 return i
357 }
358 }
359 return -1
360}
