1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
// Copyright (c) 2017, 2021 Pieter Wuille
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <bech32.h>
#include <util/vector.h>
#include <assert.h>
namespace bech32
{
namespace
{
typedef std::vector<uint8_t> data;
/** The Bech32 character set for encoding. */
const char* CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
/** The Bech32 character set for decoding. */
const int8_t CHARSET_REV[128] = {
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
15, -1, 10, 17, 21, 20, 26, 30, 7, 5, -1, -1, -1, -1, -1, -1,
-1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22, 31, 27, 19, -1,
1, 0, 3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1, -1,
-1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22, 31, 27, 19, -1,
1, 0, 3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1, -1
};
/* Determine the final constant to use for the specified encoding. */
uint32_t EncodingConstant(Encoding encoding) {
assert(encoding == Encoding::BECH32 || encoding == Encoding::BECH32M);
return encoding == Encoding::BECH32 ? 1 : 0x2bc830a3;
}
/** This function will compute what 6 5-bit values to XOR into the last 6 input values, in order to
* make the checksum 0. These 6 values are packed together in a single 30-bit integer. The higher
* bits correspond to earlier values. */
uint32_t PolyMod(const data& v)
{
// The input is interpreted as a list of coefficients of a polynomial over F = GF(32), with an
// implicit 1 in front. If the input is [v0,v1,v2,v3,v4], that polynomial is v(x) =
// 1*x^5 + v0*x^4 + v1*x^3 + v2*x^2 + v3*x + v4. The implicit 1 guarantees that
// [v0,v1,v2,...] has a distinct checksum from [0,v0,v1,v2,...].
// The output is a 30-bit integer whose 5-bit groups are the coefficients of the remainder of
// v(x) mod g(x), where g(x) is the Bech32 generator,
// x^6 + {29}x^5 + {22}x^4 + {20}x^3 + {21}x^2 + {29}x + {18}. g(x) is chosen in such a way
// that the resulting code is a BCH code, guaranteeing detection of up to 3 errors within a
// window of 1023 characters. Among the various possible BCH codes, one was selected to in
// fact guarantee detection of up to 4 errors within a window of 89 characters.
// Note that the coefficients are elements of GF(32), here represented as decimal numbers
// between {}. In this finite field, addition is just XOR of the corresponding numbers. For
// example, {27} + {13} = {27 ^ 13} = {22}. Multiplication is more complicated, and requires
// treating the bits of values themselves as coefficients of a polynomial over a smaller field,
// GF(2), and multiplying those polynomials mod a^5 + a^3 + 1. For example, {5} * {26} =
// (a^2 + 1) * (a^4 + a^3 + a) = (a^4 + a^3 + a) * a^2 + (a^4 + a^3 + a) = a^6 + a^5 + a^4 + a
// = a^3 + 1 (mod a^5 + a^3 + 1) = {9}.
// During the course of the loop below, `c` contains the bitpacked coefficients of the
// polynomial constructed from just the values of v that were processed so far, mod g(x). In
// the above example, `c` initially corresponds to 1 mod g(x), and after processing 2 inputs of
// v, it corresponds to x^2 + v0*x + v1 mod g(x). As 1 mod g(x) = 1, that is the starting value
// for `c`.
uint32_t c = 1;
for (const auto v_i : v) {
// We want to update `c` to correspond to a polynomial with one extra term. If the initial
// value of `c` consists of the coefficients of c(x) = f(x) mod g(x), we modify it to
// correspond to c'(x) = (f(x) * x + v_i) mod g(x), where v_i is the next input to
// process. Simplifying:
// c'(x) = (f(x) * x + v_i) mod g(x)
// ((f(x) mod g(x)) * x + v_i) mod g(x)
// (c(x) * x + v_i) mod g(x)
// If c(x) = c0*x^5 + c1*x^4 + c2*x^3 + c3*x^2 + c4*x + c5, we want to compute
// c'(x) = (c0*x^5 + c1*x^4 + c2*x^3 + c3*x^2 + c4*x + c5) * x + v_i mod g(x)
// = c0*x^6 + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + v_i mod g(x)
// = c0*(x^6 mod g(x)) + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + v_i
// If we call (x^6 mod g(x)) = k(x), this can be written as
// c'(x) = (c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + v_i) + c0*k(x)
// First, determine the value of c0:
uint8_t c0 = c >> 25;
// Then compute c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + v_i:
c = ((c & 0x1ffffff) << 5) ^ v_i;
// Finally, for each set bit n in c0, conditionally add {2^n}k(x):
if (c0 & 1) c ^= 0x3b6a57b2; // k(x) = {29}x^5 + {22}x^4 + {20}x^3 + {21}x^2 + {29}x + {18}
if (c0 & 2) c ^= 0x26508e6d; // {2}k(x) = {19}x^5 + {5}x^4 + x^3 + {3}x^2 + {19}x + {13}
if (c0 & 4) c ^= 0x1ea119fa; // {4}k(x) = {15}x^5 + {10}x^4 + {2}x^3 + {6}x^2 + {15}x + {26}
if (c0 & 8) c ^= 0x3d4233dd; // {8}k(x) = {30}x^5 + {20}x^4 + {4}x^3 + {12}x^2 + {30}x + {29}
if (c0 & 16) c ^= 0x2a1462b3; // {16}k(x) = {21}x^5 + x^4 + {8}x^3 + {24}x^2 + {21}x + {19}
}
return c;
}
/** Convert to lower case. */
inline unsigned char LowerCase(unsigned char c)
{
return (c >= 'A' && c <= 'Z') ? (c - 'A') + 'a' : c;
}
/** Expand a HRP for use in checksum computation. */
data ExpandHRP(const std::string& hrp)
{
data ret;
ret.reserve(hrp.size() + 90);
ret.resize(hrp.size() * 2 + 1);
for (size_t i = 0; i < hrp.size(); ++i) {
unsigned char c = hrp[i];
ret[i] = c >> 5;
ret[i + hrp.size() + 1] = c & 0x1f;
}
ret[hrp.size()] = 0;
return ret;
}
/** Verify a checksum. */
Encoding VerifyChecksum(const std::string& hrp, const data& values)
{
// PolyMod computes what value to xor into the final values to make the checksum 0. However,
// if we required that the checksum was 0, it would be the case that appending a 0 to a valid
// list of values would result in a new valid list. For that reason, Bech32 requires the
// resulting checksum to be 1 instead. In Bech32m, this constant was amended.
const uint32_t check = PolyMod(Cat(ExpandHRP(hrp), values));
if (check == EncodingConstant(Encoding::BECH32)) return Encoding::BECH32;
if (check == EncodingConstant(Encoding::BECH32M)) return Encoding::BECH32M;
return Encoding::INVALID;
}
/** Create a checksum. */
data CreateChecksum(Encoding encoding, const std::string& hrp, const data& values)
{
data enc = Cat(ExpandHRP(hrp), values);
enc.resize(enc.size() + 6); // Append 6 zeroes
uint32_t mod = PolyMod(enc) ^ EncodingConstant(encoding); // Determine what to XOR into those 6 zeroes.
data ret(6);
for (size_t i = 0; i < 6; ++i) {
// Convert the 5-bit groups in mod to checksum values.
ret[i] = (mod >> (5 * (5 - i))) & 31;
}
return ret;
}
} // namespace
/** Encode a Bech32 or Bech32m string. */
std::string Encode(Encoding encoding, const std::string& hrp, const data& values) {
// First ensure that the HRP is all lowercase. BIP-173 requires an encoder
// to return a lowercase Bech32 string, but if given an uppercase HRP, the
// result will always be invalid.
for (const char& c : hrp) assert(c < 'A' || c > 'Z');
data checksum = CreateChecksum(encoding, hrp, values);
data combined = Cat(values, checksum);
std::string ret = hrp + '1';
ret.reserve(ret.size() + combined.size());
for (const auto c : combined) {
ret += CHARSET[c];
}
return ret;
}
/** Decode a Bech32 or Bech32m string. */
DecodeResult Decode(const std::string& str) {
bool lower = false, upper = false;
for (size_t i = 0; i < str.size(); ++i) {
unsigned char c = str[i];
if (c >= 'a' && c <= 'z') lower = true;
else if (c >= 'A' && c <= 'Z') upper = true;
else if (c < 33 || c > 126) return {};
}
if (lower && upper) return {};
size_t pos = str.rfind('1');
if (str.size() > 90 || pos == str.npos || pos == 0 || pos + 7 > str.size()) {
return {};
}
data values(str.size() - 1 - pos);
for (size_t i = 0; i < str.size() - 1 - pos; ++i) {
unsigned char c = str[i + pos + 1];
int8_t rev = CHARSET_REV[c];
if (rev == -1) {
return {};
}
values[i] = rev;
}
std::string hrp;
for (size_t i = 0; i < pos; ++i) {
hrp += LowerCase(str[i]);
}
Encoding result = VerifyChecksum(hrp, values);
if (result == Encoding::INVALID) return {};
return {result, std::move(hrp), data(values.begin(), values.end() - 6)};
}
} // namespace bech32
|
