p2p: Fill reconciliation sets (Erlay) #28765

Could you explain a bit more why this is necessary, what is the lock order that would get violated if we did the locking later (just here, not necessarily in the comment)?

I tried a whole bunch of combinations. Say, you move the LOCK(m_peer_mutex); to L5831, where m_peer_map is used.

Then you get something like this in Cirrus (not exactly!).

 node0 2023-08-17T12:01:53.647510Z [msghand] [sync.cpp:97] [potential_deadlock_detected] POTENTIAL DEADLOCK DETECTED 
 node0 2023-08-17T12:01:53.647516Z [msghand] [sync.cpp:98] [potential_deadlock_detected] Previous lock order was: 
 node0 2023-08-17T12:01:53.647523Z [msghand] [sync.cpp:107] [potential_deadlock_detected]  'NetEventsInterface::g_msgproc_mutex' in net.cpp:2095 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647531Z [msghand] [sync.cpp:107] [potential_deadlock_detected]  'cs_main' in net_processing.cpp:5473 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647574Z [msghand] [sync.cpp:107] [potential_deadlock_detected]  (2) 'm_peer_mutex' in net_processing.cpp:5686 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647581Z [msghand] [sync.cpp:107] [potential_deadlock_detected]  'tx_relay->m_tx_inventory_mutex' in net_processing.cpp:5688 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647587Z [msghand] [sync.cpp:107] [potential_deadlock_detected]  'tx_relay->m_bloom_filter_mutex' in net_processing.cpp:5768 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647593Z [msghand] [sync.cpp:107] [potential_deadlock_detected]  (1) 'm_mempool.cs' in net_processing.cpp:5850 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647598Z [msghand] [sync.cpp:111] [potential_deadlock_detected] Current lock order is: 
 node0 2023-08-17T12:01:53.647604Z [msghand] [sync.cpp:122] [potential_deadlock_detected]  'NetEventsInterface::g_msgproc_mutex' in net.cpp:2095 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647610Z [msghand] [sync.cpp:122] [potential_deadlock_detected]  'm_chainstate_mutex' in validation.cpp:3102 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647616Z [msghand] [sync.cpp:122] [potential_deadlock_detected]  'cs_main' in validation.cpp:3124 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647622Z [msghand] [sync.cpp:122] [potential_deadlock_detected]  (1) 'MempoolMutex()' in validation.cpp:3126 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647627Z [msghand] [sync.cpp:122] [potential_deadlock_detected]  'cs_main' in net_processing.cpp:2013 (in thread 'msghand') 
 node0 2023-08-17T12:01:53.647633Z [msghand] [sync.cpp:122] [potential_deadlock_detected]  (2) 'm_peer_mutex' in net_processing.cpp:1593 (in thread 'msghand') 

From this log you see that m_peer_mutex should go before m_mempool.cs. I admit it might be not the 100% optimal placement, feels NP-hard to me :) Do you know how to approach this better?

no, I don't know a better approach, but thanks for the explanation!

nit: remove one //

I wonder if this algorithm (which took me a while to fully understand) could be simpler. E.g., if we used a sorted container for best_peers instead of a vector, inserted all of the peers, and then finally return the first targets elements of that container, I think we could do without the try_fanout_candidate lambda. Or would that be incorrect / less performant?

I'm thinking of something like the following (just to show idea, I didn't test it):

struct ComparePairs {
    bool operator()(const std::pair<uint64_t, NodeId>& left, const std::pair<uint64_t, NodeId>& right) const {
        return left.first > right.first;
    }
};
std::vector<NodeId> GetFanoutTargets(CSipHasher& deterministic_randomizer_with_wtxid,
                                     bool we_initiate, double limit) const EXCLUSIVE_LOCKS_REQUIRED(m_txreconciliation_mutex)
{
    // The algorithm works as follows. We iterate through the peers (of a given direction)
    // hashing them with the given wtxid, and sort them by this hash.
    // We then consider top `limit` peers to be low-fanout flood targets.
    // The randomness should be seeded with wtxid to return consistent results for every call.

    double integer_part;
    double fractional_peer = std::modf(limit, &integer_part);
    const bool drop_peer_if_extra = deterministic_randomizer_with_wtxid.Finalize() > fractional_peer * double(UINT64_MAX);
    const size_t targets = drop_peer_if_extra ? size_t(integer_part): size_t(integer_part) + 1;

    std::set<std::pair<uint64_t, NodeId>, ComparePairs> best_peers;

    for (auto indexed_state : m_states) {
        const auto cur_state = std::get_if<TxReconciliationState>(&indexed_state.second);
        if (cur_state && cur_state->m_we_initiate == we_initiate) {
            uint64_t hash_key = deterministic_randomizer_with_wtxid.Write(cur_state->m_k0).Finalize();
            best_peers.insert(std::make_pair(hash_key, indexed_state.first));
        }
    }

    std::vector<NodeId> result;
    auto it = best_peers.begin();
    for (size_t i = 0; i < targets && it != best_peers.end(); ++i, ++it) {
        result.push_back(it->second);
    }
    return result;
}

This is certainly better. For no good reason, i just chose to follow a pattern we use elsewhere and never reconsidered it. I will take this code.

Do we have to first add and then (maybe) drop a peer here (instead of determining how many peers we want at the beginning, and then getting as many peers as we can up the desired number).

10% of 30 is integer, so maybe also add an example with a fraction. If we run it often enough, we could probably assert that two values for total_fanouted are possible.

I'm always not sure what to do with these kinds of probabilistic scenarios... Say you run 1000 experiments, and get 1000/0, so the assert fails. Is 1,000,000 sufficient in that case? Or how do you think this should be asserted otherwise.

In commit "p2p: Add transactions to reconciliation set"

You could pick a fixed seed and wtxid for which you assert that with say 35 peers 3 are picked, and another seed/wtxid for which you assert that with 35 peers 4 are picked. That would at least show that the fractional probability code isn't just rounding down.

nit: remove empty line

In 983f8c6e305fd9707c109c2a92637825262b9b09: Since fanout is already initialized true, couldn't we simplify it?

@@ -5878,19 +5878,17 @@ bool PeerManagerImpl::SendMessages(CNode* pto)
                         if (reconciles_txs) {
                             auto txiter = m_mempool.GetIter(txinfo.tx->GetHash());
                             if (txiter) {
-                                if ((*txiter)->GetCountWithDescendants() > 1) {
-                                    // If a transaction has in-mempool children, always fanout it.
-                                    // Until package relay is implemented, this is needed to avoid
-                                    // breaking parent+child relay expectations in some cases.
-                                    //
-                                    // Potentially reconciling parent+child would mean that for every
-                                    // child we need to to check if any of the parents is currently
-                                    // reconciled so that the child isn't fanouted ahead. But then
-                                    // it gets tricky when reconciliation sets are full: a) the child
-                                    // can't just be added; b) removing parents from reconciliation
-                                    // sets for this one child is not good either.
-                                    fanout = true;
-                                } else {
+                                // If a transaction has in-mempool children, always fanout it.
+                                // Until package relay is implemented, this is needed to avoid
+                                // breaking parent+child relay expectations in some cases.
+                                //
+                                // Potentially reconciling parent+child would mean that for every
+                                // child we need to to check if any of the parents is currently
+                                // reconciled so that the child isn't fanouted ahead. But then
+                                // it gets tricky when reconciliation sets are full: a) the child
+                                // can't just be added; b) removing parents from reconciliation
+                                // sets for this one child is not good either.
+                                if ((*txiter)->GetCountWithDescendants() <= 1) {
                                     auto fanout_randomizer = m_connman.GetDeterministicRandomizer(RANDOMIZER_ID_FANOUTTARGET);
                                     fanout = m_txreconciliat
ion->ShouldFanoutTo(wtxid, fanout_randomizer, pto->GetId(),
                                                             
                    inbounds_nonrcncl_tx_relay, outbounds_non
rcncl_tx_relay);

In 983f8c6e305fd9707c109c2a92637825262b9b09: Correct me if I'm wrong, but we're going use inbounds_nonrcncl_tx_relay and outbounds_nonrcncl_tx_relay only whether reconciles_txs is true, couldn't we only fill them if so?:

                    if (reconciles_txs) {

I think a test can be added to exercise AddToSet and the check of the boundary MAX_SET_SIZE value.

I think can be > only. Generally sounds maximum in net_processing is understood as strictly superior, e.g MAX_INV_SZ usage.

This happens before the addition. Your suggestion would mean that the size could be 3001, which is not desired.

Given the docs on {Pre}RegisterPeer and the last paragraph on TryRemovingFromSet, shouldn't this also advise the caller to make sure the peer is registered?

I think i'd rather drop it from TryRemovingFromSet. It's not that strong anymore anyway, doesn't help much and pretty obvious i think. Let me know if you think differently.

nit: the reconciliation set

took this, but generally i think we have these mistakes all over the code and it's fine :)

I think this is a bit counter-intuitive. If the transaction to be added is already in the set, we will treat this as if it was added when that is actually not the case.

I guess the reasoning is that there should be no way of adding the same transaction more than once, so false is being used to signal failures. However, this seems like a way to potentially shoot ourselves in the foot.

If we want to keep the logic as is, I'd suggest that we at least mention this in the functions docs, given it currently reads:

[...]
* Returns whether it was added.

You're right, i shall think how to make it better.

Improved the documentation around it a bit.

Is this being used?

no, it's legacy i guess. wondering why the compiler haven't found it.

i think it's from the latter commits. can be dropped here.

I'm guessing this is supposed to be integral_part and fractional_part (?)

source: https://en.cppreference.com/w/cpp/numeric/math/modf

Shouldn't this need to be the other way around?

Maybe I'm confused by the name of the variables, but it seems like if add_extra is true, then you should do x+1

nit: also, tagets_size may be a better name, in lieu of limit which is already being used, given this does not really refer to the targets themselves, but to the size of the returned targets collection

flipped the < and flipped the ternary conditions. The behavior remains the same. Indeed, it was double-upside-down before.

The TODOs for the pubic fields referring to m_we_initiate and m_k0 should be fixable at this point, given they are both used by GetFanoutTargets, shouldn't they?

I think this stuff remained from the legacy code where its use was encapsulated.... just deleting the comments.

Where does this value come from? If we are going to use an arbitrary number, shouldn't we at least make it constant and add some reasoning?

eh, it's just a workaround to handle almost-0-fractional-value C++ thing i guess. Might as well be 0.0001 or 0.000000001. Not sure how to make it beautiful.

Right, got you. I guess we can also ask this the other way around to see if there is a cleaner workaround. In what case is destinations smaller than 1 but we still want to pass it to GetFanoutTargets?

Say we have 5 inbound Erlay peers and 0 inbound legacy peers. inbound_targets = (5+0) * 0.1 = 0.5 destinations = 0.5 - 0 = 0.5

It just means that we will take 1 inbound peer for fanout with a 50% chance.

I guess it will work just fine if i drop the 0.01 (1% or less chance) check. It's kinda unfortunate we have to do the compute if chance is that small. Fine with me either way, let me know what you think.

Just adding a comment with some context, saying that for chances lower than 1% it may not be worth the computation may be fine. It just struck me as weird where that value came from.

Shouldn't we move this a bit down the method given it may not even be used if we return early? (such as is the destinations are too small)

Either that, or seed it outside the method so you don't even need to pass the wtxid in, is writing to the randomizer is cheap enough.

Isn't reconciles_txs only used within fSendTrickle == true? Wouldn't it be worth moving it to that context?

it will have to be moved in the following PR, but yeah, I'll stick to your suggestion in this one.

Could this use the Wtxid type?

The test fails in debug mode because this assume conflicts with the test saying "Adding a duplicate transaction should not happen, but it does happen, nothing should break.".

I'm going to drop this test, unless you know a way how to handle this better.

Although this reduced it, I think the situation where the child is fanouted ahead could still happen if we receive the parent first, add it to the recon set, and only after that receive the child and decide to fanout it. Not sure if that is a problem though.

You're right.

My fear with this is unexpected behavior for tx sender: e.g., you craft a "package" thinking parent always goes ahead, but then child gets ahead (potentially with the attacker's help) and dropped on the floor due to some policy. Something along this, but maybe I'm making it up. Are these concerns at least semi-valid? @glozow

I can add "see whether a parent is in the set already" check, when looking at a child, if we think it's worth it.

I confirm with current implemented bip331 approach there is currently a MAX_ORPHAN_TOTAL_SIZE limit. You can always get a non-standard parent (e.g an under-dust output) and yet the child be policy valid. There is currently no sanitization of policy equivalence among a set of parent within ancpkginfo. In the future, you could have reconciliation at the pkgtxns-level or at package announcement (ancpkginfo). Ideally both, though that something that can be seen once erlay or bip331 are deployed.

Assuming there is no substantial timely delay between the parent being reconciliated and the child being fanout to the peer which would allow an overflow of MAX_ORPHAN_TOTAL_SIZE, I don’t think it’s altering the package acceptance of the receiving peer.

Assuming no exploitable timers, one can still make the simulation to quantity the “child drift” risk for a distribution of parent / child being reconciliated / fanout on the average time discrepancies between those 2 tx announcement strategy. Ideally in the future, we would move to sender-initiated package, which would remove this concern from my understanding. However, this is already a post-bip331 future, we’re talking about.

I wonder why are we using std::count here when we will find, at most, a single instance of peer_id within fanout_candidates. Wouldn't std::find be a better option?

On the same line, it may even be worth making GetFanoutTargets return a set instead of a vector, given we are sure that the elements of the collection won't be repeated

Is the assumption that we will never call this method more than once for the same wtxid? I wonder because it feels like the results may be deterministic based on the ordering of the m_states, which may not be persistent if a peer changes (?)

We call this for every peer. So there might be, say, 8 calls for the same wtxid. The risk of changing m_states i thought is acceptable, it's a rare event (outbound peers) and hard to exploit in a meaningful way. But I'm open to more analysis.

Why not just make a copy of the seeded randomizer instead of accumulating to it all the changes from m_states? That way you ensure that a change in the ordering is not going to, potentially, produce a completely different order of the whole best_peers set. In this case, the worst that could happen would be that the newly added peer jumps places, and becomes one of the selected/not selected peers, instead of a complete rearrange of the collection

done

Can you give more context regarding this?

Sure, what exactly?

here I talk about an alternative way to implement this. Say, we want to add a child to the set, because the parent is already there, and we don't want child ahead of parent. But the set is full. We can't ignore the limit — that's (a). (b) means that we could fanout child+parent in this case, but this remove parent from set operation is harder to reason about. Should we then remove parents of a parent too?

Maybe I overthink this issue.

I was referring to b). So this is trying to prevent a situation in which, potentially, the whole set is a cluster and once we are full, a new transaction belonging to the cluster is tried to be added, triggering a cascade removal and making us waste resources?

Yes. My primary concern is the complexity though. Cascade removal is more difficult to reason about. I just thought it was not worth it.

Fair

nit: if you have created a refactor commit to deal with removing the TODOs, it may be worth moving that change there.

Not sure if you're planning to squash it or not. Feel free to disregard.

Seems better to use a deterministic fast random context in tests, so that failures, if they happen, are deterministic?

Ups, I forgot to add this.

nit: Shouldn't this also be Wtxid& for consistency with the rest of the interface?

This is non-blocking, but I realized when reviewing the last changes to the tests

as long as you reack a new version it's fine, since no other acks are pending yet :)

I think that deterministic_randomizer could be passed by reference

Will fix if i end up retouching it :)

I believe the appropriate type in this case is CSipHasher&& deterministic_randomizer. This avoids a copy, allows the local variable inside ShouldFanoutTo to be modified, and the caller is constructing a fresh CSipHasher anyway.

The deterministic_randomizer_with_wtxid variable could be const CSipHasher& here (to make it clear that this object is only ever used as a starting point for (independent) hashes).

I believe it would be significantly faster to make this an std::vector<std::pair<uint64_t, NodeId>>, .reserve() it once, fill it up like in the loop below, and then std::sort it in-place using cmp_by_key. This has far better memory locality, less allocation overhead, and ought to have the same asymptotic complexity (O(n log n)).

Constructing the full set of fanout candidates any time you want to consider relaying anything to any node has O(n^2 log n) scaling (you'll call GetFanoutTargets O(n) times, and each does O(n log n) work going over all nodes), I believe.

That may or may not matter, but I'd consider at least one of these variants:

• Cache the GetFanoutTargets result per transaction as discussed elsewhere in this PR, making it O(n log n) only.
• Instead of computing an std::set<NodeId> in GetFanoutTargets (which at least involves an allocation per result), pass the peer_id to GetFanoutTargets, which can then just return a boolean (see if the peer_id appears in the first target_size elements of best_peers after sorting). This doesn't change the asymptotic behavior, but means there is just one allocation per ShouldFanoutTo.

Nit: const size_t targets_size = integral_part + add_extra.

An alternative which may be slightly faster (unsure, depends on how fast std::modf is):

const size_t targets_size = ((deterministic_randomizer_with_wtxid.Finalize() & 0xFFFFFFFF) + uint64_t(limit * 0x100000000)) >> 32;

It has lower precision, but I suspect 32 bits is more than sufficient here.

Pass indexed_state by reference. This is creating a copy of the entire TxReconciliationState for every element in m_states.

[](const auto& indexed_state) { ... } works.

best_peers.emplace(hash_key, indexed_state.first); (avoids a temporary std::pair object in the caller).

(it'd become best_peers.emplace_back(hash_key indexed_state.first); if best_peers is converted to a vector as suggested above.

Use const auto& indexed_state : m_states) here; you're making a copy of the entire TxReconciliationState for every iteration as written here.

Use const auto& [cur_peer_id, cur_peer] : m_peer_map here. You're making a copy of the PeerRef object for every iteration here (which isn't the end of the world, it's just a shared pointer, but copying those does involve an atomic memory operation).

nit: targes -> targets

nit: I'd be nice to define this as a constant

I don't think this is right(?), this logic is never triggered.

You are checking whether the size of tx_fanout_targes_cache_order is over the limit, but you are only adding elements to the queue within that same if context, meaning that the queue is always empty.

In "refactor: Add a pre-mutexed version of IsPeerRegistered":

I'd prefer to swap the names (= have an external IsPeerRegistered, and an internal IsPeerRegisteredInternal), as external callers ought to only care about the external one. Also is it possible to make the internal one private?

If this set may contain up to 3000 (=MAX_SET_SIZE) elements, it may be worth using an std::unordered_set instead (with something like SaltedTxidHasher as hasher).

In commit "p2p: Add transactions to reconciliation sets"

It doesn't actually matter whether we pick the lowest-hash_key entries or highest-hash_key entries to fanout to, I think? If so, can just use std::sort(best_peers.begin(), best_peers.end());, and drop the cmp_by_key.

Also, since you only care about the top targets_size results, I believe using std::partial_sort may be faster (but benchmark it).

ShouldFanoutTo looks fitting for benchmarking, and partial_sort had no effect. I took the former suggestion of course.

In commit "p2p: Add transactions to reconciliation set"

Would it make sense to have an (internal) helper function instead of IsPeerRegistered, that instead of returning a bool returns a TxReconciliationState* (nullptr if not found)? That would avoid locking/finding twice. I suspect it'd be usable in other places too.

In commit "p2p: Add transactions to reconciliation set"

This value could be cached inside TxReconciliationTracker::Impl I think, and updated on registering/deregister, to avoid recomputating it every time?

In commit "Cache fanout candidates to optimize txreconciliation"

Since the cache entry std::set<NodeId> don't change until being replaced entirely, I believe it would be more efficient to use a std::vector<NodeId>, with the nodeids in sorted order. You can then use std::binary_search to query in that vector.

It'd be more efficient as std::vector has much better memory locality than std::set, and fewer indirections.

If you do this, can also just reuse the best_peers vector, and shrink it to target_size (but make sure to call shrink_to_fit, as otherwise the memory for the remainder won't be released.

In commit "Cache fanout candidates to optimize txreconciliation"

Use std::move around new_fanout_candidates (or best_peers if you take my earlier suggestion to use a vector), to avoid a copy. If so, lookup the peer_id in it before moving, so you can return that value.

for code readability, such variables could be renamed inbounds_flooding_tx_relay / outbounds_flooding_tx_relay, which is matching the low-fanout flooding strategy used for them.

can add a LogPrint(BCLog::NET, “Non-signaling reconciliation inbound peers flooding %d Outbound peers flooding %d for debug”); for debug purpose and observation

can be constified same than OUTBOUND_FANOUT_DESTINATIONS and INBOUND_FANOUT_DESTINATIONS_FRACTION as explanation for this value is tight to them

Not really related. Change these constants in any way, and the 0.001 value won't be affected.

okay will read back the txrelayism issue on const selection.

In the eventuality of an influx of inbound transactions, faster than we can flush out them to low-fanout flooding peers, my understanding of dropping the upfront wtxid candidate, we would keep propagating this transaction only according to tx-relay policy and connection state of other peers (not this NodeId anymore).

I understand we’re fanning out only to outbound peers (m_tx_fanout_targets_cache_data doc), though here it’s more a dependency on the perfomance capabilities of the full-node itself (i.e how fast you process vInv(MSG_WTX) and how fast you-reannounce them to downstream peers if valid). To interferes with a transaction propagation, assuming a non-listening node, an attacker would have to be puppet or compromise all our low-fanout outbound peers, I think ? Obviously more outbound peers would make things better on this front, which should be allowed by Erlay tx-relay bandwidth savings.

In terms of peers-side policy check (i.e m_fee_filter_received), this policy limit is at the tx-relay link level and this is unilaterally initiated by the peer. As such I think there is no guarantee that between time point A we add a Wtxid in m_local_set and time point B we reconciliate, we have not received a new bip133 message, updating the m_fee_filter_received. I believe we can retro-actively stale stored Wtxid and as such a bandwidth performance leak, under situations of sudden network mempool spikes.

I don’t think there is that much a tx-announcement strategy (either flooding or reconciliation) can do it in itself, unless assuming some extensions to bip133 messages to commit on a feerate-level duration. As such, I think any improvement is out of scope for this PR.

I think “(1)” can be extended a bit more e.g “Memory DoS issue for a laggy peer are bounded by DEFAULT_MAX_PEER_CONNECTIONS and reconciliation state is clean up with FinalizeNode".

In 17ae36c0f60b976c237bdb522059c31cf113c773: Is there any reason to define rand_i into bench.run? Couldn't we have it out of it? Notice that without it, the bench is 70% faster.

I'm dropping it. Do you understand why this simple op as var assignment eats so much perf? :)

Do you understand why this simple op as var assignment eats so much perf? :)

I don't think std::rand() has any quality or performance documentations, so it is free to do whatever it wants

One follow-up improvement, all the descendants in GetCountWithDescendants() could be marked with parent_fanout=true, that way we guarantee more stringently that all the members of a chain of transactions are tx-announcement relayed through the same strategy (either erlay or low-fanout flooding). I’ll check if there is test coverage here.

constexpr?

FANOUTTARGET -> FANOUT_TARGET?

std::for_each?

Looking on CSipHasher, given it’s a pseudo-random hash function, verified it’s well-initialized from two hidden random 64-bit seeds in src/init.cpp (L1239). Then we add a CSipHasher instance provided by CConman at TxReconciliationTracker initialization in src/net_processing.cpp. This respect the SipHash’s PRF’s requirement to initialize it with a random 128-bit key. I still wonder if in the future TxReconciliationTracker shouldn’t get it’s own random seed (i.e use GetRand(), it promises fast entropy generation) to isolate tx-announcement from the rest of network connection management.

This seems to be consistent with how a deterministic randomizer is seeded in many other places in the codebase. What is your rationale for making it different here?

This variable name can be called destination rather than limit to be consistent with ShouldFanoutTo and denotates more clearly it’s the sample space boundary.

I think the comment L66 in src/node/txreconciliation.cpp can be updated to reflect the usage of m_k0 as a siphash input string for low-fanout flood peers selection. Not only used in ComputeShortID.

I think this can actually be seeded with anything, it doesn't have to be m_k0. IMO it'd better not be, to not repurpose something that is meant for something completely different

nit: you could return it directly.

What does "laggy peer" mean?

I'm guessing "a peer for some reason does not request reconciliations from us for a long while", hence why it references (1)