bitcoin/src/bech32.cpp at master · Dash-OS/bitcoin · GitHub

History

191 lines (169 loc) · 7.82 KB

Raw

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

// Distributed under the MIT software license, see the accompanying

// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <bech32.h>

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,

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

};

/** Concatenate two byte arrays. */

data Cat(data x, const data& y)

{

x.insert(x.end(), y.begin(), y.end());

return x;

}

/** 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 (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 (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. */

bool 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.

return PolyMod(Cat(ExpandHRP(hrp), values)) == 1;

}

/** Create a checksum. */

data CreateChecksum(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) ^ 1; // 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

namespace bech32

{

/** Encode a Bech32 string. */

std::string Encode(const std::string& hrp, const data& values) {

data checksum = CreateChecksum(hrp, values);

data combined = Cat(values, checksum);

std::string ret = hrp + '1';

ret.reserve(ret.size() + combined.size());

for (auto c : combined) {

ret += CHARSET[c];

}

return ret;

}

/** Decode a Bech32 string. */

std::pair<std::string, data> 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 < 33 || c > 126) return {};

if (c >= 'a' && c <= 'z') lower = true;

if (c >= 'A' && c <= 'Z') upper = true;

}

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 = (c < 33 || c > 126) ? -1 : 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]);

}

if (!VerifyChecksum(hrp, values)) {

return {};

}

return {hrp, data(values.begin(), values.end() - 6)};

}

} // namespace bech32

bitcoin/src/bech32.cpp at master · Dash-OS/bitcoin · GitHub

Uh oh!

Expand file tree

Breadcrumbs

bech32.cpp

Latest commit

History

Breadcrumbs

bech32.cpp

File metadata and controls