Switch CCoinsView and chainstate db from per-txid to per-txout

This patch makes several related changes:
* Changes the CCoinsView virtual methods (GetCoins, HaveCoins, ...)
  to be COutPoint/Coin-based rather than txid/CCoins-based.
* Changes the chainstate db to a new incompatible format that is also
  COutPoint/Coin based.
* Implements reconstruction code for hash_serialized_2.
* Adapts the coins_tests unit tests (thanks to Russell Yanofsky).

A side effect of the new CCoinsView model is that we can no longer
use the (unreliable) test for transaction outputs in the UTXO set
to determine whether we already have a particular transaction.

2 files changed, 109 insertions, 134 deletions

diff --git a/src/test/coins_tests.cpp b/src/test/coins_tests.cpp
index 3ad2625bab..8d519c644b 100644
--- a/src/test/coins_tests.cpp
+++ b/src/test/coins_tests.cpp
@@ -34,27 +34,27 @@ bool operator==(const Coin &a, const Coin &b) {
 class CCoinsViewTest : public CCoinsView
 {
     uint256 hashBestBlock_;
-    std::map<uint256, CCoins> map_;
+    std::map<COutPoint, Coin> map_;
 
 public:
-    bool GetCoins(const uint256& txid, CCoins& coins) const
+    bool GetCoins(const COutPoint& outpoint, Coin& coin) const
     {
-        std::map<uint256, CCoins>::const_iterator it = map_.find(txid);
+        std::map<COutPoint, Coin>::const_iterator it = map_.find(outpoint);
         if (it == map_.end()) {
             return false;
         }
-        coins = it->second;
-        if (coins.IsPruned() && insecure_rand() % 2 == 0) {
+        coin = it->second;
+        if (coin.IsPruned() && insecure_rand() % 2 == 0) {
             // Randomly return false in case of an empty entry.
             return false;
         }
         return true;
     }
 
-    bool HaveCoins(const uint256& txid) const
+    bool HaveCoins(const COutPoint& outpoint) const
     {
-        CCoins coins;
-        return GetCoins(txid, coins);
+        Coin coin;
+        return GetCoins(outpoint, coin);
     }
 
     uint256 GetBestBlock() const { return hashBestBlock_; }
@@ -106,7 +106,7 @@ static const unsigned int NUM_SIMULATION_ITERATIONS = 40000;
 // This is a large randomized insert/remove simulation test on a variable-size
 // stack of caches on top of CCoinsViewTest.
 //
-// It will randomly create/update/delete CCoins entries to a tip of caches, with
+// It will randomly create/update/delete Coin entries to a tip of caches, with
 // txids picked from a limited list of random 256-bit hashes. Occasionally, a
 // new tip is added to the stack of caches, or the tip is flushed and removed.
 //
@@ -124,7 +124,7 @@ BOOST_AUTO_TEST_CASE(coins_cache_simulation_test)
     bool missed_an_entry = false;
 
     // A simple map to track what we expect the cache stack to represent.
-    std::map<uint256, CCoins> result;
+    std::map<COutPoint, Coin> result;
 
     // The cache stack.
     CCoinsViewTest base; // A CCoinsViewTest at the bottom.
@@ -142,39 +142,38 @@ BOOST_AUTO_TEST_CASE(coins_cache_simulation_test)
         // Do a random modification.
         {
             uint256 txid = txids[insecure_rand() % txids.size()]; // txid we're going to modify in this iteration.
-            CCoins& coins = result[txid];
+            Coin& coin = result[COutPoint(txid, 0)];
             const Coin& entry = stack.back()->AccessCoin(COutPoint(txid, 0));
-            BOOST_CHECK((entry.IsPruned() && coins.IsPruned()) || entry == Coin(coins.vout[0], coins.nHeight, coins.fCoinBase));
+            BOOST_CHECK(coin == entry);
 
-            if (insecure_rand() % 5 == 0 || coins.IsPruned()) {
-                if (coins.IsPruned()) {
+            if (insecure_rand() % 5 == 0 || coin.IsPruned()) {
+                if (coin.IsPruned()) {
                     added_an_entry = true;
                 } else {
                     updated_an_entry = true;
                 }
-                coins.vout.resize(1);
-                coins.vout[0].nValue = insecure_rand();
+                coin.out.nValue = insecure_rand();
+                coin.nHeight = 1;
             } else {
-                coins.Clear();
+                coin.Clear();
                 removed_an_entry = true;
             }
-            if (coins.IsPruned()) {
+            if (coin.IsPruned()) {
                 stack.back()->SpendCoin(COutPoint(txid, 0));
             } else {
-                stack.back()->AddCoin(COutPoint(txid, 0), Coin(coins.vout[0], coins.nHeight, coins.fCoinBase), true);
+                stack.back()->AddCoin(COutPoint(txid, 0), Coin(coin), true);
             }
         }
 
         // Once every 1000 iterations and at the end, verify the full cache.
         if (insecure_rand() % 1000 == 1 || i == NUM_SIMULATION_ITERATIONS - 1) {
-            for (std::map<uint256, CCoins>::iterator it = result.begin(); it != result.end(); it++) {
-                const CCoins* coins = stack.back()->AccessCoins(it->first);
-                if (coins) {
-                    BOOST_CHECK(*coins == it->second);
-                    found_an_entry = true;
-                } else {
-                    BOOST_CHECK(it->second.IsPruned());
+            for (auto it = result.begin(); it != result.end(); it++) {
+                const Coin& coin = stack.back()->AccessCoin(it->first);
+                BOOST_CHECK(coin == it->second);
+                if (coin.IsPruned()) {
                     missed_an_entry = true;
+                } else {
+                    found_an_entry = true;
                 }
             }
             BOOST_FOREACH(const CCoinsViewCacheTest *test, stack) {
@@ -229,19 +228,19 @@ 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();
+typedef std::map<COutPoint, std::tuple<CTransaction,CTxUndo,Coin>> UtxoData;
+UtxoData utxoData;
+
+UtxoData::iterator FindRandomFrom(const std::set<COutPoint> &utxoSet) {
+    assert(utxoSet.size());
+    auto utxoSetIt = utxoSet.lower_bound(COutPoint(GetRandHash(), 0));
+    if (utxoSetIt == utxoSet.end()) {
+        utxoSetIt = utxoSet.begin();
     }
-    std::map<uint256, TxData>::iterator txdit = alltxs.find(*txIt);
-    assert(txdit != alltxs.end());
-    return txdit->second;
+    auto utxoDataIt = utxoData.find(*utxoSetIt);
+    assert(utxoDataIt != utxoData.end());
+    return utxoDataIt;
 }
 
 
@@ -254,7 +253,7 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
 {
     bool spent_a_duplicate_coinbase = false;
     // A simple map to track what we expect the cache stack to represent.
-    std::map<uint256, CCoins> result;
+    std::map<COutPoint, Coin> result;
 
     // The cache stack.
     CCoinsViewTest base; // A CCoinsViewTest at the bottom.
@@ -262,10 +261,10 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
     stack.push_back(new CCoinsViewCacheTest(&base)); // Start with one cache.
 
     // 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;
+    std::set<COutPoint> coinbaseids;
+    std::set<COutPoint> disconnectedids;
+    std::set<COutPoint> duplicateids;
+    std::set<COutPoint> utxoset;
 
     for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) {
         uint32_t randiter = insecure_rand();
@@ -277,22 +276,22 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
             tx.vout.resize(1);
             tx.vout[0].nValue = i; //Keep txs unique unless intended to duplicate
             unsigned int height = insecure_rand();
-            CCoins oldcoins;
+            Coin oldcoins;
 
             // 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()) {
-                    TxData &txd = FindRandomFrom(coinbaseids);
+                    auto utxod = FindRandomFrom(coinbaseids);
                     // Reuse the exact same coinbase
-                    tx = std::get<0>(txd);
+                    tx = std::get<0>(utxod->second);
                     // shouldn't be available for reconnection if its been duplicated
-                    disconnectedids.erase(tx.GetHash());
+                    disconnectedids.erase(utxod->first);
 
-                    duplicateids.insert(tx.GetHash());
+                    duplicateids.insert(utxod->first);
                 }
                 else {
-                    coinbaseids.insert(tx.GetHash());
+                    coinbaseids.insert(COutPoint(tx.GetHash(), 0));
                 }
                 assert(CTransaction(tx).IsCoinBase());
             }
@@ -300,85 +299,82 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
             // 17/20 times reconnect previous or add a regular tx
             else {
 
-                uint256 prevouthash;
+                COutPoint prevout;
                 // 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());
+                    auto utxod = FindRandomFrom(disconnectedids);
+                    tx = std::get<0>(utxod->second);
+                    prevout = tx.vin[0].prevout;
+                    if (!CTransaction(tx).IsCoinBase() && !utxoset.count(prevout)) {
+                        disconnectedids.erase(utxod->first);
                         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())) {
+                    if (utxoset.count(utxod->first)) {
                         assert(CTransaction(tx).IsCoinBase());
-                        assert(duplicateids.count(tx.GetHash()));
+                        assert(duplicateids.count(utxod->first));
                     }
-                    disconnectedids.erase(tx.GetHash());
+                    disconnectedids.erase(utxod->first);
                 }
 
                 // 16/20 times create a regular tx
                 else {
-                    TxData &txd = FindRandomFrom(utxoset);
-                    prevouthash = std::get<0>(txd).GetHash();
+                    auto utxod = FindRandomFrom(utxoset);
+                    prevout = utxod->first;
 
                     // Construct the tx to spend the coins of prevouthash
-                    tx.vin[0].prevout.hash = prevouthash;
-                    tx.vin[0].prevout.n = 0;
+                    tx.vin[0].prevout = prevout;
                     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];
+                oldcoins = result[prevout];
                 // Update the expected result of prevouthash to know these coins are spent
-                result[prevouthash].Clear();
+                result[prevout].Clear();
 
-                utxoset.erase(prevouthash);
+                utxoset.erase(prevout);
 
                 // 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)) {
+                if (duplicateids.count(prevout)) {
                     spent_a_duplicate_coinbase = true;
                 }
 
             }
             // Update the expected result to know about the new output coins
-            result[tx.GetHash()].FromTx(tx, height);
+            assert(tx.vout.size() == 1);
+            const COutPoint outpoint(tx.GetHash(), 0);
+            result[outpoint] = Coin(tx.vout[0], height, CTransaction(tx).IsCoinBase());
 
             // Call UpdateCoins on the top cache
             CTxUndo undo;
             UpdateCoins(tx, *(stack.back()), undo, height);
 
             // Update the utxo set for future spends
-            utxoset.insert(tx.GetHash());
+            utxoset.insert(outpoint);
 
             // Track this tx and undo info to use later
-            alltxs.insert(std::make_pair(tx.GetHash(),std::make_tuple(tx,undo,oldcoins)));
+            utxoData.emplace(outpoint, std::make_tuple(tx,undo,oldcoins));
         } else if (utxoset.size()) {
             //1/20 times undo a previous transaction
-            TxData &txd = FindRandomFrom(utxoset);
-
-            CTransaction &tx = std::get<0>(txd);
-            CTxUndo &undo = std::get<1>(txd);
-            CCoins &origcoins = std::get<2>(txd);
+            auto utxod = FindRandomFrom(utxoset);
 
-            uint256 undohash = tx.GetHash();
+            CTransaction &tx = std::get<0>(utxod->second);
+            CTxUndo &undo = std::get<1>(utxod->second);
+            Coin &origcoins = std::get<2>(utxod->second);
 
             // Update the expected result
             // Remove new outputs
-            result[undohash].Clear();
+            result[utxod->first].Clear();
             // If not coinbase restore prevout
             if (!tx.IsCoinBase()) {
-                result[tx.vin[0].prevout.hash] = origcoins;
+                result[tx.vin[0].prevout] = origcoins;
             }
 
             // Disconnect the tx from the current UTXO
             // See code in DisconnectBlock
             // remove outputs
-            {
-                stack.back()->SpendCoin(COutPoint(undohash, 0));
-            }
+            stack.back()->SpendCoin(utxod->first);
             // restore inputs
             if (!tx.IsCoinBase()) {
                 const COutPoint &out = tx.vin[0].prevout;
@@ -386,23 +382,19 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
                 ApplyTxInUndo(std::move(coin), *(stack.back()), out);
             }
             // Store as a candidate for reconnection
-            disconnectedids.insert(undohash);
+            disconnectedids.insert(utxod->first);
 
             // Update the utxoset
-            utxoset.erase(undohash);
+            utxoset.erase(utxod->first);
             if (!tx.IsCoinBase())
-                utxoset.insert(tx.vin[0].prevout.hash);
+                utxoset.insert(tx.vin[0].prevout);
         }
 
         // Once every 1000 iterations and at the end, verify the full cache.
         if (insecure_rand() % 1000 == 1 || i == NUM_SIMULATION_ITERATIONS - 1) {
-            for (std::map<uint256, CCoins>::iterator it = result.begin(); it != result.end(); it++) {
-                const CCoins* coins = stack.back()->AccessCoins(it->first);
-                if (coins) {
-                    BOOST_CHECK(*coins == it->second);
-                } else {
-                    BOOST_CHECK(it->second.IsPruned());
-                }
+            for (auto it = result.begin(); it != result.end(); it++) {
+                const Coin& coin = stack.back()->AccessCoin(it->first);
+                BOOST_CHECK(coin == it->second);
             }
         }
 
@@ -443,50 +435,36 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
 BOOST_AUTO_TEST_CASE(ccoins_serialization)
 {
     // Good example
-    CDataStream ss1(ParseHex("0104835800816115944e077fe7c803cfa57f29b36bf87c1d358bb85e"), SER_DISK, CLIENT_VERSION);
-    CCoins cc1;
+    CDataStream ss1(ParseHex("97f23c835800816115944e077fe7c803cfa57f29b36bf87c1d35"), SER_DISK, CLIENT_VERSION);
+    Coin cc1;
     ss1 >> cc1;
     BOOST_CHECK_EQUAL(cc1.fCoinBase, false);
     BOOST_CHECK_EQUAL(cc1.nHeight, 203998);
-    BOOST_CHECK_EQUAL(cc1.vout.size(), 2);
-    BOOST_CHECK_EQUAL(cc1.IsAvailable(0), false);
-    BOOST_CHECK_EQUAL(cc1.IsAvailable(1), true);
-    BOOST_CHECK_EQUAL(cc1.vout[1].nValue, 60000000000ULL);
-    BOOST_CHECK_EQUAL(HexStr(cc1.vout[1].scriptPubKey), HexStr(GetScriptForDestination(CKeyID(uint160(ParseHex("816115944e077fe7c803cfa57f29b36bf87c1d35"))))));
+    BOOST_CHECK_EQUAL(cc1.out.nValue, 60000000000ULL);
+    BOOST_CHECK_EQUAL(HexStr(cc1.out.scriptPubKey), HexStr(GetScriptForDestination(CKeyID(uint160(ParseHex("816115944e077fe7c803cfa57f29b36bf87c1d35"))))));
 
     // Good example
-    CDataStream ss2(ParseHex("0109044086ef97d5790061b01caab50f1b8e9c50a5057eb43c2d9563a4eebbd123008c988f1a4a4de2161e0f50aac7f17e7f9555caa486af3b"), SER_DISK, CLIENT_VERSION);
-    CCoins cc2;
+    CDataStream ss2(ParseHex("8ddf77bbd123008c988f1a4a4de2161e0f50aac7f17e7f9555caa4"), SER_DISK, CLIENT_VERSION);
+    Coin cc2;
     ss2 >> cc2;
     BOOST_CHECK_EQUAL(cc2.fCoinBase, true);
     BOOST_CHECK_EQUAL(cc2.nHeight, 120891);
-    BOOST_CHECK_EQUAL(cc2.vout.size(), 17);
-    for (int i = 0; i < 17; i++) {
-        BOOST_CHECK_EQUAL(cc2.IsAvailable(i), i == 4 || i == 16);
-    }
-    BOOST_CHECK_EQUAL(cc2.vout[4].nValue, 234925952);
-    BOOST_CHECK_EQUAL(HexStr(cc2.vout[4].scriptPubKey), HexStr(GetScriptForDestination(CKeyID(uint160(ParseHex("61b01caab50f1b8e9c50a5057eb43c2d9563a4ee"))))));
-    BOOST_CHECK_EQUAL(cc2.vout[16].nValue, 110397);
-    BOOST_CHECK_EQUAL(HexStr(cc2.vout[16].scriptPubKey), HexStr(GetScriptForDestination(CKeyID(uint160(ParseHex("8c988f1a4a4de2161e0f50aac7f17e7f9555caa4"))))));
+    BOOST_CHECK_EQUAL(cc2.out.nValue, 110397);
+    BOOST_CHECK_EQUAL(HexStr(cc2.out.scriptPubKey), HexStr(GetScriptForDestination(CKeyID(uint160(ParseHex("8c988f1a4a4de2161e0f50aac7f17e7f9555caa4"))))));
 
     // Smallest possible example
-    CDataStream ssx(SER_DISK, CLIENT_VERSION);
-    BOOST_CHECK_EQUAL(HexStr(ssx.begin(), ssx.end()), "");
-
-    CDataStream ss3(ParseHex("0002000600"), SER_DISK, CLIENT_VERSION);
-    CCoins cc3;
+    CDataStream ss3(ParseHex("000006"), SER_DISK, CLIENT_VERSION);
+    Coin cc3;
     ss3 >> cc3;
     BOOST_CHECK_EQUAL(cc3.fCoinBase, false);
     BOOST_CHECK_EQUAL(cc3.nHeight, 0);
-    BOOST_CHECK_EQUAL(cc3.vout.size(), 1);
-    BOOST_CHECK_EQUAL(cc3.IsAvailable(0), true);
-    BOOST_CHECK_EQUAL(cc3.vout[0].nValue, 0);
-    BOOST_CHECK_EQUAL(cc3.vout[0].scriptPubKey.size(), 0);
+    BOOST_CHECK_EQUAL(cc3.out.nValue, 0);
+    BOOST_CHECK_EQUAL(cc3.out.scriptPubKey.size(), 0);
 
     // scriptPubKey that ends beyond the end of the stream
-    CDataStream ss4(ParseHex("0002000800"), SER_DISK, CLIENT_VERSION);
+    CDataStream ss4(ParseHex("000007"), SER_DISK, CLIENT_VERSION);
     try {
-        CCoins cc4;
+        Coin cc4;
         ss4 >> cc4;
         BOOST_CHECK_MESSAGE(false, "We should have thrown");
     } catch (const std::ios_base::failure& e) {
@@ -497,17 +475,16 @@ BOOST_AUTO_TEST_CASE(ccoins_serialization)
     uint64_t x = 3000000000ULL;
     tmp << VARINT(x);
     BOOST_CHECK_EQUAL(HexStr(tmp.begin(), tmp.end()), "8a95c0bb00");
-    CDataStream ss5(ParseHex("0002008a95c0bb0000"), SER_DISK, CLIENT_VERSION);
+    CDataStream ss5(ParseHex("00008a95c0bb00"), SER_DISK, CLIENT_VERSION);
     try {
-        CCoins cc5;
+        Coin cc5;
         ss5 >> cc5;
         BOOST_CHECK_MESSAGE(false, "We should have thrown");
     } catch (const std::ios_base::failure& e) {
     }
 }
 
-const static uint256 TXID;
-const static COutPoint OUTPOINT = {uint256(), 0};
+const static COutPoint OUTPOINT;
 const static CAmount PRUNED = -1;
 const static CAmount ABSENT = -2;
 const static CAmount FAIL = -3;
@@ -522,15 +499,15 @@ const static auto FLAGS = {char(0), FRESH, DIRTY, char(DIRTY | FRESH)};
 const static auto CLEAN_FLAGS = {char(0), FRESH};
 const static auto ABSENT_FLAGS = {NO_ENTRY};
 
-void SetCoinsValue(CAmount value, CCoins& coins)
+void SetCoinsValue(CAmount value, Coin& coin)
 {
     assert(value != ABSENT);
-    coins.Clear();
-    assert(coins.IsPruned());
+    coin.Clear();
+    assert(coin.IsPruned());
     if (value != PRUNED) {
-        coins.vout.emplace_back();
-        coins.vout.back().nValue = value;
-        assert(!coins.IsPruned());
+        coin.out.nValue = value;
+        coin.nHeight = 1;
+        assert(!coin.IsPruned());
     }
 }
 
@@ -544,24 +521,22 @@ size_t InsertCoinsMapEntry(CCoinsMap& map, CAmount value, char flags)
     CCoinsCacheEntry entry;
     entry.flags = flags;
     SetCoinsValue(value, entry.coins);
-    auto inserted = map.emplace(TXID, std::move(entry));
+    auto inserted = map.emplace(OUTPOINT, std::move(entry));
     assert(inserted.second);
     return inserted.first->second.coins.DynamicMemoryUsage();
 }
 
 void GetCoinsMapEntry(const CCoinsMap& map, CAmount& value, char& flags)
 {
-    auto it = map.find(TXID);
+    auto it = map.find(OUTPOINT);
     if (it == map.end()) {
         value = ABSENT;
         flags = NO_ENTRY;
     } else {
         if (it->second.coins.IsPruned()) {
-            assert(it->second.coins.vout.size() == 0);
             value = PRUNED;
         } else {
-            assert(it->second.coins.vout.size() == 1);
-            value = it->second.coins.vout[0].nValue;
+            value = it->second.coins.out.nValue;
         }
         flags = it->second.flags;
         assert(flags != NO_ENTRY);
diff --git a/src/test/test_bitcoin_fuzzy.cpp b/src/test/test_bitcoin_fuzzy.cpp
index e11e46bb02..de14251601 100644
--- a/src/test/test_bitcoin_fuzzy.cpp
+++ b/src/test/test_bitcoin_fuzzy.cpp
@@ -168,8 +168,8 @@ int do_fuzz()
         {
             try
             {
-                CCoins block;
-                ds >> block;
+                Coin coin;
+                ds >> coin;
             } catch (const std::ios_base::failure& e) {return 0;}
             break;
         }