Merge #19935: Move SaltedHashers to separate file and add some new ones

281fd1a4a032cded7f9ea9857e3e99fc793c714b Replace KeyIDHasher with SaltedSipHasher (Andrew Chow)
210b693db66e7c5b618014b5a287aee15af00045 Add generic SaltedSipHasher (Andrew Chow)
95e61c1cf2a91d041c8025306ba36f0ea2806894 Move Hashers to util/hasher.{cpp/h} (Andrew Chow)

Pull request description:

  There are existing `SaltedOutPointHasher` and `SaltedTxidHasher` classes used for `std::unordered_map` and `std::unordered_set` that could be useful in other places in the codebase. So we these to their own `saltedhash.{cpp/h}` file. An existing `KeyIDHasher` is moved there too. Additionally, `ScriptIDHasher`, `SaltedPubkeyHasher`, and `SaltedScriptHasher` are added so that they can be used in future work.

  `KeyIDHasher` and `ScriptIDHasher` are not salted so that equality comparisons of maps and sets keyed by `CKeyID` and `CScriptID` will actually work.

  Split from #19602 (and a few other PRs/branches I have).

ACKs for top commit:
  laanwj:
    Code review ACK 281fd1a4a032cded7f9ea9857e3e99fc793c714b
  jonatack:
    ACK 281fd1a4a032cded7f9ea9857e3e99fc793c714b, code review, debug build and ran bitcoind after rebasing to master @ dff0f6f753ea
  fjahr:
    utACK 281fd1a4a032cded7f9ea9857e3e99fc793c714b

Tree-SHA512: bb03b231ccf3c9ecefc997b8da9c3770af4819f9be5b0a72997a103864e84046a2ac39b8eadf0dc9247bdccd53f86f433642e3a098882e6748341a9e7736271b

2 files changed, 118 insertions, 0 deletions

diff --git a/src/util/hasher.cpp b/src/util/hasher.cpp
new file mode 100644
index 0000000000..5900daf050
--- /dev/null
+++ b/src/util/hasher.cpp
@@ -0,0 +1,19 @@
+// Copyright (c) 2019 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 <random.h>
+#include <util/hasher.h>
+
+#include <limits>
+
+SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}
+
+SaltedOutpointHasher::SaltedOutpointHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}
+
+SaltedSipHasher::SaltedSipHasher() : m_k0(GetRand(std::numeric_limits<uint64_t>::max())), m_k1(GetRand(std::numeric_limits<uint64_t>::max())) {}
+
+size_t SaltedSipHasher::operator()(const Span<const unsigned char>& script) const
+{
+    return CSipHasher(m_k0, m_k1).Write(script.data(), script.size()).Finalize();
+}
diff --git a/src/util/hasher.h b/src/util/hasher.h
new file mode 100644
index 0000000000..fa2fea30d8
--- /dev/null
+++ b/src/util/hasher.h
@@ -0,0 +1,99 @@
+// Copyright (c) 2019 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_UTIL_HASHER_H
+#define BITCOIN_UTIL_HASHER_H
+
+#include <crypto/siphash.h>
+#include <primitives/transaction.h>
+#include <uint256.h>
+
+class SaltedTxidHasher
+{
+private:
+    /** Salt */
+    const uint64_t k0, k1;
+
+public:
+    SaltedTxidHasher();
+
+    size_t operator()(const uint256& txid) const {
+        return SipHashUint256(k0, k1, txid);
+    }
+};
+
+class SaltedOutpointHasher
+{
+private:
+    /** Salt */
+    const uint64_t k0, k1;
+
+public:
+    SaltedOutpointHasher();
+
+    /**
+     * This *must* return size_t. With Boost 1.46 on 32-bit systems the
+     * unordered_map will behave unpredictably if the custom hasher returns a
+     * uint64_t, resulting in failures when syncing the chain (#4634).
+     *
+     * Having the hash noexcept allows libstdc++'s unordered_map to recalculate
+     * the hash during rehash, so it does not have to cache the value. This
+     * reduces node's memory by sizeof(size_t). The required recalculation has
+     * a slight performance penalty (around 1.6%), but this is compensated by
+     * memory savings of about 9% which allow for a larger dbcache setting.
+     *
+     * @see https://gcc.gnu.org/onlinedocs/gcc-9.2.0/libstdc++/manual/manual/unordered_associative.html
+     */
+    size_t operator()(const COutPoint& id) const noexcept {
+        return SipHashUint256Extra(k0, k1, id.hash, id.n);
+    }
+};
+
+struct FilterHeaderHasher
+{
+    size_t operator()(const uint256& hash) const { return ReadLE64(hash.begin()); }
+};
+
+/**
+ * We're hashing a nonce into the entries themselves, so we don't need extra
+ * blinding in the set hash computation.
+ *
+ * This may exhibit platform endian dependent behavior but because these are
+ * nonced hashes (random) and this state is only ever used locally it is safe.
+ * All that matters is local consistency.
+ */
+class SignatureCacheHasher
+{
+public:
+    template <uint8_t hash_select>
+    uint32_t operator()(const uint256& key) const
+    {
+        static_assert(hash_select <8, "SignatureCacheHasher only has 8 hashes available.");
+        uint32_t u;
+        std::memcpy(&u, key.begin()+4*hash_select, 4);
+        return u;
+    }
+};
+
+struct BlockHasher
+{
+    // this used to call `GetCheapHash()` in uint256, which was later moved; the
+    // cheap hash function simply calls ReadLE64() however, so the end result is
+    // identical
+    size_t operator()(const uint256& hash) const { return ReadLE64(hash.begin()); }
+};
+
+class SaltedSipHasher
+{
+private:
+    /** Salt */
+    const uint64_t m_k0, m_k1;
+
+public:
+    SaltedSipHasher();
+
+    size_t operator()(const Span<const unsigned char>& script) const;
+};
+
+#endif // BITCOIN_UTIL_HASHER_H