The Cost of Decentralization in 0x and EtherDelta

This Tuesday, a decentralized exchange platform called 0x will be holding a $24 million token sale. In the midst of an ICO frenzy that has funneled $1.3 billion into fledgling projects, the 0x sale seems like a drop in the bucket. 0x, though, is at the forefront of a wave of decentralized exchange projects that also includes EtherDelta, BitShares, KyberNetwork, and Omega One.

So what are decentralized exchanges, and why does the world need them?

A centralized cryptocurrency exchange is administered by an entity that represents a single point of failure. Users deposit their funds directly with the exchange, and the exchange assumes responsibility for matching buy and sell orders, which it can do in real time. Many exchanges support the purchase and sale of cryptocurrencies, fiat currencies, and cryptocurrency tokens. Examples of centralized exchanges include Coinbase, Kraken, and ShapeShift—as well as MtGox and Bitfinex. These last two were famously compromised, resulting in the loss of roughly 650,000 BTC and 120,000 BTC respectively, hundreds of millions of dollars at the time. (ShapeShift too was hacked, but a mere $200k or so worth of funds were stolen.)

Therein lies the rub. Centralized exchanges have the serious drawback that they require users to trust the exchange with their money. A fraudulent or compromised exchange can result in theft of users’ funds. There are also other drawbacks to centralized exchanges, such as the vulnerability of the users to frontrunning by the exchange administrator, as we discuss below.

Decentralized exchanges were created specifically to address centralized exchanges’ vulnerability to theft of user funds. In a decentralized exchange, users retain a degree of control of their own funds. They do not send money directly to a wallet that is controlled by a single entity. Instead, trading orders, and thus the release of user funds, are authorized directly by users via digital signatures. In principle, therefore, user funds cannot be stolen.

“In principle” is the operative phrase here. As we show, the ability to sign off on transactions does not equate with real control. Enabling users to control their own funds seems a good thing, but it has the side effect of abandoning the real-time nature of centralized exchanges in favor of slow, on-chain trading, That in turn exposes users of decentralized exchanges to new risks of monetary loss. Consistent with 0x’s apparent design philosophy of community empowerment, there is further dimension of decentralization in 0x’s governance scheme, which permits token holders to upgrade 0x contracts. This feature unfortunately creates a systemic risk such that users’ funds could again be potentially exposed to theft, resulting in some degree of the worst of both worlds.

Any complex new system is likely to suffer from design flaws. Decentralized exchanges have some definite advantages over their centralized counterparts, but also some distinct drawbacks. The design landscape is complex and it is essential to evaluate the merits of individual systems and the risks they pose to users of being cheated or exploited. Some of the flaws of 0x are inherent to decentralized exchanges, while others aren’t, as we now explain.

0x closely resembles EtherDelta, an existing exchange. We therefore compare 0x with EtherDelta to better understand the design choices and likely risks in 0x exchanges.

In this blog post, we present a brief overview of the general design behind today’s decentralized exchanges. Then we discuss three categories of decentralized-exchange design flaws:

  1. General flaws affecting all decentralized exchanges, at least within the design space currently explored by the community.
  2. 0x-specific flaws introduced by particulars of the 0x architecture.
  3. EtherDelta-specific flaws that are minor and don’t affect 0x, but teach us something about the challenges of correctly implementing exchanges.

Finally, we describe experiments we have performed in EtherDelta. These experiments highlights that the risks we describe are real and already emerging in a decentralized exchange with fairly low volume. We conclude with a brief discussion of the decentralized-exchange design space as a whole.

Decentralized exchanges: Brief overview

To support real-time trades, decentralized exchanges such as EtherDelta and 0x adopt essentially the same architecture for public (“broadcast”) orders. Users send their orders to off-chain matching services (called “Relayers” in 0x), which post them in off-chain order books. Such posting takes place in real time—much faster than if orders were posted on a decentralized blockchain.

Any user (called a “Maker” in 0x) can publish any buy or sell request (that this user signs) on the order book of the off-chain service. An order is accompanied by an exact price, i.e., limit orders aren’t supported.

EtherDelta and 0x both attempt to minimize trust in the off-chain matching service by not giving it the power to perform automatic matching of the buy and sell orders. Instead, any other user (called a “Taker” in 0x) trades against a posted order by adding a counterorder and digitally signing and sending the complete transaction, i.e., pair of orders, directly to the blockchain. The transaction is sent to a smart contract that executes the transaction, transferring assets between the buyer and seller (Maker and Taker in 0x). The lifecycle of a transaction is shown below in Figure 1.

EtherDelta and 0x both adopt this general design, but differ in two key ways. 0x allows anyone to stand up an exchange (“Relayer” in 0x), while EtherDelta has a unique one. Additionally, 0x, unlike EtherDelta, has a system of tokens used to pay transaction fees and for system governance.

Lifecycle of a transaction, using 0x terminology.

Lifecycle of a transaction, using 0x terminology. (1) The Maker sends a digitally signed broadcast order (e.g., “Sell 100 TOK for 1 ETH”) to the Relayer, who (2) Posts the order to the Order book. The Taker finds the order in the order book and digitally signs it, with a counterorder (“Buy 100 TOK for 1 ETH”) to the DEX (“Decentralized EXchange”) smart contract.

General flaws in decentralized exchanges

The general design just described introduces several basic vulnerabilities:

Exposure to arbitrage: The lack of automatic matching permits in-market arbitrage, whereby stale orders are filled to the disadvantage of users unable to quickly cancel their orders in response to market fluctuations. For example, the arbitrageur can execute against a standing pair of orders (sell 1 TOK at 1 ETH and buy 1 TOK at 2 ETH) to make an immediate profit of 1 ETH. Since the only way for users to invalidate their signed orders (that they published on the off-chain service) is by sending an on-chain cancellation transaction that is explicitly processed by the exchange contract, the arbitrageur may pay a high gas fee to miners and win the race against the cancellation transaction. Therefore, users who wish to increase the probability of a successful cancellation may need to attach an excessively high fee that depends on the value of the trade, which makes the exchange platform unattractive to honest users. We show below that this problem isn’t theoretical, but already arises in practice.

Vulnerability to miner frontrunning: Order cancellations are a common feature of decentralized exchanges (after all, an exchange with no cancellation ability may not be useful in a volatile market), and their on-chain nature renders these cancellations particularly vulnerable to miner frontrunning; the miner of the next block will always have the option to execute cancelled orders with themselves as the counterparty, potentially profiting from such an order. To add injury to insult, the miner even collects gas costs from a user’s failed cancellation. This issue was noted in the Consensys 0x report, and is recognized as a limitation of on-chain cancellations in the community.

Exposure to exchange abuses: Since the off-chain matching service doesn’t perform automatic matching, it is supposed to publish all users’ orders as quickly as possible, resulting in principle in fully transparent behavior. In actual fact, though, the exchange can suppress orders, mounting a denial-of-service attack against users in order to corner a market or censor particular users’ transactions. Worse yet, it can front-run orders. Specifically, it can engage in the same kind of in-market “sandwich” arbitrage described above, especially when high-value trades are requested. The problem is that signed orders flow to the off-chain server first. The server can thus match the trade data with pseudonymous users that it controls. Both suppression and front-running by an exchange are extremely hard to detect.

0x-specific flaws

Decentralized governance: In just two days, 0x will launch the Initial Coin Offering (ICO) of their ZRX token. The token will serve two functions: First, it will allow market participants to pay a Relayer’s fees for listing orders. Second, the token will be used for "decentralized governance" over the evolution of the protocol and the DEX contract holding market participants' assets.

Why a dedicated token should be used for Relayer fees is unclear—after all one could simply pay Relayers in ETH instead. The use of a token for decentralized governance is a more interesting use case.

Unfortunately, the 0x whitepaper does not provide any detailed information on how this governance process will work. Neither does the code in 0x's github repository. Since the governance process appears to be the only good reason for creating the ZRX token, this is all the more disappointing.

The 0x whitepaper does, however, state that non-disruptive protocol updates (i.e. changing the protocol and underlying smart contracts without requiring opt-in of individual users) are an explicit design goal of the governance scheme. This immediately raises questions about the security properties of the governance process. If, for instance, 0x were to use a simple majority voting scheme to approve updates to the DEX (which holds all user assets), an attacker could perform a 51% attack where she buys more than half of all ZRX tokens and then votes to replace the DEX with a malicious contract sending all assets to the herself. Designing a secure, decentralized governance process will be difficult and involve a multitude of delicate tradeoffs. Once again, decentralization is no panacea and carries a price in terms of complexity and possibly weakened security!

Side deals: 0x's design allows for two kinds of orders, broadcast orders and point-to-point orders. Broadcast orders make use of a Relayer, who broadcasts the Maker's order to any listening Takers who can choose to fill the order by sending a signed message to the DEX. (Figure 1 shows the lifecycle of a broadcast order.) Relayers can charge fees as a reward for their broadcasting services: When an order is filled, the DEX will transfer any fees from the Taker and Maker's accounts to the Relayer's account.

In contrast, point-to-point orders do not make use of Relayers and thus avoid Relayer fees. As their name suggests, point-to-point orders allow two market participants to trade directly with each other by sending signed messages to the DEX.

This leads to a scheme that allows Makers and Takers to evade Relayer fees:

  1. The Maker M posts an order O on a Relayer service.
  2. A Taker T listening to the Relayer learns of the order and decides she wants to fill it. She contacts the Taker off-chain [1] with a point-to-point order O' corresponding to O: If O offers to sell 1 TOK for 1 ETH, O' will offer M to buy 1 TOK for 1 ETH from T.
  3. Once M receives the order, she sends a single Ethereum transaction to the blockchain. This transaction calls the DEX twice, first cancelling O and then immediately filling O'. Note that thanks to the atomicity of Ethereum transactions, M carries no risk of both O and O' being filled.

Since cancellations are free and O is never filled, the Relayer will not earn any fees. Systematic exploitation of this flaw could lead to a tragedy of the commons, where individual market participants would make it uneconomical to run a Relayer by always evading fees, thereby destroying the "common good" of Relayers.

Side deals are less of a problem in EtherDelta because EtherDelta doesn’t support point-to-point orders and the fees for broadcast orders are hardcoded in the smart contract. However, 0x’s approach is not without advantages: Having a single DEX hold the assets for all point-to-point and broadcast orders and allowing multiple Relayers will likely lead to a more liquid market; furthermore, competition among Relayers may lower the fees that user pay. This tradeoff cannot be easily overcome: EtherDelta could in principle support multiple Relayers by using a separate contract for each of them, but this approach would not allow the liquidity in the order books of the Relayers to be shared.

Maker griefing: Maker griefing is an attack recognized in audits of 0x whereby an order maker moves tokens that are supposed to be involved in an order, causing it to fail in the final on-chain processing stages responsible for moving the funds. If such a failure occurs, the on-chain taker must pay gas fees to attempt execution of an order that never completes or provides any benefit to the taker, an inefficient use of taker time and money.

Repeating this attack on a large scale could potentially waste Taker gas, making Takers incur high order fees, costs, and delays in addition to the transparent Taker fees charged by the exchange. A cartel could place both legitimate and illegitimate orders, sharing information with each other out of band about which orders were legitimate. This would force outsiders to incur penalties, a potentially profitable strategy for a sufficiently powerful cartel. The recommended tooling mitigations do not entirely solve the issue, as they rely on checks of blockchain state, which could potentially change immediately before or even during the release of a new block. The potential for miner involvement as Makers in permissionless distributed markets or miner collusion with these cartels further amplifies these attacks, as miners could both collect the profit from Takers burning gas in griefing attacks and trigger the attacks in previously unseen transactions inserted in blocks before order fulfillment. Such a miner attack would allow no possibility of detection for the recommended tool-based mitigations.

The technological and economic barriers to these attacks or the formation of potential cartels mean these strategies may not surface until decentralized exchanges achieve substantial volume (and thus allow for substantial profit), dangerously providing a false sense of security and a false confidence in on-chain market architectures.

Similarity to EtherDelta: As described in the design of both exchanges, EtherDelta and 0x share a number of similarities. As EtherDelta is a full system that is currently operational and includes a number of in-production smart contracts, it is unclear where a potentially large ICO raise could be allocated beyond the development of equivalent technologies and distributed governance. The 0x roadmap provides some hints of potential strategies for differentiation, and we hope to see the development of advance and novel R&D improvements accompany the deployment of proposed EtherDelta-like infrastructure.

EtherDelta-specific flaws

Slow cancellation: Despite its processing of cancellations with low observed latency after a cancellation order is mined on-chain, the requirement of waiting until the next mined block (or later with potentially full blocks) imposes a significant barrier to real-time exchange, potentially locking up user funds and enabling profitable miner arbitrage on larger orders through frontrunning.

Slow order processing: During the posting of our test orders on EtherDelta in the experiments we conduct below, we observed a substantial delay required to place orders in the systems. This operation is not contingent on any on-chain transaction processing, and it is not clear to us why the system is imposing such a delay.

High gas costs for competing transactions: Due to the high latency of EtherDelta’s order book, some Takers may be blind to each others’ orders. This can cause a race condition where multiple Takers compete to fulfill a single order, leading to order failure with some delay and gas costs incurred by all but the winning Takers. This could potentially become problematic on attractive orders as the system increases in size, specifically with the possibility of miner participation and frontrunning.

Experiments with EtherDelta

We experimentally verified some of the flaws listed above. First, we evaluated the total theoretical arbitrage opportunity of 10 major ERC-20 Token/ETH exchanges (BQX, CDT, CVC, EOS, PAY, PLR, PPT, VERI, XRL exchange with ETH) on EtherDelta over a period of 24 hours (from 2017-8-11 00:30:00 UTC to 2017-8-12 00:30:00 UTC). Our experiments show that—assuming perfect execution, the current EtherDelta transaction fee of 0.3% of total volume, and a gas price of 20 Gwei—an arbitrageur could have gained 14.71785 ETH in the above period. At current exchange rates ($303.9 / ETH), this corresponds to $4,472.75 / day or $1.6+ million / year. Specifically, we observed 45 arbitrage opportunities during our period of study, with an average arbitrage opportunity of 0.32 ETH. Compared with centralized exchanges, EtherDelta has relatively small volume today. Were its volume to grow substantially without technical changes, arbitrage opportunities would presumably grow to be quite substantial.

Many of these arbitrage opportunities resulted from clear user error, i.e., obvious mispricing of orders. Even without such error, however, we identified approximately 6.7 ETH in arbitrage opportunities over the 24-hour period of study, corresponding to about $2,036.

Having confirmed that arbitrage opportunities exist in practice, we demonstrated experimentally that they are exploitable in practice. We designed a simple trading bot that would monitor EtherDelta's order books for arbitrage opportunities and send orders exploiting them to the blockchain. Our preliminary numbers suggest that out of 12 orders sent, 7 (or 58.3%) succeeded. The cause of failed arbitrage attempts was a failure to post our order fast enough, i.e., someone else hit the order or the maker cancelled the order before our order executed. (We did not seek to exploit all 45 observed arbitrage opportunities because this would have required roughly 80 ETH worth of tokens, which is more than we poor academic researchers possess.)

Assuming that the success rate we observed is representative, we can approximately estimate the expected net daily profit available to arbitrageurs according to the following formula:

Expected profit = (Net profit per transaction * Probability of success - Gas per transaction * (1 - Probability of success)) * Total number of opportunities

Our experiments during the period of study suggest the estimate:

Expected profit = 0.32 ETH * 58.3% * 45 - 0.004 ETH * (1 - 58.3%) * 45= 8.32 ETH

Or about ~$2500 per day. While this is not enormous, particularly if competition arises among arbitrageurs, an increase in popularity and therefore volume on decentralized exchanges would of course result in far larger potential profits.

The decentralized-exchange design space

There is a large design space for decentralized exchanges beyond the EtherDelta/0x variety. For example, an alternative is to allow the off-chain matching service to perform automatic matching, and even require each trade to include a signature by the off-chain service. To avoid loss of funds in the case that the off-chain service disappears, users would still be able to withdraw their assets without approval of the off-chain service, but only via a slow process. This design eliminates two of the major problems that we described above: The arbitrageur won’t be able to race against users who have already cancelled their orders, and miners won’t be able to front-run users. Unfortunately, the off-chain matching service will have the same kind of power to perform in-market arbitrage as centralized exchanges. Unlike centralized exchanges, though, it won’t have the power to steal users’ deposits.

Another reason to avoid automatic matching by the off-chain service, however, is that it reduces the complexity of the code of the exchange contract. Automatic matching support would naturally support functionality such as limit orders that don’t exist in EtherDelta / 0x. (Given the simplicity of the code base for which 0x are raising $24 million, code supporting automatic matching would presumably be worth several hundred million or so...)

Conclusion

Centralized exchanges have serious drawbacks, perhaps most notably exposure of users’ funds to theft. But the wave of creation of decentralized exchanges that place users’ funds in their control does not fully protect users’ funds, and introduces new problems. It is tempting to dismiss the problems we’ve observed in EtherDelta as trivial, but we believe they will grow as decentralized exchanges do. What we’re seeing today is just a harbinger of problems to come should decentralized exchanges sweep over the cryptocurrency landscape. But since the problems that we’ve identified are exacerbated when higher value trades take place, we conjecture that such problems will ultimately limit the popularity of decentralized exchanges.

This all is not to say that decentralized exchanges do not have a place or cannot fill a valuable market niche. We are also not claiming the superiority of centralized exchanges; notably, centralized exchanges can steal all user funds, the strongest form of unfairness. Nonetheless, it is important to remain aware of the tradeoffs made to achieve this decentralization and their potential negative effects on users of a certain exchange architecture. Someday, someone may devise a decentralized exchange architecture that doesn’t suffer from any of the limitations we’ve enumerated. This challenge remains an open problem.

As a final note, we observe that 0x and EtherDelta provide only a trading platform for tokens that circulate on a single blockchain. They don’t support trading BTC for LTC and so on. As our discussion illustrates, achieving even this modest goal with adequate performance and security is a herculean task for decentralized exchanges. Support for cross-chain trading requires far more complex architectures, see for example KyberNetwork and Omega One. Decentralized exchanges that enable cross-chain trading are likely to exhibit all the problems discussed in this blog post, and more.

[1]We are deliberately vague about the mechanism of off-chain communication since it isn't relevant to the scheme. A simple example would be the use of email using a simple directory-like smart contract to associate Ethereum addresses with their owner’s email addresses.

Disclosure

In the interest of transparency, we would like to note that one of the authors of this blog post, Phil Daian, is an advisor to Swap, a P2P trading protocol that is an alternative to decentralized exchanges. Swap is not immune to many of the issues identified in this blog post, given that an Indexer, the Swap mechanism for counterparty discovery, could play a role much like that of a Relayer plus Order Book. (The Swap whitepaper provides insufficient information for detailed analysis.)

Share on Google+
Share on Linkedin
Share on Reddit
Share on Tumblr
comments powered by Disqus