Orders
For each market, Econia tracks bids and asks in two places:
- A global
OrderBook
resource for the market. - 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:
- Increasing price, then
- 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:
- Decreasing price, then
- 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:
|
|
Here, a large taker buy will fill against asks in the following sequence:
- Price 1000, size 50
- Price 1000, size 60
- Price 1000, size 55
- Price 1001, size 35
- ...
Similarly, a large taker sell will fill against bids in the following sequence:
- Price 995, size 11
- Price 995, size 2
- Price 994, size 18
- Price 993, size 14
- ...
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 , where is the number of tree nodes.
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:
- The tree exceeds a specified critical height, or
- 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:
Again, see AVL queue height spec for supporting calculations.
Tree height | Min price levels | Max price levels |
---|---|---|
0 | 1 | 1 |
1 | 2 | 3 |
2 | 4 | 7 |
... | ... | ... |
10 | 232 | 2047 |
11 | 376 | 4095 |
... | ... | ... |
18 | 10945 | 524287 |
19 | 17710 | 1048575 |
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.
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
:
Term | Specifies | Symbol |
---|---|---|
Base asset | Order size | APT |
Quote asset | Order price | USDC |
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:
Parameter | Meaning | Example |
---|---|---|
Lot size | Order size granularity | 0.1 APT |
Tick size | Price granularity | 0.01 USDC |
Minimum order size | Smallest allowed order size | 0.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:
Size | Price | Reason |
---|---|---|
7.85 | 5.23 | Size too granular |
7.8 | 5.235 | Price too granular |
0.4 | 5.23 | Size 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
:
Term | Symbol | Coin | Amount |
---|---|---|---|
Base decimals | APT | 8 | |
Quote decimals | USDC | 6 |
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)
>>> subunits
12345600000
Similarly, other terms can be converted as follows:
Variable | Decimal symbol | Integer symbol |
---|---|---|
Lot size | ||
Tick size | ||
Minimum order size | ||
Size | ||
Price | ||
Total quote amount to fill |
>>> decimals_base = 8
>>> lot_size_decimal = dec('0.1')
>>> lot_size_integer = int(lot_size_decimal * 10 ** decimals_base)
>>> lot_size_integer
10000000>>> lot_size_decimal = dec(lot_size_integer) / 10 ** decimals_base
>>> lot_size_decimal
Decimal('0.1')>>> decimals_quote = 6
>>> tick_size_decimal = dec('0.01')
>>> tick_size_integer = int(lot_size_decimal * tick_size_decimal
... * 10 ** decimals_quote)
>>> tick_size_integer
1000>>> tick_size_decimal = (dec(tick_size_integer) / dec(lot_size_integer)
... * 10 ** (decimals_base - decimals_quote)).normalize()
>>> tick_size_decimal
Decimal('0.01')>>> min_size_decimal = dec('0.5')
>>> min_size_integer = int(min_size_decimal * 10 ** decimals_base)
>>> min_size_integer
50000000>>> min_size_decimal = dec(min_size_integer) / 10 ** decimals_base
>>> min_size_decimal
Decimal('0.5')>>> size_decimal = dec('7.8')
>>> size_integer = int(size_decimal / lot_size_decimal)
>>> size_integer
78>>> size_decimal = dec(size_integer) * lot_size_integer / 10 ** decimals_base
>>> size_decimal
Decimal('7.8')>>> price_decimal = dec('5.23')
>>> price_integer = int(price_decimal / tick_size_decimal)
>>> price_integer
523>>> price_decimal = (dec(price_integer) * dec(tick_size_integer)
... / dec(lot_size_integer)
... * 10 ** (decimals_base - decimals_quote)).normalize()
>>> price_decimal
Decimal('5.23')>>> amount_decimal = size_decimal * price_decimal
>>> amount_decimal
Decimal('40.794')>>> amount_integer = int(amount_decimal * 10 ** decimals_quote)
>>> amount_integer
40794000>>> amount_integer = size_integer * price_integer * tick_size_integer
>>> amount_integer
40794000>>> amount_decimal = dec(amount_integer) / 10 ** decimals_quote
>>> amount_decimal
Decimal('40.794')
Hence:
Variable | Decimal amount | Integer amount |
---|---|---|
Lot size | 0.1 APT | 10000000 |
Tick size | 0.01 USDC | 1000 |
Minimum order size | 0.5 APT | 50000000 |
Size | 7.8 APT | 78 |
Price | 5.23 USDC | 523 |
Total quote amount to fill | 40.794 USDC | 40794000 |
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 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_check
Decimal('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_integer
1
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:
Pick a decimal lot size.
>>> lot_size_decimal = dec('0.1')
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_integerPick a decimal tick size.
>>> tick_size_decimal = dec('0.01')
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:
- 0.00001
wBTC
decimal lot size (corresponding to 0.1779227USDC
nominal). - 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_check
Decimal('0.1')
>>> assert to_check >= 1 and to_check == tick_size_integer
Traceback (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:
- 0.0001
wBTC
decimal lot size (corresponding to 1.779227USDC
nominal). - 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_integer
1
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:
- 0.00005
wBTC
decimal order size granularity (corresponding to 0.8896135USDC
nominal). - 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_integer
1
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.
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_integer
889614
Next, consider a liquid staking derivative sAPT
trading against APT
, sAPT/APT
, both having 8 decimals.
Here, high price precision may be appropriate:
Variable | Value |
---|---|
Decimal lot size | 0.01 sAPT |
Decimal tick size | 0.000001 APT per sAPT |
Base decimals | 8 |
Quote decimals | 8 |
Decimal price | 1.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_integer
1000000
>>> tick_size_integer = int(lot_size_decimal * tick_size_decimal
... * 10 ** decimals_quote)
>>> tick_size_integer
1
>>> price_integer = int(price_decimal / tick_size_decimal)
>>> price_integer
1000012
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:
Prices in Econia are represented as 32-bit integers, such that the maximum possible integer price is ticks per lot.
Variable | Value |
---|---|
Decimal lot size | 0.0001 wBTC |
Quote asset decimals | 10 |
Decimal tick size | 0.000001 USDX per wBTC |
Decimal price | 17792.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_integer
1
>>> price_integer = int(price_decimal / tick_size_decimal)
>>> price_integer
17792280012
>>> price_integer <= 2 ** 32
False
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:
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.
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 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.
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.
Adversarial considerations
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 and so on, potentially leading to a tree of height , 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:
N_NODES_MAX
insertions to the AVL queue to place their malicious orders,N_NODES_MAX
removals from the AVL queue for the evictee cancellations, andN_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 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.