diff --git a/src/Makefile.am b/src/Makefile.am --- a/src/Makefile.am +++ b/src/Makefile.am @@ -130,6 +130,7 @@ rpc/server.h \ rpc/register.h \ scheduler.h \ + script/scriptcache.h \ script/sigcache.h \ script/sign.h \ script/standard.h \ @@ -208,6 +209,7 @@ rpc/net.cpp \ rpc/rawtransaction.cpp \ rpc/server.cpp \ + script/scriptcache.cpp \ script/sigcache.cpp \ script/ismine.cpp \ timedata.cpp \ diff --git a/src/cuckoocache.h b/src/cuckoocache.h --- a/src/cuckoocache.h +++ b/src/cuckoocache.h @@ -445,11 +445,14 @@ */ inline bool contains(const Element &e, const bool erase) const { std::array locs = compute_hashes(e); - for (uint32_t loc : locs) + for (uint32_t loc : locs) { if (table[loc] == e) { - if (erase) allow_erase(loc); + if (erase) { + allow_erase(loc); + } return true; } + } return false; } }; diff --git a/src/init.cpp b/src/init.cpp --- a/src/init.cpp +++ b/src/init.cpp @@ -28,6 +28,7 @@ #include "rpc/register.h" #include "rpc/server.h" #include "scheduler.h" +#include "script/scriptcache.h" #include "script/sigcache.h" #include "script/standard.h" #include "timedata.h" @@ -705,6 +706,10 @@ "-maxsigcachesize=", strprintf("Limit size of signature cache to MiB (default: %u)", DEFAULT_MAX_SIG_CACHE_SIZE)); + strUsage += HelpMessageOpt( + "-maxscriptcachesize=", + strprintf("Limit size of script cache to MiB (default: %u)", + DEFAULT_MAX_SCRIPT_CACHE_SIZE)); strUsage += HelpMessageOpt( "-maxtipage=", strprintf("Maximum tip age in seconds to consider node in initial " @@ -1656,12 +1661,14 @@ nMaxConnections, nFD); InitSignatureCache(); + InitScriptExecutionCache(); LogPrintf("Using %u threads for script verification\n", nScriptCheckThreads); if (nScriptCheckThreads) { - for (int i = 0; i < nScriptCheckThreads - 1; i++) + for (int i = 0; i < nScriptCheckThreads - 1; i++) { threadGroup.create_thread(&ThreadScriptCheck); + } } // Start the lightweight task scheduler thread diff --git a/src/script/scriptcache.h b/src/script/scriptcache.h new file mode 100644 --- /dev/null +++ b/src/script/scriptcache.h @@ -0,0 +1,33 @@ +// Copyright (c) 2017 - The Bitcoin Developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_SCRIPT_SCRIPTCACHE_H +#define BITCOIN_SCRIPT_SCRIPTCACHE_H + +#include "uint256.h" + +#include + +class CTransaction; + +// 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) +static const unsigned int DEFAULT_MAX_SCRIPT_CACHE_SIZE = 32; +// Maximum sig cache size allowed +static const int64_t MAX_MAX_SCRIPT_CACHE_SIZE = 16384; + +/** 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); + +/** Add an entry in the cache. */ +void AddKeyInScriptCache(uint256 key); + +#endif // BITCOIN_SCRIPT_SCRIPTCACHE_H diff --git a/src/script/scriptcache.cpp b/src/script/scriptcache.cpp new file mode 100644 --- /dev/null +++ b/src/script/scriptcache.cpp @@ -0,0 +1,60 @@ +// Copyright (c) 2017 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "scriptcache.h" + +#include "crypto/sha256.h" +#include "cuckoocache.h" +#include "primitives/transaction.h" +#include "random.h" +#include "script/sigcache.h" +#include "sync.h" +#include "util.h" +#include "validation.h" + +static CuckooCache::cache scriptExecutionCache; +static uint256 scriptExecutionCacheNonce(GetRandHash()); + +void InitScriptExecutionCache() { + // nMaxCacheSize is unsigned. If -maxscriptcachesize is set to zero, + // setup_bytes creates the minimum possible cache (2 elements). + size_t nMaxCacheSize = + std::min(std::max(int64_t(0), GetArg("-maxscriptcachesize", + DEFAULT_MAX_SCRIPT_CACHE_SIZE)), + MAX_MAX_SCRIPT_CACHE_SIZE) * + (size_t(1) << 20); + size_t nElems = scriptExecutionCache.setup_bytes(nMaxCacheSize); + LogPrintf("Using %zu MiB out of %zu requested for script execution cache, " + "able to store %zu elements\n", + (nElems * sizeof(uint256)) >> 20, nMaxCacheSize >> 20, nElems); +} + +uint256 GetScriptCacheKey(const CTransaction &tx, uint32_t flags) { + uint256 key; + // 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, + "Want at least 128 bits of nonce for script execution cache"); + CSHA256() + .Write(scriptExecutionCacheNonce.begin(), 55 - sizeof(flags) - 32) + .Write(tx.GetHash().begin(), 32) + .Write((uint8_t *)&flags, sizeof(flags)) + .Finalize(key.begin()); + + return key; +} + +bool IsKeyInScriptCache(uint256 key, bool erase) { + // TODO: Remove this requirement by making CuckooCache not require external + // locks + AssertLockHeld(cs_main); + return scriptExecutionCache.contains(key, erase); +} + +void AddKeyInScriptCache(uint256 key) { + // TODO: Remove this requirement by making CuckooCache not require external + // locks + AssertLockHeld(cs_main); + scriptExecutionCache.insert(key); +} diff --git a/src/test/test_bitcoin.cpp b/src/test/test_bitcoin.cpp --- a/src/test/test_bitcoin.cpp +++ b/src/test/test_bitcoin.cpp @@ -17,6 +17,7 @@ #include "random.h" #include "rpc/register.h" #include "rpc/server.h" +#include "script/scriptcache.h" #include "script/sigcache.h" #include "txdb.h" #include "txmempool.h" @@ -52,6 +53,7 @@ SetupEnvironment(); SetupNetworking(); InitSignatureCache(); + InitScriptExecutionCache(); // Don't want to write to debug.log file. fPrintToDebugLog = false; fCheckBlockIndex = true; diff --git a/src/validation.cpp b/src/validation.cpp --- a/src/validation.cpp +++ b/src/validation.cpp @@ -23,6 +23,7 @@ #include "primitives/transaction.h" #include "random.h" #include "script/script.h" +#include "script/scriptcache.h" #include "script/sigcache.h" #include "script/standard.h" #include "timedata.h" @@ -227,7 +228,8 @@ int nManualPruneHeight); static bool CheckInputs(const CTransaction &tx, CValidationState &state, const CCoinsViewCache &view, bool fScriptChecks, - uint32_t flags, bool cacheStore, + uint32_t flags, bool sigCacheStore, + bool scriptCacheStore, const PrecomputedTransactionData &txdata, std::vector *pvChecks = nullptr); static uint32_t GetBlockScriptFlags(const CBlockIndex *pindex, @@ -879,7 +881,7 @@ // Check against previous transactions. This is done last to help // prevent CPU exhaustion denial-of-service attacks. PrecomputedTransactionData txdata(tx); - if (!CheckInputs(tx, state, view, true, scriptVerifyFlags, true, + if (!CheckInputs(tx, state, view, true, scriptVerifyFlags, true, false, txdata)) { // State filled in by CheckInputs. return false; @@ -903,7 +905,7 @@ uint32_t currentBlockScriptVerifyFlags = GetBlockScriptFlags(chainActive.Tip(), config); if (!CheckInputs(tx, state, view, true, currentBlockScriptVerifyFlags, - true, txdata)) { + true, true, txdata)) { // If we're using promiscuousmempoolflags, we may hit this normally. // Check if current block has some flags that scriptVerifyFlags does // not before printing an ominous warning. @@ -915,7 +917,8 @@ } if (!CheckInputs(tx, state, view, true, - MANDATORY_SCRIPT_VERIFY_FLAGS, true, txdata)) { + MANDATORY_SCRIPT_VERIFY_FLAGS, true, false, + txdata)) { return error( "%s: ConnectInputs failed against MANDATORY but not " "STANDARD flags due to promiscuous mempool %s, %s", @@ -941,9 +944,10 @@ LimitMempoolSize( pool, GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000, GetArg("-mempoolexpiry", DEFAULT_MEMPOOL_EXPIRY) * 60 * 60); - if (!pool.exists(txid)) + if (!pool.exists(txid)) { return state.DoS(0, false, REJECT_INSUFFICIENTFEE, "mempool full"); + } } } @@ -1368,13 +1372,20 @@ /** * Check whether all inputs of this transaction are valid (no double spends, - * scripts & sigs, amounts). This does not modify the UTXO set. If pvChecks is - * not nullptr, script checks are pushed onto it instead of being performed - * inline. + * scripts & sigs, amounts). This does not modify the UTXO set. + * + * If pvChecks is not nullptr, script checks are pushed onto it instead of being + * performed inline. Any script checks which are not necessary (eg due to script + * execution cache hits) are, obviously, not pushed onto pvChecks/run. + * + * Setting sigCacheStore/scriptCacheStore to false will remove elements from the + * corresponding cache which are matched. This is useful for checking blocks + * where we will likely never need the cache entry again. */ static bool CheckInputs(const CTransaction &tx, CValidationState &state, const CCoinsViewCache &inputs, bool fScriptChecks, - uint32_t flags, bool cacheStore, + uint32_t flags, bool sigCacheStore, + bool scriptCacheStore, const PrecomputedTransactionData &txdata, std::vector *pvChecks) { assert(!tx.IsCoinBase()); @@ -1400,6 +1411,15 @@ return true; } + // First check if script executions have been cached with the same flags. + // 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)) { + return true; + } + for (size_t i = 0; i < tx.vin.size(); i++) { const COutPoint &prevout = tx.vin[i].prevout; const Coin &coin = inputs.AccessCoin(prevout); @@ -1414,7 +1434,7 @@ const CAmount amount = coin.GetTxOut().nValue; // Verify signature - CScriptCheck check(scriptPubKey, amount, tx, i, flags, cacheStore, + CScriptCheck check(scriptPubKey, amount, tx, i, flags, sigCacheStore, txdata); if (pvChecks) { pvChecks->push_back(std::move(check)); @@ -1428,7 +1448,7 @@ CScriptCheck check2(scriptPubKey, amount, tx, i, flags & ~STANDARD_NOT_MANDATORY_VERIFY_FLAGS, - cacheStore, txdata); + sigCacheStore, txdata); if (check2()) { return state.Invalid( false, REJECT_NONSTANDARD, @@ -1450,6 +1470,12 @@ } } + if (scriptCacheStore && !pvChecks) { + // We executed all of the provided scripts, and were told to cache the + // result. Do so now. + AddKeyInScriptCache(hashCacheEntry); + } + return true; } @@ -2002,8 +2028,8 @@ std::vector vChecks; if (!CheckInputs(tx, state, view, fScriptChecks, flags, - fCacheResults, PrecomputedTransactionData(tx), - &vChecks)) { + fCacheResults, fCacheResults, + PrecomputedTransactionData(tx), &vChecks)) { return error("ConnectBlock(): CheckInputs on %s failed with %s", tx.GetId().ToString(), FormatStateMessage(state)); }