StarkDEX Deep Dive : Introduction

Part 1 of 4

Last week we released the StarkDEX alpha on a public Ethereum testnet, demonstrating for the first time a live STARK-based Layer-2 system. In the coming weeks, we will release a series of blog posts that will dive into the StarkDEX technology and explain its various components and mechanisms.

In this post, the first of the series, we will give an overview of our system and discuss user flows and batching. The next posts in the series will cover our contract and statements, the STARK scalability engine and the design of the Algebraic Intermediate Representation (AIR) for DEXes.

Diving into StarkDEX Alpha

StarkDEX allows decentralized exchanges to scale by removing the limitation set by the cost of settling every transaction on-chain, as discussed in detail in our previous post.

The important saving comes from reducing on-chain computation and storage operations. To do this, we move the data off-chain. The main idea is to store the balances using a Merkle tree, where only the root of this Merkle tree is stored on-chain. Every operation in the exchange translates to a transformation of the Merkle tree leaves. We then prove to the StarkDEX contract that a large batch of exchange operations is valid (funds do not disappear nor are created out of thin air, each trade is digitally signed by both counter-parties, etc.) and that these operations are consistent with the change in the Merkle root.

Fig 1: the data flow — transactions become proofs

To keep track of user balances, we introduce the concept of a vault. A vault represents funds of a certain token that belong to a certain user. For example, one vault may contain 1 ETH belonging to User A, while a second vault may hold 3 DAI of the same user. Each vault is given a unique 31-bit identifier and consists of three fields: the user’s public key, the token type and the balance for that user.

All the vaults are organized in a Merkle tree. The root of this Merkle tree represents the full state of all balances in the system. Thus, it suffices to store just this root on-chain, instead of the full tree, and still be able to verify claims about any balance. Whenever any balances of off-chain vaults change, the only thing that should be recorded on-chain is the new Merkle root.

Main user flows

Figure 2: The money flow — how funds are moved around

In order to trade on StarkDEX, the user first needs to deposit their funds into the StarkDEX contract. This is done by a simple Ethereum transaction, originated by the user, that adds the user’s deposit to a data structure called the “on-chain deposit balance”. StarkDEX monitors this data structure and moves the deposited amount from it to the relevant off-chain vault, computing the new Merkle root accordingly.

Once the funds are recorded in the off-chain vault, the user can use them to trade. Different exchanges can use different matching mechanisms to facilitate trading, and this part is external to the StarkDEX system. Once a trade needs to be settled, the funds of the four relevant vaults (a single trade means two traders modify two assets each) are updated, and the new Merkle root is computed accordingly. To guarantee that this operation is done with the approval of the users, they need to sign the orders. Currently, StarkDEX operates in the maker-taker model — the maker creates a signed order, consisting of the token types to be traded, the amounts and their two vault IDs. To form a trade, the taker signs this order’s hash and their own two vault IDs (partial order fulfilment is not supported on the alpha version of StarkDEX, but will be added in the next version).

When the user wants to use the funds outside of StarkDEX, they ask the exchange to withdraw a certain amount of tokens. This translates to reducing the balance of the relevant off-chain vault (computing the new Merkle root accordingly) and increasing the “on-chain withdrawal balance”. Now the user can withdraw the funds directly from the StarkDEX contract.

Note that the total amount of tokens a user owns is the sum of their off-chain vault and their two on-chain balances (deposit and withdrawal).

Throughout these flows, the user always maintains custody of their funds — they can’t be moved to a different address without the user’s explicit signature. Under normal circumstances, the user needs the exchange in order to withdraw funds. This could be problematic if the exchange is compromised, as the user’s funds might be locked within the system (but note that even in this unfortunate scenario the funds cannot be stolen). To enable the user to withdraw their funds, even in this extreme case, we introduce the “escape hatch” mechanism (not supported on the alpha version of StarkDEX, but will be added in the next version). To activate this mechanism, the user invokes a “full withdrawal” on the StarkDEX contract. This forces the StarkDEX system to release the funds (to the on-chain withdrawal balance, from where the user is able to withdraw the funds) within a certain amount of time. If the system fails to do so, the contract freezes — any future settlement will be rejected, freezing the off-chain vault Merkle tree. From this moment on, the user can withdraw directly from the contract by proving the Merkle authentication path of their off-chain vault.

Batching

STARK proofs enable inexpensive on-chain verification of complex operations that were performed off-chain. To maximize the gain from this mechanism, the StarkDEX system batches a large number of transactions into one proof. As the cost of verifying a STARK proof is almost independent of the batch size, this offers compelling economies of scale: the higher the throughput, the lower the gas cost of a single transaction, allowing nearly unlimited throughput, despite Ethereum’s gas limit.

Each StarkDEX proof contains a large number of transactions of three different types:

1. Trade settlement.
2. Deposit — moving funds from the on-chain deposit balance to the off-chain vault.
3. Withdrawal — moving funds from the off-chain vault to the on-chain withdrawal balance.

The reason StarkDEX uses on-chain balances in addition to off-chain vaults is because only the user can move funds from their wallet, and these funds are initially transferred using a regular Ethereum transaction, which cannot change the off-chain data. Once the funds are in the contract, the StarkDEX system can move it off-chain.

This concludes our overview of StarkDEX. In the next blog post we will describe our contracts and statements in more details. If you have any questions or suggestions please comment here or talk to us on Twitter @StarkWareLtd.

Lior Goldberg & Oren Katz
StarkWare