StarkExchange: Fast Withdrawals using Cookie Jars

A trustless mechanism that breaks the “proof-time” barrier

Published in
4 min readJul 22, 2019


A few weeks ago, we described StarkExchange, our scalability engine for non-custodial trading in centralized exchanges. In the original design, the speed of withdrawals on StarkExchange was gated by “proof generation time” — the time to gather a batch of trades, compute a proof attesting to their validity, and have the proof accepted on-chain (this takes several minutes).

We propose below an improvement: a trustless mechanism that allows much faster withdrawals, gated only by the duration of transacting over Ethereum.

Benefit: Lower Cost of Capital & Faster Response to Market Opportunities

Faster withdrawals mean lower cost of capital for traders: a trader needs less capital to participate in the market, because it is easier/faster for them to move funds around to benefit from arbitrage opportunities.

Table 1: Comparison of Exchange Solutions

Technical Discussion

Changes to the StarkExchange System:

  • Conditional Payment: Intuitively, this is a payment from Alice to Bob that goes through only if some condition is satisfied.
    We use Conditional Payments as a “blockchain proof” primitive — a means of ensuring that on-chain state controls off-chain state. Specifically, a payment is made off-chain (i.e. included in a batch attested to by a STARK proof), only if some record appears on-chain.
    Conditional Payments are already used in StarkExchange, when we move user deposits off-chain: a deposit cannot be included in a proof (which attests to a change in the off-chain state), unless a matching deposit is observed on-chain.
    The many benefits of Conditional Payments will be discussed in a separate blog post.
  • The Cookie Jar contract: The exchange sets up an additional smart contract, from which it pays out Fast Withdrawals. Note that this contract can benefit from the fact registry design pattern, in order to store the evolving history of payments made on-chain to the participating parties.

A Single Fast Withdrawal Flow:

  1. User sends the exchange a Fast Withdrawal request: a signed Conditional Payment transferring the amount the user wishes to withdraw to the exchange (off-chain), conditional upon the transfer of the same amount to the user on-chain.
  2. The exchange — assuming the user indeed has the funds in their off-chain balance, and the exchange has sufficient funds available in the Cookie Jar — instructs the contract to transfer the requested funds to the user, and mark the Fast Withdrawal as complete.
  3. The exchange submits the conditional payment to the prover. As this payment’s condition is satisfied (a corresponding payment to the user can be observed on-chain), the prover includes it in its next proof, and consequently funds are moved off-chain from the user’s account, to the exchange’s account.

Replenishing the Cookie Jar Contract:

The exchange replenishes its on-chain Cookie Jar from its off-chain balance (in essence recycling funds between its on-chain and off-chain balances). Replenishment can be done periodically, or can be triggered by the available funds (per token) reaching some minimum threshold amount/value.

Worth noting: the more frequent the replenishment, the lower is the exchange’s cost of capital to support Fast Withdrawals. For example: let us consider a Cookie Jar from which x tokens/hour are withdrawn. If it is replenished daily, the exchange must lock up 24x tokens in the Cookie Jar (or some higher amount that includes some safety margin). If, on the other hand, it is replenished hourly, then the exchange must keep only x tokens in the Cookie Jar. The cost of capital is determined by the frequency of replenishment.

New Revenue Stream for Exchanges

Fast withdrawals can be priced for different tiers of service. As such, they present an interesting business opportunity for exchanges, one which allows to price-discriminate between professionals (arbitrageurs, for example) who will pay for a premium service, and retail customers.

Historical Note

A similar proposal for fast withdrawals on Plasma was presented back in June 2018. That mechanism relied on fraud proofs, not validity proofs, resulting in a more complex protocol. Importantly, the “liquidity contract” presented there (the Cookie Jar contract, in our proposal), had to cover the period of time for disputing frauds (on the order of two weeks, compared to our one hour timeframe), resulting in a much higher cost of capital (about 200X higher).


StarkExchange V1.0 was designed to enable liquid self-custodial trading.

With Fast Withdrawals, StarkExchange provides:

  • For the user: lower cost of capital
  • For the exchange: greater revenue potential (for example by enabling new pricing tiers, appealing to arbitrageurs, and more)
  • For all parties: inexpensive & trustless. Neither the exchange nor the user can steal the other party’s funds

The incremental cost of Fast Withdrawal to users is only the cost of capital of the limited funds locked up in the Cookie Jar; other costs (gas cost and proof generation cost) remain essentially unchanged.

Tom Brand, Avihu Levy, and Michael Riabzev




STARK-Based Scaling Solutions