Order Matching: Achieving Seamless Trades

Decentralized exchanges (DEXs) have disrupted the cryptocurrency trading landscape by introducing trustless and transparent platforms for exchanging digital assets. A critical element of DEXs is the order-matching mechanism, which enables the execution of trades. This blog post delves into the intricacies of order-matching mechanisms, highlighting the advancements that have enhanced user efficiency, liquidity, and overall trading experience.

Understanding Order Matching

Order matching is the fundamental process of pairing buy and sell orders to enable asset exchange. In traditional centralized exchanges, order matching is typically facilitated by a centralized order book. However, DEXs operate in a decentralized manner, necessitating alternative mechanisms to address the challenges associated with the absence of a central authority.

Approaches to Order Matching in DEXs

In the early days of DEXs, simplistic order matching mechanisms, often referred to as "first-come, first-served" or "priority-based" matching, were prevalent. During this nascent stage, trades were executed based on the order of receipt, without considering factors such as price or quantity.

Order Books

Order books serve as records of trade orders submitted by users who want to exchange assets. Here's how the process typically works:

1. Users looking to exchange assets submit buy or sell requests, which are stored in the order book. By submitting an order, the user becomes a "maker."
2. The order book contains information about the tokens the user wishes to exchange and the desired terms of the trade.
3. To validate the order, makers sign it with their private key, providing authentication.
4. The order is then broadcasted through the exchange network, where takers, or other participants looking to trade, come forward.
5. If a taker is satisfied with a maker's order, they confirm the trade, and the smart contract handles the remaining steps of the process, such as asset transfers and settlement.

Liquidity Pools

To address the centralization challenge associated with order books, decentralized finance (DeFi) projects utilize liquidity pools. In this model, market makers are referred to as liquidity providers, and the pools facilitate trading. Here's an overview of how liquidity pools work:

1. A liquidity pool consists of two or more tokens. When a liquidity pool is created, a liquidity provider supplies equal-value amounts of each token to the pool and sets an initial price.
2. Any person adding tokens to the liquidity pool contributes an equal value of both tokens. As a result, liquidity providers earn LP (Liquidity Provider) tokens based on the amount of liquidity they provide to the pool.
3. When trades occur, a portion of the transaction fee is distributed among all LP token holders in the pool. This rewards liquidity providers for their participation.
4. With each trade, an automated market-making algorithm adjusts the price of the tokens in the pool, maintaining balance and reflecting market dynamics.

Liquidity pools and automated market making provide an alternative approach to trading, promoting decentralization and liquidity provision within the DeFi ecosystem.

This blog focuses on order books and the revolving aspect.

An order-matching system is imperative whether centralized or decentralized order books are employed. Where as in the case of AMMs we need liquidity for order to be fulfilled.

Order Matching Engine

An order-matching engine is a mechanism used in financial exchanges to match buy and sell orders submitted by market participants. It operates based on predefined rules and algorithms, considering price, time, and order priority factors. The primary objective of the order matching system is to facilitate the optimal execution of trades, ensuring fairness, efficiency, and price discovery within the marketplace.

The order-matching engine in a decentralized exchange constantly listens to the order book for new orders. When a new order is received, the engine attempts to find a matching order in the book. If no match is found, the order is added to the order book and remains there until a suitable match is found. The transaction is executed once a match is identified and both parties are notified.

Various methods can be employed within an order-matching engine. The most commonly used algorithm is the first in, first out (FIFO), which prioritizes fulfilling the older order first. Additionally, there are algorithms like Price-Time Priority and Pro-Rata Algorithms.

Price-Time Priority Algorithm

A price-time priority algorithm is a fundamental approach used in order-matching systems. It prioritizes the highest bid with the lowest ask to ensure the best available price for trade execution. The algorithm compares the prices of buy and sell orders, giving preference to orders with the most favorable prices. In case of orders with the same price, the algorithm prioritizes the order placed earliest.

Example

Using the price-time priority algorithm, the highest bid ($35,500) will be matched with the lowest ask ($35,000). This ensures that the best available price is achieved and the trade is executed based on the order priority.

Pro-Rata Algorithm

The pro-rata algorithm distributes the available quantity among compatible orders proportionally. When there are multiple orders at the same price, this algorithm divides the trade quantity based on the relative sizes of the orders. Each order receives a fraction of the trade based on its proportion to the total quantity. The pro-rata algorithm promotes fairness by providing an equal opportunity for traders to participate in trades at the same price level.

Example

Consider the following scenario.

The available quantity will be proportionally distributed among the compatible orders using the pro-rata algorithm. In this case, each order will receive a fraction of the trade based on its relative size.

To calculate the fractions, we need to determine the total quantity of all compatible ask orders, which is 2 + 3 + 1 = 6 Bitcoins. Using the pro-rata algorithm, User X will receive 2 Bitcoins, User Y will receive 3 Bitcoins, and User Z will receive 1 Bitcoin.

Each user's allocation is determined by the proportion of their order size relative to the total quantity available to be traded.

Enhancing Order Matching Engine With BlockApex

Team BlockApex is working on a DEX, that aims to combine the user-friendly experience of centralized exchanges with the security and transparency of decentralized platforms.

The order matching algorithm implemented by our experienced team enables partial and fractional order matching.

The order matching engine follows a price-time matching preference, where the price is the primary key and time as the secondary factor. The highest bid is always matched with the lowest ask. To facilitate this, the exchange maintains two priority queues, one for bids, also known as buy orders, and the other for asks or sell orders, for each trading pair.

Let's walk through the order-matching flow using an example

Suppose User X submits an ask order of 1 Bitcoin for $35,500. Since this price is lower than the highest bid (User A's $36,000), the system attempts to match User X's ask order with the available bids.

The system takes the top bid from the bid queue, which in this case is User A's bid of $36,000, and checks if User X's ask can be fulfilled. The order can be fully filled since User A's bid price is higher than User X's ask price. The system updates the order status, and User X's ask order is matched and filled by User A's bid. If the bid price were lower than the asking price, the system would continue checking the next bid in the queue until a match is found or no more bids are available.

After the successful match, the queue is updated accordingly. User A's bid is removed from the bid queue, and the next highest bid (User B's $34,500) becomes the new top bid in the queue.

If a new order enters the queue, it does so through smart insertion. Furthermore, it should be noted that order matching always takes O(1) time. The order-matching algorithm handles various scenarios, including both bid and ask orders being partial or complete and cases where either the bid or ask order is partial or complete.

Users have the flexibility to choose whether they want to allow partial orders or only complete orders. However, the system supports both direct order matching, i.e., where orders are matched at the exact price point, and fractional order matching, i.e., where orders are partially matched based on their proportional quantities.

The order-matching algorithm handles various cases such as

• Both the bid and ask orders can be partial.
• Both the bid and ask orders can be completed.
• The bid order can be partial while the ask order is complete.
• The ask order can be partial while the bid order is complete.

Priority Queue: Fueling Efficiency and Precision

In a Priority queue each element is assigned a priority value. Elements with higher priority are dequeued before elements with lower priority. In the context of order matching, priority queues are used to manage buy and sell orders based on their prices.

There are multiple reasons for using priority queue such as

• Time Complexity: Priority queues provide fast access and retrieval of the highest and lowest priority elements, typically achieved with a time complexity of O(1). This constant-time complexity allows for speedy order matching, even in scenarios with a large number of orders.
• Order Book Maintenance: This DS help maintain the order book in an organized and efficient manner. The buy and sell orders are sorted based on their priority, allowing the order matching engine to identify the best matches easily. As new orders arrive, they can be inserted smartly.
• Flexibility: Priority queues provide flexibility in handling partial order matching. They facilitate the management of partial matches and ensure that the remaining unmatched portion of the order is preserved for future matching opportunities.
• Scalability: Priority queues can handle a large number of orders efficiently, making them scalable for high-volume trading environments. Regardless of the number of orders in the queue, the order matching engine can quickly identify the best matches and execute trades. 

Partial Order Matching

When the users choose the option of partial order matching, the order gets fulfilled with multiple orders. Users have the freedom to accept the bids and leave, even if their ask orders are not fully filled, or they can wait until they obtain the requested amount.

An example of how it works is shown in the figure below

The order matching engine ensures efficient and equitable trade execution by matching the highest bids with the lowest asks while considering the time priority of orders. Partial order matching is supported, further augmenting efficiency and liquidity.

Order matching engines and algorithms play a vital role in decentralized exchanges, facilitating the seamless execution of trades and ensuring fair and efficient market operations. From the early priority-based matching to the more sophisticated algorithms like price-time priority, FIFO, and pro-rata, order matching has evolved to meet the diverse needs of traders. 

As decentralized exchanges continue to innovate and refine their order-matching mechanisms, users can expect improved liquidity, faster order execution, and a more seamless trading experience. With the combination of user-friendly interfaces and the inherent benefits of decentralization, DEXs are poised to revolutionize the financial landscape, empowering individuals to have full control over their digital assets and participate in a global, trustless marketplace.

TL;DR

Decentralized exchanges (DEXs) have transformed cryptocurrency trading by providing transparent and trustless platforms for exchanging digital assets. Order matching, a crucial component of DEXs, has evolved from simplistic priority-based matching to advanced algorithms like price-time priority, FIFO, and pro-rata. DEXs have introduced centralized and decentralized order book models to improve efficiency while maintaining decentralization.

Also read our blog about Liquidity Challenges In Illiquid Marketplaces.