Verify Mempool Candidate Iteration Algorithm

Is your feature request related to a problem? Please describe. This issue asks for better ability to verify that the mempool walk algorithm is correct.

It is motivated originally by the fact that I ran the stacks-inspect try-mine tool on the chain state saved at (https://storage.googleapis.com/hiro-public/mainnet.tar.gz). I got a block with only 2 transactions from 44 candidates:

DEBG [1657539187.515011] [src/chainstate/stacks/miner.rs:2111] [main] Anchored block transaction selection finished (child of 05eeea820cb6283bfe5cdc34db756236eb0f47610a246fc995808a5641f3d7f4): 1 transactions selected (44 considered)
DEBG [1657539188.796492] [src/chainstate/stacks/miner.rs:2151] [main] Miner: mined anchored block, block_hash: 0ef5706030aeb4dbd12f747d556662a8a6f6a88103addf599fc155ec89cae34d, height: 65116, tx_count: 2, parent_stacks_block_hash: 05eeea820cb6283bfe5cdc34db756236eb0f47610a246fc995808a5641f3d7f4, parent_stacks_microblock: e274103c8d343cdc6f3e9dc06e91af2746495e47e1f9af08dc2da267efab577b, parent_stacks_microblock_seq: 3, block_size: 575, execution_consumed: {"runtime": 1326849, "write_len": 689, "write_cnt": 9, "read_len": 441018, "read_cnt": 79}, assembly_time_ms: 42219, tx_fees_microstacks: 180

This led to me to wonder if there might be a bug in the candidate selection algorithm. I don't know if there is. Maybe there is or maybe this was the size of the mempool at the relevant time. I haven't had a chance to cross-reference what the mempool might have been then.

However, this request is based on the experience I had trying to figure out if the mempool walk might have a bug.

Currently, the candidate selection algorithm is coupled with the processing of transactions. That is, they can't be separated. Processing a transaction is relatively slow (e.g., 1 transaction per second). Thus, most times there is not time to walk the entire mempool, while processing transactions along the way: https://github.com/stacks-network/stacks-blockchain/blob/08c163bab484954b3934515ee7bf60848f52ed4a/src/core/mempool.rs#L1013

Thus:

at no point is the entire mempool actually traversed in its entirety by anyone (either miner or follower)
we cannot separate out the traversal of the mempool into a separate object to analyze (#3188)

Also, from the documentation we have, it is not actually clear what the algorithm that we are running is: https://github.com/stacks-network/stacks-blockchain/blob/08c163bab484954b3934515ee7bf60848f52ed4a/src/core/mempool.rs#L892

We noticed in the Friday meeting that none of us could describe this algorithm at a high level. But, this is a very central algorithm for the chain!

Describe the solution you'd like I propose the following set of changes:

1) Separate out the creation of a mempool traversal from the processing of transactions. This way, the entire traversal can be accomplished quickly, and then analyzed. 2) Develop pseudo-code for this traversal algorithm, so that we can verify whether the implemented algorithm is correct with respect to the intended algorithm. 2) Add tests and/or other ways to verify (e.g., #3188) that the traversal is actually correct.

Additional context Part of debugging and fixing transaction throughput.

stacks-network / stacks-core

Verify Mempool Candidate Iteration Algorithm #3193