Research Summary: TEX – A Securely Scalable Trustless Exchange

Mechanism Design and Game Theory
, ,
1

TLDR:

  • Traditional DEXs are vulnerable to front-running because they rely on trusted order books, potentially allowing a malicious miner or operator to alter order execution.
  • The authors propose a Trustless Exchange (TEX), a centralized non-custodial settlement layer that can scale like a custodian centralized exchange, as a solution.

Citation

  • Khalil, Rami, Gervais, Arthur and Felley, Guillaume . “TEX-A Securely Scalable Trustless Exchange.” IACR Cryptol. ePrint Arch. 2019 (2019): 265.

Link

Core Research Question

  • How can we design a scalable, trustless exchange that is also front-running resilient?

Background

  • Decentralized exchange (DEX) is an exchange that does not involve trusted third parties and is implemented with smart contracts.
  • Front-running exploits insider information to conduct privileged trades. For example, an exchange’s operator can execute its own order before another order, thereby anticipating the impact on prices. This can be conducted by (1) the operator of an order book, (2) a blockchain miner who can reorder transactions in a blockchain block, and (3) traders paying higher transaction fees.
  • Custodial exchanges have their users’ private keys (i.e. holding their users’ cryptocurrency). Trades are performed off-chain, and tracked on their balance sheet instead of verified by the blockchain. Custodial exchanges usually require KYC while non-custodial exchanges do not, offering better anonymity.
  • Moonwalk order
    • Goal
      • The order book does not gain any information about an incoming order, and is expected to confirm incoming orders before learning their details.
      • Front-runners will be degraded from profit-driven reporters.
    • Components
      • Time-Lock Puzzle (time-lapse encrypted order)
        • Goal: To send information to the future
        • The information will be encrypted and only decryptable after a time span with the trader’s key.
      • Zero Knowledge Proof
        • Goal: Allow a prover to prove to a verifier that a certain statement is true, without revealing any other information.
        • zkSNARK is a type of zero knowledge proof (ZKP) that is non-interactive, succinct (small proof length), and can be verified with few computational costs (with a smart contract). However, most constructs require trusted setups.
  • Payment channels establish private peer-to-peer channels between two parties so that they can enjoy lower transaction latency without committing all transactions to the blockchain.
  • Commit-chain is a mechanism to perform off-chain transactions.
    • Detailed steps:
      • Users lock their funds in a pool of collateral using a smart contract.
      • A centralized operator coordinates payments between the users.
      • The operator periodically commits the state of the commit-chain to the smart contract such that the user’s account and transactions are easily verified.
    • Pros
      • The operator does not have custody of funds (the smart contract does).
      • Users are not required to be online during the entire transaction, they need only verify their balance proof from the operator.
      • Users can exit the smart contract at any time with their latest confirmed balances.
    • Cons
      • The operator is a single point of failure for two parties to perform payments.
    • Example implementation: NOCUST
  • Eon is the time interval that the commit-chain submits a checkpoint to the parent ledger.

Summary

  • The problem
    • Traditional financial exchanges have two components:
      • a trade-matching system matching the supply and demand for assets
      • a trade-settlement system which executes matching trades
    • Early DEXes:
      • Expensive and slow due to the low throughput of PoW blockchains
      • Users may have to pay the transaction fee for non-fulfilled orders
    • The second generation of DEXs:
      • More scalable by making the trade-matching system more centralized and external to the blockchain. The settlement system remains on chain.
      • Front-running on the centralized matching system is hard to detect.
    • Summary
      • Both crypto and custodian exchanges suffer from front-running, since the matching system is centralized. For DEXes, traders are vulnerable to transaction fee bidding and miner front-running.
  • Existing solutions
    • LibSubmarine
      • Mechanism: Submarine Sends
        • Steps
          • Alice wants to interact with a smart contract without being front-run.
          • Alice sends a commit transaction to the submarine address with encrypted parameters to interact with the smart contract and some locked-up ether.
          • After the commit transaction is included in the blockchain, Alice can reveal the parameters in the commit to interact with the smart contract.
          • If Alice does not reveal the transaction, she will lose the locked-up money.
      • Limitations
        • This can only prevent miner front-running but cannot counter centralized front running attacks.
    • Payment channel
      • Mechanism:
        • Establish private peer-to-peer channels between two parties.
        • A channel is instantiated and closed with a respective blockchain transaction.
      • Limitations
        • Requires a parent-chain transaction to on-board each new user.
        • Traders need to be online simultaneously to ratify a trade.
        • The amount of collateral needs to be equivalent to the trade volume .
  • The solution:
    • The authors propose TEX, the first centralized non-custodial settlement layer that can scale like custodian-centralized exchanges.
    • TEX characteristics:
      • It is based on the commit-chain scheme.
      • Trade matching is performed off chain while trade settlement is on chain.
      • The centralized part in TEX can be a single point of availability failure.
      • If a TEX instance were to act maliciously, a smart contract would force the instance to halt, and users could retrieve their funds.
      • Users can easily migrate to another TEX instance.
    • TEX’s system components
      • Ledger supervised by a smart contract:
        • Properties
          • TEX requires the periodic submission of a constant-sized checkpoint, irrespective of the number of trades executed.
      • Trader: users that trade on TEX
        • Properties
          • Trades sent to the exchange will not reveal a trader’s identity.
          • Traders need only be online when initiating orders, but do not need to remain online to execute the order.
          • Concerning privacy, traders do not learn which counter-party their orders matched with.
          • Traders need to monitor the parent ledger at least once per eon to verify that their funds remain consistent.
            • If not matched, they can submit a dispute with the smart contract to halt the TEX instance.
            • They can also outsource verification to a third party.
      • Order Book
        • Functions
          • Collects orders, provides trade receipts, matches trades, and forwards them to the settlement layer.
        • Example
          • Alice creates a time-lapse encrypted moonwalk order hiding the details (price, assets, address), and a ZKP to prove the validity of the order.
          • Alice sends the order to the order book.
          • The orderbook verifies through the ZKP that the time-lock puzzle is correct.
          • The order book appends the order with a signed receipt.
          • After receiving the receipt, Alice either provides the solution to the time-lock puzzle (revealing the key to decrypt the order), or the exchange is required to decrypt it (by investing a few seconds of computation).
      • Trade Settlement System
        • Function
          • A centralized server that executes matched orders
          • Interacts regularly at a time interval with the TEX smart contract
        • Properties
          • If the server fails to submit checkpoints to the parent-chain ontime, the smart contract would halt it.
          • If a TEX instance (the server) is halted, the not-yet checkpointed trades are reverted.
          • The server cannot create more assets than have been deposited on the parent-chain.
        • Example
          • Alice wants to convert coin X to coin Y, while Bob wants to do the opposite.
          • Alice converts 1 X parent-coin into a commit-chain asset, by depositing the coin into the TEX smart contract.
          • Alice signs a state update for agreeing to receive 1 Y if being debited 1 X. Bob performs the opposite.
          • The trade settlement system ratifies the two orders respectively.
          • The trade settlement system matches and executes the two orders.
          • Every eon, TEX submits a checkpoint to the smart contract that applies the commit-chain balance updates.
          • Alice and Bob (traders) both verify the validity of the checkpoint.
          • After the trade, Alice does not know who Bob is and vice versa.
    • TEX’s attacker model
      • Order book
        • If the exchange operator wants to front-run trades
          • To do so, the operator needs to solve the time-lock puzzle, before providing a trade-receipt to the trader. The trader can monitor the response-time of the operator to detect suspiciously long response times.
        • If a trader withholds the moonwalk order’s key to decrypt the time-lock puzzle
          • The exchange must invest (a few seconds of) computational resources to solve the order.
          • Other traders cannot see the latest order book or submit new orders until the order is decrypted.
          • Traders that repeat this misbehaviour may be banned.
      • Settlement system
        • If a trader attempts to double-trade commit-chain funds
          • The TEX server will not ratify such trade
        • If a trader colludes with the exchange operator
          • The trader may be able to double trade, but they will be reported by other honest traders.
          • The trader is still not able to create commit-chain assets indefinitely since it requires full collateralization of assets.
        • If a blockchain miner wants to front run trades
          • Since trades are performed on the commit-chain instead of the parent chain, miners cannot front-run it.
  • The authors present the pseudocode of the algorithms to implement TEX and provide proofs for the claimed properties of TEX.

Method

  • The authors deployed the TEX settlement smart contract on Ethereum.
  • The TEX server is implemented in Python, with an eon interval of 36 hours.
  • Traders can interact with the exchange through a JavaScript library.

Results

  • The gas cost of the operations on the parent chain

1060×458 48.7 KB

  • Storage Costs and Performance
    • Storage required on the parent chain is small and thus TEX is scalable.
      • The only parent-chain footprint is the constant sized checkpoint hash that compresses all of the user’s balances.
    • Trade Throughput
      • 10 trades per second between two accounts on a single CPU core
  • Instant Exchange Collateral Costs
    • The collateral requirements of TEX for instant trade finality equals the trade volume of the last two eons, times the price difference of the traded assets within the last two eons.
    • Assuming an eon interval of 12 hours, a daily trade volume of 300M USD, and a currency fluctuation of 10%, the collateral amounts to 300 × 0.1 = 30M USD

Discussion & Key Takeaways

  • TEX is based on the commit-chain scheme, where trade matching is performed off chain while trade settlement is on-chain.
  • TEX solves the high transaction fee problem of current decentralized exchanges by utilizing a separate blockchain that is easily scalable and commits periodically to the main chain.
  • TEX consists of four components, including a smart contract-enabled ledger, traders on the platform, an orderbook that matches trades, and a trade-settlement system that executes the orders.
  • The author introduces a novel concept called a “Moonwalk order”, that is privacy-preserving and front-running resilient. It is achieved by leveraging time-lock puzzles and zero-knowledge proofs.
  • Compared with payment channels, TEX requires less collateral and does not require additional transactions to onboard new users.
  • Custodian exchange honesty is currently enforced through manual regulatory audits. TEX is held accountable through cryptographic and non-repudiable supervision.
  • Maleficence by the TEX operator, i.e. front-running of orders, can be transparently uncovered via secure cryptographic means. The reporters are also incentivized to do so.

Implications & Follow-ups

  • Currently, the authors do not provide a demo or open-source code for others to experiment with. Only the gas cost measurement for using the system is available.
  • A comparison between the advantages and disadvantages of different exchanges is worth exploring (i.e. custodian vs non-custodian, front-running resilient or not, privacy-preserving or not).

Applicability

  • It should be worth trying TEX once the platform is live, given its proposed benefits.
  • For TEX to be adopted by mainstream users, it still requires time to prove the soundness and security of its architecture design. From a user’s perspective, using centralized and custodian exchanges is still preferable since funds are guaranteed to be backed by the operating company.
6 Likes
2

Interesting read! Seems like this design sits at the intersection of an optimistic rollup scheme and a sidechain. If the goal of TEX is to provide a wide range of tradable products (esp. derivatives), its architecture makes a lot of sense.

But if the goal is for simple P2P exchanges with shielded orderbooks and deferred settlement on-chain, I don’t understand why this would be better than a zk-rollup exchange. Like TEX, the majority of DEX designs using zk-rollups shield orderbooks.

My superficial analysis on the key difference is that, if a zk-rollup DEX goes down, zk validity proofs still enable users to recreate their balances in L1. On the other hand, if a TEX instance goes down, users would still have to rely on the DEX operators to bootstrap a new one, unless I’m missing something.

If you assume the zkSNARKs used in a zk-rollup scheme to be safe (admittedly, a non-trivial assumption) the trust models between the two seem to be considerably different.

4 Likes
3

Yes you are right about this. Currently zk-rollup cannot support complex operations like financial products and derivatives. So this can be seen as the trade-offs between using TEX vs zk-rollup.

4 Likes
4

I wonder the extent to which zkp circuits can be used to create generalized programming languages that could circumvent that limitation.

zkSync, for example, is building Zinc as a programming language for zk-rollup smart contracts. Its syntax looks a lot like Rust, which I like, but haven’t seen any applications built on it.

3 Likes
5

If I got it right…that’s a big if.

The commit-chain design in TEX is borrowed from author’s previous work:

And I think the exit protocol still enables user to have an emergency exit if an operator attempts to censor/block user from withdraw his/her funds.
圖片

For CEX vs DEX, the first thing that comes to my mind is that CEX enables high-frequency trading, and this is indeed likely what the author wants to emphasis in,as seen in Table 1.

圖片
圖片1225×360 55.3 KB

Still, excited and can’t wait to see if a codebase/product backs the performance that was claimed in the paper, and if it scales up (i.e., engineering issues).

4 Likes
6

@Jerry_Ho I like the insights here. I’m wondering if you’re willing to go a little further with your thoughts about where this goes. In particular, you stated:

and what wonder what you see as the potential barriers to this scaling and performance?

2 Likes
7

I’d just say it’s more of an engineering barrier rather than a theoritical barrier.
One always has to prove that he/she has a reliable experienced engineering team to fully realize their ideal upperbound performance.

In the landscape of Blockchain, we always almost prefer decentralized solution most of the time (it’s also politically correct).

However:

圖片
圖片875×633 62.1 KB

(picture credit: Vitalik)
AFAIK, it’s more reasonable to have high frequency trading (bots) happen on CEX rather than DEX, this is also what the author of the paper suggested/implicated.

I think it will be a good application to increase the diversity of exhanges on Blockchain, if TEX ever got implemented & has good performance.

2 Likes
8

This seems to be pointing toward another article that @Vishesh posted a few months back.

A diversity of exchanges does seem like a great idea in practice, but in a hybrid TEX/DEX world, would it be likely that there would be polarization? In my mind, these different mindsets regarding exchanges seem to incentivize different behaviors.

3 Likes
9

I am not sure that a more diverse exchange design space, such as the hybrid TEX/DEX world actually looks any different. As @Jerry_Ho pointed out, it is not clear whether the incentive design is any better than in the DEX construction with some sort of shielded orderbook.

In fact, a more private P2P construction might present more concerns with respect to MEV if it is harder to determine when out of band payments are made as “bribes” for transactions.

As far as polarization goes, I do not think that centralized exchanges even have reduced risk of front-running or bribery, but rather just a reduced risk of finding out about it since not all transactions are recorded on chain.

3 Likes