txgraph: use real intra-cluster dependencies in Trim() #36733

pull bazzoneto wants to merge 1 commits into bitcoin:master from bazzoneto:txgraph-trim-real-deps changing 3 files +144 −22
  1. bazzoneto commented at 2:35 PM on November 2, 2026: none

    TxGraph::Trim() builds a rudimentary linearization of the would-be cluster to decide which transactions to remove. For the dependencies inside each involved cluster, it did not use the real ones: it added an implicit dependency between each pair of consecutive transactions in that cluster's linearization. This makes transactions look dependent when they are not, which can merge partitions unnecessarily and cause Trim() to remove more transactions than needed (see #36656).

    This PR makes GenericClusterImpl::AppendTrimData() emit the cluster's actual dependencies (only the reduced parents, since the rest follow by transitivity) instead of the implicit chain. As a result, several transactions from the same cluster can be in the heap at the same time. Topological order is still respected, because a transaction only becomes eligible once all of its dependencies are met. The related comments in Trim() and in the fuzz test were updated.

    Tests:

    • New unit tests txgraph_trim_no_cascade and txgraph_trim_no_overcount in src/test/txgraph_tests.cpp, based on the existing zigzag/flower Trim tests.
    • The existing txgraph fuzz target exercises Trim() and checks its invariants.

    As noted by instagibbs in the issue, this is low priority since Trim() only runs during reorgs. I have not yet built or run the tests locally, so I'm opening this as a draft to let CI run.

    Fixes #36656.

  2. txgraph: use real intra-cluster dependencies in Trim()
    Trim() previously approximated each involved cluster's dependencies by
    an implicit chain between consecutive transactions of its linearization.
    This could merge partitions and remove transactions that did not need
    to be removed.
    
    Emit the cluster's reduced parent dependencies instead, and add unit
    tests covering the cascade and overcount cases.
    
    Fixes #36656.
    01330633a2
  3. DrahtBot commented at 2:35 PM on November 2, 2026: contributor

    <!--e57a25ab6845829454e8d69fc972939a-->

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

    <!--006a51241073e994b41acfe9ec718e94-->

    External sites

    <!--021abf342d371248e50ceaed478a90ca-->

    Reviews

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

    <!--5faf32d7da4f0f540f40219e4f7537a3-->

  4. maflcko commented at 3:15 PM on November 2, 2026: member

    Thx, but LLM output is not accepted if the author can not properly explain, test or could have written the change themselves. Also, LLM generated content is not allowed in comments/communications. See https://github.com/bitcoin/bitcoin/blob/master/doc/AI_POLICY.md

    The bottleneck in this project has always been review and testing, not writing code. Development here is intentionally conservative and slow, and reviewer attention is the scarcest resource we have. LLMs have made this worse, anyone can now prompt them and post their output as PRs. There is an infinite amount plausible looking "improvements" for LLMs to suggest and work on.

    Unless we fully trust LLMs to both write and review code, humans still have to spend time understanding the proposed changes, which incurs a non-zero cost for every opened PR.

    I understand that contributing to this project can be intimidating, and using LLMs may seem tempting, but it really creates more issues for this project than it solves. The best way to help this project, is to review and test changes. You can use LLMs for this, but you shouldn't solely rely on them, or just post their output.

    I am asking you to reconsider whether it's something you genuinely think the project should pursue, independent of what your LLM suggested.

    See https://github.com/bitcoin/bitcoin/blob/master/doc/AI_POLICY.md

  5. maflcko closed this on Nov 2, 2026


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: 2026-11-20 15:51 UTC

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