Add a native solana instruction to check ordering.

[godmodegalactus]

Problem

Currently for mango, marker makers used a special program which checks the ordering of transactions. The transaction is canceled if the order in the program is not greater than the expected order. We have write lock contention most of the transactions take a write lock and fail because of the incorrect ordering. Market makers spam the cluster and most of these transactions are failed because they do not come in the right order to the leader. This feature is important for market makers they want to enforce that only the most updated price is in the orderbook.

For stats : https://dune.com/iwillnotsaveyou/sequence-enforcer Program id : GDDMwNyyx8uB6zrqwBFHjLLG3TBYk2F8Az4yrQC5RzMp Code : https://anchor.projectserum.com/build/313

Proposed Solution

Make a special instruction like ComputeBudget in solana which will enforce sequencing. Check the sequencing before creating the transaction batches so that we filter out transactions which cannot be executed which will improve write lock contention.

[godmodegalactus]

Having this feature is very important before implementing https://github.com/solana-labs/solana/issues/21883

[apfitzge]

~Link to the code is not working for me~ Not sure why the link doesn't work - navigating there manually works

[godmodegalactus]

Link to the code is not working for me

Could you check now, Go to https://anchor.projectserum.com/build/313 and then its programs/sequence_enforcer/src/lib.rs

[godmodegalactus]

@apfitzge saw your message on the tx-scheduler channel, I do not have permission to reply. But you are correct about not locking write accounts if the transaction is going to fail because of sequencing. We can still take a small transaction fee for reading the account for example. I am still thinking of a better solution for removing the need for an SequenceAccount account as searching the account while batching the transactions could be expensive.

[apfitzge]

I am still thinking of a better solution for removing the need for an SequenceAccount account as searching the account while batching the transactions could be expensive.

Yeah that was one of my initial concerns. Other being that until we get central scheduler we'd probably have to check the sequence multiple times - once when we put it into a batch, then again after locking. That's better once we only have a single thread doing the "locking".

Going to have to think about it more in general as well. Not gonna happen in the next few days, and I'm trying to wrap some stuff up before breakpoint - I'll keep thinking about this.

[ryoqun]

@godmodegalactus hey, I'm another scheduler guy.

This feature is important for market makers they want to enforce that only the most updated price is in the orderbook.

just curious. why not just continuously out-bid your own older txes by small increment of SetComputeUnitPrice?

from validator's perspective, they just want to maximize tx fees. so, they just pack txes as much as possible, not caring tx fails or not. Prioritization doesn't incur incentive misalignment, so that works as best-effort basis. but, sequencing introduce misalignment unfortunately. that means, we need some deterministic check, which in turn costs some considerable overhead.

The thing would be different story if all of your txes are need to be executed in that order without loss like program deploy. ;)

anyway, the bright future is that once my (centralized) scheduler did ever land, compute unit price based ordering should work nicely.

[ryoqun]

also, note that a bit convoluted but you can use ephemeral barely-funded fee payer accounts as a nonce. so, once the highest-paying tx got included into a block, all other stale txes of the some kind of same generation or older won't get included due to unfunded transactionerror.

[mschneider]

let me give a bit of background on the use-case:

A reasonable update frequency for HFT traders is around 10hz, so they sign and submit a transaction every 100ms. The desired logic here is that when the cluster process a new update (t=0), that prevents any update (t<0) from ever getting processed as it contains stale data. In the current forwarding scheme with RPCs resubmitting transactions or leaders forwarding transactions to the next leader, a block usually contains various transactions from -30s < t <= 0. The custom program linked above is currently being used to narrow down which one of those execute.

Continuously increasing your fee is a solution on blockchains with fast finality and slow block times. I don't see how it can work economically for users. If you have only 100ms to submit a new tx, but you need to wait ~30s for finality, then it's really difficult to ever stop increasing fees / reset them. The goal of this proposal is to reduce block space consumption in order to minimize fees.

@ryoqun I understand the techniques you propose, but I don't see how they address the problem. Could you elaborate?

[ryoqun]

@mschneider thanks for detailed explanation. love to see concrete use case of solana for hft.

well, I wanted to say that you can just continue to use the sequence-enforcer program as before with some tweaks.

Given the explanation, I'm still thinking the status quo solution is the best for market-maker's interest (desired strict enforcement of sequencing). I'm not sure adjusting something at protocol level would be workable, because validator is basically free to reorder/censor txes and introducing these rules complicates solana impl considerably. (fyi, I'm trying to plug the reordering/mev ability: #23837).

That said, the remaining problems are 1. low success rate, 2. write contention., 3. spam

I suggested ComputeUnitPrice for 1., paired with the sequence enforcer program. Say, there are on-flight txes: txA(t=-2), txB(t=-1), txC(t=0) in some way in a cluster (rpc/forwareding/leader's buffer, etc). mm want txC to succeed. They're treated equally without prioritization hint. On the other hand, if txA(prioritization fee=1 lamport), txB(p.f. = 2 lamport), txC(p.f. = 3 lamports), txC is prioritized as much as possible for scheduling/forwarding (assuming centralized scheduler/forwarder within each nodes; i.e. no multiple banking threads).

Assuming mms can tolerate some degraded ordering guarantees for few secs, they can reset prioritization fees minutely. Fee increments can be done by 1 lamports. So, 600txs/min = 180_300 lamports for priotization cost (=sum(1,600)), along side the base sig fees for those txes: 3_000_000 lamports (= 5_000 * 600). guess this is acceptable extra cost relatively?

as for 2., it's not problem as soon as local fee markets are in place; heavy (yet local) write contention for mm's sequence address shouldn't be problem for a cluster as a whole

as for 3., it's not problem as well for cluster's view point. these failed txes are fine txes, which burns 50% fees with fast tx termination, meaning less block space is consumed for the collected fee. indeed, mms want to avoid to pay for these failed txes. but I think they're paying necessary premium for what they're doing: continuous onchain state mutation on top of ordered guarantee. (the ephemeral fee payer is rather complicated legimate trick to save the fees, though)

happy chat more. :) please remind that I'm not wanting to be a meanie. Rather, I'm passionate to create high-performance blockchain for hfts.

[godmodegalactus]

@ryoqun : In a distributed system we cannot guarantee that the current leader has knowledge of all the transactions. In your example if the current leader is only aware of txA and txB it will execute txB as it is unaware of txC. The next leader cannot execute txC as there are insufficient funds in nonce but the MM wants to execute txC as it is most recent price. MM only care if all txA, txB and txC are executed in exactly this order (i.e txB or txA should not ever be executed after txC).

for 2. The write contention is not actually local but we will acquire write locks on serum spot markets which are used not used in this context but also by other protocols.

This issue will be very interesting to solve when there is a huge congestion in the system we can easily filter out the transactions which are definitely going to fail because of the sequence enforcer.

[tao-stones]

@godmodegalactus can you elaborate proposed solution? Does the new ix provide to leader the sequence number of transaction, and if leader keeps the last sequence number as a local state, then it could drop transactions that satisfy condition of tx.ix.sequence_number < leader.local_state.last_packed_tx.ix.sequence_number?

[godmodegalactus]

@taozhu-chicago yes exactly. But this sequence number is different for each user. After some thoughts we could incentivize validators more to process these transactions.

[tao-stones]

Makes sense sequence_number is per user_id. I'm wondering, since you are preparing to incentivize validators to allocate cpu/memory to honor the ordering, would it be possible to do this during packet receiving, before sending to validator? My initial thoughts are similar to @ryoqun's that modifying protocol may not be the best course, but I need to understand the issue more.

[apfitzge]

After some thoughts we could incentivize validators more to process these transactions.

@godmodegalactus trying to think through how this would work from a malicious point of view, and I'm not sure this really solves a problem in a satisfying way once we have a scheduler.

I think the ideal case for the user is that a scheduling algo would only keep & process the most up-to-date (highest seqnum) transaction: in your example txC. With txA, txB being dropped either with no fee or small fee.

But if I'm a greedy validator, and I'm aware of all 3 txs/sequencing, the way I make the most money is by processing them in sequence order - i.e. A, B, C and collecting full fees for each. Even with @ryoqun's suggestion of out-bidding your previous txs, i.e. increasing priority order, a greedy validator would process them in reverse-priority order here. I think the native sequencing potentially just makes it easier for the validator to do this, thought it's possible even without it.

Overall, I think having a default priority-order scheduler that's more efficient than current approach solves most of the concerns this proposal is considering. As I mentioned in-person, it's probably best to re-consider this once we have a centralized scheduler in-place and see how things are performing then.

[godmodegalactus]

@apfitzge @taozhu-chicago We can wait and check the performance difference after releasing the first scheduler implementation. This feature will help to prefilter the transactions so that we avoid extreme write lock contention on the market accounts like event queue, asks and bids when there is a lot of congestion. But I agree this problem will be less important (impacting) if the scheduling stage is improved.

[SpaceMonkeyForever]

What happened to this idea, guys? I came across this randomly while googling. Enforcing a correct sequence is indeed essential on Solana and if we can make that check cheaper for the validators, it will decrease the ratio of invalid TXs significantly (as you explained)