blockencodings_tests.cpp
1 // Copyright (c) 2011-2022 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 <blockencodings.h> 6 #include <chainparams.h> 7 #include <consensus/merkle.h> 8 #include <pow.h> 9 #include <streams.h> 10 #include <test/util/random.h> 11 #include <test/util/txmempool.h> 12 13 #include <test/util/setup_common.h> 14 15 #include <boost/test/unit_test.hpp> 16 17 const std::vector<std::pair<Wtxid, CTransactionRef>> empty_extra_txn; 18 19 BOOST_FIXTURE_TEST_SUITE(blockencodings_tests, RegTestingSetup) 20 21 static CMutableTransaction BuildTransactionTestCase() { 22 CMutableTransaction tx; 23 tx.vin.resize(1); 24 tx.vin[0].scriptSig.resize(10); 25 tx.vout.resize(1); 26 tx.vout[0].nValue = 42; 27 return tx; 28 } 29 30 static CBlock BuildBlockTestCase(FastRandomContext& ctx) { 31 CBlock block; 32 CMutableTransaction tx = BuildTransactionTestCase(); 33 34 block.vtx.resize(3); 35 block.vtx[0] = MakeTransactionRef(tx); 36 block.nVersion = 42; 37 block.hashPrevBlock = ctx.rand256(); 38 block.nBits = 0x207fffff; 39 40 tx.vin[0].prevout.hash = Txid::FromUint256(ctx.rand256()); 41 tx.vin[0].prevout.n = 0; 42 block.vtx[1] = MakeTransactionRef(tx); 43 44 tx.vin.resize(10); 45 for (size_t i = 0; i < tx.vin.size(); i++) { 46 tx.vin[i].prevout.hash = Txid::FromUint256(ctx.rand256()); 47 tx.vin[i].prevout.n = 0; 48 } 49 block.vtx[2] = MakeTransactionRef(tx); 50 51 bool mutated; 52 block.hashMerkleRoot = BlockMerkleRoot(block, &mutated); 53 assert(!mutated); 54 while (!CheckProofOfWork(block.GetHash(), block.nBits, Params().GetConsensus())) ++block.nNonce; 55 return block; 56 } 57 58 // Number of shared use_counts we expect for a tx we haven't touched 59 // (block + mempool entry + our copy from the GetSharedTx call) 60 constexpr long SHARED_TX_OFFSET{3}; 61 62 BOOST_AUTO_TEST_CASE(SimpleRoundTripTest) 63 { 64 CTxMemPool& pool = *Assert(m_node.mempool); 65 TestMemPoolEntryHelper entry; 66 auto rand_ctx(FastRandomContext(uint256{42})); 67 CBlock block(BuildBlockTestCase(rand_ctx)); 68 69 LOCK2(cs_main, pool.cs); 70 TryAddToMempool(pool, entry.FromTx(block.vtx[2])); 71 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 0); 72 73 // Do a simple ShortTxIDs RT 74 { 75 CBlockHeaderAndShortTxIDs shortIDs{block, rand_ctx.rand64()}; 76 77 DataStream stream{}; 78 stream << shortIDs; 79 80 CBlockHeaderAndShortTxIDs shortIDs2; 81 stream >> shortIDs2; 82 83 PartiallyDownloadedBlock partialBlock(&pool); 84 BOOST_CHECK(partialBlock.InitData(shortIDs2, empty_extra_txn) == READ_STATUS_OK); 85 BOOST_CHECK( partialBlock.IsTxAvailable(0)); 86 BOOST_CHECK(!partialBlock.IsTxAvailable(1)); 87 BOOST_CHECK( partialBlock.IsTxAvailable(2)); 88 89 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 1); 90 91 size_t poolSize = pool.size(); 92 pool.removeRecursive(*block.vtx[2], MemPoolRemovalReason::REPLACED); 93 BOOST_CHECK_EQUAL(pool.size(), poolSize - 1); 94 95 CBlock block2; 96 { 97 PartiallyDownloadedBlock tmp = partialBlock; 98 BOOST_CHECK(partialBlock.FillBlock(block2, {}, /*segwit_active=*/true) == READ_STATUS_INVALID); // No transactions 99 partialBlock = tmp; 100 } 101 102 // Wrong transaction 103 { 104 PartiallyDownloadedBlock tmp = partialBlock; 105 partialBlock.FillBlock(block2, {block.vtx[2]}, /*segwit_active=*/true); // Current implementation doesn't check txn here, but don't require that 106 partialBlock = tmp; 107 } 108 bool mutated; 109 BOOST_CHECK(block.hashMerkleRoot != BlockMerkleRoot(block2, &mutated)); 110 111 CBlock block3; 112 BOOST_CHECK(partialBlock.FillBlock(block3, {block.vtx[1]}, /*segwit_active=*/true) == READ_STATUS_OK); 113 BOOST_CHECK_EQUAL(block.GetHash().ToString(), block3.GetHash().ToString()); 114 BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block3, &mutated).ToString()); 115 BOOST_CHECK(!mutated); 116 } 117 } 118 119 class TestHeaderAndShortIDs { 120 // Utility to encode custom CBlockHeaderAndShortTxIDs 121 public: 122 CBlockHeader header; 123 uint64_t nonce; 124 std::vector<uint64_t> shorttxids; 125 std::vector<PrefilledTransaction> prefilledtxn; 126 127 explicit TestHeaderAndShortIDs(const CBlockHeaderAndShortTxIDs& orig) { 128 DataStream stream{}; 129 stream << orig; 130 stream >> *this; 131 } 132 explicit TestHeaderAndShortIDs(const CBlock& block, FastRandomContext& ctx) : 133 TestHeaderAndShortIDs(CBlockHeaderAndShortTxIDs{block, ctx.rand64()}) {} 134 135 uint64_t GetShortID(const Wtxid& txhash) const { 136 DataStream stream{}; 137 stream << *this; 138 CBlockHeaderAndShortTxIDs base; 139 stream >> base; 140 return base.GetShortID(txhash); 141 } 142 143 SERIALIZE_METHODS(TestHeaderAndShortIDs, obj) { READWRITE(obj.header, obj.nonce, Using<VectorFormatter<CustomUintFormatter<CBlockHeaderAndShortTxIDs::SHORTTXIDS_LENGTH>>>(obj.shorttxids), obj.prefilledtxn); } 144 }; 145 146 BOOST_AUTO_TEST_CASE(NonCoinbasePreforwardRTTest) 147 { 148 CTxMemPool& pool = *Assert(m_node.mempool); 149 TestMemPoolEntryHelper entry; 150 auto rand_ctx(FastRandomContext(uint256{42})); 151 CBlock block(BuildBlockTestCase(rand_ctx)); 152 153 LOCK2(cs_main, pool.cs); 154 TryAddToMempool(pool, entry.FromTx(block.vtx[2])); 155 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 0); 156 157 Txid txhash; 158 159 // Test with pre-forwarding tx 1, but not coinbase 160 { 161 TestHeaderAndShortIDs shortIDs(block, rand_ctx); 162 shortIDs.prefilledtxn.resize(1); 163 shortIDs.prefilledtxn[0] = {1, block.vtx[1]}; 164 shortIDs.shorttxids.resize(2); 165 shortIDs.shorttxids[0] = shortIDs.GetShortID(block.vtx[0]->GetWitnessHash()); 166 shortIDs.shorttxids[1] = shortIDs.GetShortID(block.vtx[2]->GetWitnessHash()); 167 168 DataStream stream{}; 169 stream << shortIDs; 170 171 CBlockHeaderAndShortTxIDs shortIDs2; 172 stream >> shortIDs2; 173 174 PartiallyDownloadedBlock partialBlock(&pool); 175 BOOST_CHECK(partialBlock.InitData(shortIDs2, empty_extra_txn) == READ_STATUS_OK); 176 BOOST_CHECK(!partialBlock.IsTxAvailable(0)); 177 BOOST_CHECK( partialBlock.IsTxAvailable(1)); 178 BOOST_CHECK( partialBlock.IsTxAvailable(2)); 179 180 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 1); // +1 because of partialBlock 181 182 CBlock block2; 183 { 184 PartiallyDownloadedBlock tmp = partialBlock; 185 BOOST_CHECK(partialBlock.FillBlock(block2, {}, /*segwit_active=*/true) == READ_STATUS_INVALID); // No transactions 186 partialBlock = tmp; 187 } 188 189 // Wrong transaction 190 { 191 PartiallyDownloadedBlock tmp = partialBlock; 192 partialBlock.FillBlock(block2, {block.vtx[1]}, /*segwit_active=*/true); // Current implementation doesn't check txn here, but don't require that 193 partialBlock = tmp; 194 } 195 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 2); // +2 because of partialBlock and block2 196 bool mutated; 197 BOOST_CHECK(block.hashMerkleRoot != BlockMerkleRoot(block2, &mutated)); 198 199 CBlock block3; 200 PartiallyDownloadedBlock partialBlockCopy = partialBlock; 201 BOOST_CHECK(partialBlock.FillBlock(block3, {block.vtx[0]}, /*segwit_active=*/true) == READ_STATUS_OK); 202 BOOST_CHECK_EQUAL(block.GetHash().ToString(), block3.GetHash().ToString()); 203 BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block3, &mutated).ToString()); 204 BOOST_CHECK(!mutated); 205 206 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 3); // +2 because of partialBlock and block2 and block3 207 208 txhash = block.vtx[2]->GetHash(); 209 block.vtx.clear(); 210 block2.vtx.clear(); 211 block3.vtx.clear(); 212 BOOST_CHECK_EQUAL(pool.get(txhash).use_count(), SHARED_TX_OFFSET + 1 - 1); // + 1 because of partialBlock; -1 because of block. 213 } 214 BOOST_CHECK_EQUAL(pool.get(txhash).use_count(), SHARED_TX_OFFSET - 1); // -1 because of block 215 } 216 217 BOOST_AUTO_TEST_CASE(SufficientPreforwardRTTest) 218 { 219 CTxMemPool& pool = *Assert(m_node.mempool); 220 TestMemPoolEntryHelper entry; 221 auto rand_ctx(FastRandomContext(uint256{42})); 222 CBlock block(BuildBlockTestCase(rand_ctx)); 223 224 LOCK2(cs_main, pool.cs); 225 TryAddToMempool(pool, entry.FromTx(block.vtx[1])); 226 BOOST_CHECK_EQUAL(pool.get(block.vtx[1]->GetHash()).use_count(), SHARED_TX_OFFSET + 0); 227 228 Txid txhash; 229 230 // Test with pre-forwarding coinbase + tx 2 with tx 1 in mempool 231 { 232 TestHeaderAndShortIDs shortIDs(block, rand_ctx); 233 shortIDs.prefilledtxn.resize(2); 234 shortIDs.prefilledtxn[0] = {0, block.vtx[0]}; 235 shortIDs.prefilledtxn[1] = {1, block.vtx[2]}; // id == 1 as it is 1 after index 1 236 shortIDs.shorttxids.resize(1); 237 shortIDs.shorttxids[0] = shortIDs.GetShortID(block.vtx[1]->GetWitnessHash()); 238 239 DataStream stream{}; 240 stream << shortIDs; 241 242 CBlockHeaderAndShortTxIDs shortIDs2; 243 stream >> shortIDs2; 244 245 PartiallyDownloadedBlock partialBlock(&pool); 246 BOOST_CHECK(partialBlock.InitData(shortIDs2, empty_extra_txn) == READ_STATUS_OK); 247 BOOST_CHECK( partialBlock.IsTxAvailable(0)); 248 BOOST_CHECK( partialBlock.IsTxAvailable(1)); 249 BOOST_CHECK( partialBlock.IsTxAvailable(2)); 250 251 BOOST_CHECK_EQUAL(pool.get(block.vtx[1]->GetHash()).use_count(), SHARED_TX_OFFSET + 1); 252 253 CBlock block2; 254 PartiallyDownloadedBlock partialBlockCopy = partialBlock; 255 BOOST_CHECK(partialBlock.FillBlock(block2, {}, /*segwit_active=*/true) == READ_STATUS_OK); 256 BOOST_CHECK_EQUAL(block.GetHash().ToString(), block2.GetHash().ToString()); 257 bool mutated; 258 BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block2, &mutated).ToString()); 259 BOOST_CHECK(!mutated); 260 261 txhash = block.vtx[1]->GetHash(); 262 block.vtx.clear(); 263 block2.vtx.clear(); 264 BOOST_CHECK_EQUAL(pool.get(txhash).use_count(), SHARED_TX_OFFSET + 1 - 1); // + 1 because of partialBlock; -1 because of block. 265 } 266 BOOST_CHECK_EQUAL(pool.get(txhash).use_count(), SHARED_TX_OFFSET - 1); // -1 because of block 267 } 268 269 BOOST_AUTO_TEST_CASE(EmptyBlockRoundTripTest) 270 { 271 CTxMemPool& pool = *Assert(m_node.mempool); 272 CMutableTransaction coinbase = BuildTransactionTestCase(); 273 274 CBlock block; 275 auto rand_ctx(FastRandomContext(uint256{42})); 276 block.vtx.resize(1); 277 block.vtx[0] = MakeTransactionRef(std::move(coinbase)); 278 block.nVersion = 42; 279 block.hashPrevBlock = rand_ctx.rand256(); 280 block.nBits = 0x207fffff; 281 282 bool mutated; 283 block.hashMerkleRoot = BlockMerkleRoot(block, &mutated); 284 assert(!mutated); 285 while (!CheckProofOfWork(block.GetHash(), block.nBits, Params().GetConsensus())) ++block.nNonce; 286 287 // Test simple header round-trip with only coinbase 288 { 289 CBlockHeaderAndShortTxIDs shortIDs{block, rand_ctx.rand64()}; 290 291 DataStream stream{}; 292 stream << shortIDs; 293 294 CBlockHeaderAndShortTxIDs shortIDs2; 295 stream >> shortIDs2; 296 297 PartiallyDownloadedBlock partialBlock(&pool); 298 BOOST_CHECK(partialBlock.InitData(shortIDs2, empty_extra_txn) == READ_STATUS_OK); 299 BOOST_CHECK(partialBlock.IsTxAvailable(0)); 300 301 CBlock block2; 302 std::vector<CTransactionRef> vtx_missing; 303 BOOST_CHECK(partialBlock.FillBlock(block2, vtx_missing, /*segwit_active=*/true) == READ_STATUS_OK); 304 BOOST_CHECK_EQUAL(block.GetHash().ToString(), block2.GetHash().ToString()); 305 BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block2, &mutated).ToString()); 306 BOOST_CHECK(!mutated); 307 } 308 } 309 310 BOOST_AUTO_TEST_CASE(ReceiveWithExtraTransactions) { 311 CTxMemPool& pool = *Assert(m_node.mempool); 312 TestMemPoolEntryHelper entry; 313 auto rand_ctx(FastRandomContext(uint256{42})); 314 315 CMutableTransaction mtx = BuildTransactionTestCase(); 316 mtx.vin[0].prevout.hash = Txid::FromUint256(rand_ctx.rand256()); 317 mtx.vin[0].prevout.n = 0; 318 const CTransactionRef non_block_tx = MakeTransactionRef(std::move(mtx)); 319 320 CBlock block(BuildBlockTestCase(rand_ctx)); 321 std::vector<std::pair<Wtxid, CTransactionRef>> extra_txn; 322 extra_txn.resize(10); 323 324 LOCK2(cs_main, pool.cs); 325 TryAddToMempool(pool, entry.FromTx(block.vtx[2])); 326 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 0); 327 // Ensure the non_block_tx is actually not in the block 328 for (const auto &block_tx : block.vtx) { 329 BOOST_CHECK_NE(block_tx->GetHash(), non_block_tx->GetHash()); 330 } 331 // Ensure block.vtx[1] is not in pool 332 BOOST_CHECK_EQUAL(pool.get(block.vtx[1]->GetHash()), nullptr); 333 334 { 335 const CBlockHeaderAndShortTxIDs cmpctblock{block, rand_ctx.rand64()}; 336 PartiallyDownloadedBlock partial_block(&pool); 337 PartiallyDownloadedBlock partial_block_with_extra(&pool); 338 339 BOOST_CHECK(partial_block.InitData(cmpctblock, extra_txn) == READ_STATUS_OK); 340 BOOST_CHECK( partial_block.IsTxAvailable(0)); 341 BOOST_CHECK(!partial_block.IsTxAvailable(1)); 342 BOOST_CHECK( partial_block.IsTxAvailable(2)); 343 344 // Add an unrelated tx to extra_txn: 345 extra_txn[0] = {non_block_tx->GetWitnessHash(), non_block_tx}; 346 // and a tx from the block that's not in the mempool: 347 extra_txn[1] = {block.vtx[1]->GetWitnessHash(), block.vtx[1]}; 348 349 BOOST_CHECK(partial_block_with_extra.InitData(cmpctblock, extra_txn) == READ_STATUS_OK); 350 BOOST_CHECK(partial_block_with_extra.IsTxAvailable(0)); 351 // This transaction is now available via extra_txn: 352 BOOST_CHECK(partial_block_with_extra.IsTxAvailable(1)); 353 BOOST_CHECK(partial_block_with_extra.IsTxAvailable(2)); 354 } 355 } 356 357 BOOST_AUTO_TEST_CASE(TransactionsRequestSerializationTest) { 358 BlockTransactionsRequest req1; 359 req1.blockhash = m_rng.rand256(); 360 req1.indexes.resize(4); 361 req1.indexes[0] = 0; 362 req1.indexes[1] = 1; 363 req1.indexes[2] = 3; 364 req1.indexes[3] = 4; 365 366 DataStream stream{}; 367 stream << req1; 368 369 BlockTransactionsRequest req2; 370 stream >> req2; 371 372 BOOST_CHECK_EQUAL(req1.blockhash.ToString(), req2.blockhash.ToString()); 373 BOOST_CHECK_EQUAL(req1.indexes.size(), req2.indexes.size()); 374 BOOST_CHECK_EQUAL(req1.indexes[0], req2.indexes[0]); 375 BOOST_CHECK_EQUAL(req1.indexes[1], req2.indexes[1]); 376 BOOST_CHECK_EQUAL(req1.indexes[2], req2.indexes[2]); 377 BOOST_CHECK_EQUAL(req1.indexes[3], req2.indexes[3]); 378 } 379 380 BOOST_AUTO_TEST_CASE(TransactionsRequestDeserializationMaxTest) { 381 // Check that the highest legal index is decoded correctly 382 BlockTransactionsRequest req0; 383 req0.blockhash = m_rng.rand256(); 384 req0.indexes.resize(1); 385 req0.indexes[0] = 0xffff; 386 DataStream stream{}; 387 stream << req0; 388 389 BlockTransactionsRequest req1; 390 stream >> req1; 391 BOOST_CHECK_EQUAL(req0.indexes.size(), req1.indexes.size()); 392 BOOST_CHECK_EQUAL(req0.indexes[0], req1.indexes[0]); 393 } 394 395 BOOST_AUTO_TEST_CASE(TransactionsRequestDeserializationOverflowTest) { 396 // Any set of index deltas that starts with N values that sum to (0x10000 - N) 397 // causes the edge-case overflow that was originally not checked for. Such 398 // a request cannot be created by serializing a real BlockTransactionsRequest 399 // due to the overflow, so here we'll serialize from raw deltas. 400 BlockTransactionsRequest req0; 401 req0.blockhash = m_rng.rand256(); 402 req0.indexes.resize(3); 403 req0.indexes[0] = 0x7000; 404 req0.indexes[1] = 0x10000 - 0x7000 - 2; 405 req0.indexes[2] = 0; 406 DataStream stream{}; 407 stream << req0.blockhash; 408 WriteCompactSize(stream, req0.indexes.size()); 409 WriteCompactSize(stream, req0.indexes[0]); 410 WriteCompactSize(stream, req0.indexes[1]); 411 WriteCompactSize(stream, req0.indexes[2]); 412 413 BlockTransactionsRequest req1; 414 try { 415 stream >> req1; 416 // before patch: deserialize above succeeds and this check fails, demonstrating the overflow 417 BOOST_CHECK(req1.indexes[1] < req1.indexes[2]); 418 // this shouldn't be reachable before or after patch 419 BOOST_CHECK(0); 420 } catch(std::ios_base::failure &) { 421 // deserialize should fail 422 BOOST_CHECK(true); // Needed to suppress "Test case [...] did not check any assertions" 423 } 424 } 425 426 BOOST_AUTO_TEST_SUITE_END()