Off-chain state

Balances Tree

The first element in the off-chain state of StarkEx is the balancesTree. The balancesTreeis a Merkle Tree. We refer to its leaves as "Vaults". Each Vault contains a starkKey - a unique key that identifies the user in the off-chain state. This key is coupled through the StarkEx smart contract to the user's Ethereum address. Other elements in the vault are defined according to the business logic.
The exact structure of the vault is described here for spot trading and here for perpetual trading.

Orders Tree

A bit less intuitive but crucial part of the off-chain state is the ordersTree. This is another Merkle Tree, and its goal is to prevent replayability of transactions in the system by the operator. To prevent this attack, StarkEx does the following:
  • The i leaf of the ordersTree includes the already fulfilled amount of the limit order with the hash i. For example, if Alice signed on a transfer request with a total amount of 1000 USDC and a hash value 0xdeadbeef, StarkEx stores in leaf index 0xdeadbeef in the ordersTree an amount of 1000 USDC (after quantization).
  • Should the operator try to re-submit Alice's order - As part of checking the validity of a transfer, we check that this transfer was not executed before - meaning that the value written in leaf number 0xdeadbeef is zero. Since this is not the case, this order cannot be accepted by our on-chain Cairo Verifier.
Partial fulfillment of limit orders is also supported by this mechanism. On trades, the operator has to provide the original user's limit order, as well as the corresponding amount that is transferred in this settlement. StarkEx enforces that the value saved in the ordersTree, plus the new transferred amount, is still smaller than the amount that the user signed on in the original limit order.

Enforcing Consistency on the On-Chain State

The StarkEx smart contract stores the root of thebalancesTree and the root of the ordersTree which are a commitment to the off-chain state. The state is updated when the contract receives a new proof that there exists a valid sequence of transactions that when executed, moves the current state (i.e. the current tuple of Merkle roots) to a new state (i.e. - the new tuple of Merkle roots).