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.

1 files changed, 61 insertions, 184 deletions

diff --git a/src/db.cpp b/src/db.cpp
index 53be48cb0f..0a6ba3fb39 100644
--- a/src/db.cpp
+++ b/src/db.cpp
@@ -244,7 +244,7 @@ CDB::CDB(const char *pszFile, const char* pszMode) :
 
             ret = pdb->open(NULL,      // Txn pointer
                             fMockDb ? NULL : pszFile,   // Filename
-                            "main",    // Logical db name
+                            fMockDb ? pszFile : "main", // Logical db name
                             DB_BTREE,  // Database type
                             nFlags,    // Flags
                             0);
@@ -273,7 +273,7 @@ CDB::CDB(const char *pszFile, const char* pszMode) :
 
 static bool IsChainFile(std::string strFile)
 {
-    if (strFile == "blkindex.dat")
+    if (strFile == "coins.dat" || strFile == "chain.dat")
         return true;
 
     return false;
@@ -475,111 +475,66 @@ void CDBEnv::Flush(bool fShutdown)
 
 
 //
-// CTxDB
+// CChainDB and CCoinsDB
 //
 
-bool CTxDB::ReadTxIndex(uint256 hash, CTxIndex& txindex)
-{
+bool CCoinsDB::HaveCoins(uint256 hash) {
     assert(!fClient);
-    txindex.SetNull();
-    return Read(make_pair(string("tx"), hash), txindex);
+    return Exists(make_pair('c', hash));
 }
 
-bool CTxDB::UpdateTxIndex(uint256 hash, const CTxIndex& txindex)
-{
+bool CCoinsDB::ReadCoins(uint256 hash, CCoins &coins) {
     assert(!fClient);
-    return Write(make_pair(string("tx"), hash), txindex);
-}
-
-bool CTxDB::AddTxIndex(const CTransaction& tx, const CDiskTxPos& pos, int nHeight)
-{
-    assert(!fClient);
-
-    // Add to tx index
-    uint256 hash = tx.GetHash();
-    CTxIndex txindex(pos, tx.vout.size());
-    return Write(make_pair(string("tx"), hash), txindex);
+    return Read(make_pair('c', hash), coins);
 }
 
-bool CTxDB::EraseTxIndex(const CTransaction& tx)
-{
-    assert(!fClient);
-    uint256 hash = tx.GetHash();
-
-    return Erase(make_pair(string("tx"), hash));
-}
-
-bool CTxDB::ContainsTx(uint256 hash)
-{
+bool CCoinsDB::WriteCoins(uint256 hash, const CCoins &coins) {
     assert(!fClient);
-    return Exists(make_pair(string("tx"), hash));
+    if (coins.IsPruned())
+        return Erase(make_pair('c', hash));
+    else
+        return Write(make_pair('c', hash), coins);
 }
 
-bool CTxDB::ReadDiskTx(uint256 hash, CTransaction& tx, CTxIndex& txindex)
+bool CChainDB::WriteBlockIndex(const CDiskBlockIndex& blockindex)
 {
-    assert(!fClient);
-    tx.SetNull();
-    if (!ReadTxIndex(hash, txindex))
-        return false;
-    return (tx.ReadFromDisk(txindex.pos));
+    return Write(make_pair('b', blockindex.GetBlockHash()), blockindex);
 }
 
-bool CTxDB::ReadDiskTx(uint256 hash, CTransaction& tx)
+bool CCoinsDB::ReadHashBestChain(uint256& hashBestChain)
 {
-    CTxIndex txindex;
-    return ReadDiskTx(hash, tx, txindex);
+    return Read('B', hashBestChain);
 }
 
-bool CTxDB::ReadDiskTx(COutPoint outpoint, CTransaction& tx, CTxIndex& txindex)
+bool CCoinsDB::WriteHashBestChain(uint256 hashBestChain)
 {
-    return ReadDiskTx(outpoint.hash, tx, txindex);
+    return Write('B', hashBestChain);
 }
 
-bool CTxDB::ReadDiskTx(COutPoint outpoint, CTransaction& tx)
+bool CChainDB::ReadBestInvalidWork(CBigNum& bnBestInvalidWork)
 {
-    CTxIndex txindex;
-    return ReadDiskTx(outpoint.hash, tx, txindex);
+    return Read('I', bnBestInvalidWork);
 }
 
-bool CTxDB::WriteBlockIndex(const CDiskBlockIndex& blockindex)
+bool CChainDB::WriteBestInvalidWork(CBigNum bnBestInvalidWork)
 {
-    return Write(make_pair(string("blockindex"), blockindex.GetBlockHash()), blockindex);
+    return Write('I', bnBestInvalidWork);
 }
 
-bool CTxDB::WriteBlockFileInfo(int nFile, const CBlockFileInfo &info) {
-    return Write(make_pair(string("blockfile"), nFile), info);
+bool CChainDB::WriteBlockFileInfo(int nFile, const CBlockFileInfo &info) {
+    return Write(make_pair('f', nFile), info);
 }
 
-bool CTxDB::ReadBlockFileInfo(int nFile, CBlockFileInfo &info) {
-    return Read(make_pair(string("blockfile"), nFile), info);
+bool CChainDB::ReadBlockFileInfo(int nFile, CBlockFileInfo &info) {
+    return Read(make_pair('f', nFile), info);
 }
 
-bool CTxDB::WriteLastBlockFile(int nFile) {
-    return Write(string("lastblockfile"), nFile);
+bool CChainDB::WriteLastBlockFile(int nFile) {
+    return Write('l', nFile);
 }
 
-bool CTxDB::ReadLastBlockFile(int &nFile) {
-    return Read(string("lastblockfile"), nFile);
-}
-
-bool CTxDB::ReadHashBestChain(uint256& hashBestChain)
-{
-    return Read(string("hashBestChain"), hashBestChain);
-}
-
-bool CTxDB::WriteHashBestChain(uint256 hashBestChain)
-{
-    return Write(string("hashBestChain"), hashBestChain);
-}
-
-bool CTxDB::ReadBestInvalidWork(CBigNum& bnBestInvalidWork)
-{
-    return Read(string("bnBestInvalidWork"), bnBestInvalidWork);
-}
-
-bool CTxDB::WriteBestInvalidWork(CBigNum bnBestInvalidWork)
-{
-    return Write(string("bnBestInvalidWork"), bnBestInvalidWork);
+bool CChainDB::ReadLastBlockFile(int &nFile) {
+    return Read('l', nFile);
 }
 
 CBlockIndex static * InsertBlockIndex(uint256 hash)
@@ -602,9 +557,9 @@ CBlockIndex static * InsertBlockIndex(uint256 hash)
     return pindexNew;
 }
 
-bool CTxDB::LoadBlockIndex()
+bool LoadBlockIndex(CCoinsDB &coindb, CChainDB &chaindb)
 {
-    if (!LoadBlockIndexGuts())
+    if (!chaindb.LoadBlockIndexGuts())
         return false;
 
     if (fRequestShutdown)
@@ -626,29 +581,39 @@ bool CTxDB::LoadBlockIndex()
     }
 
     // Load block file info
-    ReadLastBlockFile(nLastBlockFile);
+    chaindb.ReadLastBlockFile(nLastBlockFile);
     printf("LoadBlockIndex(): last block file = %i\n", nLastBlockFile);
-    if (ReadBlockFileInfo(nLastBlockFile, infoLastBlockFile))
+    if (chaindb.ReadBlockFileInfo(nLastBlockFile, infoLastBlockFile))
         printf("LoadBlockIndex(): last block file: %s\n", infoLastBlockFile.ToString().c_str());
  
     // Load hashBestChain pointer to end of best chain
-    if (!ReadHashBestChain(hashBestChain))
+    if (!coindb.ReadHashBestChain(hashBestChain))
     {
         if (pindexGenesisBlock == NULL)
             return true;
         return error("CTxDB::LoadBlockIndex() : hashBestChain not loaded");
     }
-    if (!mapBlockIndex.count(hashBestChain))
+    std::map<uint256, CBlockIndex*>::iterator it = mapBlockIndex.find(hashBestChain);
+    if (it == mapBlockIndex.end()) {
         return error("CTxDB::LoadBlockIndex() : hashBestChain not found in the block index");
-    pindexBest = mapBlockIndex[hashBestChain];
-    nBestHeight = pindexBest->nHeight;
-    bnBestChainWork = pindexBest->bnChainWork;
-    printf("LoadBlockIndex(): hashBestChain=%s  height=%d  date=%s\n",
-      hashBestChain.ToString().substr(0,20).c_str(), nBestHeight,
-      DateTimeStrFormat("%x %H:%M:%S", pindexBest->GetBlockTime()).c_str());
+    } else {
+        // set 'next' pointers in best chain
+        CBlockIndex *pindex = it->second;
+        while(pindex != NULL && pindex->pprev != NULL) {
+             CBlockIndex *pindexPrev = pindex->pprev;
+             pindexPrev->pnext = pindex;
+             pindex = pindexPrev;
+        }
+        pindexBest = it->second;
+        nBestHeight = pindexBest->nHeight;
+        bnBestChainWork = pindexBest->bnChainWork;
+    }
+    printf("LoadBlockIndex(): hashBestChain=%s  height=%d date=%s\n",
+        hashBestChain.ToString().substr(0,20).c_str(), nBestHeight,
+        DateTimeStrFormat("%x %H:%M:%S", pindexBest->GetBlockTime()).c_str());
 
     // Load bnBestInvalidWork, OK if it doesn't exist
-    ReadBestInvalidWork(bnBestInvalidWork);
+    chaindb.ReadBestInvalidWork(bnBestInvalidWork);
 
     // Verify blocks in the best chain
     int nCheckLevel = GetArg("-checklevel", 1);
@@ -664,7 +629,6 @@ bool CTxDB::LoadBlockIndex()
         if (fRequestShutdown || pindex->nHeight < nBestHeight-nCheckDepth)
             break;
         CBlock block;
-        CDiskBlockPos blockPos = pindex->GetBlockPos();
         if (!block.ReadFromDisk(pindex))
             return error("LoadBlockIndex() : block.ReadFromDisk failed");
         // check level 1: verify block validity
@@ -673,98 +637,12 @@ bool CTxDB::LoadBlockIndex()
             printf("LoadBlockIndex() : *** found bad block at %d, hash=%s\n", pindex->nHeight, pindex->GetBlockHash().ToString().c_str());
             pindexFork = pindex->pprev;
         }
-        // check level 2: verify transaction index validity
-        if (nCheckLevel>1)
-        {
-            BOOST_FOREACH(const CTransaction &tx, block.vtx)
-            {
-                uint256 hashTx = tx.GetHash();
-                CTxIndex txindex;
-                if (ReadTxIndex(hashTx, txindex))
-                {
-                    // check level 3: checker transaction hashes
-                    if (nCheckLevel>2 || blockPos != txindex.pos.blockPos)
-                    {
-                        // either an error or a duplicate transaction
-                        CTransaction txFound;
-                        if (!txFound.ReadFromDisk(txindex.pos))
-                        {
-                            printf("LoadBlockIndex() : *** cannot read mislocated transaction %s\n", hashTx.ToString().c_str());
-                            pindexFork = pindex->pprev;
-                        }
-                        else
-                            if (txFound.GetHash() != hashTx) // not a duplicate tx
-                            {
-                                printf("LoadBlockIndex(): *** invalid tx position for %s\n", hashTx.ToString().c_str());
-                                pindexFork = pindex->pprev;
-                            }
-                    }
-                    // check level 4: check whether spent txouts were spent within the main chain
-                    unsigned int nOutput = 0;
-                    if (nCheckLevel>3)
-                    {
-                        BOOST_FOREACH(const CDiskTxPos &txpos, txindex.vSpent)
-                        {
-                            if (!txpos.IsNull())
-                            {
-                                // check level 6: check whether spent txouts were spent by a valid transaction that consume them
-                                if (nCheckLevel>5)
-                                {
-                                    CTransaction txSpend;
-                                    if (!txSpend.ReadFromDisk(txpos))
-                                    {
-                                        printf("LoadBlockIndex(): *** cannot read spending transaction of %s:%i from disk\n", hashTx.ToString().c_str(), nOutput);
-                                        pindexFork = pindex->pprev;
-                                    }
-                                    else if (!txSpend.CheckTransaction())
-                                    {
-                                        printf("LoadBlockIndex(): *** spending transaction of %s:%i is invalid\n", hashTx.ToString().c_str(), nOutput);
-                                        pindexFork = pindex->pprev;
-                                    }
-                                    else
-                                    {
-                                        bool fFound = false;
-                                        BOOST_FOREACH(const CTxIn &txin, txSpend.vin)
-                                            if (txin.prevout.hash == hashTx && txin.prevout.n == nOutput)
-                                                fFound = true;
-                                        if (!fFound)
-                                        {
-                                            printf("LoadBlockIndex(): *** spending transaction of %s:%i does not spend it\n", hashTx.ToString().c_str(), nOutput);
-                                            pindexFork = pindex->pprev;
-                                        }
-                                    }
-                                }
-                            }
-                            nOutput++;
-                        }
-                    }
-                }
-                // check level 5: check whether all prevouts are marked spent
-                if (nCheckLevel>4)
-                {
-                     BOOST_FOREACH(const CTxIn &txin, tx.vin)
-                     {
-                          CTxIndex txindex;
-                          if (ReadTxIndex(txin.prevout.hash, txindex))
-                              if (txindex.vSpent.size()-1 < txin.prevout.n || txindex.vSpent[txin.prevout.n].IsNull())
-                              {
-                                  printf("LoadBlockIndex(): *** found unspent prevout %s:%i in %s\n", txin.prevout.hash.ToString().c_str(), txin.prevout.n, hashTx.ToString().c_str());
-                                  pindexFork = pindex->pprev;
-                              }
-                     }
-                }
-            }
-        }
+        // TODO: stronger verifications
     }
     if (pindexFork && !fRequestShutdown)
     {
-        // Reorg back to the fork
-        printf("LoadBlockIndex() : *** moving best chain pointer back to block %d\n", pindexFork->nHeight);
-        CBlock block;
-        if (!block.ReadFromDisk(pindexFork))
-            return error("LoadBlockIndex() : block.ReadFromDisk failed");
-        CTxDB txdb;
-        block.SetBestChain(txdb, pindexFork);
+        // TODO: reorg back
+        return error("LoadBlockIndex(): chain database corrupted");
     }
 
     return true;
@@ -772,7 +650,7 @@ bool CTxDB::LoadBlockIndex()
 
 
 
-bool CTxDB::LoadBlockIndexGuts()
+bool CChainDB::LoadBlockIndexGuts()
 {
     // Get database cursor
     Dbc* pcursor = GetCursor();
@@ -786,7 +664,7 @@ bool CTxDB::LoadBlockIndexGuts()
         // Read next record
         CDataStream ssKey(SER_DISK, CLIENT_VERSION);
         if (fFlags == DB_SET_RANGE)
-            ssKey << make_pair(string("blockindex"), uint256(0));
+            ssKey << make_pair('b', uint256(0));
         CDataStream ssValue(SER_DISK, CLIENT_VERSION);
         int ret = ReadAtCursor(pcursor, ssKey, ssValue, fFlags);
         fFlags = DB_NEXT;
@@ -798,9 +676,9 @@ bool CTxDB::LoadBlockIndexGuts()
         // Unserialize
 
         try {
-        string strType;
-        ssKey >> strType;
-        if (strType == "blockindex" && !fRequestShutdown)
+        char chType;
+        ssKey >> chType;
+        if (chType == 'b' && !fRequestShutdown)
         {
             CDiskBlockIndex diskindex;
             ssValue >> diskindex;
@@ -808,7 +686,6 @@ bool CTxDB::LoadBlockIndexGuts()
             // Construct block index object
             CBlockIndex* pindexNew = InsertBlockIndex(diskindex.GetBlockHash());
             pindexNew->pprev          = InsertBlockIndex(diskindex.hashPrev);
-            pindexNew->pnext          = InsertBlockIndex(diskindex.hashNext);
             pindexNew->nHeight        = diskindex.nHeight;
             pindexNew->pos            = diskindex.pos;
             pindexNew->nUndoPos       = diskindex.nUndoPos;