How does mempool Decide what transaction to prioritize

[gmaxwell]

In the new Bitcoin core cluster-based block template construction algorithm, i will like to know how are the clusters of interdependent parent-child transaction precisely defined and also identified,  i mean like what constitute the boundaries of a connected component in the transaction dependency graph?

A cluster is all unconfirmed transactions connected by any parent/child relationship.  It's essentially all the transactions that must be topologically sorted with respect to each other.

also i really dont know what specific algorithm is used to compute the topology- respecting linear order (parent for children ) that actually maximize the prefix-per-weight and how it compare in efficiency to standard topological sort?

The result that ends up in a block must be a topological sort to be consensus valid... but a topological sort is usually not unique.  If it is unique (like a linear chain of transactions) than that's what it'll use.  If you take an ordering and make a running sum of the fees you get as a function of taking more and more of the list starting at the beginning you get something that the developers call a "fee rate diagram".  The algorithm chooses an ordering that maximizes the area under this curve (and obeys topology, of course).  If there are multiple such orderings it has a number of tiebreakers, but they're seldom hit.  Maximizing the area under the curve can be shown to maximize miner income under the assumption that the miner will select some unknown-in-advance prefix of the linearized cluster.

For more info:

https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032

https://delvingbitcoin.org/t/how-to-linearize-your-cluster/303

[Curious T]

What happens if different nodes accept different versions temporarily?

Nothing, because after reaching a single confirmation, everyone will know, which version was placed in a block. And all new blocks on top of it simply couldn't include a second version, without invalidating that block.

So if two different nodes accept two different fees for a particular transaction, when the miners adds the transaction to a block, which fee does he use? Does it automatically becomes the new fee? If it's the old fee, then what happens to the new fee? What happens in that kind of situation?
Sorry for the rookie question.

[stwenhao]

So if two different nodes accept two different fees for a particular transaction, when the miners adds the transaction to a block, which fee does he use?

Each miner can include or reject any transaction, for any reason. That miner simply decides, what is included, and what is rejected. As long as the rules they use are similar between many different nodes, you can predict, what would be included, and what would be rejected.

Does it automatically becomes the new fee?

Changing anything in a transaction, including amounts, which would change the fee, causes it to have a new transaction ID, and can also invalidate some signatures in some cases, depending on what is signed by them. Which means, that if you have two or more transactions, spending the same inputs, then only one of them can be included in a block, otherwise, the whole block would be invalid.

And then, of course, one miner can include one transaction, and another miner can include a different version, and you can have two different valid blocks, on the same height. Then, the stronger chain will decide, what is valid, and what is not, and next blocks, built on top of it, will show you the right chain.

If it's the old fee, then what happens to the new fee?

Finally, only one version is included, and considered as confirmed. Other versions of the same transaction are invalid, if something becomes deeply confirmed. With each and every block, it becomes exponentially harder to change transactions in the older blocks.

[hmbdofficial]

So if two different nodes accept two different fees for a particular transaction, when the miners adds the transaction to a block, which fee does he use?

Each miner can include or reject any transaction, for any reason. That miner simply decides, what is included, and what is rejected. As long as the rules they use are similar between many different nodes, you can predict, what would be included, and what would be rejected.

Does it automatically becomes the new fee?

Changing anything in a transaction, including amounts, which would change the fee, causes it to have a new transaction ID, and can also invalidate some signatures in some cases, depending on what is signed by them. Which means, that if you have two or more transactions, spending the same inputs, then only one of them can be included in a block, otherwise, the whole block would be invalid.

And then, of course, one miner can include one transaction, and another miner can include a different version, and you can have two different valid blocks, on the same height. Then, the stronger chain will decide, what is valid, and what is not, and next blocks, built on top of it, will show you the right chain.

If it's the old fee, then what happens to the new fee?

Finally, only one version is included, and considered as confirmed. Other versions of the same transaction are invalid, if something becomes deeply confirmed. With each and every block, it becomes exponentially harder to change transactions in the older blocks.

In the scenario you describe, where a user broadcast a low-fee transaction and later creates a conflicting replacement transaction ( with higher fee, different Transaction ID, and potentially adjusted sequence number to enable RBF), how do modern Bitcoin nodes and miners like you distinguish between an opt-in RBF replacement (BIP 125) versus a full RBF replacement? Specifically;
- what checks are also performed on the n sequence field, transaction id and signature before a node accept the replacement into its mempool?
-does the two different propagated transactions have any practical implications for wallet developers based on on confirmation reliability and double spending monitoring, especially once the winning chain reach 6+ confirmation?

[stwenhao]

how do modern Bitcoin nodes and miners like you distinguish between an opt-in RBF replacement (BIP 125) versus a full RBF replacement?

If you have full-RBF, then it means all transactions are unconditionally replaceable, based on fees alone. Which means, that you can have Alice to Bob transaction with low fees, replaced by Alice to Charlie transaction with higher fees. Unconfirmed means unconfirmed, if you want to trust unconfirmed transactions, then you need another protection as well, for example multisig, or Proof of Work inside Script, or whatever else you want to require, to minimize the risk, that coins will be sent in a completely different way.

what checks are also performed on the n sequence field, transaction id and signature before a node accept the replacement into its mempool?

If transaction is valid, then it is considered as a possible replacement. If not, then it is rejected immediately, because of not meeting the relay rules in a given node. First, all transactions are checked in the same way, and then, replacement rules are checked only between transactions, which can spend the same inputs.

does the two different propagated transactions have any practical implications for wallet developers

You can see that in regtest. If some transaction reaches a single confirmation, and then a chain reorganization will invalidate it, then it will be shown as invalid. In Bitcoin Core, it is displayed as "Conflicted" on the list of transactions in that case.