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 - +#include #include 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 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 #include -static CuckooCache::cache, 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 + 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 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 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;