An academic approach to front-running free cross-chain exchange
Two main challenges of web3 is the inherent lack of decentralized cross-chain communication and privacy on smart contracts. Many companies and works have tried to handle these issues in different ways. For cross-chain communication, Chainlink might be one of the biggest contenders in the space, through the use of somewhat trusted oracles, that relays information from one chain onto the other. For privacy many works and systems try to achieve this by adding zero knowledge proofs. Unfortunately, this inherently only allows privacy in showing statements about private data, but does not directly facility computation on private data.
One specific case where the need for both cross-chain communication and the need for private computation comes up, is when trying to do order matching or auctions of digital goods, residing on distinct chains. This generalises to the problem of exchanging different tokens on different chains, in a way that prevents front-running.
In our work (in collaboration with Carsten Baum, Bernardo David and James Hsin-yu Chiang) we try to tackle both the blockchain issues at the same time through the use of MPC, by leveragning a small set of servers. The servers can act maliciously, but are financially incentivised (through ante on a smart contract) to be available and behaving honestly. Security of the entire system is fulfilled as long as not all servers maliciously collude.
In our first paper, P2DEX, we construct such a system by having all the servers create and hold threshold keys for burner addresses. Concretely the servers create a burner address on each blockchain for each client wish to give input/tokens to. The clients then transfers their tokens to their burner address and give auxiliary, private input to all the servers through an "outsourced MPC" protocol. The servers then execute the desired MPC protocol. This could for example be a limit order matching, on tokens which a client wishes to exchange on chain A, to tokens on another chain B. Based on the output of the MPC computation the servers threshold sign transfers out of the burner addresses to the appropriate clients and post these transactions to the relevant blockchains.
By doing the order matching in MPC, it means that neither the servers, nor miners are able to front-run the exchange, since they only learn about the clearing price once the order have been matched.
In a follow-up work called Eagle, currently in submission, we enhance the above solution by adding support for computation on hidden token amounts, besides just hidden auxiliary input. We achieve this by adding a second layer for confidential transfers, on top of any Turing complete smart contracting language. This approach uses Pedersen commitments to hidden token amounts. These commitments can be minted or burned by a holding smart contract. Clients can thus exchange native tokens for their hidden counterparts using this contract. The hidden tokens can then be used as input to an MPC computation. As part of the MPC computation, the servers compute new hidden token amounts, and ask the holding smart contract to mint these and transfer them to the appropriate clients. The servers can administrate the holding smart contract using a threshold signing key. The protocol involves a bit more cumbersome techniques, such as Schnorr and range proofs which are described in the paper. We tried to implement a minimal integration of this, but did not manage to finalise it due to limited funding. So when it comes to future work, it would be very interesting to do a full proof-of-concept implementation along with researching additional optimisations in relation to storing commitment opening information in a user-friendly manner and optimise the needed ZKPs.
A simplistic approach using Medusa
Medusa gives access to threshold signatures and threshold decryption, but not a fully fledged MPC scheme. Even if MPC were to be implemented in Medusa, the throughput needed for an exchange service would likely be higher than what would be feasible to compute with low latency using MP,C. Thus we consider a more simplistic approach. This approach does not offer the same level of fairness but would still be better than the competition, e.g. Axelar.
The overall idea is to utilise a holding contract on all chains in question, which is administered by a threshold signature, held collaboratively by the servers in the Medusa network. Clients then communicate orders to the Medusa network through threshold encrypted messages, posted to the holding contract for posteriority needs.
Simplest approach - leaks token amounts
- Clients will transfer a large amount of tokens (some of which they they wish to exchange) to the holding contract on the chain in question. At the same time they post a threshold encryption of their order information (i.e. amount they wish to exchange, and to what tokens and to what address).
- At a certain point in time the servers then decrypt all new orders, and based on these, along with the liquidity of the holding contracts, compute the market clearing price.
- The servers then threshold sign the exchanges that must be carried out on each chain and post the orders to each of these holding contracts.
- The holding contracts validate the signature send the appropriate funds to the clients.
It is easy to see that an upper bound on the amount of tokens a client wish to exchange gets leaked before the exchange is carried out, or the exchange rates are finalised. Based on metadata, an observer could conjecture which tokens are the most popular and perhaps use this to arbitrage. Furthermore, this also has the problem of privacy, since clients will now publicly leak how much they exchange from one token to another at what time.
Encrypted transactions
The potential for arbitrate can perhaps be limited a bit using the following approach:
- Clients encrypts a signed transfer to the holding contract in question under the threshold key. They post this, along with encrypted auxiliary information (i.e. to what tokens and to what address), to the holding smart contract.
- At a certain point in time the servers then decrypt the new orders. They post the signed order on behalf of the clients to move their funds to the holding contract.
- Once this is finalised the servers compute the market clearing prices and based on this, threshold sign the exchanges that must be carried out on each chain and post the orders to each of these holding contracts.
- The holding contracts send the appropriate funds to the clients.
This solution prevents the client’s orders from being known publicly before they will get carried out. Unfortunately the token amounts are still leaked.
This leakage can be prevented by constructing an anonymous token on each of the different blockchains that can be exchanged from/to. This follows the approach of Eagle. It has the downside that zero-knowledge range proofs are now required to be constructed and validated. However, these should still be lightweight enough and simple enough to do efficiently, without too much complexity.
A note on holding contracts
As described above the holding contract only holds tokens which clients wish to exchange. It is unrealistic to assume that the popularity of tokens on different chains will perfectly match. Thus the holding contracts will require some liquidity to carry out the exchanges. In fact, such liquidity can be used to ensure a natural and fair exchange rate between each pair of tokens that can be exchanged by letting it define an AMM.
A note on financial use-case
Since the servers have threshold access to the funds of the users, it is easy for them to take a certain fee for the exchange and to continue to provide gas to the holding smart contracts.
In a similar manner such a fee can also be taken and distributed to the liquidity providers if realising the system as at set of AMMs.
A note on threshold security
We note that in the approaches mentioned above security reduces to the fact that not all threshold servers collude, as they together would be able to convince the holding contracts to pay out tokens to whichever address they desire, including their own.
We can mitigate this with a dispute phase on the holding contracts before payout. Basically payout consists of the servers first position the threshold signature on the desired payout distribution to the holding contract. Then after a set amount of rounds, if no dispute has been received, the contract will pay out. This gives the clients a chance to dispute the payout. That is, if a client notices that they don’t receive what they expect. Such a dispute can be handled through them posting the signed block containing transfer information of the holding contracts on the other block chains along with a decryption of the order information they posted along with their order. Based on the algorithm for computing the exchange rates, the smart contract can validate that the servers do not behave honestly and thus refuse to carry out the exchange and refund the users.
This is of course quite expensive and would have to be paid by the user issuing the dispute to prevent a financial denial of service attack. However, by requiring the servers to put in ante to the holding smart-contracts, then we can add logic saying that the servers will lose their ante if they cheat, and it will instead be shared among the clients who did not have their orders carried out.
Miner front running
While all orders are either carried out or not, after they are finalised, a miner could still choose not to include the batch of order in the block they mine. This means that the exchange rates for the given round of exchanges does not become public immediately. Thus the miner has a chance to arbitrage based on this knowledge, by quickly exchanging tokens though another exchange service with better exchange rates at this point in time.
This is unfortunately hard to prevent when orders are public, but also seems to be a hard attack to carry out. Furthermore it is an attack that does not directly cause unfair prices to the users of the exchange.