p2p: Fill reconciliation sets (Erlay) attempt 2 #30116

In “p2p: Functions to add/remove wtxids to tx reconciliation sets” 2e29e9beeebcadfc7afc56a28791456d40551bed: I think MAX_SET_SIZE could be in txreconciliation.h then we can use it in the tests.

 0-/**
 1- * Maximum number of wtxids stored in a peer local set, bounded to protect the memory use of
 2- * reconciliation sets and short ids mappings, and CPU used for sketch computation.
 3- */
 4-constexpr size_t MAX_SET_SIZE = 3000;
 5 
 6 /**
 7  * Maximum number of transactions for which we store assigned fanout targets.
 8diff --git a/src/node/txreconciliation.h b/src/node/txreconciliation.h
 9index c2cdf9875f..648b6369c0 100644
10--- a/src/node/txreconciliation.h
11+++ b/src/node/txreconciliation.h
12@@ -14,6 +14,12 @@
13 /** Supported transaction reconciliation protocol version */
14 static constexpr uint32_t TXRECONCILIATION_VERSION{1};
15 
16+/**
17+ * Maximum number of wtxids stored in a peer local set, bounded to protect the memory use of
18+ * reconciliation sets and short ids mappings, and CPU used for sketch computation.
19+ */
20+constexpr size_t MAX_SET_SIZE = 3000;
21+
22 enum class ReconciliationRegisterResult {
23     NOT_FOUND,
24     SUCCESS,
25diff --git a/src/test/txreconciliation_tests.cpp b/src/test/txreconciliation_tests.cpp
26index a0071e4388..8befe0d36e 100644
27--- a/src/test/txreconciliation_tests.cpp
28+++ b/src/test/txreconciliation_tests.cpp
29@@ -115,7 +115,7 @@ BOOST_AUTO_TEST_CASE(AddToSetTest)
30     BOOST_REQUIRE_EQUAL(tracker.RegisterPeer(peer_id1, true, 1, 1), ReconciliationRegisterResult::SUCCESS);
31     BOOST_CHECK(tracker.IsPeerRegistered(peer_id1));
32 
33-    for (size_t i = 0; i < 3000; ++i)
34+    for (size_t i = 0; i < MAX_SET_SIZE; ++i)
35         BOOST_REQUIRE(tracker.AddToSet(peer_id1, Wtxid::FromUint256(frc.rand256())));
36     BOOST_REQUIRE(!tracker.AddToSet(peer_id1, Wtxid::FromUint256(frc.rand256())));

Ended up taking this, since the limit will be kept in the end.

Thanks!

Notice this does not apply to all transactions though. The exception here applies to transactions that have some ancestors in the mempool. In that case, we need to be consistent with the way we share this set of transactions, otherwise, it could be the case that the parents are reconciled at time T and the children are fanout at T-n, potentially making the children orphan.

Under these conditions, we are checking how many peers have the ancestors in their reconciliation sets, and selecting a subset of the ones with fewer of them, so the amount of transactions to be fanout is the smallest possible.

We could. I left it as for simplicity, given this case should not be too frequent, so having a higher fanout under these conditions shouldn’t be too bad.

I’ll consider adding it if it does not make the code much harder to read, or if there is a clear counterargument in favor of it.

This function could easily return two numbers: how many of these peers are inbound and outbound. And then just pass this pair along to ShouldFanoutTo. Should be not that complex code. A cheap cost to preserve the efficiency model.

I might try if you don’t get to it earlier.

0for (int i = 1; i < inbound_peers; ++i) {
1        // create 4000 random wtxids so that FANOUT_TARGETS_PER_TX_CACHE_SIZE is breached
2        for (int j = 0; j < 4000; ++j) {
3            tracker.ShouldFanoutTo(Wtxid::FromUint256(frc.rand256()), i,
4                                   /*inbounds_fanout_tx_relay=*/0, /*outbounds_fanout_tx_relay=*/0);
5        }
6    }

increases coverage of the units tests to check the cache_size check in IsFanoutTarget .

Okay, see the last two commits here.

I also dropped the <0.001 check, it’s kinda pointless anyway…

The commit with the casting works, but the test one is actually not a good way of testing this; it would pass both with and without the change.

Turns out that passing a huge value to IsFanoutTarget would result in targets_size being 0, which results in the method returning false. I don’t think there is really a good way of testing this.

I’ll take the code commit but skip the addition to the test.

Interesting. So, for me, the first commit (with a new test) takes forever to execute.

More specifically, the execution hangs on best_peers.resize(targets_size);, with targets_size being a huge number.

I guess your system handles this gracefully instead?

A clear failure could be triggered by e.g. Assume(targets_size <= m_states.size());

50c19dd21f6e437cd8e3d9047a89d793d097c5e5

worth adding a comment on what would happen if there are 3 colliding transactions (probably fine but some text would be helpful) :)

Being this part of RelayTransaction, which processed transactions one at a time, and given that if a collision happens the existing transaction is removed from the set, there cannot be a three-way collision. If a third transaction that happens to have the same short id as the two previous ones is added to the set later, it would be added normally since there won’t be a transaction to collide with.

I could add a comment for three, but someone may then mention what happens if there are four 😅

I was looking for something like “As a general rule, we keep the transaction that appeared first”.

Currently, the AddToSet documentation seems outdated—it basically claims that the only way to fail is to reach a set limit.

How about the following replacement:

0    /**
1     * Step 1. Add a to-be-announced transaction to the local reconciliation set of the target peer.
2     * Returns false if the set is at capacity, or if the set contains a colliding transaction.
3     * Returns true if the transaction appears in the set (whether it was already there or just was added).
4     */

Apparently I was wrong.

0                // If the transaction fails because it collides with an existing one,
1                // we also remove and fanout the conflict and all its descendants.
2                // This is because our peer may have added the conflicting transaction
3                // to its set, in which reconciliation of these two would fail

Say A, B, C arrive.

• First A added to the set.
• then B doesn’t make it to the set, but also drops A from it.
• then C takes a place in the set.

That’s a good point. It may be the case that the selected peer has a parent -> child dependency but was not picked as one of the fanout_with_ancestors peers, the parent and the child may have ended up in different sets.

We should check the return of TryRemovingFromSet before adding it to vInv

say a descendant was never considered for reconciliation (somehow), but now is used to removefromset some other transaction (it collides with)

or maybe it was considered, but then was dropped in favor of something else (that’s not how we currently handle collisions, but that would be a hard assumption)

Collisions of this kind could happen in theory, but I don’t think they can be really gamed:

short ids are peer specific, they are generated using SipHashUint256 which are salted using m_k0 and m_k1. Therefore, while a collision of this kind is theoretically possible, an adversarial peer should not be able to exploit them

392facfce1be6d0395abecc2e049ff39635bd1a5

why do you think force relay should influence whether we reconcile or flood? The transaction is relayed in either case (the original meaning of force relay)

392facfce1be6d0395abecc2e049ff39635bd1a5

these kind of refactors we better apply where the code was introduced, in the older commits of this PR

392facfce1be6d0395abecc2e049ff39635bd1a5

you can technically feed it arbitrary transactions. I think the comment should say it, and then later say “we normally pass a list of parents to determine whether [… … …]”.

392facfce1be6d0395abecc2e049ff39635bd1a5

why not modifying the former commit that introduces this code?

392facfce1be6d0395abecc2e049ff39635bd1a5

what about the order of the parents here? Deserves a comment at least. With the current non-cluster mempool it might break something?

UPD:

Say the following happens: A -> B - > C

• A arrives, we add it to some sets.
• B arrives, triggers a flood from half the sets, but the other half has A+B now.
• C arrives, triggers a flood from A+B. But then, can we guarantee A is flooded before B?

UPD2: topo sort should work. Have a common place where the INV vector is handled?

another question: say a child arrives a few minutes after a parent (parent still in the mempool, but it’s been announced to peers a while ago). Why bother with this inv? Perhaps we should do it only if TryRemovingFromSet actually have removed it?

(same applies to handling a collision below)

i know m_tx_inventory_known_filter will probably catch it, but i think it’s better to do it here.

392facfce1be6d0395abecc2e049ff39635bd1a5

where do you do this (consider in-mempool descendants and decide to fanout everything)? I only see you do it for the collision

I don’t think this comment is accurate since this can never be the case. A transaction considered for relay cannot have in-mempool descendants by definition, since they would have been orphans at the time of considering them.

I cannot recall if this is a re-word of the previous approach, which tried to consider descendants, or I tried to refer to the collisions and it didn’t make much sense.

I’ll remove the comment

20772c077832592265bd6a2876aa6b4cb7dbde7d

with this code, and especially the 5/2 trickle delay (very long), previous performance measurements become outdated.

My idea was to delay the responses. And by this time, the hope was flooding does enough job so that scanning the sets through many connections does not work.

Also, adding to a set already happens on a trickle… so that’s another level of protection

Just talked to Bruno a bit more about this.

I think it’s fair to compare this delayed set mechanism to what i have in the code there. I like my solution more because:

• its synced across peers (handles better spying across multiple conns i think?)
• simpler code
• more flexibility (doesn’t have to be same trickling as adding to sets or fanouting)

Interested in what other people think though.

I think the current approach mimics what you were doing with your old one. I haven’t picked up the trickle reduction commit not the delayed response, but I was planning to in the next PR.

Your approach used to add transactions to the reconciliation set during INV building, which happens on trickle intervals. So data was added to to_be_announced (delayed) on RelayTransaction and then made available on trickle. The current approach adds data to the delayed set on RelayTransaction and makes it available on trickle too.

So I don’t think the previous performance measurements become outdated, building the whole Erlay PR on this should yield similar results.

I agree now, it’s equivalent. Still wrapping my head around RelayTransaction refactoring :)

A difference could be in handling dependencies: during the trickle window after the first transaction arrives.

Say, a parent arrives, and then a child arrives in a second. In my approach we may notice the child when handling (announcement-wise) the parent (because handling the parent is postponed via trickle). In your approach, you handle the parent independently.

Is there any use of knowing about the child while handling (announcement-wise) the parent? I don’t think so. You probably could save some efforts of adding the parent to reconset, and then removing it, but that should be cheap anyway.

(the child-before-parent case is entirely different, as the child-to-arrive-early doesn’t normally hit the announcement step while in orphanage)

Found another relevant thing! (here)

009:42:53<@gmaxwell> Existing relay logic checks that transactions are still in the mempool before relaying them. I think the issue there would go away if instead of keeping around some erlay datastructure you just keep growing the queue of the peers transactions to relay until its time to reconcile, enh?  then the existing logic to check if things are still in the mempool is sufficient.

“Existing” refers to the legacy code in my branch.

https://github.com/bitcoin/bitcoin/commit/d2f260507279b1edd6c0f55d02c7ae2e598b3585

nit: in three places in this commit /* Continued */ should be dropped, it’s no longer necessary (been a linter thing)

873e8dd60b93f740330e9b0fbae4b3200204653a

nit: cur_peer->m_is_inbound ? ++inbounds_fanout_tx_relay : ++outbounds_fanout_tx_relay

4234f5ebe133b949080aaa56da8cbdd18b650ff2

Originally, the code forced me to make this call for every peer, that’s why i needed it to be deterministic. It’s not the case anymore. Do we still need determinism then?

This could be ReattemptInitialBroadcast, BroadcastTransaction (rpc/wallet), ProcessValidTx, or earlier upon handling NetMsgType::TX.

I think it’s odd we have two calls to RelayTransaction in the two latter cases. I’d rather change this code, e.g. pass already_relayed (duplicating force) to RelayTransaction. Perhaps too much for this PR and we should do it elsewhere (especially now that the package stuff happens in-between). I understand why it was ok when RelayTransaction was simple.

And while we’re stuck with these two calls, let’s say we drop the determinism.

Why RelayTransaction doesn’t look at m_tx_inventory_to_send very early (and maybe m_tx_inventory_known_filter too)? That would catch the transactions we already set for flooding, and just pass on them.

Now, the transactions in the sets. If we add them to the set again, nothing is done. If we try to flood them by a different choice, nothing is done still because we hit m_tx_inventory_to_send already having it.

Thus, for now, i think we should repeat the m_tx_inventory_to_send check above, rather than having the determinism. It kinda makes sense anyway, no?

Why RelayTransaction doesn’t look at m_tx_inventory_to_send very early (and maybe m_tx_inventory_known_filter too)? That would catch the transactions we already set for flooding, and just pass on them.

I don’t think this really works(?).

Imagine we call this once, and peer p (who has ForceRelay` permissions) is selected for reconciliation using a non-deterministic approach.

Now, the transaction is sent again by p shortly after, and now he is selected for flooding instead. The filter won’t catch this, and the transaction would end up in both sets.

This makes me recall that even though the process of selecting peers is deterministic at the moment, it is dependent on our peer list. Calling this twice with a different set of peers can result in a different ordering, so maybe we should not assume that transactions can be freely added to any of the two sets, and we should make sure that the opposite set does not contain the transaction before adding it to our desired one?

There is no need to cast it to double anymore.

What we should do is something like

0        size_t outbounds_target_size = 0;
1        if (OUTBOUND_FANOUT_DESTINATIONS > outbounds_fanout_tx_relay) outbounds_target_size = OUTBOUND_FANOUT_DESTINATIONS - outbounds_fanout_tx_relay;

Perhaps there is a less ugly way to do this. But casting to double seems worse.

The following test would break the code if we forget the double cast (discussion here). I suggest adding it to the tests.

0        std::tie(in_fanout_targets, out_fanout_targets) = tracker.GetFanoutTargets(Wtxid::FromUint256(frc.rand256()), /*inbounds_fanout_tx_relay=*/0, /*outbounds_fanout_tx_relay=*/100);
1        BOOST_CHECK(!tracker.ShouldFanoutTo(peer_id0, in_fanout_targets, out_fanout_targets));

4234f5ebe133b949080aaa56da8cbdd18b650ff2

We can just merge the two vectors, no? There is no use for this separation.

Nit

0        const size_t removed = m_local_set.erase(wtxid) + m_delayed_local_set.erase(wtxid);
1        // Data must be in one of the sets at most
2        Assume(removed <= 1);
3        return removed == 1;

Not too sure about the return removed == 1

The assume is there to make sure that if the code happens to be wrong, it is catched on testing. In the current approach, if the code moving data from delayed_set to m_local_set was broken somehow, this method will return that data was actually removed. If were to return removed == 1 in the aforementioned case, it would return false, and the caller’s logic may break.

I don’t think any of these cases is likely to happen given the assume will catch it before getting merged, but the proposed change makes me anxious.

PS: I agree on doing the variable renaming if you feel that makes the code more readable though

I thought size_t 0 will be cast to bool false on return, and just suggested the exact same behavior (1==true, 0==false) but without forcing the reader to think about casting and cause this exact confusion between us. Am i wrong?

Ahhh, so you saying 2==true is also important? Then I’ll be fine with explicit return removed >= 1, and comment that 2 should not normally happen.

2==true would mean that we had the transaction in both places, which should never happen (I’d mean that a transaction is both ready and delayed at the same time).

If that were to happen in production for whatever reason, this would return false with the suggested changes, which may break something?

Probably a taste thing. I think auto should be used only when it’s obvious what type it is.

Here there are two non-obvious occasions:

• auto x = bool + bool resulting in x=2.
• casting 2 to bool for the result.

I won’t insist but i think verbose types are better here. Feel free to close.

fd7c35a22669d440afe182a153bed28fd326b51f

Often, there will be no parents (e.g., a parent is in the mempool but has already been flooded/reconciled). In that case, it would be nice to give a random order. And then comment it please.

(currently it’s ordered by m_states i think).

In that case, no transaction would be moved from the reconciliation set to invs_to_send, given no transaction would be removed. Therefore, the order wouldn’t matter:

0auto it = std::find(fanout_with_ancestors.begin(), fanout_with_ancestors.end(), peer_id);
1if (it != fanout_with_ancestors.end()) {
2    for (const auto wtxid: parents) {
3        m_txreconciliation->TryRemovingFromSet(peer_id, wtxid);
4        invs_to_send.push_back(wtxid);
5    }
6} else {
7    // If the peer is registered for set reconciliation, maybe pick it as fanout
8    fanout = m_txreconciliation->ShouldFanoutTo(peer_id, fanout_targets);
9}

This may be a bit counterintuitive. I’ll give some though and potentially re-design so it clearer

Say there is an in-mempool parent announced earlier, so it’s not in any of the sets. SortPeersByFewestParents will return the same order as m_states (since all parent_count are 0), and fanout_with_ancestors will take first two after resize.

Then for two peers (specifically, the first two from m_states) this code is executed:

0                for (const auto wtxid: parents) {
1                    m_txreconciliation->TryRemovingFromSet(peer_id, wtxid);
2                    invs_to_send.push_back(wtxid);
3                }

TryRemovingFromSet will do nothing. But then invs_to_send.push_back(wtxid); is executed anyway. And always for the same two first peers from m_states. In other words, the first two are guaranteed to take the fanout in this case.

Sorry, you’re right. I’ve been looking at this being conditional to m_txreconciliation->TryRemovingFromSet(peer_id, wtxid), which is what happens with the descendants, but here it is unconditional.

It should be added only if TryRemovingFromSet succeeds, and therefore the ordering in case there are no ancestors won’t matter. I’ll also add some comments regarding that.

Notice the point of this is not to add something to invs_to_send but rather to move it from m_txreconciliation to invs_to_send, otherwise things would be sent more than once (or potentially captured by the bloom filters before hand, but still not optimal)

e942f3a7493908988eea08640d87b2ae420c5eef

This entire paragraph currently seems to me more confusing than useful. I suggest dropping it altogether.

e942f3a7493908988eea08640d87b2ae420c5eef

Duplicates the comment around MAX_RECONSET_SIZE. One of them we better dop.

90059530379cf99cf4b82d664ad35c1ddefc3d07

“Would fail” is very confusing. “Failed reconciliation” will have a technical meaning in the latter commits. Here, i’d rather be more explicit “two transactions mapped to the same short-id won’t be announced between these two peers”.

c790aa0e7ebfcf0b03b4d0ef5fcc0ddfa4199943

I think “upon trickle” or “see m_next_inv_send_time” is much less confusing.

I changed ReconSetSize to return a tuple, and updated this to read:

0 "Now the set contains %i reconcilable transactions (plus %i delayed transactions).\n",

ee46e21a5c913175415a192661b406b328209800

First I thought why don’t fanout=true here and handle it below. We can’t do it because txid/wtxid difference (although we could have a txid_or_wtxid variable above….). But then, you certainly want to at least set fanout=false here, otherwise it remains true and added to invs_to_send twice (it’s not critical but a bug still).

Not sure if this comment only applied before #30116 (review). But I think this is not currently the case.

Here we are only adding the parents. Leaving fanout=true triggers adding the actual transaction RelayTransaction was called with in the following if (fanout) block.

We could also add it here, but it would involve adding another boolean to skip the if (fanout) block, since we need to populate m_tx_inventory_to_send with data from invs_to_send which happens right after

1dce9aedc59eba2b623c7785f59430a586fbd833

the variable found could be dropped

Multimap is ordered by key, and for same-key (same parent_count) since c++11 the order is consistent (documented here). Feel free to include this as a comment, although I’m not even sure we care about the same exact output of multiple SortPeersByFewestParents calls.

(also it depends on the consistent ordering of m_states iterator too, which could be documented along the same lines, here and elsewhere it is iterated over)

I’ve been playing a bit with this, plus adding a test for SortPeersByFewestParents, which was missing. The multimap does have a consistent ordering, but it does reverse order of insertion instead of order of insertion for ties. Not really like it matters to be honest, if that is something we care about we can always start from a shuffled copy of m_states.

nvm, the order was changing because this is iterating over m_states, which is an unordered_map.

I’ll take the suggestion, but I’m thinking about modifying it a bit so the order does not have to be so reliant on m_states, which is something you also pointed out in an older review IIRC. What about something along the line of:

 0std::vector<NodeId> registered_peers;
 1for (const auto &[peer_id, _]: m_states) {
 2    registered_peers.push_back(peer_id);
 3}
 4std::shuffle(registered_peers.begin(), registered_peers.end(), FastRandomContext());
 5
 6std::multimap<uint16_t, NodeId> parents_by_peer;
 7for (const auto &peer_id: registered_peers) {
 8    if (const auto state = GetRegisteredPeerState(peer_id)) {
 9        const size_t parent_count = std::count_if(parents.begin(), parents.end(),
10               [state](const auto& wtxid){return state->m_local_set.find(wtxid) != state->m_local_set.end();});
11        parents_by_peer.emplace(parent_count, peer_id);
12    }
13}
14
15std::vector<NodeId> sorted_peers;
16sorted_peers.reserve(parents_by_peer.size());
17for (const auto &[_, node_id]: parents_by_peer) {
18    sorted_peers.emplace_back(node_id);
19}
20
21return sorted_peers;

I think an extra shuffle is a bit too much, because then for consistency you’d do it every time we access m_states? I think a comment in those places where order might matter is sufficient.

Im fine if you do this extra shuffle i guess.

0092f70314b8d59b41ff4bd2bc15a71f954668d4

Consider fanout=false because the peer has too many parents (cut the tail from fanout_with_ancestors). Now, we fail to add a transaction to the set (whatever reason, say set too full), and we’re now going to flood a child while reconciling the parents again?

Perhaps AddToSet result could be handled more carefully instead (or have a todo/comment, this is a corner case of a corner case of course).

Yes, that’s right. In the current revision, if the set is full and the given transaction has some ancestors, the children will be flooded while the parents will be reconciled, which may cause orphans.

I think we could handle this at the same level that we handled fanout_with_ancestors:

• Fanout to peers that have ancestors and have a full set
• Fanout to peers that have the least amount of ancestors

However, this will still be an issue in some cases, given we only select a subset of peers to fanout to when these conditions hold (currently 2, but let’s say n). If we do not fanout to all peers that fall under these conditions, there will always be some that will receive parents and children using different approaches, which may cause orphans. However, I think it is undesirable to fanout to all matches in this situation.

This raises the question, is it worth the added complexity, or should we add a comment acknowledging that this can be the case, but that we expect it to happen really infrequently?

I added a comment for this instead of making a full set part of the sorting criteria. This should not happen under normal circumstances provided the set size is defined to account for way over the expected traffic between reconciliations. A peer hitting the limit is likely to be either broken or an attacker, and I don’t think we should be catering to them (nor making the logic more complex based on that)

https://github.com/bitcoin/bitcoin/pull/30116/commits/f51e36057e509356890a70ced3a7209f98e8db4f

https://github.com/bitcoin/bitcoin/commit/0092f70314b8d59b41ff4bd2bc15a71f954668d4

consider defining this variable inside the loop rather than cleaning it after each iteration?

840a4e14f2d833717c87a54ec2707a92d5131ada

been thinking about the use of a delayed set here.

We apply the delay only on addition, but not on fanouting parents (or counting them), neither on removing stuff from the sets (say at receiving a transaction).

For me the choice is pretty arbitrary (and probably fine to save the code complexity for this rare corner case), but perhaps we would benefit from better documentation around it.

I see your point. The reasoning for this is so we can use ContainsTx in testing to check that things have been added/removed to/from the proper collection. Throughout the rest of the codebase, we always call this with true, and we do an implicit check on deletion.

I’m happy to consider an alternative that covers the same functionality if you have one

fc06786f32b2fc82c9571ebde67b4ff54f4ad825

this wrapper is not needed anymore. The Registered check already happens at the caller site. Just drop it and expose GetFanoutTargets?

 0        auto assign_key = [](const TxReconciliationState& peer_state, NodeId node_id, CSipHasher randomizer, std::vector<std::pair<uint64_t, NodeId>>& weighted_peers) {
 1            uint64_t hash_key = randomizer.Write(node_id).Finalize();
 2            weighted_peers.emplace_back(hash_key, node_id);
 3        };
 4
 5        for (const auto& [node_id, op_peer_state]: m_states) {
 6            const auto peer_state = std::get_if<TxReconciliationState>(&op_peer_state);
 7            if (peer_state) {
 8                if (peer_state->m_we_initiate) {
 9                    assign_key(*peer_state, node_id, deterministic_randomizer_out, sorted_outbounds);
10                } else {
11                    assign_key(*peer_state, node_id, deterministic_randomizer_in, sorted_inbounds);
12                }
13            }
14        }

very subjectively a little cleaner :)

8a73b1ca91b1ff47b56451ca4074f73ef71b9f79

Mind handling the result of erasure here? Either Assert/Assume or if

4b4d99fb2df2c60a2214487cec627bc560f50f53

this could be moved into the lambda :)