Building SPEEDEX – A Novel Design for a Scalable Decentralized Exchange

The ideal DEX should: 1) charge the lowest fees necessary, 2) be fast and scalable, 3) be easy to use, 4) treat users fairly, 5) be equally accessible to all users around the globe with modest internet connections, and 6) provide markets as liquid as possible directly between every pair of assets.

Unfortunately, existing DEX designs do not come close to meeting these criteria, for the following reasons:

• The DEXes (and centralized exchanges) of the world today divide liquidity by asset pair. While the markets between USD and many other currencies can be relatively liquid, direct markets between non-reserve currencies may not be. Suppose, for example, that a user wishes to trade ARS to NGN. A DEX might support trading one directly for the other, but the user would likely get a better overall exchange rate by using a path payment — by trading ARS for USD, and then USD for NGN. This problem is especially pronounced on modern blockchains where many organizations have deployed distinct stablecoins that represent that same underlying asset.
• The optimal trade between any two assets in a network of trading pairs is almost always a combination of path payments, with each path payment leaving behind small arbitrage opportunities that encourage arbitrage spam on the network.
• Transactions on virtually every DEX are processed in a sequential order, determined pseudorandomly (e.g. on Stellar) or non-deterministically by the block producer (e.g. on Ethereum). Control of this ordering can be particularly valuable. If one trader offers to buy something at slightly above the current market price, an agent with influence over the transaction ordering can buy the asset in question at exactly the market price and immediately resell it to the trader at their maximum price, netting the difference as pure profit. This type of risk-free front-running and complicated ordering manipulations results in users seeing worse exchange rates, plus the network has to do more computational work to handle the same number of real cross-border payments.
• Sequential execution also means that the only way to boost transaction throughput is to wait for hardware manufacturers to design CPUs with faster single-core performance.

SPEEDEX is a novel design for a fully on-chain distributed exchange, and is the first such design that simultaneously:

• Gives every user the same level of access. SPEEDEX gives every user (approximately) the same level of access, since it does not take into account the ordering of transactions within a batch in any way. As such, a user's network connection latency does not affect the quality of the user's trading experience. So long as the user can get their trade to a block producer before a block cutoff time, the user will get the same exchange rate as a user with a low-latency connection to the producer.
• Gives every user a fair trade. SPEEDEX prevents many of the front-running attacks seen today on existing DEXes. Even a trader with such an advantageous network access that they can see every other transaction in a block before submitting their own cannot buy an asset and re-sell it at a higher price in the same block.
• Makes optimal use of its available liquidity. SPEEDEX makes the best possible use of its available liquidity. In particular, a market between any two assets is as least as liquid any multi-hop path between the two assets. As such, SPEEDEX obviates the need for multi-hop path payments.
• Avoids reliance on reserve currencies and transaction paths. Many lesser-used currencies are traded on highly liquid markets with global reserve currencies such as the US Dollar, but rarely traded directly with each other. By contrast, SPEEDEX automatically ensures the direct markets between these less traded currencies are as liquid as the (minimum of the) markets from these currencies to the dollar. A trade does not even need a direct counterparty to execute.
• Avoids leaving arbitrage opportunities behind. SPEEDEX leaves behind no arbitrage opportunities, in that there are no arbitrage opportunities among the orders that do not execute. Furthermore, no trades within a batch can constitute an arbitrage opportunity. A trade path along a cycle makes exactly zero profit or loss. Of course, SPEEDEX cannot eliminate arbitrage opportunities between itself and external exchanges.
• And can support not just the transaction rates we see today, but also transaction rates many orders of magnitude greater than we see today, so as to remain useful decades into the future. SPEEDEX is scalable because its operation is parallelizable. The outcome of any one trade has no dependence on the ordering between trades in a block. As such, SPEEDEX can parallelize all of its computational work (e.g. transferring assets) with virtually no inter-thread synchronization or overhead, effectively using as many CPU cores as are available on a blockchain node. The system as a whole can get a higher transaction throughput by simply installing more CPU cores.
  

SPEEDEX processes trades in batches. Every trade within one batch occurs at the same set of exchange rates as every other trade in that batch, and careful computation of the exchange rates leaves no arbitrage opportunities after executing a batch of trades. These exchange rates eliminate the need for multi-hop path payments — all paths give a user the exact same exchange rate, and every market between two assets is at least as liquid as the most liquid path.

Furthermore, because all trades occur at the same exchange rates, trades have no ordering dependencies with each other; that is, SPEEDEX can execute the trades in one batch in any ordering and get the same results, no matter the ordering. This property simultaneously blocks front-running and enables SPEEDEX to effectively parallelize its operation and use as many CPU cores as it has available. In other words, the more CPU cores there are on a machine running SPEEDEX, the more trades per second SPEEDEX can process

Batch trading fits particularly well in a blockchain context. All the transactions in one block are finalized at the same time, so why should one of those transactions execute before another in the same block?

SPEEDEX's approach to batch trading is to construct a virtual "auctioneer." Users exchange assets with the auctioneer and not directly with each other. For SPEEDEX, a trade offer will be an offer to sell one asset in exchange for as much of another asset as possible, so long as the price of the first asset relative to the second is at least some minimum price.

Given a batch of trades, the auctioneer computes a "valuation" for each asset. These valuations quantify the "value" of an asset relative to another asset. These relative valuations imply an exchange rate between every pair of assets, which the auctioneer offers to every trade request. Trade requests look at the offered exchange rates and compute whether the offered rate is greater than an offer's minimum limit price. The trade offers that accept the auctioneer's rate then sell their assets to the auctioneer and receive the proportional amount of another asset in return from the auctioneer.

There always exists a unique (up to rescaling, and a few technical conditions) set of valuations that "clears" the market (which follows from Theorem 1 of [Devanur, Garg, Végh], combined with some technical conditions). A set of valuations clears the market if:

1. Every offer with a limit price less than the auctioneer's offered exchange rate sells all of its assets to the auctioneer and receives the implied amount of another asset from the auctioneer.
2. The auctioneer has no profit or debt. That is to say, the total amount of each asset that trade offers choose to sell to the auctioneer is exactly equal to the amount of the asset that the offers buy from the auctioneer.
   

Because market clearing prices are unique and the auctioneer never makes a profit or loss, the auctioneer does not actually make a strategic choice when "choosing" the valuations. Instead, it merely reports a set of values that are an inherent property of a batch of trades.

The core algorithmic challenge for SPEEDEX is to compute market clearing valuations efficiently. SPEEDEX runs once per block – integrated with Stellar, that means roughly once every five seconds, and ideally in well under one second.

I plot here the transaction rate of my research implementation of SPEEDEX trading 20 distinct assets. The overall transaction numbers here should be taken with a large grain of salt. This is not battle-tested code, and is running in an isolated development environment with a simple closed-membership consensus protocol. I include the graph, though, to emphasize two points. First, letting SPEEDEX access more CPU cores (more worker threads) lets SPEEDEX run faster. Second, the price computation process, which must run in every block, does not significantly slow down as the number of open trade offers increases.

Almost all of the slowdown associated with an increase in the number of open offers is a preprocessing phase of the algorithm. My test machines unfortunately only had relatively slow hard disks, and could not always keep up with SPEEDEX.

SPEEDEX fits naturally into the Stellar blockchain, since it runs best in a replicated state machine that is explicitly built to support it. The scalability benefits rely on a design that can use multiple CPUs, and price computation algorithms are memory-intensive, running best when built directly into the replicated state machine. SPEEDEX also benefits from careful design of memory access patterns and careful CPU cache management.

These types of performance concerns would be nigh-impossible to handle inside of a smart contract. It would be impossibly gas-intensive to run the price computation algorithms within the Ethereum Virtual Machine, for example, or in nearly any smart contracting language. A smart contracting language could design a set of primitives that interact with a distinct SPEEDEX module, but that module would still likely need to be implemented directly within the Layer-1 state machine. The price computation or order matching could also be moved off-chain (as with LoopRing or CoWSwap), but then the DEX is no longer a truly decentralized, replicated piece of infrastructure.

SPEEDEX lets a Layer 1 blockchain scale directly, without moving most of the interesting computation off-chain – but that requires that the blockchain itself be willing to redesign itself to support parallelism and direct integration with SPEEDEX.

Finally, Stellar's precisely designed transaction semantics substantially simplify an integration with SPEEDEX.

SPEEDEX closely aligns with Stellar's mission of enabling a future of low-cost and fast cross-border payments. Any DEX powering a global system of payments must give every user worldwide equitable access. Further, to support not just today's transaction volumes but the transaction volumes of coming decades, blockchains like Stellar will need to scale far beyond their performance today. Nearly every other widely-deployed relevant computer system scales itself by running more copies of itself or parallelizing request handling. SPEEDEX can help the Stellar network horizontally scale in the same manner, and become a truly global payments infrastructure.

-----

Stellar has done incredible work already in building a decentralized network for cross-border and cross-currency transactions. But Stellar will need to scale its on-chain DEX performance as more and more users around the world transact through the blockchain. Integrated into Stellar, SPEEDEX builds on Stellar's work to create a DEX that can scale its transaction throughput to support the transaction volumes we will see decades from now. SPEEDEX also provides a host of economically useful properties, including equality of access, elimination of risk-free front-running and internal arbitrage, and direct liquidity between illiquid trading pairs.

To learn more about SPEEDEX, check out the following:

• A standalone, open-source SPEEDEX implementation, implemented on its own blockchain (using HotStuff as a consensus protocol) is available here. We (myself and my coauthors, Professors Ashish Goel and David Mazières) give a detailed technical description of how this implementation works in this preprint.
• A prototype of an integration of SPEEDEX within Stellar-Core is available here.
• For details on how the market-maker's computation works, see the Appendix blog post, or, for a more mathematical description and a discussion of some of the tradeoffs involved, see this workshop paper (by myself and Professors Goel and Mazières) or the preprint.