Fix dangerous condition in ModifyNewCoins.

We were marking coins FRESH before being sure they were not overwriting dirty undo data. This condition was never reached in existing code because undo data was always flushed before UpdateCoins was called with new transactions, but could have been exposed in an otherwise safe refactor.
Clarify in the comments the assumptions made in ModifyNewCoins.
Add ability to undo transactions to UpdateCoins unit test.
Thanks to Russ Yanofsky for suggestion on how to make logic clearer and fixing up the ccoins_modify_new test cases.

1 files changed, 144 insertions, 55 deletions

diff --git a/src/test/coins_tests.cpp b/src/test/coins_tests.cpp
index 09fe0bf158..94a11d1768 100644
--- a/src/test/coins_tests.cpp
+++ b/src/test/coins_tests.cpp
@@ -5,6 +5,7 @@
 #include "coins.h"
 #include "script/standard.h"
 #include "uint256.h"
+#include "undo.h"
 #include "utilstrencodings.h"
 #include "test/test_bitcoin.h"
 #include "test/test_random.h"
@@ -16,6 +17,9 @@
 
 #include <boost/test/unit_test.hpp>
 
+bool ApplyTxInUndo(const CTxInUndo& undo, CCoinsViewCache& view, const COutPoint& out);
+void UpdateCoins(const CTransaction& tx, CCoinsViewCache& inputs, CTxUndo &txundo, int nHeight);
+
 namespace
 {
 class CCoinsViewTest : public CCoinsView
@@ -213,6 +217,22 @@ BOOST_AUTO_TEST_CASE(coins_cache_simulation_test)
     BOOST_CHECK(missed_an_entry);
 }
 
+typedef std::tuple<CTransaction,CTxUndo,CCoins> TxData;
+// Store of all necessary tx and undo data for next test
+std::map<uint256, TxData> alltxs;
+
+TxData &FindRandomFrom(const std::set<uint256> &txidset) {
+    assert(txidset.size());
+    std::set<uint256>::iterator txIt = txidset.lower_bound(GetRandHash());
+    if (txIt == txidset.end()) {
+        txIt = txidset.begin();
+    }
+    std::map<uint256, TxData>::iterator txdit = alltxs.find(*txIt);
+    assert(txdit != alltxs.end());
+    return txdit->second;
+}
+
+
 // This test is similar to the previous test
 // except the emphasis is on testing the functionality of UpdateCoins
 // random txs are created and UpdateCoins is used to update the cache stack
@@ -229,77 +249,139 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
     std::vector<CCoinsViewCacheTest*> stack; // A stack of CCoinsViewCaches on top.
     stack.push_back(new CCoinsViewCacheTest(&base)); // Start with one cache.
 
-    // Track the txids we've used and whether they have been spent or not
-    std::map<uint256, CAmount> coinbaseids;
-    std::set<uint256> alltxids;
+    // Track the txids we've used in various sets
+    std::set<uint256> coinbaseids;
+    std::set<uint256> disconnectedids;
     std::set<uint256> duplicateids;
+    std::set<uint256> utxoset;
 
     for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) {
-        {
+        uint32_t randiter = insecure_rand();
+
+        // 19/20 txs add a new transaction
+        if (randiter % 20 < 19) {
             CMutableTransaction tx;
             tx.vin.resize(1);
             tx.vout.resize(1);
             tx.vout[0].nValue = i; //Keep txs unique unless intended to duplicate
             unsigned int height = insecure_rand();
+            CCoins oldcoins;
 
-            // 1/10 times create a coinbase
-            if (insecure_rand() % 10 == 0 || coinbaseids.size() < 10) {
-                // 1/100 times create a duplicate coinbase
+            // 2/20 times create a new coinbase
+            if (randiter % 20 < 2 || coinbaseids.size() < 10) {
+                // 1/10 of those times create a duplicate coinbase
                 if (insecure_rand() % 10 == 0 && coinbaseids.size()) {
-                    std::map<uint256, CAmount>::iterator coinbaseIt = coinbaseids.lower_bound(GetRandHash());
-                    if (coinbaseIt == coinbaseids.end()) {
-                        coinbaseIt = coinbaseids.begin();
-                    }
-                    //Use same random value to have same hash and be a true duplicate
-                    tx.vout[0].nValue = coinbaseIt->second;
-                    assert(tx.GetHash() == coinbaseIt->first);
-                    duplicateids.insert(coinbaseIt->first);
+                    TxData &txd = FindRandomFrom(coinbaseids);
+                    // Reuse the exact same coinbase
+                    tx = std::get<0>(txd);
+                    // shouldn't be available for reconnection if its been duplicated
+                    disconnectedids.erase(tx.GetHash());
+
+                    duplicateids.insert(tx.GetHash());
                 }
                 else {
-                    coinbaseids[tx.GetHash()] = tx.vout[0].nValue;
+                    coinbaseids.insert(tx.GetHash());
                 }
                 assert(CTransaction(tx).IsCoinBase());
             }
-            // 9/10 times create a regular tx
+
+            // 17/20 times reconnect previous or add a regular tx
             else {
+
                 uint256 prevouthash;
-                // equally likely to spend coinbase or non coinbase
-                std::set<uint256>::iterator txIt = alltxids.lower_bound(GetRandHash());
-                if (txIt == alltxids.end()) {
-                    txIt = alltxids.begin();
+                // 1/20 times reconnect a previously disconnected tx
+                if (randiter % 20 == 2 && disconnectedids.size()) {
+                    TxData &txd = FindRandomFrom(disconnectedids);
+                    tx = std::get<0>(txd);
+                    prevouthash = tx.vin[0].prevout.hash;
+                    if (!CTransaction(tx).IsCoinBase() && !utxoset.count(prevouthash)) {
+                        disconnectedids.erase(tx.GetHash());
+                        continue;
+                    }
+
+                    // If this tx is already IN the UTXO, then it must be a coinbase, and it must be a duplicate
+                    if (utxoset.count(tx.GetHash())) {
+                        assert(CTransaction(tx).IsCoinBase());
+                        assert(duplicateids.count(tx.GetHash()));
+                    }
+                    disconnectedids.erase(tx.GetHash());
                 }
-                prevouthash = *txIt;
 
-                // Construct the tx to spend the coins of prevouthash
-                tx.vin[0].prevout.hash = prevouthash;
-                tx.vin[0].prevout.n = 0;
+                // 16/20 times create a regular tx
+                else {
+                    TxData &txd = FindRandomFrom(utxoset);
+                    prevouthash = std::get<0>(txd).GetHash();
 
+                    // Construct the tx to spend the coins of prevouthash
+                    tx.vin[0].prevout.hash = prevouthash;
+                    tx.vin[0].prevout.n = 0;
+                    assert(!CTransaction(tx).IsCoinBase());
+                }
+                // In this simple test coins only have two states, spent or unspent, save the unspent state to restore
+                oldcoins = result[prevouthash];
                 // Update the expected result of prevouthash to know these coins are spent
-                CCoins& oldcoins = result[prevouthash];
-                oldcoins.Clear();
+                result[prevouthash].Clear();
 
-                // It is of particular importance here that once we spend a coinbase tx hash
-                // it is no longer available to be duplicated (or spent again)
-                // BIP 34 in conjunction with enforcing BIP 30 (at least until BIP 34 was active)
-                // results in the fact that no coinbases were duplicated after they were already spent
-                alltxids.erase(prevouthash);
-                coinbaseids.erase(prevouthash);
+                utxoset.erase(prevouthash);
 
                 // The test is designed to ensure spending a duplicate coinbase will work properly
                 // if that ever happens and not resurrect the previously overwritten coinbase
                 if (duplicateids.count(prevouthash))
                     spent_a_duplicate_coinbase = true;
 
-                assert(!CTransaction(tx).IsCoinBase());
             }
-            // Track this tx to possibly spend later
-            alltxids.insert(tx.GetHash());
-
             // Update the expected result to know about the new output coins
-            CCoins &coins = result[tx.GetHash()];
-            coins.FromTx(tx, height);
+            result[tx.GetHash()].FromTx(tx, height);
+
+            // Call UpdateCoins on the top cache
+            CTxUndo undo;
+            UpdateCoins(tx, *(stack.back()), undo, height);
 
-            UpdateCoins(tx, *(stack.back()), height);
+            // Update the utxo set for future spends
+            utxoset.insert(tx.GetHash());
+
+            // Track this tx and undo info to use later
+            alltxs.insert(std::make_pair(tx.GetHash(),std::make_tuple(tx,undo,oldcoins)));
+        }
+
+        //1/20 times undo a previous transaction
+        else if (utxoset.size()) {
+            TxData &txd = FindRandomFrom(utxoset);
+
+            CTransaction &tx = std::get<0>(txd);
+            CTxUndo &undo = std::get<1>(txd);
+            CCoins &origcoins = std::get<2>(txd);
+
+            uint256 undohash = tx.GetHash();
+
+            // Update the expected result
+            // Remove new outputs
+            result[undohash].Clear();
+            // If not coinbase restore prevout
+            if (!tx.IsCoinBase()) {
+                result[tx.vin[0].prevout.hash] = origcoins;
+            }
+
+            // Disconnect the tx from the current UTXO
+            // See code in DisconnectBlock
+            // remove outputs
+            {
+                CCoinsModifier outs = stack.back()->ModifyCoins(undohash);
+                outs->Clear();
+            }
+            // restore inputs
+            if (!tx.IsCoinBase()) {
+                const COutPoint &out = tx.vin[0].prevout;
+                const CTxInUndo &undoin = undo.vprevout[0];
+                ApplyTxInUndo(undoin, *(stack.back()), out);
+            }
+            // Store as a candidate for reconnection
+            disconnectedids.insert(undohash);
+
+            // Update the utxoset
+            utxoset.erase(undohash);
+            if (!tx.IsCoinBase())
+                utxoset.insert(tx.vin[0].prevout.hash);
         }
 
         // Once every 1000 iterations and at the end, verify the full cache.
@@ -308,9 +390,9 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
                 const CCoins* coins = stack.back()->AccessCoins(it->first);
                 if (coins) {
                     BOOST_CHECK(*coins == it->second);
-                 } else {
+                } else {
                     BOOST_CHECK(it->second.IsPruned());
-                 }
+                }
             }
         }
 
@@ -334,7 +416,7 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
                     tip = stack.back();
                 }
                 stack.push_back(new CCoinsViewCacheTest(tip));
-           }
+            }
         }
     }
 
@@ -420,6 +502,7 @@ BOOST_AUTO_TEST_CASE(ccoins_serialization)
 const static uint256 TXID;
 const static CAmount PRUNED = -1;
 const static CAmount ABSENT = -2;
+const static CAmount FAIL = -3;
 const static CAmount VALUE1 = 100;
 const static CAmount VALUE2 = 200;
 const static CAmount VALUE3 = 300;
@@ -630,11 +713,17 @@ BOOST_AUTO_TEST_CASE(ccoins_modify)
 void CheckModifyNewCoinsBase(CAmount base_value, CAmount cache_value, CAmount modify_value, CAmount expected_value, char cache_flags, char expected_flags, bool coinbase)
 {
     SingleEntryCacheTest test(base_value, cache_value, cache_flags);
-    SetCoinsValue(modify_value, *test.cache.ModifyNewCoins(TXID, coinbase));
 
     CAmount result_value;
     char result_flags;
-    GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
+    try {
+        SetCoinsValue(modify_value, *test.cache.ModifyNewCoins(TXID, coinbase));
+        GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
+    } catch (std::logic_error& e) {
+        result_value = FAIL;
+        result_flags = NO_ENTRY;
+    }
+
     BOOST_CHECK_EQUAL(result_value, expected_value);
     BOOST_CHECK_EQUAL(result_flags, expected_flags);
 }
@@ -669,7 +758,7 @@ BOOST_AUTO_TEST_CASE(ccoins_modify_new)
     CheckModifyNewCoins(PRUNED, PRUNED, PRUNED, 0          , DIRTY      , true );
     CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, FRESH      , NO_ENTRY   , false);
     CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, FRESH      , NO_ENTRY   , true );
-    CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, DIRTY      , NO_ENTRY   , false);
+    CheckModifyNewCoins(PRUNED, PRUNED, PRUNED, DIRTY      , DIRTY      , false);
     CheckModifyNewCoins(PRUNED, PRUNED, PRUNED, DIRTY      , DIRTY      , true );
     CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY   , false);
     CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY   , true );
@@ -677,25 +766,25 @@ BOOST_AUTO_TEST_CASE(ccoins_modify_new)
     CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, 0          , DIRTY      , true );
     CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, FRESH      , DIRTY|FRESH, false);
     CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, FRESH      , DIRTY|FRESH, true );
-    CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY      , DIRTY|FRESH, false);
+    CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY      , DIRTY      , false);
     CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY      , DIRTY      , true );
     CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, false);
     CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, true );
-    CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, 0          , NO_ENTRY   , false);
+    CheckModifyNewCoins(VALUE2, PRUNED, FAIL  , 0          , NO_ENTRY   , false);
     CheckModifyNewCoins(VALUE2, PRUNED, PRUNED, 0          , DIRTY      , true );
-    CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, FRESH      , NO_ENTRY   , false);
+    CheckModifyNewCoins(VALUE2, PRUNED, FAIL  , FRESH      , NO_ENTRY   , false);
     CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, FRESH      , NO_ENTRY   , true );
-    CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, DIRTY      , NO_ENTRY   , false);
+    CheckModifyNewCoins(VALUE2, PRUNED, FAIL  , DIRTY      , NO_ENTRY   , false);
     CheckModifyNewCoins(VALUE2, PRUNED, PRUNED, DIRTY      , DIRTY      , true );
-    CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY   , false);
+    CheckModifyNewCoins(VALUE2, PRUNED, FAIL  , DIRTY|FRESH, NO_ENTRY   , false);
     CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY   , true );
-    CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, 0          , DIRTY|FRESH, false);
+    CheckModifyNewCoins(VALUE2, VALUE3, FAIL  , 0          , NO_ENTRY   , false);
     CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, 0          , DIRTY      , true );
-    CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, FRESH      , DIRTY|FRESH, false);
+    CheckModifyNewCoins(VALUE2, VALUE3, FAIL  , FRESH      , NO_ENTRY   , false);
     CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, FRESH      , DIRTY|FRESH, true );
-    CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY      , DIRTY|FRESH, false);
+    CheckModifyNewCoins(VALUE2, VALUE3, FAIL  , DIRTY      , NO_ENTRY   , false);
     CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY      , DIRTY      , true );
-    CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, false);
+    CheckModifyNewCoins(VALUE2, VALUE3, FAIL  , DIRTY|FRESH, NO_ENTRY   , false);
     CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, true );
 }