1// Copyright (c) 2022-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <kernel/coinstats.h>
6
7#include <chain.h>
8#include <coins.h>
9#include <crypto/muhash.h>
10#include <hash.h>
11#include <node/blockstorage.h>
12#include <primitives/transaction.h>
13#include <script/script.h>
14#include <span.h>
15#include <streams.h>
16#include <sync.h>
17#include <txdb.h>
18#include <uint256.h>
19#include <util/check.h>
20#include <util/log.h>
21#include <util/overflow.h>
22#include <validation.h>
23
24#include <cstddef>
25#include <map>
26#include <memory>
27#include <utility>
28
29namespace kernel {
30
31CCoinsStats::CCoinsStats(int block_height, const uint256& block_hash)
32    : nHeight(block_height),
33      hashBlock(block_hash) {}
34
35// Database-independent metric indicating the UTXO set size
36uint64_t GetBogoSize(const CScript& script_pub_key)
37{
38    return 32 /* txid */ +
39           4 /* vout index */ +
40           4 /* height + coinbase */ +
41           8 /* amount */ +
42           2 /* scriptPubKey len */ +
43           script_pub_key.size() /* scriptPubKey */;
44}
45
46template <typename T>
47static void TxOutSer(T& ss, const COutPoint& outpoint, const Coin& coin)
48{
49    ss << outpoint;
50    ss << ((uint32_t{coin.nHeight} << 1) | uint32_t{coin.fCoinBase});
51    ss << coin.out;
52}
53
54static void ApplyCoinHash(HashWriter& ss, const COutPoint& outpoint, const Coin& coin)
55{
56    TxOutSer(ss, outpoint, coin);
57}
58
59void ApplyCoinHash(MuHash3072& muhash, const COutPoint& outpoint, const Coin& coin)
60{
61    DataStream ss{};
62    TxOutSer(ss, outpoint, coin);
63    muhash.Insert(MakeUCharSpan(ss));
64}
65
66void RemoveCoinHash(MuHash3072& muhash, const COutPoint& outpoint, const Coin& coin)
67{
68    DataStream ss{};
69    TxOutSer(ss, outpoint, coin);
70    muhash.Remove(MakeUCharSpan(ss));
71}
72
73static void ApplyCoinHash(std::nullptr_t, const COutPoint& outpoint, const Coin& coin) {}
74
75//! Warning: be very careful when changing this! assumeutxo and UTXO snapshot
76//! validation commitments are reliant on the hash constructed by this
77//! function.
78//!
79//! If the construction of this hash is changed, it will invalidate
80//! existing UTXO snapshots. This will not result in any kind of consensus
81//! failure, but it will force clients that were expecting to make use of
82//! assumeutxo to do traditional IBD instead.
83//!
84//! It is also possible, though very unlikely, that a change in this
85//! construction could cause a previously invalid (and potentially malicious)
86//! UTXO snapshot to be considered valid.
87template <typename T>
88static void ApplyHash(T& hash_obj, const Txid& hash, const std::map<uint32_t, Coin>& outputs)
89{
90    for (auto it = outputs.begin(); it != outputs.end(); ++it) {
91        COutPoint outpoint = COutPoint(hash, it->first);
92        Coin coin = it->second;
93        ApplyCoinHash(hash_obj, outpoint, coin);
94    }
95}
96
97static void ApplyStats(CCoinsStats& stats, const std::map<uint32_t, Coin>& outputs)
98{
99    assert(!outputs.empty());
100    stats.nTransactions++;
101    for (auto it = outputs.begin(); it != outputs.end(); ++it) {
102        stats.nTransactionOutputs++;
103        if (stats.total_amount.has_value()) {
104            stats.total_amount = CheckedAdd(*stats.total_amount, it->second.out.nValue);
105        }
106        stats.nBogoSize += GetBogoSize(it->second.out.scriptPubKey);
107    }
108}
109
110//! Calculate statistics about the unspent transaction output set
111template <typename T>
112static std::optional<CCoinsStats> ComputeUTXOStats(T hash_obj, const CCoinsViewDB& view, node::BlockManager& blockman, const std::function<void()>& interruption_point)
113{
114    std::unique_ptr<CCoinsViewCursor> pcursor;
115    CBlockIndex* pindex;
116    {
117        LOCK(::cs_main);
118        pcursor = view.Cursor();
119        pindex = blockman.LookupBlockIndex(pcursor->GetBestBlock());
120    }
121    CCoinsStats stats{Assert(pindex)->nHeight, pindex->GetBlockHash()};
122
123    Txid prevkey;
124    std::map<uint32_t, Coin> outputs;
125    while (pcursor->Valid()) {
126        if (interruption_point) interruption_point();
127        COutPoint key;
128        Coin coin;
129        if (pcursor->GetKey(key) && pcursor->GetValue(coin)) {
130            if (!outputs.empty() && key.hash != prevkey) {
131                ApplyStats(stats, outputs);
132                ApplyHash(hash_obj, prevkey, outputs);
133                outputs.clear();
134            }
135            prevkey = key.hash;
136            outputs[key.n] = std::move(coin);
137            stats.coins_count++;
138        } else {
139            LogError("%s: unable to read value\n", __func__);
140            return std::nullopt;
141        }
142        pcursor->Next();
143    }
144    if (!outputs.empty()) {
145        ApplyStats(stats, outputs);
146        ApplyHash(hash_obj, prevkey, outputs);
147    }
148
149    FinalizeHash(hash_obj, stats);
150
151    stats.nDiskSize = view.EstimateSize();
152    return stats;
153}
154
155std::optional<CCoinsStats> ComputeUTXOStats(CoinStatsHashType hash_type, const CCoinsViewDB& view, node::BlockManager& blockman, const std::function<void()>& interruption_point)
156{
157    return [&]() -> std::optional<CCoinsStats> {
158        switch (hash_type) {
159        case(CoinStatsHashType::HASH_SERIALIZED): {
160            HashWriter ss{};
161            return ComputeUTXOStats(ss, view, blockman, interruption_point);
162        }
163        case(CoinStatsHashType::MUHASH): {
164            MuHash3072 muhash;
165            return ComputeUTXOStats(muhash, view, blockman, interruption_point);
166        }
167        case(CoinStatsHashType::NONE): {
168            return ComputeUTXOStats(nullptr, view, blockman, interruption_point);
169        }
170        } // no default case, so the compiler can warn about missing cases
171        assert(false);
172    }();
173}
174
175static void FinalizeHash(HashWriter& ss, CCoinsStats& stats)
176{
177    stats.hashSerialized = ss.GetHash();
178}
179static void FinalizeHash(MuHash3072& muhash, CCoinsStats& stats)
180{
181    uint256 out;
182    muhash.Finalize(out);
183    stats.hashSerialized = out;
184}
185static void FinalizeHash(std::nullptr_t, CCoinsStats& stats) {}
186
187} // namespace kernel
188