[p2p] Introduce node rebroadcast module #21061

pull amitiuttarwar wants to merge 21 commits into bitcoin:master from amitiuttarwar:2021-01-the-realest-rebroadcast changing 23 files +947 −37
  1. amitiuttarwar commented at 1:28 am on February 2, 2021: contributor

    Status

    (this section will be updated as the PR progresses, and eventually removed)

    • I’m reworking some of the approach, will mark ready for review once that is done.

    Motivation:

    Our legacy rebroadcast mechanism lives in the wallet code. It rebroadcasts only & all transactions which are “mine”, not discerning if the fee rate indicates the transaction should actually have been confirmed by now. This is bad for privacy because it leaks information that allows spy nodes to link bitcoin addresses with IP addresses, a relationship we aim to obfuscate.

    PR Overview:

    This PR introduces a rebroadcast mechanism in the node. Instead of only rebroadcasting our own transactions, we will notify the network about any transactions we identified as missing from blocks based on fee rate expectations in our own mempool.

    The new module is currently behind a configuration flag that defaults to off.

    The end goal is to enable node rebroadcast by default, and remove wallet rebroadcast. This would improve privacy for a few main reasons:

    1. We would no longer eagerly rebroadcast all of our wallet transactions regardless of fee-rate. We add logic to rebroadcast the ones which have a competitive rate according to the current blocks being mined.
    2. If a spy observes a bitcoin core node rebroadcasting a transaction, it would no longer know that the node has wallet enabled.
    3. If a spy observed a bitcoin core node rebroadcasting a transaction, it would no longer be able to deduce with high confidence that the associated wallet is participating in that transaction.

    Approach:

    Conceptually, we want to rebroadcast transactions that we believe “should” have been mined by now. Since we expect miners to prioritize transactions with the highest package fee rates, we select high fee rate transactions that have been in our mempool for some time, but have not yet been mined.

    This PR introduces a txrebroadcast module that encapsulates the selection logic. When PeerManager gets notified that we have received and processed a block, we trigger the rebroadcast logic. The module calculates the highest fee rate mempool packages that meet some additional conditions- the transaction must be > 30 minutes old, and surpass a fee threshold. This threshold is calculated by periodically (every minute) identifying the top block of transactions in our mempool, and caching the fee rate for a package to be included. We eliminate any of these candidates that we have rebroadcasted recently (last 4 hours), or already rebroadcast more than a maximum amount of times (6). We store any remaining candidates on each peer’s setInventoryTxToSend, which they will potentially relay next time we hit SendMessages for that peer (subject to general transaction relay conditions).

  2. fanquake added the label P2P on Feb 2, 2021
  3. amitiuttarwar commented at 7:23 am on February 2, 2021: contributor

    Future work

    to be addressed either in this PR or a follow up:

    • persist rebroadcast attempt tracker to disk
    • remove wallet dependency for p2p_rebroadcast.py

    Merge Plan & Next Steps:

    All of the functionality in this PR is hidden behind a configuration switch that defaults to off, and the wallet rebroadcast logic is currently untouched. The idea is to make these changes as safe as possible to merge into master, and allow reviewers to easily enable and observe the new rebroadcast mechanism in today’s network conditions.

    If we build confidence that these changes are safe and desirable, we can default enable this new node rebroadcast logic and disable the legacy wallet rebroadcast logic. This is the desired end goal.

    Project History:

    A version of these changes were originally proposed in #16698.

    #18038 broke out a subset of the functionality, enabling the node to provide a guarantee around minimal initial broadcast & reducing the frequency of the existing wallet rebroadcast functionality (unbroadcast set)

    Since #16698, there have been some changes in approach, and all of the unbroadcast conversation is no longer relevant. So, to help with review, I’ve decided to open a new PR. To preserve the relevant feedback and concerns, I’ve tried my best to capture the history of conversations in the following write-up: https://github.com/amitiuttarwar/bitcoin-notes/blob/main/rebroadcast-history.md. warning: it goes quite in depth.

    🙌🏽 Huge shout out to the village of core contributors who have provided feedback & guidance on this project so far. Honestly too many to name, but this project is much better for it. Thank you :)

  4. DrahtBot commented at 8:05 am on February 2, 2021: member

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

    Conflicts

    Reviewers, this pull request conflicts with the following ones:

    • #21866 ([Bundle 7/7] validation: Farewell, global Chainstate! by dongcarl)
    • #21789 (refactor: Remove ::Params() global from CChainState by MarcoFalke)
    • #21562 ([net processing] Various tidying up of PeerManagerImpl ctor by jnewbery)
    • #21526 (validation: UpdateTip/CheckBlockIndex assumeutxo support by jamesob)
    • #17580 (refactor: Add ALLOW_LIST flags and enforce usage in CheckArgFlags by ryanofsky)

    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.

  5. amitiuttarwar force-pushed on Feb 2, 2021
  6. amitiuttarwar marked this as a draft on Feb 3, 2021
  7. amitiuttarwar commented at 3:32 am on February 3, 2021: contributor
    marking as draft until I resolve CI issues
  8. amitiuttarwar force-pushed on Feb 4, 2021
  9. amitiuttarwar force-pushed on Feb 7, 2021
  10. in test/lint/lint-includes.sh:60 in 3766479d79 outdated
    56@@ -57,6 +57,7 @@ EXPECTED_BOOST_INCLUDES=(
    57     boost/filesystem.hpp
    58     boost/filesystem/fstream.hpp
    59     boost/multi_index/hashed_index.hpp
    60+    boost/multi_index/member.hpp
    


    amitiuttarwar commented at 5:44 pm on February 8, 2021:

    I’m importing this file so I can use the default key extractors in the indexed_rebroadcast_set multi_index: 1. https://github.com/bitcoin/bitcoin/pull/21061/files#diff-eccf6b88ae8b612dbdbdb92c110b66e4e7e3ffa665ccdc1acf08093aadc66b82R49 2. https://github.com/bitcoin/bitcoin/pull/21061/files#diff-eccf6b88ae8b612dbdbdb92c110b66e4e7e3ffa665ccdc1acf08093aadc66b82R55

    The contents of the boost header file can be found here.

    If we’d rather not import another boost header, I can avoid by writing custom key extractors.


    laanwj commented at 6:58 am on February 11, 2021:
    I think it’s fine to add a boost multi_index header dependency, it’s the only submodule of boost that we really need and for which there is no replacement on the horizon. So just use what you need IMO, re-implementing anything from multi-index without a good plan would be a waste of time, I think.
  11. amitiuttarwar marked this as ready for review on Feb 8, 2021
  12. amitiuttarwar force-pushed on Feb 9, 2021
  13. amitiuttarwar force-pushed on Feb 9, 2021
  14. amitiuttarwar force-pushed on Feb 9, 2021
  15. amitiuttarwar commented at 2:44 am on February 10, 2021: contributor

    rebased master, added a functional test, some small fixups.

    this PR is ready for review! 🎈

  16. amitiuttarwar force-pushed on Feb 12, 2021
  17. DrahtBot added the label Needs rebase on Feb 16, 2021
  18. amitiuttarwar commented at 8:27 pm on February 16, 2021: contributor
    rebased
  19. amitiuttarwar force-pushed on Feb 16, 2021
  20. DrahtBot removed the label Needs rebase on Feb 16, 2021
  21. MarcoFalke referenced this in commit 569b5ba1dc on Feb 17, 2021
  22. sidhujag referenced this in commit 3d9605586b on Feb 17, 2021
  23. amitiuttarwar force-pushed on Feb 17, 2021
  24. amitiuttarwar commented at 11:29 pm on February 17, 2021: contributor
    rebased to include #21121
  25. laanwj added this to the "Blockers" column in a project

  26. casey commented at 0:52 am on February 28, 2021: contributor

    This seems like a big win, both for privacy and for quality of service. There are a lot of nodes out there with larger-than-default mempools, and if this were the default, they would serve as reservoirs for transactions that were dropped from the default mempool, eventually rebroadcasting them when they noticed that they had a chance of getting confirmed. This would save users from sometimes having to manually intervene to unstick stuck transactions.

    It might be a good idea to log whenever this logic kicks in and rebroadcast transactions. Perhaps just the number of transactions that it’s rebroadcasting, i.e. Rebroadcasting 23 transactions, and maybe also the individual transaction IDs.

    I’d like to run this code on mainnet, and having logging statements would be very helpful for tracking how it actually behaves.

  27. fanquake deleted a comment on Feb 28, 2021
  28. amitiuttarwar commented at 10:17 pm on February 28, 2021: contributor

    @casey thanks for taking a look!

    The current code does have some logging, the most relevant statement firing here: https://github.com/bitcoin/bitcoin/pull/21061/files?file-filters%5B%5D=.cpp&file-filters%5B%5D=.h&file-filters%5B%5D=.py&file-filters%5B%5D=.sh#diff-7dff50848db96bdb8edffc4d21daeca6d9050ec0e67d96072780ea5751e7df06R90. This prints the transactions hashes where a rebroadcast will be attempted for all peers. Those candidates will go through additional per-peer filters (see SendMessages code that copies setInventoryTxToSend and filterInventoryKnown), so might not actually make it to every peer, but should be sufficient signal for us to monitor the frequency of rebroadcast.

    I’ve also added logs to monitor how long it takes to calculate rebroadcast blocks. The logs are all in the NET & BENCH categories. I’m currently running a node with this patch, but I’d love to gather more data so It’d be helpful if you are willing to run the patch and share your findings.

    So far, I ran a node for 1 week with default mempool settings & 0 transactions were selected for rebroadcast. That seems reasonable. I’m now running a node with a larger mempool, and also want to tinker with making low fee rate wallet transactions to monitor node rebroadcast logic.

    If you’ve intended to request more logging than what’s currently there, I’m open to suggestions.

  29. casey commented at 6:09 am on March 1, 2021: contributor

    The current code does have some logging, the most relevant statement firing here:

    Ah, excellent! I was looking where the transactions are actually rebroadcast, so I missed that. What’s there looks good, I can’t think of anything else I’d want.

    …but I’d love to gather more data so It’d be helpful if you are willing to run the patch and share your findings.

    I was thinking about running a node with a very large max mempool size, as well as no mempool expiration time, to try to maximize transaction rebroadcasting. (Those are the only two settings I can think of that would affect this, but let me know if you can think of others.) I’ll definitely share the logs if I wind up doing this!

  30. amitiuttarwar commented at 5:15 am on March 2, 2021: contributor

    @casey

    I was thinking about running a node with a very large max mempool size, as well as no mempool expiration time, to try to maximize transaction rebroadcasting

    yup, that’s exactly what I did, I also minimized the feefilter and minrelaytxfee to ensure I’d get all the transactions.

    I’ll definitely share the logs if I wind up doing this!

    sounds good, thanks :)

  31. DrahtBot added the label Needs rebase on Mar 4, 2021
  32. amitiuttarwar force-pushed on Mar 4, 2021
  33. amitiuttarwar commented at 10:27 pm on March 4, 2021: contributor
    Rebased
  34. DrahtBot removed the label Needs rebase on Mar 4, 2021
  35. DrahtBot added the label Needs rebase on Mar 11, 2021
  36. amitiuttarwar force-pushed on Mar 11, 2021
  37. amitiuttarwar commented at 11:34 pm on March 11, 2021: contributor
    Rebased
  38. ghost commented at 0:45 am on March 12, 2021: none

    Motivation and PR overview looks interesting. Couldn’t compile though. Maybe I should have checked CI results.

    image

  39. DrahtBot removed the label Needs rebase on Mar 12, 2021
  40. amitiuttarwar force-pushed on Mar 12, 2021
  41. amitiuttarwar commented at 6:39 pm on March 12, 2021: contributor
    @prayank23 Thanks for taking a look. I missed the tests in a recent rebase. It should be fixed now
  42. ghost commented at 0:58 am on March 13, 2021: none

    Concept ACK. Have few questions about the approach and will mention them below. Compiled successfully on Ubuntu. Tests passed.

    Conceptually, we want to rebroadcast transactions that we believe “should” have been mined by now.

    Not sure about this part. Can we randomly rebroadcast different transactions to make it difficult for spy nodes to notice any pattern?

    I used below bitcoin.conf:

    0testnet=1
    1rebroadcast=1
    2debug=1
    

    Had 1 incoming and 1 outgoing transaction pending associated with my wallet (segwit,rbf,1sat/vB). Node was connected to 10 peers.

    image

    Still trying to understand if I can find something relevant in logs. Only one line related to rebroadcast:

    2021-03-13T00:34:03Z Caching minimum fee for rebroadcast to 1.000 sat/vB, took 122 µs to calculate.

    After we process a block, invoke the rebroadcast module to identify if there are any transactions we would have expected to be included, and queue them up for relay to our peers.

    Maybe it couldn’t find any transactions that should be rebroadcasted based on fee rate and other things.

    In order to prevent spam, we need to carefully select which transactions to rebroadcast. As of this commit, we select the transactions in the mempool that have the highest feerate.

    Can you explain the SPAM part mentioned in https://github.com/bitcoin/bitcoin/pull/21061/commits/b86f6d90a844dd71008f7c8a5fb92a1ac8673891?

    Checked unit tests and functional test included in this PR. It would be helpful if you can suggest more ways to experiment with rebroadcast and check different things?

  43. in src/txrebroadcast.cpp:24 in 24e7415aeb outdated
    12 /** We rebroadcast 3/4 of max block weight to reduce noise due to circumstances
    13  *  such as miners mining priority transactions. */
    14 static constexpr unsigned int MAX_REBROADCAST_WEIGHT = 3 * MAX_BLOCK_WEIGHT / 4;
    15 
    16+/** Default minimum age for a transaction to be rebroadcast */
    17+static constexpr std::chrono::minutes REBROADCAST_MIN_TX_AGE = 30min;
    


    unknown commented at 10:03 pm on March 14, 2021:
    Any reasons for 30 minutes? Less than 30 minutes might have issues. What if we use more than 30 minutes or user can define this in bitcoin.conf?

    amitiuttarwar commented at 3:40 am on April 13, 2021:
    30 minutes was chosen as the minimum age to ensure that transactions would have ample time to propagate through mempools. I don’t think it makes sense for this to be a configurable value, both because of what sipa highlighted here: #21061 (comment), as well as the fact that it would increase the complexity of reasoning about & maintenance burden. However, that said, I don’t think of this value (30min) as set in stone- through the review process & running the patch, we should identify if this value is appropriate. Another thing to keep in mind is that any rebroadcast candidates will have to pass through filterInventoryKnown for an inv to be sent to the peer.
  44. in src/txrebroadcast.h:35 in 038f751e9c outdated
    30+          m_wtxid(wtxid),
    31+          m_count(1) {}
    32+
    33+    std::chrono::microseconds m_last_attempt;
    34+    const uint256 m_wtxid;
    35+    int m_count;
    


    jnewbery commented at 8:27 pm on March 15, 2021:

    Prefer default initialization when a member will always be initialized to the same value.

    0    int m_count{1};
    

    And remove m_count from the initializer list.


    amitiuttarwar commented at 11:28 pm on April 7, 2021:
    done
  45. in src/txrebroadcast.h:9 in 038f751e9c outdated
    0@@ -0,0 +1,95 @@
    1+// Copyright (c) 2021 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+#ifndef BITCOIN_TXREBROADCAST_H
    6+#define BITCOIN_TXREBROADCAST_H
    7+
    8+#include <policy/feerate.h>
    9+#include <tuple>
    


    jnewbery commented at 8:28 pm on March 15, 2021:
    I think this is unused.

    amitiuttarwar commented at 11:28 pm on April 7, 2021:
    removed
  46. in src/txrebroadcast.h:16 in 038f751e9c outdated
    15+#include <boost/multi_index/hashed_index.hpp>
    16+#include <boost/multi_index/member.hpp>
    17+#include <boost/multi_index/ordered_index.hpp>
    18+#include <boost/multi_index_container.hpp>
    19+
    20+struct TxIds {
    


    jnewbery commented at 8:38 pm on March 15, 2021:

    It seems unnecessary to define a type here. GetRebroadcastTransactions() could just return a vector of std::pairs, and the one caller (UpdatedBlockTip()) can unpack that vector of pairs using :sparkle: s t r u c t u t e d :sparkle: b i n d i n g s :sparkle:. Here’s what the caller would look like:

     0diff --git a/src/net_processing.cpp b/src/net_processing.cpp
     1index 7811e3ca40..e5a425b4c1 100644
     2--- a/src/net_processing.cpp
     3+++ b/src/net_processing.cpp
     4@@ -1393,12 +1393,12 @@ void PeerManagerImpl::UpdatedBlockTip(const CBlockIndex *pindexNew, const CBlock
     5 
     6     // Rebroadcast selected mempool transactions
     7     if (gArgs.GetArg("-rebroadcast", DEFAULT_REBROADCAST_ENABLED)) {
     8-        std::vector<TxIds> rebroadcast_txs = m_txrebroadcast.GetRebroadcastTransactions();
     9+        auto rebroadcast_txs = m_txrebroadcast.GetRebroadcastTransactions();
    10 
    11         LOCK(cs_main);
    12 
    13-        for (auto ids : rebroadcast_txs) {
    14-            RelayTransaction(ids.m_txid, ids.m_wtxid, m_connman);
    15+        for (auto [txid, wtxid] : rebroadcast_txs) {
    16+            RelayTransaction(txid, wtxid, m_connman);
    17         }
    18     }
    

    That client code works whether you return a vector of TxIds or a vector of std::pair<uint256, uint256>>s (which is as it should be :slightly_smiling_face: )


    amitiuttarwar commented at 11:31 pm on April 7, 2021:
    yeah, I considered this approach but I went for an explicitly defined structure because its easy to mix up txid & wtxid, and doing so would cause quiet failures. It feels harder for a call site to accidentally mixup with the named access.

    jnewbery commented at 9:54 am on May 7, 2021:
    That’s fair. Marking this as resolved.
  47. in src/net_processing.cpp:329 in 038f751e9c outdated
    325@@ -325,6 +326,7 @@ class PeerManagerImpl final : public PeerManager
    326     ChainstateManager& m_chainman;
    327     CTxMemPool& m_mempool;
    328     TxRequestTracker m_txrequest GUARDED_BY(::cs_main);
    329+    TxRebroadcastHandler m_txrebroadcast;
    


    jnewbery commented at 8:44 pm on March 15, 2021:

    Perhaps make this a unique_ptr, and then pass in a boolean to the PeerManagerImpl ctor to indicate whether you want to enable tx rebroadcast and initialize the pointer.

    Then, in UpdatedBlockTip:

     0diff --git a/src/net_processing.cpp b/src/net_processing.cpp
     1index 7811e3ca40..8bb5e8f87f 100644
     2--- a/src/net_processing.cpp
     3+++ b/src/net_processing.cpp
     4@@ -1392,8 +1392,8 @@ void PeerManagerImpl::UpdatedBlockTip(const CBlockIndex *pindexNew, const CBlock
     5     }
     6 
     7     // Rebroadcast selected mempool transactions
     8-    if (gArgs.GetArg("-rebroadcast", DEFAULT_REBROADCAST_ENABLED)) {
     9-        std::vector<TxIds> rebroadcast_txs = m_txrebroadcast.GetRebroadcastTransactions();
    10+    if (m_txrebroadcast) {
    11+        std::vector<TxIds> rebroadcast_txs = m_txrebroadcast->GetRebroadcastTransactions();
    12 
    13         LOCK(cs_main);
    

    parametrizing whether the TxRebroadcastHandler is initialized avoids having to read the global args every block, and should make it the code path more obviously isolated and testable.


    amitiuttarwar commented at 11:31 pm on April 7, 2021:
    great idea! done
  48. in src/miner.cpp:57 in 038f751e9c outdated
    52@@ -53,6 +53,8 @@ void RegenerateCommitments(CBlock& block, BlockManager& blockman)
    53 BlockAssembler::Options::Options() {
    54     blockMinFeeRate = CFeeRate(DEFAULT_BLOCK_MIN_TX_FEE);
    55     nBlockMaxWeight = DEFAULT_BLOCK_MAX_WEIGHT;
    56+    m_skip_inclusion_until = std::chrono::microseconds::max();
    57+    check_block_validity = true;
    


    jnewbery commented at 8:46 pm on March 15, 2021:
    Prefer default initialization in the declaration, rather than setting these in the ctor.
  49. in src/miner.cpp:85 in 038f751e9c outdated
    79@@ -76,6 +80,9 @@ static BlockAssembler::Options DefaultOptions()
    80     } else {
    81         options.blockMinFeeRate = CFeeRate(DEFAULT_BLOCK_MIN_TX_FEE);
    82     }
    83+
    84+    options.m_skip_inclusion_until = std::chrono::microseconds::max();
    85+    options.check_block_validity = true;
    


    jnewbery commented at 8:48 pm on March 15, 2021:
    These aren’t doing anything. They already get set in the Options constructor.

    amitiuttarwar commented at 11:35 pm on April 7, 2021:
    good point, removed
  50. in src/test/txrebroadcast_tests.cpp:17 in 038f751e9c outdated
    12+#include <rpc/util.h>
    13+#include <script/interpreter.h>
    14+#include <script/script.h>
    15+#include <streams.h>
    16+#include <test/util/setup_common.h>
    17+#include <tuple>
    


    jnewbery commented at 8:49 pm on March 15, 2021:
    not needed!

    amitiuttarwar commented at 11:36 pm on April 7, 2021:
    removed
  51. in src/test/txrebroadcast_tests.cpp:6 in 038f751e9c outdated
    0@@ -0,0 +1,193 @@
    1+// Copyright (c) 2011-2021 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 <amount.h>
    6+#include <boost/test/unit_test.hpp>
    


    jnewbery commented at 8:50 pm on March 15, 2021:

    Separate library imports from local project imports:

    0#include <boost/test/unit_test.hpp>
    1
    2#include <amount.h>
    

    amitiuttarwar commented at 11:40 pm on April 7, 2021:
    I separated them, but I have boost after internal. Is that ok? Btw, I don’t see anything in the style guide about this, maybe we should add?

    jnewbery commented at 10:37 am on April 13, 2021:

    Yes, that’s the right way to do it.

    I don’t think we have any guidance in the style guide, but general best practice seems to be to go from small to large: https://stackoverflow.com/a/2762596/933705.

  52. in src/txrebroadcast.h:18 in 038f751e9c outdated
    13+#include <validation.h>
    14+
    15+#include <boost/multi_index/hashed_index.hpp>
    16+#include <boost/multi_index/member.hpp>
    17+#include <boost/multi_index/ordered_index.hpp>
    18+#include <boost/multi_index_container.hpp>
    


    jnewbery commented at 8:55 pm on March 15, 2021:
    It’d be really nice to avoid including these boost headers in a header that will transitively be included in a lot of translation units. Could you hide the indexed_rebroadcast_set inside the .cpp file to avoid this?

    jnewbery commented at 10:20 am on March 16, 2021:

    A quick and easy way to do this is to make indexed_rebroadcast_set a class that inherits from the boost::multi_index_container template class (defined in .cpp), forward declare it in .h and make m_attempt_tracker a unique pointer to indexed_rebroadcast_set. A few other things need to be shuffled around to make that work, but here’s a rough implementation:

      0diff --git a/src/test/txrebroadcast_tests.cpp b/src/test/txrebroadcast_tests.cpp
      1index 6fdd5deb8f..d10a962ab3 100644
      2--- a/src/test/txrebroadcast_tests.cpp
      3+++ b/src/test/txrebroadcast_tests.cpp
      4@@ -27,34 +27,13 @@ public:
      5 
      6     bool CheckRecordedAttempt(uint256 txhsh, int expected_count, std::chrono::microseconds expected_timestamp)
      7     {
      8-        const auto it = m_attempt_tracker.find(txhsh);
      9-        if (it == m_attempt_tracker.end()) return false;
     10-        if (it->m_count != expected_count) return false;
     11-
     12-        // Check the recorded timestamp is within 2 seconds of the param passed in
     13-        std::chrono::microseconds delta = expected_timestamp - it->m_last_attempt;
     14-        if (delta.count() > 2) return false;
     15-
     16-        return true;
     17-    };
     18+        return TxRebroadcastHandler::CheckRecordedAttempt(txhsh, expected_count, expected_timestamp);
     19+    }
     20 
     21     void UpdateAttempt(uint256 txhsh, int count)
     22     {
     23-        auto it = m_attempt_tracker.find(txhsh);
     24-        for (int i = 0; i < count; ++i) {
     25-            RecordAttempt(it);
     26-        }
     27-    };
     28-
     29-    void RecordAttempt(indexed_rebroadcast_set::index<index_by_wtxid>::type::iterator& entry_it)
     30-    {
     31-        auto UpdateRebroadcastEntry = [](RebroadcastEntry& rebroadcast_entry) {
     32-            rebroadcast_entry.m_last_attempt = GetTime<std::chrono::microseconds>() - 4h;
     33-            ++rebroadcast_entry.m_count;
     34-        };
     35-
     36-        m_attempt_tracker.modify(entry_it, UpdateRebroadcastEntry);
     37-    };
     38+        TxRebroadcastHandler::UpdateAttempt(txhsh, count);
     39+    }
     40 
     41     void UpdateCachedFeeRate(CFeeRate new_fee_rate)
     42     {
     43diff --git a/src/txrebroadcast.cpp b/src/txrebroadcast.cpp
     44index 3cb9abaf69..49050c0d39 100644
     45--- a/src/txrebroadcast.cpp
     46+++ b/src/txrebroadcast.cpp
     47@@ -10,6 +10,11 @@
     48 #include <txrebroadcast.h>
     49 #include <validation.h>
     50 
     51+#include <boost/multi_index/hashed_index.hpp>
     52+#include <boost/multi_index/member.hpp>
     53+#include <boost/multi_index/ordered_index.hpp>
     54+#include <boost/multi_index_container.hpp>
     55+
     56 /** We rebroadcast 3/4 of max block weight to reduce noise due to circumstances
     57  *  such as miners mining priority transactions. */
     58 static constexpr unsigned int MAX_REBROADCAST_WEIGHT = 3 * MAX_BLOCK_WEIGHT / 4;
     59@@ -30,6 +35,46 @@ static constexpr int MAX_ENTRIES = 500;
     60 /** The maximum age of an entry ~3 months */
     61 static constexpr std::chrono::hours MAX_ENTRY_AGE = std::chrono::hours(3 * 30 * 24);
     62 
     63+/** Used for multi_index tag  */
     64+struct index_by_last_attempt {};
     65+
     66+struct RebroadcastEntry {
     67+    RebroadcastEntry(std::chrono::microseconds now_time, uint256 wtxid)
     68+        : m_last_attempt(now_time),
     69+          m_wtxid(wtxid),
     70+          m_count(1) {}
     71+
     72+    std::chrono::microseconds m_last_attempt;
     73+    const uint256 m_wtxid;
     74+    int m_count;
     75+};
     76+
     77+class indexed_rebroadcast_set : public
     78+boost::multi_index_container<
     79+    RebroadcastEntry,
     80+    boost::multi_index::indexed_by<
     81+        // sorted by wtxid
     82+        boost::multi_index::hashed_unique<
     83+            boost::multi_index::tag<index_by_wtxid>,
     84+            boost::multi_index::member<RebroadcastEntry, const uint256, &RebroadcastEntry::m_wtxid>,
     85+            SaltedTxidHasher
     86+        >,
     87+        // sorted by last rebroadcast time
     88+        boost::multi_index::ordered_non_unique<
     89+            boost::multi_index::tag<index_by_last_attempt>,
     90+            boost::multi_index::member<RebroadcastEntry, std::chrono::microseconds, &RebroadcastEntry::m_last_attempt>
     91+        >
     92+    >
     93+> {};
     94+
     95+TxRebroadcastHandler::TxRebroadcastHandler(CTxMemPool& mempool, ChainstateManager& chainman)
     96+    : m_attempt_tracker{std::make_unique<indexed_rebroadcast_set>()}
     97+    , m_mempool{mempool}
     98+    , m_chainman{chainman}
     99+{}
    100+
    101+TxRebroadcastHandler::~TxRebroadcastHandler() = default;
    102+
    103 std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
    104 {
    105     std::vector<TxIds> rebroadcast_txs;
    106@@ -58,12 +103,12 @@ std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
    107 
    108         // Check if we have previously rebroadcasted, decide if we will this
    109         // round, and if so, record the attempt.
    110-        auto entry_it = m_attempt_tracker.find(wtxid);
    111+        auto entry_it = m_attempt_tracker->find(wtxid);
    112 
    113-        if (entry_it == m_attempt_tracker.end()) {
    114+        if (entry_it == m_attempt_tracker->end()) {
    115             // No existing entry, we will rebroadcast, so create a new one
    116             RebroadcastEntry entry(start_time, wtxid);
    117-            m_attempt_tracker.insert(entry);
    118+            m_attempt_tracker->insert(entry);
    119         } else if (entry_it->m_count >= MAX_REBROADCAST_COUNT) {
    120             // We have already rebroadcast this transaction the maximum number
    121             // of times permitted, so skip rebroadcasting.
    122@@ -76,7 +121,12 @@ std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
    123         } else {
    124             // We have rebroadcasted this transaction before, but will try
    125             // again now.
    126-            RecordAttempt(entry_it);
    127+            auto UpdateRebroadcastEntry = [](RebroadcastEntry& rebroadcast_entry) {
    128+                rebroadcast_entry.m_last_attempt = GetTime<std::chrono::microseconds>();
    129+                ++rebroadcast_entry.m_count;
    130+            };
    131+
    132+            m_attempt_tracker->modify(entry_it, UpdateRebroadcastEntry);
    133         }
    134 
    135         // Add to set of rebroadcast candidates
    136@@ -97,6 +147,32 @@ std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
    137     return rebroadcast_txs;
    138 };
    139 
    140+void TxRebroadcastHandler::UpdateAttempt(uint256 txhsh, int count)
    141+{
    142+    auto it = m_attempt_tracker->find(txhsh);
    143+    for (int i = 0; i < count; ++i) {
    144+        auto UpdateRebroadcastEntry = [](RebroadcastEntry& rebroadcast_entry) {
    145+            rebroadcast_entry.m_last_attempt = GetTime<std::chrono::microseconds>() - 4h;
    146+            ++rebroadcast_entry.m_count;
    147+        };
    148+
    149+        m_attempt_tracker->modify(it, UpdateRebroadcastEntry);
    150+    }
    151+};
    152+
    153+bool TxRebroadcastHandler::CheckRecordedAttempt(uint256 txhsh, int expected_count, std::chrono::microseconds expected_timestamp)
    154+{
    155+    const auto it = m_attempt_tracker->find(txhsh);
    156+    if (it == m_attempt_tracker->end()) return false;
    157+    if (it->m_count != expected_count) return false;
    158+
    159+    // Check the recorded timestamp is within 2 seconds of the param passed in
    160+    std::chrono::microseconds delta = expected_timestamp - it->m_last_attempt;
    161+    if (delta.count() > 2) return false;
    162+
    163+    return true;
    164+};
    165+
    166 void TxRebroadcastHandler::CacheMinRebroadcastFee()
    167 {
    168     // Update stamp of chain tip on cache run
    169@@ -109,33 +185,23 @@ void TxRebroadcastHandler::CacheMinRebroadcastFee()
    170     LogPrint(BCLog::BENCH, "Caching minimum fee for rebroadcast to %s, took %d µs to calculate.\n", m_cached_fee_rate.ToString(FeeEstimateMode::SAT_VB), delta_time.count());
    171 };
    172 
    173-void TxRebroadcastHandler::RecordAttempt(indexed_rebroadcast_set::index<index_by_wtxid>::type::iterator& entry_it)
    174-{
    175-    auto UpdateRebroadcastEntry = [](RebroadcastEntry& rebroadcast_entry) {
    176-        rebroadcast_entry.m_last_attempt = GetTime<std::chrono::microseconds>();
    177-        ++rebroadcast_entry.m_count;
    178-    };
    179-
    180-    m_attempt_tracker.modify(entry_it, UpdateRebroadcastEntry);
    181-};
    182-
    183 void TxRebroadcastHandler::TrimMaxRebroadcast()
    184 {
    185     // Delete any entries that are older than MAX_ENTRY_AGE
    186     std::chrono::microseconds min_age = GetTime<std::chrono::microseconds>() - MAX_ENTRY_AGE;
    187 
    188-    while (!m_attempt_tracker.empty()) {
    189-        auto it = m_attempt_tracker.get<index_by_last_attempt>().begin();
    190+    while (!m_attempt_tracker->empty()) {
    191+        auto it = m_attempt_tracker->get<index_by_last_attempt>().begin();
    192         if (it->m_last_attempt < min_age) {
    193-            m_attempt_tracker.get<index_by_last_attempt>().erase(it);
    194+            m_attempt_tracker->get<index_by_last_attempt>().erase(it);
    195         } else {
    196             break;
    197         }
    198     }
    199 
    200     // If there are still too many entries, delete the oldest ones
    201-    while (m_attempt_tracker.size() > MAX_ENTRIES) {
    202-        auto it = m_attempt_tracker.get<index_by_last_attempt>().begin();
    203-        m_attempt_tracker.get<index_by_last_attempt>().erase(it);
    204+    while (m_attempt_tracker->size() > MAX_ENTRIES) {
    205+        auto it = m_attempt_tracker->get<index_by_last_attempt>().begin();
    206+        m_attempt_tracker->get<index_by_last_attempt>().erase(it);
    207     }
    208 };
    209diff --git a/src/txrebroadcast.h b/src/txrebroadcast.h
    210index 8a176a08bc..ec3ea34ed7 100644
    211--- a/src/txrebroadcast.h
    212+++ b/src/txrebroadcast.h
    213@@ -12,11 +12,6 @@
    214 #include <util/time.h>
    215 #include <validation.h>
    216 
    217-#include <boost/multi_index/hashed_index.hpp>
    218-#include <boost/multi_index/member.hpp>
    219-#include <boost/multi_index/ordered_index.hpp>
    220-#include <boost/multi_index_container.hpp>
    221-
    222 struct TxIds {
    223     TxIds(uint256 txid, uint256 wtxid) : m_txid(txid), m_wtxid(wtxid) {}
    224 
    225@@ -24,43 +19,15 @@ struct TxIds {
    226     const uint256 m_wtxid;
    227 };
    228 
    229-struct RebroadcastEntry {
    230-    RebroadcastEntry(std::chrono::microseconds now_time, uint256 wtxid)
    231-        : m_last_attempt(now_time),
    232-          m_wtxid(wtxid),
    233-          m_count(1) {}
    234-
    235-    std::chrono::microseconds m_last_attempt;
    236-    const uint256 m_wtxid;
    237-    int m_count;
    238-};
    239-
    240-/** Used for multi_index tag  */
    241-struct index_by_last_attempt {};
    242-
    243-using indexed_rebroadcast_set = boost::multi_index_container<
    244-    RebroadcastEntry,
    245-    boost::multi_index::indexed_by<
    246-        // sorted by wtxid
    247-        boost::multi_index::hashed_unique<
    248-            boost::multi_index::tag<index_by_wtxid>,
    249-            boost::multi_index::member<RebroadcastEntry, const uint256, &RebroadcastEntry::m_wtxid>,
    250-            SaltedTxidHasher
    251-        >,
    252-        // sorted by last rebroadcast time
    253-        boost::multi_index::ordered_non_unique<
    254-            boost::multi_index::tag<index_by_last_attempt>,
    255-            boost::multi_index::member<RebroadcastEntry, std::chrono::microseconds, &RebroadcastEntry::m_last_attempt>
    256-        >
    257-    >
    258->;
    259+class indexed_rebroadcast_set;
    260 
    261 class TxRebroadcastHandler
    262 {
    263 public:
    264-    TxRebroadcastHandler(CTxMemPool& mempool, ChainstateManager& chainman)
    265-        : m_mempool(mempool),
    266-          m_chainman(chainman){};
    267+    TxRebroadcastHandler(CTxMemPool& mempool, ChainstateManager& chainman);
    268+    ~TxRebroadcastHandler();
    269+
    270+    TxRebroadcastHandler(const TxRebroadcastHandler& other) = delete;
    271 
    272     std::vector<TxIds> GetRebroadcastTransactions();
    273 
    274@@ -75,10 +42,13 @@ protected:
    275     CFeeRate m_cached_fee_rate;
    276 
    277     /** Keep track of previous rebroadcast attempts */
    278-    indexed_rebroadcast_set m_attempt_tracker;
    279+    std::unique_ptr<indexed_rebroadcast_set> m_attempt_tracker;
    280+
    281+    /** Test only */
    282+    void UpdateAttempt(uint256 txhsh, int count);
    283 
    284-    /** Update an existing RebroadcastEntry - increment count and update timestamp */
    285-    void RecordAttempt(indexed_rebroadcast_set::index<index_by_wtxid>::type::iterator& entry_it);
    286+    /** Test only */
    287+    bool CheckRecordedAttempt(uint256 txhsh, int expected_count, std::chrono::microseconds expected_timestamp);
    288 
    289 private:
    290     const CTxMemPool& m_mempool;
    

    ajtowns commented at 2:54 am on March 18, 2021:
    txrebroadcast.h is only included from net_processing and txrebroadcast.cpp itself, and net_processing already includes txmempool.h so there’s not much saving to be had here I think

    jnewbery commented at 12:17 pm on March 24, 2021:

    Not currently, but I think a long-term it’d be good to remove the boost header dependencies from modules that aren’t using boost multi_index. That’d involve refactoring the txmempool interface so it’s not exposing multi_index objects.

    To be honest, I’m not entirely sure how much actual benefit this would have on build times and binary size. I think that boost multi_index is almost entirely templates, so if they’re not being instantiated in a translation unit, then it’s probably minimal. Still, I think it’s a good goal in itself to minimize where third party libraries are exposed within our code structure.


    amitiuttarwar commented at 11:49 pm on April 7, 2021:
    I don’t think that having the boost headers has much tangible impact, but I decided to implement mostly for code legibility. The boost logic was ~1/2 of txrebroadcast.h, obscuring the way the module is supposed to be interacted with. I think it’d be fine for now, but more annoying if the rebroadcast logic were to get any more complex, which I think is a possibility.
  53. jnewbery commented at 8:55 pm on March 15, 2021: member
    I’ve reviewed the first 5 commits. Looks good so far!
  54. in src/txrebroadcast.cpp:107 in 038f751e9c outdated
    102+    // Update stamp of chain tip on cache run
    103+    m_tip_at_cache_time = ::ChainActive().Tip();
    104+
    105+    // Update cache fee rate
    106+    std::chrono::microseconds start_time = GetTime<std::chrono::microseconds>();
    107+    m_cached_fee_rate = BlockAssembler(m_mempool, Params()).minTxFeeRate();
    


    ajtowns commented at 2:50 am on March 18, 2021:

    Could keep the old cached fee rate here, so that if you try end up doing UpdateTip / CacheMinRebroadcastFee / RebroadcatTxs you can do something sensible?

    0   new_tip = ::ChainActive().Tip();
    1   if (new_tip != m_tip_at_cache_time) {
    2       m_last_cached_fee_rate = m_cached_fee_rate;
    3   } else {
    4       m_last_cached_fee_rate = max; // ?
    5   }
    6   m_tip_at_cache_time = new_tip;
    

    amitiuttarwar commented at 8:26 pm on April 16, 2021:
    I added some logging to see how often this happens, and indeed it looks like it skips 1-3 times on most days, sometimes up to ~10 times. So, this mechanism seems good, I’ll add it.

    amitiuttarwar commented at 8:13 pm on May 5, 2021:
    done
  55. laanwj commented at 9:15 am on March 24, 2021: member

    Sorry to bring bad news but this needs rebase. There is a silent merge conflict (with 680eb56d828ce358b4e000c140f5b247ff5e6179 part of #21162). Merged on top of master the following build error appears:

    0  CXX      libbitcoin_server_a-net_processing.o
    1net_processing.cpp:1396:55: error: too many arguments to function call, expected 2, have 3
    2            RelayTransaction(ids.m_txid, ids.m_wtxid, m_connman);
    3            ~~~~~~~~~~~~~~~~                          ^~~~~~~~~
    4net_processing.cpp:251:5: note: 'RelayTransaction' declared here
    5    void RelayTransaction(const uint256& txid, const uint256& wtxid) override;
    6    ^
    71 error generated.
    
  56. in src/txrebroadcast.cpp:38 in 0c84415ae9 outdated
    41 
    42     // Use CreateNewBlock to identify rebroadcast candidates
    43     auto block_template = BlockAssembler(m_mempool, Params(), options)
    44                           .CreateNewBlock(m_chainman.ActiveChainstate(), CScript());
    45 
    46-    LOCK(m_mempool.cs);
    


    mzumsande commented at 11:51 pm on March 24, 2021:
    Why is this lock added in the first commit and then removed?

    amitiuttarwar commented at 11:50 pm on April 7, 2021:
    oops, removed
  57. ghost commented at 0:01 am on March 25, 2021: none

    NACK if:

    1. Not random #21061 (comment)

    2. User cannot decide REBROADCAST_MIN_TX_AGE #21061 (review)

    Because, then it does not achieve things mentioned in motivation: This is bad for privacy because it leaks information that allows spy nodes to link bitcoin addresses with IP addresses, a relationship we aim to obfuscate.

    We should not change the way spy nodes work. There will be a pattern here which can be followed.

    I changed my opinion and shared things below: #21061 (comment)

  58. in src/txrebroadcast.cpp:229 in 6f70142fce outdated
    103@@ -96,3 +104,24 @@ void TxRebroadcastHandler::RecordAttempt(indexed_rebroadcast_set::index<index_by
    104 
    105     m_attempt_tracker.modify(entry_it, UpdateRebroadcastEntry);
    106 };
    107+
    108+void TxRebroadcastHandler::TrimMaxRebroadcast()
    


    mzumsande commented at 0:02 am on March 25, 2021:
    Entries from m_attempt_tracker seem to be only cleared after 3 months or when it’s full. Shouldn’t we also remove them if the tx is removed from the mempool because it has made it into a block (which would seem like the most common cause for removing)?

    jnewbery commented at 12:53 pm on March 26, 2021:
    Also make sure that you remove transactions that are conflicted out by the block (ie a conflicting transaction is included in the block).

    glozow commented at 9:48 pm on April 1, 2021:

    Other cases:

    • tx was RBFed out of mempool
    • parents were invalidated by conflicting tx in mempool and/or block

    ~I think it boils down to = if we aren’t keeping the tx in mempool, don’t keep it in the rebroadcast tracker.~ I totally misunderstood, I thought you wouldn’t want a tx in rebroadcast tracker if you didn’t have it in mempool, but actually you’d want to keep it for a bit.


    i0x0ff commented at 6:46 am on April 7, 2021:

    Removing entries from m_attempt_tracker when tx is removed from mempool doesn’t seem necessary given m_attempt_tracker isn’t used as a source for txs that need to be rebroadcasted.

    I also don’t see an issue with keeping txs that have already been included in a block or RBFed out of mempool in the m_attempt_tracker for up to 90 days (as per current setting) or till it gets removed after 500 limit is reached. Removing these entries from m_attempt_tracker would add unnecessary complexity for a small benefit of a little saved memory as far as I understand. On that note, would perhaps removing the 90 days limit and just keeping the 500 limit still be fine?


    mzumsande commented at 4:40 pm on April 7, 2021:

    Removing entries from m_attempt_tracker when tx is removed from mempool doesn’t seem necessary given m_attempt_tracker isn’t used as a source for txs that need to be rebroadcasted.

    I agree that rebroadcast would still work - the problem is more that m_attempt_tracker might not be able to fulfill its intended purpose with a 500 limit if it was keeping track of too many unnecessary transactions (and at the same time expel those that it was meant to keep track off after capacity is reached).


    amitiuttarwar commented at 8:31 pm on April 16, 2021:
    I added commit 2ac22164f82a51d4eaece9acc42f346e8db679a5 to address this! I agree that when transactions are removed from the mempool for certain reasons, we are highly unlikely to see it again, so it makes sense for it to be removed from the rebroadcast attempt tracker. It’s ok if it doesn’t work perfectly for edge cases, but this behavior supports helps it work as intended. Thanks!
  59. sipa commented at 0:07 am on March 25, 2021: member

    @prayank23 I think you’re confused about the goal of this PR. The current problem is that rebroadcasting is something that only happens for your own transactions. Any peer that observes rebroadcasting knows for a fact that it is yours. This PR changes things so that rebroadcasting is done uniformly for all transactions, without special treatment of your own. By definition, if the fact whether a transaction is yours is no longer used in the decision to rebroadcast or not, there is no signal any peer can infer anything from.

    That obviously does not prevent spy nodes from learning other things (like observing which nodes broadcast first to infer origin), but it categorically removes rebroadcasting behavior from the set of leaks.

  60. in src/txrebroadcast.h:41 in 0c84415ae9 outdated
    36+};
    37+
    38+/** Used for multi_index tag  */
    39+struct index_by_last_attempt {};
    40+
    41+using indexed_rebroadcast_set = boost::multi_index_container<
    


    mzumsande commented at 0:10 am on March 25, 2021:
    The mempool is persisted to disk, would it make sense to do the same with the rebroadcast tracker? With the index designed to keep a memory of months, I’d guess that several nodes would undergo several restarts during such a long period and, currently, lose all memory about past rebroadcasts.

    amitiuttarwar commented at 8:32 pm on April 16, 2021:
    seems reasonable, but this PR is getting pretty huge so I’d rather keep this for a follow-up. I’ve noted it down here #21061 (comment) so I can keep track of it, and am going to resolve this conversation.
  61. ghost commented at 0:44 am on March 25, 2021: none

    This PR changes things so that rebroadcasting is done uniformly for all transactions, without special treatment of your own. By definition, if the fact whether a transaction is yours is no longer used in the decision to rebroadcast or not, there is no signal any peer can infer anything from.

    This PR improves on 1 thing: They are not all mine This PR adds 1 thing: New pattern (fee rate and time in mempool)

    It makes things different but not difficult for spy nodes

    What is wrong with my comments? Random txs and time decided by users

    Nobody knows what “should” be mined except miners and that 30 minutes time frame is weird for Bitcoin

  62. sipa commented at 1:09 am on March 25, 2021: member

    This PR adds 1 thing: New pattern (fee rate and time in mempool)

    I see what you mean now. Indeed, it does, but I think this is completely negligible. What it leaks about the mempool is on a scale of 30 minutes to hours. Within such amounts of time, we already reveal the transactions we’ve learned (simply by telling other nodes in the process of normal relay, every few seconds). The concern about privacy here is on the scale of seconds or less - by knowing which nodes see a transaction first an attacker can infer its origin. Revealing what was in your mempool 30 minutes ago is a non-issue.

    Feerate is already revealed (infrequently & quantized) through BIP133 feefilter messages.

    It makes things different but not difficult for spy nodes.

    I disagree here. This change completely removes the issue of learning which transactions belong to a node based on rebroadcasting behavior, which is an enormous leak.

    What is wrong with my comments? Random txs and time decided by users

    What do you mean by “random txs”?

    Time decided by users: generally the criterion for deciding whether a parameter should be configurable is whether you can also give advice under which cases users should be changing it, and how. I don’t know what advice I’d give users except not to touch it; setting it very low could become a privacy issue (using the mechanism you point out), setting it very high may make it useless; things in between probably hardly matter. Do you have a scenario in mind under which you’d suggest changing it?

    Nobody knows what “should” be mined except miners

    That is literally what the mempool is: a node’s prediction of what will be mined in the near future. It doesn’t matter that this prediction is sometimes wrong.

    and that 30 minutes time frame is weird for Bitcoin

    Real world protocol implementations are full of arbitrary-seeming constants.

  63. ghost commented at 8:14 am on March 26, 2021: none

    I thought of different scenarios including weekends when we see less transactions but couldn’t find anything that supports my argument. So I change my opinion for now and maybe need to do more research. This PR improves things and if there is any need for further changes to improve privacy it can be done in follow up PRs.

    Below is a diagram in which I was trying to visualize what happens in A(this PR) and B(things I suggested). I agree with you this change completely removes the issue of learning which transactions belong to a node based on rebroadcasting behavior, which is an enormous leak.

    image

    What do you mean by “random txs”?

    Randomization can be done using different algorithms. But a basic random rebroadcast would ignore filtering based on fee rate. Example: Mempool has 10 txs. A,B,C,D,E,F,G,H,I,J. Using this PR, ABCD are rebroadcasted but in my case AB rebroadcasted once and maybe AED next time if still not confirmed and almost same mempool. Again this suggestion can be ignored and I saw 1sat/vByte being used for filtering when I tried on testnet. Maybe need to do more tests and use mainnet as well.

    Real world protocol implementations are full of arbitrary-seeming constants.

    I was suggesting to use either a default value like 30 minutes and user can change it if required. Or decide a MIN and MAX so that anything between this range can be used else default 30 minutes will be used.

    Sometimes we don’t see any blocks for more than 30 minutes in Bitcoin and few blocks are mined in couple of minutes gap. Considering this it would have been better if there was some algorithm that could adjust the value for us automatically within a range based on last N blocks. But it can also be done manually or we could just ignore this suggestion and do in follow up PRs if required.

    image

  64. in src/txrebroadcast.cpp:49 in 038f751e9c outdated
    44+    options.m_skip_inclusion_until = start_time - REBROADCAST_MIN_TX_AGE;
    45+    options.check_block_validity = false;
    46+    options.blockMinFeeRate = m_cached_fee_rate;
    47+
    48+    // Use CreateNewBlock to identify rebroadcast candidates
    49+    auto block_template = BlockAssembler(m_mempool, Params(), options)
    


    jnewbery commented at 10:27 am on March 26, 2021:

    We’re trying to get rid of global calls like Params(). Consider adding a:

    0    const CChainParams& m_chainparams;
    

    member to TxRebroadcastHandler and setting it in the ctor (like PeerManagerImpl does)


    amitiuttarwar commented at 11:54 pm on April 7, 2021:
    done
  65. in src/miner.h:139 in 038f751e9c outdated
    132@@ -133,6 +133,10 @@ class BlockAssembler
    133     bool fIncludeWitness;
    134     unsigned int nBlockMaxWeight;
    135     CFeeRate blockMinFeeRate;
    136+    std::chrono::microseconds m_skip_inclusion_until;
    137+
    138+    // To permit disabling block validity check
    139+    bool check_block_validity;
    


    jnewbery commented at 12:38 pm on March 26, 2021:
    0    bool m_check_block_validity;
    

    amitiuttarwar commented at 11:54 pm on April 7, 2021:
    done
  66. in src/txrebroadcast.cpp:36 in 038f751e9c outdated
    31+static constexpr std::chrono::hours MAX_ENTRY_AGE = std::chrono::hours(3 * 30 * 24);
    32+
    33+std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
    34+{
    35+    std::vector<TxIds> rebroadcast_txs;
    36+    std::chrono::microseconds start_time = GetTime<std::chrono::microseconds>();
    


    jnewbery commented at 12:41 pm on March 26, 2021:

    The type is obvious from the template parameter, so may be a good place to use auto:

    0    auto start_time = GetTime<std::chrono::microseconds>();
    

    (and in the other calls to GetTime)


    amitiuttarwar commented at 11:55 pm on April 7, 2021:
    ok ok, I think I auto-ed the GetTime call sites.
  67. in src/txrebroadcast.cpp:88 in 038f751e9c outdated
    83+        rebroadcast_txs.push_back(TxIds(txid, wtxid));
    84+    }
    85+
    86+    TrimMaxRebroadcast();
    87+
    88+    std::chrono::microseconds delta1 = after_CNB_time - start_time;
    


    jnewbery commented at 12:46 pm on March 26, 2021:
    AUTO
  68. in src/txrebroadcast.cpp:90 in 038f751e9c outdated
    85+
    86+    TrimMaxRebroadcast();
    87+
    88+    std::chrono::microseconds delta1 = after_CNB_time - start_time;
    89+    std::chrono::microseconds delta2 = GetTime<std::chrono::microseconds>() - start_time;
    90+    LogPrint(BCLog::BENCH, "GetRebroadcastTransactions(): %d µs total, %d µs spent in CreateNewBlock.\n", delta1.count(), delta2.count());
    


    jnewbery commented at 12:47 pm on March 26, 2021:
    Maybe better to use “us” instead of “µs” to keep logs in ascii.

    amitiuttarwar commented at 11:56 pm on April 7, 2021:
    aw man, I thought I was so cool
  69. in src/miner.cpp:321 in 038f751e9c outdated
    316+    int packages_selected = 0;
    317+    int descendants_updated = 0;
    318+    CFeeRate min_fee_rate = CFeeRate(COIN, 1);
    319+
    320+    resetBlock();
    321+    pblocktemplate.reset(new CBlockTemplate());
    


    jnewbery commented at 12:59 pm on March 26, 2021:
    use std::make_unique() to make unique pointers.

    amitiuttarwar commented at 11:56 pm on April 7, 2021:
    done
  70. in src/miner.cpp:323 in 038f751e9c outdated
    318+    CFeeRate min_fee_rate = CFeeRate(COIN, 1);
    319+
    320+    resetBlock();
    321+    pblocktemplate.reset(new CBlockTemplate());
    322+
    323+    if (!pblocktemplate.get()) {
    


    jnewbery commented at 1:00 pm on March 26, 2021:
    This seems impossible to hit. You’ve just constructed a new std::unique_ptr<CBlockTemplate>.

    amitiuttarwar commented at 11:57 pm on April 7, 2021:
    yeah, looks like I copied this from CreateNewBlock and thought it was a “safety check” but I agree, it seems pointless. Removed.
  71. in src/miner.cpp:321 in 038f751e9c outdated
    336+
    337+    block->nTime = static_cast<uint32_t>(GetAdjustedTime());
    338+    const int64_t median_time_past = prev_block_index->GetMedianTimePast();
    339+
    340+    nLockTimeCutoff = median_time_past;
    341+    fIncludeWitness = IsWitnessEnabled(prev_block_index, chainparams.GetConsensus());
    


    jnewbery commented at 1:01 pm on March 26, 2021:
    I don’t think this is needed. Witness is definitely enabled at the tip!

    amitiuttarwar commented at 2:14 am on April 3, 2021:
    so you’d prefer if I hard coded this to fIncludeWitness = true? 🤔 IsWitnessEnabled doesn’t seem like an expensive function.
  72. in src/txrebroadcast.cpp:103 in 038f751e9c outdated
     98+};
     99+
    100+void TxRebroadcastHandler::CacheMinRebroadcastFee()
    101+{
    102+    // Update stamp of chain tip on cache run
    103+    m_tip_at_cache_time = ::ChainActive().Tip();
    


    jnewbery commented at 1:03 pm on March 26, 2021:
    Avoid calls to the global ::ChainActive().

    amitiuttarwar commented at 0:04 am on April 8, 2021:
    done by making chainman a member
  73. in src/txrebroadcast.cpp:106 in 038f751e9c outdated
    101+{
    102+    // Update stamp of chain tip on cache run
    103+    m_tip_at_cache_time = ::ChainActive().Tip();
    104+
    105+    // Update cache fee rate
    106+    std::chrono::microseconds start_time = GetTime<std::chrono::microseconds>();
    


    jnewbery commented at 1:03 pm on March 26, 2021:
    0    auto start_time = GetTime<std::chrono::microseconds>();
    
  74. in src/miner.h:176 in 038f751e9c outdated
    168@@ -163,6 +169,12 @@ class BlockAssembler
    169     static Optional<int64_t> m_last_block_num_txs;
    170     static Optional<int64_t> m_last_block_weight;
    171 
    172+    /* This function wraps addPackageTxs to calculate and return the minimum fee
    173+     * rate required for a package to currently be included in the highest fee rate
    174+     * block possible based on mempool transactions.
    175+     */
    176+    CFeeRate minTxFeeRate();
    


    jnewbery commented at 1:03 pm on March 26, 2021:

    Functions should be capitalized:

    0    CFeeRate MinTxFeeRate();
    

    amitiuttarwar commented at 0:05 am on April 8, 2021:
    fixed
  75. in src/txrebroadcast.cpp:109 in 038f751e9c outdated
    104+
    105+    // Update cache fee rate
    106+    std::chrono::microseconds start_time = GetTime<std::chrono::microseconds>();
    107+    m_cached_fee_rate = BlockAssembler(m_mempool, Params()).minTxFeeRate();
    108+    std::chrono::microseconds delta_time = GetTime<std::chrono::microseconds>() - start_time;
    109+    LogPrint(BCLog::BENCH, "Caching minimum fee for rebroadcast to %s, took %d µs to calculate.\n", m_cached_fee_rate.ToString(FeeEstimateMode::SAT_VB), delta_time.count());
    


    jnewbery commented at 1:05 pm on March 26, 2021:

    again, maybe avoid greek letters:

    0    LogPrint(BCLog::BENCH, "Caching minimum fee for rebroadcast to %s, took %d us to calculate.\n", m_cached_fee_rate.ToString(FeeEstimateMode::SAT_VB), delta_time.count());
    
  76. in src/miner.cpp:331 in 038f751e9c outdated
    326+    CBlock* block = &pblocktemplate->block;
    327+
    328+    // Add dummy coinbase tx as first transaction
    329+    block->vtx.emplace_back();
    330+    pblocktemplate->vTxFees.push_back(-1);
    331+    pblocktemplate->vTxSigOpsCost.push_back(-1);
    


    jnewbery commented at 1:09 pm on March 26, 2021:
    Are these definitely needed? You’re just going to throw the block template away at the end.

    amitiuttarwar commented at 7:49 pm on April 8, 2021:
    I think you’re right, so I’ve removed these three lines. nice catch!
  77. in src/miner.cpp:333 in 038f751e9c outdated
    328+    // Add dummy coinbase tx as first transaction
    329+    block->vtx.emplace_back();
    330+    pblocktemplate->vTxFees.push_back(-1);
    331+    pblocktemplate->vTxSigOpsCost.push_back(-1);
    332+
    333+    CBlockIndex* prev_block_index = ::ChainActive().Tip();
    


    jnewbery commented at 1:10 pm on March 26, 2021:
    Avoid the global ::ChainActive()

    amitiuttarwar commented at 7:51 pm on April 8, 2021:
    fixed
  78. in src/miner.cpp:337 in 038f751e9c outdated
    332+
    333+    CBlockIndex* prev_block_index = ::ChainActive().Tip();
    334+    assert(prev_block_index != nullptr);
    335+    nHeight = prev_block_index->nHeight + 1;
    336+
    337+    block->nTime = static_cast<uint32_t>(GetAdjustedTime());
    


    jnewbery commented at 1:12 pm on March 26, 2021:
    I don’t think this is needed. You’re throwing away the block afterwards.

    amitiuttarwar commented at 7:52 pm on April 8, 2021:
    agreed, gone
  79. in src/miner.cpp:340 in 038f751e9c outdated
    335+    nHeight = prev_block_index->nHeight + 1;
    336+
    337+    block->nTime = static_cast<uint32_t>(GetAdjustedTime());
    338+    const int64_t median_time_past = prev_block_index->GetMedianTimePast();
    339+
    340+    nLockTimeCutoff = median_time_past;
    


    jnewbery commented at 1:12 pm on March 26, 2021:
    join these lines?
  80. in src/miner.cpp:324 in 038f751e9c outdated
    339+
    340+    nLockTimeCutoff = median_time_past;
    341+    fIncludeWitness = IsWitnessEnabled(prev_block_index, chainparams.GetConsensus());
    342+
    343+    {
    344+        LOCK2(cs_main, m_mempool.cs);
    


    jnewbery commented at 1:17 pm on March 26, 2021:
    Is cs_main definitely required here? addPackageTxs() isn’t annotated to say that it’s required.

    amitiuttarwar commented at 8:34 pm on April 16, 2021:
    I tried to audit addPackageTxs and I think you’re right that it’s not necessary, but it’s hard to be certain because there is a lot going on in the function & its only ever called under the cs_main lock. Do you have any recommendations for how I could build confidence other than checking the thread of every call site of every invoked function / variable? Maybe I could just remove and run the node and give it a 👍 if it doesn’t crash for a week? 😅

    amitiuttarwar commented at 5:03 am on May 31, 2021:
    I removed the cs_main call from here, but think I actually have to lock it from the caller, see: #21061 (review)
  81. in src/miner.cpp:337 in 038f751e9c outdated
    357@@ -308,7 +358,7 @@ void BlockAssembler::SortForBlock(const CTxMemPool::setEntries& package, std::ve
    358 // Each time through the loop, we compare the best transaction in
    359 // mapModifiedTxs with the next transaction in the mempool to decide what
    360 // transaction package to work on next.
    361-void BlockAssembler::addPackageTxs(int &nPackagesSelected, int &nDescendantsUpdated)
    362+void BlockAssembler::addPackageTxs(int& nPackagesSelected, int& nDescendantsUpdated, CFeeRate* min_package_fee_rate)
    


    jnewbery commented at 1:32 pm on March 26, 2021:

    min_package_fee_rate seems very cheap to calculate. Perhaps just make it a reference so it’s always returned.

    (even better would be:

    0std::tuple<int, int, CFeeRate> BlockAssembler::addPackageTxs()
    

    but that’s maybe beyond the scope of this PR)


    amitiuttarwar commented at 7:00 pm on April 16, 2021:

    agree that updating min_package_fee_rate is pretty cheap, there’s no additional calculation, its just updating the stored value, but might do so up to ~once per mempool transaction.

    but can you help me understand the context of why you’re suggesting a reference? even if it’s not a lot of calculation, seems unnecessary?

    (agree that returning a tuple instead of in/out params would be nice. but leaving other params as is within this PR.)

  82. in src/txrebroadcast.cpp:40 in 038f751e9c outdated
    35+    std::vector<TxIds> rebroadcast_txs;
    36+    std::chrono::microseconds start_time = GetTime<std::chrono::microseconds>();
    37+
    38+    // If there has not been a cache run since the last block, the fee rate
    39+    // condition will not filter out any transactions, so skip this run.
    40+    if (m_tip_at_cache_time == ::ChainActive().Tip()) return rebroadcast_txs;
    


    jnewbery commented at 1:40 pm on March 26, 2021:
    avoid global ::ChainActive

    amitiuttarwar commented at 10:29 pm on April 8, 2021:
    fixed
  83. in src/txrebroadcast.cpp:11 in 038f751e9c outdated
     5+#include <chainparams.h>
     6+#include <consensus/consensus.h>
     7+#include <logging.h>
     8+#include <miner.h>
     9+#include <script/script.h>
    10+#include <txrebroadcast.h>
    


    jnewbery commented at 1:46 pm on March 26, 2021:
    I think we prefer to include all headers that are used in the translation unit, even if they’re also included in the corresponding header file. You don’t need to remove the “#include <util/time.h> in the [rebroadcast] Track rebroadcast attempts commit.
  84. in src/txrebroadcast.cpp:26 in 038f751e9c outdated
    15+static constexpr unsigned int MAX_REBROADCAST_WEIGHT = 3 * MAX_BLOCK_WEIGHT / 4;
    16+
    17+/** Default minimum age for a transaction to be rebroadcast */
    18+static constexpr std::chrono::minutes REBROADCAST_MIN_TX_AGE = 30min;
    19+
    20+/** Maximum number of times we will rebroadcast a tranasaction */
    


    jnewbery commented at 1:47 pm on March 26, 2021:
    Perhaps add some of the description from the [rebroadcast] Track rebroadcast attempts commit log here. It’s not at all obvious why we’d stop rebroadcasting after some time, and that commit log has a good explanation.

    amitiuttarwar commented at 4:49 am on April 13, 2021:
    done, how’s it look? 3f4b664 (#21061)
  85. in src/txrebroadcast.cpp:112 in 038f751e9c outdated
    107+    m_cached_fee_rate = BlockAssembler(m_mempool, Params()).minTxFeeRate();
    108+    std::chrono::microseconds delta_time = GetTime<std::chrono::microseconds>() - start_time;
    109+    LogPrint(BCLog::BENCH, "Caching minimum fee for rebroadcast to %s, took %d µs to calculate.\n", m_cached_fee_rate.ToString(FeeEstimateMode::SAT_VB), delta_time.count());
    110+};
    111+
    112+void TxRebroadcastHandler::RecordAttempt(indexed_rebroadcast_set::index<index_by_wtxid>::type::iterator& entry_it)
    


    jnewbery commented at 1:52 pm on March 26, 2021:
    Maybe pass in the current time to avoid calling GetTime() for every transaction?

  86. in src/txrebroadcast.cpp:31 in 038f751e9c outdated
    26+
    27+/** The maximum number of entries permitted in m_attempt_tracker */
    28+static constexpr int MAX_ENTRIES = 500;
    29+
    30+/** The maximum age of an entry ~3 months */
    31+static constexpr std::chrono::hours MAX_ENTRY_AGE = std::chrono::hours(3 * 30 * 24);
    


    jnewbery commented at 1:55 pm on March 26, 2021:

    y so verbose?

    0static constexpr std::chrono::hours MAX_ENTRY_AGE = 24h * 30 * 3;
    
  87. in test/functional/p2p_rebroadcast.py:28 in 038f751e9c outdated
    23+from test_framework.util import (
    24+    assert_approx,
    25+    assert_greater_than,
    26+    create_confirmed_utxos,
    27+)
    28+import time
    


    jnewbery commented at 1:58 pm on March 26, 2021:
    Import standard libraries first, then local modules (this is the opposite order from c++)

    jnewbery commented at 10:37 am on April 13, 2021:
    (this is recommended in PEP8: https://www.python.org/dev/peps/pep-0008/#imports)
  88. 0xB10C commented at 1:33 pm on March 31, 2021: member

    Concept ACK: this removes the rebroadcasting privacy leak

    I found the your summary of the previous discussion very helpful and still want to think though some of the edge cases in regards to e.g. bandwidth usage (which I think is already in a good state).


    @prayank23 I’m not sure I understood your concern with the constant min-age of 30min before consider to rebroadcast a transaction. This exists to limit the bandwidth usage (see the summary linked above if you haven’t already read it). I think having this configurable doesn’t add anything.


    I’ve been comparing the contents of block templates to the actual blocks (with the goal detecting miners censoring transactions; unrelated to this PR). One edge case I’ve observed a few times is: A transaction tx1 is missing from 100+ blocks it “should have been in”. Manually rebroadcasting fails as there exists a conflicting and better propagated transaction tx2 paying a substantially lower feerate. (This essentially a real-world observation of what @gmaxwell mentioned at the end of #16698 (comment) as a potential bandwidth attack).

    A naive implemention would try to rebroadcast tx1 for each of the 100+ blocks until tx2 confirms. I haven’t checked your code, but based on the summary this would be mitigated by only rebroadcasting the transaction every 4h and not more than six times total. I don’t think adding ‘do-not-re-rebroadcast-previously-rejected/conflicting-tx’-logic is worth it.

  89. DrahtBot added the label Needs rebase on Apr 1, 2021
  90. in src/txrebroadcast.cpp:34 in 038f751e9c outdated
    23+/** Minimum amount of time between returning the same transaction for
    24+ * rebroadcast */
    25+static constexpr std::chrono::hours MIN_REATTEMPT_INTERVAL = 4h;
    26+
    27+/** The maximum number of entries permitted in m_attempt_tracker */
    28+static constexpr int MAX_ENTRIES = 500;
    


    glozow commented at 9:26 pm on April 1, 2021:
    braced initialization? 😛

    amitiuttarwar commented at 4:53 am on April 13, 2021:
    ok, done for all the constants in this file
  91. in src/txrebroadcast.h:86 in 038f751e9c outdated
    87+
    88+    /** Block at time of cache */
    89+    CBlockIndex* m_tip_at_cache_time{nullptr};
    90+
    91+    /** Limit the size of m_attempt_tracker by deleting the oldest entries */
    92+    void TrimMaxRebroadcast();
    


    glozow commented at 9:34 pm on April 1, 2021:
    Why oldest and not random eviction, for example? Have you considered having a configurable value (similar to -maxorphantx)?

    amitiuttarwar commented at 4:06 am on April 13, 2021:

    RE oldest vs random: since the attempt tracker updates the timestamp every time a transaction is selected as a candidate for rebroadcast, it makes sense to me that the least relevant would be ones that haven’t been selected for the longest time. usually we use randomness in p2p data structures to ensure that a malicious peer cannot have disproportionate influence, which I don’t think quite applies here. its possible that a peer could roll the attempt tracker, but they would also have to roll filterInventoryKnown in order to spend actual network bandwidth. I haven’t thought this through in great depth, so let me know if I’m missing some reasons why we should consider randomizing.

    RE configurable: as sipa mentioned in #21061 (comment), “generally the criterion for deciding whether a parameter should be configurable is whether you can also give advice under which cases users should be changing it, and how.” I am also sensitive to introducing configurable params because it increases the maintenance burden of the project essentially forever. Do you see use cases of how you would recommend users to adjust the attempt tracker? The main reason I’d imagine for wanting a larger tracker is to reduce bandwidth, but in that case I think a “turn rebroadcast off” toggle would make more sense (and of this PR its off by default)

  92. in src/net_processing.cpp:1395 in 038f751e9c outdated
    1390@@ -1384,6 +1391,17 @@ void PeerManagerImpl::UpdatedBlockTip(const CBlockIndex *pindexNew, const CBlock
    1391         }
    1392     }
    1393 
    1394+    // Rebroadcast selected mempool transactions
    1395+    if (gArgs.GetArg("-rebroadcast", DEFAULT_REBROADCAST_ENABLED)) {
    


    glozow commented at 9:55 pm on April 1, 2021:
    ~I don’t think we should rebroadcast after every block if we’re in IBD?~ Nevermind there’s already an IBD gate above
  93. in src/net_processing.cpp:1257 in 038f751e9c outdated
    1253+    // Attempt initial broadcast of locally submitted transactions in 10-15 minutes
    1254     const std::chrono::milliseconds delta = std::chrono::minutes{10} + GetRandMillis(std::chrono::minutes{5});
    1255     scheduler.scheduleFromNow([&] { ReattemptInitialBroadcast(scheduler); }, delta);
    1256+
    1257+    // Rebroadcast cache every minute
    1258+    scheduler.scheduleEvery([this] { m_txrebroadcast.CacheMinRebroadcastFee(); }, std::chrono::minutes{1});
    


    glozow commented at 9:58 pm on April 1, 2021:
    Same, maybe not worth doing until after IBD?

  94. glozow commented at 10:15 pm on April 1, 2021: member

    Approach ACK, I think it makes sense to run the block assembler to determine which transactions we expect should have been mined. I’ve only done a light review so far, put in some suggestions about IBD and evicting from the tracker.

    Have you considered using the size of the block received instead of the max block weight? If an empty block is mined, for example, it seems unnecessary for all the Core nodes rebroadcast hundreds of transactions.

    commit message from 0c84415ae9:

    We use this information primarily to ensure we don’t exceed a maximum number of rebroadcast attempts. This allows transactions to genuinely expire from the majority of mempools.

    I don’t really understand - what does it mean for tx to not genuinely expire from mempool? I thought the mempool would just evict a tx after expiry, and then rebroadcasts no longer happen either because we forgot about it? If you didn’t have the rebroadcast tracker, would you keep rebroadcasting to each other and keep it in your mempool?

  95. in src/txrebroadcast.cpp:51 in 038f751e9c outdated
    46+    options.blockMinFeeRate = m_cached_fee_rate;
    47+
    48+    // Use CreateNewBlock to identify rebroadcast candidates
    49+    auto block_template = BlockAssembler(m_mempool, Params(), options)
    50+                          .CreateNewBlock(m_chainman.ActiveChainstate(), CScript());
    51+    std::chrono::microseconds after_CNB_time = GetTime<std::chrono::microseconds>();
    


    practicalswift commented at 9:42 am on April 7, 2021:
    Super small nit: Since this is new code - consider renaming as after_cnb_time to conform to the symbol naming conventions as described in the developer notes? :)
  96. laanwj commented at 2:14 pm on April 7, 2021: member

    Looks like 7b8e976cd5ac78a22f1be2b2fed8562c693af5d9 (#21525) introduced a small merge conflict with 9307196d13ec589f01546ff8c4758211fc1d48cb in miner.cpp (function BlockAssembler::CreateNewBlock).

    I think it can be solved by changing chainparams to m_chainparams on the affected line. Edit: no, it is needed on more lines. This is just the only one where an explicit conflict happens.

  97. amitiuttarwar force-pushed on Apr 7, 2021
  98. DrahtBot removed the label Needs rebase on Apr 8, 2021
  99. amitiuttarwar commented at 2:08 am on April 8, 2021: contributor
    thank you all for the reviews! I’m working on incorporating/addressing all the comments. I’ve taken a first pass, but am still working my way through, I’ll post again when I believe I’ve addressed all outstanding comments.
  100. vasild commented at 3:09 pm on April 9, 2021: member

    Two noob questions (I did not look at the code):

    1. Could it happen that well propagated transactions with high fees are unnecessary rebroadcasted by all nodes at the same time, if a new block is mined that does not include them? Could this even be common? @0xB10C do you have some stats, on average, per block, how many transactions are not mined, that should have been mined?

    2. Wrt transactions with very low fees that originated on our node, is my understanding correct:

    • before this PR we would have rebroadcast them which is good for propagation and bad for privacy
    • after this PR we would not rebroadcast them which is good for privacy and bad for propagation?

    If yes, then what about still rebroadcasting our low-fee transactions but also rebroadcast a bunch of random ones to make it less obvious that a tx is ours?

  101. 0xB10C commented at 9:41 pm on April 9, 2021: member

    0xB10C do you have some stats, on average, per block, how many transactions are not mined, that should have been mined?

    Over the last ~2350 blocks there were on average 38 transactions (standard derivation of 116) and median 15 transactions not in the the block that my node’s template (generated a few seconds before the pool-set block time ¹ ) would have included. Not all of these on average 38 transactions would make it into the rebroadcast set.

    0count    2347.000000
    1mean       37.921176
    2std       116.198727
    3min         1.000000
    425%         6.000000
    550%        15.000000
    675%        36.000000
    7max      3226.000000
    

    ¹) My methodology is not perfect as 1) pools clocks are not always accurate and 2) miners do additional nTime rolling on the timestamp so the pool likely generated his template before the block-time of the final block. That said, these numbers should still work here.

  102. vasild commented at 8:38 am on April 12, 2021: member

    @0xB10C, thanks!

    So, to summarize, most of the time, shortly after every block is created, all nodes (that run this software) will rebroadcast a few 10s of transactions (and occasionally a few 1000s of transactions (corresponding to max 3226 above)). And this will be because miners’ algo for composing a block differ from ours, not necessary because the transactions are not well propagated.

    Is this too aggressive, possibly creating unnecessary traffic? Would it make sense to rebroadcast a given tx only if it should have been included in each one of the last N blocks, but was not? (currently, I assume, it works as if N=1)

  103. in src/miner.h:196 in 0689065102 outdated
    189@@ -188,7 +190,10 @@ class BlockAssembler
    190       * only as an extra check in case of suboptimal node configuration */
    191     bool TestPackageTransactions(const CTxMemPool::setEntries& package) const;
    192     /** Return true if given transaction from mapTx has already been evaluated,
    193-      * or if the transaction's cached data in mapTx is incorrect. */
    194+      * or if the transaction's cached data in mapTx is incorrect.
    195+      * If m_skip_inclusion_until is set in the options, we will skip
    196+      * transactions until they meet that age. This is currently used for
    197+      * rebroadcast logic.*/
    


    achow101 commented at 8:06 pm on April 12, 2021:

    In 06890651027cc50bdf3897283386a973bbf55725 “[mining] Add recency condition on block creation to get rebroadcast set”

    This comment could be clearer as m_skip_inclusion_until isn’t really an age. Rather we exclude any transactions that entered the mempool after the time specified by m_skip_inclusion_until.


    amitiuttarwar commented at 4:56 am on April 13, 2021:

    Used this suggested wording & updated to:

    0      * If m_skip_inclusion_until is set in the options, we will exclude any
    1      * transactions that entered the mempool after the time specified. This is
    2      * currently used for rebroadcast logic. */
    
  104. in src/txrebroadcast.cpp:26 in 8b4db051ba outdated
    20@@ -20,10 +21,15 @@ std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions()
    21 {
    22     std::vector<TxIds> rebroadcast_txs;
    23 
    24+    // If there has not been a cache run since the last block, the fee rate
    25+    // condition will not filter out any transactions, so skip this run.
    26+    if (m_tip_at_cache_time == m_chainman.ActiveChain().Tip()) return rebroadcast_txs;
    


    achow101 commented at 8:26 pm on April 12, 2021:

    In 8b4db051bac56cefa8c85fe20e5548ddfab0f070 “[rebroadcast] Apply a fee rate filter”

    I’m having a hard time understanding how this comment explains the condition here. Could you explain in more detail?


    amitiuttarwar commented at 4:29 am on April 13, 2021:

    you’re right, this comment is really confusing. updated to:

    0    // If the cache has run since we received the last block, the fee rate
    1    // condition will not filter out any transactions, so skip this run.
    

    And here’s some more explanation:

    Let’s refer to the fee rate for a txn to be in the top MAX_REBROADCAST_WEIGHT as top-of-mempool fee rate. The only event that has the ability to decrease the top-of-mempool fee rate is a block being mined. Otherwise, as transactions enter the mempool, the top-of-mempool fee rate either stays the same or increases.

    If the top-of-mempool fee rate is only increasing over time, the fee rate cache would not help filter any transactions out.

    Our desired order is: cache | block | rebroadcast, with the delta between cache & block to be as small as possible.

    The order we want to skip is: block | cache | rebroadcast, because then the fee rate filter will be meaningless, and would simply select the next highest transactions to rebroadcast (which we logically wouldn’t expect to be mined yet).

    Does this make sense? Does the update to the comment help clarify? I’m not sure the best way to capture this in the code, so open to suggestions.

  105. in src/txrebroadcast.cpp:195 in d579110263 outdated
    190+            rebroadcast_entry.m_last_attempt = last_attempt_time;
    191+            ++rebroadcast_entry.m_count;
    192+        };
    193+
    194+        m_attempt_tracker->modify(it, UpdateRebroadcastEntry);
    195+    }
    


    achow101 commented at 9:03 pm on April 12, 2021:

    In d579110263ad07386f1fbf796a3397a12340b6d5 “[test] Add unit test for rebroadcast attempt logic”

    It seems like this for loop is not necessary as it is essentially doing m_count += count. Could instead be:

    0    auto UpdateRebroadcastEntry = [last_attempt_time, count](RebroadcastEntry& rebroadcast_entry) {
    1        rebroadcast_entry.m_last_attempt = last_attempt_time;
    2        rebroadcast_entry.m_count += count;
    3    };
    4
    5    m_attempt_tracker->modify(it, UpdateRebroadcastEntry);
    

    amitiuttarwar commented at 4:57 am on April 13, 2021:
    good point, updated!
  106. in src/test/txrebroadcast_tests.cpp:36 in d579110263 outdated
    26+    TxRebroadcastHandlerTest(CTxMemPool& mempool, ChainstateManager& chainman, const CChainParams& chainparams) :
    27+        TxRebroadcastHandler(mempool, chainman, chainparams){};
    28+
    29+    void UpdateAttempt(uint256 txhsh, int count)
    30+    {
    31+        auto attempt_time = GetTime<std::chrono::microseconds>() - 4h;
    


    achow101 commented at 9:06 pm on April 12, 2021:

    In d579110263ad07386f1fbf796a3397a12340b6d5 “[test] Add unit test for rebroadcast attempt logic”

    It seems a bit odd to me that this function is supposed to be a wrapper but it also implements a little bit of test logic in that it changes the recorded last attempt time. I think it would make more sense to have the main test logic calculate the timestamp change and make this function a pure wrapper (or perhaps remove the entire class).


    amitiuttarwar commented at 8:34 pm on April 16, 2021:
    ok! removed the entire class and just made the test functions public with a comment indicating they are test only
  107. in src/test/txrebroadcast_tests.cpp:125 in 0f13d87697 outdated
    141@@ -96,7 +142,7 @@ BOOST_AUTO_TEST_CASE(max_rebroadcast)
    142 
    143     // Check that the transaction gets returned to rebroadcast
    144     std::vector<TxIds> candidates = tx_rebroadcast.GetRebroadcastTransactions();
    145-    BOOST_CHECK_EQUAL(candidates.size(), 1);
    146+    BOOST_REQUIRE_EQUAL(candidates.size(), 1);
    


    achow101 commented at 9:10 pm on April 12, 2021:

    In 0f13d876977d6a83549fa40f68a73308ba10d95d “[test] Add unit test for the fee rate cache”

    Seems like this change should be part of the previous commit.


    amitiuttarwar commented at 4:57 am on April 13, 2021:
    fixed
  108. in src/test/txrebroadcast_tests.cpp:145 in 0f13d87697 outdated
    159@@ -114,7 +160,7 @@ BOOST_AUTO_TEST_CASE(max_rebroadcast)
    160     SetMockTime(current_time);
    161     // Then check that it gets returned for rebroadacst
    162     candidates = tx_rebroadcast.GetRebroadcastTransactions();
    163-    BOOST_CHECK_EQUAL(candidates.size(), 1);
    164+    BOOST_REQUIRE_EQUAL(candidates.size(), 1);
    


    achow101 commented at 9:10 pm on April 12, 2021:

    In 0f13d876977d6a83549fa40f68a73308ba10d95d “[test] Add unit test for the fee rate cache”

    Seems like this change should be part of the previous commit.

  109. in test/functional/p2p_rebroadcast.py:2 in 7005767691 outdated
    0@@ -0,0 +1,191 @@
    1+#!/usr/bin/env python3
    2+# Copyright (c) 2009-2021 The Bitcoin Core developers
    


    achow101 commented at 9:18 pm on April 12, 2021:

    In 7005767691005f66e7e08ec2e575d436dae3be47 “[test] Functional tests for rebroadcast logic.”

    0# Copyright (c) 2021 The Bitcoin Core developers
    
  110. in test/functional/p2p_rebroadcast.py:55 in 7005767691 outdated
    50+
    51+        inputs = [{'txid': input_utxo['txid'], 'vout': input_utxo['vout']}]
    52+
    53+        # Calculate how much input values add up to
    54+        input_tx_hsh = input_utxo['txid']
    55+        raw_tx = node.decoderawtransaction(node.getrawtransaction(input_tx_hsh))
    


    achow101 commented at 9:24 pm on April 12, 2021:

    In 7005767691005f66e7e08ec2e575d436dae3be47 “[test] Functional tests for rebroadcast logic.”

    getrawtransaction can decode txs too.

    0        raw_tx = node.getrawtransaction(input_tx_hsh, True)
    
  111. in test/functional/p2p_rebroadcast.py:46 in 7005767691 outdated
    40+            "-txindex",
    41+            "-rebroadcast=1"
    42+        ]] * self.num_nodes
    43+
    44+    def skip_test_if_missing_module(self):
    45+        self.skip_if_no_wallet()
    


    achow101 commented at 9:29 pm on April 12, 2021:

    In 7005767691005f66e7e08ec2e575d436dae3be47 “[test] Functional tests for rebroadcast logic.”

    It would be nice to not require the wallet for a p2p test.


    amitiuttarwar commented at 8:35 pm on April 16, 2021:
    agreed, I’ve noted it down here: #21061 (comment) so I can keep track of it, and will address either in this PR or in a follow up. I’m going to resolve this conversation and will track it with that comment.
  112. achow101 commented at 9:32 pm on April 12, 2021: member
    Concept ACK
  113. amitiuttarwar force-pushed on Apr 13, 2021
  114. ajtowns commented at 3:29 am on April 15, 2021: member

    FWIW, I’ve been running this for about a week (a total of 1012 blocks), and most blocks result in an attempt to rebroadcast 6 or fewer txs, 75% of blocks are 51 or under, 99% of blocks are under 600 transactions, and the highest 1% of blocks result in 586- 1075 txs being queued for rebroadcast.

    I haven’t investigated how many of these “queued for attempted rebroadcast” txs actually result in an INV being sent to some/all peers (since they’ll be filtered by the inventory known bloom filter if they were at all recent), or how many of the txs that get INVed actually get requested. (I have seen at least one rebroadcasted tx get requested by a peer though, so that’s something!)

  115. amitiuttarwar force-pushed on Apr 16, 2021
  116. in src/txrebroadcast.cpp:21 in d1bcb1d213 outdated
    16+#include <boost/multi_index/ordered_index.hpp>
    17+#include <boost/multi_index_container.hpp>
    18+
    19+/** We rebroadcast 3/4 of max block weight to reduce noise due to circumstances
    20+ *  such as miners mining priority transactions. */
    21+static constexpr unsigned int MAX_REBROADCAST_WEIGHT{3 * MAX_BLOCK_WEIGHT / 4};
    


    ariard commented at 9:34 pm on April 16, 2021:

    IIUC the purpose of this variable, we assume miners’s mempools to be composed in average of 1/4 of irreplaceable transactions. I.e transactions even if we know better feerate candidates, we won’t be able to replace them as their scores are unduly increased by miner’s mempool policy.

    Intuitively, this sounds a lot, do you have any real-world data backing up this assumption ? One could look on how many mined block transactions are under the local node MinTxFeeRate you’ve introduced to determine the size of the surprise set.

    What’s the trade-off of picking a value deviating from real-world data ? Well I think you may prevent or delay rebroadcast of transactions in the bottom quarter of block feerate. Due to this delay, broadcasting clients of those transactions may reach a fee-bumping timer and they trigger a RBF/CPFP in consequence. As such bleeding feerate beyond what would have been effective to get into block templates.

    If the risk I’m describing is founded, do you think we should preserve transactions broadcaster’s feerate instead of network nodes’ bandwidth ? I’m leaning toward a yes as rebroadcast logic is at least opt-in, but broadcaster won’t be aware of their peers’s policies barring propagation of their good-enough feerate transaction.

  117. in src/txrebroadcast.cpp:34 in d1bcb1d213 outdated
    29+/** Minimum amount of time between returning the same transaction for
    30+ * rebroadcast */
    31+static constexpr std::chrono::hours MIN_REATTEMPT_INTERVAL{4h};
    32+
    33+/** The maximum number of entries permitted in m_attempt_tracker */
    34+static constexpr int MAX_ENTRIES{500};
    


    ariard commented at 10:14 pm on April 16, 2021:

    Let’s say an attacker partitions a victim’s mempool from the rest of network mempools thanks to maliciously conflicting transactions. E.g send non-rbf signaling, differing transactions to victim and all its tx-relay connected peers.

    Those malicious transactions are attached a feerate high-enough to completely occupy the m_attempt_tracker. Due to MIN_REATTEMPT_INTERVAL=4h and assuming 6 blocks per hour, it will require 6 * 4 * 500 = 12000 transactions to jam victim’s rebroadcast attempt. Of course, MAX_REBROADCAST_COUNT should upper bound such behavior, but an attacker can easily renew m_attempt_tracker jamming by RBFing the pinning transactions.

    Let’s assume malicious transactions size is MIN_STANDARD_TX_NONWITNESS_SIZE, so 82 bytes. Let’s assume top block feerate is 170 sat/vbyte. Shrugging at RBF replacement fee penalties, 12_000 * 82 * 170 = 167_280_000 sats. So a permanent m_attempt_tracker jamming would require 1,67 BTC available to the attacker, though not burnt if the mempool isolation is operated properly.

    Do the attack model seems sound to you ? If so I think we should carefully document risks of m_attempt_tracker pinning and likely scale up parameters value.


    amitiuttarwar commented at 9:51 pm on April 27, 2021:

    what is the fundamental resource that is being spent in this attack? are you evaluating the possibility of asymmetric bandwidth usage? if that’s the case then you also need to factor in rolling over filterInventoryKnown.

    also I don’t understand how the attacker avoids spending any funds- say A and A’ are two versions of the same txn via RBF. A is sent to the victim & A’ is sent to the rest of the network. according to the current patch, if A’ gets mined into a block, A is removed from the attempt tracker.

    update: wait, you refer to the bandwidth interactions with filterInventoryKnown in your comment #21061 (review), so then I must be missing what you are trying to describe in this attack.

    second update: is an assumption behind this hypothetical attack that jamming m_attempt_tracker would prevent a node from rebroadcasting? just want to clarify that rebroadcasts would work without the tracker, its mainly a technique to mitigate bandwidth usage.


    ariard commented at 4:20 pm on May 6, 2021:

    Thanks for the second clarifying update, effectively this is documented L124 in src/txrebroadcast.cpp, “No existing entry, we will rebroadcast, so create new one”.

    So IIUC, even if m_attempt_tracker is fulfilled with pinning transactions, it won’t block node rebroadcast capability. I think pinning costs of m_attempt_tracker above roughly above but it can’t be abused by an attacker to jam rebroadcasting, so we’re good.

    I would recommend to document this “pinning-doesn’t-block-rebroadcast-so-not-a-new-tx-relay jamming-vector” around m_attempt_tracker declaration in src/txreconciliation.h, it’s quite an important design aspect imo.

    W.r.t to asymmetric bandwidth usage and risks of bleeding, I don’t think m_attempt_tracker pinning is making it better or worst, I share the opinion we’re ultimately protected by filterInventoryKnown.

    I don’t understand how the attacker avoids spending any funds- say A and A’ are two versions of the same txn via RBF. A is sent to the victim & A’ is sent to the rest of the network. according to the current patch, if A’ gets mined into a block, A is removed from the attempt tracker.

    I should have precise this point. Transaction A feerate to successfully pin m_attempt_tracker must be at 170 sat/vbyte. However transaction A’ feerate just need to be above miners’mempools min feerates to block propagation of transaction A. If transaction A’ feerate is 2 sat/vbyte, with same equation laid out above, effective pinning cost for an attacker is 12_000 * 82 * 2 = 1_968_000 sats and not 167_280_000 sats. Miners observe and eventually mine transactions with a far lower-feerate than the ones maliciously sent to non-miner nodes. This is what I meant by “not burnt if the mempool isolation is operated properly”.


    amitiuttarwar commented at 7:17 pm on May 8, 2021:

    So IIUC, even if m_attempt_tracker is fulfilled with pinning transactions, it won’t block node rebroadcast capability.

    yeah, exactly.

    I would recommend to document this “pinning-doesn’t-block-rebroadcast-so-not-a-new-tx-relay jamming-vector” around m_attempt_tracker declaration in src/txreconciliation.h, it’s quite an important design aspect imo.

    I don’t think it makes sense to document what data structures don’t do.

    I should have precise this point…

    Ah I understand now, thanks for clarifying.

  118. amitiuttarwar force-pushed on Apr 16, 2021
  119. in src/txrebroadcast.cpp:27 in 7ae2e385b6 outdated
    22+
    23+/** Default minimum age for a transaction to be rebroadcast */
    24+static constexpr std::chrono::minutes REBROADCAST_MIN_TX_AGE{30min};
    25+
    26+/** Maximum number of times we will rebroadcast a transaction */
    27+static constexpr int MAX_REBROADCAST_COUNT{6};
    


    ariard commented at 10:38 pm on April 16, 2021:

    Assuming an entry’s m_count reaches MAX_REBROADCAST_COUNT, it should never be again selected by GetRebroadcastTransactions. At that point, should we return an event to the wallet logic inviting to RBF the transaction ?

    Otherwise, the entry should stale until deletion by TrimMaxRebroadcast. At that point should we return an event inviting to re-submit the same transaction ? Network mempools might have cleared up in between.

    I don’t know if this new rebroadcasting mechanism should be transparent or not to Bitcoin applications vetted with their own rebroadcasting logics.


    amitiuttarwar commented at 9:56 pm on April 27, 2021:

    At that point, should we return an event to the wallet logic inviting to RBF the transaction ?

    that’s a cool idea. I don’t think it is applicable yet, but I’ve noted it down for future work where it would be more relevant.

    why I don’t think it is applicable yet: as of this patch, ResendWalletTransactions still calls SubmitMemoryPoolAndRelay with the relay bool set to true (aka patch doesn’t change it). This gets used in BroadcastTransaction to force relaying the transaction to peers at the time of submission. in the future, the goal is to disable this (see “Merge Plan & Next Steps” in #21061 (comment)), at which time I believe this sort of mechanism would make sense.

  120. in src/txrebroadcast.cpp:37 in 7ae2e385b6 outdated
    32+
    33+/** The maximum number of entries permitted in m_attempt_tracker */
    34+static constexpr int MAX_ENTRIES{500};
    35+
    36+/** The maximum age of an entry ~3 months */
    37+static constexpr std::chrono::hours MAX_ENTRY_AGE{24h * 30 * 3};
    


    ariard commented at 10:48 pm on April 16, 2021:

    What’s the rational to pick up this value ?

    I don’t think Bitcoin applications care about confirmation of transactions broadcast 3 months ago. At the contrary, an attacker could use this really long expiration delay as a fingerprint vector.

    Let’s say in optimistic scenarios, a rebroadcast entry has a compelling feerate enough to be selected by GetRebroadcastTransactions after each MIN_REATTEMPT_INTERVAL, after 6 * 4, it’s matured enough to be legitimately expired ? Of course, we can assume some margin of error and double to 48h. Or even select MEMPOOL_EXPIRY as a maximum age. But I don’t understand the month-length delay…


    amitiuttarwar commented at 10:30 pm on April 27, 2021:

    I don’t understand this comment, let me explain some of the mechanisms incase that helps. otherwise, please help me understand what you are trying to communicate.

    I don’t think Bitcoin applications care about confirmation of transactions broadcast 3 months ago.

    1. the attempt tracker records the timestamp of when the mempool transaction was last selected for rebroadcast, not when it was initially broadcast / ATMPed (see https://github.com/bitcoin/bitcoin/pull/21061/files?file-filters%5B%5D=.cpp&file-filters%5B%5D=.h&file-filters%5B%5D=.py&file-filters%5B%5D=.sh#diff-7dff50848db96bdb8edffc4d21daeca6d9050ec0e67d96072780ea5751e7df06R110 and https://github.com/bitcoin/bitcoin/pull/21061/files?file-filters%5B%5D=.cpp&file-filters%5B%5D=.h&file-filters%5B%5D=.py&file-filters%5B%5D=.sh#diff-7dff50848db96bdb8edffc4d21daeca6d9050ec0e67d96072780ea5751e7df06R125).
    2. MAX_ENTRY_AGE is only called from TrimMaxRebroadcast. It is essentially used to say “if a transaction hasn’t been selected for rebroadcast in the past 3 months, remove it from the attempt tracker”

    Let’s say in optimistic scenarios, a rebroadcast entry has a compelling feerate enough to be selected by GetRebroadcastTransactions after each MIN_REATTEMPT_INTERVAL, after 6 * 4, it’s matured enough to be legitimately expired ?

    can you clarify what you mean by “legitimately expired”? if you mean that we should disable automatic rebroadcast so the txn can (probably) expire from the (majority of) network mempools, then yes I agree. which is why we put it on the tracker. but then, what is the question?

    select MEMPOOL_EXPIRY as a maximum age.

    if we stored transactions on the attempt tracker for the same duration as MEMPOOL_EXPIRY time, that would leave room for the issue that the attempt tracker is meant to address. for more explanation on that, please see https://github.com/amitiuttarwar/bitcoin-notes/blob/main/rebroadcast-history.md#faq section “What happens if a transaction can / will never be mined?”. expiry would be one of the main ways to get the ping-ponging behavior for never-going-to-be-mined transactions (eg. due to a policy upgrade on the network).


    ariard commented at 5:08 pm on May 6, 2021:

    IIRC, by “legitimately expired” I meant a transaction of which m_count has reached MAX_REBROADCAST_COUNT. As we already rebroadcasted this transaction the maximum number of times permitted, we skip its rebroadcasting forever, but without necessarily removing it from m_attempt_tracker ? I think such transaction has exhausted its rebroadcast “credit” and it’s mature enough to be “legitimately” expired or pruned. Though this deletion criteria isn’t currently considered in TrimMaxRebroadcast() ?

    I think this deletion criteria would be more efficient to expire transactions from the majority of network mempools rather than MAX_ENTRY_AGE, especially with a 3 months delay.

    if we stored transactions on the attempt tracker for the same duration as MEMPOOL_EXPIRY time, that would leave room for the issue that the attempt tracker is meant to address. for more explanation on that, please see https://github.com/amitiuttarwar/bitcoin-notes/blob/main/rebroadcast-history.md#faq section “What happens if a transaction can / will never be mined?”. expiry would be one of the main ways to get the ping-ponging behavior for never-going-to-be-mined transactions (eg. due to a policy upgrade on the network)

    IIUC, the problem we’re trying to solve is “How to avoid never-going-to-be-mined transactions to forever ping-pong across the network ?”.

    To achieve this aim, I believe we should expire a rebroadcast entry as soon as it has exhausted its rebroadcast count, a hint that either feerate is definitively aloof or severer circumstances as described in documentation. But selecting a MAX_ENTRY_AGE superior to MEMPOOL_EXPIRY moves in the opposite direction.

    If rebroadcast entry average rebroadcast interval is superior to 56 hours, 56 * MAX_REBROADCAST_COUNT== MEMPOOL_EXPIRY and node rebroadcast guarantees attempts beyond the mempool expiration limit ?

    Or is the behavior I’m describing not possible ? I’m happy to illustrate with a test to assert our intuitions :)

    update: Or is the purpose of keeping rebroadcast entry with m_count == MAX_REBROADCAST_COUNT and only expire them when last_attempt is older than MAX_ENTRY_AGE prevent new registration in m_attempt_tracker cache provoked by rebroadcast from other network mempools ? Thus you expect a transaction to expire from mempools after MEMPOOL_EXPIRY, then to avoid network laggards with differing policy to trigger new rebroadcasting wawes, you have MAX_ENTRY_AGE as an upper bound of MEMPOOL_EXPIRY ?

    Okay I can see how it solves mempool ping-pong though reasoning could be better documented and still we should envisage to reduce MAX_ENTRY_AGE to minimize node fingerprinting.


    amitiuttarwar commented at 2:14 am on May 9, 2021:

    it seems like the majority of this comment is based on a misunderstanding of how m_attempt_tracker works.

    the update seems like its getting on the right track- the main purpose of tracking rebroadcast entries is to allow enforcing a maximum number of rebroadcast attempts.

    IIUC, the problem we’re trying to solve is “How to avoid never-going-to-be-mined transactions to forever ping-pong across the network ?”.

    yes, exactly.

    but it still seems like there is remaining confusion. MAX_ENTRY_AGE indicates the amount of time has passed since tx A has been rebroadcast to peers. if its been 3 months since we last tried to rebroadcast tx A, we remove the attempts from the tracker. if there is no entry for tx A on the tracker, we don’t have record of the fact that we tried to rebroadcast it, so if tx A is selected by the block assembler, we would rebroadcast it again.

    I don’t see how MAX_ENTRY_AGE would viably be used for node fingerprinting when you combine with the other factors such as filterInventoryKnown.

  121. in src/Makefile.am:240 in 7ae2e385b6 outdated
    225@@ -226,6 +226,7 @@ BITCOIN_CORE_H = \
    226   txdb.h \
    227   txmempool.h \
    228   txorphanage.h \
    229+  txrebroadcast.h \
    230   txrequest.h \
    231   undo.h \
    


    78051301012 commented at 10:49 pm on April 16, 2021:
    0  txdb.h \
    1  txmempool.h \
    2  txorphanage.h \
    3  txrebroadcast.h \
    4  txrequest.h \
    5  undo.h \
    

    amitiuttarwar commented at 10:53 pm on April 16, 2021:
    is there a suggestion here?
  122. in src/net_processing.cpp:1293 in 7ae2e385b6 outdated
    1285@@ -1283,22 +1286,57 @@ PeerManagerImpl::PeerManagerImpl(const CChainParams& chainparams, CConnman& conn
    1286     // same probability that we have in the reject filter).
    1287     m_recent_confirmed_transactions.reset(new CRollingBloomFilter(48000, 0.000001));
    1288 
    1289+    if (enable_rebroadcast) {
    1290+        m_txrebroadcast = std::make_unique<TxRebroadcastHandler>(m_mempool, m_chainman, m_chainparams);
    1291+
    1292+        // Run fee rate cache every minute
    1293+        scheduler.scheduleEvery([this] { m_txrebroadcast->CacheMinRebroadcastFee(); }, std::chrono::minutes{1});
    


    ariard commented at 10:54 pm on April 16, 2021:

    Have you tried to run this branch on mainet with a wide-sized mempool ? I think there is a logger in CacheMinRebroadcastFee, do you have stats to share on how much time it take by attempts ?

    Not sure if the block min feerate accuracy is worth the CPU time…


    amitiuttarwar commented at 6:30 pm on April 17, 2021:

    yup, here are some values are for running the whole function. Note that it does not distinguish CPU time vs time spent waiting to acquire the lock, as it currently acquires cs_main and mempool.cs, but the first might be unnecessary (see #21061 (review)):

    the median value is 9090 μs, with 75% of the runs being under 11300 μs, and 99% of the run being under 11826 μs.

    Not sure if the block min feerate accuracy is worth the CPU time…

    its a pretty critical component to this approach, without it the node would most likely be attempting to rebroadcast MAX_REBROADCAST_WEIGHT of transactions on every block.


    ariard commented at 3:26 pm on April 21, 2021:

    the median value is 9090 μs, with 75% of the runs being under 11300 μs, and 99% of the run being under 11826 μs.

    Okay and with a fulfilled mempool of the default size 300 MiB ? If yes I agree that’s not that much and I think we’re relieved on this concern :) If it does causes issues on low-grade nodes in the future, due to non-linear scaling of the CPU time in function of mempool size, I guess we’ll be able to make this value configurable, offering a trade-off between CPU and bandwidth to node operators.

    its a pretty critical component to this approach, without it the node would most likely be attempting to rebroadcast MAX_REBROADCAST_WEIGHT of transactions on every block.

    Do you mean without it or with a lower frequency rather than 1 min ? IIUC, the node would attempt to rebroadcast MAX_REBROADCAST_WEIGHT because you don’t account for the fresh arrivals of new transactions. The feerate of those newcomers making most of your rebroadcast candidates irrelevant to block confirmation ? If refreshing the cache was costly, I guess we would run it once between expected block intervals when the odds of having discovered enough new transactions to have a consistent view of next block are high. But cost is pretty low, so I don’t think we care further…

    nit: maybe replace 1 by a named constant like CACHE_REBROADCAST_FEERATE_FREQUENCY ?


    amitiuttarwar commented at 10:36 pm on April 27, 2021:

    Okay and with a fulfilled mempool of the default size 300 MiB ? If yes I agree that’s not that much and I think we’re relieved on this concern :)

    my mempool is bumped up to 1000MiB, so these are values for a significantly-larger-than-normal mempool :)

    I guess we’ll be able to make this value configurable

    yup, rebroadcast currently defaults off, but the plan is to keep this toggle in the long run to address any bandwidth concerns.


    amitiuttarwar commented at 0:03 am on April 28, 2021:

    maybe replace 1 by a named constant like CACHE_REBROADCAST_FEERATE_FREQUENCY

    done

  123. in src/txrebroadcast.cpp:205 in 7ae2e385b6 outdated
    179+        } else {
    180+            break;
    181+        }
    182+    }
    183+
    184+    // If there are still too many entries, delete the oldest ones
    


    ariard commented at 10:58 pm on April 16, 2021:
    I think a deletion criteria which might applied before age is delaying if m_count == MAX_REBROADCAST_COUNT. A transaction might be the oldest one but still feerate compelling and was unlucky on its previous rebroadcast attempts ?

    amitiuttarwar commented at 10:59 pm on April 27, 2021:

    hm, then what do you propose as the method to ensure old attempts expire from the tracker?

    keep in mind that the time is updated every time a transaction is selected to be rebroadcast.

    that said, there still could be the case that the transaction is very high fee rate but hasn’t been rebroadcast in a long time because it hit the MAX_REBROADCAST_COUNT. if this is the concern, we could address that by re-ordering the if / else logic in GetRebroadcastTransactions and update the timestamp if a transaction is being considered to rebroadcast, but filtered due to having hit the max. this way they would stay recent and we could continue with the same deletion logic.


    ariard commented at 5:21 pm on May 6, 2021:

    Do we agree first on the problem solved by m_attempt_tracker ? See new comment : #21061 (review)

    What we want to do in TrimMaxRebroadcast() is pending on this conversation imo.


    amitiuttarwar commented at 2:15 am on May 9, 2021:
    ok, going to resolve this conversation here in favor of the other comment thread.
  124. in src/txrebroadcast.h:62 in 7ae2e385b6 outdated
    54+
    55+    /** Block at time of cache */
    56+    CBlockIndex* m_tip_at_cache_time{nullptr};
    57+
    58+    /** Minimum fee rate for package to be included in block */
    59+    CFeeRate m_cached_fee_rate;
    


    ariard commented at 11:00 pm on April 16, 2021:
    Not exactly to be included in a block as we overprice its weight with MAX_REBROADCAST_WEIGHT ?

    amitiuttarwar commented at 2:45 pm on April 17, 2021:
    we apply MAX_REBROADCAST_WEIGHT for calculating the set of candidates when it is time to rebroadcast, not for calculating the minimum fee rate
  125. in src/txrebroadcast.h:69 in 7ae2e385b6 outdated
    64+     *  that will never be mined. Two examples:
    65+     *  1. A software upgrade tightens policy, but the node has not been
    66+     *  upgraded and thus is accepting transactions that other nodes on the
    67+     *  network now reject.
    68+     *  2. An attacker targets the network by sending conflicting transactions
    69+     *  to nodes based on their distance from a miner.
    


    ariard commented at 11:06 pm on April 16, 2021:
    I don’t understand how victim’s node distance from miner mempools make it easier or harder to successfully conflict. Of course, you can assume that few miner mempools are running full-rbf and as such you can’t leverage lack of rbf signaling as a tx-relay jamming vector but a) require victim to be strict neighbor of miner and b) attacker can exploit other relay policies differences, i.e non taproot spend allowed ?

    amitiuttarwar commented at 7:31 pm on April 17, 2021:

    I don’t understand how victim’s node distance from miner mempools make it easier or harder to successfully conflict

    I’m not suggesting it is??


    ariard commented at 2:58 pm on April 21, 2021:
    So what are you suggesting is how a victim node distance from a miner enters into attacker motivation to target it ? Otherwise, I would suggest just drop “distance from a miner” part, I’m not sure if it significant information here.

    amitiuttarwar commented at 11:20 pm on April 27, 2021:
    I’m unable to parse your question. Although I think it helps motivate the attack, I’ll drop the end of the sentence.

    amitiuttarwar commented at 0:04 am on April 28, 2021:
    updated to 2. An attacker targets the network by sending conflicting transactions to nodes.

    ariard commented at 2:26 pm on May 6, 2021:
    Thanks, my question was simply “Why a node distance from a miner helps to motivate the attack ?”
  126. in src/txrebroadcast.cpp:31 in 7ae2e385b6 outdated
    26+/** Maximum number of times we will rebroadcast a transaction */
    27+static constexpr int MAX_REBROADCAST_COUNT{6};
    28+
    29+/** Minimum amount of time between returning the same transaction for
    30+ * rebroadcast */
    31+static constexpr std::chrono::hours MIN_REATTEMPT_INTERVAL{4h};
    


    ariard commented at 11:18 pm on April 16, 2021:

    I think you should document somewhere how filterInventoryKnown is mitigating bandwidth attacks as described by gmaxwell in your notes. Even if you can pin m_attempt_tracker permanently or for a while, most of reattempt should be ended up by being passed over and won’t consume again INV bandwidth.

    Though you may roll over a majority of network nodes’s filterInventoryKnown with cheap-RBF replacement ? Dunno if anyone has already done the math, but it might be interesting to know them for this PR…


    amitiuttarwar commented at 11:25 pm on April 27, 2021:
    this comment seems to have a lot of overlap with the one you left here: #21061 (review). I don’t understand exactly what you mean by “cheap-RBF replacement”. I’m going to resolve this conversation, but we can continue the topic in that other thread.

    ariard commented at 5:38 pm on May 6, 2021:

    See second half of other comment answer on why you can consider RBF cheap for an attacker. More generally there is also the fact that the bip125 replacement penalty is static (DEFAULT_INCREMENTAL_RELAY_FEE) is static and doesn’t scale up in function of your mempool congestion.

    Simplify fee-bumping algorithms a lot though at the price of bandwidth overcost for network nodes processing replacement…

    W.r.t to filterInventoryKnown, a malicious roll over isn’t new from introducing node rebroadcast logic, though from now this module make assumptions on it to prevent bandwidth bleeding.

  127. in src/init.cpp:452 in 7ae2e385b6 outdated
    457@@ -458,6 +458,7 @@ void SetupServerArgs(NodeContext& node)
    458     argsman.AddArg("-port=<port>", strprintf("Listen for connections on <port>. Nodes not using the default ports (default: %u, testnet: %u, signet: %u, regtest: %u) are unlikely to get incoming connections.", defaultChainParams->GetDefaultPort(), testnetChainParams->GetDefaultPort(), signetChainParams->GetDefaultPort(), regtestChainParams->GetDefaultPort()), ArgsManager::ALLOW_ANY | ArgsManager::NETWORK_ONLY, OptionsCategory::CONNECTION);
    459     argsman.AddArg("-proxy=<ip:port>", "Connect through SOCKS5 proxy, set -noproxy to disable (default: disabled)", ArgsManager::ALLOW_ANY, OptionsCategory::CONNECTION);
    460     argsman.AddArg("-proxyrandomize", strprintf("Randomize credentials for every proxy connection. This enables Tor stream isolation (default: %u)", DEFAULT_PROXYRANDOMIZE), ArgsManager::ALLOW_ANY, OptionsCategory::CONNECTION);
    461+    argsman.AddArg("-rebroadcast", strprintf("Enable node rebroadcast functionality (default: %u)", DEFAULT_REBROADCAST_ENABLED), ArgsManager::ALLOW_BOOL | ArgsManager::DEBUG_ONLY, OptionsCategory::CONNECTION);
    


    ariard commented at 11:30 pm on April 16, 2021:

    I think for rational 2) to hold (“If a spy observes a bitcoin core node rebroadcasting a transaction, it would no longer know that the node has wallet enabled”), you need bandwidth increase from rebroadcast set to be low enough for not being a burden to a wide majority of node operators. Otherwise, a privacy attacker can still guess with high success that only node operators with an associated wallet will activate rebroadcasting.

    Is the longer plan to activate it by default ? If so we should have really good real-world data and I think consensus of what’s an acceptable bandwidth increase for the alleged benefits.


    amitiuttarwar commented at 6:36 pm on April 17, 2021:
    agree that we don’t want rebroadcast to have high bandwidth requirements. the longer plan is to activate it by default after building confidence about resource usage. please see Merge Plan & Next Steps.
  128. amitiuttarwar commented at 11:31 pm on April 16, 2021: contributor

    thank you all SO MUCH for these reviews 🙌🏽 I believe I have addressed all outstanding review comments 🎉 I have one more piece of functionality I’d like to implement in this patch (link), but otherwise everything in this PR should be current and ready for further review.

    My next step is to develop a patch for more insightful monitoring. I’ve been running this patch on mainnet for the past 2 weeks, and have seen results very similar to what aj reported in this comment. However, my main curiosity is how many of these transactions queued for rebroadcast 1. actually get inved to the network & 2. are subsequently requested via a getdata? Once I’ve written that, I’ll share here incase anyone else is interested in running.

    A couple more conceptual responses: @0xB10C really cool that you’re doing a very similar comparison, I’d be curious to learn more about how this patch compares to what you are running. I agree that the attempt tracker will mitigate & cap the worst case of something like this. @vasild it seems like your questions are highlighting two tensions that we are aiming to strike a balance between:

    1. privacy vs propagation
    2. propagation vs bandwidth

    While this patch uses getblocktemplate logic as a starting point for identifying which transactions to attempt to rebroadcast, there is a lot of nuance to ensure that we don’t waste bandwidth (such as the attempt tracker). I’d suggest looking at the GetRebroadcastTransaction function (link) to see the various filters being applied. However, after they are selected, they will also need to pass through filterInventoryKnown before they actually make it as a network message. The monitoring I mentioned above will help us observe the numbers around that.

    If we find that the number of transactions currently being rebroadcast is too high, the suggestion of looking at the last N blocks seems like a good approach :)

  129. ariard commented at 0:15 am on April 17, 2021: member

    Beyond comments, I’ve still have a high-level concern about how this new rebroadcasting mechanism is servicing custom rebroadcasting logics. A lot of second-layers nodes and more and more Bitcoin applications have their own RBF-able rebroadcast logics, with their own frequencies and attempt limits. This new mechanism doesn’t serve them well as their rebroadcast logics are going to leak a behavior breaking from the anonymous sets constituted by m_attempt_tracker. Assuming those differing rebroadcast logics are using sendrawtransaction, I don’t think it’s realistic to assume that filterInventoryKnown will protect them here, an attacker can renew its inbound connection quite quickly forcing the victim node to cleanup corresponding malicious peer filter ?

    Those node operators won’t be incentivized to turn on this mechanism. We have already a 10k contingent of Lightning nodes against ~100k full-nodes ? Few years from now, we might have only a small minority of network nodes rebroadcasting thus severely minimizing benefits of motivation 2)

    Another concern, I think this PR is making the assumption that big-sized node mempools will serve as some sort of transaction archives for the rest of the network by rebroadcasting a-week-ago-or-month-ago bottom of mempools now feerate compelling for block inclusion ? I believe we should let Bitcoin applications be responsible of rescheduling their utxo claims, it’s less complexity for full-nodes and prevent subtle issues. I.e a client might be interested to cheaply double-spend a utxo once the first spend has reached MEMPOOL_EXPIRY but could be now accidentally jammed by this new rebroadcast mechanism ?

    Further, I would attend a more detailed privacy attacker model, we might have other privacy-preserving rebroadcast strategies with cheaper bandwidth trade-offs. E.g, one-shot tx-relay peer with aggressive rotation between rebroadcast attempts, and tracking that announced-to peers belong to different netgroups. Such rebroadcast strategy might suit better custom rebroadcast logics mentioned as first concern. Of course, we could support different ones, just at the price of smaller anonymous sets…

    That said, I agree that this work is an obvious privacy improvement for Core wallet rebroadcast, I just fear we have more interactions to weigh in that might appear at first sight.

  130. DISC30 commented at 5:19 am on April 21, 2021: none
    Hey @amitiuttarwar what is the best way to pay you for the work you have done? I don’t have BTCPay but can do static address or paypal.
  131. fjahr commented at 1:25 pm on April 25, 2021: member
    I haven’t followed the project in detail over the past few months and might have missed some discussions on this aspect, so forgive me if this is a stupid question: The issues around nodes that use this new module but are not aware of a new softfork were discussed in the review club and also that m_attempt_tracker seems to resolve the issue. But it seems this could be exploited by an attacker at almost zero cost, spamming these nodes with such txs that are high fee but invalid under the new rules. Has this already been discussed somewhere? I haven’t thought about it much but maybe rebroadcast should ignore txs with anyone-can-spend outputs?
  132. amitiuttarwar force-pushed on Apr 28, 2021
  133. ajtowns commented at 11:45 am on April 29, 2021: member

    But it seems this could be exploited by an attacker at almost zero cost, spamming these nodes with such txs that are high fee but invalid under the new rules.

    If the txs are invalid under the new rules no node will accept them – new nodes won’t because they’ll be invalid, old nodes won’t because anything covered by the new rules is non-standard so not acceptable to the mempool/for relay.

    The spam case is for txs that are only valid under the new rules, but miners aren’t bothering to mine any txs that use the new rules – in that case all the nodes running the new rules will rebroadcast them to everyone regularly – but that’s limited by expiry (each tx can only be rebroadcast so many times), inventory known (won’t inv the same thing until it expires from the bloom filter), and (hopefully) by some miner creating blocks with txs that follow the new rules.

  134. amitiuttarwar force-pushed on May 4, 2021
  135. amitiuttarwar force-pushed on May 5, 2021
  136. amitiuttarwar force-pushed on May 5, 2021
  137. amitiuttarwar commented at 8:35 pm on May 5, 2021: contributor

    I believe all review comments are now addressed (including the explanations below) 🎈

    Some updates about the latest push:

    • The rebroadcast logic now mines a block with a weight of 3/4 weight-of-incoming-block instead of 3/4 weight-of-maximum-block, to reduce bandwidth spikes
    • Rebased on master to resolve a silent merge conflict
    • We now store the last two values for the fee-rate cache, so we can use the previous if there has been a run since the block came in

    One more note- looks like the latest push has caused a lock-order failure in the TSan build. I will address this soon!

    Also, I’ve been monitoring the code using this branch. In addition to a bunch of rebroadcast specific logging, the top commit adds two RPC endpoints: getrebroadcastinfo and getgeneralbroadcastinfo which reports counts of # of times we do events such as sending INVs and receiving GETDATAs.

    Here are a couple observations:

    • The patch has been running on my node with a huge mempool. I have feefilter: 0, maxmempool: 1000, mempoolexpiry:17520 (approx 2 years), and minrelaytxfee: 0, along with inbound connections enabled.
    • After running for a couple days, the rebroadcast INV:GETDATA ratio was 11-12:1, while the general ratio was 35-40:1. As the node ran for longer, both of these ratios have been reducing. After running for ~8 days, the rebroadcast ratio has been hovering around 9:1, and the general broadcast ratio has dropped to ~12:1.
    • The number of transactions identified for rebroadcast is very spiky, its often 0, or will hop up to 100-150 on a particular block. The latest push has changed the maximum weight to reflect the incoming block, so I’m curious to see

    If anyone is interested in reviewing or running the monitoring code, that would be awesome! I’d love to gather more data :)


    @fjahr

    But it seems this could be exploited by an attacker at almost zero cost, spamming these nodes with such txs that are high fee but invalid under the new rules.

    Hm, so indeed an attacker could essentially nullify the utility of a mempool by spamming old nodes with now-policy-invalid transactions, but this is already the case.

    In relation to this PR, we want to make sure we don’t worsen, or automate that behavior. So m_attempt_tracker ensures that there are bounds on the number of times & frequency that we will rebroadcast any particular transaction. Combined with the filterInventoryKnown functionality, we can have some guarantees around bandwidth usage, especially asymmetric bandwidth usage, that nodes will have under normal or malicious worst case scenarios. However, I am not aiming to fix the existing issue around policy upgrades and attack vectors.

    Does this help / make sense? @ariard

    A lot of second-layers nodes and more and more Bitcoin applications have their own RBF-able rebroadcast logics, with their own frequencies and attempt limits. This new mechanism doesn’t serve them well as their rebroadcast logics are going to leak a behavior breaking from the anonymous sets constituted by m_attempt_tracker.

    I don’t understand what you are trying to say here. I don’t find it unexpected or undesirable for various applications, users, companies to run custom rebroadcast logic. I also don’t understand why you say that m_attempt_tracker is creating an anonymity set- it mostly serves as a way to mitigate frequently rebroadcasting any particular transaction, not the technique we use to identify rebroadcasts.

    Another concern, I think this PR is making the assumption that big-sized node mempools will serve as some sort of transaction archives for the rest of the network by rebroadcasting a-week-ago-or-month-ago bottom of mempools now feerate compelling for block inclusion ?

    Yes I think that’s a fair way of looking at the long picture vision.

    Further, I would attend a more detailed privacy attacker model, we might have other privacy-preserving rebroadcast strategies with cheaper bandwidth trade-offs…

    I agree that there are many possibilities & that it would be beneficial to have a more specific breakdown of privacy assumptions & guarantees. However, I don’t think that we should gate concrete improvements on theoretically infinite problem spaces. I believe that the changes proposed in this PR & the intended direction of this project offer concrete, auditable improvements to privacy around 3rd parties deducing the source wallet of a transaction. @DISC30 thanks for the offer, I don’t think this PR is the right place to discuss, so I emailed you (based on the email in your github).

  138. ariard commented at 6:22 pm on May 6, 2021: member

    @amitiuttarwar

    I don’t understand what you are trying to say here. I don’t find it unexpected or undesirable for various applications, users, companies to run custom rebroadcast logic.

    I think the problem this work is alleguing to solve is “How to improve Bitcoin Core Wallet rebroadcast privacy”. The solution proposed is to rebroadcast any transaction identified as missing from a block based on feerate expectations. This new behavior is justifying to improve privacy for the following reason “If a spy observes a bitcoin core node rebroadcasting a transaction, it would not longer know that the node has wallet enabled” among others. I believe we agree this assumption is function of node rebroadcasting module being activated by default.

    However, and that’s my point, a lot of full-nodes are hosting Bitcoin applications with custom rebroadcast logic, and this trend is likely to increase in the future. So those full-nodes operators, with custom rebroadcast logics and not using the bitcoin core wallet, won’t be incentivized to activate by default node rebroadcasting as it doesn’t enhance privacy of their transactions. For this reason, improvement of Bitcoin Core wallet rebroadcast privacy as alleged by this work might reveal a tight upper bound in the future, under our optimistic intuitions. To be more concrete, if only 5% of node operators activate the node rebroadcast module, it won’t offer the same level of rebroadcast privacy that if it’s activated on 80% of the network IMHO.

    I believe we should address this concern before to propose default activation of this module in the future, or at least gauge bandwidth increases are insignificant to be borne by default. I’ll try to run the patch soon to help there :)

    Again, as I noticed in my previous comment, this work is of course a valuable privacy improvement for Bitcoin Core wallet users, or any Bitcoin software with the same rebroadcast strategy.

    I also don’t understand why you say that m_attempt_tracker is creating an anonymity set- it mostly serves as a way to mitigate frequently rebroadcasting any particular transaction, not the technique we use to identify rebroadcasts.

    IIUC, a transaction is selected for rebroadcast if it passes block min feerate, reattempt interval and max reattempt count. However those 2 late checks aren’t applied if the transaction isn’t a rebroadcast entry. So m_attempt_tracker and its content is part of the logic determining the rebroadcast set. From an attacker viewpoint, this rebroadcast set constitutes an anonymity set. Yes m_attempt_tracker isn’t a technique to identify rebroadcast but it’s used to filter them. Though I agree, for clarify of conversation, it would have been easier to employ as a term node rebroadcast logic.

    I agree that there are many possibilities & that it would be beneficial to have a more specific breakdown of privacy assumptions & guarantees. However, I don’t think that we should gate concrete improvements on theoretically infinite problem spaces. I believe that the changes proposed in this PR & the intended direction of this project offer concrete, auditable improvements to privacy around 3rd parties deducing the source wallet of a transaction.

    And I share the same feeling, we would be better off not traversing an infinite problem space. Though, unless you propose an efficient problem space traversal algorithm, we’re left with raising and proceeding problem if relevant one by one :/ FYI, IETF does have such design questions checklist about Internet protocols (see https://www.rfc-editor.org/rfc/rfc3426.html), though ofc not suiting per se Bitcoin space. Otherwise, I would recall that this project history showed us “concrete improvements” not solving the privacy issues alleged while introducing subtle DoS issues (e.g bloom filters)

  139. michaelfolkson commented at 7:01 pm on May 6, 2021: contributor

    @ariard: To summarize, I think what you are concerned with is the rebroadcast privacy offered by this module to nodes that are using it assuming only a minority (perhaps a small minority) of the network is using it. This module is currently off by default and according to you (I have no reason to doubt you) a significant proportion of the network is already running custom rebroadcast logic.

    To me it appears nodes that choose to use the module benefit and nodes that aren’t using it aren’t negatively impacted. As long as that is true (and you agree with that) it doesn’t matter if only a (small) minority are using it? (Of course in time there could be a lot more than a small minority of the network using it.) Or is your concern with nodes that choose to use this module when they really shouldn’t be using it?

  140. ghost commented at 0:29 am on May 7, 2021: none

    However, and that’s my point, a lot of full-nodes are hosting Bitcoin applications with custom rebroadcast logic, and this trend is likely to increase in the future

    Interesting. Can you please share few examples?

  141. in src/txrebroadcast.cpp:86 in 343e3cbb3a outdated
    81+    auto start_time = GetTime<std::chrono::microseconds>();
    82+
    83+    int rebroadcast_block_weight = MAX_REBROADCAST_WEIGHT;
    84+    CBlock block;
    85+    const Consensus::Params& consensus_params = m_chainparams.GetConsensus();
    86+    if (ReadBlockFromDisk(block, recent_block_index, consensus_params)) {
    


    jnewbery commented at 8:55 am on May 7, 2021:
    It seems a shame to add a disk read here (which gets called in net_processing’s UpdatedBlockTip() callback). We could avoid this by updating the UpdatedBlockTip() signature function to also pass a const std::shared_ptr<const CBlock> &block in the same way that BlockConnected() does. It could also just pass the weight of the new block, but that seems strangely specific for the validation interface. What do you think?

    amitiuttarwar commented at 3:51 am on May 13, 2021:
    yeah, I went through a similar thought process. In the initial pass, I opted for the ReadBlockFromDisk approach because it seemed simpler. But in the latest push, I updated the UpdateBlockTip function signature to also take in block. Unfortunately, it seems like callers cannot rely on block to be properly populated, so I still need to have the ReadBlockFromDisk as a fallback. The relevant code is in 33eb966d284bd954af16ed5905315e0bc91c3662 & 33eb966d284bd954af16ed5905315e0bc91c3662, let me know what you think.
  142. in src/net_processing.cpp:1293 in 343e3cbb3a outdated
    1288@@ -1286,22 +1289,57 @@ PeerManagerImpl::PeerManagerImpl(const CChainParams& chainparams, CConnman& conn
    1289     // same probability that we have in the reject filter).
    1290     m_recent_confirmed_transactions.reset(new CRollingBloomFilter(48000, 0.000001));
    1291 
    1292+    if (enable_rebroadcast) {
    1293+        m_txrebroadcast = std::make_unique<TxRebroadcastHandler>(m_mempool, m_chainman, m_chainparams);
    


    jnewbery commented at 9:11 am on May 7, 2021:

    This could go in the initializer list:

     0diff --git a/src/net_processing.cpp b/src/net_processing.cpp
     1index 9a7bc8efd3..79897845d3 100644
     2--- a/src/net_processing.cpp
     3+++ b/src/net_processing.cpp
     4@@ -337,7 +337,7 @@ private:
     5     ChainstateManager& m_chainman;
     6     CTxMemPool& m_mempool;
     7     TxRequestTracker m_txrequest GUARDED_BY(::cs_main);
     8-    std::unique_ptr<TxRebroadcastHandler> m_txrebroadcast;
     9+    const std::unique_ptr<TxRebroadcastHandler> m_txrebroadcast;
    10 
    11     /** The height of the best chain */
    12     std::atomic<int> m_best_height{-1};
    13@@ -1271,6 +1271,7 @@ PeerManagerImpl::PeerManagerImpl(const CChainParams& chainparams, CConnman& conn
    14       m_banman(banman),
    15       m_chainman(chainman),
    16       m_mempool(pool),
    17+      m_txrebroadcast{enable_rebroadcast ? std::make_unique<TxRebroadcastHandler>(m_mempool, m_chainman, m_chainparams) : nullptr},
    18       m_stale_tip_check_time(0),
    19       m_ignore_incoming_txs(ignore_incoming_txs)
    20 {
    21@@ -1289,9 +1290,7 @@ PeerManagerImpl::PeerManagerImpl(const CChainParams& chainparams, CConnman& conn
    22     // same probability that we have in the reject filter).
    23     m_recent_confirmed_transactions.reset(new CRollingBloomFilter(48000, 0.000001));
    24 
    25-    if (enable_rebroadcast) {
    26-        m_txrebroadcast = std::make_unique<TxRebroadcastHandler>(m_mempool, m_chainman, m_chainparams);
    27-
    28+    if (m_txrebroadcast) {
    29         // Run fee rate cache every minute
    30         scheduler.scheduleEvery([this] { m_txrebroadcast->CacheMinRebroadcastFee(); }, REBROADCAST_CACHE_FREQUENCY);
    31     }
    32[john] /home/john/Code/crypto/bitcoin
    

    That allows you to make the m_txrebroadcast member const (which means that there can’t possibly be any data races on setting/reading the pointer).


    amitiuttarwar commented at 3:52 am on May 13, 2021:
    very nice, done
  143. in src/net_processing.cpp:1295 in 343e3cbb3a outdated
    1288@@ -1286,22 +1289,57 @@ PeerManagerImpl::PeerManagerImpl(const CChainParams& chainparams, CConnman& conn
    1289     // same probability that we have in the reject filter).
    1290     m_recent_confirmed_transactions.reset(new CRollingBloomFilter(48000, 0.000001));
    1291 
    1292+    if (enable_rebroadcast) {
    1293+        m_txrebroadcast = std::make_unique<TxRebroadcastHandler>(m_mempool, m_chainman, m_chainparams);
    1294+
    1295+        // Run fee rate cache every minute
    


    jnewbery commented at 9:12 am on May 7, 2021:
    Don’t put the value (minute) in this comment. If the constant is updated at some point in the future, this comment will become outdated. In fact, I think this comment can be removed entirely. The code is pretty self-documenting.

    amitiuttarwar commented at 3:52 am on May 13, 2021:
    agree, removed.
  144. in src/txrebroadcast.cpp:128 in 343e3cbb3a outdated
    104+        }
    105+    }
    106+
    107+    // Use CreateNewBlock to identify rebroadcast candidates
    108+    auto block_template = BlockAssembler(m_chainman.ActiveChainstate(), m_mempool, m_chainparams, options)
    109+                              .CreateNewBlock(CScript());
    


    jnewbery commented at 9:21 am on May 7, 2021:
    It’d be really nice if BlockAssembler could be extracted so that rebroadcast doesn’t have dependencies on the mining-specific code. That would allow you to remove m_chainman.ActiveChainstate(), m_chainparams and CScript() from this call.

    amitiuttarwar commented at 3:54 am on May 13, 2021:
    yeah, that would be nice! I don’t think it makes sense to increase the complexity of this PR, but I have noted it down as potential future work.
  145. in src/txrebroadcast.cpp:80 in 343e3cbb3a outdated
    75+      m_chainparams(chainparams),
    76+      m_attempt_tracker{std::make_unique<indexed_rebroadcast_set>()}{}
    77+
    78+std::vector<TxIds> TxRebroadcastHandler::GetRebroadcastTransactions(const CBlockIndex* recent_block_index)
    79+{
    80+    std::vector<TxIds> rebroadcast_txs;
    


    jnewbery commented at 9:27 am on May 7, 2021:
    Maybe move this initialization down to below the call to CNB (just above the main for loop in this function where rebroadcast_txs is used), and then call reserve to the size of block_template->block.vtx so that we don’t to multiple reallocations)

    amitiuttarwar commented at 3:54 am on May 13, 2021:
    done
  146. in src/txrebroadcast.h:33 in 343e3cbb3a outdated
    28+    ~TxRebroadcastHandler();
    29+
    30+    TxRebroadcastHandler(const TxRebroadcastHandler& other) = delete;
    31+    TxRebroadcastHandler& operator=(const TxRebroadcastHandler& other) = delete;
    32+
    33+    std::vector<TxIds> GetRebroadcastTransactions(const CBlockIndex* recent_block_index);
    


    jnewbery commented at 9:58 am on May 7, 2021:
    Could this be a const CBlockIndex& rather than pointer? ReadBlockFromDisk() unconditionally dereferences the pointer, so it can’t be null.

    amitiuttarwar commented at 3:55 am on May 13, 2021:
    done
  147. in src/txrebroadcast.cpp:230 in 343e3cbb3a outdated
    187+    if (it == m_attempt_tracker->end()) return;
    188+    m_attempt_tracker->erase(it);
    189+}
    190+
    191+void TxRebroadcastHandler::TrimMaxRebroadcast()
    192+{
    


    jnewbery commented at 10:21 am on May 7, 2021:
    Maybe add an assertion that m_attempt_tracker is held.

    amitiuttarwar commented at 3:56 am on May 13, 2021:
    done
  148. in src/txrebroadcast.cpp:234 in 343e3cbb3a outdated
    191+void TxRebroadcastHandler::TrimMaxRebroadcast()
    192+{
    193+    // Delete any entries that are older than MAX_ENTRY_AGE
    194+    auto min_age = GetTime<std::chrono::microseconds>() - MAX_ENTRY_AGE;
    195+
    196+    while (!m_attempt_tracker->empty()) {
    


    jnewbery commented at 10:28 am on May 7, 2021:

    The two while loops can be consolidated:

     0diff --git a/src/txrebroadcast.cpp b/src/txrebroadcast.cpp
     1index 940735df1a..401621153c 100644
     2--- a/src/txrebroadcast.cpp
     3+++ b/src/txrebroadcast.cpp
     4@@ -195,18 +195,11 @@ void TxRebroadcastHandler::TrimMaxRebroadcast()
     5 
     6     while (!m_attempt_tracker->empty()) {
     7         auto it = m_attempt_tracker->get<index_by_last_attempt>().begin();
     8-        if (it->m_last_attempt < min_age) {
     9-            m_attempt_tracker->get<index_by_last_attempt>().erase(it);
    10-        } else {
    11+        if (it->m_last_attempt >= min_age && m_attempt_tracker->size() <= MAX_ENTRIES) {
    12+            // The transaction is not old enough to trim and the attempt tracker is not full
    13             break;
    14         }
    15     }
    16-
    17-    // If there are still too many entries, delete the oldest ones
    18-    while (m_attempt_tracker->size() > MAX_ENTRIES) {
    19-        auto it = m_attempt_tracker->get<index_by_last_attempt>().begin();
    20-        m_attempt_tracker->get<index_by_last_attempt>().erase(it);
    21-    }
    22 };
    

    Perhaps that’s easier to read since there’s less repetition?

    If you do that, then perhaps you could just remove this function entirely and put the loop inside GetRebroadcastTransactions() since it’s only called in that one place.


    amitiuttarwar commented at 3:58 am on May 13, 2021:
    good point on consolidating the two loops. the code you shared doesn’t quite make sense (it no longer erases anything from the attempt tracker? 😛), but I got the gist and reworked the logic.
  149. in src/miner.cpp:83 in 343e3cbb3a outdated
    79@@ -78,6 +80,7 @@ static BlockAssembler::Options DefaultOptions()
    80     } else {
    81         options.blockMinFeeRate = CFeeRate(DEFAULT_BLOCK_MIN_TX_FEE);
    82     }
    83+
    


    jnewbery commented at 10:30 am on May 7, 2021:
    Perhaps remove this added newline?
  150. in src/txrebroadcast.cpp:229 in 343e3cbb3a outdated
    186+    const auto it = m_attempt_tracker->find(tx->GetWitnessHash());
    187+    if (it == m_attempt_tracker->end()) return;
    188+    m_attempt_tracker->erase(it);
    189+}
    190+
    191+void TxRebroadcastHandler::TrimMaxRebroadcast()
    


    jnewbery commented at 10:58 am on May 7, 2021:

    It seems to me that m_attempt_tracker has two distinct purposes:

    1. prevent us from rebroadcasting transactions too frequently (see entry_it->m_last_attempt > start_time - MIN_REATTEMPT_INTERVAL)
    2. prevent us from rebroadcasting transactions too many times (see else if (entry_it->m_count >= MAX_REBROADCAST_COUNT))

    I think the expiry strategies conflict for these two purposes. Imagine that we (unupgraded) have 550 txs that are no longer standard for the rest of the network

    • for don’t-rebroadcast-too-frequently, we want to expire least-recently-rebroadcast first, since if we expire more recently rebroadcast transactions, then we’ll try to rebroadcast them again the next time we receive a block, and we’ll end up rebroadcasting a very small set of txs very frequently.
    • for don’t-rebroadcast-too-many-times, if we expire the least-recently-rebroadcast first, then the next time we calculate a rebroadcast set, we’ll include them again, re-add them to attempt_tracker, and expire the next oldest 50. We’ll continue cycling all the now-nonstandard transactions through the attempt tracker over and over again.

    I think it might be a good idea to separate these two purposes by adding a (rolling?) bloom filter for (2). Once a transaction has been rebroadcast MIN_REATTEMPT_INTERVAL times (or it’s removed from the attempt tracker because the tracker is full) we toss it in the bloom filter and then never rebroadcast it again (at least until restart).

  151. jnewbery commented at 10:59 am on May 7, 2021: member

    Looking really good!

    I think commits 9301c280e139132413092abde1f372b736f9af54 ([rebroadcast] Delete TxRebroadcastHandler default copy member functions.) and 343e3cbb3aea6c8e1f561c798a62b343f5ac7e1c ([doc] Improve description for m_attempt_tracker) can be squashed with earlier commits.

  152. ariard commented at 6:16 pm on May 7, 2021: member

    @michaelfolkson

    @ariard: To summarize, I think what you are concerned with is the rebroadcast privacy offered by this module to nodes that are using it assuming only a minority (perhaps a small minority) of the network is using it. This module is currently off by default and according to you (I have no reason to doubt you) a significant proportion of the network is already running custom rebroadcast logic.

    Yes you’re summing up well my concern, though significant would need more qualification. I gave some rough numbers above with 10k of Lightning nodes for 100k estimated full-nodes.

    To me it appears nodes that choose to use the module benefit and nodes that aren’t using it aren’t negatively impacted. As long as that is true (and you agree with that) it doesn’t matter if only a (small) minority are using it? (Of course in time there could be a lot more than a small minority of the network using it.) Or is your concern with nodes that choose to use this module when they really shouldn’t be using it?

    Withholding the point on risks of node fingerprint, I agree it should benefit nodes that are using this module and don’t have negative impacts for not-using nodes/other network clients. It doesn’t matter if only a small minority are using it, though due to the more limited set of module users, rebroadcast privacy won’t be as good as alleged. Where I’m really skeptical is about activating by default this module in the future and thus inflating everyone’s bandwidth if only a minority of nodes operators are benefiting from the feature.

    I have no reason to doubt you

    Please always doubt what I’m saying, I might be wrong or approximate :) @prayank23

    Interesting. Can you please share few examples?

    Most of Lightning nodes implementations are able to CPFP their transactions. It might be automatically triggered by a block-based timer, a user-selected once-for-all height confirmation or manually through custom’s RPC. For eg see lnd’s bumpfee or dual-funded channel spec with a new init_rbf message. For CPFP to be efficient, you will rebroadcast the parent, and its frequency is matter of suiting application/user requirements, likely not matching the new rebroadcast policy introduced by this module.

  153. michaelfolkson commented at 1:54 pm on May 8, 2021: contributor

    @ariard:

    Where I’m really skeptical is about activating by default this module in the future and thus inflating everyone’s bandwidth if only a minority of nodes operators are benefiting from the feature.

    Most of Lightning nodes implementations are able to CPFP their transactions. It might be automatically triggered by a block-based timer, a user-selected once-for-all height confirmation or manually through custom’s RPC. For eg see lnd’s bumpfee or dual-funded channel spec with a new init_rbf message. For CPFP to be efficient, you will rebroadcast the parent, and its frequency is matter of suiting application/user requirements, likely not matching the new rebroadcast policy introduced by this module.

    Ok thanks, makes sense. Based on that I’m a Concept ACK, Approach ACK for this particular PR (and it sounds like @ariard isn’t NACKing this PR either). Any future PR turning this module on by default will need a more rigorous discussion based on above considerations.

  154. in src/txrebroadcast.cpp:117 in 343e3cbb3a outdated
    112+    LOCK(m_rebroadcast_mutex);
    113+    for (const CTransactionRef& tx : block_template->block.vtx) {
    114+        if (tx->IsCoinBase()) continue;
    115+
    116+        uint256 txid = tx->GetHash();
    117+        uint256 wtxid = tx->GetWitnessHash();
    


    jonatack commented at 11:50 am on May 10, 2021:
    Quick comment noticed while writing about this review club session. IIRC it’s preferable to pass uint256 by reference to const rather than by value, e.g. const uint256& txid{tx->GetHash()}; or const auto& txid = tx->GetHash(); (and here these aliases may as well be const anyway as IIUC they aren’t intended to be mutated). It looks like there are a few other places.

    amitiuttarwar commented at 4:04 am on May 13, 2021:

    yup, makes sense. thanks!

    I’ve updated this site, but in all the other places that I found, was already using references. Let me know if I’m missing some?

  155. in src/net.h:80 in a3367b9b79 outdated
    75@@ -76,6 +76,8 @@ static const unsigned int DEFAULT_MAX_PEER_CONNECTIONS = 125;
    76 static constexpr uint64_t DEFAULT_MAX_UPLOAD_TARGET = 0;
    77 /** Default for blocks only*/
    78 static const bool DEFAULT_BLOCKSONLY = false;
    79+/** Default for node rebroadcast logic */
    80+static constexpr bool DEFAULT_REBROADCAST_ENABLED = false;
    


    glozow commented at 2:32 am on May 11, 2021:

    In a3367b9b79086326f75d111d6b381088d88312f0 [p2p] Implement flag to disable rebroadcast

    Should this be in net_processing.h instead of net.h? It seems more like an application-layer thing.


    amitiuttarwar commented at 4:06 am on May 13, 2021:
    great point! fixed now, thanks.
  156. in src/miner.cpp:308 in d72f030be9 outdated
    305@@ -306,6 +306,29 @@ void BlockAssembler::SortForBlock(const CTxMemPool::setEntries& package, std::ve
    306     std::sort(sortedEntries.begin(), sortedEntries.end(), CompareTxIterByAncestorCount());
    307 }
    308 
    309+CFeeRate BlockAssembler::MinTxFeeRate()
    


    glozow commented at 2:45 am on May 11, 2021:

    Approach-related question about d72f030be9c9fa77e23132268e16708d7cbb192e [mining] Calculate the minimum fee rate for transaction inclusion

    Apologies if this has already been asked. Why is a new BlockAssembler::MinTxFeeRate() function created instead of using CBlockPolicyEstimator::estimateSmartFee() with a confirmation target of 1 block or some implementation built using the fee estimator? I’m not too familiar with how it works, but it seems like a very similar idea - get an estimation of what fee would be needed to make it into the next block.


    amitiuttarwar commented at 4:15 am on May 13, 2021:

    it’s an interesting idea, but I don’t think it makes sense to reuse. although they are answering conceptually similar questions, the way these two functions are going about answering is quite different. MinTxFeeRate is calculating very precisely based on the state of the mempool right now, where as the estimateSmartFee function is trying to predict a rate based on current conditions combined with various confidence thresholds.

    (also note that a confTarget of 1 gets automatically turned into 2. I didn’t dig into the function too deep to understand exactly why that’s necessary, but I think indicates the divergent aims)

  157. in src/txrebroadcast.cpp:117 in 956819c69d outdated
    39+    {
    40+        LOCK(m_rebroadcast_mutex);
    41+        if (m_tip_at_cache_time == m_chainman.ActiveTip()) {
    42+            options.blockMinFeeRate = m_previous_cached_fee_rate;
    43+        } else {
    44+            options.blockMinFeeRate = m_cached_fee_rate;
    


    glozow commented at 2:58 am on May 11, 2021:

    In 956819c69de99db84908df0fb3b25ba616f2362d [rebroadcast] Apply a fee rate filter:

    What happens if our node has its own prioritized transactions, which could be returned by our own block assembler but miners wouldn’t care about? I believe the block assembler uses modified feerate, so setting blockMinFeeRate here won’t filter those out.


    amitiuttarwar commented at 4:18 am on May 13, 2021:

    GREAT point! in the original PR (#16698), I had a commit to update the prioritisetransaction help documentation, but somehow got lost along the way to this current PR. In the latest push, I’ve cherry-picked that commit onto this PR.

    and, to confirm, you’re absolutely right. the block assembler uses modified feerate, so could select transactions to rebroadcast that the user has manually added priority.

  158. in src/net_processing.cpp:1327 in 4165cb0606 outdated
    1324+            // Although transactions removed for this reason will not be
    1325+            // returned by this callback, include it here so the compiler
    1326+            // can warn about missing cases in this switch statement.
    1327+            // These transactions are handled by BlockConnected.
    1328+            break;
    1329+        case MemPoolRemovalReason::EXPIRY:
    


    glozow commented at 3:19 am on May 11, 2021:

    In 4165cb0606e4be476651899b80525f63f6e4465a [rebroadcast] Stop tracking rebroadcast attempts for certain transactions

    Would it be possible to write in a comment here “we want to avoid a situation where two peers that are unaware of new policy/consensus rules endlessly rebroadcast a transaction considered invalid by the majority of the network. Thus, the rebroadcast attempt tracker should remember transactions even after they have expired from the mempool.” or something along those lines? I just remember it being confusing what “genuinely expire from majority of mempools” meant and why we don’t remove from the tracker when a tx expires from mempool.


    amitiuttarwar commented at 4:19 am on May 13, 2021:
    done, thanks! I’ve been having a hard time explaining, added a comment along these lines.
  159. in src/net_processing.cpp:1325 in 4165cb0606 outdated
    1323+        case MemPoolRemovalReason::BLOCK:
    1324+            // Although transactions removed for this reason will not be
    1325+            // returned by this callback, include it here so the compiler
    1326+            // can warn about missing cases in this switch statement.
    1327+            // These transactions are handled by BlockConnected.
    1328+            break;
    


    glozow commented at 3:24 am on May 11, 2021:

    In 4165cb0606e4be476651899b80525f63f6e4465a [rebroadcast] Stop tracking rebroadcast attempts for certain transactions

    Why not group MemPoolRemovalReason::BLOCK with the cases that we call RemoveFromAttemptTracker() for (while keeping the comment indicating that they don’t go through this callback)?


    amitiuttarwar commented at 4:20 am on May 13, 2021:
    sure, doesn’t seem like it matters either way? but done regardless
  160. in src/net_processing.cpp:1342 in 4165cb0606 outdated
    1340+ * Update state based on a newly connected block:
    1341+ * - Evict orphan txn pool entries
    1342+ * - Save the time of the last tip update
    1343+ * - Remember recently confirmed transactions
    1344+ * - Delete tracked announcements for block transactions
    1345+ * - Delete tracked rebroadcast attempts
    


    glozow commented at 3:27 am on May 11, 2021:
    0 * - Delete tracked rebroadcast attempts for block transactions
    
  161. in src/test/txrebroadcast_tests.cpp:99 in 0ae1420767 outdated
    89+
    90+    // Confirm both transactions successfully made it into the mempool
    91+    BOOST_CHECK_EQUAL(m_node.mempool->size(), 2);
    92+
    93+    // Age transaction to be older than REBROADCAST_MIN_TX_AGE
    94+    SetMockTime(GetTime<std::chrono::seconds>() + 35min);
    


    glozow commented at 3:39 am on May 11, 2021:

    In 0ae1420767a320cfeafd2acee0b54bc6a6eb9b27 [test] Add unit test for the fee rate cache

    Why note just use + REBROADCAST_MIN_TX_AGE + 5 minutes here?


    amitiuttarwar commented at 4:24 am on May 13, 2021:
    REBROADCAST_MIN_TX_AGE is defined in the .cpp, so isn’t available to import in the test. I could move it to the header, but I was trying to minimize how much stuff is in the header only for tests. I could redefine the symbol as a constant in the test, but then we run into the same issue of having to update it if the code changes, so doesn’t seem much better..
  162. in src/test/txrebroadcast_tests.cpp:65 in 0ae1420767 outdated
    56@@ -57,6 +57,48 @@ BOOST_AUTO_TEST_CASE(recency)
    57     BOOST_CHECK_EQUAL(candidates.front().m_txid, tx_old.GetHash());
    58 }
    59 
    60+BOOST_AUTO_TEST_CASE(fee_rate)
    


    glozow commented at 3:40 am on May 11, 2021:

    In 0ae1420767a320cfeafd2acee0b54bc6a6eb9b27 [test] Add unit test for the fee rate cache

    Would be nice if the test also checked what happens with transactions that are prioritized.

  163. in src/txrebroadcast.h:60 in 87d6466380 outdated
    40@@ -41,13 +41,19 @@ class TxRebroadcastHandler
    41     /** Remove transaction entry from the attempt tracker.*/
    42     void RemoveFromAttemptTracker(const CTransactionRef& tx);
    43 
    44+    /** Test only */
    45+    void UpdateAttempt(const uint256& wtxid, const int count, const std::chrono::microseconds last_attempt_time);
    46+
    47+    /** Test only */
    48+    bool CheckRecordedAttempt(const uint256& wtxid, const int expected_count, const std::chrono::microseconds expected_timestamp) const;
    


    glozow commented at 3:43 am on May 11, 2021:

    In 87d6466380737c2d05932d4af3879950982e61c4 [test] Add unit test for rebroadcast attempt logic

    I’m not sure what difference it would make, but why don’t these require m_rebroadcast_mutex instead of doing the locking internally?


    amitiuttarwar commented at 4:27 am on May 13, 2021:
    just so I can keep m_rebroadcast_mutex as a private member
  164. amitiuttarwar force-pushed on May 13, 2021
  165. amitiuttarwar force-pushed on May 14, 2021
  166. in src/init.cpp:1228 in 1cc12f956a outdated
    1224@@ -1224,8 +1225,10 @@ bool AppInitMain(NodeContext& node, interfaces::BlockAndHeaderTipInfo* tip_info)
    1225     ChainstateManager& chainman = *Assert(node.chainman);
    1226 
    1227     assert(!node.peerman);
    1228+    bool enable_rebroadcast = gArgs.GetArg("-rebroadcast", DEFAULT_REBROADCAST_ENABLED);
    


    MarcoFalke commented at 6:42 am on May 15, 2021:
    0    const bool enable_rebroadcast{args.GetArg("-rebroadcast", DEFAULT_REBROADCAST_ENABLED)};
    

    amitiuttarwar commented at 11:44 pm on May 17, 2021:
    done. note: had to change GetArg to GetBoolArg to work with braced initialization, which seems better anyways.
  167. in src/net_processing.cpp:1485 in 1cc12f956a outdated
    1480+    if (m_txrebroadcast) {
    1481+        const std::vector<TxIds> rebroadcast_txs = m_txrebroadcast->GetRebroadcastTransactions(block, *pindexNew);
    1482+
    1483+        LOCK(cs_main);
    1484+        for (auto ids : rebroadcast_txs) {
    1485+            RelayTransaction(ids.m_txid, ids.m_wtxid);
    


    MarcoFalke commented at 6:54 am on May 15, 2021:

    to avoid the recursive lock

    0            _RelayTransaction(ids.m_txid, ids.m_wtxid);
    

    amitiuttarwar commented at 11:45 pm on May 17, 2021:
    good call, rebased to get the internal function & updated
  168. in test/functional/p2p_rebroadcast.py:40 in 1cc12f956a outdated
    35+
    36+class NodeRebroadcastTest(BitcoinTestFramework):
    37+    def set_test_params(self):
    38+        self.num_nodes = 2
    39+        self.extra_args = [[
    40+            "-whitelist=127.0.0.1",
    


    MarcoFalke commented at 6:59 am on May 15, 2021:
    would be nice to select the exact permission needed

    amitiuttarwar commented at 11:45 pm on May 17, 2021:
    done
  169. amitiuttarwar force-pushed on May 17, 2021
  170. amitiuttarwar force-pushed on May 18, 2021
  171. amitiuttarwar force-pushed on May 18, 2021
  172. [interface] Add block param to the UpdatedBlockTip interface function c5efa7ffba
  173. [rebroadcast] Introduce a mempool rebroadcast module
    Introduce a module that rebroadcasts transactions from the node instead of the
    wallet. This module is currently unused.
    
    The fundamental difference from the existing wallet rebroadcast logic is that
    we apply the logic to all transactions, not just "mine". In order to prevent
    spam, we need to carefully select which transactions to rebroadcast. As of this
    commit, we select the transactions in the mempool that have the highest
    feerate.
    b18de18ca2
  174. [rebroadcast] Reduce amount of rebroadcast candidates
    Instead of determining the maximum size of the rebroadcast candidates based on
    the maximum allowed block weight, calculate based on the incoming block that
    triggered the mechanism. This will reduce the possible bandwidth usage when
    smaller blocks are mined, for example, an empty block.
    a4b342fa7a
  175. [p2p] Start rebroadcasting mempool transactions
    After we process a block, invoke the rebroadcast module to identify if there
    are any transactions we would have expected to be included, and queue them up
    for relay to our peers.
    
    This will only identify rebroadcast candidates, as transactions will be subject
    to RelayTransaction and subsequent SendMessages logic, such as checking
    filterInventoryKnown, the rate limit logic of INVENTORY_BROADCAST_MAX, etc.
    61f5d0d73b
  176. [p2p] Implement flag to disable rebroadcast
    To initially roll out and test, default the node rebroadcast functionality to
    false. Since this is for developer testing, make this a hidden option so we do
    not need to maintain an additional option in the long-term.
    23635b4874
  177. [mining] Add recency condition on block creation to get rebroadcast set
    When identifying the rebroadcast candidates, only select transactions that
    entered the mempool REBROADCAST_MIN_TX_AGE ago. This gives the transactions a
    chance to have been picked up by a block, versus one that just entered our
    mempool.
    3d5d123838
  178. [p2p] Rebroadcast skips the block-validity check
    It's not worth throwing a runtime error if the rebroadcast block fails the
    validity checks. Also, its an unnecessary use of resources to be regularly
    performing the check.
    32970c9457
  179. [mining] Use the new option to skip unconditional logging.
    The unconditional logging would make sense if a user is calling
    CreateNewBlock to mine blocks. However, it seems confusing as a
    side effect of normal transaction relay, so skip it.
    028536a1d3
  180. amitiuttarwar force-pushed on May 18, 2021
  181. amitiuttarwar force-pushed on May 18, 2021
  182. in src/txrebroadcast.cpp:77 in b927ab97c7 outdated
    72+TxRebroadcastHandler::TxRebroadcastHandler(const CTxMemPool& mempool, const ChainstateManager& chainman, const CChainParams& chainparams)
    73+    : m_mempool{mempool},
    74+      m_chainman{chainman},
    75+      m_chainparams(chainparams),
    76+      m_attempt_tracker{std::make_unique<indexed_rebroadcast_set>()},
    77+      m_max_filter(1500, 0.0001){}
    


    ajtowns commented at 4:14 am on May 19, 2021:
    This gives a 1-in-10k fp rate, so once the bloom filter has had time to fill up, we should expect each node to incorrectly not rebroadcast 1-in-10k transactions. However, the nTweak parameter should ensure that this is affects different transactions on different nodes, so I think this should be fine.
  183. in src/txrebroadcast.cpp:193 in b927ab97c7 outdated
    188+
    189+void TxRebroadcastHandler::CacheMinRebroadcastFee()
    190+{
    191+    CChainState& chain_state = m_chainman.ActiveChainstate();
    192+    if (chain_state.IsInitialBlockDownload()) return;
    193+    auto tip = m_chainman.ActiveTip();
    


    ajtowns commented at 3:00 am on May 25, 2021:
    I think you should be locking cs_main prior to calling this – you want a consistent view between tip and current_fee_rate, but currently there’s no reason you couldn’t update the tip immediately after this line, thus associating the old tip with the new (much reduced) fee rate.

    amitiuttarwar commented at 5:01 am on May 31, 2021:
    yeah makes sense, done
  184. in src/miner.cpp:456 in b927ab97c7 outdated
    449@@ -419,6 +450,12 @@ void BlockAssembler::addPackageTxs(int &nPackagesSelected, int &nDescendantsUpda
    450         // This transaction will make it in; reset the failed counter.
    451         nConsecutiveFailed = 0;
    452 
    453+        if (min_package_fee_rate) {
    454+            // Compare package fee rate and potentially update new minimum
    455+            CFeeRate newFeeRate(packageFees, packageSize);
    456+            if (newFeeRate < *min_package_fee_rate) *min_package_fee_rate = newFeeRate;
    


    ajtowns commented at 3:04 am on May 25, 2021:
    Earlier in this function, there’s code to skip transactions if they’re too large for the block. I think this can result in the mempool containing txs with fee rates of: 120 s/vb, 119 s/vb, 118 s/vb, 117 s/vb, 115 s/vb, 110 s/vb, 105 s/vb, 100 s/vb, 95 s/vb, 80 s/vb, 79 s/vb, ... and the block containing txs with fee rates of: 120, 119, 118, 117, 95, 80 – because the 110-100 s/vb txs just didn’t fit in the block, but the 95 and 80 s/vb txs happened to be tiny. This would then incorrectly result in txs with fee rates above 80 s/vb being rebroadcast, whereas really only txs with fee rates above 117 s/vb should be.
  185. [mining] Calculate the minimum fee rate for transaction inclusion.
    The functionality introduced in this commit is currently unused. The ability
    to calculate the minimum fee rate for a transaction to be included into a block
    is used to identify the top of the mempool, and later applied to filter the
    rebroadcast candidates before sending them to peers.
    f80a01a23c
  186. [rebroadcast] Apply a fee rate filter
    Every minute, calculate the threshold fee rate for a transaction to be
    considered at the top of the mempool, and cache this value. Apply this as a
    condition when identifying rebroadcast candidates.
    25a41e6a72
  187. [rebroadcast] Track rebroadcast attempts
    Introduce a boost::multi_index to track our previous rebroadcast attempts. We
    use this information primarily to ensure we don't exceed a maximum number of
    rebroadcast attempts. This allows transactions to genuinely expire from the
    majority of mempools. We disable automatic rebroadcasts because the
    conceptually desired behavior should be that after a certain amount of time,
    only the source wallet should rebroadcast the transaction. (Of course, we
    cannot enforce this on a decentralized network, but design the default behavior
    to uphold this idea.)
    a615dd3df8
  188. [rebroadcast] Delete TxRebroadcastHandler default copy member functions.
    Since the attempt tracker is implemented as a unique pointer, it should not be
    copied. Delete the special member functions that would allow copying the
    TxRebroadcastHandler, and thus the unique pointer member variable (copy
    constructor and copy assignment operator).
    d48f4930fa
  189. [rebroadcast] Add a bloom filter for txns that have been max rebroadcasted.
    When a transaction hits the maximum on the attempt tracker, add it to a bloom
    filter. Don't rebroadcast transactions present in the bloom filter. This
    ensures that we won't repeatedly rebroadcast transactions that have hit the
    MAX_REBROADCAST_COUNT, even if there are more transactions than can fit in
    m_attempt_tracker at once.
    8eccc1e29b
  190. [rebroadcast] Delete and expire entries from m_attempt_tracker
    Ensure the index does not grow unbounded, and delete entries that
    were last updated >3 months ago.
    83777da9fe
  191. [rebroadcast] Add logging to monitor rebroadcast. b3053c338c
  192. [rebroadcast] Stop tracking rebroadcast attempts for certain transactions
    Depending on the reason a transaction is removed from the mempool, it can be
    extremely unlikely for it to be able to re-enter. Some examples are if it was
    mined into a block or replaced using RBF. In these circumstances, we can remove
    the transaction entry from the rebroadcast tracker. Under an unlikely
    circumstance where the transaction does re-enter the mempool and gets
    rebroadcast, it will simply be re-added to the attempt tracker.
    4eabc075b6
  193. [test] Add unit test to confirm the recency filter works.
    Includes adding a helper to the shared unit test utilities to create a valid
    transaction and submit to the mempool.
    
    update test to use normal key generation
    d584294c21
  194. [test] Add unit test for rebroadcast attempt logic 26b3c58f81
  195. [test] Add unit test for the fee rate cache f81a728a92
  196. [test] Functional tests for rebroadcast logic.
    We test that when a block comes in, we rebroadcast missing transactions based
    on time and fee rate.
    d46fdb83c7
  197. [docs] Update prioritisetransaction help man 9b757c214e
  198. in src/txrebroadcast.cpp:192 in b927ab97c7 outdated
    187+};
    188+
    189+void TxRebroadcastHandler::CacheMinRebroadcastFee()
    190+{
    191+    CChainState& chain_state = m_chainman.ActiveChainstate();
    192+    if (chain_state.IsInitialBlockDownload()) return;
    


    ajtowns commented at 3:20 am on May 25, 2021:
    Perhaps this should also be conditional on mempool.IsLoaded() ?

    amitiuttarwar commented at 5:01 am on May 31, 2021:
    done
  199. amitiuttarwar force-pushed on May 29, 2021
  200. sdaftuar commented at 3:33 pm on May 31, 2021: member

    I’ve been simulating the behavior of this logic using historical transaction and block data, and I have some general concept thoughts:

    1. In a situation where a transaction propagated reasonably well, it doesn’t make sense that the whole network should simultaneously try to rebroadcast that transaction at the same time. That is needlessly bandwidth-wasteful, as it results in an INV for that transaction to be re-sent on every link in the network, in a situation where (by assumption) few nodes would be missing it.

    2. In a situation where a transaction didn’t propagate well or has dropped out of many nodes’ mempools, but would propagate well if rebroadcast, it should be sufficient for a single node or a small number of nodes to do the rebroadcasting.

    3. The benefit of rebroadcasting a transaction that wouldn’t propagate well seems small. The goal is to get good transactions into miners’ mempools, but if a transaction doesn’t propagate well to node mempools, it probably wouldn’t make it into a lot of miners’ mempools either.

    4. I think we want to avoid bandwidth spikes on the network – particularly right after a new block is found, when we would ideally be prioritizing bandwidth for block relay. So it seems better to me to (a) not have all nodes on the network synchronizing on rebroadcasting simultaneously and (b) not have block connection be a trigger for rebroadcast.

    5. If a bunch of nodes on the network are simultaneously deciding to rebroadcast a large set of transactions, the rate-limiting we have on transaction announcements will mean that the network’s transaction relay latency will go up as it takes time for the backlog to clear. So, I think in general we should want to avoid situations where a node might want to broadcast (for example) several hundred transactions at once – even more so if all the nodes on the network would decide to do the same thing at the same time. This is another reason for not synchronizing rebroadcast across nodes, and I think it is also an argument for capping the number of transactions that might get selected for rebroadcasting at any particular time.

    6. There’s little value in rebroadcasting transactions whose feerates are only slightly better than other transactions in the mempool. Not to say we should never do it, but in thinking about the cost/benefit of transaction rebroadcast, it seems to me that prioritizing bandwidth usage on the most comparatively valuable transactions makes the most sense.

    Taking the above into account, I’d propose this approach:

    a) Any given node should rebroadcast way less often – perhaps each node could attempt to rebroadcast on the order of once every 24 hours or every 48 hours on average, whether on a poisson timer or a random offset. In a network with 10k listening nodes this is already a lot of rebroadcasting (10,000 / (24*60) is about 7 such nodes attempting rebroadcast every minute, not even taking into account the non-listening nodes on the network which will also be doing this!).

    b) If we do (a) then we’ve probably greatly mitigated bandwidth spikes on the network, but I’d go further and limit the number of transactions that are ever selected to be rebroadcast at some small value like 25 or 50, to ensure we don’t ever try to re-announce several hundred (or more) transactions onto the network at once.

    c) I think the logic in this PR could use some refining to avoid edge-case behavior when we might rebroadcast a lot of transactions that are not valuable to rebroadcast. These first two are cases that I’ve seen so far in my simulations, and the last one is a conjecture:

    • If a node comes back online after being offline for a while, then using block connections to trigger rebroadcast can result in rapid-fire rebroadcast of transactions that we really shouldn’t be reannouncing (because both our mempool and our tip are not up to date). I think this would be fixed by adopting (a) and (b) above.
    • The mining heuristic of calling CreateNewBlock with an option for excluding recent transactions can result in us deciding to rebroadcast a lot of transactions that we wouldn’t even select for a new block. Imagine that the mempool has just less than 1MB (vsize) of high feerate stuff that is all recent, and everything else is some uniform low feerate. Then our cached feerate for inclusion in a block might be the low feerate (if at least 1 such transaction would be included in the block), and the heuristic of calling CNB with the cached feerate and excluding recent transactions can pick up thousands of low-feerate old stuff that wouldn’t all realistically make it in to a new block.
    • I think that reannouncing transactions that are part of a package (ie have more than 1 unconfirmed ancestor) may not be a great idea, because there are at least two reasons that packages might not relay well: (a) if any unconfirmed parent has a feerate below a peer’s mempool-min-fee, then the package won’t be accepted, and (b) descendant transaction limits on unconfirmed parents can interfere with relay of even a high-fee-rate child. So to avoid wasting bandwidth, I think there’s an argument that perhaps we should start by just relaying transactions with no unconfirmed parents in our initial deployment of this logic, and defer trying to relay transactions with unconfirmed ancestors until we have a package relay protocol deployed.

    d) Given the issue described above with CreateNewBlock and the issues I am conjecturing with package relay, I suggest that we simplify the logic by eliminating the dependency on the mining algorithm, and instead just do a really simple algorithm for deciding what to consider rebroadcasting. Randomly once a day (or maybe once every two days):

    • Walk the mempool by descending ancestor-fee-rate
    • If in the first 1MB (by vsize) of size-with-ancestor we encounter a transaction that is > 30 minutes old and has no unconfirmed parents (and hasn’t hit our max number of rebroadcast attempts), then add to the rebroadcast set.
    • If we we hit 1MB of vsize that we’ve looked at or hit some cap on the number of transactions to rebroadcast (say 25), break and announce whatever we’ve picked so far. One thing I’m not sure about is if we should be concerned about rebroadcasting a transaction that is close to the end of our -mempoolexpiry value; it seems like it could be problematic if we rebroadcast some low-feerate transaction that would otherwise be expiring soon and somehow cause it to ping-pong into other’s mempools again, and then others cause it to get resurrected in our own. Maybe we should only rebroadcast transactions that are signaling BIP 125 RBF?

    e) I think that we should only rebroadcast transactions to peers that are using wtxidrelay (BIP 339). Bitcoin Core software that predates wtxidrelay will not cache validation failure for segwit transactions that don’t make it into the mempool. This means that if a transaction doesn’t propagate for some random policy reason (eg feerate), then the peer would still try download it from every connection that announces it. As this PR is drafted now, where all nodes are on the same announcement timer, that means a lot of wasted transaction download bandwidth (not just wasted INV bandwidth!) whenever a transaction that doesn’t get accepted is rebroadcast. This would be mitigated by randomizing rebroadcasts and reducing the frequency, but I think we might as well just limit this to wtxidrelay peers as well for an extra safety margin.

    My simulations of this PR on historical data are still ongoing and I don’t have a good summary yet, but please let me know if there are statistics or other specific questions that would be helpful for us to consider (I have a few ideas in mind but I’m still gathering my thoughts).

  201. sdaftuar commented at 2:00 pm on June 1, 2021: member

    I had one other thought about how we select transactions for rebroadcast; I think it could be problematic to base transaction rebroadcast solely on how transactions in our mempool compare to transactions that we would select in CreateNewBlock without regard to what transaction fees we’re actually seeing in blocks on the network.

    Imagine that you are running a somewhat older node, and there have been releases of Bitcoin Core that enable new standard transaction types that others are using. Then your node will not be aware of those new transactions, and it’s possible that only looking at the set of transactions that you know to be standard would result in rebroadcasting transactions from your mempool that are actually quite a bit below the feerate that the rest of the network thinks is needed to be confirmed soon.

    (Or really there could be any reason that miners might have access to better feerate transactions than a single node does – there’s still no point in aggressively rebroadcasting transactions that are worse than what we see are being confirmed.)

    This problem would also be largely mitigated by making this behavior occur much less frequently and limiting the number of transactions that we’d consider rebroadcasting at once, but I think the heuristic of calling CreateNewBlock every minute and caching the lowest observed package feerate may be inferior to just looking at the contents of each block we see, and trying to infer the lowest feerate that we think is actually needed to be included in a block (perhaps we could look at the set of in-block transactions that have no ancestors or descendants, and try to estimate the minimum feerate needed for inclusion as a moving average of what we’ve recently observed – would need to test out any kind of heuristic like this though).

  202. amitiuttarwar commented at 9:57 pm on June 4, 2021: contributor
    Marking this PR as draft- After offline conversations with @ajtowns, @sdaftuar & @jnewbery, I’m planning to rework the approach of this patch to increase the requirements for a transaction to be rebroadcast. The biggest change will be only sending an INV after a transaction has been missed from 3 blocks.
  203. amitiuttarwar marked this as a draft on Jun 4, 2021
  204. laanwj removed this from the "Blockers" column in a project

  205. ghost commented at 5:31 pm on July 30, 2021: none

    I was searching for privacy related PRs to review and write tests using PowerShell scripts for my project.

    Found this PR in the search results which I had already reviewed in March 2021, however I don’t think writing test for it makes sense based on last two comments.

    Also agree with the things mentioned by Suhas Daftuar.

    I’m planning to rework the approach of this patch to increase the requirements for a transaction to be rebroadcast.

    Hoping new approach will be better and we soon improve privacy in rebroadcast mechanism. Thanks for working on this.

  206. DrahtBot commented at 11:18 pm on December 13, 2021: member

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

    Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a “draft”.

  207. DrahtBot added the label Needs rebase on Dec 13, 2021
  208. DrahtBot commented at 1:06 pm on March 21, 2022: member
    • Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
    • Is it no longer relevant? ➡️ Please close.
    • Did the author lose interest or time to work on this? ➡️ Please close it and mark it ‘Up for grabs’ with the label, so that it can be picked up in the future.
  209. fanquake commented at 2:43 pm on March 22, 2022: member
    Closing this for now. It may be reopened at a later point.
  210. fanquake closed this on Mar 22, 2022

  211. DrahtBot locked this on Mar 22, 2023

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-11-11 12:12 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me