From 2d90330d8c731273a9f50eb82eaa6d4bcc7b6fb8 Mon Sep 17 00:00:00 2001 From: Gavin Andresen Date: Wed, 16 May 2012 15:57:04 -0400 Subject: [PATCH] Cache signature verifications Create a maximum-10MB signature verification result cache. This should almost double the number of transactions that can be processed on a given CPU, because before this change ECDSA signatures were verified when transactions were added to the memory pool and then again when they appeared in a block. --- src/key.cpp | 68 +++++++++++++++++++++++++++++++++++ src/test/DoS_tests.cpp | 93 +++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 160 insertions(+), 1 deletions(-) diff --git a/src/key.cpp b/src/key.cpp index ece835d..ac7ac4d 100644 --- a/src/key.cpp +++ b/src/key.cpp @@ -2,10 +2,14 @@ // Distributed under the MIT/X11 software license, see the accompanying // file license.txt or http://www.opensource.org/licenses/mit-license.php. +#include + +#include #include #include #include "key.h" +#include "util.h" // Generate a private key from just the secret parameter int EC_KEY_regenerate_key(EC_KEY *eckey, BIGNUM *priv_key) @@ -347,21 +351,85 @@ bool CKey::SetCompactSignature(uint256 hash, const std::vector& v return false; } +// Valid signature cache, to avoid doing expensive ECDSA signature checking +// twice for every transaction (once when accepted into memory pool, and +// again when accepted into the block chain) + +// sigdata_type is (signature hash, signature, public key): +typedef boost::tuple, std::vector > sigdata_type; +static std::set< sigdata_type> setValidSigCache; +static CCriticalSection cs_sigcache; + +static bool +GetValidSigCache(uint256 hash, const std::vector& vchSig, const std::vector& pubKey) +{ + LOCK(cs_sigcache); + + sigdata_type k(hash, vchSig, pubKey); + std::set::iterator mi = setValidSigCache.find(k); + if (mi != setValidSigCache.end()) + return true; + return false; +} + +static void +SetValidSigCache(uint256 hash, const std::vector& vchSig, const std::vector& pubKey) +{ + // DoS prevention: limit cache size to less than 10MB + // (~200 bytes per cache entry times 50,000 entries) + // Since there are a maximum of 20,000 signature operations per block + // 50,000 is a reasonable default. + int64 nMaxCacheSize = GetArg("-maxsigcachesize", 50000); + if (nMaxCacheSize <= 0) return; + + LOCK(cs_sigcache); + + while (setValidSigCache.size() > nMaxCacheSize) + { + // Evict a random entry. Random because that helps + // foil would-be DoS attackers who might try to pre-generate + // and re-use a set of valid signatures just-slightly-greater + // than our cache size. + uint256 randomHash = GetRandHash(); + std::vector unused; + std::set::iterator it = + setValidSigCache.lower_bound(sigdata_type(randomHash, unused, unused)); + if (it == setValidSigCache.end()) + it = setValidSigCache.begin(); + setValidSigCache.erase(*it); + } + + sigdata_type k(hash, vchSig, pubKey); + setValidSigCache.insert(k); +} + + bool CKey::Verify(uint256 hash, const std::vector& vchSig) { + if (GetValidSigCache(hash, vchSig, GetPubKey())) + return true; + // -1 = error, 0 = bad sig, 1 = good if (ECDSA_verify(0, (unsigned char*)&hash, sizeof(hash), &vchSig[0], vchSig.size(), pkey) != 1) return false; + + // good sig + SetValidSigCache(hash, vchSig, GetPubKey()); return true; } bool CKey::VerifyCompact(uint256 hash, const std::vector& vchSig) { + if (GetValidSigCache(hash, vchSig, GetPubKey())) + return true; + CKey key; if (!key.SetCompactSignature(hash, vchSig)) return false; if (GetPubKey() != key.GetPubKey()) return false; + + SetValidSigCache(hash, vchSig, GetPubKey()); return true; } diff --git a/src/test/DoS_tests.cpp b/src/test/DoS_tests.cpp index cea4577..2e418b3 100644 --- a/src/test/DoS_tests.cpp +++ b/src/test/DoS_tests.cpp @@ -1,7 +1,10 @@ // // Unit tests for denial-of-service detection/prevention code // +#include + #include // for 'map_list_of()' +#include #include #include @@ -57,7 +60,7 @@ BOOST_AUTO_TEST_CASE(DoS_banscore) BOOST_CHECK(!CNode::IsBanned(addr1)); dummyNode1.Misbehaving(1); BOOST_CHECK(CNode::IsBanned(addr1)); - mapArgs["-banscore"] = "100"; + mapArgs.erase("-banscore"); } BOOST_AUTO_TEST_CASE(DoS_bantime) @@ -228,4 +231,92 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans) BOOST_CHECK(mapOrphanTransactionsByPrev.empty()); } +BOOST_AUTO_TEST_CASE(DoS_checkSig) +{ + // Test signature caching code (see key.cpp Verify() methods) + + CKey key; + key.MakeNewKey(true); + CBasicKeyStore keystore; + keystore.AddKey(key); + + // 100 orphan transactions: + static const int NPREV=100; + CTransaction orphans[NPREV]; + for (int i = 0; i < NPREV; i++) + { + CTransaction& tx = orphans[i]; + tx.vin.resize(1); + tx.vin[0].prevout.n = 0; + tx.vin[0].prevout.hash = GetRandHash(); + tx.vin[0].scriptSig << OP_1; + tx.vout.resize(1); + tx.vout[0].nValue = 1*CENT; + tx.vout[0].scriptPubKey.SetBitcoinAddress(key.GetPubKey()); + + CDataStream ds(SER_DISK, CLIENT_VERSION); + ds << tx; + AddOrphanTx(ds); + } + + // Create a transaction that depends on orphans: + CTransaction tx; + tx.vout.resize(1); + tx.vout[0].nValue = 1*CENT; + tx.vout[0].scriptPubKey.SetBitcoinAddress(key.GetPubKey()); + tx.vin.resize(NPREV); + for (int j = 0; j < tx.vin.size(); j++) + { + tx.vin[j].prevout.n = 0; + tx.vin[j].prevout.hash = orphans[j].GetHash(); + } + // Creating signatures primes the cache: + boost::posix_time::ptime mst1 = boost::posix_time::microsec_clock::local_time(); + for (int j = 0; j < tx.vin.size(); j++) + BOOST_CHECK(SignSignature(keystore, orphans[j], tx, j)); + boost::posix_time::ptime mst2 = boost::posix_time::microsec_clock::local_time(); + boost::posix_time::time_duration msdiff = mst2 - mst1; + long nOneValidate = msdiff.total_milliseconds(); + if (fDebug) printf("DoS_Checksig sign: %ld\n", nOneValidate); + + // ... now validating repeatedly should be quick: + // 2.8GHz machine, -g build: Sign takes ~760ms, + // uncached Verify takes ~250ms, cached Verify takes ~50ms + // (for 100 single-signature inputs) + mst1 = boost::posix_time::microsec_clock::local_time(); + for (int i = 0; i < 5; i++) + for (int j = 0; j < tx.vin.size(); j++) + BOOST_CHECK(VerifySignature(orphans[j], tx, j, true, SIGHASH_ALL)); + mst2 = boost::posix_time::microsec_clock::local_time(); + msdiff = mst2 - mst1; + long nManyValidate = msdiff.total_milliseconds(); + if (fDebug) printf("DoS_Checksig five: %ld\n", nManyValidate); + + BOOST_CHECK_MESSAGE(nManyValidate < nOneValidate, "Signature cache timing failed"); + + // Empty a signature, validation should fail: + CScript save = tx.vin[0].scriptSig; + tx.vin[0].scriptSig = CScript(); + BOOST_CHECK(!VerifySignature(orphans[0], tx, 0, true, SIGHASH_ALL)); + tx.vin[0].scriptSig = save; + + // Swap signatures, validation should fail: + std::swap(tx.vin[0].scriptSig, tx.vin[1].scriptSig); + BOOST_CHECK(!VerifySignature(orphans[0], tx, 0, true, SIGHASH_ALL)); + BOOST_CHECK(!VerifySignature(orphans[1], tx, 1, true, SIGHASH_ALL)); + std::swap(tx.vin[0].scriptSig, tx.vin[1].scriptSig); + + // Exercise -maxsigcachesize code: + mapArgs["-maxsigcachesize"] = "10"; + // Generate a new, different signature for vin[0] to trigger cache clear: + CScript oldSig = tx.vin[0].scriptSig; + BOOST_CHECK(SignSignature(keystore, orphans[0], tx, 0)); + BOOST_CHECK(tx.vin[0].scriptSig != oldSig); + for (int j = 0; j < tx.vin.size(); j++) + BOOST_CHECK(VerifySignature(orphans[j], tx, j, true, SIGHASH_ALL)); + mapArgs.erase("-maxsigcachesize"); + + LimitOrphanTxSize(0); +} + BOOST_AUTO_TEST_SUITE_END() -- 1.7.1