Crypto Island

 image/svg+xml

Simple Cardano "batching bots" for concurrent DEX protocols

Posted 2021-09-10
Updated 2021-09-11
Tags: , , , , , ,
Contents

Everyone seems so interested in Cardano’s concurrency problem that I decided it’s worth posting my own half-baked solution. This is mainly based on (and almost identical to?) Chris from Mirqur’s idea. It sounds like others are thinking along similar lines as well.

Update: MELD has a simpler solution that removes the need for an auction by requiring a predefined set of UTXOs to be used as user inputs. That looks better for most use cases. I could see it having an issue with auction sniping though.

Update: only one bid can reference each original trade UTXO; subsequent bids just reference the previous state

A (relatively) simple batching protocol

The basic idea is to have a three-phase protocol for updating the DEX state:

  1. First, everyone who wants to interact with the DEX posts a transaction that announces the trade they intend to make. It doesn’t actually consume the current DEX state though. They would just send their tokens to a DEX-controlled script address that acts like a queue with an attached datum specifying the trade parameters they agree to. A large number of them could be submitted at once during one or several slots.

  2. Next, an “auction” where anyone can run a bot that gathers up all the posted trades and executes them at once according to the DEX logic. They would be paid a small fee for doing it, and have to post collateral to be slashed if they leave any valid trades out. Each “bid” has to include all previous valid transactions plus at least one new one.

  3. After waiting a few slots for any more state transition bids to appear, the final step is to apply the highest-bidding transition to the main DEX UTXO, reward the winning bidder, and slash any other bidders’ collateral. Anyone could do this step as well but the winning bot is the one with the most incentive.

Here’s an example workflow. Rectangles are transactions and ovals are UTXOs. Color indicates who controls each thing: blue for a user, green for a bot, orange for the DEX contract.

protocol cluster_phase1 Phase 1: announce trades in parallel cluster_phase2 Phase 2: single-threaded batching auction cluster_phase3 Phase 3: finalize winning state transition Wallet1 Wallet1 UserWallet1 User1 posts trade Wallet1->UserWallet1 Wallet2 Wallet2 UserWallet2 User2 posts trade Wallet2->UserWallet2 Wallet3 Wallet3 UserWallet3 User3 posts trade Wallet3->UserWallet3 BotWallet1 BotWallet1 Batch1 Bot1 bids 2 trades, posts collateral BotWallet1->Batch1 BotWallet2 BotWallet2 Batch2 Bot2 bids 3 trades, posts collateral BotWallet2->Batch2 Wallet1p Wallet1 Wallet2p Wallet2 Wallet3p Wallet3 BotWallet1p BotWallet1 BotWallet2p BotWallet2 State1 State1 State1->Batch1 State4 State4 Trade3 Trade3 UserWallet3->Trade3 Trade2 Trade2 UserWallet2->Trade2 Trade1 Trade1 UserWallet1->Trade1 Trade1->Batch1 Trade2->Batch1 Trade3->Batch2 State2 State2 Batch1->State2 State3 State3 Batch2->State3 State2->Batch2 Finalize Bot2 applies all 3 trades, slashes Bot1 for omitting Trade3, rewards itself, distributes traded tokens State3->Finalize Finalize->Wallet1p Finalize->Wallet2p Finalize->Wallet3p Finalize->BotWallet1p Finalize->BotWallet2p Finalize->State4

Something like this should work for not only a DEX, but for any contract that needs someone to post a state transition and be assured that they include all the valid inputs. For example a concurrent auction contract could tip a bot for calling its close endpoint and gathering all valid bids at the end of the auction. (I imagine this would come up a lot in real auctions, since everyone would wait to snipe at the end)

The simplest way I can think of bootstrapping a generalized bot economy would be to have a cardano-batch-bot-contrib or similar repo where everyone posts code for operating a bot on their protocol, and bot operators choose which ones to include. Any stake pool operator (SPO) who wants some extra revenue could also operate a bot and customize it to run only the protocols they’re comfortable with.

Potential objections

Q: Is this too complicated or too slow to operate at scale?

A: I don’t think so. This protocol could probably be run on the main chain at least as fast as an oracle could come to consensus on price changes. Trades would be ordered by the slot they were submitted in, which is the same level of resolution a trivial “single-threaded” DEX would be capable of. And inside a Hydra head it could go orders of magnitude faster. Probably fast enough that users wouldn’t notice any delay at all! Finally, because cheating bots will always be caught, there should normally only be one bid.

Q: Would this introduce nondeterminism and miner-extractable value (MEV)?

A: It depends whether the DEX protocol is deterministic. Batching bots would probably end up being run by SPOs and the slot leader would be able to include their own batch transaction, but they would be unable to censor or re-order transactions unless the DEX contract + batching protocol allows it.

Q: Would batching bot operators be legally responsible for operating an order book, like what happened to EtherDelta?

A: I have no legal training whatsoever, but it seems to me that that should also depend on whether the protocol is deterministic. If so, bot operators don’t have any decision-making power to abuse and therefore don’t need to be regulated. The only choice they would have is whether to participate in the protocol at all or not. One could imagine situations where everyone might refuse to process money from a hack for example, but I think that would be better regulated at the DEX protocol level so everyone is clear on what counts as a legal trade beforehand. The founders, devs, or token holders might be responsible in that case.

Next steps

Lots of things would still need to be worked out. For example: