From 1485533092a0732bae55313659a3e3f9669fd77a Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 5 Jan 2021 12:55:15 -0800 Subject: Implement Bech32m encoding/decoding Github-Pull: #20861 Rebased-From: da2bb6976dadeec682d163c258c9afecc87d6428 --- src/bech32.cpp | 44 ++++++++++++++++++++++++++------------------ src/bech32.h | 30 ++++++++++++++++++++++++------ src/bench/bech32.cpp | 2 +- src/key_io.cpp | 16 ++++++++-------- src/test/bech32_tests.cpp | 10 +++++----- src/test/fuzz/bech32.cpp | 32 ++++++++++++++++---------------- 6 files changed, 80 insertions(+), 54 deletions(-) (limited to 'src') diff --git a/src/bech32.cpp b/src/bech32.cpp index 1e0471f110..289e0213e8 100644 --- a/src/bech32.cpp +++ b/src/bech32.cpp @@ -1,4 +1,4 @@ -// Copyright (c) 2017 Pieter Wuille +// 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. @@ -7,6 +7,9 @@ #include +namespace bech32 +{ + namespace { @@ -27,6 +30,12 @@ const int8_t CHARSET_REV[128] = { 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. */ @@ -111,21 +120,24 @@ data ExpandHRP(const std::string& hrp) } /** Verify a checksum. */ -bool VerifyChecksum(const std::string& hrp, const data& values) +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. - return PolyMod(Cat(ExpandHRP(hrp), values)) == 1; + // 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(const std::string& hrp, const data& values) +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) ^ 1; // Determine what to XOR into those 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. @@ -136,16 +148,13 @@ data CreateChecksum(const std::string& hrp, const data& values) } // namespace -namespace bech32 -{ - -/** Encode a Bech32 string. */ -std::string Encode(const std::string& hrp, const data& values) { +/** 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(hrp, values); + data checksum = CreateChecksum(encoding, hrp, values); data combined = Cat(values, checksum); std::string ret = hrp + '1'; ret.reserve(ret.size() + combined.size()); @@ -155,8 +164,8 @@ std::string Encode(const std::string& hrp, const data& values) { return ret; } -/** Decode a Bech32 string. */ -std::pair Decode(const std::string& str) { +/** 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]; @@ -183,10 +192,9 @@ std::pair Decode(const std::string& str) { 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)}; + Encoding result = VerifyChecksum(hrp, values); + if (result == Encoding::INVALID) return {}; + return {result, std::move(hrp), data(values.begin(), values.end() - 6)}; } } // namespace bech32 diff --git a/src/bech32.h b/src/bech32.h index fb39cd352b..3679ea8ccb 100644 --- a/src/bech32.h +++ b/src/bech32.h @@ -1,4 +1,4 @@ -// Copyright (c) 2017 Pieter Wuille +// 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. @@ -7,7 +7,7 @@ // separator character (1), and a base32 data section, the last // 6 characters of which are a checksum. // -// For more information, see BIP 173. +// For more information, see BIP 173 and BIP 350. #ifndef BITCOIN_BECH32_H #define BITCOIN_BECH32_H @@ -19,11 +19,29 @@ namespace bech32 { -/** Encode a Bech32 string. If hrp contains uppercase characters, this will cause an assertion error. */ -std::string Encode(const std::string& hrp, const std::vector& values); +enum class Encoding { + INVALID, //!< Failed decoding -/** Decode a Bech32 string. Returns (hrp, data). Empty hrp means failure. */ -std::pair> Decode(const std::string& str); + BECH32, //!< Bech32 encoding as defined in BIP173 + BECH32M, //!< Bech32m encoding as defined in BIP350 +}; + +/** Encode a Bech32 or Bech32m string. If hrp contains uppercase characters, this will cause an + * assertion error. Encoding must be one of BECH32 or BECH32M. */ +std::string Encode(Encoding encoding, const std::string& hrp, const std::vector& values); + +struct DecodeResult +{ + Encoding encoding; //!< What encoding was detected in the result; Encoding::INVALID if failed. + std::string hrp; //!< The human readable part + std::vector data; //!< The payload (excluding checksum) + + DecodeResult() : encoding(Encoding::INVALID) {} + DecodeResult(Encoding enc, std::string&& h, std::vector&& d) : encoding(enc), hrp(std::move(h)), data(std::move(d)) {} +}; + +/** Decode a Bech32 string. */ +DecodeResult Decode(const std::string& str); } // namespace bech32 diff --git a/src/bench/bech32.cpp b/src/bench/bech32.cpp index c74d8d51b3..8e10862a37 100644 --- a/src/bench/bech32.cpp +++ b/src/bench/bech32.cpp @@ -19,7 +19,7 @@ static void Bech32Encode(benchmark::Bench& bench) tmp.reserve(1 + 32 * 8 / 5); ConvertBits<8, 5, true>([&](unsigned char c) { tmp.push_back(c); }, v.begin(), v.end()); bench.batch(v.size()).unit("byte").run([&] { - bech32::Encode("bc", tmp); + bech32::Encode(bech32::Encoding::BECH32, "bc", tmp); }); } diff --git a/src/key_io.cpp b/src/key_io.cpp index d2f5be93f5..f927ebbb42 100644 --- a/src/key_io.cpp +++ b/src/key_io.cpp @@ -44,7 +44,7 @@ public: std::vector data = {0}; data.reserve(33); ConvertBits<8, 5, true>([&](unsigned char c) { data.push_back(c); }, id.begin(), id.end()); - return bech32::Encode(m_params.Bech32HRP(), data); + return bech32::Encode(bech32::Encoding::BECH32, m_params.Bech32HRP(), data); } std::string operator()(const WitnessV0ScriptHash& id) const @@ -52,7 +52,7 @@ public: std::vector data = {0}; data.reserve(53); ConvertBits<8, 5, true>([&](unsigned char c) { data.push_back(c); }, id.begin(), id.end()); - return bech32::Encode(m_params.Bech32HRP(), data); + return bech32::Encode(bech32::Encoding::BECH32, m_params.Bech32HRP(), data); } std::string operator()(const WitnessUnknown& id) const @@ -63,7 +63,7 @@ public: std::vector data = {(unsigned char)id.version}; data.reserve(1 + (id.length * 8 + 4) / 5); ConvertBits<8, 5, true>([&](unsigned char c) { data.push_back(c); }, id.program, id.program + id.length); - return bech32::Encode(m_params.Bech32HRP(), data); + return bech32::Encode(bech32::Encoding::BECH32, m_params.Bech32HRP(), data); } std::string operator()(const CNoDestination& no) const { return {}; } @@ -91,13 +91,13 @@ CTxDestination DecodeDestination(const std::string& str, const CChainParams& par } } data.clear(); - auto bech = bech32::Decode(str); - if (bech.second.size() > 0 && bech.first == params.Bech32HRP()) { + const auto dec = bech32::Decode(str); + if (dec.encoding == bech32::Encoding::BECH32 && dec.data.size() > 0 && dec.hrp == params.Bech32HRP()) { // Bech32 decoding - int version = bech.second[0]; // The first 5 bit symbol is the witness version (0-16) + int version = dec.data[0]; // The first 5 bit symbol is the witness version (0-16) // The rest of the symbols are converted witness program bytes. - data.reserve(((bech.second.size() - 1) * 5) / 8); - if (ConvertBits<5, 8, false>([&](unsigned char c) { data.push_back(c); }, bech.second.begin() + 1, bech.second.end())) { + data.reserve(((dec.data.size() - 1) * 5) / 8); + if (ConvertBits<5, 8, false>([&](unsigned char c) { data.push_back(c); }, dec.data.begin() + 1, dec.data.end())) { if (version == 0) { { WitnessV0KeyHash keyid; diff --git a/src/test/bech32_tests.cpp b/src/test/bech32_tests.cpp index a2098f4f56..2ddc284761 100644 --- a/src/test/bech32_tests.cpp +++ b/src/test/bech32_tests.cpp @@ -22,9 +22,9 @@ BOOST_AUTO_TEST_CASE(bip173_testvectors_valid) "?1ezyfcl", }; for (const std::string& str : CASES) { - auto ret = bech32::Decode(str); - BOOST_CHECK(!ret.first.empty()); - std::string recode = bech32::Encode(ret.first, ret.second); + const auto dec = bech32::Decode(str); + BOOST_CHECK(dec.encoding == bech32::Encoding::BECH32); + std::string recode = bech32::Encode(bech32::Encoding::BECH32, dec.hrp, dec.data); BOOST_CHECK(!recode.empty()); BOOST_CHECK(CaseInsensitiveEqual(str, recode)); } @@ -49,8 +49,8 @@ BOOST_AUTO_TEST_CASE(bip173_testvectors_invalid) "A12uEL5L", }; for (const std::string& str : CASES) { - auto ret = bech32::Decode(str); - BOOST_CHECK(ret.first.empty()); + const auto dec = bech32::Decode(str); + BOOST_CHECK(dec.encoding != bech32::Encoding::BECH32); } } diff --git a/src/test/fuzz/bech32.cpp b/src/test/fuzz/bech32.cpp index 8b91f9bc96..0ac1f02263 100644 --- a/src/test/fuzz/bech32.cpp +++ b/src/test/fuzz/bech32.cpp @@ -16,28 +16,28 @@ void test_one_input(const std::vector& buffer) { const std::string random_string(buffer.begin(), buffer.end()); - const std::pair> r1 = bech32::Decode(random_string); - if (r1.first.empty()) { - assert(r1.second.empty()); + const auto r1 = bech32::Decode(random_string); + if (r1.hrp.empty()) { + assert(r1.encoding == bech32::Encoding::INVALID); + assert(r1.data.empty()); } else { - const std::string& hrp = r1.first; - const std::vector& data = r1.second; - const std::string reencoded = bech32::Encode(hrp, data); + assert(r1.encoding != bech32::Encoding::INVALID); + const std::string reencoded = bech32::Encode(r1.encoding, r1.hrp, r1.data); assert(CaseInsensitiveEqual(random_string, reencoded)); } std::vector input; ConvertBits<8, 5, true>([&](unsigned char c) { input.push_back(c); }, buffer.begin(), buffer.end()); - const std::string encoded = bech32::Encode("bc", input); - assert(!encoded.empty()); - const std::pair> r2 = bech32::Decode(encoded); - if (r2.first.empty()) { - assert(r2.second.empty()); - } else { - const std::string& hrp = r2.first; - const std::vector& data = r2.second; - assert(hrp == "bc"); - assert(data == input); + if (input.size() + 3 + 6 <= 90) { + // If it's possible to encode input in Bech32(m) without exceeding the 90-character limit: + for (auto encoding : {bech32::Encoding::BECH32, bech32::Encoding::BECH32M}) { + const std::string encoded = bech32::Encode(encoding, "bc", input); + assert(!encoded.empty()); + const auto r2 = bech32::Decode(encoded); + assert(r2.encoding == encoding); + assert(r2.hrp == "bc"); + assert(r2.data == input); + } } } -- cgit v1.2.3