Changeset View
Changeset View
Standalone View
Standalone View
src/cashaddr.cpp
- This file was added.
// Copyright (c) 2017 Pieter Wuille | |||||
// Copyright (c) 2017 The Bitcoin developers | |||||
// Distributed under the MIT software license, see the accompanying | |||||
// file COPYING or http://www.opensource.org/licenses/mit-license.php. | |||||
#include "cashaddr.h" | |||||
namespace { | |||||
typedef std::vector<uint8_t> data; | |||||
/** | |||||
* The cashaddr character set for encoding. | |||||
*/ | |||||
const char *CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"; | |||||
/** | |||||
* The cashaddr 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}; | |||||
/** | |||||
* 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 8 5-bit values to XOR into the last 8 input | |||||
* values, in order to make the checksum 0. These 8 values are packed together | |||||
* in a single 40-bit integer. The higher bits correspond to earlier values. | |||||
*/ | |||||
uint64_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 40-bit integer whose 5-bit groups are the coefficients of | |||||
* the remainder of v(x) mod g(x), where g(x) is the cashaddr generator, x^8 | |||||
* + {19}*x^7 + {3}*x^6 + {25}*x^5 + {11}*x^4 + {25}*x^3 + {3}*x^2 + {19}*x | |||||
* + {1}. g(x) is chosen in such a way that the resulting code is a BCH | |||||
* code, guaranteeing detection of up to 4 errors within a window of 1025 | |||||
* characters. Among the various possible BCH codes, one was selected to in | |||||
* fact guarantee detection of up to 5 errors within a window of 160 | |||||
* characters and 6 erros within a window of 126 characters. In addition, | |||||
* the code guarantee the detection of a burst of up to 8 errors. | |||||
* | |||||
* 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`. | |||||
*/ | |||||
uint64_t c = 1; | |||||
for (uint8_t d : 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 + d) mod g(x), where d is the next input to | |||||
* process. | |||||
* | |||||
* Simplifying: | |||||
* c'(x) = (f(x) * x + d) mod g(x) | |||||
* ((f(x) mod g(x)) * x + d) mod g(x) | |||||
* (c(x) * x + d) 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 + d | |||||
* mod g(x) | |||||
* = c0*x^6 + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + d | |||||
* mod g(x) | |||||
* = c0*(x^6 mod g(x)) + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + | |||||
* c5*x + d | |||||
* 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 + d) + c0*k(x) | |||||
*/ | |||||
// First, determine the value of c0: | |||||
uint8_t c0 = c >> 35; | |||||
// Then compute c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + d: | |||||
c = ((c & 0x07ffffffff) << 5) ^ d; | |||||
// Finally, for each set bit n in c0, conditionally add {2^n}k(x): | |||||
if (c0 & 0x01) { | |||||
// k(x) = {19}*x^7 + {3}*x^6 + {25}*x^5 + {11}*x^4 + {25}*x^3 + | |||||
// {3}*x^2 + {19}*x + {1} | |||||
c ^= 0x98f2bc8e61; | |||||
} | |||||
if (c0 & 0x02) { | |||||
// {2}k(x) = {15}*x^7 + {6}*x^6 + {27}*x^5 + {22}*x^4 + {27}*x^3 + | |||||
// {6}*x^2 + {15}*x + {2} | |||||
c ^= 0x79b76d99e2; | |||||
} | |||||
if (c0 & 0x04) { | |||||
// {4}k(x) = {30}*x^7 + {12}*x^6 + {31}*x^5 + {5}*x^4 + {31}*x^3 + | |||||
// {12}*x^2 + {30}*x + {4} | |||||
c ^= 0xf33e5fb3c4; | |||||
} | |||||
if (c0 & 0x08) { | |||||
// {8}k(x) = {21}*x^7 + {24}*x^6 + {23}*x^5 + {10}*x^4 + {23}*x^3 + | |||||
// {24}*x^2 + {21}*x + {8} | |||||
c ^= 0xae2eabe2a8; | |||||
} | |||||
if (c0 & 0x10) { | |||||
// {16}k(x) = {3}*x^7 + {25}*x^6 + {7}*x^5 + {20}*x^4 + {7}*x^3 + | |||||
// {25}*x^2 + {3}*x + {16} | |||||
c ^= 0x1e4f43e470; | |||||
} | |||||
} | |||||
return c; | |||||
} | |||||
/** | |||||
* Convert to lower case. | |||||
* | |||||
* Assume the input is a character. | |||||
*/ | |||||
inline uint8_t LowerCase(uint8_t c) { | |||||
// ASCII black magic. | |||||
return c | 0x20; | |||||
} | |||||
/** | |||||
* Expand the address prefix for the checksum computation. | |||||
*/ | |||||
data ExpandPrefix(const std::string &prefix) { | |||||
data ret; | |||||
ret.resize(prefix.size() + 1); | |||||
for (size_t i = 0; i < prefix.size(); ++i) { | |||||
ret[i] = prefix[i] & 0x1f; | |||||
} | |||||
ret[prefix.size()] = 0; | |||||
return ret; | |||||
} | |||||
/** | |||||
* Verify a checksum. | |||||
*/ | |||||
bool VerifyChecksum(const std::string &prefix, 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, cashaddr requires the resulting checksum | |||||
* to be 1 instead. | |||||
*/ | |||||
return PolyMod(Cat(ExpandPrefix(prefix), values)) == 1; | |||||
} | |||||
/** | |||||
* Create a checksum. | |||||
*/ | |||||
data CreateChecksum(const std::string &prefix, const data &values) { | |||||
data enc = Cat(ExpandPrefix(prefix), values); | |||||
// Append 8 zeroes. | |||||
enc.resize(enc.size() + 8); | |||||
// Determine what to XOR into those 8 zeroes. | |||||
uint64_t mod = PolyMod(enc) ^ 1; | |||||
data ret(8); | |||||
for (size_t i = 0; i < 8; ++i) { | |||||
// Convert the 5-bit groups in mod to checksum values. | |||||
ret[i] = (mod >> (5 * (7 - i))) & 0x1f; | |||||
} | |||||
return ret; | |||||
} | |||||
} // namespace | |||||
namespace cashaddr { | |||||
/** | |||||
* Encode a cashaddr string. | |||||
*/ | |||||
std::string Encode(const std::string &prefix, const data &values) { | |||||
data checksum = CreateChecksum(prefix, values); | |||||
data combined = Cat(values, checksum); | |||||
std::string ret = prefix + ':'; | |||||
ret.reserve(ret.size() + combined.size()); | |||||
for (uint8_t c : combined) { | |||||
ret += CHARSET[c]; | |||||
} | |||||
return ret; | |||||
} | |||||
/** | |||||
* Decode a cashaddr string. | |||||
*/ | |||||
std::pair<std::string, data> Decode(const std::string &str) { | |||||
// Go over the string and do some sanity checks. | |||||
bool lower = false, upper = false; | |||||
size_t prefixSize = 0; | |||||
for (size_t i = 0; i < str.size(); ++i) { | |||||
uint8_t c = str[i]; | |||||
if (c >= 'a' && c <= 'z') { | |||||
lower = true; | |||||
continue; | |||||
} | |||||
if (c >= 'A' && c <= 'Z') { | |||||
upper = true; | |||||
continue; | |||||
} | |||||
if (c >= '0' && c <= '9') { | |||||
// We cannot have numbers in the prefix. | |||||
if (prefixSize == 0) { | |||||
return {}; | |||||
} | |||||
continue; | |||||
} | |||||
if (c == ':') { | |||||
// The separator must not be the first character, and there must not | |||||
// be 2 separators. | |||||
if (i == 0 || prefixSize != 0) { | |||||
return {}; | |||||
} | |||||
prefixSize = i; | |||||
continue; | |||||
} | |||||
// We have an unexpected character. | |||||
return {}; | |||||
} | |||||
// We must have a prefix and a data part and we can't have both uppercase | |||||
// and lowercase. | |||||
if ((prefixSize == 0) || (upper && lower)) { | |||||
return {}; | |||||
} | |||||
// Get the prefix. | |||||
std::string prefix; | |||||
prefix.reserve(prefixSize); | |||||
for (size_t i = 0; i < prefixSize; ++i) { | |||||
prefix += LowerCase(str[i]); | |||||
} | |||||
// Decode values. | |||||
const size_t valuesSize = str.size() - 1 - prefixSize; | |||||
data values(valuesSize); | |||||
for (size_t i = 0; i < valuesSize; ++i) { | |||||
uint8_t c = str[i + prefixSize + 1]; | |||||
// We have an invalid char in there. | |||||
if (c > 127 || CHARSET_REV[c] == -1) { | |||||
return {}; | |||||
} | |||||
values[i] = CHARSET_REV[c]; | |||||
} | |||||
// Verify the checksum. | |||||
if (!VerifyChecksum(prefix, values)) { | |||||
return {}; | |||||
} | |||||
return {prefix, data(values.begin(), values.end() - 8)}; | |||||
} | |||||
} // namespace cashaddr |