Select orphan transaction uniformly for eviction by sipa · Pull Request #14626 · bitcoin/bitcoin

sipa · 2018-11-01T00:40:19Z

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

DrahtBot · 2018-11-01T03:03:42Z

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

Conflicts

No conflicts as of last run.

gmaxwell · 2018-11-03T21:20:10Z

Concept ACK.

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

sipa · 2018-12-13T21:46:54Z

Rebased.

Empact · 2019-01-31T17:14:26Z

    };
    std::map<COutPoint, std::set<std::map<uint256, COrphanTx>::iterator, IteratorComparator>> mapOrphanTransactionsByPrev GUARDED_BY(g_cs_orphans);

+    std::vector<std::map<uint256, COrphanTx>::iterator> g_orphan_list GUARDED_BY(g_cs_orphans); //! For random eviction


//!< for in-line doxygen

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 · 2019-01-31T18:31:30Z

utACK 7257353

sipa · 2019-02-02T21:59:12Z

@sdaftuar @naumenkogs Feel like reviewing this?

naumenkogs

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.

naumenkogs · 2019-02-03T01:49:40Z

    };
    std::map<COutPoint, std::set<std::map<uint256, COrphanTx>::iterator, IteratorComparator>> mapOrphanTransactionsByPrev GUARDED_BY(g_cs_orphans);

+    std::vector<std::map<uint256, COrphanTx>::iterator> g_orphan_list GUARDED_BY(g_cs_orphans); //! For random eviction


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

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

sdaftuar · 2019-02-04T18:30:00Z

utACK 7257353

gmaxwell · 2019-02-14T20:57:38Z

ACK

7257353 Select orphan transaction uniformly for eviction (Pieter Wuille) Pull request description: The previous code was biased towards evicting transactions whose txid has a larger gap (lexicographically) with the previous txid in the orphan pool. Tree-SHA512: e35f700aea5ed79d1bc57f64bffcb623424b40156fd0a12f05f74f981a8aa4175d5c18d042989243f7559242bdf1d6d720bcf588d28f43d74a798a4843f09c70

maflcko · 2019-02-14T21:15:31Z

+        // Unless we're deleting the last entry in g_orphan_list, move the last
+        // entry to the position we're deleting.
+        auto it_last = g_orphan_list.back();
+        g_orphan_list[old_pos] = it_last;


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

maflcko · 2019-02-14T21:16:00Z

ACK

Summary: 7257353b93 Select orphan transaction uniformly for eviction (Pieter Wuille) Pull request description: The previous code was biased towards evicting transactions whose txid has a larger gap (lexicographically) with the previous txid in the orphan pool. Tree-SHA512: e35f700aea5ed79d1bc57f64bffcb623424b40156fd0a12f05f74f981a8aa4175d5c18d042989243f7559242bdf1d6d720bcf588d28f43d74a798a4843f09c70 Backport of Core [[bitcoin/bitcoin#14626 | PR14626]] Test Plan: ninja ninja check-all Reviewers: O1 Bitcoin ABC, #bitcoin_abc, Fabien Reviewed By: O1 Bitcoin ABC, #bitcoin_abc, Fabien Differential Revision: https://reviews.bitcoinabc.org/D6488

hebasto · 2020-06-24T15:43:36Z

+        size_t randompos = rng.randrange(g_orphan_list.size());
+        EraseOrphanTx(g_orphan_list[randompos]->first);


@sipa

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

Suggested change

size_t randompos = rng.randrange(g_orphan_list.size());

EraseOrphanTx(g_orphan_list[randompos]->first);

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

Or did I miss something?

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

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

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

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

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.

7257353 Select orphan transaction uniformly for eviction (Pieter Wuille) Pull request description: The previous code was biased towards evicting transactions whose txid has a larger gap (lexicographically) with the previous txid in the orphan pool. Tree-SHA512: e35f700aea5ed79d1bc57f64bffcb623424b40156fd0a12f05f74f981a8aa4175d5c18d042989243f7559242bdf1d6d720bcf588d28f43d74a798a4843f09c70 Signed-off-by: pasta <pasta@dashboost.org>

fanquake added the P2P label Nov 1, 2018

DrahtBot mentioned this pull request Nov 1, 2018

Some simple improvements to the RNG code #14624

Merged

laanwj reviewed Nov 5, 2018

View reviewed changes

Comment thread src/net_processing.cpp Outdated

promag reviewed Nov 20, 2018

View reviewed changes

Comment thread src/net_processing.cpp Outdated

Comment thread src/net_processing.cpp Outdated

DrahtBot added the Needs rebase label Dec 13, 2018

Select orphan transaction uniformly for eviction

7257353

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

sipa force-pushed the 201810_uniform_orphan_eviction branch from 64e1dbb to 7257353 Compare December 13, 2018 21:46

DrahtBot removed the Needs rebase label Dec 13, 2018

sipa mentioned this pull request Jan 7, 2019

Orphan eviction is not actually random #15121

Closed

Empact reviewed Jan 31, 2019

View reviewed changes

naumenkogs reviewed Feb 3, 2019

View reviewed changes

maflcko merged commit 7257353 into bitcoin:master Feb 14, 2019

maflcko reviewed Feb 14, 2019

View reviewed changes

hebasto reviewed Jun 24, 2020

View reviewed changes

hebasto mentioned this pull request Jun 24, 2020

refactor: Drop g_orphan_list global #19374

Closed

furszy mentioned this pull request Apr 12, 2021

[net_processing] Improve/upgrade orphan transactions handling PIVX-Project/PIVX#2301

Merged

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

		size_t randompos = rng.randrange(g_orphan_list.size());
		EraseOrphanTx(g_orphan_list[randompos]->first);

	size_t randompos = rng.randrange(g_orphan_list.size());
	EraseOrphanTx(g_orphan_list[randompos]->first);
	EraseOrphanTx(mapOrphanTransactions.begin()->first);

Uh oh!

Conversation

sipa commented Nov 1, 2018

Uh oh!

DrahtBot commented Nov 1, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

gmaxwell commented Nov 3, 2018

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sipa commented Dec 13, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Empact commented Jan 31, 2019

Uh oh!

sipa commented Feb 2, 2019

Uh oh!

naumenkogs left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sdaftuar commented Feb 4, 2019

Uh oh!

gmaxwell commented Feb 14, 2019

Uh oh!

Choose a reason for hiding this comment

Uh oh!

maflcko commented Feb 14, 2019

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

11 participants

DrahtBot commented Nov 1, 2018 •

edited

Loading