p2p: Fill reconciliation sets (Erlay) attempt 2

sr-gi commented at 8:01 pm on May 15, 2024: member

This is a re-attempt of #28765

The main differences from it are:

Most outstanding comments have been addressed (or responded to on the original PR)
The description of how a node is picked in IsFanoutTarget has been updated to reflect what the algorithm is doing (not how it is doing it)
The way hash_key is seeded in IsFanoutTarget has changed (from m_k0 to node_id). This is to prevent using m_k0 for something it is not intended to, given what data we feed to the randomizer should not matter for this
The cache in IsFanoutTarget was only being fed data to, but never checked. This has been reworked to make use of it
destinations/target has been renamed to n in ShouldFanoutTo/IsFanoutTarget
The PR has been rebased

Also, the following things have been added/changed to the approach:

Deal with short id collisions by fanning out both transactions
Deal with ancestors being present on the mempool when a child needs to be placed in the fanout or reconciliation sets (as opposed to dealing with parents, which was the wrong approach)
Move fanout/reconcile logic from INV creation to RelayTransaction
- Create a delayed set where transactions that are added for reconciliation but still not offered to peers (for privacy reasons) live. This is analogous to how fanout works, where transactions are only made available on trickle intervals

Erlay Project Tracking: https://github.com/bitcoin/bitcoin/issues/30249

DrahtBot commented at 8:01 pm on May 15, 2024: contributor

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

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/30116.

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#31153 (bench: Remove various extraneous benchmarks by dergoegge)
#31001 (refactor: ensure type safety for txid and wtxid in RelayTransaction by marcofleon)
#30987 (Don’t zero-after-free DataStream: Faster IBD on some configurations by davidgumberg)
#29415 (Broadcast own transactions only via short-lived Tor or I2P connections by vasild)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label P2P on May 15, 2024

sr-gi commented at 8:05 pm on May 15, 2024: member

I’ve talked to @naumenkogs about picking this up and he was happy about it. I’m happy to close this if he changes his mind.

sr-gi renamed this:
~~p2p: Fill reconciliation sets (Erlay) attempt: 2~~
p2p: Fill reconciliation sets (Erlay) attempt 2
on May 15, 2024

in src/node/txreconciliation.h:127 in 7c047d30cb outdated

80+     * Returns whether the transaction appears in the set.
81+     */
82+    bool AddToSet(NodeId peer_id, const Wtxid& wtxid);
83+
84+    /**
85+     * Before Step 2, we might want to remove a wtxid from the reconciliation set, for example if

brunoerg commented at 10:03 pm on May 15, 2024:

In “p2p: Functions to add/remove wtxids to tx reconciliation sets” 7c047d30cb0eadc8a424cb01de2fcd0978e22206: What is the step 2? This comment seems a little confuse because I couldn’t find it as I see for Step 1.

sr-gi commented at 1:44 pm on May 16, 2024:

I think this refers to the steps listed at the beginning of the file. Not all of them are covered yet. This PR leaves this right before 2 AFAICT

brunoerg commented at 3:02 pm on May 16, 2024:

My bad, missed that. Thanks.

in src/node/txreconciliation.cpp:180 in 7c047d30cb outdated

176+                          wtxid.ToString(), peer_id, peer_state->m_local_set.size());
177+        }
178+        return true;
179+    }
180+
181+    bool TryRemovingFromSet(NodeId peer_id, const Wtxid& wtxid_to_remove) EXCLUSIVE_LOCKS_REQUIRED(!m_txreconciliation_mutex)

brunoerg commented at 10:06 pm on May 15, 2024:

In “p2p: Functions to add/remove wtxids to tx reconciliation sets” https://github.com/bitcoin/bitcoin/commit/7c047d30cb0eadc8a424cb01de2fcd0978e22206: Perhaps adding a log when removing from set?

sr-gi commented at 2:51 pm on May 16, 2024:

Updated to track both successful and unsuccessful deletions (in debug log, to prevent unnecessarily spamming the logs)

in src/bench/txreconciliation.cpp:7 in 3f59bf83a4 outdated

0@@ -0,0 +1,40 @@
1+// Copyright (c) 2020-2022 The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+#include <bench/bench.h>
6+
7+#include <net.h>

brunoerg commented at 1:02 pm on May 16, 2024:

In “add bench for ShouldFanoutTo” 3f59bf83a41b7787f9c43c277b5e62f327a72c3e: net.h include seems unnecessary.

sr-gi commented at 2:57 pm on May 16, 2024:

Removed

sr-gi force-pushed on May 16, 2024

in src/test/txreconciliation_tests.cpp:110 in 2e29e9beee outdated

105+    NodeId peer_id1 = 1;
106+    tracker.PreRegisterPeer(peer_id1);
107+    BOOST_REQUIRE_EQUAL(tracker.RegisterPeer(peer_id1, true, 1, 1), ReconciliationRegisterResult::SUCCESS);
108+    BOOST_CHECK(tracker.IsPeerRegistered(peer_id1));
109+
110+    for (size_t i = 0; i < 3000; ++i)

brunoerg commented at 2:51 pm on May 22, 2024:

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())));

sr-gi commented at 2:59 pm on May 22, 2024:

I’ve been talking to @sipa about this recently and I think the limit may not be necessary if the approach for when to compute the reconciliation sets is changed. I’m may get rid of it, but if not, I’ll take this

sr-gi commented at 3:05 pm on May 30, 2024:

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

Thanks!

sr-gi force-pushed on May 30, 2024

sr-gi force-pushed on May 31, 2024

sr-gi commented at 4:29 pm on May 31, 2024: member

I’ve slightly extended the approach adding 3 commits to deal with short id collisions, which were not taken into account. Some of this may be squashable, I’ve added them separately for now so they are easy to diff/review.

This would be missing an additional commit/amend to deal with #28765 (review), which I overlooked when addressing the outstanding comments

sr-gi force-pushed on May 31, 2024

DrahtBot added the label CI failed on May 31, 2024

DrahtBot commented at 4:32 pm on May 31, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/25659971810

sr-gi force-pushed on Jun 3, 2024

DrahtBot removed the label CI failed on Jun 3, 2024

sr-gi force-pushed on Jun 7, 2024

sr-gi marked this as a draft on Jun 7, 2024

sr-gi commented at 6:21 pm on June 7, 2024: member

I added two more commits, moving the fanout/reconciling logic to RelayTransaction instead of send message, plus dealing with ancestors in mempool, instead of descendants (which seemed to be the wrong approach).

I’m moving this to draft for now until I clean it a bit, plus get some feedback on the approach

DrahtBot added the label CI failed on Jun 8, 2024

DrahtBot commented at 5:17 am on June 8, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/25955152377

Saraeutsza approved

sr-gi force-pushed on Jun 10, 2024

in src/node/txreconciliation.cpp:496 in f71575cf43 outdated

424@@ -390,7 +425,13 @@ TxReconciliationTracker::~TxReconciliationTracker() = default;
425 
426 uint64_t TxReconciliationTracker::PreRegisterPeer(NodeId peer_id)
427 {
428-    return m_impl->PreRegisterPeer(peer_id);
429+    const uint64_t local_salt{GetRand(UINT64_MAX)};
430+    return m_impl->PreRegisterPeer(peer_id, local_salt);

Prabhat1308 commented at 11:58 am on June 11, 2024:

What is the intention behind moving salt calculation out of PreRegisterPeer ? Now if PreRegisterPeer is not executed due to lock being held we are doing meaningless computation .

sr-gi commented at 5:09 pm on June 11, 2024:

The purpose is for PreRegisterPeer to be callable with a fixed salt (via PreRegisterPeerWithSalt), so collisions can be tested. This is just moving it out of the PImpl, the effects on the external caller should be the same

sr-gi force-pushed on Jun 11, 2024

DrahtBot removed the label CI failed on Jun 12, 2024

sr-gi force-pushed on Jun 13, 2024

sr-gi marked this as ready for review on Jun 13, 2024

sr-gi commented at 8:01 pm on June 13, 2024: member

This should be ready for review now.

in src/net_processing.cpp:2160 in 9de4233d00 outdated

2366+                if (!parents_refs.empty()) {
2367+                    for (const auto &tx : parents_refs) {
2368+                        parents.emplace_back(tx.get().GetTx().GetWitnessHash());
2369+                    }
2370+                    fanout_with_ancestors = m_txreconciliation->SortPeersByFewestParents(parents);
2371+                    fanout_with_ancestors.resize(2); // FIXME: Resize to 2 for now

sr-gi commented at 8:02 pm on June 13, 2024:

This is pending. Happy get get feedback on how many to pick (either hardcoded or based on what)

Prabhat1308 commented at 3:26 pm on June 16, 2024:

The number of parents per peer should mostly be in the range of (0-2/3) , This should include a significant numbers of peers to reconcile with . A constant number might not be ideal considering if the array returned is smaller than that constant number , we might be reconciling with non-existent peers .

sr-gi commented at 2:53 pm on June 18, 2024:

I’m curious to know where do you get that parent count range from 🤔

Prabhat1308 commented at 7:57 pm on June 19, 2024:

I got some data for about 4100+ transactions from a source (cant be sure of the credibility) for bitcoin transactions in a mempool and i ran a script to count the avg. parents which came to approx. 1.6 . Another way I thought of this is I got the avg. number of inputs per transaction . For 2023-2024 the average is somewhat between 2-3 . If we make a tree like dependency structure for transaction considering the transactions which had their inputs as utxo’s , the probability of having higher ancestories diminishes rapidly since any transaction missing will eliminate the ancestory above it . Considering the mempool are in general highly updated , ancestories beyond grandparent transactions are not very likely to be there . So if I consider this , there are supposed to be 6 ancestors for a transactions on an average and we can expect 2-3 range to have a significant number of transactions.

sr-gi commented at 2:46 pm on June 20, 2024:

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.

brunoerg commented at 2:28 pm on September 25, 2024:

Shouldn’t we decrease the number of inbounds_fanout_tx_relay/outbounds_fanout_tx_relay by the number of peers we’re going to fanout with ancestors?

sr-gi commented at 10:11 am on September 26, 2024:

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.

naumenkogs commented at 9:54 am on November 1, 2024:

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.

sr-gi force-pushed on Jun 14, 2024

sr-gi force-pushed on Jun 18, 2024

DrahtBot added the label CI failed on Jun 19, 2024

DrahtBot removed the label CI failed on Jun 19, 2024

DrahtBot added the label Needs rebase on Jun 20, 2024

sr-gi force-pushed on Jun 20, 2024

DrahtBot removed the label Needs rebase on Jun 20, 2024

glozow commented at 11:03 am on July 4, 2024: member

Needs rebase (for #29625)

DrahtBot added the label Needs rebase on Jul 4, 2024

in src/test/txreconciliation_tests.cpp:350 in 2e0b6742b8 outdated

262+        total_fanouted2 += tracker2.ShouldFanoutTo(wtxid, i,
263+                                                   /*inbounds_fanout_tx_relay=*/0, /*outbounds_fanout_tx_relay=*/0);
264+    }
265+    BOOST_CHECK_EQUAL(total_fanouted1, 3);
266+    BOOST_CHECK_EQUAL(total_fanouted2, 4);
267+

Prabhat1308 commented at 7:52 pm on July 7, 2024:

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 .

sr-gi commented at 8:22 pm on September 13, 2024:

I haven’t taken this yet, given I’m working on a last commit reworking part of how the fanout selection works. I may consider it after that. In any case, looks like this is only filling the cache but not testing anything after it

sr-gi commented at 8:00 pm on November 1, 2024:

Resolving since we don’t have a cache anymore

sr-gi commented at 1:40 pm on July 8, 2024: member

Needs rebase (for #29625)

Currently working on some simulations, will rebase soon

sr-gi force-pushed on Sep 13, 2024

DrahtBot added the label CI failed on Sep 13, 2024

DrahtBot commented at 7:59 pm on September 13, 2024: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/30127266270

Make sure to run all tests locally, according to the documentation.

The failure may happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

DrahtBot removed the label Needs rebase on Sep 13, 2024

sr-gi force-pushed on Sep 13, 2024

DrahtBot removed the label CI failed on Sep 13, 2024

in src/net_processing.cpp:2453 in 3879f550d3 outdated

2451+            if (!result.m_succeeded) {
2452+                // If the transactions fails to get into the set, we fanout
2453+                invs_to_send.push_back(wtxid);
2454+                // If the transaction fails because it collides with an existing one,
2455+                // we also remove and fanout the conflict and all its descendants.
2456+                // This is because our peer may have added the conflicting tranaction

brunoerg commented at 12:47 pm on September 21, 2024:

0                // This is because our peer may have added the conflicting transaction

Saraeutsza approved

sr-gi force-pushed on Oct 2, 2024

sr-gi commented at 3:35 pm on October 2, 2024: member

I’ve added a commit introducing a delayed set to store transactions that are being reconciled, but won’t be added to the sketch should it be constructed at this time. This is to mimic the fanout trickling logic where transactions are only made available to peers if they would have been INVed to them. This was already part of @naumenkogs approach, but was scrapped out when reworking when data is added to the reconciliation set in a22b2364f5942266596c78ad306b1e32aa89aa0f

sr-gi force-pushed on Oct 2, 2024

sr-gi force-pushed on Oct 3, 2024

in src/node/txreconciliation.cpp:457 in 20772c0778 outdated

452+        // We first decide how many reconciling peers of a given direction we want to flood to,
453+        // and then generate a list of peers of that size for a given transaction. We then see
454+        // whether the given peer falls into this list.
455+        double n;
456+        if (peer_state->m_we_initiate) {
457+            n = OUTBOUND_FANOUT_DESTINATIONS - outbounds_fanout_tx_relay;

marcofleon commented at 3:46 pm on October 12, 2024:

Can outbounds_fanout_tx_relay ever be greater than 1 here? I think if we have two (or more) unregistered outbound peers and at least one registered peer, then this results in an unsigned integer overflow. Which then overflows targets_size in IsFanoutTarget.

naumenkogs commented at 3:03 pm on October 23, 2024:

working on a test and fix for this.

sr-gi commented at 3:44 pm on October 23, 2024:

Oh sorry, I forgot to reply to this. We discussed this in person last week and this is indeed an issue. Happy to take your fix @naumenkogs

naumenkogs commented at 10:06 am on October 24, 2024:

Okay, see the last two commits here.

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

sr-gi commented at 7:42 pm on October 28, 2024:

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.

sr-gi commented at 7:48 pm on October 28, 2024:

I squashed the change in here: ad95b2c0e21f1e865f967aa9463ef99bc252550a

naumenkogs commented at 9:57 am on October 29, 2024:

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());

naumenkogs commented at 10:19 am on October 29, 2024:

feel free to resolve this and let’s talk in the new commit.

marcofleon commented at 4:19 pm on October 12, 2024: contributor

I fuzzed the txreconciliation class with -DSANITIZERS=fuzzer,undefined,integer and two related runtime errors occurred:

 0../../src/node/txreconciliation.cpp:457:46: runtime error: unsigned integer overflow: 1 - 3 cannot be represented in type 'size_t' (aka 'unsigned long')
 1    [#0](/bitcoin-bitcoin/0/) 0x55ddab3b7d99 in TxReconciliationTracker::Impl::ShouldFanoutTo(transaction_identifier<true> const&, long, unsigned long, unsigned long) erlayfuzzbuild/src/../../src/node/txreconciliation.cpp:457:46
 2    [#1](/bitcoin-bitcoin/1/) 0x55ddaa5521c7 in txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_7::operator()() const erlayfuzzbuild/src/test/fuzz/../../../../src/test/fuzz/txreconciliation.cpp:118:46
 3    [#2](/bitcoin-bitcoin/2/) 0x55ddaa5521c7 in unsigned long CallOneOf<txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_0, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_1, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_2, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_3, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_4, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_5, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_6, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_7, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_8>(FuzzedDataProvider&, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_0, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_1, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_2, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_3, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_4, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_5, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_6, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_7, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_8) erlayfuzzbuild/src/test/fuzz/../../../../src/test/fuzz/util.h:42:27
 4    [#3](/bitcoin-bitcoin/3/) 0x55ddaa5521c7 in txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>) erlayfuzzbuild/src/test/fuzz/../../../../src/test/fuzz/txreconciliation.cpp:68:9
 5    [#4](/bitcoin-bitcoin/4/) 0x55ddaa6bf726 in std::function<void (std::span<unsigned char const, 18446744073709551615ul>)>::operator()(std::span<unsigned char const, 18446744073709551615ul>) const /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/std_function.h:591:9
 6    [#5](/bitcoin-bitcoin/5/) 0x55ddaa6bf726 in LLVMFuzzerTestOneInput erlayfuzzbuild/src/test/fuzz/util/../../../../../src/test/fuzz/fuzz.cpp:209:5
 7    [#6](/bitcoin-bitcoin/6/) 0x55ddaa04a840 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19e6840) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
 8    [#7](/bitcoin-bitcoin/7/) 0x55ddaa049f75 in fuzzer::Fuzzer::RunOne(unsigned char const*, unsigned long, bool, fuzzer::InputInfo*, bool, bool*) (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19e5f75) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
 9    [#8](/bitcoin-bitcoin/8/) 0x55ddaa04b705 in fuzzer::Fuzzer::MutateAndTestOne() (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19e7705) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
10    [#9](/bitcoin-bitcoin/9/) 0x55ddaa04c305 in fuzzer::Fuzzer::Loop(std::vector<fuzzer::SizedFile, std::allocator<fuzzer::SizedFile>>&) (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19e8305) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
11    [#10](/bitcoin-bitcoin/10/) 0x55ddaa03a52f in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19d652f) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
12    [#11](/bitcoin-bitcoin/11/) 0x55ddaa0638e2 in main (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19ff8e2) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
13    [#12](/bitcoin-bitcoin/12/) 0x7fcd32ab6249  (/lib/x86_64-linux-gnu/libc.so.6+0x27249) (BuildId: 58254ca972028402bc40624f81388d85ec95f70d)
14    [#13](/bitcoin-bitcoin/13/) 0x7fcd32ab6304 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x27304) (BuildId: 58254ca972028402bc40624f81388d85ec95f70d)
15    [#14](/bitcoin-bitcoin/14/) 0x55ddaa02f920 in _start (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19cb920) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
16SUMMARY: UndefinedBehaviorSanitizer: unsigned-integer-overflow ../../src/node/txreconciliation.cpp:457:46 
17
18../../src/node/txreconciliation.cpp:401:100: runtime error: 7.92282e+28 is outside the range of representable values of type 'unsigned long'
19    [#0](/bitcoin-bitcoin/0/) 0x55ddab3c704a in TxReconciliationTracker::Impl::IsFanoutTarget(transaction_identifier<true> const&, long, bool, double) erlayfuzzbuild/src/../../src/node/txreconciliation.cpp:401:100
20    [#1](/bitcoin-bitcoin/1/) 0x55ddab3b7b83 in TxReconciliationTracker::Impl::ShouldFanoutTo(transaction_identifier<true> const&, long, unsigned long, unsigned long) erlayfuzzbuild/src/../../src/node/txreconciliation.cpp:471:16
21    [#2](/bitcoin-bitcoin/2/) 0x55ddaa5521c7 in txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_7::operator()() const erlayfuzzbuild/src/test/fuzz/../../../../src/test/fuzz/txreconciliation.cpp:118:46
22    [#3](/bitcoin-bitcoin/3/) 0x55ddaa5521c7 in unsigned long CallOneOf<txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_0, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_1, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_2, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_3, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_4, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_5, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_6, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_7, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_8>(FuzzedDataProvider&, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_0, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_1, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_2, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_3, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_4, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_5, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_6, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_7, txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_8) erlayfuzzbuild/src/test/fuzz/../../../../src/test/fuzz/util.h:42:27
23    [#4](/bitcoin-bitcoin/4/) 0x55ddaa5521c7 in txreconciliation_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>) erlayfuzzbuild/src/test/fuzz/../../../../src/test/fuzz/txreconciliation.cpp:68:9
24    [#5](/bitcoin-bitcoin/5/) 0x55ddaa6bf726 in std::function<void (std::span<unsigned char const, 18446744073709551615ul>)>::operator()(std::span<unsigned char const, 18446744073709551615ul>) const /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/std_function.h:591:9
25    [#6](/bitcoin-bitcoin/6/) 0x55ddaa6bf726 in LLVMFuzzerTestOneInput erlayfuzzbuild/src/test/fuzz/util/../../../../../src/test/fuzz/fuzz.cpp:209:5
26    [#7](/bitcoin-bitcoin/7/) 0x55ddaa04a840 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19e6840) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
27    [#8](/bitcoin-bitcoin/8/) 0x55ddaa049f75 in fuzzer::Fuzzer::RunOne(unsigned char const*, unsigned long, bool, fuzzer::InputInfo*, bool, bool*) (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19e5f75) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
28    [#9](/bitcoin-bitcoin/9/) 0x55ddaa04b705 in fuzzer::Fuzzer::MutateAndTestOne() (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19e7705) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
29    [#10](/bitcoin-bitcoin/10/) 0x55ddaa04c305 in fuzzer::Fuzzer::Loop(std::vector<fuzzer::SizedFile, std::allocator<fuzzer::SizedFile>>&) (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19e8305) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
30    [#11](/bitcoin-bitcoin/11/) 0x55ddaa03a52f in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19d652f) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
31    [#12](/bitcoin-bitcoin/12/) 0x55ddaa0638e2 in main (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19ff8e2) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
32    [#13](/bitcoin-bitcoin/13/) 0x7fcd32ab6249  (/lib/x86_64-linux-gnu/libc.so.6+0x27249) (BuildId: 58254ca972028402bc40624f81388d85ec95f70d)
33    [#14](/bitcoin-bitcoin/14/) 0x7fcd32ab6304 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x27304) (BuildId: 58254ca972028402bc40624f81388d85ec95f70d)
34    [#15](/bitcoin-bitcoin/15/) 0x55ddaa02f920 in _start (/root/bitcoin/erlayfuzzbuild/src/test/fuzz/fuzz+0x19cb920) (BuildId: 9429992cf566016ee2d3d51625e57700f09635fc)
35SUMMARY: UndefinedBehaviorSanitizer: float-cast-overflow ../../src/node/txreconciliation.cpp:401:100 
36==222068== ERROR: libFuzzer: out-of-memory (used: 4046Mb; limit: 2048Mb)
37   To change the out-of-memory limit use -rss_limit_mb=<N>
38
39MS: 4 ChangeBinInt-ChangeBit-CrossOver-CrossOver-; base unit: 0cbe4c9fe667ead352437139e9ea437783de5c0c
400xad,0xad,0xad,0x60,0x0,0x0,0x0,0x0,0x0,0x0,0x37,0xff,0xff,0xff,0xff,0xd2,0xff,0xff,0xff,0xd2,0xd2,0xd2,0xd2,0xd2,0xd2,0xd2,0xd2,0x3b,0xd2,0xd2,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xdf,0xff,0x0,0xff,0xff,0x9,0x0,0x0,0x0,0x0,0x0,0xff,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x75,0xff,0xff,0xff,0xd2,0xd2,0xd2,0xd2,0xd2,0xd2,0xbf,0xff,0x0,0x0,0x0,0x52,0xad,0xad,0xbf,0x6a,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xa0,0xad,0x1,0x0,0x0,
41\255\255\255`\000\000\000\000\000\0007\377\377\377\377\322\377\377\377\322\322\322\322\322\322\322\322;\322\322\377\377\377\377\377\377\377\377\337\377\000\377\377\011\000\000\000\000\000\377\000\000\000\000\000\000\000u\377\377\377\322\322\322\322\322\322\277\377\000\000\000R\255\255\277j\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\240\255\001\000\000
42artifact_prefix='./'; Test unit written to ./oom-b217ee9df2670caf13a47abe1623c2f80e6d1f02
43Base64: ra2tYAAAAAAAADf/////0v///9LS0tLS0tLSO9LS///////////f/wD//wkAAAAAAP8AAAAAAAAAdf///9LS0tLS0r//AAAAUq2tv2qgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgrQEAAA==
44SUMMARY: libFuzzer: out-of-memory

oom-b217ee9df2670caf13a47abe1623c2f80e6d1f02.txt

Left a question about it below.

in src/node/txreconciliation.cpp:234 in 50c19dd21f outdated

208+        }
209+
210+        return false;
211+    }
212+
213+    bool HasCollision(NodeId peer_id, const Wtxid& wtxid, Wtxid& collision, uint32_t &short_id) EXCLUSIVE_LOCKS_REQUIRED(!m_txreconciliation_mutex)

naumenkogs commented at 8:16 am on October 28, 2024:

50c19dd21f6e437cd8e3d9047a89d793d097c5e5 Not sure it’s worth exposing this external method if the only reason to have it is testing.

sr-gi commented at 2:34 pm on November 1, 2024:

Happy to consider an alternative approach that allows us to check there are no collisions without having to expose a public method if you have something in mind

naumenkogs commented at 9:07 am on November 4, 2024:

Yeah just dropping HasCollision, keeping HasCollisionInternal. The former is used only in tests. And since its implementation is trivial, i think testing for collisions through AddToSet is sufficient.

sr-gi commented at 7:12 pm on November 13, 2024:

Sure, looks like tests can be rewritten for it not to be needed. Will address in the next push

in src/net_processing.cpp:6276 in 50c19dd21f outdated

6272+                            auto result = m_txreconciliation->AddToSet(pto->GetId(), wtxid);
6273+                            if (!result.m_succeeded) {
6274+                                vInv.push_back(inv);
6275+                                // If the transaction fails because it collides with an existing one,
6276+                                // we also remove and fanout the conflict and all its descendants.
6277+                                // This is because our peer may have added the conflicting tranaction

naumenkogs commented at 8:20 am on October 28, 2024:

50c19dd21f6e437cd8e3d9047a89d793d097c5e5

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

sr-gi commented at 6:58 pm on October 30, 2024:

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 😅

naumenkogs commented at 8:22 am on October 31, 2024:

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     */

naumenkogs commented at 10:23 am on October 31, 2024:

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.

sr-gi commented at 8:05 pm on November 1, 2024:

Agreed the docs for TxReconciliationTracker::AddToSet could be improved. I’ll update it with a version of your suggestion

in src/net_processing.cpp:6286 in 50c19dd21f outdated

6282+                                    CTxMemPool::setEntries descendants;
6283+                                    m_mempool.CalculateDescendants(m_mempool.get_iter_from_wtxid(collision.value()), descendants);
6284+                                    for (const auto &txit: descendants) {
6285+                                        auto wtxid = txit->GetTx().GetWitnessHash();
6286+                                        m_txreconciliation->TryRemovingFromSet(pto->GetId(), wtxid);
6287+                                        vInv.emplace_back(MSG_WTX, wtxid);

naumenkogs commented at 8:22 am on October 28, 2024:

50c19dd21f6e437cd8e3d9047a89d793d097c5e5 what would happen if a descendant was already flooded?

sr-gi commented at 3:14 pm on November 1, 2024:

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

sr-gi commented at 8:39 pm on November 1, 2024:

I just realized this is also the case for the ancestors. When relaying with ancestors, we should also check that the ancestor we are trying to relay is part of the reconciliation set (i.e. that it has not been previously flooded)

naumenkogs commented at 9:47 am on November 4, 2024:

The fix should be done in p2p: Deal with shortid collisions for reconciliation sets, please move it if you retouch.

in src/net_processing.cpp:6285 in 50c19dd21f outdated

6281+                                    Assume(peer->m_wtxid_relay);
6282+                                    CTxMemPool::setEntries descendants;
6283+                                    m_mempool.CalculateDescendants(m_mempool.get_iter_from_wtxid(collision.value()), descendants);
6284+                                    for (const auto &txit: descendants) {
6285+                                        auto wtxid = txit->GetTx().GetWitnessHash();
6286+                                        m_txreconciliation->TryRemovingFromSet(pto->GetId(), wtxid);

naumenkogs commented at 8:32 am on October 28, 2024:

50c19dd21f6e437cd8e3d9047a89d793d097c5e5 could this be used to game collisions (for wtxid you have here)?

naumenkogs commented at 8:33 am on October 28, 2024:

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)

sr-gi commented at 3:28 pm on November 1, 2024:

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

naumenkogs commented at 9:08 am on November 4, 2024:

Right, please resolve this issue.

in src/net_processing.cpp:509 in 392facfce1 outdated

522@@ -523,7 +523,7 @@ class PeerManagerImpl final : public PeerManager
523     PeerManagerInfo GetInfo() const override EXCLUSIVE_LOCKS_REQUIRED(!m_peer_mutex);
524     void SendPings() override EXCLUSIVE_LOCKS_REQUIRED(!m_peer_mutex);
525     std::pair<size_t, size_t> GetFanoutPeersCount() override EXCLUSIVE_LOCKS_REQUIRED(!m_peer_mutex);
526-    void RelayTransaction(const uint256& txid, const uint256& wtxid) override EXCLUSIVE_LOCKS_REQUIRED(!m_peer_mutex);
527+    void RelayTransaction(const uint256& txid, const uint256& wtxid, bool force_relay) override EXCLUSIVE_LOCKS_REQUIRED(!m_peer_mutex);

naumenkogs commented at 8:37 am on October 28, 2024:

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)

sr-gi commented at 7:23 pm on November 14, 2024:

I misunderstood the use of ForceRelay here. Will amend it so it applied to both

in src/net_processing.cpp:2129 in 392facfce1 outdated

2369@@ -2370,8 +2370,8 @@ std::pair<size_t, size_t> PeerManagerImpl::GetFanoutPeersCount()
2370     if (m_txreconciliation) {
2371         LOCK(m_peer_mutex);
2372         for(const auto& [peer_id, peer] : m_peer_map) {
2373-            if (auto tx_relay = peer->GetTxRelay()) {
2374-                bool peer_relays_txs = WITH_LOCK(tx_relay->m_bloom_filter_mutex, return tx_relay->m_relay_txs);
2375+            if (const auto tx_relay = peer->GetTxRelay()) {

naumenkogs commented at 8:38 am on October 28, 2024:

392facfce1be6d0395abecc2e049ff39635bd1a5

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

sr-gi commented at 6:45 pm on October 30, 2024:

You’re right, should have been added to the previous commit. Will fix

in src/node/txreconciliation.h:158 in 392facfce1 outdated

138@@ -139,6 +139,12 @@ class TxReconciliationTracker
139      */
140     bool ShouldFanoutTo(const Wtxid& wtxid, NodeId peer_id,
141                         size_t inbounds_fanout_tx_relay, size_t outbounds_fanout_tx_relay);
142+
143+    /**
144+     * Returns a collections of node ids sorted by how many parents the peer has in its reconciliation set

naumenkogs commented at 8:43 am on October 28, 2024:

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 [… … …]”.

sr-gi commented at 6:26 pm on November 14, 2024:

I’ve reworked the docs for this

in src/net_processing.cpp:6220 in 392facfce1 outdated

6283@@ -6216,27 +6284,6 @@ bool PeerManagerImpl::SendMessages(CNode* pto)
6284                     // No reason to drain out at many times the network's capacity,
6285                     // especially since we have many peers and some will draw much shorter delays.
6286                     unsigned int nRelayedTransactions = 0;
6287-
6288-                    size_t inbounds_fanout_tx_relay = 0, outbounds_fanout_tx_relay = 0;

naumenkogs commented at 8:44 am on October 28, 2024:

392facfce1be6d0395abecc2e049ff39635bd1a5

why not modifying the former commit that introduces this code?

sr-gi commented at 7:31 pm on October 30, 2024:

Do you mean squashing these changes instead of having a “move” commit?

naumenkogs commented at 10:25 am on October 31, 2024:

yes

sr-gi commented at 2:30 pm on November 1, 2024:

Because it is doing more than just moving the code around, so I thought it may be easier for reviewers already familiar with the original approach to understand the changes. I wouldn’t mind squashing it once all the discussion around RelayTranaction is resolved

naumenkogs commented at 9:10 am on November 4, 2024:

My impression was that there are very-very few reviewers already familiar with the original approach at the moment, so it’s an extra burden for most to understand that former code you drop anyway. But yeah it’s ok. Perhaps a commit message saying it will be dropped will work.

sr-gi commented at 9:36 pm on November 4, 2024:

I’ll squash in the next force push

in src/net_processing.cpp:2188 in 392facfce1 outdated

2429+            // to reconcile, fanout the transaction an all its ancestors. We just add the parents here and leave fanout as true
2430+            auto it = std::find(fanout_with_ancestors.begin(), fanout_with_ancestors.end(), peer_id);
2431+            if (it != fanout_with_ancestors.end()) {
2432+                for (const auto wtxid: parents) {
2433+                    m_txreconciliation->TryRemovingFromSet(peer_id, wtxid);
2434+                    invs_to_send.push_back(wtxid);

naumenkogs commented at 8:54 am on October 28, 2024:

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?

naumenkogs commented at 10:17 am on October 31, 2024:

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.

sr-gi commented at 7:52 pm on November 14, 2024:

Not sure I follow how the first comment is an issue, but I do agree with the second. This needs to be conditional to TryRemovingFromSet succeeding.

in src/net_processing.cpp:2202 in 392facfce1 outdated

2442+        if (fanout) {
2443+            // We fanout if force relay is set, if the peer does not reconcile transactions, or if it does but it has been picked for fanout.
2444+            invs_to_send.push_back(peer->m_wtxid_relay ? wtxid : txid);
2445+        } else {
2446+            // Otherwise, we try to add the transaction to the peer's reconciliation set.
2447+            // If the transaction has in mempool descendants, we will fanout all the descendant

naumenkogs commented at 9:11 am on October 28, 2024:

392facfce1be6d0395abecc2e049ff39635bd1a5

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

sr-gi commented at 2:52 pm on November 1, 2024:

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

in src/net_processing.cpp:5833 in 20772c0778 outdated

6269@@ -6270,6 +6270,10 @@ bool PeerManagerImpl::SendMessages(CNode* pto)
6270 
6271                 // Determine transactions to relay
6272                 if (fSendTrickle) {
6273+                    if (m_txreconciliation && m_txreconciliation->IsPeerRegistered(pto->GetId())) {
6274+                        // Make transactions added to the reconciliation set during the last interval available
6275+                        m_txreconciliation->ReadyDelayedTransactions(pto->GetId());

naumenkogs commented at 9:19 am on October 28, 2024:

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

naumenkogs commented at 11:35 am on October 30, 2024:

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.

sr-gi commented at 3:07 pm on October 30, 2024:

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.

naumenkogs commented at 10:14 am on October 31, 2024:

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)

naumenkogs commented at 12:22 pm on November 1, 2024:

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.

in src/node/txreconciliation.cpp:213 in d2f2605072 outdated

132@@ -115,10 +133,66 @@ class TxReconciliationTracker::Impl
133                       peer_id, is_peer_inbound);
134 
135         const uint256 full_salt{ComputeSalt(local_salt, remote_salt)};
136-        recon_state->second = TxReconciliationState(!is_peer_inbound, full_salt.GetUint64(0), full_salt.GetUint64(1));
137+
138+        auto new_state = TxReconciliationState(!is_peer_inbound, full_salt.GetUint64(0), full_salt.GetUint64(1));;
139+        m_states.erase(recon_state);
140+        m_states.emplace(peer_id, std::move(new_state));

naumenkogs commented at 9:28 am on October 28, 2024:

d2f260507279b1edd6c0f55d02c7ae2e598b3585 nit: Assume(m_states.emplace(peer_id, std::move(new_state)).second);

sr-gi commented at 8:46 pm on November 14, 2024:

Done

in src/node/txreconciliation.cpp:325 in d2f2605072 outdated

180+        auto peer_state = GetRegisteredPeerState(peer_id);
181+        if (!peer_state) return false;
182+
183+        auto removed = peer_state->m_local_set.erase(wtxid) > 0;
184+        if (removed) {
185+            LogPrintLevel(BCLog::TXRECONCILIATION, BCLog::Level::Debug, "Removed %s from the reconciliation set for peer=%d. " /* Continued */

naumenkogs commented at 9:29 am on October 28, 2024:

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)

in src/net_processing.cpp:6211 in 873e8dd60b outdated

6206+                                // When we consider to which (and how many) Erlay peers
6207+                                // we should fanout a tx, we must know to how
6208+                                // many peers we would certainly announce this tx
6209+                                // (non-Erlay peers).
6210+                                if (peer_tx_relay->m_relay_txs && !m_txreconciliation->IsPeerRegistered(cur_peer_id)) {
6211+                                    inbounds_fanout_tx_relay += cur_peer->m_is_inbound;

naumenkogs commented at 9:31 am on October 28, 2024:

873e8dd60b93f740330e9b0fbae4b3200204653a

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

naumenkogs changes_requested

sr-gi force-pushed on Oct 28, 2024

sr-gi commented at 7:50 pm on October 28, 2024: member

Squashed @naumenkogs fix on @marcofleon comment in ad95b2c0e21f1e865f967aa9463ef99bc252550a, plus added a commit replacing IsFanoutTarget with GetFanoutTargets so the cache for fanout can be dropped. After this, the fanout targets are computed just once per transaction

sr-gi force-pushed on Oct 28, 2024

DrahtBot added the label CI failed on Oct 28, 2024

DrahtBot commented at 8:02 pm on October 28, 2024: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/32180649974

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

sr-gi force-pushed on Oct 28, 2024

DrahtBot removed the label CI failed on Oct 28, 2024

in src/node/txreconciliation.cpp:379 in 4234f5ebe1 outdated

393+        const double inbound_targets = (inbounds_fanout_tx_relay + m_inbounds_count) * INBOUND_FANOUT_DESTINATIONS_FRACTION;
394+        double n = std::max(inbound_targets - inbounds_fanout_tx_relay, 0.0);
395+
396+        // Being this a fraction, we need to round it either up or down. We do this deterministically at random based on the
397+        // transaction we are picking the peers for.
398+        CSipHasher deterministic_randomizer_in{m_deterministic_randomizer};

naumenkogs commented at 10:06 am on October 29, 2024:

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?

naumenkogs commented at 10:08 am on October 29, 2024:

Otherwise we can drop m_deterministic_randomizer altogether and use some cheap FastRandomContext instead.

sr-gi commented at 7:34 pm on October 29, 2024:

Well, this really depends. GetFanoutTargets is called by RelayTransaction, which, in turn, may be called by ProcessMessage for a peer that has NetPermissionFlags::ForceRelay. So if force relay is used for both fanout and set reconciliation, as suggested in #30116 (review), then this could be called twice leading to two different sorting if we don’t do so deterministically

naumenkogs commented at 9:15 am on October 30, 2024:

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?

in src/node/txreconciliation.cpp:374 in 4234f5ebe1 outdated

385+        LOCK(m_txreconciliation_mutex);
386 
387+        // We decide whether a particular peer is a low-fanout flood target differently based on its connection direction:
388+        // - for outbounds we have a fixed number of flood destinations.
389+        // - for inbounds we use a fraction of all inbound peers supporting tx relay.
390+        auto outbounds_target_size = (double)OUTBOUND_FANOUT_DESTINATIONS - outbounds_fanout_tx_relay;

naumenkogs commented at 10:17 am on October 29, 2024:

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.

naumenkogs commented at 10:27 am on October 29, 2024:

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));

naumenkogs commented at 10:30 am on October 29, 2024:

(technically the code you have is correct, it’s just confusing for no reason i think)

sr-gi commented at 9:06 pm on October 29, 2024:

I’ve added it to the initial commit and reworked it on the last one

in src/node/txreconciliation.cpp:420 in 4234f5ebe1 outdated

440+            for_each(sorted_outbounds.begin(), sorted_outbounds.end(),
441+                    [&out_fanout_targets](auto& keyed_peer) { out_fanout_targets.push_back(keyed_peer.second); });
442+            out_fanout_targets.resize(outbounds_target_size);
443+        }
444+
445+        return std::make_tuple(in_fanout_targets, out_fanout_targets);

naumenkogs commented at 10:33 am on October 29, 2024:

4234f5ebe133b949080aaa56da8cbdd18b650ff2

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

sr-gi commented at 7:38 pm on October 29, 2024:

Yeah, you’re right. Given how small the two vectors are, calling ShouldFanoutTo with a merged vector should not incur any major overhead, so merging will make it easier to read

DrahtBot added the label Needs rebase on Oct 29, 2024

sr-gi force-pushed on Oct 29, 2024

sr-gi force-pushed on Oct 30, 2024

sr-gi commented at 2:59 pm on October 30, 2024: member

Rebasing to deal with merge conflicts

DrahtBot removed the label Needs rebase on Oct 30, 2024

in src/node/txreconciliation.cpp:110 in ccd695851c outdated

106+        return m_local_set.size() + m_delayed_local_set.size();
107+    }
108+
109+    bool RemoveFromSet(const Wtxid& wtxid)
110+    {
111+        auto r = m_local_set.erase(wtxid) + m_delayed_local_set.erase(wtxid);

naumenkogs commented at 11:17 am on October 31, 2024:

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;

sr-gi commented at 8:27 pm on November 1, 2024:

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

naumenkogs commented at 10:08 am on November 4, 2024:

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.

sr-gi commented at 9:10 pm on November 13, 2024:

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?

naumenkogs commented at 7:33 am on November 14, 2024:

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.

sr-gi commented at 8:20 pm on November 14, 2024:

That is fair. I’ve updated it to make it more explicit (and readable)

in src/node/txreconciliation.cpp:436 in fd7c35a226 outdated

376@@ -376,6 +377,38 @@ class TxReconciliationTracker::Impl
377 
378         return IsFanoutTarget(wtxid, peer_id, peer_state->m_we_initiate, n);
379     }
380+
381+    std::vector<NodeId> SortPeersByFewestParents(std::vector<Wtxid> parents) EXCLUSIVE_LOCKS_REQUIRED(!m_txreconciliation_mutex)

naumenkogs commented at 9:49 am on November 1, 2024:

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).

sr-gi commented at 8:42 pm on November 1, 2024:

This is only called if there are in mempol parents though, the ordering doesn’t matter much otherwise

naumenkogs commented at 9:57 am on November 4, 2024:

There could be mempool parents, but none are in reconciliation sets (say, they were already reconciled). For all these cases, it would be nice to not choose the peer sitting first in m_states?

sr-gi commented at 9:51 pm on November 13, 2024:

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

naumenkogs commented at 7:12 am on November 14, 2024:

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.

sr-gi commented at 7:49 pm on November 14, 2024:

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)

sr-gi commented at 8:49 pm on November 14, 2024:

Mave the move dependant on TryRemovingFromSet

in src/net_processing.cpp:2217 in fd7c35a226 outdated

2212+                // we also remove and fanout the conflict and all its descendants.
2213+                // This is because our peer may have added the conflicting transaction
2214+                // to its set, in which reconciliation of these two would fail
2215+                if (const auto collision = result.m_conflict; collision.has_value()) {
2216+                    CTxMemPool::setEntries descendants;
2217+                    WITH_LOCK(m_mempool.cs, m_mempool.CalculateDescendants(m_mempool.get_iter_from_wtxid(collision.value()), descendants));

naumenkogs commented at 10:06 am on November 1, 2024:

Why having a collision means we should fanout the children? They may get reconciled in their own time.

sr-gi commented at 2:20 pm on November 1, 2024:

Because if you remove the parent from the reconciliation set but not the children, it could be the case that you reconcile with that peer before fanning out the parent, and all those children will be orphan

naumenkogs commented at 9:54 am on November 4, 2024:

Something worth documenting too :) Again, at least one place where we talk about handling dependencies.

sr-gi commented at 10:01 pm on November 13, 2024:

Done

refactor: remove legacy comments

These comments became irrelevant in one of the previous code changes.
They simply don't make sense anymore.

7e42a50631

sr-gi force-pushed on Nov 1, 2024

sr-gi commented at 8:44 pm on November 1, 2024: member

Rebased to make CI green, plus covered (and masked as resolved) some outstanding comments:

#30116 (review) #30116 (review) #30116 (review) #30116 (review) #30116 (review) #30116 (review)

sr-gi force-pushed on Nov 1, 2024

DrahtBot added the label CI failed on Nov 1, 2024

sr-gi force-pushed on Nov 1, 2024

DrahtBot removed the label CI failed on Nov 2, 2024

in src/node/txreconciliation.cpp:261 in e942f3a749 outdated

151+
152+        // Check if the reconciliation set is not at capacity for two reasons:
153+        // - limit sizes of reconciliation sets and short id mappings;
154+        // - limit CPU use for sketch computations.
155+        //
156+        // Since we reconcile frequently, reaching capacity either means:

naumenkogs commented at 9:16 am on November 4, 2024:

e942f3a7493908988eea08640d87b2ae420c5eef

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

sr-gi commented at 8:52 pm on November 14, 2024:

The whole thing from L151-L160?

in src/node/txreconciliation.cpp:257 in e942f3a749 outdated

147+        AssertLockNotHeld(m_txreconciliation_mutex);
148+        LOCK(m_txreconciliation_mutex);
149+        auto peer_state = GetRegisteredPeerState(peer_id);
150+        if (!peer_state) return false;
151+
152+        // Check if the reconciliation set is not at capacity for two reasons:

naumenkogs commented at 9:18 am on November 4, 2024:

e942f3a7493908988eea08640d87b2ae420c5eef

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

sr-gi commented at 8:53 pm on November 14, 2024:

I’m guessing this is related to #30116 (review), in which case I’ll drop that

in src/net_processing.cpp:5827 in 9005953037 outdated

5823+                            auto result = m_txreconciliation->AddToSet(pto->GetId(), wtxid);
5824+                            if (!result.m_succeeded) {
5825+                                vInv.push_back(inv);
5826+                                // If the transaction fails because it collides with an existing one,
5827+                                // we also remove and fanout the conflict and all its descendants.
5828+                                // This is because our peer may have added the conflicting tranaction

naumenkogs commented at 9:44 am on November 4, 2024:

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”.

sr-gi commented at 10:02 pm on November 13, 2024:

Done

in src/net_processing.cpp:5826 in 9005953037 outdated

5822+                            // If the transactions fails to get into the set, we fanout
5823+                            auto result = m_txreconciliation->AddToSet(pto->GetId(), wtxid);
5824+                            if (!result.m_succeeded) {
5825+                                vInv.push_back(inv);
5826+                                // If the transaction fails because it collides with an existing one,
5827+                                // we also remove and fanout the conflict and all its descendants.

naumenkogs commented at 9:45 am on November 4, 2024:

Let’s provide a hint why fanouting the descendants (or at least send a reader to where the dependency issue is explained better — we should have a one place explaining it)

sr-gi commented at 10:02 pm on November 13, 2024:

Done

in src/node/txreconciliation.cpp:62 in c790aa0e7e outdated

55@@ -56,6 +56,13 @@ class TxReconciliationState
56      */
57     uint64_t m_k0, m_k1;
58 
59+    /**
60+    * Set of transactions to be added to the reconciliation set on the next trickle. These are still unrequestable for
61+    * privacy reasons (to prevent transaction probing), transactions became available (moved to m_local_set) once they
62+    * would have been announced via fanout.

naumenkogs commented at 10:04 am on November 4, 2024:

c790aa0e7ebfcf0b03b4d0ef5fcc0ddfa4199943

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

in src/node/txreconciliation.cpp:279 in c790aa0e7e outdated

285+        if (peer_state->m_delayed_local_set.insert(wtxid).second) {
286             peer_state->m_short_id_mapping.emplace(short_id, wtxid);
287             LogPrintLevel(BCLog::TXRECONCILIATION, BCLog::Level::Debug, "Added %s to the reconciliation set for peer=%d. "
288                                                                         "Now the set contains %i transactions.\n",
289-                          wtxid.ToString(), peer_id, peer_state->m_local_set.size());
290+                          wtxid.ToString(), peer_id, set_size + 1);

naumenkogs commented at 10:12 am on November 4, 2024:

c790aa0e7ebfcf0b03b4d0ef5fcc0ddfa4199943 This is probably the most important log in the entire file, and I think it’s better to distinguish two set sizes here (preferably other places the size is logged too).

sr-gi commented at 9:16 pm on November 14, 2024:

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",

sr-gi commented at 9:22 pm on November 14, 2024:

I have also applied the same logic when removing

bitcoin deleted a comment on Nov 4, 2024

sr-gi force-pushed on Nov 13, 2024

in src/net_processing.cpp:2186 in ee46e21a5c outdated

2184+            // to reconcile, fanout the transaction an all its ancestors. We just add the parents here and leave fanout as true
2185+            auto it = std::find(fanout_with_ancestors.begin(), fanout_with_ancestors.end(), peer_id);
2186+            if (it != fanout_with_ancestors.end()) {
2187+                for (const auto wtxid: parents) {
2188+                    m_txreconciliation->TryRemovingFromSet(peer_id, wtxid);
2189+                    invs_to_send.push_back(wtxid);

naumenkogs commented at 7:16 am on November 14, 2024:

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).

sr-gi commented at 9:32 pm on November 14, 2024:

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

sr-gi force-pushed on Nov 14, 2024

p2p: Functions to add/remove wtxids to tx reconciliation sets

They will be used later on.

9667c89a7b

p2p: Make short id collision detectable when adding wtxids to tx reconciliation sets 784c458acb

p2p: Add PeerManager method to count the amount of inbound/outbounds fanout peers e1c33ff9b7

p2p: Adds a method to sort peers by fewest parent

When receiving a transaction that depends on an unconfirmed transactions, and needing to
decide what peer to fanout to, those with fewer parents already in the reconciliation set
will be prioritized

1dce9aedc5

p2p: Add transactions to reconciliation sets

Transactions eligible for reconciliation are added to the
reconciliation sets. For the remaining txs, low-fanout is used.

If a transaction to be reconciled has in mempool ancestors, we need to be consistent
with the way in which we announce this transaction (either by fanning out or reconciling
all the ancestor set). In order for Erlay to work best, a minimum amount of fanout is required.
Therefore, we cannot simply reconcile with everyone in this case either. Find the subset of peers
that have the least ancestors to be reconciled and send all of them via fanout

Co-authored-by:  Gleb Naumenko <naumenko.gs@gmail.com>

0092f70314

bench: add bench for ShouldFanoutTo a9195aef33

p2p: Cache inbound reconciling peers count

It helps to avoid recomputing every time we consider
a transaction for fanout/reconciliation.

Co-authored-by: Sergi Delgado Segura <sergi.delgado.s@gmail.com>

bbe837eb31

p2p: Add helper to compute reconciliation tx short ids and a cache of short ids to wtxids 88f6765523

p2p: Deal with shortid collisions for reconciliation sets

If a wtxid to be added to a peer's recon set has a shot id collisions (a previously
added wtxid maps to the same short id), both transaction should be fanout, given
our peer may have added the opposite transaction to our recon set, and reconciliation
will fail. Moreover, all descendants of the previously added transaction that were in
the recon set should also be removed and fanout.

5996d47343

p2p: Makes transactions available for reconciliation on trickle

Splits the reconciliation set in two, a delayed set and an available set.
Transactions are added to the delayed set and made available when on the next
trickle interval for the peer. This prevents adversarial nodes from proving
our reconciliation set by spamming reconciliation requests, in an equivalent
manner to how fanout delays work

840a4e14f2

p2p: Replaces IsFanoutTarget with GetFanoutTargets in TxReconciliationTracker

Instead of checking if a target is fanout for every single node and having to store already
computed values in a cache, we can simply return the lists of fanout targets for both inbounds and outbounds
and just check for membership for each peer (depending on its type)

fc06786f32

sr-gi force-pushed on Nov 14, 2024

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

Code Coverage & Benchmarks

Reviews

Conflicts