index: Add Coinstats index

The index holds the values previously calculated in coinstats.cpp
for each block, representing the state of the UTXO set at each
height.

6 files changed, 437 insertions, 8 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index ddeccd85ea..73d4edb77a 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -152,6 +152,7 @@ BITCOIN_CORE_H = \
   i2p.h \
   index/base.h \
   index/blockfilterindex.h \
+  index/coinstatsindex.h \
   index/disktxpos.h \
   index/txindex.h \
   indirectmap.h \
@@ -318,6 +319,7 @@ libbitcoin_server_a_SOURCES = \
   i2p.cpp \
   index/base.cpp \
   index/blockfilterindex.cpp \
+  index/coinstatsindex.cpp \
   index/txindex.cpp \
   init.cpp \
   mapport.cpp \
diff --git a/src/index/base.h b/src/index/base.h
index ac3c429a5a..d887620524 100644
--- a/src/index/base.h
+++ b/src/index/base.h
@@ -81,6 +81,8 @@ protected:
 
     void ChainStateFlushed(const CBlockLocator& locator) override;
 
+    const CBlockIndex* CurrentIndex() { return m_best_block_index.load(); };
+
     /// Initialize internal state from the database and block index.
     virtual bool Init();
 
diff --git a/src/index/coinstatsindex.cpp b/src/index/coinstatsindex.cpp
new file mode 100644
index 0000000000..7f59323b8c
--- /dev/null
+++ b/src/index/coinstatsindex.cpp
@@ -0,0 +1,363 @@
+// Copyright (c) 2020-2021 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 <chainparams.h>
+#include <coins.h>
+#include <crypto/muhash.h>
+#include <index/coinstatsindex.h>
+#include <node/blockstorage.h>
+#include <serialize.h>
+#include <txdb.h>
+#include <undo.h>
+#include <validation.h>
+
+static constexpr char DB_BLOCK_HASH = 's';
+static constexpr char DB_BLOCK_HEIGHT = 't';
+static constexpr char DB_MUHASH = 'M';
+
+namespace {
+
+struct DBVal {
+    uint256 muhash;
+    uint64_t transaction_output_count;
+    uint64_t bogo_size;
+    CAmount total_amount;
+
+    SERIALIZE_METHODS(DBVal, obj)
+    {
+        READWRITE(obj.muhash);
+        READWRITE(obj.transaction_output_count);
+        READWRITE(obj.bogo_size);
+        READWRITE(obj.total_amount);
+    }
+};
+
+struct DBHeightKey {
+    int height;
+
+    explicit DBHeightKey(int height_in) : height(height_in) {}
+
+    template <typename Stream>
+    void Serialize(Stream& s) const
+    {
+        ser_writedata8(s, DB_BLOCK_HEIGHT);
+        ser_writedata32be(s, height);
+    }
+
+    template <typename Stream>
+    void Unserialize(Stream& s)
+    {
+        char prefix{static_cast<char>(ser_readdata8(s))};
+        if (prefix != DB_BLOCK_HEIGHT) {
+            throw std::ios_base::failure("Invalid format for coinstatsindex DB height key");
+        }
+        height = ser_readdata32be(s);
+    }
+};
+
+struct DBHashKey {
+    uint256 block_hash;
+
+    explicit DBHashKey(const uint256& hash_in) : block_hash(hash_in) {}
+
+    SERIALIZE_METHODS(DBHashKey, obj)
+    {
+        char prefix{DB_BLOCK_HASH};
+        READWRITE(prefix);
+        if (prefix != DB_BLOCK_HASH) {
+            throw std::ios_base::failure("Invalid format for coinstatsindex DB hash key");
+        }
+
+        READWRITE(obj.block_hash);
+    }
+};
+
+}; // namespace
+
+std::unique_ptr<CoinStatsIndex> g_coin_stats_index;
+
+CoinStatsIndex::CoinStatsIndex(size_t n_cache_size, bool f_memory, bool f_wipe)
+{
+    fs::path path{GetDataDir() / "indexes" / "coinstats"};
+    fs::create_directories(path);
+
+    m_db = std::make_unique<CoinStatsIndex::DB>(path / "db", n_cache_size, f_memory, f_wipe);
+}
+
+bool CoinStatsIndex::WriteBlock(const CBlock& block, const CBlockIndex* pindex)
+{
+    CBlockUndo block_undo;
+
+    // Ignore genesis block
+    if (pindex->nHeight > 0) {
+        if (!UndoReadFromDisk(block_undo, pindex)) {
+            return false;
+        }
+
+        std::pair<uint256, DBVal> read_out;
+        if (!m_db->Read(DBHeightKey(pindex->nHeight - 1), read_out)) {
+            return false;
+        }
+
+        uint256 expected_block_hash{pindex->pprev->GetBlockHash()};
+        if (read_out.first != expected_block_hash) {
+            if (!m_db->Read(DBHashKey(expected_block_hash), read_out)) {
+                return error("%s: previous block header belongs to unexpected block %s; expected %s",
+                             __func__, read_out.first.ToString(), expected_block_hash.ToString());
+            }
+        }
+
+        // TODO: Deduplicate BIP30 related code
+        bool is_bip30_block{(pindex->nHeight == 91722 && pindex->GetBlockHash() == uint256S("0x00000000000271a2dc26e7667f8419f2e15416dc6955e5a6c6cdf3f2574dd08e")) ||
+                            (pindex->nHeight == 91812 && pindex->GetBlockHash() == uint256S("0x00000000000af0aed4792b1acee3d966af36cf5def14935db8de83d6f9306f2f"))};
+
+        // Add the new utxos created from the block
+        for (size_t i = 0; i < block.vtx.size(); ++i) {
+            const auto& tx{block.vtx.at(i)};
+
+            // Skip duplicate txid coinbase transactions (BIP30).
+            if (is_bip30_block && tx->IsCoinBase()) {
+                continue;
+            }
+
+            for (size_t j = 0; j < tx->vout.size(); ++j) {
+                const CTxOut& out{tx->vout[j]};
+                Coin coin{out, pindex->nHeight, tx->IsCoinBase()};
+                COutPoint outpoint{tx->GetHash(), static_cast<uint32_t>(j)};
+
+                // Skip unspendable coins
+                if (coin.out.scriptPubKey.IsUnspendable()) continue;
+
+                m_muhash.Insert(MakeUCharSpan(TxOutSer(outpoint, coin)));
+
+                ++m_transaction_output_count;
+                m_total_amount += coin.out.nValue;
+                m_bogo_size += GetBogoSize(coin.out.scriptPubKey);
+            }
+
+            // The coinbase tx has no undo data since no former output is spent
+            if (!tx->IsCoinBase()) {
+                const auto& tx_undo{block_undo.vtxundo.at(i - 1)};
+
+                for (size_t j = 0; j < tx_undo.vprevout.size(); ++j) {
+                    Coin coin{tx_undo.vprevout[j]};
+                    COutPoint outpoint{tx->vin[j].prevout.hash, tx->vin[j].prevout.n};
+
+                    m_muhash.Remove(MakeUCharSpan(TxOutSer(outpoint, coin)));
+
+                    --m_transaction_output_count;
+                    m_total_amount -= coin.out.nValue;
+                    m_bogo_size -= GetBogoSize(coin.out.scriptPubKey);
+                }
+            }
+        }
+    }
+
+    std::pair<uint256, DBVal> value;
+    value.first = pindex->GetBlockHash();
+    value.second.transaction_output_count = m_transaction_output_count;
+    value.second.bogo_size = m_bogo_size;
+    value.second.total_amount = m_total_amount;
+
+    uint256 out;
+    m_muhash.Finalize(out);
+    value.second.muhash = out;
+
+    return m_db->Write(DBHeightKey(pindex->nHeight), value) && m_db->Write(DB_MUHASH, m_muhash);
+}
+
+static bool CopyHeightIndexToHashIndex(CDBIterator& db_it, CDBBatch& batch,
+                                       const std::string& index_name,
+                                       int start_height, int stop_height)
+{
+    DBHeightKey key{start_height};
+    db_it.Seek(key);
+
+    for (int height = start_height; height <= stop_height; ++height) {
+        if (!db_it.GetKey(key) || key.height != height) {
+            return error("%s: unexpected key in %s: expected (%c, %d)",
+                         __func__, index_name, DB_BLOCK_HEIGHT, height);
+        }
+
+        std::pair<uint256, DBVal> value;
+        if (!db_it.GetValue(value)) {
+            return error("%s: unable to read value in %s at key (%c, %d)",
+                         __func__, index_name, DB_BLOCK_HEIGHT, height);
+        }
+
+        batch.Write(DBHashKey(value.first), std::move(value.second));
+
+        db_it.Next();
+    }
+    return true;
+}
+
+bool CoinStatsIndex::Rewind(const CBlockIndex* current_tip, const CBlockIndex* new_tip)
+{
+    assert(current_tip->GetAncestor(new_tip->nHeight) == new_tip);
+
+    CDBBatch batch(*m_db);
+    std::unique_ptr<CDBIterator> db_it(m_db->NewIterator());
+
+    // During a reorg, we need to copy all hash digests for blocks that are
+    // getting disconnected from the height index to the hash index so we can
+    // still find them when the height index entries are overwritten.
+    if (!CopyHeightIndexToHashIndex(*db_it, batch, m_name, new_tip->nHeight, current_tip->nHeight)) {
+        return false;
+    }
+
+    if (!m_db->WriteBatch(batch)) return false;
+
+    {
+        LOCK(cs_main);
+        CBlockIndex* iter_tip{g_chainman.m_blockman.LookupBlockIndex(current_tip->GetBlockHash())};
+        const auto& consensus_params{Params().GetConsensus()};
+
+        do {
+            CBlock block;
+
+            if (!ReadBlockFromDisk(block, iter_tip, consensus_params)) {
+                return error("%s: Failed to read block %s from disk",
+                             __func__, iter_tip->GetBlockHash().ToString());
+            }
+
+            ReverseBlock(block, iter_tip);
+
+            iter_tip = iter_tip->GetAncestor(iter_tip->nHeight - 1);
+        } while (new_tip != iter_tip);
+    }
+
+    return BaseIndex::Rewind(current_tip, new_tip);
+}
+
+static bool LookUpOne(const CDBWrapper& db, const CBlockIndex* block_index, DBVal& result)
+{
+    // First check if the result is stored under the height index and the value
+    // there matches the block hash. This should be the case if the block is on
+    // the active chain.
+    std::pair<uint256, DBVal> read_out;
+    if (!db.Read(DBHeightKey(block_index->nHeight), read_out)) {
+        return false;
+    }
+    if (read_out.first == block_index->GetBlockHash()) {
+        result = std::move(read_out.second);
+        return true;
+    }
+
+    // If value at the height index corresponds to an different block, the
+    // result will be stored in the hash index.
+    return db.Read(DBHashKey(block_index->GetBlockHash()), result);
+}
+
+bool CoinStatsIndex::LookUpStats(const CBlockIndex* block_index, CCoinsStats& coins_stats) const
+{
+    DBVal entry;
+    if (!LookUpOne(*m_db, block_index, entry)) {
+        return false;
+    }
+
+    coins_stats.hashSerialized = entry.muhash;
+    coins_stats.nTransactionOutputs = entry.transaction_output_count;
+    coins_stats.nBogoSize = entry.bogo_size;
+    coins_stats.nTotalAmount = entry.total_amount;
+
+    return true;
+}
+
+bool CoinStatsIndex::Init()
+{
+    if (!m_db->Read(DB_MUHASH, m_muhash)) {
+        // Check that the cause of the read failure is that the key does not
+        // exist. Any other errors indicate database corruption or a disk
+        // failure, and starting the index would cause further corruption.
+        if (m_db->Exists(DB_MUHASH)) {
+            return error("%s: Cannot read current %s state; index may be corrupted",
+                         __func__, GetName());
+        }
+    }
+
+    if (BaseIndex::Init()) {
+        const CBlockIndex* pindex{CurrentIndex()};
+
+        if (pindex) {
+            DBVal entry;
+            if (!LookUpOne(*m_db, pindex, entry)) {
+                return false;
+            }
+
+            m_transaction_output_count = entry.transaction_output_count;
+            m_bogo_size = entry.bogo_size;
+            m_total_amount = entry.total_amount;
+        }
+
+        return true;
+    }
+
+    return false;
+}
+
+// Reverse a single block as part of a reorg
+bool CoinStatsIndex::ReverseBlock(const CBlock& block, const CBlockIndex* pindex)
+{
+    CBlockUndo block_undo;
+    std::pair<uint256, DBVal> read_out;
+
+    // Ignore genesis block
+    if (pindex->nHeight > 0) {
+        if (!UndoReadFromDisk(block_undo, pindex)) {
+            return false;
+        }
+
+        if (!m_db->Read(DBHeightKey(pindex->nHeight - 1), read_out)) {
+            return false;
+        }
+
+        uint256 expected_block_hash{pindex->pprev->GetBlockHash()};
+        if (read_out.first != expected_block_hash) {
+            if (!m_db->Read(DBHashKey(expected_block_hash), read_out)) {
+                return error("%s: previous block header belongs to unexpected block %s; expected %s",
+                             __func__, read_out.first.ToString(), expected_block_hash.ToString());
+            }
+        }
+    }
+
+    // Remove the new UTXOs that were created from the block
+    for (size_t i = 0; i < block.vtx.size(); ++i) {
+        const auto& tx{block.vtx.at(i)};
+
+        for (size_t j = 0; j < tx->vout.size(); ++j) {
+            const CTxOut& out{tx->vout[j]};
+            COutPoint outpoint{tx->GetHash(), static_cast<uint32_t>(j)};
+            Coin coin{out, pindex->nHeight, tx->IsCoinBase()};
+
+            // Skip unspendable coins
+            if (coin.out.scriptPubKey.IsUnspendable()) continue;
+
+            m_muhash.Remove(MakeUCharSpan(TxOutSer(outpoint, coin)));
+        }
+
+        // The coinbase tx has no undo data since no former output is spent
+        if (!tx->IsCoinBase()) {
+            const auto& tx_undo{block_undo.vtxundo.at(i - 1)};
+
+            for (size_t j = 0; j < tx_undo.vprevout.size(); ++j) {
+                Coin coin{tx_undo.vprevout[j]};
+                COutPoint outpoint{tx->vin[j].prevout.hash, tx->vin[j].prevout.n};
+
+                m_muhash.Insert(MakeUCharSpan(TxOutSer(outpoint, coin)));
+            }
+        }
+    }
+
+    // Check that the rolled back internal value of muhash is consistent with the DB read out
+    uint256 out;
+    m_muhash.Finalize(out);
+    Assert(read_out.second.muhash == out);
+
+    m_transaction_output_count = read_out.second.transaction_output_count;
+    m_total_amount = read_out.second.total_amount;
+    m_bogo_size = read_out.second.bogo_size;
+
+    return m_db->Write(DB_MUHASH, m_muhash);
+}
diff --git a/src/index/coinstatsindex.h b/src/index/coinstatsindex.h
new file mode 100644
index 0000000000..4d57e80770
--- /dev/null
+++ b/src/index/coinstatsindex.h
@@ -0,0 +1,52 @@
+// Copyright (c) 2020-2021 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_INDEX_COINSTATSINDEX_H
+#define BITCOIN_INDEX_COINSTATSINDEX_H
+
+#include <chain.h>
+#include <crypto/muhash.h>
+#include <flatfile.h>
+#include <index/base.h>
+#include <node/coinstats.h>
+
+/**
+ * CoinStatsIndex maintains statistics on the UTXO set.
+ */
+class CoinStatsIndex final : public BaseIndex
+{
+private:
+    std::string m_name;
+    std::unique_ptr<BaseIndex::DB> m_db;
+
+    MuHash3072 m_muhash;
+    uint64_t m_transaction_output_count{0};
+    uint64_t m_bogo_size{0};
+    CAmount m_total_amount{0};
+
+    bool ReverseBlock(const CBlock& block, const CBlockIndex* pindex);
+
+protected:
+    bool Init() override;
+
+    bool WriteBlock(const CBlock& block, const CBlockIndex* pindex) override;
+
+    bool Rewind(const CBlockIndex* current_tip, const CBlockIndex* new_tip) override;
+
+    BaseIndex::DB& GetDB() const override { return *m_db; }
+
+    const char* GetName() const override { return "coinstatsindex"; }
+
+public:
+    // Constructs the index, which becomes available to be queried.
+    explicit CoinStatsIndex(size_t n_cache_size, bool f_memory = false, bool f_wipe = false);
+
+    // Look up stats for a specific block using CBlockIndex
+    bool LookUpStats(const CBlockIndex* block_index, CCoinsStats& coins_stats) const;
+};
+
+/// The global UTXO set hash object.
+extern std::unique_ptr<CoinStatsIndex> g_coin_stats_index;
+
+#endif // BITCOIN_INDEX_COINSTATSINDEX_H
diff --git a/src/node/coinstats.cpp b/src/node/coinstats.cpp
index b17a475ca3..a9af53ca80 100644
--- a/src/node/coinstats.cpp
+++ b/src/node/coinstats.cpp
@@ -16,14 +16,22 @@
 #include <map>
 
 // Database-independent metric indicating the UTXO set size
-static uint64_t GetBogoSize(const CScript& scriptPubKey)
+uint64_t GetBogoSize(const CScript& script_pub_key)
 {
     return 32 /* txid */ +
            4 /* vout index */ +
            4 /* height + coinbase */ +
            8 /* amount */ +
            2 /* scriptPubKey len */ +
-           scriptPubKey.size() /* scriptPubKey */;
+           script_pub_key.size() /* scriptPubKey */;
+}
+
+CDataStream TxOutSer(const COutPoint& outpoint, const Coin& coin) {
+    CDataStream ss(SER_DISK, PROTOCOL_VERSION);
+    ss << outpoint;
+    ss << static_cast<uint32_t>(coin.nHeight * 2 + coin.fCoinBase);
+    ss << coin.out;
+    return ss;
 }
 
 //! Warning: be very careful when changing this! assumeutxo and UTXO snapshot
@@ -63,12 +71,7 @@ static void ApplyHash(MuHash3072& muhash, const uint256& hash, const std::map<ui
     for (auto it = outputs.begin(); it != outputs.end(); ++it) {
         COutPoint outpoint = COutPoint(hash, it->first);
         Coin coin = it->second;
-
-        CDataStream ss(SER_DISK, PROTOCOL_VERSION);
-        ss << outpoint;
-        ss << static_cast<uint32_t>(coin.nHeight * 2 + coin.fCoinBase);
-        ss << coin.out;
-        muhash.Insert(MakeUCharSpan(ss));
+        muhash.Insert(MakeUCharSpan(TxOutSer(outpoint, coin)));
     }
 }
 
diff --git a/src/node/coinstats.h b/src/node/coinstats.h
index 85896a2a1d..826df2fd73 100644
--- a/src/node/coinstats.h
+++ b/src/node/coinstats.h
@@ -7,6 +7,9 @@
 #define BITCOIN_NODE_COINSTATS_H
 
 #include <amount.h>
+#include <chain.h>
+#include <coins.h>
+#include <streams.h>
 #include <uint256.h>
 
 #include <cstdint>
@@ -42,4 +45,8 @@ struct CCoinsStats
 //! Calculate statistics about the unspent transaction output set
 bool GetUTXOStats(CCoinsView* view, BlockManager& blockman, CCoinsStats& stats, const std::function<void()>& interruption_point = {});
 
+uint64_t GetBogoSize(const CScript& script_pub_key);
+
+CDataStream TxOutSer(const COutPoint& outpoint, const Coin& coin);
+
 #endif // BITCOIN_NODE_COINSTATS_H