Written by Cavey, Jakob Povšič, and Max Resnick
On June 7, 2019, Cboe EDGA Exchange, Inc. filed with the SEC requesting permission to experiment with a rules change that they believed would improve liquidity in the market. The rule would give cancel orders on the exchange a 4ms asymmetric headstart. The SEC denied their request on the grounds that it was ‘discriminatory.’
“The proposed rule change is discriminatory in that the Exchange would delay incoming executable orders by 4 milliseconds, which would allow market participants with orders on the EDGA book that are not subject to the delay up to 4 milliseconds to cancel or modify their orders.”
- SEC 2019, Cboe EDGA Exchange, Inc.; Order Disapproving Proposed Rule Change To Introduce a Liquidity Provider Protection Delay Mechanism on EDGA
Lobbying and overregulation make it nearly impossible to experiment with new market structures in traditional finance. Some of Solana’s detractors have claimed it is also difficult to experiment with new market structures on Solana today because of its decentralized validator set. Those detractors are wrong. Contrary to popular belief, we have the technology to start experimenting with some types of Application Controlled Sequencing right now. This article introduces Asynchronous Market Queues (AMQs), an approach to transaction reordering that can be implemented purely within a Solana program without any changes to the Solana protocol.
The Problem
Motivation
If the price of an asset jumps suddenly, market makers need to rush to cancel their stale limit orders on order books before a trader pockets the difference. Traders outnumber the maker, so when jumps happen, makers are picked off more often than they can cancel. This creates an environment that is hostile to makers, leading to wider spreads. A DEX on Solana may want to offer makers a more forgiving experience so that the DEX can offer tighter spreads.
The Solution
What is Application Controlled Execution (ACE)?
Application Controlled Execution can be described as a dynamic internal auction mechanism for execution that is specified by the application – an alternative to first-come, first-serve. This auction can be done in many different ways, but the simplest is to batch all of the transactions for a market over a block and let the programs decide the ordering. For the case of the order book or AMM, the application can now directly specify that all cancels or price updates in the auction are sorted before limit orders. This gives makers more leeway in canceling stale orders, and allows them to tighten spreads accordingly.
There are two forms of ACE, one which is stronger than the other. There are benefits and drawbacks to both.
A weaker form of ACE can be implemented in the core protocol by allowing individual programs to inspect transactions and specify some priority prior to ordering, and then the core protocol merges the specified priority for the individual instructions into some final transaction priority. This is a weaker form because a transaction that includes a low priority instruction according to some program A with a high priority instruction according to some program B will have a conflicting priority ordering with some other transaction that includes a high priority instruction according to A with low priority according to B. However, this form preserves atomicity.
A stronger form of ACE can be implemented in programs, without any changes to the core protocol of Solana. This form breaks the atomicity of execution (and, to some extent, the composability of programs) but allows for all transaction instructions to be ordered as specified by the programs. This degraded composability occurs because other programs cannot atomically compose with asynchronous instructions since their execution is deferred. This can be implemented today in what are called Asynchronous Market Queues (AMQs).
What are Asynchronous Market Queues (AMQs)?
Solana programs have the ability to implement a mixture of synchronous instructions, as well as asynchronous instructions which are queued (instead of immediately executed) and then sorted in any manner as specified prior to execution. This asynchronous window allows the program to batch multiple instructions from different transactions and users, then process them in a priority order that benefits the application's design goals.
How AMQs Work
An AMQ implementation divides program instructions into two categories:
- Synchronous Instructions: These execute immediately when called. Examples include initializing user accounts, deposits, withdrawals.
- Asynchronous Instructions: These are queued when called and processed later based on application-defined priority. Examples include cancel orders, limit orders.
The program stores a priority queue in its own program state. When an asynchronous instruction arrives, instead of executing immediately, do:
- Assigned the instruction a priority based on the instruction type
- Tag it with the current slot and sequence number
- Add it to the queue to be executed with ACE-time priority
Later, a separate instruction processes the queue, but only after a configurable delay (e.g. slot + 1, or when the queue is full). During processing, instructions execute in priority order rather than arrival order.
It’s important to note that this form of ACE does not necessarily add any additional latency to the finalization of state compared to one implemented at the core protocol level, i.e. one which would reorder transactions in a block prior to execution. Similar to asynchronous execution at the core protocol level, even if the asynchronous queue is not fully empty and executed, the final state is already determined once the ACE period is over.
These queues can be very large (16384 actions is easily possible), but should be at least large enough to support 512 actions to defend against transaction bundles which attempt to fill the queue and begin cranking.
Implementation Example
Consider a DEX implementing AMQs with the following instructions:
- Cancel orders (asynchronous priority 1)
- Limit orders (asynchronous priority 0)
- Deposit, Withdraw (synchronous)
The next page features pseudocode showing how this can be implemented (no auth checks, asset transfers, etc)
pub process_instruction( accounts: &[Account], instruction: Instruction ) {
match instruction {
Instruction::Cancel(id) => queue_cancel(accounts, id),
Instruction::Limit(side, price, amount)
=> queue_limit(accounts, side, price, amount),
Instruction::Deposit(amount) => process_deposit(accounts, amount),
Instruction::Withdraw(amount) => process_withdraw(accounts, amount),
Instruction::Crank => crank(accounts),
}
}
/// synchronous instructions
fn process_deposit( accounts: &[Accounts], amount: Amount ) { /* deposit now */ }
fn process_withdraw( accounts: &[Accounts], amount: Amount ) { /* withdraw now */ }
/// These are inserted into a tree in the queue account by
/// 1. slot (earlier slot comes before later slot),
/// 2. then by priority (0 comes before 1)
/// 3. then by seq
enum Operation {
Cancel(Id), // disc = 0
Limit(Side, Price, Amount), // disc = 1
}
fn queue_cancel( accounts: &[Account], id: Id ) {
let queue_account = &accounts[0];
let slot = get_current_slot();
let seq = get_and_increment_seq(queue_account);
queue_operation(queue_account, Operation::Cancel(id), slot, seq);
}
fn queue_limit( accounts: &[Account], side: Side, price: Price, amount: Amount ) {
let queue_account = &accounts[0];
let slot = get_current_slot();
let seq = get_and_increment_seq(queue_account);
queue_operation(queue_account, Operation::Limit(side, price, amount), slot, seq);
}
fn crank( accounts: &[Account] ) {
let queue_account = &accounts[0];
let current_slot = get_current_slot();
// iterates sorted by slot, then by op priority, then by seq
for (op, slot) in iter_ops(queue_account) {
// current auction (slot) has not ended yet
if slot == current_slot { break }
process_operation(queue_account, op);
}
}
Here's a concrete scenario showcasing the ordering functionality with a 10% price spike:
Slot N: 1. Market maker deposits $10,000
2. Market maker queues sell order @ $100
3. Funds locked, order pending execution
Slot N+1: Price jumps to $110 (10% spike)
1. Crank executes, sell order at $100 in force
2. Arbitrageur deposits $10,000
3. Arbitrageur queues buy order @ $100
4. Market maker queues cancel order for $100 sell order
Slot N+2: Process queue (second auction window closes):
1. Cancel order executes first (priority 1)
2. Buy order fails - no matching sell order
Result: Market maker avoids $1,000 loss
A market maker deposits funds synchronously, and then queues two limit orders to make a market. When the limit order is queued, the deposited funds are locked, preventing synchronous withdrawal. Eventually these orders are executed and the market is made.
After a large price jump, an arbitrageur deposits funds synchronously, and then queues a limit order for a buy. When the limit order is queued, the deposited funds are locked (preventing synchronous withdrawal).
The market maker then has until the end of the auction window (1 slot) to queue a cancel order. Due to the higher priority, the cancel executes before the arbitrageur's order.
While cancel orders could be implemented synchronously to remove orders from either the order book or the async queue immediately, this would create too much of an unfair advantage for makers over takers, resulting in poor execution for the user (e.g. instantly removing all orders up to the user’s limit price).
Enforcing ACE
AMQs offer an alternative to sequencer based approaches to application specific sequencing; however, similar to all other forms of ACE that do not involve multiple proposers, AMQs can still be bypassed by a validator within protocol enforced tick boundaries through censorship and delay. Shorter slot times, faster leader rotation, and multiple concurrent leaders all complement AMQs by increasing the frequency of protocol enforced ticks that can be referenced by AMQ programs.
Conclusion
Application Controlled Execution through Asynchronous Market Queues offers a powerful primitive for Solana applications. By moving away from pure first-come-first-serve ordering, applications can create more sophisticated mechanisms that benefit specific application goals. While AMQs come with tradeoffs, such as killing atomicity and degrading composability, they demonstrate that significant improvements in execution ordering are possible today without protocol changes.
Developers interested in implementing AMQs can find our reference implementation for a simple counter program here: https://github.com/cavemanloverboy/ace
