17:00:55 <glozow> #startmeeting 
17:00:55 <corebot> glozow: Meeting started at 2025-04-23T17:00+0000
17:00:56 <corebot> glozow: Current chairs: glozow
17:00:57 <corebot> glozow: Useful commands: #action #info #idea #link #topic #motion #vote #close #endmeeting
17:00:58 <corebot> glozow: See also: https://hcoop-meetbot.readthedocs.io/en/stable/
17:00:59 <corebot> glozow: Participants should now identify themselves with '#here' or with an alias like '#here FirstLast'
17:00:59 <sipa> hello!
17:01:30 <glozow> Welcome to PR review club! Today is txgraph round 2, notes are available here: https://bitcoincore.reviews/31444
17:01:59 <glozow> Did anybody have a chance to review the PR or the notes?
17:02:22 <abubakarsadiq> I am in the process of reviewing the PR
17:02:45 <monlovesmango> I did review the best that I could
17:03:14 <glozow> Nice! What is your review approach/
17:03:34 <glozow> ?*
17:03:59 <monlovesmango> read PR review club notes, read through pr desc, read/skimmed through the commits, tried to answer pr review club questions
17:04:02 <abubakarsadiq> I like the approach, I am reviewing it commit by commit and running the fuzz test locally with modifications
17:04:10 <pseudoramdom> Hi! First time here. Did glance over the PR and the notes. Getting caught up on Cluster Mempool
17:04:24 <glozow> pseudoramdom: welcome!
17:04:26 <sipa> pseudoramdom: welcome to the (review) club!
17:04:45 <glozow> Let's start with the questions
17:04:45 <monlovesmango> oh yeah I also am runnign fuzz tests but it is taking forever and this is my first time so not sure what i'm doing
17:04:46 <glozow> Why are block building and eviction relevant to each other? Wouldn’t it be easier to evict transactions by the order they entered the mempool?
17:05:19 <glozow> Feel free to ask any of your own questions, whenever you like
17:05:46 <sipa> monlovesmango: just in case you're not aware - running fuzz tests generally runs indefinitely; it keeps trying to make randomized changes to the input, and seeing if those trigger code coverage change and (even better) assertion failures
17:06:13 <monlovesmango> they are both looking for the same data (ording of tx clusters by fee rate), just opposite goals. one wants the top fee rates, the other the lowest fee rate.
17:06:50 <abubakarsadiq> glozow: you would want to evict the worst transaction in the mempool, i.e the one very unlikely to be mined soon.
17:06:50 <abubakarsadiq> As such when you use the order they enter mempool you will likely evict a transaction that might be mined in the next block.
17:06:55 <monlovesmango> it would be easier to evict by order they entered, but this can also evict your highest paying tx
17:07:10 <pseudoramdom> Does block building and eviction need to be opposites? or not necessary?
17:07:14 <sipa> monlovesmango: just a tiny nit, it's not sorting the *clusters* by feerate, but something else
17:07:32 <monlovesmango> sipa: haha ok thank you for letting me know! will have to look into how to run that properly
17:07:44 <monlovesmango> sipa: not clusters, chunks right?
17:07:48 <sipa> monlovesmango: bingo
17:07:51 <glozow> monlovesmango: abubakarsadiq: yes exactly
17:08:17 <sipa> pseudoramdom: today, they are very much not each other's opposite; the question is why we'd like them to be opposities
17:08:57 <glozow> to be fair, today, eviction is an approximation of the opposite of block building, just not an accurate one
17:09:10 <sipa> glozow: right, that's phrased more clearly
17:09:29 <glozow> True / false: if all clusters are singletons (have 1 transaction each), m_main_chunkindex would just be sorting the transactions by feerate
17:09:46 <monlovesmango> I want to say true
17:09:53 <abubakarsadiq> True :)
17:10:32 <pseudoramdom> I see. Yeah, it makes sense to have them accurately ordered. Block building can select the "best" end of the list. And eviction removes from the "worst" end
17:10:43 <glozow> Great :) can you explain why true?
17:10:45 <abubakarsadiq> If there is tie it it will compare the sequence of the clusters (individual tx)
17:11:29 <monlovesmango> if all clusters are singletons, then each cluster will have one chunk, and the linearization orders by chunk fee rate
17:11:47 <sipa> Bonus question: imagine two singleton clusters, with the same feerate, but they have different vsize. What can you say about their order?
17:11:56 <glozow> for the people following at home, we are looking at https://github.com/bitcoin-core-review-club/bitcoin/blob/27a0c93abb7e70b93214eb857e2046f848139e68/src/txgraph.cpp#L290-L306
17:12:19 <abubakarsadiq> sipa: thats a tie?
17:12:31 <sipa> abubakarsadiq: depends on your perspective :p
17:12:46 <glozow> monlovesmango: yes!
17:13:10 <abubakarsadiq> We have two comparators yes.
17:13:42 <pseudoramdom> m_sequence?
17:15:13 <abubakarsadiq> sipa: I think the one with higher vsize will come first in the order since the sorting uses the > operator not `FeeRateCompare`?
17:15:52 <sipa> abubakarsadiq: no it uses FeeRateCompare, sorry - I thought it didn't, so this was a very trick question
17:16:06 <sipa> they'll be sorted by cluster creation order (m_sequence)
17:16:19 <Murch[m]> monlovesmango: You can just interrupt fuzz tests any time, or you can set a `max_total_time` or `runs` limit. You can ping me later if you want
17:16:26 <glozow> does `FeeRateCompare` return 0 for same feerate different vsize?
17:16:51 <glozow> I suppose yes
17:17:02 <sipa> glozow: yes, FeeFrac::operator<=> (and derived operator<, ... etc) treat equal feerate objects as sorted by increasing size
17:17:07 <glozow> So it tie-breaks by sequence
17:17:11 <abubakarsadiq> ah, I've mentioned that as well above. and changed my mind :)
17:17:12 <sipa> but FeeRateCompare specifically just compares the feerate itself
17:17:20 <monlovesmango> Murch: ok sounds good thank you!
17:18:35 <glozow> here: https://github.com/bitcoin-core-review-club/bitcoin/blob/27a0c93abb7e70b93214eb857e2046f848139e68/src/util/feefrac.h#L113
17:18:46 <glozow> Next question
17:18:47 <Murch[m]> (or rather, we can discuss here in this channel after the meeting, I think others might also chime in or want to read it)
17:18:47 <glozow> In English, using the approach in this PR, what is the algorithm for selecting transactions in order for block building? And for eviction?
17:19:04 <abubakarsadiq> @monlovesmango: I run the fuzz test to verify my understand that if I make modification to a commit I expect an assertion I added to be triggered which always do.
17:19:13 <glozow> You can discuss here, it's about the PR
17:19:54 <monlovesmango> glozow: I can't process too much at a time and would rather focus on questions :)
17:20:10 <monlovesmango> abubakarsa: that is a good idea!
17:21:15 <Murch[m]> glozow: Repeatedly pick from all clusters the chunk with the highest available chunk feerate until the block is full
17:21:44 <sipa> glozow: is your question more about what BlockBuildImpl does internally, or how you imagine high-level code would use BlockBuilder based on its interface?
17:22:02 <sipa> (because the actual block building code isn't inside this PR)
17:22:08 <glozow> let's start with: how would higher level code use BlockBuilder?
17:22:09 <abubakarsadiq> In English?
17:22:31 <glozow> (Oh oops, that's the next question)
17:22:39 <pseudoramdom> @glozow picking chunks in the order of highest to lowest feerate
17:22:43 <Murch[m]> abubakarsadiq: Hausa would be confusing to most of us :~
17:22:54 <sipa> Murch[m]: :D
17:22:54 <abubakarsadiq> :P
17:24:01 <glozow> so let's start with: How would a client of BlockBuilder use it to build a block? When would GetCurrentChunk, Include, and Skip be called?
17:24:03 <monlovesmango> the algorithm for selecting transactions is to group related tx into clusters, and then linearize each cluster into chunks by their fee rate (this part i'm still fuzzy on), and then order all chunks by fee rate, and then pick chunks by decreasing fee rate (skipping chunks from clusters that have had a chunk skipped)
17:24:28 <glozow> monlovesmango: yes!
17:24:31 <monlovesmango> eviction is the same but starting from lowest fee rate
17:25:06 <abubakarsadiq> It's a linear algorithm that just get the current chunk recommended by block builder and include it when it satisfy a condition  or skip it when it didn't
17:25:45 <abubakarsadiq> Not sure why a chunk will be skipped is it because of blockmintxfee?
17:25:56 <pseudoramdom> GetCurrentChunk would give the "best" chunk available?
17:25:58 <monlovesmango> i think if the cluster can't fit in a block?
17:26:03 <glozow> abubakarsadiq; can you think of a nother reason?
17:26:20 <glozow> monlovesmango; yes! but s/cluster/chunk
17:26:42 <glozow> What is the expected lifetime of BlockBuilder (is it similar to CTxMemPool’s or very different)?
17:26:51 <abubakarsadiq> thanks @monlovesmango
17:27:03 <monlovesmango> oh, but then why does it remember what to skip by cluster?
17:27:17 <glozow> monlovesmango: what happens if it doesn't?
17:27:43 <sipa> monlovesmango: once any chunk in a cluster has been skipped, nothing else from the cluster can't be included anymore, because the later transactions in the cluster may depend on transactions from the skipped chunk
17:27:47 <sipa> oh, sorry, spoiler
17:28:04 <abubakarsadiq> It is different, you should discard it immediately you are done building a block template.
17:28:04 <abubakarsadiq> TxGraph mutation methods can't be triggered  when we have a block builder instance;
17:28:14 <monlovesmango> it will evaluate a chunk fromt he same cluster, which likely has missing dependencies! hah yeah what you said
17:28:38 <glozow> is it necessarily true that nothing else from the cluster can be included/
17:28:42 <glozow> ?* ugh my shift key
17:28:56 <sipa> glozow: you used it correctly for "English"
17:28:58 <monlovesmango> glozow: cool that makes a lot of sense thanks!
17:30:12 <abubakarsadiq> @sipa also if you skip a chunk in a cluster then that cluster linearization is incorrect yeah?
17:30:29 <sipa> abubakarsadiq: maybe
17:30:30 <monlovesmango> expected lifetime of BlockBuilder is short, as you can't make updates to txgraph if there is an observer right?
17:30:56 <glozow> If you skip something, you could still include its sibling, no?
17:31:01 <monlovesmango> should always be contained within CTxMemPool's lifetime
17:31:11 <sipa> abubakarsadiq: depends what you mean with correct; it won't be a linearization for the full cluster anymore as some transactions will clearly be missing, but it may still be a valid linearization for what remains of the cluster after removing the skipped chunk
17:31:51 <sipa> but BlockBuilderImpl (currently) doesn't try to reason about that because it's hard, and breaks the abstraction offered by linearizations/chunks
17:32:05 <glozow> monlovesmango: yes!
17:32:06 <sipa> so as soon as you skip anything of a cluster, it conservatively assumes nothing more from that cluster can be included
17:32:23 <abubakarsadiq> then if it is valid and topological even with the skipped chunk, arent miners losing on fees by skipping everything in the cluster?
17:32:36 <glozow> Why should `TxGraph` disallow changes while an observer exists?
17:32:42 <sipa> abubakarsadiq: yes, it is neccessarily an approximation, like block building always is
17:33:07 <sipa> abubakarsadiq: even the fact that we're only considering transactions in just a single order (the linearization) may result in small amounts of lost fees
17:33:21 <sipa> or the fact that it's an eager algorithm to begin with
17:34:25 <glozow> Can you create a BlockBuilder when staging exists? Can you build a block using the TxGraph’s state with its staged changes?
17:35:04 <monlovesmango> bc everytime TxGraph is updated it will need re-linearization, which you don't want to do while something is actively observing the ordering
17:35:26 <glozow> monlovesmango: exactly, it'll invalidate the chunk ordering that the observer is using
17:35:32 <pseudoramdom> Why should `TxGraph` disallow changes while an observer exists? - the ordering mught change, possibility of missing a tx if the underlying graph changed?
17:35:41 <abubakarsadiq> I think this case will likely happen towards the tail end of the block building process when we are close to the 4M `WU` limit.
17:35:41 <abubakarsadiq> And also I think majority of tx are single clusters so it is fine?
17:36:28 <monlovesmango> yes I think you can't create a BlockBuilder when staging exists, but you can't build a block using staging
17:36:39 <sipa> monlovesmango: correct
17:36:40 <monlovesmango> you can* create a BlockBuiler
17:36:46 <sipa> oh, *can*, indeed
17:36:53 <monlovesmango> haha
17:37:15 <abubakarsadiq> @glozow: I think you can create a block builder while we have staging; but the recommended chunks will always be from main
17:37:35 <glozow> yep yep
17:37:51 <sipa> specifically, if you were making changes to main while a block builder exists, what would go wrong (ignoring the fact that it's not allowed, and might trigger Assume failes)
17:38:35 <sipa> glozow: tell me to shut up if my extra questions make us move too slowly
17:38:36 <monlovesmango> sipa: I would imagine things like double including a tx, or missing txs all together
17:38:58 <glozow> sipa: all good
17:39:08 <abubakarsadiq> @sipa; I think you will mess up with chunk order and invalidate the chunk index iterators?
17:39:15 <sipa> abubakarsadiq: yep, that's it
17:39:42 <sipa> the m_current_chunk iterator in BlockBuilderImpl may end up referring to a chunk index entry that no longer exists
17:39:50 <sipa> which would be undefined behavior in C++
17:39:59 <abubakarsadiq> yeah
17:40:30 <monlovesmango> ok interesting. is there no way that it would point to an inaccurate index, but one that does exist?
17:41:14 <sipa> monlovesmango: that is definitely possible, the point of undefined behavior is that it makes the behavior of the entire program undefined
17:41:17 <sipa> so it might do that
17:41:26 <glozow> Does `BlockBuilder` modify `TxGraph`?
17:41:31 <sipa> it might also result in sending all your BTC away
17:42:32 <abubakarsadiq> yep in constructor and destructor, while incrementing and decrementing block builder observer
17:42:38 <monlovesmango> yes, it modifies observer count
17:43:13 <sipa> might it make any other changes in the constructor?
17:43:52 <abubakarsadiq> peeping at the constructor.......
17:44:01 <monlovesmango> MakeAllAcceptable
17:44:16 <sipa> ✅
17:44:32 <glozow> tada https://github.com/bitcoin-core-review-club/bitcoin/blob/27a0c93abb7e70b93214eb857e2046f848139e68/src/txgraph.cpp#L2394
17:45:05 <monlovesmango> which looks like it does ApplyDependencies, which will mutate txgraph
17:45:20 <sipa> indeed
17:45:30 <abubakarsadiq> I second :)
17:45:45 <sipa> but it doesn't make any *observable* changes to the graph, as in, ApplyDependencies would have been called anyway, but possibly later
17:45:50 <glozow> In some ways, "no," because the observable contents of the graph don't change - BlockBuilder doesn't remove transactions for exampl
17:45:55 <abubakarsadiq> It might not though when their is nothing to apply
17:47:13 <glozow> We already answered Q9 before, so moving on to Q10
17:47:22 <glozow> looking at this commit https://github.com/bitcoin-core-review-club/bitcoin/commit/3429e9d79df1336cf1d0a61cb5f9bf028aa860b2
17:47:34 <glozow> This commit adds new fields in data structures that need to point to each other: Entry now contains an iterator to the transaction’s ChunkData in m_main_chunkindex, and ChunkData refrence Entrys by their position in m_entries. In your review, how did you check that these pointers are always kept up-to-date?
17:49:06 <monlovesmango> wasn't able to finish trying to answer this question, but I would imagine that you want to check all the places where txgraph mutates (ApplyDependencies and Relinearize)
17:51:01 <glozow> Yeah, this is more of a "how do you review stuff?" question. I counted up the pointers and checked that there were assertions for them in `SanityCheck()`
17:51:18 <glozow> Conceptually, what are all the ways that an entry’s chunk index can change?
17:52:09 <pseudoramdom> when child tx is added/removed?
17:52:11 <monlovesmango> glozow: can you explain more about SanityCheck()?
17:52:46 <monlovesmango> when a tx is added or removed from that entry's cluster?
17:53:20 <monlovesmango> i guess also if any tx is added/removed from mempool
17:53:35 <pseudoramdom> oops, there could be more scenarios - maybe when feerate changes by RBF
17:54:12 <glozow> monlovesmango: sure. generally I think that if pointer consistency is checked in `SanityCheck` and the fuzzer is good at finding possible (mis)uses of `TxGraph`, I can feel reasonably confident that `TxGraph` is updating those pointers correctly
17:54:37 <sipa> pseudoramdom: that's the same thing... chunk feerates are a function of the linearization of a cluster, so anything that changes the linearization can affect it... and that includes RBF, but that is effectively through the cluster changes by adding/removing transactions from it
17:55:21 <sipa> glozow: and as abubakarsadiq already mentioned, to get confidence that the fuzzer is indeed capable of finding such problems, it's often good to just try introducing a bug you expect SanityCheck (or other assertion) to find, and see if it actually does
17:55:47 <pseudoramdom> gotcha yeah, thanks for claryfying. (For a sec I was wondering my messages were not going thr')
17:55:47 <glozow> monlovesmango: pseudoramdom: yeah, any of the mutators can change the chunk index
17:56:04 <sipa> also CommitStaging
17:56:14 <pseudoramdom> can clusters merge?
17:56:23 <monlovesmango> glozow: interesting thank you!
17:56:28 <glozow> pseudoramdom: yep!
17:56:28 <sipa> pseudoramdom: yes, by adding a dependency between transactions that are in distinct clusters
17:56:42 <sipa> also, invoking the ~Ref destructor can change clusters
17:56:54 <sipa> because it causes the corresponding transaction to be removed
17:57:02 <glozow> In the ChunkOrder comparator, when cmp_feerate != 0, why can it be returned directly without comparing position within the cluster?
17:58:35 <monlovesmango> bc fee rate is the first priority when determining order?
17:58:53 <sipa> monlovesmango: but why is that ok?
17:59:07 <glozow> monlovesmango: but why doesn't that violate any dependencies?
18:00:16 <monlovesmango> bc we know they are from different clusters?
18:00:28 <monlovesmango> hmm no
18:00:31 <glozow> No, they can be within the same cluster
18:01:00 <glozow> But chunks within a cluster are already in feerate order :)
18:01:31 <glozow> Uh oh, we're already out of time!
18:01:46 <glozow> We got through a lot today, thanks for coming everybody
18:01:55 <glozow> #endmeeting