Orders

For each market, Econia tracks bids and asks in two places:

1. A global OrderBook resource for the market.
2. A user-specific MarketAccount for each user trading on the market.

Order book structure​

Econia uses a custom data structure, the AVL queue, for storing orders. In short, the AVL queue combines an AVL tree with a doubly linked list at every tree node, where tree nodes are price levels and list nodes are orders. For example, consider the following "ascending" AVL queue:

                                   1001 [35 -> 38]                                  /    \              [50 -> 60 -> 55] 1000    1003 [20]AVL queue head ^                      /    \                         [15 -> 5] 1002    1004 [4 -> 10]                                                      ^ AVL queue tail

Here, orders are sorted by:

1. Increasing price, then
2. Increasing order of insertion within a price level.

Conversely, consider the following "descending" AVL queue:

                        992 [25 -> 28]                       /   \   [30 -> 40 -> 45] 991    994 [18] AVL queue tail ^         /   \              [14 -> 4] 993   995 [11 -> 2]                                   ^ AVL queue head

Here, orders are sorted by:

1. Decreasing price, then
2. Increasing order of insertion within a price level.

Each OrderBook has an ascending AVL queue for asks, and a descending AVL queue for bids, such that the two structures above produce the following price-time priority order book:

PriceSizeSide
PriceSizeSide
99511Bid
9952Bid
99418Bid
99314Bid
9934Bid
99225Bid
99228Bid
99130Bid
99140Bid
99145Bid

Here, a large taker buy will fill against asks in the following sequence:

1. Price 1000, size 50
2. Price 1000, size 60
3. Price 1000, size 55
4. Price 1001, size 35
5. ...

Similarly, a large taker sell will fill against bids in the following sequence:

1. Price 995, size 11
2. Price 995, size 2
3. Price 994, size 18
4. Price 993, size 14
5. ...

Insertion​

When a new order is placed, it is inserted at the tail of the corresponding doubly linked list for the given price level, if such a price level is already in the tree. For instance, continuing the above example, placing an ask order for size 18 at price 1003 would lead to the following asks AVL queue:

                     1001 [35 -> 38]                    /    \[50 -> 60 -> 55] 1000    1003 [20 -> 18]                        /    \       ^ new list node           [15 -> 5] 1002    1004 [4 -> 10]

Attempting to place another ask at a price of 1005, however, would require inserting a new tree node, yielding an unbalanced AVL tree:

    1001   /    \1000    1003       /    \    1002    1004                \                1005

And this would require a rotation:

        1003       /    \    1001    1004   /    \       \1000    1002    1005

This self-balancing behavior reduces lookup cost reductions, since the upper limit on AVL tree height is approximately $1.44 \log_2 n$, where $n$ is the number of tree nodes.

tip

See the AVL queue height spec for more mathematical properties and derivations.

Without an upper bound on the number of price levels, however, the tree can still grow to prohibitive sizes, since Aptos' storage gas schedule charges per-item costs. In particular, each tree node is a table entry, meaning that lookup gas costs increase linearly with tree height.

Eviction​

To prevent tree height from growing too tall, the AVL queue supports eviction functionality, whereby the AVL queue tail is popped upon insertion of a different order, if one of two conditions are met:

1. The tree exceeds a specified critical height, or
2. The AVL tree cannot fit any more orders.

Presently, the AVL tree supports up to N_NODES_MAX = 16383 orders at a time, meaning that for a critical height of 18, for example, up to 16383 orders, each at a different price level, are supported. At a critical height of 10 however, eviction may happen for as few as 376 price levels, and is guaranteed to happen for 2048 or more price levels, due to the upper and lower bounds on price level count for a given height:

note

Again, see AVL queue height spec for supporting calculations.

Tree heightMin price levelsMax price levels
011
123
247
.........
102322047
113764095
.........
1810945524287
19177101048575

For example, consider the following price level tree:

    1001   /    \1000    1003

Here, the tree has a height of one, and if a critical height of 1 were chosen, the following order structure would be valid:

               1001 [12 -> 45 -> 67]              /    \[45 -> 78] 1000    1003 [19]

Up to 16377 orders could be placed at a price of 1000 without meeting the eviction criteria, but if an order were placed at price 1002, the tree would exceed the critical height and the next insertion would result in an eviction.

The first insertion at price 1002 results in a tree that exceeds the critical height for this example:

               1001 [12 -> 45 -> 67]              /    \[45 -> 78] 1000    1003 [19]                  /              1002 [43]

The next insertion at price 1002 results in an eviction, since the critical height has been exceeded prior to the insertion:

               1001 [12 -> 45 -> 67]              /    \[45 -> 78] 1000    1002 [43 -> 78]

Here, the single order at price 1003 has been evicted.

note

Econia does not use a critical height of 1. The actual critical height is defined at CRITICAL_HEIGHT.

Units and market parameters​

Consider a hypothetical trading pair APT/USDC, APT denominated in USDC. Here, APT is considered the "base" asset and USDC is considered the "quote asset", meaning that orders sized in APT are quoted in USDC per APT:

TermSpecifiesSymbol
Base assetOrder sizeAPT
Quote assetOrder priceUSDC

In addition to a base/quote trading pair, each market in Econia additionally contains the following parameters, which are selected by the market registrant during registration:

ParameterMeaningExample
Lot sizeOrder size granularity0.1 APT
Tick sizePrice granularity0.01 USDC
Minimum order sizeSmallest allowed order size0.5 APT

On this market, an order for 7.8 APT at a price of 5.23 USDC per APT would be valid, but the following would be invalid:

SizePriceReason
7.855.23Size too granular
7.85.235Price too granular
0.45.23Size too small

Econia's matching engine uses integers rather than decimals, such that conversion from decimal amounts to integer amounts requires the aptos_framework::coin::CoinInfo.decimals for a given CoinType:

TermSymbolCoinAmount
Base decimals$\large d_b$APT8
Quote decimals$\large d_q$USDC6

Here, a decimal amount of coins (e.g. 7.8 APT), can be converted to an integer amount of indivisible coin subunits (aptos_framework::coin::Coin.value):

>>> from decimal import Decimal as dec>>> decimals = 8>>> coins = dec('123.456')>>> subunits = int(coins * 10 ** decimals)>>> subunits12345600000

Similarly, other terms can be converted as follows:

VariableDecimal symbolInteger symbol
Lot size$\large l_d$$\large l_i$
Tick size$\large t_d$$\large t_i$
Minimum order size$\large m_d$$\large m_i$
Size$\large s_d$$\large s_i$
Price$\large p_d$$\large p_i$
Total quote amount to fill$\large a_d$$\large a_i$
1. $\LARGE l_i = l_d 10 ^ {d_b}$

>>> decimals_base = 8>>> lot_size_decimal = dec('0.1')>>> lot_size_integer = int(lot_size_decimal * 10 ** decimals_base)>>> lot_size_integer10000000
2. $\LARGE l_d = l_i 10 ^ {-d_b}$

>>> lot_size_decimal = dec(lot_size_integer) / 10 ** decimals_base>>> lot_size_decimalDecimal('0.1')
3. $\LARGE t_i = l_d t_d 10 ^ {d_q}$

>>> decimals_quote = 6>>> tick_size_decimal = dec('0.01')>>> tick_size_integer = int(lot_size_decimal * tick_size_decimal...                         * 10 ** decimals_quote)>>> tick_size_integer1000
4. $\LARGE t_d = \frac{t_i}{l_i} 10 ^ {d_b - d_q}$

>>> tick_size_decimal = (dec(tick_size_integer) / dec(lot_size_integer)...                      * 10 ** (decimals_base - decimals_quote)).normalize()>>> tick_size_decimalDecimal('0.01')
5. $\LARGE m_i = m_d 10 ^ {d_b}$

>>> min_size_decimal = dec('0.5')>>> min_size_integer = int(min_size_decimal * 10 ** decimals_base)>>> min_size_integer50000000
6. $\LARGE m_d = m_i 10 ^ {-d_b}$

>>> min_size_decimal = dec(min_size_integer) / 10 ** decimals_base>>> min_size_decimalDecimal('0.5')
7. $\LARGE s_i = \frac{s_d}{l_d}$

>>> size_decimal = dec('7.8')>>> size_integer = int(size_decimal / lot_size_decimal)>>> size_integer78
8. $\LARGE s_d = s_i l_i 10 ^ {-d_b}$

>>> size_decimal = dec(size_integer) * lot_size_integer / 10 ** decimals_base>>> size_decimalDecimal('7.8')
9. $\LARGE p_i = \frac{p_d}{t_d}$

>>> price_decimal = dec('5.23')>>> price_integer = int(price_decimal / tick_size_decimal)>>> price_integer523
10. $\LARGE p_d = \frac{p_i t_i}{l_i} 10 ^ {d_b - d_q}$

>>> price_decimal = (dec(price_integer) * dec(tick_size_integer)...                  / dec(lot_size_integer)...                  * 10 ** (decimals_base - decimals_quote)).normalize()>>> price_decimalDecimal('5.23')
11. $\LARGE a_d = s_d p_d$

>>> amount_decimal = size_decimal * price_decimal>>> amount_decimalDecimal('40.794')
12. $\LARGE a_i = a_d 10 ^ {d_q}$

>>> amount_integer = int(amount_decimal * 10 ** decimals_quote)>>> amount_integer40794000
13. $\LARGE a_i = s_i p_i t_i$

>>> amount_integer = size_integer * price_integer * tick_size_integer>>> amount_integer40794000
14. $\LARGE a_d = a_i 10 ^ {-d_q}$

>>> amount_decimal = dec(amount_integer) / 10 ** decimals_quote>>> amount_decimalDecimal('40.794')

Hence:

VariableDecimal amountInteger amount
Lot size0.1 APT10000000
Tick size0.01 USDC1000
Minimum order size0.5 APT50000000
Size7.8 APT78
Price5.23 USDC523
Total quote amount to fill40.794 USDC40794000

Note that Econia can only support precision down to a single indivisible subunit for either base or quote. This means, for example, that a market may not have a decimal lot size of $10^{-9} = 0.000000001$ APT, as each increment in size would correspond to a number of base asset subunits that could not be represented as an integer (0.1 indivisible subunits of APT):

>>> lot_size_decimal = dec('0.000000001')>>> (lot_size_decimal * 10 ** decimals_base).normalize()Decimal('0.1')

Similarly, if a market has a decimal lot size of 0.0001 APT, than it can only support a decimal tick size down to 0.01 USDC per APT, because the increment in total quote amount for each additional lot or tick corresponds to a single USDC subunit:

>>> lot_size_decimal = dec('0.0001')>>> tick_size_decimal = dec('0.01')>>> quote_increment_decimal = lot_size_decimal * tick_size_decimal>>> to_check = (quote_increment_decimal * 10 ** decimals_quote).normalize()>>> to_checkDecimal('1')

Notably, this check amount is equivalent to the integer tick size:

>>> tick_size_integer = int(lot_size_decimal * tick_size_decimal...                         * 10 ** decimals_quote)>>> tick_size_integer1

A decimal tick size of 0.001 USDC per APT would not be supported, however, because at the lowest possible price of 1 tick, the increment in total quote amount for each additional lot could not be represented as an integer multiple of subunits:

>>> tick_size_decimal = dec('0.001')>>> quote_increment_decimal = lot_size_decimal * tick_size_decimal>>> (quote_increment_decimal * 10 ** decimals_quote).normalize()Decimal('0.1')

Hence to check that a lot size/tick size combination is even possible for a market:

1. Pick a decimal lot size.

>>> lot_size_decimal = dec('0.1')
2. Assert that integer lot size corresponds to an integer multiple of base subunits.

>>> to_check = lot_size_decimal * 10 ** decimals_base>>> lot_size_integer = int(to_check)>>> assert to_check >= 1 and to_check == lot_size_integer
3. Pick a decimal tick size.

>>> tick_size_decimal = dec('0.01')
4. Assert that the integer tick size corresponds to an integer multiple of quote subunits.

>>> to_check = (lot_size_decimal * tick_size_decimal...             * 10 ** decimals_quote).normalize()>>> tick_size_integer = int(to_check)>>> assert to_check >= 1 and to_check == tick_size_integer

Noteworthy examples​

Consider the trading pair wBTC/USDC: as of the time of this writing, one BTC costs approximately 17792.27 USD, so initial choices for lot size and tick size might entail:

1. 0.00001 wBTC decimal lot size (corresponding to 0.1779227 USDC nominal).
2. 0.01 USDC decimal tick size.

Notably, these choices yield a total quote amount increment that does not correspond to an integer multiple of USDC subunits:

>>> lot_size_decimal = dec('0.00001')>>> tick_size_decimal = dec('0.01')>>> to_check = (lot_size_decimal * tick_size_decimal...             * 10 ** decimals_quote).normalize()>>> tick_size_integer = int(to_check)>>> to_checkDecimal('0.1')>>> assert to_check >= 1 and to_check == tick_size_integerTraceback (most recent call last):  File "<stdin>", line 1, in <module>AssertionError

Thus a different combination must be chosen, for example, by increasing decimal lot size by a factor of 10:

1. 0.0001 wBTC decimal lot size (corresponding to 1.779227 USDC nominal).
2. 0.01 USDC decimal tick size.

Here, the resultant quote amount increment corresponds to 1 USDC subunit, for a tick size of 1:

>>> lot_size_decimal = dec('0.0001')>>> to_check = (lot_size_decimal * tick_size_decimal...             * 10 ** decimals_quote).normalize()>>> tick_size_integer = int(to_check)>>> assert to_check >= 1 and to_check == tick_size_integer>>> tick_size_integer1

However, the new decimal order size granularity corresponds to 1.779227 USDC nominal, which may not be considered granular enough. Hence alternative parametric inputs might entail:

1. 0.00005 wBTC decimal order size granularity (corresponding to 0.8896135 USDC nominal).
2. 0.02 USDC decimal price granularity.

Here, the total quote amount increment again corresponds to an integer multiple of USDC subunits, for a tick size of 1:

>>> lot_size_decimal = dec('0.00005')>>> tick_size_decimal = dec('0.02')>>> to_check = (lot_size_decimal * tick_size_decimal...             * 10 ** decimals_quote).normalize()>>> tick_size_integer = int(to_check)>>> assert to_check >= 1 and to_check == tick_size_integer>>> tick_size_integer1

Note, however, that compared with the other viable parameter set, this set trades off size precision for price precision: twice as much size granularity entails one half as much price granularity.

note

Size granularity restrictions only apply to limit orders. Market orders and swaps allow users to specify precise trade amounts down to a single integer subunit.

Hence the nominal price of 17792.27 USD per BTC must be truncated to either 17792.26 or 17792.28. For the latter case, this entails an integer price of 889614:

>>> price_decimal = dec('17792.28')>>> price_integer = int(price_decimal / tick_size_decimal)>>> price_integer889614

Next, consider a liquid staking derivative sAPT trading against APT, sAPT/APT, both having 8 decimals. Here, high price precision may be appropriate:

VariableValue
Decimal lot size0.01 sAPT
Decimal tick size0.000001 APT per sAPT
Base decimals8
Quote decimals8
Decimal price1.000012 APT per sAPT
>>> decimals_base = 8>>> decimals_quote = 8>>> lot_size_decimal = dec('0.01')>>> tick_size_decimal = dec('0.000001')>>> price_decimal = dec('1.000012')>>> lot_size_integer = int(lot_size_decimal * 10 ** decimals_base)>>> lot_size_integer1000000>>> tick_size_integer = int(lot_size_decimal * tick_size_decimal...                         * 10 ** decimals_quote)>>> tick_size_integer1>>> price_integer = int(price_decimal / tick_size_decimal)>>> price_integer1000012

Next, consider wBTC trading against a hypothetical stable coin USDX with 10 decimals: wBTC/USDX. Here, a market registrant may again opt for high price precision, but if they specify too much, they may not be able to encode the corresponding integer price in 32 bits:

tip

Prices in Econia are represented as 32-bit integers, such that the maximum possible integer price is $2^{32} = 4294967296$ ticks per lot.

VariableValue
Decimal lot size0.0001 wBTC
Quote asset decimals10
Decimal tick size0.000001 USDX per wBTC
Decimal price17792.280012 USDX per wBTC
>>> lot_size_decimal = dec('0.0001')>>> decimals_quote = 10>>> tick_size_decimal = dec('0.000001')>>> price_decimal = dec('17792.280012')>>> tick_size_integer = int(lot_size_decimal * tick_size_decimal...                         * 10 ** decimals_quote)>>> tick_size_integer1>>> price_integer = int(price_decimal / tick_size_decimal)>>> price_integer17792280012>>> price_integer <= 2 ** 32False

Hence decimal tick size must be reduced so that integer prices can fit into a 32-bit integer.

Picking the right parameters​

As shown above, picking the "correct" lot size, tick size, and minimum order size for a given market is ultimately a judgement call. Still, however, there are several guidelines that can aid the process:

1. Only specify as much granularity as needed: overly-granular lot size and tick size combinations do not properly translate to integer tick sizes, and may make indexing more difficult. Three orders at price 12.34 is easier to interpret than one order each at 12.3401, 12.3404, and 12.3407.

2. Specify a reasonable minimum order size that will help keep gas costs low: when matching against the book, an AVL queue removal is required for each fill, which means that taker orders will require more global storage operations if they have to fill against more maker orders. For example, if the minimum order size for a market corresponds to $0.1 USD nominal, and someone submits a market buy order for$100 of the base asset, then they may have to pay the gas costs for up to $100 / 0.1 = 1000$ AVL queue operations. In contrast, for a more reasonable minimum order size of \$ 10 USD nominal, at most they will have to pay for 10 AVL queue operations.

3. Plan for price increases: as shown above, prices must be able to fit into 32-bit integers. If a market's parameters have been calibrated such that a 3x price increase will lead to a 32-bit integer overflow, then a different lot size/tick size combination should be chosen. Notably, if prices go up on the order of 100x, for instance, then a new market will likely be necessary anyways, due to changes in the appropriate level of granularity for a lot size/tick size combination. Hence initial market parameters should be chosen to support the maximum price swing possible before the registration of a new market becomes necessary due to granularity considerations alone.

Econia operates within the bounds of the Aptos virtual machine, a resource-scarce computing environment that imposes a unique set of operational constraints. In particular, Aptos' gas schedule charges for each "per-item" storage operation, which means that the cost of a transaction increases each time a key-able resource or a table entry is accessed.

Since Econia's AVL queue is based on table entries, this means that Econia could become prohibitively expensive if it did not place an upper bound on the number of possible price levels. For instance, if Econia were to allow an unbounded number of price levels and 256-bit prices, then an attacker could place orders at integer prices of $1, 2, 3, 4, \ldots$ and so on, potentially leading to a tree of height $h \approx 1.44 * 256 \approx 368$, such that insertion/removal operations would have to access as many as 368 table entries. This would lead to prohibitively high gas costs, such that a malicious actor could effectively denial-of-service (DoS) an order book by placing orders across all possible integer prices below/above the spread (depending on the side).

In the interest of preventing such an attack, Econia's AVL queue implementation thus sets an upper bound on the number of price levels, as well as the number of total orders, allowed on a given side of the order book. Yet simply imposing an upper bound is not enough: with only an upper bound on the size of the order book, an attacker could simply place the maximum number of orders possible to completely occupy the entire order book, far enough away from the spread so that no one would ever accept the best price. Here the order book would be practically locked until the attacker decided to cancel an order.

Hence Econia additionally imposes eviction logic, whereby the order with lowest price-time priority is evicted if the order book fills up. Here, orders far away from the spread are subject to cancellation if a better price comes around, such that an attacker attempting to fill up the order book will either have their orders matched against or will get evicted. If an attacker were to attempt placing and cancelling during the same transaction to circumvent these implications, they would still have to pay for:

1. N_NODES_MAX insertions to the AVL queue to place their malicious orders,
2. N_NODES_MAX removals from the AVL queue for the evictee cancellations, and
3. N_NODES_MAX removals from the AVL queue to cancel their own malicious orders.

Notably, each of these operations entails assorted function calls, global state mutation, etc., such that the requisite transaction would fail due to too high of a gas cost. In theory an attacker could split up the operation across multiple transactions, but then of course they risk having their orders filled at a price worse than the best market price (since they would have to place an order closer to the spread than that of the best order, in order to evict the order with the highest price-time priority).

In the rare case that an attacker is also a block-producing node, then the multi-transaction requirement does not necessarily apply, but here there is a larger issue at play that affects more than just Econia: block-producing nodes have the power to sequence transactions in ways that benefit themselves, even to the detriment of others. A solution to this broader issue (miner extractable value, or MEV) lies outside the scope of the present discussion.

Note that the economic outcomes of any adversarial behaviors discussed above do not constitute a failure per se of the Econia protocol, but rather, present a set of critical implications for anyone who makes assumptions about Econia's operations: if a substantial portion of an order book were to be evicted, then it would not be the case that Econia had been "hacked", as Econia would continue to accept new orders from trading bots, retail users, etc., and the order book could freely fill back up. But if someone were to build a protocol on top of Econia that assumed there would always be orders within a certain price range, for example, then the violation of this assumption could lead to economic losses higher up in the protocol dependency stack.

Hence the above analysis is provided in the interest of educating protocol developers about potential adversarial dynamics, such that they may avoid making erroneous assumptions with unintended consequences.

More on data structures​

An Econia OrderBook tracks each order as market::Order, which is complemented by a user::Order under the corresponding user's MarketAccount: when a user places a bid, for example, the global OrderBook for the market is updated along with the user's corresponding MarketAccount.

While market::Order instances are stored in an AVL queue inside an OrderBook for the corresponding side, user::Order instances are stored in a different custom data structure, the Tablist. A Tablist is a hybrid between a doubly linked list and a table, such that iteration is possible both during runtime and off-chain. Here, a user's asks and bids are each stored in a Tablist, having key-value pairs where the value is a user::Order. The key in the pair is known as an "access key", which essentially functions as a pointer into Tablist memory:

Rather than allocate a new node for each order and de-allocate it when the order fills, unused nodes are pushed onto a stack of inactive nodes, then popped off when a new order needs to be tabulated. Each node is referred to by its index in the underlying table, and this index is the access key used for $O(1)$ node lookup.

Each market::Order stores the access key for the corresponding user::Order, and similarly, each user::Order stores a "market order ID" used for lookup within the AVL queue. As explained in the market module documentation, a market order ID encodes the price of the order as well as a counter for the number of orders that have been placed on the corresponding order book.

Notably, each market order ID also contains an AVL queue-specific access key, which essentially functions as a pointer into AVL queue memory for a similar inactive node stack paradigm. Whether in a MarketAccount or an OrderBook, the inactive node stack approach decreases gas costs by minimizing the number of table item creations.