A high-quality decentralized exchange (DEX) is a crucial piece of infrastructure for a global payments network. Cross-border remittances rely on exchanging one country's currency for another, but businesses in one country cannot transact with customers in another country unless customers can exchange their currency for one that the business accepts. However, current exchange implementations, especially centralized exchanges, typically limit who can access the exchange and often charge high trading fees. Thus, decentralization of the exchange around the globe is crucial to ensure egalitarian, open access to the world’s financial system.
SPEEDEX – a Scalable, Parallelizable, and Economically Efficient Distributed EXchange – is a new design for a fully on-chain decentralized exchange that can scale to an arbitrarily high transaction throughput. Current on-chain decentralized exchanges are slow, expensive, and inefficient. SPEEDEX, by contrast, is none of these; it can scale its throughput by effectively using many CPU cores, and, at the same time, SPEEDEX eliminates risk-free front-running, gives every user the same, fair exchange rate, and boosts liquidity between illiquid trading pairs.
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:
SPEEDEX is a novel design for a fully on-chain distributed exchange, and is the first such design that simultaneously:
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:
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: