Transaction priority research

[dj8yfo]

No description provided.

[vldm]

I should extend:
For now, we have tx pool, that is ordered by tx hash, this cause some problems:

1. There possibility that some transaction is depend on another, and we should execute it in some other than "by hash" order.
2. With ordered by hash transaction, there a possibility to censorship some of transaction, by spamming another ones with lowest hash.
3. Additionally some of transactions (for example configuration) is more important for network then other.

[slowli]

Some preliminary thoughts. Just want to share; nothing should be taken as an authoritative direction for implementation at this point.

There are 2 problems associated with tx prioritization:

• Problem 1: Tell whether a particular transaction is ready for inclusion into proposal. This problem is internal to the transaction definition (i.e., can be encapsulated within Transaction trait).
• Problem 2: Prioritize transactions globally; i.e., for each 2 transactions tell the priority of which is higher (while there may be some tx pairs with undefined ordering, this does not influence the analysis below). This clearly cannot be a part of the transaction interface because we may need to order transactions of different classes.

Problem 1 analysis

Transactions can be in one of 3 states determined by the current blockchain state (affected by previous transactions in a block proposal - more on that later):

• Transaction may be rejected. For example, it may be expired (provided we have time-limited txs), or it may have a counter lesser than the currently used for the author of the tx (provided we have CAS based on incrementing counters). Importantly, this status may not change in the future; which means that as soon as a tx reaches this status, it can be safely evicted from the mempool, added to the rolling Bloom filter for rejected txs (if we're going to implement it), etc. (To clarify, unless there is a consensus rule not to include rejected txs into blocks, there must be a way to get a tx even if it's rejected.)

• Transaction may be ready. For example, in the case of a counter-based CAS, the counter expected by the tx is precisely the same as in the current blockchain state.

• Transaction may be pending. For example, in the case a counter-based CAS, the counter expected by the tx is more than in the current blockchain state. Unlike rejected txs, pending txs can become ready in the future; they are similar to orphaned txs in Bitcoin or txs with future counters in Ethereum.

With this classification in mind, rejected txs should never be in proposals (in fact, they can be removed from the mempool as described previously), neither should pending txs. Now, the tricky part is that the tx state can change after applying any tx in the block proposal (and we don't execute txs when forming a proposal). This leads to

Question 1. Can txs be executed during forming a proposal? How will it impact consensus?

Assuming this is solvable, it's inefficient to update statuses of all txs in mempool after applying a single tx. Fortunately, this seems somewhat solvable; a tx may declare in its interface which key(s) in the blockchain state its status depends on, so that only statuses of relevant txs may be updated after each tx execution. Notice that the amount of keys is quite small in many practical use cases; e.g., a counter CAS depends on a single key (the counter), a blockchain height-based timelock - too (assuming blockchain height is stored somewhere in the state), a coins transfer tx - too (the balance of the sender).

Question 2. How does this work with composable/embeddable txs? E.g., how the author will be computed for a coins transfer tx if it's embedded somewhere, e.g., after a timelock or a multisig? Needs more research.

Problem 2 analysis

Within the composable tx model, there is a single endpoint that embeds all other transactions (e.g., authenticated tx in the most generic case). IMO, it's logical to introduce tx priority (e.g., numeric) to the interface of this entry endpoint. Notice that it may work in more complex use cases, say, when we have tx fees (implemented, say, as a batch tx, with the first component being payment to the validators). The aforementioned entry endpoint method may inspect that an embedded tx is a batch with a fee payment, and if not, drop the tx, and if it is assign the priority based on the fee. Of course, there is a room for more complex logic; e.g., there may be certain tx types without fees (say, configuration updates, as you mention earlier).

Question 3. How are the 2 problems combined into final prioritization? Is it possible to combine them into a single interface?

To reiterate again: these are preliminary thoughts only; feel free to ask questions and criticize. I assume (because I want to believe) that composable txs will be implemented in the observable future; to my mind, they will help tackle this and other problems significantly.

cc @vldm @defuz @gisochre for visibility.

[dj8yfo]

@slowli
Problem 1

Do i get possible state transitions for a transaction right
(after execution of another transaction):

• rejected -> rejected
• pending -> {pending, ready, rejected}
• ready -> {ready, rejected}

Now, the tricky part is that the tx state can change after applying any tx in the block proposal (and we don't execute txs when forming a proposal).

How's that? Pleaze be a bit more specific with a scenario.

---

1. Do we need pending status? Do we need an orphaned (sub)pool?
   With a block header each 10 seconds (more sparse without tx load if we ever finish and test Timeout adjusters refactoring #256 ) it only comes at a price of 600 mb/year of block headers. Which is a drop in the ocean of 3000 txs/sec ;
2. Currently we have only ready status. I'd start with incrementally adding rejected status and thinking about the merits of pending meanwhile.
3. What are the merits of recounting status of all affected transactions after executing each one during forming propose?
   Why not just shoot off those which accidentally became ready -> rejected? During execution of block (as they are now).
   And revaluating the status of next portion, being added to next propose.
   With respect to interaction with storage the read-only part of verify is faster than read+write part of execute which has to embed all checks of verify anyway. At least, not slower.
   (It's hard to come up with an example when all or some of verify checks have to be ommitted during execute).
4. Thus, i'm thinking of a 3-tier scheme:
   • verify before adding to txPool. if !self.verify_full(snapshot) reject()
   • verify before adding to newly formed propose. (whereas some lucky txs (propose participants) may be verified only once by combining the add-to-pool and add-to-next-propose-if-its-not-alread-full steps). if !self.verify_storage(snapshot) {remove_from_pool(self); reject()}
   • verify as an embedded preliminary check of execute. It can be defined so at Transaction trait level.
     as in:

     fn execute_template(&self, fork: &mut Fork) -> Status {
         if !self.verify_storage(fork.as_ref()) {
             crit()
         }
         else {
             self.exexute_everything_else(fork)
         }
     }
     

verify_full = verify_inner + verify_storage