Merge bitcoin/bitcoin#29015: kernel: Streamline util library

c7376babd19d0c858fef93ebd58338abd530c1f4 doc: Clarify distinction between util and common libraries in libraries.md (Ryan Ofsky)
4f74c59334d496f28e1a5c0d84c412f9020b366f util: Move util/string.h functions to util namespace (Ryan Ofsky)
4d05d3f3b42a41525aa6ec44b90f543dfab53ecf util: add TransactionError includes and namespace declarations (Ryan Ofsky)
680eafdc74021c1e0893c3a62404e607fd4724f5 util: move fees.h and error.h to common/messages.h (Ryan Ofsky)
02e62c6c9af4beabaeea58fb1ea3ad0dc5094678 common: Add PSBTError enum (Ryan Ofsky)
0d44c44ae33434f366229c612d6edeedf7658963 util: move error.h TransactionError enum to node/types.h (Ryan Ofsky)
9bcce2608dd2515dc35a0f0866abc9d43903c795 util: move spanparsing.h to script/parsing.h (Ryan Ofsky)
6dd2ad47922694d2ab84bad4dac9dd442c5df617 util: move spanparsing.h Split functions to string.h (Ryan Ofsky)
23cc8ddff472d259605d7790ba98a1900e77efab util: move HexStr and HexDigit from util to crypto (TheCharlatan)
6861f954f8ff42c87ad638037adae86a5bd89600 util: move util/message to common/signmessage (Ryan Ofsky)
cc5f29fbea15d33e4d1aa95591253c6b86953fe7 build: move memory_cleanse from util to crypto (Ryan Ofsky)
5b9309420cc9721a0d5745b6ad3166a4bdbd1508 build: move chainparamsbase from util to common (Ryan Ofsky)
ffa27af24da81a97d6c4912ae0e10bc5b6f17f69 test: Add check-deps.sh script to check for unexpected library dependencies (Ryan Ofsky)

Pull request description:

  Remove `fees.h`, `errors.h`, and `spanparsing.h` from the util library. Specifically:

  - Move `Split` functions from `util/spanparsing.h` to `util/string.h`, using `util` namespace for clarity.
  - Move remaining spanparsing functions to `script/parsing.h` since they are used for descriptor and miniscript parsing.
  - Combine `util/fees.h` and `util/errors.h` into `common/messages.h` so there is a place for simple functions that generate user messages to live, and these functions are not part of the util library.

  Motivation for this change is that the util library is a dependency of the kernel, and we should remove functionality from util that shouldn't be called by kernel code or kernel applications. These changes should also improve code organization and make functions easier to discover. Some of these same moves are (or were) part of #28690, but did not help with code organization, or made it worse, so it is better to move them and clean them up in the same PR so code only has to change one time.

ACKs for top commit:
  achow101:
    ACK c7376babd19d0c858fef93ebd58338abd530c1f4
  TheCharlatan:
    Re-ACK c7376babd19d0c858fef93ebd58338abd530c1f4
  hebasto:
    re-ACK c7376babd19d0c858fef93ebd58338abd530c1f4.

Tree-SHA512: 5bcef16c1255463b1b69270548711e7ff78ca0dd34e300b95e3ca1ce52ceb34f83d9ddb2839e83800ba36b200de30396e504bbb04fa02c6d0c24a16d06ae523d

7 files changed, 378 insertions, 0 deletions

diff --git a/src/common/config.cpp b/src/common/config.cpp
index 1c85273f69..98223fc3e3 100644
--- a/src/common/config.cpp
+++ b/src/common/config.cpp
@@ -27,6 +27,9 @@
 #include <utility>
 #include <vector>
 
+using util::TrimString;
+using util::TrimStringView;
+
 static bool GetConfigOptions(std::istream& stream, const std::string& filepath, std::string& error, std::vector<std::pair<std::string, std::string>>& options, std::list<SectionInfo>& sections)
 {
     std::string str, prefix;
diff --git a/src/common/messages.cpp b/src/common/messages.cpp
new file mode 100644
index 0000000000..9e88ca8b0f
--- /dev/null
+++ b/src/common/messages.cpp
@@ -0,0 +1,139 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2022 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <common/messages.h>
+
+#include <common/types.h>
+#include <policy/fees.h>
+#include <node/types.h>
+#include <tinyformat.h>
+#include <util/strencodings.h>
+#include <util/string.h>
+#include <util/translation.h>
+
+#include <cassert>
+#include <map>
+#include <string>
+#include <utility>
+#include <vector>
+
+using node::TransactionError;
+using util::Join;
+
+namespace common {
+std::string StringForFeeReason(FeeReason reason)
+{
+    static const std::map<FeeReason, std::string> fee_reason_strings = {
+        {FeeReason::NONE, "None"},
+        {FeeReason::HALF_ESTIMATE, "Half Target 60% Threshold"},
+        {FeeReason::FULL_ESTIMATE, "Target 85% Threshold"},
+        {FeeReason::DOUBLE_ESTIMATE, "Double Target 95% Threshold"},
+        {FeeReason::CONSERVATIVE, "Conservative Double Target longer horizon"},
+        {FeeReason::MEMPOOL_MIN, "Mempool Min Fee"},
+        {FeeReason::PAYTXFEE, "PayTxFee set"},
+        {FeeReason::FALLBACK, "Fallback fee"},
+        {FeeReason::REQUIRED, "Minimum Required Fee"},
+    };
+    auto reason_string = fee_reason_strings.find(reason);
+
+    if (reason_string == fee_reason_strings.end()) return "Unknown";
+
+    return reason_string->second;
+}
+
+const std::vector<std::pair<std::string, FeeEstimateMode>>& FeeModeMap()
+{
+    static const std::vector<std::pair<std::string, FeeEstimateMode>> FEE_MODES = {
+        {"unset", FeeEstimateMode::UNSET},
+        {"economical", FeeEstimateMode::ECONOMICAL},
+        {"conservative", FeeEstimateMode::CONSERVATIVE},
+    };
+    return FEE_MODES;
+}
+
+std::string FeeModes(const std::string& delimiter)
+{
+    return Join(FeeModeMap(), delimiter, [&](const std::pair<std::string, FeeEstimateMode>& i) { return i.first; });
+}
+
+std::string InvalidEstimateModeErrorMessage()
+{
+    return "Invalid estimate_mode parameter, must be one of: \"" + FeeModes("\", \"") + "\"";
+}
+
+bool FeeModeFromString(const std::string& mode_string, FeeEstimateMode& fee_estimate_mode)
+{
+    auto searchkey = ToUpper(mode_string);
+    for (const auto& pair : FeeModeMap()) {
+        if (ToUpper(pair.first) == searchkey) {
+            fee_estimate_mode = pair.second;
+            return true;
+        }
+    }
+    return false;
+}
+
+bilingual_str PSBTErrorString(PSBTError err)
+{
+    switch (err) {
+        case PSBTError::MISSING_INPUTS:
+            return Untranslated("Inputs missing or spent");
+        case PSBTError::SIGHASH_MISMATCH:
+            return Untranslated("Specified sighash value does not match value stored in PSBT");
+        case PSBTError::EXTERNAL_SIGNER_NOT_FOUND:
+            return Untranslated("External signer not found");
+        case PSBTError::EXTERNAL_SIGNER_FAILED:
+            return Untranslated("External signer failed to sign");
+        case PSBTError::UNSUPPORTED:
+            return Untranslated("Signer does not support PSBT");
+        // no default case, so the compiler can warn about missing cases
+    }
+    assert(false);
+}
+
+bilingual_str TransactionErrorString(const TransactionError err)
+{
+    switch (err) {
+        case TransactionError::OK:
+            return Untranslated("No error");
+        case TransactionError::MISSING_INPUTS:
+            return Untranslated("Inputs missing or spent");
+        case TransactionError::ALREADY_IN_CHAIN:
+            return Untranslated("Transaction already in block chain");
+        case TransactionError::MEMPOOL_REJECTED:
+            return Untranslated("Transaction rejected by mempool");
+        case TransactionError::MEMPOOL_ERROR:
+            return Untranslated("Mempool internal error");
+        case TransactionError::MAX_FEE_EXCEEDED:
+            return Untranslated("Fee exceeds maximum configured by user (e.g. -maxtxfee, maxfeerate)");
+        case TransactionError::MAX_BURN_EXCEEDED:
+            return Untranslated("Unspendable output exceeds maximum configured by user (maxburnamount)");
+        case TransactionError::INVALID_PACKAGE:
+            return Untranslated("Transaction rejected due to invalid package");
+        // no default case, so the compiler can warn about missing cases
+    }
+    assert(false);
+}
+
+bilingual_str ResolveErrMsg(const std::string& optname, const std::string& strBind)
+{
+    return strprintf(_("Cannot resolve -%s address: '%s'"), optname, strBind);
+}
+
+bilingual_str InvalidPortErrMsg(const std::string& optname, const std::string& invalid_value)
+{
+    return strprintf(_("Invalid port specified in %s: '%s'"), optname, invalid_value);
+}
+
+bilingual_str AmountHighWarn(const std::string& optname)
+{
+    return strprintf(_("%s is set very high!"), optname);
+}
+
+bilingual_str AmountErrMsg(const std::string& optname, const std::string& strValue)
+{
+    return strprintf(_("Invalid amount for -%s=<amount>: '%s'"), optname, strValue);
+}
+} // namespace common
diff --git a/src/common/messages.h b/src/common/messages.h
new file mode 100644
index 0000000000..68e7bb2169
--- /dev/null
+++ b/src/common/messages.h
@@ -0,0 +1,38 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+//! @file common/messages.h is a home for simple string functions returning
+//! descriptive messages that are used in RPC and GUI interfaces or log
+//! messages, and are called in different parts of the codebase across
+//! node/wallet/gui boundaries.
+
+#ifndef BITCOIN_COMMON_MESSAGES_H
+#define BITCOIN_COMMON_MESSAGES_H
+
+#include <string>
+
+struct bilingual_str;
+
+enum class FeeEstimateMode;
+enum class FeeReason;
+namespace node {
+enum class TransactionError;
+} // namespace node
+
+namespace common {
+enum class PSBTError;
+bool FeeModeFromString(const std::string& mode_string, FeeEstimateMode& fee_estimate_mode);
+std::string StringForFeeReason(FeeReason reason);
+std::string FeeModes(const std::string& delimiter);
+std::string InvalidEstimateModeErrorMessage();
+bilingual_str PSBTErrorString(PSBTError error);
+bilingual_str TransactionErrorString(const node::TransactionError error);
+bilingual_str ResolveErrMsg(const std::string& optname, const std::string& strBind);
+bilingual_str InvalidPortErrMsg(const std::string& optname, const std::string& strPort);
+bilingual_str AmountHighWarn(const std::string& optname);
+bilingual_str AmountErrMsg(const std::string& optname, const std::string& strValue);
+} // namespace common
+
+#endif // BITCOIN_COMMON_MESSAGES_H
diff --git a/src/common/signmessage.cpp b/src/common/signmessage.cpp
new file mode 100644
index 0000000000..1612751e44
--- /dev/null
+++ b/src/common/signmessage.cpp
@@ -0,0 +1,93 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2022 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <common/signmessage.h>
+#include <hash.h>
+#include <key.h>
+#include <key_io.h>
+#include <pubkey.h>
+#include <uint256.h>
+#include <util/strencodings.h>
+
+#include <cassert>
+#include <optional>
+#include <string>
+#include <variant>
+#include <vector>
+
+/**
+ * Text used to signify that a signed message follows and to prevent
+ * inadvertently signing a transaction.
+ */
+const std::string MESSAGE_MAGIC = "Bitcoin Signed Message:\n";
+
+MessageVerificationResult MessageVerify(
+    const std::string& address,
+    const std::string& signature,
+    const std::string& message)
+{
+    CTxDestination destination = DecodeDestination(address);
+    if (!IsValidDestination(destination)) {
+        return MessageVerificationResult::ERR_INVALID_ADDRESS;
+    }
+
+    if (std::get_if<PKHash>(&destination) == nullptr) {
+        return MessageVerificationResult::ERR_ADDRESS_NO_KEY;
+    }
+
+    auto signature_bytes = DecodeBase64(signature);
+    if (!signature_bytes) {
+        return MessageVerificationResult::ERR_MALFORMED_SIGNATURE;
+    }
+
+    CPubKey pubkey;
+    if (!pubkey.RecoverCompact(MessageHash(message), *signature_bytes)) {
+        return MessageVerificationResult::ERR_PUBKEY_NOT_RECOVERED;
+    }
+
+    if (!(PKHash(pubkey) == *std::get_if<PKHash>(&destination))) {
+        return MessageVerificationResult::ERR_NOT_SIGNED;
+    }
+
+    return MessageVerificationResult::OK;
+}
+
+bool MessageSign(
+    const CKey& privkey,
+    const std::string& message,
+    std::string& signature)
+{
+    std::vector<unsigned char> signature_bytes;
+
+    if (!privkey.SignCompact(MessageHash(message), signature_bytes)) {
+        return false;
+    }
+
+    signature = EncodeBase64(signature_bytes);
+
+    return true;
+}
+
+uint256 MessageHash(const std::string& message)
+{
+    HashWriter hasher{};
+    hasher << MESSAGE_MAGIC << message;
+
+    return hasher.GetHash();
+}
+
+std::string SigningResultString(const SigningResult res)
+{
+    switch (res) {
+        case SigningResult::OK:
+            return "No error";
+        case SigningResult::PRIVATE_KEY_NOT_AVAILABLE:
+            return "Private key not available";
+        case SigningResult::SIGNING_FAILED:
+            return "Sign failed";
+        // no default case, so the compiler can warn about missing cases
+    }
+    assert(false);
+}
diff --git a/src/common/signmessage.h b/src/common/signmessage.h
new file mode 100644
index 0000000000..215b563bbb
--- /dev/null
+++ b/src/common/signmessage.h
@@ -0,0 +1,77 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2022 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_COMMON_SIGNMESSAGE_H
+#define BITCOIN_COMMON_SIGNMESSAGE_H
+
+#include <uint256.h>
+
+#include <string>
+
+class CKey;
+
+extern const std::string MESSAGE_MAGIC;
+
+/** The result of a signed message verification.
+ * Message verification takes as an input:
+ * - address (with whose private key the message is supposed to have been signed)
+ * - signature
+ * - message
+ */
+enum class MessageVerificationResult {
+    //! The provided address is invalid.
+    ERR_INVALID_ADDRESS,
+
+    //! The provided address is valid but does not refer to a public key.
+    ERR_ADDRESS_NO_KEY,
+
+    //! The provided signature couldn't be parsed (maybe invalid base64).
+    ERR_MALFORMED_SIGNATURE,
+
+    //! A public key could not be recovered from the provided signature and message.
+    ERR_PUBKEY_NOT_RECOVERED,
+
+    //! The message was not signed with the private key of the provided address.
+    ERR_NOT_SIGNED,
+
+    //! The message verification was successful.
+    OK
+};
+
+enum class SigningResult {
+    OK, //!< No error
+    PRIVATE_KEY_NOT_AVAILABLE,
+    SIGNING_FAILED,
+};
+
+/** Verify a signed message.
+ * @param[in] address Signer's bitcoin address, it must refer to a public key.
+ * @param[in] signature The signature in base64 format.
+ * @param[in] message The message that was signed.
+ * @return result code */
+MessageVerificationResult MessageVerify(
+    const std::string& address,
+    const std::string& signature,
+    const std::string& message);
+
+/** Sign a message.
+ * @param[in] privkey Private key to sign with.
+ * @param[in] message The message to sign.
+ * @param[out] signature Signature, base64 encoded, only set if true is returned.
+ * @return true if signing was successful. */
+bool MessageSign(
+    const CKey& privkey,
+    const std::string& message,
+    std::string& signature);
+
+/**
+ * Hashes a message for signing and verification in a manner that prevents
+ * inadvertently signing a transaction.
+ */
+uint256 MessageHash(const std::string& message);
+
+std::string SigningResultString(const SigningResult res);
+
+#endif // BITCOIN_COMMON_SIGNMESSAGE_H
diff --git a/src/common/system.cpp b/src/common/system.cpp
index ddd0feda3b..6d04c8a7bc 100644
--- a/src/common/system.cpp
+++ b/src/common/system.cpp
@@ -28,6 +28,8 @@
 #include <string>
 #include <thread>
 
+using util::ReplaceAll;
+
 // Application startup time (used for uptime calculation)
 const int64_t nStartupTime = GetTime();
 
diff --git a/src/common/types.h b/src/common/types.h
new file mode 100644
index 0000000000..0d9cb67ce9
--- /dev/null
+++ b/src/common/types.h
@@ -0,0 +1,26 @@
+// Copyright (c) 2010-2021 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+//! @file common/types.h is a home for simple enum and struct type definitions
+//! that can be used internally by functions in the libbitcoin_common library,
+//! but also used externally by node, wallet, and GUI code.
+//!
+//! This file is intended to define only simple types that do not have external
+//! dependencies. More complicated types should be defined in dedicated header
+//! files.
+
+#ifndef BITCOIN_COMMON_TYPES_H
+#define BITCOIN_COMMON_TYPES_H
+
+namespace common {
+enum class PSBTError {
+    MISSING_INPUTS,
+    SIGHASH_MISMATCH,
+    EXTERNAL_SIGNER_NOT_FOUND,
+    EXTERNAL_SIGNER_FAILED,
+    UNSUPPORTED,
+};
+} // namespace common
+
+#endif // BITCOIN_COMMON_TYPES_H