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

The differences can be easily checked via git range-diff a14dfd9c873d1e196252c77ad7a8b32bd21b6f6d...2e0b6742b82e60ea685afd25f2d19b8b558678ce

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

For detailed information about the code coverage, see the test coverage report.

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:

#30385 ([WIP] p2p: send not_found msgs for unknown, pruned or unwilling to share blocks by furszy)
#30277 ([DO NOT MERGE] Erlay: bandwidth-efficient transaction relay protocol (Full implementation) by sr-gi)
#30111 (locks: introduce mutex for tx download, flush rejection filters on UpdatedBlockTip by glozow)
#29625 (Several randomness improvements by sipa)
#29415 (Broadcast own transactions only via short-lived Tor or I2P connections by vasild)
#27052 (test: rpc: add last block announcement time to getpeerinfo result by LarryRuane)

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:120 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:467 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:2343 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.

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

refactor: move m_is_inbound out of CNodeState

`m_is_inbound` cannot be changed throughout the life of a `Peer`. However, we
are currently storing it in `CNodeState`, which requires locking `cs_main` in
order to access it. This can be moved to the outside scope and only require
`m_peer_mutex`.

This is a refactor in preparation for Erlay reworks.

ee46cf4ffe

refactor: remove legacy comments

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

a0b6bfb85b

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

They will be used later on.

ff3b2efbed

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

p2p: Add transactions to reconciliation sets

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

Co-authored-by: Martin Zumsande <mzumsande@gmail.com>
Co-authored-by: Pieter Wuille <pieter.wuille@gmail.com>

ef41fcc34d

bench: add bench for ShouldFanoutTo 4e57be54e2

p2p: Cache fanout candidates to optimize txreconciliation

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

2184b207cf

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>

b7ec71c014

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

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.

b5a575cbd4

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

p2p: Moves fanout logic to RelayTransaction and properly fanouts ancestors

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

2e0b6742b8

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

DrahtBot commented at 11:16 am on July 4, 2024: contributor

🐙 This pull request conflicts with the target branch and needs rebase.

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

Code Coverage

Reviews

Conflicts