Merge pull request #6077

517e6dd Unit test doublespends in new blocks (Gavin Andresen)
17b1142 Cache transaction validation successes (Pieter Wuille)

8 files changed, 330 insertions, 6 deletions

diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 0997148117..f9384a09a4 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -73,6 +73,7 @@ BITCOIN_TESTS =\
   test/test_bitcoin.h \
   test/timedata_tests.cpp \
   test/transaction_tests.cpp \
+  test/txvalidationcache_tests.cpp \
   test/uint256_tests.cpp \
   test/univalue_tests.cpp \
   test/util_tests.cpp
diff --git a/src/main.cpp b/src/main.cpp
index fefeabeb64..7477d08b18 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -1277,6 +1277,9 @@ int GetSpendHeight(const CCoinsViewCache& inputs)
     return pindexPrev->nHeight + 1;
 }
 
+static mrumap<uint256, unsigned int> cacheCheck(2 * MAX_BLOCK_SIZE / CTransaction().GetSerializeSize(SER_NETWORK, PROTOCOL_VERSION));
+static boost::mutex cs_cacheCheck;
+
 namespace Consensus {
 bool CheckTxInputs(const CTransaction& tx, CValidationState& state, const CCoinsViewCache& inputs, int nSpendHeight)
 {
@@ -1331,6 +1334,17 @@ bool CheckInputs(const CTransaction& tx, CValidationState &state, const CCoinsVi
 {
     if (!tx.IsCoinBase())
     {
+        if (fScriptChecks) {
+            boost::unique_lock<boost::mutex> lock(cs_cacheCheck);
+            mrumap<uint256, unsigned int>::const_iterator iter = cacheCheck.find(tx.GetHash());
+            if (iter != cacheCheck.end()) {
+                // The following test relies on the fact that all script validation flags are softforks (i.e. an extra bit set cannot cause a false result to become true).
+                if ((iter->second & flags) == flags) {
+                    return true;
+                }
+            }
+        }
+
         if (!Consensus::CheckTxInputs(tx, state, inputs, GetSpendHeight(inputs)))
             return false;
 
@@ -1381,6 +1395,11 @@ bool CheckInputs(const CTransaction& tx, CValidationState &state, const CCoinsVi
         }
     }
 
+    if (cacheStore && fScriptChecks && pvChecks == NULL) {
+        boost::unique_lock<boost::mutex> lock(cs_cacheCheck);
+        cacheCheck.insert(tx.GetHash(), flags);
+    }
+
     return true;
 }
 
@@ -2101,6 +2120,13 @@ bool static ConnectTip(CValidationState &state, CBlockIndex *pindexNew, CBlock *
     BOOST_FOREACH(const CTransaction &tx, pblock->vtx) {
         SyncWithWallets(tx, pblock);
     }
+    // Erase block's transactions from the validation cache
+    {
+        boost::unique_lock<boost::mutex> lock(cs_cacheCheck);
+        BOOST_FOREACH(const CTransaction &tx, pblock->vtx) {
+            cacheCheck.erase(tx.GetHash());
+        }
+    }
 
     int64_t nTime6 = GetTimeMicros(); nTimePostConnect += nTime6 - nTime5; nTimeTotal += nTime6 - nTime1;
     LogPrint("bench", "  - Connect postprocess: %.2fms [%.2fs]\n", (nTime6 - nTime5) * 0.001, nTimePostConnect * 0.000001);
diff --git a/src/mruset.h b/src/mruset.h
index 398aa173bf..9dff5694ba 100644
--- a/src/mruset.h
+++ b/src/mruset.h
@@ -9,6 +9,10 @@
 #include <vector>
 #include <utility>
 
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+
 /** STL-like set container that only keeps the most recent N elements. */
 template <typename T>
 class mruset
@@ -62,4 +66,60 @@ public:
     size_type max_size() const { return nMaxSize; }
 };
 
+/** STL-like map container that only keeps the most recent N elements. */
+template <typename K, typename V>
+class mrumap
+{
+private:
+    struct key_extractor {
+        typedef K result_type;
+        const result_type& operator()(const std::pair<K, V>& e) const { return e.first; }
+        result_type& operator()(std::pair<K, V>* e) const { return e->first; }
+    };
+
+    typedef boost::multi_index_container<
+        std::pair<K, V>,
+        boost::multi_index::indexed_by<
+            boost::multi_index::sequenced<>,
+            boost::multi_index::ordered_unique<key_extractor>
+        >
+    > map_type;
+
+public:
+    typedef K key_type;
+    typedef std::pair<K, V> value_type;
+    typedef typename map_type::iterator iterator;
+    typedef typename map_type::const_iterator const_iterator;
+    typedef typename map_type::size_type size_type;
+
+protected:
+    map_type m_;
+    size_type max_size_;
+
+public:
+    mrumap(size_type max_size_in = 1) { clear(max_size_in); }
+    iterator begin() { return m_.begin(); }
+    iterator end() { return m_.end(); }
+    const_iterator begin() const { return m_.begin(); }
+    const_iterator end() const { return m_.end(); }
+    size_type size() const { return m_.size(); }
+    bool empty() const { return m_.empty(); }
+    iterator find(const key_type& key) { return m_.template project<0>(boost::get<1>(m_).find(key)); }
+    const_iterator find(const key_type& key) const { return m_.template project<0>(boost::get<1>(m_).find(key)); }
+    size_type count(const key_type& key) const { return boost::get<1>(m_).count(key); }
+    void clear(size_type max_size_in) { m_.clear(); max_size_ = max_size_in; }
+    std::pair<iterator, bool> insert(const K& key, const V& value) 
+    {
+        std::pair<K, V> elem(key, value);
+        std::pair<iterator, bool> p = m_.push_front(elem);
+        if (p.second && m_.size() > max_size_) {
+            m_.pop_back();
+        }
+        return p;
+    }
+    void erase(iterator it) { m_.erase(it); }
+    void erase(const key_type& k) { boost::get<1>(m_).erase(k); }
+    size_type max_size() const { return max_size_; }
+};
+
 #endif // BITCOIN_MRUSET_H
diff --git a/src/test/README.md b/src/test/README.md
index 7efce6f052..e36112bd4f 100644
--- a/src/test/README.md
+++ b/src/test/README.md
@@ -18,4 +18,16 @@ uint256_tests.cpp.
 
 For further reading, I found the following website to be helpful in
 explaining how the boost unit test framework works:
-[http://www.alittlemadness.com/2009/03/31/c-unit-testing-with-boosttest/](http://www.alittlemadness.com/2009/03/31/c-unit-testing-with-boosttest/).
\ No newline at end of file
+[http://www.alittlemadness.com/2009/03/31/c-unit-testing-with-boosttest/](http://www.alittlemadness.com/2009/03/31/c-unit-testing-with-boosttest/).
+
+test_bitcoin has some built-in command-line arguments; for
+example, to run just the getarg_tests verbosely:
+
+    test_bitcoin --log_level=all --run_test=getarg_tests
+
+... or to run just the doubledash test:
+
+    test_bitcoin --run_test=getarg_tests/doubledash
+
+Run  test_bitcoin --help   for the full list.
+
diff --git a/src/test/mruset_tests.cpp b/src/test/mruset_tests.cpp
index 2b68f8899e..3c06689168 100644
--- a/src/test/mruset_tests.cpp
+++ b/src/test/mruset_tests.cpp
@@ -78,4 +78,68 @@ BOOST_AUTO_TEST_CASE(mruset_test)
     }
 }
 
+BOOST_AUTO_TEST_CASE(mrumap_test)
+{
+    // The mrumap being tested.
+    mrumap<int, char> mru(5000);
+
+    // Run the test 10 times.
+    for (int test = 0; test < 10; test++) {
+        // Reset mru.
+        mru.clear(5000);
+
+        // A deque + set to simulate the mruset.
+        std::deque<int> rep;
+        std::map<int, char> all;
+
+        // Insert 10000 random integers below 15000.
+        for (int j=0; j<10000; j++) {
+            int add = GetRandInt(15000);
+            char val = (char)GetRandInt(256);
+            mru.insert(add, val);
+
+            // Add the number to rep/all as well.
+            if (all.count(add) == 0) {
+               all.insert(std::make_pair<int, char>(add, val));
+               rep.push_back(add);
+               if (all.size() == 5001) {
+                   all.erase(rep.front());
+                   rep.pop_front();
+               }
+            }
+
+            if (GetRandInt(5) == 0) {
+                // With 20% chance: remove an item
+                int pos = GetRandInt(rep.size());
+                std::deque<int>::iterator it = rep.begin();
+                while (pos--) { it++; }
+                int delval = *it;
+                mru.erase(delval);
+                all.erase(delval);
+                rep.erase(it);
+            }
+
+            // Do a full comparison between mru and the simulated mru every 1000 and every 5001 elements.
+            if (j % 1000 == 0 || j % 5001 == 0) {
+                // Check that all elements that should be in there, are in there.
+                BOOST_FOREACH(int x, rep) {
+                    BOOST_CHECK(mru.count(x));
+                    BOOST_CHECK(mru.find(x)->second == all[x]);
+                }
+
+                // Check that all elements that are in there, should be in there.
+                for (mrumap<int, char>::iterator it = mru.begin(); it != mru.end(); it++) {
+                    BOOST_CHECK(all.count(it->first));
+                    BOOST_CHECK(all[it->first] == it->second);
+                }
+
+                for (int t = 0; t < 10; t++) {
+                    int r = GetRandInt(15000);
+                    BOOST_CHECK(all.count(r) == mru.count(r));
+                }
+            }
+        }
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/test_bitcoin.cpp b/src/test/test_bitcoin.cpp
index ba616365f2..8d81275a6f 100644
--- a/src/test/test_bitcoin.cpp
+++ b/src/test/test_bitcoin.cpp
@@ -7,8 +7,12 @@
 #include "test_bitcoin.h"
 
 #include "chainparams.h"
+#include "consensus/consensus.h"
+#include "consensus/validation.h"
 #include "key.h"
 #include "main.h"
+#include "miner.h"
+#include "pubkey.h"
 #include "random.h"
 #include "txdb.h"
 #include "ui_interface.h"
@@ -28,20 +32,22 @@ CWallet* pwalletMain;
 extern bool fPrintToConsole;
 extern void noui_connect();
 
-BasicTestingSetup::BasicTestingSetup()
+BasicTestingSetup::BasicTestingSetup(CBaseChainParams::Network network)
 {
         ECC_Start();
         SetupEnvironment();
         fPrintToDebugLog = false; // don't want to write to debug.log file
         fCheckBlockIndex = true;
-        SelectParams(CBaseChainParams::MAIN);
+        SelectParams(network);
+        noui_connect();
 }
+
 BasicTestingSetup::~BasicTestingSetup()
 {
         ECC_Stop();
 }
 
-TestingSetup::TestingSetup()
+TestingSetup::TestingSetup(CBaseChainParams::Network network) : BasicTestingSetup(network)
 {
 #ifdef ENABLE_WALLET
         bitdb.MakeMock();
@@ -87,6 +93,51 @@ TestingSetup::~TestingSetup()
         boost::filesystem::remove_all(pathTemp);
 }
 
+TestChain100Setup::TestChain100Setup() : TestingSetup(CBaseChainParams::REGTEST)
+{
+    // Generate a 100-block chain:
+    coinbaseKey.MakeNewKey(true);
+    CScript scriptPubKey = CScript() <<  ToByteVector(coinbaseKey.GetPubKey()) << OP_CHECKSIG;
+    for (int i = 0; i < COINBASE_MATURITY; i++)
+    {
+        std::vector<CMutableTransaction> noTxns;
+        CBlock b = CreateAndProcessBlock(noTxns, scriptPubKey);
+        coinbaseTxns.push_back(b.vtx[0]);
+    }
+}
+
+//
+// Create a new block with just given transactions, coinbase paying to
+// scriptPubKey, and try to add it to the current chain.
+//
+CBlock
+TestChain100Setup::CreateAndProcessBlock(const std::vector<CMutableTransaction>& txns, const CScript& scriptPubKey)
+{
+    CBlockTemplate *pblocktemplate = CreateNewBlock(scriptPubKey);
+    CBlock& block = pblocktemplate->block;
+
+    // Replace mempool-selected txns with just coinbase plus passed-in txns:
+    block.vtx.resize(1);
+    BOOST_FOREACH(const CMutableTransaction& tx, txns)
+        block.vtx.push_back(tx);
+    // IncrementExtraNonce creates a valid coinbase and merkleRoot
+    unsigned int extraNonce = 0;
+    IncrementExtraNonce(&block, chainActive.Tip(), extraNonce);
+
+    while (!CheckProofOfWork(block.GetHash(), block.nBits, Params(CBaseChainParams::REGTEST).GetConsensus())) ++block.nNonce;
+
+    CValidationState state;
+    ProcessNewBlock(state, NULL, &block, true, NULL);
+
+    CBlock result = block;
+    delete pblocktemplate;
+    return result;
+}
+
+TestChain100Setup::~TestChain100Setup()
+{
+}
+
 void Shutdown(void* parg)
 {
   exit(0);
diff --git a/src/test/test_bitcoin.h b/src/test/test_bitcoin.h
index 2f75332d40..b9314d0611 100644
--- a/src/test/test_bitcoin.h
+++ b/src/test/test_bitcoin.h
@@ -1,6 +1,8 @@
 #ifndef BITCOIN_TEST_TEST_BITCOIN_H
 #define BITCOIN_TEST_TEST_BITCOIN_H
 
+#include "chainparamsbase.h"
+#include "key.h"
 #include "txdb.h"
 
 #include <boost/filesystem.hpp>
@@ -10,7 +12,7 @@
  * This just configures logging and chain parameters.
  */
 struct BasicTestingSetup {
-    BasicTestingSetup();
+    BasicTestingSetup(CBaseChainParams::Network network = CBaseChainParams::MAIN);
     ~BasicTestingSetup();
 };
 
@@ -23,8 +25,30 @@ struct TestingSetup: public BasicTestingSetup {
     boost::filesystem::path pathTemp;
     boost::thread_group threadGroup;
 
-    TestingSetup();
+    TestingSetup(CBaseChainParams::Network network = CBaseChainParams::MAIN);
     ~TestingSetup();
 };
 
+class CBlock;
+struct CMutableTransaction;
+class CScript;
+
+//
+// Testing fixture that pre-creates a
+// 100-block REGTEST-mode block chain
+//
+struct TestChain100Setup : public TestingSetup {
+    TestChain100Setup();
+
+    // Create a new block with just given transactions, coinbase paying to
+    // scriptPubKey, and try to add it to the current chain.
+    CBlock CreateAndProcessBlock(const std::vector<CMutableTransaction>& txns,
+                                 const CScript& scriptPubKey);
+
+    ~TestChain100Setup();
+
+    std::vector<CTransaction> coinbaseTxns; // For convenience, coinbase transactions
+    CKey coinbaseKey; // private/public key needed to spend coinbase transactions
+};
+
 #endif
diff --git a/src/test/txvalidationcache_tests.cpp b/src/test/txvalidationcache_tests.cpp
new file mode 100644
index 0000000000..edad18644e
--- /dev/null
+++ b/src/test/txvalidationcache_tests.cpp
@@ -0,0 +1,86 @@
+// Copyright (c) 2011-2014 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "consensus/validation.h"
+#include "key.h"
+#include "main.h"
+#include "miner.h"
+#include "pubkey.h"
+#include "txmempool.h"
+#include "random.h"
+#include "script/standard.h"
+#include "test/test_bitcoin.h"
+#include "utiltime.h"
+
+#include <boost/test/unit_test.hpp>
+
+BOOST_AUTO_TEST_SUITE(tx_validationcache_tests)
+
+static bool
+ToMemPool(CMutableTransaction& tx)
+{
+    LOCK(cs_main);
+
+    CValidationState state;
+    return AcceptToMemoryPool(mempool, state, tx, false, NULL, false);
+}
+
+BOOST_FIXTURE_TEST_CASE(tx_mempool_block_doublespend, TestChain100Setup)
+{
+    // Make sure skipping validation of transctions that were
+    // validated going into the memory pool does not allow
+    // double-spends in blocks to pass validation when they should not.
+
+    CScript scriptPubKey = CScript() <<  ToByteVector(coinbaseKey.GetPubKey()) << OP_CHECKSIG;
+
+    // Create a double-spend of mature coinbase txn:
+    std::vector<CMutableTransaction> spends;
+    spends.resize(2);
+    for (int i = 0; i < 2; i++)
+    {
+        spends[i].vin.resize(1);
+        spends[i].vin[0].prevout.hash = coinbaseTxns[0].GetHash();
+        spends[i].vin[0].prevout.n = 0;
+        spends[i].vout.resize(1);
+        spends[i].vout[0].nValue = 11*CENT;
+        spends[i].vout[0].scriptPubKey = scriptPubKey;
+
+        // Sign:
+        std::vector<unsigned char> vchSig;
+        uint256 hash = SignatureHash(scriptPubKey, spends[i], 0, SIGHASH_ALL);
+        BOOST_CHECK(coinbaseKey.Sign(hash, vchSig));
+        vchSig.push_back((unsigned char)SIGHASH_ALL);
+        spends[i].vin[0].scriptSig << vchSig;
+    }
+
+    CBlock block;
+
+    // Test 1: block with both of those transactions should be rejected.
+    block = CreateAndProcessBlock(spends, scriptPubKey);
+    BOOST_CHECK(chainActive.Tip()->GetBlockHash() != block.GetHash());
+
+    // Test 2: ... and should be rejected if spend1 is in the memory pool
+    BOOST_CHECK(ToMemPool(spends[0]));
+    block = CreateAndProcessBlock(spends, scriptPubKey);
+    BOOST_CHECK(chainActive.Tip()->GetBlockHash() != block.GetHash());
+    mempool.clear();
+
+    // Test 3: ... and should be rejected if spend2 is in the memory pool
+    BOOST_CHECK(ToMemPool(spends[1]));
+    block = CreateAndProcessBlock(spends, scriptPubKey);
+    BOOST_CHECK(chainActive.Tip()->GetBlockHash() != block.GetHash());
+    mempool.clear();
+
+    // Final sanity test: first spend in mempool, second in block, that's OK:
+    std::vector<CMutableTransaction> oneSpend;
+    oneSpend.push_back(spends[0]);
+    BOOST_CHECK(ToMemPool(spends[1]));
+    block = CreateAndProcessBlock(oneSpend, scriptPubKey);
+    BOOST_CHECK(chainActive.Tip()->GetBlockHash() == block.GetHash());
+    // spends[1] should have been removed from the mempool when the
+    // block with spends[0] is accepted:
+    BOOST_CHECK_EQUAL(mempool.size(), 0);
+}
+
+BOOST_AUTO_TEST_SUITE_END()