Inside Bitcoin

251        // were just evicted in the previous block additions.
252        for (unsigned int i{num_from_peer1}; i < num_from_peer1 + 10; ++i) {
253            // Tx has already been sent by peer_dosy
254            BOOST_CHECK(orphanage->HaveTxFromPeer(txns.at(i)->GetWitnessHash(), peer_dosy));
255            orphanage->AddTx(txns.at(i), peer2);
256
257            // peer_dosy is still the only one getting evicted
258            BOOST_CHECK_EQUAL(orphanage->AnnouncementsFromPeer(peer_dosy), max_announcements - i - 1);
259            BOOST_CHECK_EQUAL(orphanage->AnnouncementsFromPeer(peer1), num_from_peer1);
260            BOOST_CHECK_EQUAL(orphanage->AnnouncementsFromPeer(peer2), i + 1 - num_from_peer1);
261
262            // Evictions are FIFO within a peer, so the ith transaction sent by peer_dosy is the one that was evicted.
263            BOOST_CHECK(!orphanage->HaveTxFromPeer(txns.at(i)->GetWitnessHash(), peer_dosy));
264            BOOST_CHECK(orphanage->HaveTx(txns.at(i)->GetWitnessHash()));
265        }
266
267        // With 6 peers, each can add 10, and still only peer_dosy's orphans are evicted.
268        const unsigned int max_per_peer{max_announcements / 6};
269        const unsigned int num_announcements{orphanage->CountAnnouncements()};
270        for (NodeId peer{3}; peer < 6; ++peer) {
271            for (unsigned int i{0}; i < max_per_peer; ++i) {
272                // Each addition causes 1 eviction.
273                orphanage->AddTx(txns.at(peer * max_per_peer + i), peer);
274                BOOST_CHECK_EQUAL(orphanage->CountAnnouncements(), num_announcements);
275            }
276        }
277        for (NodeId peer{0}; peer < 6; ++peer) {
278            BOOST_CHECK_EQUAL(orphanage->AnnouncementsFromPeer(peer), max_per_peer);
279        }
280        orphanage->SanityCheck();
281    }
282
283    // Limits change as more peers are added.
284    {
285        auto orphanage{node::MakeTxOrphanage()};
286        // These stay the same regardless of number of peers
287        BOOST_CHECK_EQUAL(orphanage->MaxGlobalLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
288        BOOST_CHECK_EQUAL(orphanage->ReservedPeerUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
289
290        // These change with number of peers
291        BOOST_CHECK_EQUAL(orphanage->MaxGlobalUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
292        BOOST_CHECK_EQUAL(orphanage->MaxPeerLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
293
294        // Number of peers = 1
295        orphanage->AddTx(txns.at(0), 0);
296        BOOST_CHECK_EQUAL(orphanage->MaxGlobalLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
297        BOOST_CHECK_EQUAL(orphanage->ReservedPeerUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
298        BOOST_CHECK_EQUAL(orphanage->MaxGlobalUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
299        BOOST_CHECK_EQUAL(orphanage->MaxPeerLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
300
301        // Number of peers = 2
302        orphanage->AddTx(txns.at(1), 1);
303        BOOST_CHECK_EQUAL(orphanage->MaxGlobalLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
304        BOOST_CHECK_EQUAL(orphanage->ReservedPeerUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
305        BOOST_CHECK_EQUAL(orphanage->MaxGlobalUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER * 2);
306        BOOST_CHECK_EQUAL(orphanage->MaxPeerLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE / 2);
307
308        // Number of peers = 3
309        orphanage->AddTx(txns.at(2), 2);
310        BOOST_CHECK_EQUAL(orphanage->MaxGlobalLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
311        BOOST_CHECK_EQUAL(orphanage->ReservedPeerUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
312        BOOST_CHECK_EQUAL(orphanage->MaxGlobalUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER * 3);
313        BOOST_CHECK_EQUAL(orphanage->MaxPeerLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE / 3);
314
315        // Number of peers didn't change.
316        orphanage->AddTx(txns.at(3), 2);
317        BOOST_CHECK_EQUAL(orphanage->MaxGlobalLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
318        BOOST_CHECK_EQUAL(orphanage->ReservedPeerUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
319        BOOST_CHECK_EQUAL(orphanage->MaxGlobalUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER * 3);
320        BOOST_CHECK_EQUAL(orphanage->MaxPeerLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE / 3);
321
322        // Once a peer has no orphans, it is not considered in the limits.
323        // Number of peers = 2
324        orphanage->EraseForPeer(2);
325        BOOST_CHECK_EQUAL(orphanage->MaxGlobalLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
326        BOOST_CHECK_EQUAL(orphanage->ReservedPeerUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
327        BOOST_CHECK_EQUAL(orphanage->MaxGlobalUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER * 2);
328        BOOST_CHECK_EQUAL(orphanage->MaxPeerLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE / 2);
329
330        // Number of peers = 1
331        orphanage->EraseTx(txns.at(0)->GetWitnessHash());
332        BOOST_CHECK_EQUAL(orphanage->MaxGlobalLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
333        BOOST_CHECK_EQUAL(orphanage->ReservedPeerUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
334        BOOST_CHECK_EQUAL(orphanage->MaxGlobalUsage(), node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER);
335        BOOST_CHECK_EQUAL(orphanage->MaxPeerLatencyScore(), node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE);
336
337        orphanage->SanityCheck();
338    }
339
340    // Test eviction of multiple transactions at a time
341    {
342        // Create a large transaction that is 10 times larger than the normal size transaction.
343        CMutableTransaction tx_large;
344        tx_large.vin.resize(1);
345        BulkTransaction(tx_large, 10 * TX_SIZE);
346        auto ptx_large = MakeTransactionRef(tx_large);
347
348        const auto large_tx_size = GetTransactionWeight(*ptx_large);
349        BOOST_CHECK(large_tx_size > 10 * TX_SIZE);
350        BOOST_CHECK(large_tx_size < 11 * TX_SIZE);
351
352        auto orphanage = node::MakeTxOrphanage(20, large_tx_size);
353        // One peer sends 10 normal size transactions. The other peer sends 10 normal transactions and 1 very large one
354        NodeId peer_normal{0};
355        NodeId peer_large{1};
356        for (unsigned int i = 0; i < 20; i++) {
357            orphanage->AddTx(txns.at(i), i < 10 ? peer_normal : peer_large);
358        }
359        BOOST_CHECK(orphanage->TotalLatencyScore() <= orphanage->MaxGlobalLatencyScore());
360        BOOST_CHECK(orphanage->TotalOrphanUsage() <= orphanage->MaxGlobalUsage());
361
362        // Add the large transaction. This should cause evictions of all the previous 10 transactions from that peer.
363        orphanage->AddTx(ptx_large, peer_large);
364
365        // peer_normal should still have 10 transactions, and peer_large should have 1.
366        BOOST_CHECK_EQUAL(orphanage->AnnouncementsFromPeer(peer_normal), 10);
367        BOOST_CHECK_EQUAL(orphanage->AnnouncementsFromPeer(peer_large), 1);
368        BOOST_CHECK(orphanage->HaveTxFromPeer(ptx_large->GetWitnessHash(), peer_large));
369        BOOST_CHECK_EQUAL(orphanage->CountAnnouncements(), 11);
370
371        orphanage->SanityCheck();
372    }
373
374    // Test that latency score includes number of inputs.
375    {
376        auto orphanage = node::MakeTxOrphanage();
377
378        // Add 10 transactions with 9 inputs each.
379        std::vector<COutPoint> outpoints_9;
380        for (unsigned int j{0}; j < 9; ++j) {
381            outpoints_9.emplace_back(Txid::FromUint256(m_rng.rand256()), j);
382        }
383        for (unsigned int i{0}; i < 10; ++i) {
384            auto ptx = MakeTransactionSpending(outpoints_9, m_rng);
385            orphanage->AddTx(ptx, 0);
386        }
387        BOOST_CHECK_EQUAL(orphanage->CountAnnouncements(), 10);
388        BOOST_CHECK_EQUAL(orphanage->TotalLatencyScore(), 10);
389
390        // Add 10 transactions with 50 inputs each.
391        std::vector<COutPoint> outpoints_50;
392        for (unsigned int j{0}; j < 50; ++j) {
393            outpoints_50.emplace_back(Txid::FromUint256(m_rng.rand256()), j);
394        }
395
396        for (unsigned int i{0}; i < 10; ++i) {
397            CMutableTransaction tx;
398            std::shuffle(outpoints_50.begin(), outpoints_50.end(), m_rng);
399            auto ptx = MakeTransactionSpending(outpoints_50, m_rng);
400            BOOST_CHECK(orphanage->AddTx(ptx, 0));
401            if (i < 5) BOOST_CHECK(!orphanage->AddTx(ptx, 1));
402        }
403        // 10 of the 9-input transactions + 10 of the 50-input transactions + 5 more announcements of the 50-input transactions
404        BOOST_CHECK_EQUAL(orphanage->CountAnnouncements(), 25);
405        // Base of 25 announcements, plus 10 * 5 for the 50-input transactions (counted just once)
406        BOOST_CHECK_EQUAL(orphanage->TotalLatencyScore(), 25 + 50);
407
408        // Peer 0 sent all 20 transactions
409        BOOST_CHECK_EQUAL(orphanage->AnnouncementsFromPeer(0), 20);
410        BOOST_CHECK_EQUAL(orphanage->LatencyScoreFromPeer(0), 20 + 10 * 5);
411
412        // Peer 1 sent 5 of the 10 transactions with many inputs
413        BOOST_CHECK_EQUAL(orphanage->AnnouncementsFromPeer(1), 5);
414        BOOST_CHECK_EQUAL(orphanage->LatencyScoreFromPeer(1), 5 + 5 * 5);
415
416        orphanage->SanityCheck();
417    }
418}
419BOOST_AUTO_TEST_CASE(DoS_mapOrphans)
420{
421    // This test had non-deterministic coverage due to
422    // randomly selected seeds.
423    // This seed is chosen so that all branches of the function
424    // ecdsa_signature_parse_der_lax are executed during this test.
425    // Specifically branches that run only when an ECDSA
426    // signature's R and S values have leading zeros.
427    m_rng.Reseed(uint256{33});
428
429    std::unique_ptr<node::TxOrphanage> orphanage{node::MakeTxOrphanage()};
430    CKey key;
431    MakeNewKeyWithFastRandomContext(key, m_rng);
432    FillableSigningProvider keystore;
433    BOOST_CHECK(keystore.AddKey(key));
434
435    FakeNodeClock clock{};
436
437    std::vector<CTransactionRef> orphans_added;
438
439    // 50 orphan transactions:
440    for (int i = 0; i < 50; i++)
441    {
442        CMutableTransaction tx;
443        tx.vin.resize(1);
444        tx.vin[0].prevout.n = 0;
445        tx.vin[0].prevout.hash = Txid::FromUint256(m_rng.rand256());
446        tx.vin[0].scriptSig << OP_1;
447        tx.vout.resize(1);
448        tx.vout[0].nValue = i*CENT;
449        tx.vout[0].scriptPubKey = GetScriptForDestination(PKHash(key.GetPubKey()));
450
451        auto ptx = MakeTransactionRef(tx);
452        orphanage->AddTx(ptx, i);
453        orphans_added.emplace_back(ptx);
454    }
455
456    // ... and 50 that depend on other orphans:
457    for (int i = 0; i < 50; i++)
458    {
459        const auto& txPrev = orphans_added[m_rng.randrange(orphans_added.size())];
460
461        CMutableTransaction tx;
462        tx.vin.resize(1);
463        tx.vin[0].prevout.n = 0;
464        tx.vin[0].prevout.hash = txPrev->GetHash();
465        tx.vout.resize(1);
466        tx.vout[0].nValue = i*CENT;
467        tx.vout[0].scriptPubKey = GetScriptForDestination(PKHash(key.GetPubKey()));
468        SignatureData empty;
469        BOOST_CHECK(SignSignature(keystore, *txPrev, tx, 0, SIGHASH_ALL, empty));
470
471        auto ptx = MakeTransactionRef(tx);
472        orphanage->AddTx(ptx, i);
473        orphans_added.emplace_back(ptx);
474    }
475
476    // This really-big orphan should be ignored:
477    for (int i = 0; i < 10; i++)
478    {
479        const auto& txPrev = orphans_added[m_rng.randrange(orphans_added.size())];
480
481        CMutableTransaction tx;
482        tx.vout.resize(1);
483        tx.vout[0].nValue = 1*CENT;
484        tx.vout[0].scriptPubKey = GetScriptForDestination(PKHash(key.GetPubKey()));
485        tx.vin.resize(2777);
486        for (unsigned int j = 0; j < tx.vin.size(); j++)
487        {
488            tx.vin[j].prevout.n = j;
489            tx.vin[j].prevout.hash = txPrev->GetHash();
490        }
491        SignatureData empty;
492        BOOST_CHECK(SignSignature(keystore, *txPrev, tx, 0, SIGHASH_ALL, empty));
493        // Reuse same signature for other inputs
494        // (they don't have to be valid for this test)
495        for (unsigned int j = 1; j < tx.vin.size(); j++)
496            tx.vin[j].scriptSig = tx.vin[0].scriptSig;
497
498        BOOST_CHECK(!orphanage->AddTx(MakeTransactionRef(tx), i));
499    }
500