murchandamus / blockbuilding Goto Github PK

There are broken image links in the 'Block Building' gist below, which make the content hard to follow.

https://gist.github.com/murchandamus/5cb413fe9f26dbce57abfd344ebbfaf2

We only use transactions that were eventually included in the blockchain as it is otherwise hard to impossible to get all relevant meta data. Currently, mempools are pruned per the allowlist created from the transactions that occurred in the same month. If we instead used an allowlist created from all months this would give our blockbuilders a bigger set of transactions to work with, especially towards the end of a month when the mempool is not empty.

A simple approach would be to also include the transactions from blocks until the next time the mempool fully cleared after the end of the month. A more comprehensive approach would be to train a cuckoo filter on all transactions confirmed starting with the first month we consider and use that as a replacement of an allowlist explicitly encompassing all transactions.

Keep all transactions sorted by feerate, and only backfill the ancestry when the individual transactions become relevant per their feerate. When backfilling ancestors, also register all relevant children and descendants from the currently observed transaction set to the whole set.

Effect: Instead of processing the whole transaction set and backfilling all transactions even when some will never be considered for blockbuilding, this will only do the graph traversals for transactions relevant to the selection process. Could improve processing performance if we do a lot more simulations.

Currently, all transactions are clustered after they're loaded by the candidate-set-based blockbuilder. If we were to run a lot more simulations, it would probably be more performant if transactions were only clustered on demand. All transactions would be sorted by feerate, and while there is a transaction with a higher individual feerate than the best candidate set of the current cluster, that transaction would get clustered to potentially discover a better candidate set.

This should allow the blockbuilder to forgo clustering of most transactions when the mempool is very full, but since any transaction that individually has a higher feerate would cause itself and all of its ancestors to get clustered, any transactions that pay a higher feerate than the current best candidate set would have had to been considered before, and therefore we should expect to have the best candidate set globally even while lazily evaluating clusters.

This no longer links to the document you are refering to.

https://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#file-candidate-set-based-block-building-md