Ultraprune

This switches bitcoin's transaction/block verification logic to use a
"coin database", which contains all unredeemed transaction output scripts,
amounts and heights.

The name ultraprune comes from the fact that instead of a full transaction
index, we only (need to) keep an index with unspent outputs. For now, the
blocks themselves are kept as usual, although they are only necessary for
serving, rescanning and reorganizing.

The basic datastructures are CCoins (representing the coins of a single
transaction), and CCoinsView (representing a state of the coins database).
There are several implementations for CCoinsView. A dummy, one backed by
the coins database (coins.dat), one backed by the memory pool, and one
that adds a cache on top of it. FetchInputs, ConnectInputs, ConnectBlock,
DisconnectBlock, ... now operate on a generic CCoinsView.

The block switching logic now builds a single cached CCoinsView with
changes to be committed to the database before any changes are made.
This means no uncommitted changes are ever read from the database, and
should ease the transition to another database layer which does not
support transactions (but does support atomic writes), like LevelDB.

For the getrawtransaction() RPC call, access to a txid-to-disk index
would be preferable. As this index is not necessary or even useful
for any other part of the implementation, it is not provided. Instead,
getrawtransaction() uses the coin database to find the block height,
and then scans that block to find the requested transaction. This is
slow, but should suffice for debug purposes.

3 files changed, 37 insertions, 29 deletions

diff --git a/src/test/DoS_tests.cpp b/src/test/DoS_tests.cpp
index d469593120..8235b0bda7 100644
--- a/src/test/DoS_tests.cpp
+++ b/src/test/DoS_tests.cpp
@@ -278,7 +278,7 @@ BOOST_AUTO_TEST_CASE(DoS_checkSig)
     mst1 = boost::posix_time::microsec_clock::local_time();
     for (unsigned int i = 0; i < 5; i++)
         for (unsigned int j = 0; j < tx.vin.size(); j++)
-            BOOST_CHECK(VerifySignature(orphans[j], tx, j, true, true, SIGHASH_ALL));
+            BOOST_CHECK(VerifySignature(CCoins(orphans[j], MEMPOOL_HEIGHT), tx, j, true, true, SIGHASH_ALL));
     mst2 = boost::posix_time::microsec_clock::local_time();
     msdiff = mst2 - mst1;
     long nManyValidate = msdiff.total_milliseconds();
@@ -289,13 +289,13 @@ BOOST_AUTO_TEST_CASE(DoS_checkSig)
     // 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, true, SIGHASH_ALL));
+    BOOST_CHECK(!VerifySignature(CCoins(orphans[0], MEMPOOL_HEIGHT), tx, 0, true, 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, true, SIGHASH_ALL));
-    BOOST_CHECK(!VerifySignature(orphans[1], tx, 1, true, true, SIGHASH_ALL));
+    BOOST_CHECK(!VerifySignature(CCoins(orphans[0], MEMPOOL_HEIGHT), tx, 0, true, true, SIGHASH_ALL));
+    BOOST_CHECK(!VerifySignature(CCoins(orphans[1], MEMPOOL_HEIGHT), tx, 1, true, true, SIGHASH_ALL));
     std::swap(tx.vin[0].scriptSig, tx.vin[1].scriptSig);
 
     // Exercise -maxsigcachesize code:
@@ -305,7 +305,7 @@ BOOST_AUTO_TEST_CASE(DoS_checkSig)
     BOOST_CHECK(SignSignature(keystore, orphans[0], tx, 0));
     BOOST_CHECK(tx.vin[0].scriptSig != oldSig);
     for (unsigned int j = 0; j < tx.vin.size(); j++)
-        BOOST_CHECK(VerifySignature(orphans[j], tx, j, true, true, SIGHASH_ALL));
+        BOOST_CHECK(VerifySignature(CCoins(orphans[j], MEMPOOL_HEIGHT), tx, j, true, true, SIGHASH_ALL));
     mapArgs.erase("-maxsigcachesize");
 
     LimitOrphanTxSize(0);
diff --git a/src/test/script_P2SH_tests.cpp b/src/test/script_P2SH_tests.cpp
index 9db584c147..35069a3fdd 100644
--- a/src/test/script_P2SH_tests.cpp
+++ b/src/test/script_P2SH_tests.cpp
@@ -105,7 +105,7 @@ BOOST_AUTO_TEST_CASE(sign)
         {
             CScript sigSave = txTo[i].vin[0].scriptSig;
             txTo[i].vin[0].scriptSig = txTo[j].vin[0].scriptSig;
-            bool sigOK = VerifySignature(txFrom, txTo[i], 0, true, true, 0);
+            bool sigOK = VerifySignature(CCoins(txFrom, 0), txTo[i], 0, true, true, 0);
             if (i == j)
                 BOOST_CHECK_MESSAGE(sigOK, strprintf("VerifySignature %d %d", i, j));
             else
@@ -243,7 +243,8 @@ BOOST_AUTO_TEST_CASE(switchover)
 
 BOOST_AUTO_TEST_CASE(AreInputsStandard)
 {
-    std::map<uint256, std::pair<CTxIndex, CTransaction> > mapInputs;
+    CCoinsView coinsDummy;
+    CCoinsViewCache coins(coinsDummy);
     CBasicKeyStore keystore;
     CKey key[3];
     vector<CKey> keys;
@@ -264,23 +265,29 @@ BOOST_AUTO_TEST_CASE(AreInputsStandard)
     CScript pay1of3; pay1of3.SetMultisig(1, keys);
 
     txFrom.vout[0].scriptPubKey = payScriptHash1;
+    txFrom.vout[0].nValue = 1000;
     txFrom.vout[1].scriptPubKey = pay1;
+    txFrom.vout[1].nValue = 2000;
     txFrom.vout[2].scriptPubKey = pay1of3;
+    txFrom.vout[2].nValue = 3000;
 
     // Last three non-standard:
     CScript empty;
     keystore.AddCScript(empty);
     txFrom.vout[3].scriptPubKey = empty;
+    txFrom.vout[3].nValue = 4000;
     // Can't use SetPayToScriptHash, it checks for the empty Script. So:
     txFrom.vout[4].scriptPubKey << OP_HASH160 << Hash160(empty) << OP_EQUAL;
+    txFrom.vout[4].nValue = 5000;
     CScript oneOfEleven;
     oneOfEleven << OP_1;
     for (int i = 0; i < 11; i++)
         oneOfEleven << key[0].GetPubKey();
     oneOfEleven << OP_11 << OP_CHECKMULTISIG;
     txFrom.vout[5].scriptPubKey.SetDestination(oneOfEleven.GetID());
+    txFrom.vout[5].nValue = 6000;
 
-    mapInputs[txFrom.GetHash()] = make_pair(CTxIndex(), txFrom);
+    coins.SetCoins(txFrom.GetHash(), CCoins(txFrom, 0));
 
     CTransaction txTo;
     txTo.vout.resize(1);
@@ -297,21 +304,22 @@ BOOST_AUTO_TEST_CASE(AreInputsStandard)
     txTo.vin[2].prevout.hash = txFrom.GetHash();
     BOOST_CHECK(SignSignature(keystore, txFrom, txTo, 2));
 
-    BOOST_CHECK(txTo.AreInputsStandard(mapInputs));
-    BOOST_CHECK_EQUAL(txTo.GetP2SHSigOpCount(mapInputs), 1);
+    BOOST_CHECK(txTo.AreInputsStandard(coins));
+    BOOST_CHECK_EQUAL(txTo.GetP2SHSigOpCount(coins), 1);
 
     // Make sure adding crap to the scriptSigs makes them non-standard:
     for (int i = 0; i < 3; i++)
     {
         CScript t = txTo.vin[i].scriptSig;
         txTo.vin[i].scriptSig = (CScript() << 11) + t;
-        BOOST_CHECK(!txTo.AreInputsStandard(mapInputs));
+        BOOST_CHECK(!txTo.AreInputsStandard(coins));
         txTo.vin[i].scriptSig = t;
     }
 
     CTransaction txToNonStd;
     txToNonStd.vout.resize(1);
     txToNonStd.vout[0].scriptPubKey.SetDestination(key[1].GetPubKey().GetID());
+    txToNonStd.vout[0].nValue = 1000;
     txToNonStd.vin.resize(2);
     txToNonStd.vin[0].prevout.n = 4;
     txToNonStd.vin[0].prevout.hash = txFrom.GetHash();
@@ -320,11 +328,11 @@ BOOST_AUTO_TEST_CASE(AreInputsStandard)
     txToNonStd.vin[1].prevout.hash = txFrom.GetHash();
     txToNonStd.vin[1].scriptSig << OP_0 << Serialize(oneOfEleven);
 
-    BOOST_CHECK(!txToNonStd.AreInputsStandard(mapInputs));
-    BOOST_CHECK_EQUAL(txToNonStd.GetP2SHSigOpCount(mapInputs), 11);
+    BOOST_CHECK(!txToNonStd.AreInputsStandard(coins));
+    BOOST_CHECK_EQUAL(txToNonStd.GetP2SHSigOpCount(coins), 11);
 
     txToNonStd.vin[0].scriptSig.clear();
-    BOOST_CHECK(!txToNonStd.AreInputsStandard(mapInputs));
+    BOOST_CHECK(!txToNonStd.AreInputsStandard(coins));
 }
 
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/transaction_tests.cpp b/src/test/transaction_tests.cpp
index 1dacdeaa23..17b925c340 100644
--- a/src/test/transaction_tests.cpp
+++ b/src/test/transaction_tests.cpp
@@ -173,7 +173,7 @@ BOOST_AUTO_TEST_CASE(basic_transaction_tests)
 // paid to a TX_PUBKEYHASH.
 //
 static std::vector<CTransaction>
-SetupDummyInputs(CBasicKeyStore& keystoreRet, MapPrevTx& inputsRet)
+SetupDummyInputs(CBasicKeyStore& keystoreRet, CCoinsView & coinsRet)
 {
     std::vector<CTransaction> dummyTransactions;
     dummyTransactions.resize(2);
@@ -192,14 +192,14 @@ SetupDummyInputs(CBasicKeyStore& keystoreRet, MapPrevTx& inputsRet)
     dummyTransactions[0].vout[0].scriptPubKey << key[0].GetPubKey() << OP_CHECKSIG;
     dummyTransactions[0].vout[1].nValue = 50*CENT;
     dummyTransactions[0].vout[1].scriptPubKey << key[1].GetPubKey() << OP_CHECKSIG;
-    inputsRet[dummyTransactions[0].GetHash()] = make_pair(CTxIndex(), dummyTransactions[0]);
+    coinsRet.SetCoins(dummyTransactions[0].GetHash(), CCoins(dummyTransactions[0], 0));
 
     dummyTransactions[1].vout.resize(2);
     dummyTransactions[1].vout[0].nValue = 21*CENT;
     dummyTransactions[1].vout[0].scriptPubKey.SetDestination(key[2].GetPubKey().GetID());
     dummyTransactions[1].vout[1].nValue = 22*CENT;
     dummyTransactions[1].vout[1].scriptPubKey.SetDestination(key[3].GetPubKey().GetID());
-    inputsRet[dummyTransactions[1].GetHash()] = make_pair(CTxIndex(), dummyTransactions[1]);
+    coinsRet.SetCoins(dummyTransactions[1].GetHash(), CCoins(dummyTransactions[1], 0));
 
     return dummyTransactions;
 }
@@ -207,8 +207,9 @@ SetupDummyInputs(CBasicKeyStore& keystoreRet, MapPrevTx& inputsRet)
 BOOST_AUTO_TEST_CASE(test_Get)
 {
     CBasicKeyStore keystore;
-    MapPrevTx dummyInputs;
-    std::vector<CTransaction> dummyTransactions = SetupDummyInputs(keystore, dummyInputs);
+    CCoinsView coinsDummy;
+    CCoinsViewCache coins(coinsDummy);
+    std::vector<CTransaction> dummyTransactions = SetupDummyInputs(keystore, coins);
 
     CTransaction t1;
     t1.vin.resize(3);
@@ -225,25 +226,24 @@ BOOST_AUTO_TEST_CASE(test_Get)
     t1.vout[0].nValue = 90*CENT;
     t1.vout[0].scriptPubKey << OP_1;
 
-    BOOST_CHECK(t1.AreInputsStandard(dummyInputs));
-    BOOST_CHECK_EQUAL(t1.GetValueIn(dummyInputs), (50+21+22)*CENT);
+    BOOST_CHECK(t1.AreInputsStandard(coins));
+    BOOST_CHECK_EQUAL(t1.GetValueIn(coins), (50+21+22)*CENT);
 
     // Adding extra junk to the scriptSig should make it non-standard:
     t1.vin[0].scriptSig << OP_11;
-    BOOST_CHECK(!t1.AreInputsStandard(dummyInputs));
+    BOOST_CHECK(!t1.AreInputsStandard(coins));
 
     // ... as should not having enough:
     t1.vin[0].scriptSig = CScript();
-    BOOST_CHECK(!t1.AreInputsStandard(dummyInputs));
+    BOOST_CHECK(!t1.AreInputsStandard(coins));
 }
 
 BOOST_AUTO_TEST_CASE(test_GetThrow)
 {
     CBasicKeyStore keystore;
-    MapPrevTx dummyInputs;
-    std::vector<CTransaction> dummyTransactions = SetupDummyInputs(keystore, dummyInputs);
-
-    MapPrevTx missingInputs;
+    CCoinsView coinsDummy;
+    CCoinsViewCache coins(coinsDummy);
+    std::vector<CTransaction> dummyTransactions = SetupDummyInputs(keystore, coins);
 
     CTransaction t1;
     t1.vin.resize(3);
@@ -257,8 +257,8 @@ BOOST_AUTO_TEST_CASE(test_GetThrow)
     t1.vout[0].nValue = 90*CENT;
     t1.vout[0].scriptPubKey << OP_1;
 
-    BOOST_CHECK_THROW(t1.AreInputsStandard(missingInputs), runtime_error);
-    BOOST_CHECK_THROW(t1.GetValueIn(missingInputs), runtime_error);
+    BOOST_CHECK_THROW(t1.AreInputsStandard(coinsDummy), runtime_error);
+    BOOST_CHECK_THROW(t1.GetValueIn(coinsDummy), runtime_error);
 }
 
 BOOST_AUTO_TEST_SUITE_END()