Implement Bech32m encoding/decoding

Github-Pull: #20861
Rebased-From: da2bb6976dadeec682d163c258c9afecc87d6428

6 files changed, 80 insertions, 54 deletions

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 <assert.h>
 
+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<std::string, data> 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<std::string, data> 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<uint8_t>& values);
+enum class Encoding {
+    INVALID, //!< Failed decoding
 
-/** Decode a Bech32 string. Returns (hrp, data). Empty hrp means failure. */
-std::pair<std::string, std::vector<uint8_t>> 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<uint8_t>& 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<uint8_t> data; //!< The payload (excluding checksum)
+
+    DecodeResult() : encoding(Encoding::INVALID) {}
+    DecodeResult(Encoding enc, std::string&& h, std::vector<uint8_t>&& 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<unsigned char> 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<unsigned char> 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<unsigned char> 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<uint8_t>& buffer)
 {
     const std::string random_string(buffer.begin(), buffer.end());
-    const std::pair<std::string, std::vector<uint8_t>> 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<uint8_t>& 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<unsigned char> 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<std::string, std::vector<uint8_t>> r2 = bech32::Decode(encoded);
-    if (r2.first.empty()) {
-        assert(r2.second.empty());
-    } else {
-        const std::string& hrp = r2.first;
-        const std::vector<uint8_t>& 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);
+        }
     }
 }