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,35 @@
#ifndef BITCOIN_SCRIPT_SCRIPTCACHE_H
#define BITCOIN_SCRIPT_SCRIPTCACHE_H
-#include <uint256.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, 28> 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 +44,15 @@
/** 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. */
-bool IsKeyInScriptCache(uint256 key, bool erase);
+/**
+ * Check if a given key is in the cache, and if so, return its values.
+ * (if not found, nSigChecks may or may not be set to an arbitrary value)
+ */
+bool IsKeyInScriptCache(ScriptCacheKey key, bool erase, int &nSigChecksOut);
-/** Add an entry in the cache. */
-void AddKeyInScriptCache(uint256 key);
+/**
+ * Add an entry in the cache.
+ */
+void AddKeyInScriptCache(ScriptCacheKey key, int nSigChecks);
#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
@@ -13,7 +13,63 @@
#include <util/system.h>
#include <validation.h>
-static CuckooCache::cache<CuckooCache::KeyOnly<uint256>, SignatureCacheHasher>
+/**
+ * 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;
+ int nSigChecks;
+
+ ScriptCacheElement() = default;
+
+ ScriptCacheElement(const KeyType &keyIn, int nSigChecksIn)
+ : key(keyIn), nSigChecks(nSigChecksIn) {}
+
+ const KeyType &getKey() const { return key; }
+};
+
+static_assert(sizeof(ScriptCacheElement) == 32,
+ "ScriptCacheElement should 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) == 28,
+ "modify the following if key size changes");
+
+ uint32_t u;
+ static_assert(sizeof(u) == 4 && sizeof(d[0]) == 1, "basic assumptions");
+ if (hash_select < 7) {
+ std::memcpy(&u, d.data() + 4 * hash_select, 4);
+ } else {
+ // We are required to produce 8 subhashes, and all bytes have
+ // been used once. We re-use the bytes but mix together different
+ // entries (and flip the order) to get a new, distinct value.
+ uint8_t arr[4];
+ arr[0] = d[3] ^ d[7] ^ d[11] ^ d[15];
+ arr[1] = d[6] ^ d[10] ^ d[14] ^ d[18];
+ arr[2] = d[9] ^ d[13] ^ d[17] ^ d[21];
+ arr[3] = d[12] ^ d[16] ^ d[20] ^ d[24];
+ std::memcpy(&u, arr, 4);
+ }
+ return u;
+ }
+};
+
+static CuckooCache::cache<ScriptCacheElement, ScriptCacheHasher>
scriptExecutionCache;
static uint256 scriptExecutionCacheNonce(GetRandHash());
@@ -32,8 +88,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) {
+ std::array<uint8_t, 32> 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 +98,28 @@
.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.begin() + data.size(), data.begin());
}
-bool IsKeyInScriptCache(uint256 key, bool erase) {
+bool IsKeyInScriptCache(ScriptCacheKey key, bool erase, int &nSigChecksOut) {
// 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);
+ nSigChecksOut = elem.nSigChecks;
+ return ret;
}
-void AddKeyInScriptCache(uint256 key) {
+void AddKeyInScriptCache(ScriptCacheKey key, int nSigChecks) {
// TODO: Remove this requirement by making CuckooCache not require external
// locks
AssertLockHeld(cs_main);
- scriptExecutionCache.insert(key);
+
+ ScriptCacheElement elem(key, nSigChecks);
+ scriptExecutionCache.insert(elem);
}
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
@@ -443,4 +443,86 @@
}
}
+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_sigchecks) \
+ { \
+ int nSigChecksRet(0x12345678 ^ (expected_sigchecks)); \
+ BOOST_CHECK(IsKeyInScriptCache(key, false, nSigChecksRet)); \
+ BOOST_CHECK(nSigChecksRet == (expected_sigchecks)); \
+ }
+#define CHECK_CACHE_MISSING(key) \
+ { \
+ int dummy; \
+ BOOST_CHECK(!IsKeyInScriptCache(key, false, dummy)); \
+ }
+
+ 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, 42);
+ CHECK_CACHE_HAS(key1A, 42);
+
+ CHECK_CACHE_MISSING(key1B);
+ CHECK_CACHE_MISSING(key2A);
+ CHECK_CACHE_MISSING(key2B);
+
+ // 0 may be stored
+ AddKeyInScriptCache(key1B, 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.
+ const int max_standard_sigchecks = 1 + (MAX_TX_SIZE / 33);
+ AddKeyInScriptCache(key2A, max_standard_sigchecks);
+
+ // Read out values again.
+ CHECK_CACHE_HAS(key1A, 42);
+ CHECK_CACHE_HAS(key1B, 0);
+ CHECK_CACHE_HAS(key2A, max_standard_sigchecks);
+ CHECK_CACHE_MISSING(key2B);
+
+ // Try overwriting an existing entry with different value (should never
+ // happen in practice but see what happens).
+ AddKeyInScriptCache(key1A, 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, 42);
+}
+
BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -1227,8 +1227,10 @@
// 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);
+ int nSigChecksDummy;
+ if (IsKeyInScriptCache(hashCacheEntry, !scriptCacheStore,
+ nSigChecksDummy)) {
return true;
}
@@ -1291,7 +1293,7 @@
if (scriptCacheStore && !pvChecks) {
// We executed all of the provided scripts, and were told to cache the
// result. Do so now.
- AddKeyInScriptCache(hashCacheEntry);
+ AddKeyInScriptCache(hashCacheEntry, 0);
}
return true;