diff --git a/src/script/script_metrics.h b/src/script/script_metrics.h
--- a/src/script/script_metrics.h
+++ b/src/script/script_metrics.h
@@ -11,6 +11,13 @@
  */
 struct ScriptExecutionMetrics {
     int nSigChecks = 0;
+
+    ScriptExecutionMetrics() = default;
+    ScriptExecutionMetrics(int _nSigChecks) : nSigChecks(_nSigChecks) {}
+
+    bool operator==(const ScriptExecutionMetrics &rhs) {
+        return nSigChecks == rhs.nSigChecks;
+    }
 };
 
 #endif // BITCOIN_SCRIPT_SCRIPT_METRICS_H
diff --git a/src/script/scriptcache.h b/src/script/scriptcache.h
--- a/src/script/scriptcache.h
+++ b/src/script/scriptcache.h
@@ -5,12 +5,37 @@
 #ifndef BITCOIN_SCRIPT_SCRIPTCACHE_H
 #define BITCOIN_SCRIPT_SCRIPTCACHE_H
 
-#include <uint256.h>
+#include <script/script_metrics.h>
 
+#include <array>
 #include <cstdint>
 
 class CTransaction;
 
+/**
+ * The script cache is a map using a key/value element, that caches the
+ * success of executing a specific transaction's input scripts under a
+ * specific set of flags, along with any associated information learned
+ * during execution.
+ *
+ * The key is slightly shorter than a power-of-two size to make room for
+ * the value.
+ */
+class ScriptCacheKey {
+    std::array<uint8_t, 30> data;
+
+public:
+    ScriptCacheKey() = default;
+    ScriptCacheKey(const ScriptCacheKey &rhs) = default;
+    ScriptCacheKey(const CTransaction &tx, uint32_t flags);
+
+    bool operator==(const ScriptCacheKey &rhs) const {
+        return rhs.data == data;
+    }
+
+    friend class ScriptCacheHasher;
+};
+
 // DoS prevention: limit cache size to 32MB (over 1000000 entries on 64-bit
 // systems). Due to how we count cache size, actual memory usage is slightly
 // more (~32.25 MB)
@@ -21,13 +46,34 @@
 /** Initializes the script-execution cache */
 void InitScriptExecutionCache();
 
-/** Compute the cache key for a given transaction and flags. */
-uint256 GetScriptCacheKey(const CTransaction &tx, uint32_t flags);
+/**
+ * Check if a given key is in the cache, and if so, return its values.
+ * (if not found, metricsOut may or may not be set to an arbitrary value)
+ */
+bool IsKeyInScriptCache(ScriptCacheKey key, bool erase,
+                        ScriptExecutionMetrics &metricsOut);
+
+constexpr int SCRIPT_CACHE_MAX_SIGCHECKS = UINT16_MAX;
 
-/** Check if a given key is in the cache. */
-bool IsKeyInScriptCache(uint256 key, bool erase);
+/**
+ * Try to store a given key with values in the cache. Due to limited storage
+ * bits, the cache can only store values in certain ranges:
+ *
+ *    0 <= metricsIn.nSigChecks <= SCRIPT_CACHE_MAX_SIGCHECKS
+ *
+ * If any value is out of range, this will return false rather than storing this
+ * item into the cache. Otherwise it returns true.
+ */
+bool TryAddKeyInScriptCache(ScriptCacheKey key, ScriptExecutionMetrics metrics);
 
-/** Add an entry in the cache. */
-void AddKeyInScriptCache(uint256 key);
+/**
+ * Add an entry in the cache.
+ */
+static inline void AddKeyInScriptCache(ScriptCacheKey key,
+                                       ScriptExecutionMetrics metrics) {
+    if (!TryAddKeyInScriptCache(key, metrics)) {
+        throw std::range_error("metrics out of range");
+    }
+}
 
 #endif // BITCOIN_SCRIPT_SCRIPTCACHE_H
diff --git a/src/script/scriptcache.cpp b/src/script/scriptcache.cpp
--- a/src/script/scriptcache.cpp
+++ b/src/script/scriptcache.cpp
@@ -10,10 +10,70 @@
 #include <random.h>
 #include <script/sigcache.h>
 #include <sync.h>
+#include <uint256.h>
 #include <util/system.h>
 #include <validation.h>
 
-static CuckooCache::cache<CuckooCache::KeyOnly<uint256>, SignatureCacheHasher>
+#include <limits>
+
+/**
+ * In future if many more values are added, it should be considered to
+ * expand the element size to 64 bytes (with padding the spare space as
+ * needed) so the key can be long. Shortening the key too much risks
+ * opening ourselves up to consensus-failing collisions, however it should
+ * be noted that our cache nonce is private and unique, so collisions would
+ * affect only one node and attackers have no way of offline-preparing a
+ * collision attack even on short keys.
+ */
+struct ScriptCacheElement {
+    using KeyType = ScriptCacheKey;
+
+    KeyType key;
+    uint16_t nSigChecks;
+
+    static_assert(SCRIPT_CACHE_MAX_SIGCHECKS ==
+                      std::numeric_limits<decltype(nSigChecks)>::max(),
+                  "the declared maximum must match the storage type");
+
+    ScriptCacheElement() = default;
+
+    ScriptCacheElement(const KeyType &keyIn, uint16_t nSigChecksIn)
+        : key(keyIn), nSigChecks(nSigChecksIn) {}
+
+    const KeyType &getKey() const { return key; }
+};
+
+static_assert(sizeof(ScriptCacheElement) == 32,
+              "ScriptCacheElement must be 32 bytes");
+
+class ScriptCacheHasher {
+public:
+    template <uint8_t hash_select>
+    uint32_t operator()(const ScriptCacheKey &k) const {
+        static_assert(hash_select < 8, "only has 8 hashes available.");
+
+        const auto &d = k.data;
+
+        static_assert(sizeof(d) == 30,
+                      "modify the following if key size changes");
+
+        uint32_t u;
+        if (hash_select < 7) {
+            std::memcpy(&u, d.data() + 4 * hash_select, 4);
+        } else {
+            // We are required to produce 8 subhashes. We have only two
+            // key bytes left over but this is fine. We put the leftovers
+            // on the higher bits, as these are what primarily get used to
+            // determine the index. The lower bits are filled by reusing
+            // some other bytes.
+            u = (uint32_t(d[28]) << 24) + (uint32_t(d[29]) << 16) +
+                (uint32_t(d[3]) << 8) + uint32_t(d[7]);
+        }
+        return u;
+    }
+};
+
+static CuckooCache::cache<ScriptCacheElement, ScriptCacheHasher>
     scriptExecutionCache;
 static uint256 scriptExecutionCacheNonce(GetRandHash());
 
@@ -32,8 +92,8 @@
               (nElems * sizeof(uint256)) >> 20, nMaxCacheSize >> 20, nElems);
 }
 
-uint256 GetScriptCacheKey(const CTransaction &tx, uint32_t flags) {
-    uint256 key;
+ScriptCacheKey::ScriptCacheKey(const CTransaction &tx, uint32_t flags) {
+    uint256 hash;
     // We only use the first 19 bytes of nonce to avoid a second SHA round -
     // giving us 19 + 32 + 4 = 55 bytes (+ 8 + 1 = 64)
     static_assert(55 - sizeof(flags) - 32 >= 128 / 8,
@@ -42,21 +102,40 @@
         .Write(scriptExecutionCacheNonce.begin(), 55 - sizeof(flags) - 32)
         .Write(tx.GetHash().begin(), 32)
         .Write((uint8_t *)&flags, sizeof(flags))
-        .Finalize(key.begin());
+        .Finalize(hash.begin());
 
-    return key;
+    assert(data.size() < hash.size());
+    std::copy(hash.begin() + hash.size() - data.size(), hash.end(),
+              data.begin());
 }
 
-bool IsKeyInScriptCache(uint256 key, bool erase) {
+bool IsKeyInScriptCache(ScriptCacheKey key, bool erase,
+                        ScriptExecutionMetrics &metricsOut) {
     // TODO: Remove this requirement by making CuckooCache not require external
     // locks
     AssertLockHeld(cs_main);
-    return scriptExecutionCache.contains(key, erase);
+
+    ScriptCacheElement elem(key, 0);
+    bool ret = scriptExecutionCache.get(elem, erase);
+
+    // use constructor initialization here rather than initializer list /
+    // setting individual items, to make sure we don't miss any.
+    metricsOut = ScriptExecutionMetrics(elem.nSigChecks);
+    return ret;
 }
 
-void AddKeyInScriptCache(uint256 key) {
+bool TryAddKeyInScriptCache(ScriptCacheKey key,
+                            ScriptExecutionMetrics metricsIn) {
     // TODO: Remove this requirement by making CuckooCache not require external
     // locks
     AssertLockHeld(cs_main);
-    scriptExecutionCache.insert(key);
+
+    if (metricsIn.nSigChecks < 0 ||
+        metricsIn.nSigChecks > SCRIPT_CACHE_MAX_SIGCHECKS) {
+        return false;
+    }
+
+    ScriptCacheElement elem(key, metricsIn.nSigChecks);
+    scriptExecutionCache.insert(elem);
+    return true;
 }
diff --git a/src/test/txvalidationcache_tests.cpp b/src/test/txvalidationcache_tests.cpp
--- a/src/test/txvalidationcache_tests.cpp
+++ b/src/test/txvalidationcache_tests.cpp
@@ -431,4 +431,100 @@
     }
 }
 
+BOOST_AUTO_TEST_CASE(scriptcache_values) {
+    // Test insertion and querying of keys&values from the script cache.
+
+    // Define a couple of macros (handier than functions since errors will print
+    // out the correct line number)
+#define CHECK_CACHE_HAS(key, expected_metrics)                                 \
+    {                                                                          \
+        ScriptExecutionMetrics metricsRet(0x12345678);                         \
+        BOOST_CHECK(IsKeyInScriptCache(key, false, metricsRet));               \
+        BOOST_CHECK(metricsRet == expected_metrics);                           \
+    }
+#define CHECK_CACHE_MISSING(key)                                               \
+    {                                                                          \
+        ScriptExecutionMetrics metricsDummy;                                   \
+        BOOST_CHECK(!IsKeyInScriptCache(key, false, metricsDummy));            \
+    }
+
+    InitScriptExecutionCache();
+
+    // construct four distinct keys from very slightly different data
+    CMutableTransaction tx1;
+    tx1.nVersion = 1;
+    CMutableTransaction tx2;
+    tx2.nVersion = 2;
+    uint32_t flagsA = 0x7fffffff;
+    uint32_t flagsB = 0xffffffff;
+    ScriptCacheKey key1A(CTransaction(tx1), flagsA);
+    ScriptCacheKey key1B(CTransaction(tx1), flagsB);
+    ScriptCacheKey key2A(CTransaction(tx2), flagsA);
+    ScriptCacheKey key2B(CTransaction(tx2), flagsB);
+
+    BOOST_CHECK(key1A == key1A);
+    BOOST_CHECK(!(key1A == key1B));
+    BOOST_CHECK(!(key1A == key2A));
+    BOOST_CHECK(!(key1A == key2B));
+    BOOST_CHECK(key1B == key1B);
+    BOOST_CHECK(!(key1B == key2A));
+    BOOST_CHECK(!(key1B == key2B));
+    BOOST_CHECK(key2A == key2A);
+    BOOST_CHECK(!(key2A == key2B));
+    BOOST_CHECK(key2B == key2B);
+
+    // Key is not yet inserted.
+    CHECK_CACHE_MISSING(key1A);
+    // Add the key and check it worked
+    AddKeyInScriptCache(key1A, ScriptExecutionMetrics(42));
+    CHECK_CACHE_HAS(key1A, ScriptExecutionMetrics(42));
+
+    CHECK_CACHE_MISSING(key1B);
+    CHECK_CACHE_MISSING(key2A);
+    CHECK_CACHE_MISSING(key2B);
+
+    // 0 may be stored
+    BOOST_CHECK(TryAddKeyInScriptCache(key1B, ScriptExecutionMetrics(0)));
+
+    // Calculate the most possible transaction sigchecks that can occur in a
+    // standard transaction, and make sure the cache can hold it.
+    //
+    // To be pessimistic, use consensus (MAX_TX_SIZE) instead of policy
+    // (MAX_STANDARD_TX_SIZE) since that particular policy limit is bypassed on
+    // testnet.
+    //
+    // Assume that a standardness rule limiting density to ~33 bytes/sigcheck is
+    // in place.
+    ScriptExecutionMetrics max_standard_sigchecks(1 + (MAX_TX_SIZE / 33));
+    AddKeyInScriptCache(key2A, max_standard_sigchecks);
+
+    // Try adding an unstoreable value
+    ScriptExecutionMetrics badMetrics1(-1);
+    ScriptExecutionMetrics badMetrics2(SCRIPT_CACHE_MAX_SIGCHECKS + 1);
+    BOOST_CHECK(!TryAddKeyInScriptCache(key2B, badMetrics1));
+    BOOST_CHECK(!TryAddKeyInScriptCache(key2B, badMetrics2));
+    BOOST_CHECK_THROW(AddKeyInScriptCache(key2B, badMetrics1),
+                      std::range_error);
+    BOOST_CHECK_THROW(AddKeyInScriptCache(key2B, badMetrics2),
+                      std::range_error);
+
+    // Read out values again.
+    CHECK_CACHE_HAS(key1A, ScriptExecutionMetrics(42));
+    CHECK_CACHE_HAS(key1B, ScriptExecutionMetrics(0));
+    CHECK_CACHE_HAS(key2A, max_standard_sigchecks);
+    CHECK_CACHE_MISSING(key2B);
+
+    // We can insert the max.
+    AddKeyInScriptCache(key2A,
+                        ScriptExecutionMetrics(SCRIPT_CACHE_MAX_SIGCHECKS));
+
+    // Try overwriting an existing entry with different value (should never
+    // happen in practice but see what happens).
+    AddKeyInScriptCache(key1A, ScriptExecutionMetrics(99));
+    // This succeeds without error, but (currently) no replacement is done.
+    // It would also be acceptable to overwrite, but if we ever come to a
+    // situation where this matters then neither alternative is better.
+    CHECK_CACHE_HAS(key1A, ScriptExecutionMetrics(42));
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -1232,8 +1232,9 @@
     // Note that this assumes that the inputs provided are correct (ie that the
     // transaction hash which is in tx's prevouts properly commits to the
     // scriptPubKey in the inputs view of that transaction).
-    uint256 hashCacheEntry = GetScriptCacheKey(tx, flags);
-    if (IsKeyInScriptCache(hashCacheEntry, !scriptCacheStore)) {
+    ScriptCacheKey hashCacheEntry(tx, flags);
+    ScriptExecutionMetrics metricsDummy;
+    if (IsKeyInScriptCache(hashCacheEntry, !scriptCacheStore, metricsDummy)) {
         return true;
     }
 
@@ -1296,7 +1297,16 @@
     if (scriptCacheStore && !pvChecks) {
         // We executed all of the provided scripts, and were told to cache the
         // result. Do so now.
-        AddKeyInScriptCache(hashCacheEntry);
+        if (!TryAddKeyInScriptCache(hashCacheEntry,
+                                    ScriptExecutionMetrics(0))) {
+            // This shouldn't happen, but it's not a disaster since it just
+            // means we have to re-execute the scripts next time we see this
+            // transaction (and some of its signatures ought to be cached, so it
+            // will be faster the second time).
+            LogPrintf("%s: BUG! PLEASE REPORT THIS! Unable to cache validity "
+                      "of tx %s (with flags %x).\n",
+                      __func__, tx.GetId().ToString(), flags);
+        }
     }
 
     return true;