Select orphan transaction uniformly for eviction #14626

sipa commented at 12:40 AM on November 1, 2018: member

The previous code was biased towards evicting transactions whose txid has a larger gap (lexicographically) with the previous txid in the orphan pool.

fanquake added the label P2P on Nov 1, 2018

DrahtBot commented at 3:03 AM on November 1, 2018: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

No conflicts as of last run.

DrahtBot cross-referenced this on Nov 1, 2018 from issue Some simple improvements to the RNG code by sipa

gmaxwell commented at 9:20 PM on November 3, 2018: contributor

Concept ACK.

in src/net_processing.cpp:801 in 64e1dbb554 outdated

 797 | @@ -782,11 +798,8 @@ unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans)
 798 |      while (mapOrphanTransactions.size() > nMaxOrphans)
 799 |      {
 800 |          // Evict a random orphan:
 801 | -        uint256 randomhash = GetRandHash();
 802 | -        std::map<uint256, COrphanTx>::iterator it = mapOrphanTransactions.lower_bound(randomhash);
 803 | -        if (it == mapOrphanTransactions.end())
 804 | -            it = mapOrphanTransactions.begin();
 805 | -        EraseOrphanTx(it->first);
 806 | +        size_t randompos = GetRandInt(g_orphan_list.size());

laanwj commented at 3:38 PM on November 5, 2018:

the argument to GetRandInt is 'max', isn't this an off-by-one error?

sipa commented at 12:27 AM on November 20, 2018:

No, its argument is named confusingly. The last line of GetRandInt is return (nRand % nMax), so it always returns a value less than nMax.

in src/net_processing.cpp:746 in 64e1dbb554 outdated

 741 | +    size_t old_pos = it->second.list_pos;
 742 | +    assert(g_orphan_list[old_pos] == it);
 743 | +    if (old_pos + 1 != g_orphan_list.size()) {
 744 | +        // Unless we're deleting the last entry in g_orphan_list, move the last
 745 | +        // entry to the position we're deleting.
 746 | +        auto it_last = g_orphan_list.back();

promag commented at 12:42 AM on November 20, 2018:

Use http://www.cplusplus.com/reference/algorithm/iter_swap/?

sipa commented at 2:32 AM on November 20, 2018:

How?

in src/net_processing.cpp:174 in 64e1dbb554 outdated

 170 | @@ -170,6 +171,8 @@ namespace {
 171 |      };
 172 |      std::map<COutPoint, std::set<std::map<uint256, COrphanTx>::iterator, IteratorComparator>> mapOrphanTransactionsByPrev GUARDED_BY(g_cs_orphans);
 173 |  
 174 | +    std::vector<std::map<uint256, COrphanTx>::iterator> g_orphan_list; //! For random eviction

promag commented at 12:44 AM on November 20, 2018:

Guarded by g_cs_orphans?

sipa commented at 9:46 PM on December 13, 2018:

Done.

DrahtBot added the label Needs rebase on Dec 13, 2018

Select orphan transaction uniformly for eviction

The previous code was biased towards evicting transactions whose txid has
a larger gap (lexicographically) with the previous txid in the orphan pool.

7257353b93

sipa force-pushed on Dec 13, 2018

sipa commented at 9:46 PM on December 13, 2018: member

Rebased.

DrahtBot removed the label Needs rebase on Dec 13, 2018

sipa cross-referenced this on Jan 7, 2019 from issue Orphan eviction is not actually random by sr-gi

in src/net_processing.cpp:174 in 7257353b93

 170 | @@ -170,6 +171,8 @@ namespace {
 171 |      };
 172 |      std::map<COutPoint, std::set<std::map<uint256, COrphanTx>::iterator, IteratorComparator>> mapOrphanTransactionsByPrev GUARDED_BY(g_cs_orphans);
 173 |  
 174 | +    std::vector<std::map<uint256, COrphanTx>::iterator> g_orphan_list GUARDED_BY(g_cs_orphans); //! For random eviction

Empact commented at 5:14 PM on January 31, 2019:

//!< for in-line doxygen

naumenkogs commented at 1:49 AM on February 3, 2019:

Is there any benefit of having COrphanTx inside, why not just using a hash?

naumenkogs commented at 3:04 AM on February 3, 2019:

Right, I guess it's cleaner this way. Feel free to resolve this one.

sipa commented at 4:59 AM on February 3, 2019:

It's not storing a COrphanTx inside. It's storing a list of iterators to entries in a map from uint256 to COrphanTx.

Such iterators are only as large as one pointer.

Empact commented at 6:31 PM on January 31, 2019: member

utACK https://github.com/bitcoin/bitcoin/pull/14626/commits/7257353b93e9f45e67071b0b86a0313e7a70aaaa

sipa commented at 9:59 PM on February 2, 2019: member

@sdaftuar @naumenkogs Feel like reviewing this?

naumenkogs commented at 1:15 AM on February 3, 2019: member

Concept ACK, will look closer.

First of all, we either should remove this comment or do what it says? struct COrphanTx { // When modifying, adapt the copy of this definition in tests/DoS_tests.

sdaftuar commented at 6:30 PM on February 4, 2019: member

utACK 7257353b93e9f45e67071b0b86a0313e7a70aaaa

gmaxwell commented at 8:57 PM on February 14, 2019: contributor

ACK

MarcoFalke merged this on Feb 14, 2019

MarcoFalke closed this on Feb 14, 2019

MarcoFalke referenced this in commit cd8ca8be31 on Feb 14, 2019

in src/net_processing.cpp:747 in 7257353b93

 742 | +    assert(g_orphan_list[old_pos] == it);
 743 | +    if (old_pos + 1 != g_orphan_list.size()) {
 744 | +        // Unless we're deleting the last entry in g_orphan_list, move the last
 745 | +        // entry to the position we're deleting.
 746 | +        auto it_last = g_orphan_list.back();
 747 | +        g_orphan_list[old_pos] = it_last;

MarcoFalke commented at 9:15 PM on February 14, 2019:

style-nit: Looks odd to assign an iterator. (The code is still correct, since back() returns a reference, but the naming might be wrong)

MarcoFalke commented at 9:16 PM on February 14, 2019: member

ACK

deadalnix referenced this in commit adeae3daa5 on Jun 10, 2020

in src/net_processing.cpp:803 in 7257353b93

 803 | -        std::map<uint256, COrphanTx>::iterator it = mapOrphanTransactions.lower_bound(randomhash);
 804 | -        if (it == mapOrphanTransactions.end())
 805 | -            it = mapOrphanTransactions.begin();
 806 | -        EraseOrphanTx(it->first);
 807 | +        size_t randompos = rng.randrange(g_orphan_list.size());
 808 | +        EraseOrphanTx(g_orphan_list[randompos]->first);

hebasto commented at 3:43 PM on June 24, 2020:

@sipa

As the mapOrphanTransactions items are sorted by hash, the first item is random with a negligible bias:

        EraseOrphanTx(mapOrphanTransactions.begin()->first);

Or did I miss something?

sipa commented at 4:16 PM on June 24, 2020:

That would always evict lower txids before higher txids. Not exactly negligible...

hebasto commented at 4:19 PM on June 24, 2020:

Is this applicable https://crypto.stackexchange.com/questions/12822/are-the-sha-family-hash-outputs-practically-random ?

hebasto commented at 4:23 PM on June 24, 2020:

That would always evict lower txids before higher txids. Not exactly negligible...

I do not mean "random txid", rather "random transaction".

sipa commented at 4:23 PM on June 24, 2020:

No. That would apply if the transactions were secret, but since an attacker may know the transactions, they also know the txids. The hashing applied is not relevant.

If mapOrphanTransactions was say an unordered_map, and was using salted hash for its internal hashing (to convert txids to bucket positions) like is used in some places, then this would perhaps not be an issue.

hebasto cross-referenced this on Jun 24, 2020 from issue refactor: Drop g_orphan_list global by hebasto

furszy cross-referenced this on Apr 12, 2021 from issue [net_processing] Improve/upgrade orphan transactions handling by furszy

PastaPastaPasta referenced this in commit 198880093d on Jul 18, 2021

PastaPastaPasta referenced this in commit 378ef2b8c6 on Jul 18, 2021

PastaPastaPasta referenced this in commit 4a256bfa03 on Jul 19, 2021

PastaPastaPasta referenced this in commit c1b6e52206 on Jul 19, 2021

PastaPastaPasta referenced this in commit 9fd70ab11b on Jul 20, 2021

PastaPastaPasta referenced this in commit efd82152e6 on Jul 20, 2021

bitcoin locked this on Feb 15, 2022