StarkDEX Deep Dive: Contracts & Statement

Part 2 of 4

This is the second part of our StarkDEX deep dive, explaining the various components of the StarkDEX Alpha. In the first part we gave an overview of the system and discussed user flows and batching — if you haven’t already read it, we encourage you to do so before reading this post.

In this post we will describe in detail our smart contracts, our system-specific terminology and how it translates into the statement of a valid state transition we are proving.

Design Goals

The main goal of the smart contract is to ensure users’ self-custody, alongside the ability of trading in the exchange. For scalability, the contract does not store the entire balance state as decentralized exchanges do. Instead, it saves a succinct representation of the balance state — a Merkle commitment (32 bytes for the entire state). We ensure the integrity of the state by requiring a valid STARK proof for every update of the state commitment, showing the validity of the update. Our escape-hatch mechanism ensures that users can always retrieve their funds, even if the exchange service is unresponsive, or decides to maliciously censor them.

High Level Design

Figure 1: High level contract — Structure and interaction with users.

There are two central contracts:
(a) The StarkVerifier contract — A stateless contract that receives as input a STARK proof and its public input, and verifies the correctness of the public input using the proof. If the proof is accepted, the public input is then passed to the StarkExchange contract in order to manipulate its state.
(b) The StarkExchange contract — This contract maintains a commitment — a succinct representation of the balances. Moreover, it holds records of on-chain deposits and withdrawals.

Notation

StarkDEX user key

The StarkDEX user key is used by StarkDEX to verify users’ ECDSA signatures. The signature is verified as part of the proof, and because the elliptic curve used in Ethereum is not STARK-friendly, we use an ECDSA implementation over a different, STARK-friendly, curve. This requires users to generate additional key pairs in order to use the StarkDEX system. In order to distinguish the standard Ethereum key from the StarkDEX user key, we refer to it both here and in the code as “STARK key”.

Vaults

Vaults are used for storing balances. Each vault is identified by a unique ID, and labeled by its owner’s (STARK) public key and the asset ID it stores (AKA tokenId). The content of a vault is the amount of coins in the vault. Users can have several vaults, storing different portions of the same asset.

Asset Quantum

In the proof system we are bounded by 63 bits for amount representation (by design), thus we normalize each asset using a dedicated quantum, defined at the asset’s registration. A single unit of a quantized amount (of any asset) is expected to be worth approximately 10–4 USD, excluding the case of non-fungible tokens. For example, when trading Wrapped Ether, we would use a quantum of approximately 103 (wrapped) Gwei (there are 109 Gwei in one Ether), which is approximately 10–4 USD at the moment, and allows for trading amounts from 10–4 USD up to 1015 USD, which seems sufficient for most practical uses. An asset’s quantum can become obsolete as a result of extreme changes in the asset’s worth. To protect against this happening, an asset can be registered again with a different ID and an updated quantum, allowing multiple versions of the asset to exist simultaneously.

Standard User Flows

Registration

To register, the user calls the contract function register, providing it with their STARK public key. The contract associates the caller’s Ether key with the provided STARK key. This association is essential for user-address translation during withdrawal and deposit flows, as within the system, StarkDEX users are identified by their STARK key.

Deposit

To deposit funds into the system, the user invokes the deposit function, providing it with the tokenId identifying the asset, a vaultId, and the quantizedAmount to deposit. When depositing a new asset, for which the user does not have a vault, the user should contact StarkDEX for a dedicated vault ID assigned to this asset. In practice, such communication can be done transparently from the front-end. The on-chain deposit records are identified by the triplet of (starkKey, tokenId, vaultId), and the only restriction applied by the contract on user deposits is for the STARK key to be compatible with the depositor’s ether key. It is up to StarkDEX to choose which deposits are legitimate. Should some deposits not be picked up by StarkDEX for any reason, whether because the (tokenId, vaultId) were not provided by the operator or because the operator becomes malicious, the user can cancel the deposit using the Escape Hatch mechanism. Finally, if the deposit is legitimate, the funds are moved from the on-chain deposits area to the off-chain area using a proof attesting the vault’s off-chain balance has been increased by the correct amount.

Withdrawal

To withdraw funds from the exchange, the user should first contact StarkDEX via an off-chain channel (e.g., the exchange’s website), and request to move funds from the off-chain area to the on-chain withdrawals area. Once a proof confirms the movement of funds to the on-chain area, the user can withdraw from the StarkDEX contract directly using the withdraw function. The function receives only a tokenId, identifies the user’s key from the request, and transfers the amount (of this specific asset) stored in the user’s on-chain withdrawals area directly to the user’s wallet.

If StarkDEX does not fulfill the user’s request to withdraw from the off-chain area, the user can use the Escape Hatch mechanism to ensure the user always get their funds.

Escape Hatch Flows

The Escape Hatch is designed to let the user maintain the ability to withdraw funds regardless of StarkDEX’s availability (we will publish a separate post on the range of data availability solutions in the coming weeks).

As shown in our previous blog-post, there are three areas in which funds (actually, their records) can be present — the on-chain deposits area, the on-chain withdrawals area, and the off-chain trading area.

Recall the standard flow of funds between areas: deposits → trading → withdrawals.

Each movement from one area to another requires StarkDEX’s involvement. Using the standard flow, users can extract funds only from the on-chain withdrawals area. The Escape Hatch mechanism enables users to extract funds from the other two areas.

Escaping from the On-Chain Deposits Area

The main purpose of this escape mechanism is to extract the funds even if StarkDEX, whether maliciously or not, does not pick up the deposit (i.e., does not move the funds off-chain).

Users can retrieve funds from the on-chain deposits area by following the flow described here.

A user must first call the function depositCancel, providing it with the tokenId and vaultId, requesting to cancel the transfer of deposit of the requested asset into the requested vault. The cancellation request is time-locked to prevent a race condition between the request and incoming proofs sent by the exchange; thus, calling depositCancel only records the request, activating the time-lock. After a sufficiently long period of time has passed (set arbitrarily to be 1 day in the Alpha contract), the user can call depositReclaim with the same parameters, transferring all the funds from the requested vault to the user’s wallet.

Note that at any time between the two calls, a proof reducing the amount on-chain can be accepted. In this case, the second call only transfers the funds left on-chain to the user’s wallet.

Escaping from the Off-Chain Trading Area

Forcefully withdrawing funds from StarkDEX is done in two different ways that we explain in detail later in this section: (1) As long as the exchange is operational, the smart contract ensures that the exchange does not censor any user. (2) Once the exchange ignores even a single user’s withdrawal request, the contract allows the ignored user to shut down the exchange (we say the exchange becomes ‘frozen’ in this state) and allows users to withdraw their funds by displaying a binding of their vault contents to the (fixed) Merkle root of the balances’ DB. Now for the details.

Phase (1): Operational Exchange

If the user’s (off-chain) requests to withdraw funds are ignored by the exchange, they can call the escapeRequest function, providing it with a vaultId, notifying the exchange that it must withdraw the user’s funds from the requested vault. To prevent DoS attacks on the exchange, which needs to respond to each such request (within a time frame), a non-negligible fee would be collected for escapeRequest. If within a fixed time (set arbitrarily to five days in the Alpha) StarkDEX does not provide a proof moving all vault content to the on-chain withdrawals area, or alternatively showing the vault does not belong to the caller, then the user may call the escapeFreeze function, freezing the exchange, and moving to the next phase.

Phase (2): Frozen Exchange

Once the exchange is frozen, all proofs submitted by it are automatically rejected by the contract, consequently freezing the state of the off-chain balances’ DB by fixing its Merkle root and rendering it immutable. While in frozen state , all users may withdraw their funds by presenting to the contract a direct proof of asset ownership. This part was not implemented in the Alpha, and can be implemented succinctly using STARKs, or less succinctly by explicitly providing Merkle authentication paths from a vault to the (frozen) DB root.

StarkDEX Contract State

In the previous sections we introduced several parts of the StarkDEX contract’s state, namely, the on-chain deposits and withdrawal areas, and a structure storing users’ escape requests. All these structures are dynamically modified by actions invoked by users on-chain. In the next section we describe the interaction of the StarkDEX contract with the exchange operator, but first we show how the off-chain state is projected in the StarkDEX contract: the vaults’ Merkle commitment, the settlements’ Merkle commitment, and the sequence number that increases with every update of the state.

The Vaults’ Merkle Commitment

As described earlier, user balances are kept in vaults, each vault is represented by a unique ID and a triple (starkKey, tokenId, amount), where the starkKey identifies the vault’s owner, the tokenId identifies the asset stored in it, and the amount is the (quantized) amount currently stored in the vault. A vault storing (starkKey=0, tokenId=0, amount=0) is called “empty”. Vault IDs are consecutive integers between 0 and 2³¹-1, thus every ID defines a unique path to a leaf in a Merkle tree of height 31, where the information is stored. The StarkDEX contract manages the off-chain balances by storing the root of the vaults’ Merkle tree (and its height), ensuring that any change to its state is a result of a (legal) deposit, withdrawal or settlement. If the vaults’ Merkle root is updated as a result of a deposit or a withdrawal, the StarkDEX contract confirms the on-chain balances are updated accordingly.

Figure 2: Illustration of the vaults’ Merkle tree.

Data Availability

Note that in case the StarkDEX contract freezes (see the Escape Hatch section), it is crucial for users to have access to the entire vaults’ state. This is called the data availability problem. As our current solution, StarkDEX uses a committee of reliable parties (e.g., StarkWare, 0x, the Ethereum Foundation, exchanges, etc.), and expects every new root to be signed by a majority of the committee, ensuring the data is publicly available. Note that (1) the data availability mechanism is not implemented in the Alpha and (2) if and when other data availability solutions are considered “standard best practice” we plan to use them instead.

The Settlements’ Merkle Root

Each settlement is identified by a unique ID, signed by both parties (maker and taker). Similarly to the vaults’ Merkle tree, the settlement IDs are in the range 0…2³¹–1, and we record the set of executed settlements using a Merkle tree with boolean value leaves, where each leaf corresponds to a settlement ID (the boolean value signifies whether the settlement has been executed or not). The root of the settlements’ Merkle tree (and its height) is stored in the StarkDEX contract as well, and is required to ensure no settlement is executed twice. This feature is only partially implemented in the Alpha.

Figure 3: Illustration of the settlements’ Merkle tree.

Sequence Number

The sequence number is a monotonously increasing identifier of the off-chain state, and together with the vaults’ Merkle root and tree height, is signed by the committee members. Its purpose is to ensure that every change to the root is verified by the committee, even if the new root represents a repeating balance state. Without the sequence number, someone could save all the committee signatures, and if a state repeats, they could withhold the data from the committee, and use the old signature on the same state, which the committee might not be able to restore.

StarkDEX Operator Actions

The exchange operator can change the StarkDEX state by applying any of the following operations: (a) deposit from the on-chain area to the off-chain area. (b) executing a settlement (c) withdrawal from the off-chain area to the on-chain area. (d) fulfilling Escape Hatch requests from the off-chain area (AKA “full withdrawal”). Below, we describe how each of these operations affect the state of the StarkDEX contract, and the requirements for validating the operations’ legitimacy.

Deposits: From On-Chain to Off-Chain Areas

The parameters of a deposit operation are (starkKey, vaultId, tokenId, amount).

The operation requires that the corresponding on-chain balance holds at least (a quantized) amount of the required asset, and that the vault with the required ID in the off-chain state (represented by the Merkle root) either belongs to the same STARK key or is empty.

The following is guaranteed after the deposit is finalized:

• The required amount is reduced from the on-chain balance, and added to the off-chain vault
• The off-chain vault’s starkKey and tokenId are consistent with the parameters
• The changes to the off-chain state are reflected in the on-chain vaults’ Merkle root

Settlements

The parameters of a settlement are:

• Two STARK keys and signatures; one for each party
• Two token ids and amounts representing the traded assets
• Four vault IDs. Each party has two vaults involved (one for each asset)
• Settlement ID

The operation requires the following:

• Knowledge of the maker’s signature on maker’s vault IDs, token IDs, amounts, and the settlement ID
• Knowledge of the taker’s signature on the message the maker signed, together with the taker’s vault IDs
• The settlement ID was not already used (not in the Alpha)
• The vaults belong to the expected owners (maker/taker) and store the required assets

The following is guaranteed after the settlement is finalized:

• The required amounts are reduced from the corresponding outgoing vaults and added to the corresponding incoming vaults
• The settlement ID is changed from unused to used in the settlements’ Merkle tree
• If a vault has amount=0 after the settlement is executed, it is emptied so that it now has starkKey=tokenId=0 as well
• The changes to the off-chain state are reflected in the on-chain vaults Merkle root

It is worth mentioning that a vault that was empty at the beginning can belong to anyone and can store any asset.

Notice that the only effect this operation has on the StarkDEX contract state is to the Merkle roots. It is the same with a batch of many settlements — there is no need to transmit any of the settlements’ data, and it is sufficient to merely send a single STARK proof for the entire batch, together with the new Merkle roots. This gives StarkDEX the ability to batch enormous amounts of settlements in a single Ethereum block.

Withdrawals: from Off-Chain to On-Chain

The withdrawals operation is (naturally) very similar to the deposits operation. Its parameters are (starkKey, vaultId, tokenId, amount) as well, and it requires the off-chain vault to have the expected parameters (owner’s starkKey, and storing assets of tokenId), and have enough funds. It ensures that this operation reduces the off-chain vault amount accordingly (affecting the Merkle root), and marks the vault as empty in case its amount is 0. Additionally, it verifies that the on-chain withdrawal balance corresponding to starkKey,tokenId is raised accordingly.

Fulfilling Escape Hatch Requests

An escape request is valid only if the requested vault ID indeed belongs to the caller. The current architecture does not provide the StarkDEX contract with enough information to verify the validity of an escape request at submission time, thus the system addresses invalid escape requests as well. To fulfill an escape request, the operator must send a proof to the contract, either (1) proving that the vault indeed belongs to the request initiator and a withdrawal operation was invoked, after which the vault became empty, or (2) proving that the requested vault does not belong to the request initiator, and, hence, its state must not change as a result of performing this operation.

This concludes the section describing the main StarkDEX contract (aka StarkExchange). In the next section we dive into the statement verified by the StarkVerifier contract.

StarkDEX statement

The statement verified by the StarkDEX verifier contract is the valid sequential execution of a batch of operator actions, projected in the Merkle roots and the public input, which is used to modify on-chain records.

Batching Operations Using STARK Proofs

StarkDEX uses STARK proofs to batch many operations together. Each proof attests to the integrity of some public input (which is transmitted on-chain), which is used to change the StarkDEX contract state. Let’s assume for the moment that the only operation is settlement. In this case, the public input could have been two Merkle roots, initial and final. The proven statement in this case would be knowledge of a sequence of valid settlements changing the vaults state from the initial root to the final root (see figure 4). In practice, the public input contains additional details. There are two main reasons for the extra details.

The first reason is that as stated earlier, deposits and withdrawals change the on-chain balances, so information regarding such changes must be sent. The second reason is to allow for information that affects the verification algorithm — the batch size, for example.

Figure 4: Illustrating the relation between public input and witness for a batch of (5) settlements.

In StarkDEX, the integrity of the public input is verified by the StarkVerifier contract (which is stateless) using a STARK proof . Only if the proof is accepted will the public input that is required for the change in the StarkDEX state be passed forward to the StarkExchange contract. The StarkExchange contract confirms that these types of update commands are sent only from the StarkVerifier contract, ensuring the validity of each update. Next, we describe the public input fields used in our STARK proof. We focus on fields that affect the StarkDEX contract, and, for the sake of simplicity, neglect fields required for the correct operation of the verifier (e.g., batch size).

Merkle Roots

Each proof is sent with four Merkle roots in the public input, namely, the initial and final roots of the vaults’ tree, and the initial and final roots of the settlements’ tree. The StarkDEX contract ensures that the initial roots are equal to the currently stored roots, and that the vaults’ root is signed by the committee (see the section about data availability) together with the correct sequence number. The heights are part of the public input, to support future needs to enlarge one of the trees, but the functionality is not implemented in the Alpha. After confirming that the initial roots and the heights are consistent with the contract’s state, the roots on the contract are updated to the final values.

Non-Settlement Operations

Any non-settlement operation requires public input data showing changes made in the off-chain area, and this data is used to change the on-chain funds area. For technical reasons (simplifying the design of the AIR — Algebraic Intermediate Representation), we use the same public input format for all operations (except for settlements, that do not require public input). The public input format for every such operation is (vaultId, starkKey, tokenId, amountBefore, amountAfter).

The following is guaranteed by the STARK proof:

• The operation was applied to the vault with the expected ID
• The vault belongs to the starkKey owner, and stores assets of the required tokenId (or is empty)
• The operation changed the balance in the vault from amountBefore to amountAfter

One can notice this format is indeed sufficient to prove legitimacy of any operation changing the on-chain state, as listed previously, including the need to fulfill escape requests, valid or not.

This concludes our detailed discussion of the on-chain components of StarkDEX. In the next post of the StarkDEX Deep Dive series we will detail what goes into the construction of a STARK engine for DEXes.

If you have any questions or suggestions please comment here or talk to us on Twitter @StarkWareLtd.

Michael Riabzev & Alon Frydberg

StarkWare Industries