Decentralising CoW solver auctions using pod network

[_shresth]

Cow protocol currently conducts an off-chain auction, where external parties, known as solvers, apply different strategies to propose competing solutions.

Currently, the autopilot service is responsible for maintaining the order book and arbitrating the solver auctions. It maintains all the user orders, invokes the solvers at the auction start, collects solutions (bids) by solvers, chooses the solution that maximizes the score, and informs the relevant solver to settle on-chain.

The autopilot service represents a single point of failure for the entire CoW protocol. Users and solvers must trust it not to censor orders and solver bids, as a malicious service could compromise auction safety without being held accountable. Furthermore, CoW Core, the entity responsible for operating and maintaining this service, faces potential legal and compliance risks in the evolving regulatory environment.

In this proposal, we provide the first practical step towards decentralisation. We propose moving the solver auctions to use pod network. pod is a programmable L1 that is designed to conduct real-time censorship-resistant auctions. The proposed design enables extending the system further to decentralize the order book, which would eliminate the need for the autopilot service.

Existing solutions do not work.

Informally, conducting auctions requires that users be able to:

(i) bid until the deadline;

(ii) fetch the set of bids after the deadline and find the winner locally.

The order of bids is irrelevant. The auction protocol should be fast to operate intra-block and with a minimal latency overhead, maximizing the time available for solvers to compute optimal solutions.

Existing primitives either do not provide the required interface or are not efficient:

1. Decentralized Storage and Data Availability systems cannot enforce the auction deadline.
2. Consensus Protocols (existing Blockchains): Consensus protocols (Blockchains) require several rounds of communication, making them slow for conducting inter-block auctions. Consensus protocols are also prone to short-term censorship. L2s rely on a centralised sequencer, which would not provide any improvement over the autopilot.

For more information, read our blog post on why blockchains are a bad fit for fast auctions and our report evaluating potential solutions to decentralize the Flashbots PBS auction.

Overview

pod is a programmable layer-1 primitive designed to facilitate censorship-resistant real-time auctions. pod finalizes transactions in a single network round-trip (<150ms), validating each transaction completely independently, maximising parallelism. Unlike consensus protocols, pod does not totally order transactions, which is an acceptable trade-off for auctions, but is necessary to achieve this level of efficiency.

For CoW auctions, we implement optimistic single-shot transparent auctions. These auctions take place on a CoW pod subnet but settle on the original network where the liquidity lives, such as Ethereum.

Protocol. Bidders submit their bids through the auction contract on pod, subscribe to the network for other bids, and the auction deadline. The network notifies the bidders that the deadline has passed, and no new bids can be confirmed for this auction. The bidders then look at their local bidset, and the winning bidder declares their victory optimistically by executing their proposed solution on-chain.

Since there is no strong consensus, participants may occasionally see different sets of bids and identify different winners. However, this can only occur if some bidder misbehaves—in which case they are held accountable and their stake is slashed on Ethereum. Similarly, if a winning bidder fails to declare their victory, they can be held accountable and slashed.

Check out the single-shot auction paper for the detailed pseudocode and analysis of the construction.

Rollout. Initially, the pod system will run in addition to the centralised auctioneer and only log its results (shadow-mode). This allows to measure the latency of the new system and simulate that the behaviour is indeed identical to the current auction. Over time, the winner selection can gradually move from the autopilot to pod. Note that this will need a CiP, requiring all solvers to update their drivers to post their bids on pod. There will be a canonical implementation for a pod-compatible driver, but solvers will also be able to implement their own. Optionally, the current autopilot will be able to act as a circuit breaker that observes pod and the L1 chain, and performs accounting and emergency interventions in the case of misbehaviour.

Staking & Gas. The pod-cow subnet will use the top n (~60) addresses that have staked COW tokens in a staking contract as the active validator set. Solvers are expected to pay gas in ETH for bidding in the network. This amount can be 0 in the shadow mode.

Auction Flow

1. Auction starts: Autopilot announces a new batch of orders and provides a deadline for solutions.
2. Solution submission: After the driver calculates a solution, it submits a transaction on pod that calls submitBid function on the auction contract and receives a certificate that the solution was included. Solutions must reach a supermajority of the pod validators before the auction deadline.
3. Waiting for other solutions: The solvers subscribe to pod with eth_subscribe RPC to receive bids. The solvers also subscribe to a custom event pod_pastPerfectTime(auction_deadline). After this event, the protocol ensures that no new bids can be confirmed.
4. Computing the winner: The solvers look at the local set of bids they have received so far, and compute the maximum.
5. Settlement: The solver with the highest bid announces themselves as the winner on the settlement contract, providing proof that he submitted a bid on time.

Dispute resolution

As in the existing autopilot-based auction, the settlement contract allows a solver to claim that he is the winner. In order to make the settlement efficient in the case of no misbehaviour, this claim is not immediately verified by the smart contract. Instead:

1. If a bidder falsely claims to be the winner without being the highest bidder, any party can show a higher bid that was confirmed on pod to slash the false winner.
2. If a bidder wins the auction but does not show up, any party that has seen the winning bid being submitted on pod can slash the winner.

The dispute resolution smart contract leverages transaction confirmation certificates generated by pod which are efficiently verifiable on-chain.

Check out the auction paper for the complete pseudo-code and auction analysis.

References

1. Proof of concept integration that provides a foundation for the first milestone: Comparing cowprotocol:main...podnetwork:feat/pod · cowprotocol/services · GitHub
2. Documentation for the pod devnet: https://docs.pod.network
3. Similar integration, using pod for PBS auctions for Flashbots’ rollup-boost stack: pod-sdk/examples/optimism-tx-auction at main · podnetwork/pod-sdk · GitHub
4. pod auction explorer: https://explorer.pod.network

[AndreaC]

Hi @_shresth,

Thanks a lot for the write-up! The discussion on how to decentralize CoW is long overdue, and it’s exciting to see that we can utilize the new primitives introduced by POD to achieve this.

One of the advantages of what you describe is speed: each bidder sends its bid to each validator and then asks each validator for the list of bids it has received, and that’s it. Let me therefore start by discussing the speed requirement for CoW Auction. Assuming 12-second block time, 2 seconds for the winner to submit its transaction on-chain, a solid 8 seconds for solvers to compute their solution, that leaves 2 seconds for the auction to run. Which means that we don’t need the minimalistic setup described in the paper, and we could theoretically introduce additional communication rounds.

And I’m afraid that those additional communication rounds may be necessary. Reason #1 is that the auction is combinatorial: each bidder submits multiple bids, and there can be multiple winners. Hence, you need an agreement on the entire set of bids to figure out the auction’s winners. There are, therefore, additional attack vectors. For example, a malicious bidder could make two honest bidders believe that they won the same order. I don’t think the protocol described in the paper has any way to detect and react to such malicious behavior. There is also the possibility of a “partial no show” where some but not all winners settle on the target chain. Again, I don’t think the system can detect such behavior.

I’m not a consensus expert, but it seems to me that introducing an additional communication round may help. As an example, suppose bidders submit their bids, which are signed by validators (BTW, at this step, bids could also be hashed). Then each bidder collects 2f+1 signatures from validators to create a “confirmed bid” (if the initial bid was hashed, a confirmed bid is the hashed bid signed by validators plus the bid in the clear). Then the protocol continues as described in the paper, with “bids” replaced by “confirmed bids”. Note that, now, an attacker who wants to create uncertainty about the bid set needs to send its bid to at least 2f+1 validators and then share its “confirmed bid” to fewer than 2f+1, which implies that at least 1 honest validator observed the bid but not the confirmed bid, which could become a slashable offense.

Another reason I believe additional communication rounds may be necessary is the order book. The paper is a bit unclear on this point. However, from a game-theoretic viewpoint, a competitive auction requires common knowledge about the object being auctioned off. That is, it is not enough that each bidder knows what is being auctioned off; they also should know that all other bidders know what is being auctioned off (else a bidder may bid low believing that they are the only bidder); they also should know that all other bidder know that all other bidder know what is being auction off, and so on. (Common knowledge is a bit of a strange concept, but when you think about it, it is at the heart of many types of social interactions. If you want to know more, see here).

Achieving higher-order knowledge seems to me intimately related to the different rounds of communication in a consensus protocol, in which validators sign that they know something, then sign that they know that other validators know something, and finally, sign that they know that other validators know that other validators know that other validators know something.

Long story short: I believe introducing additional communication rounds may also help create higher-order knowledge about the new orders in the orderbook and make the auction more competitive.,

[_shresth]

Hey @AndreaC - Thanks for the detailed feedback. Both combinatorial auctions and orderbook work with the Octopod construction proposed above.

Combinatorial Auctions

The above proposed construction extends naturally to combinatorial auctions. The bidding phase allows for multiple bids from the same bidder. After the deadline, when the bidder reviews the bid set, instead of just calculating the maximum bid, they apply the same algorithm as used by autopilot with combinatorial auctions to determine the winners (multiple). If you are a winner on a single or multiple bids, you optimistically go on-chain and settle. There are still only two possible dispute cases:

1. A bidder who maliciously claimed himself as the winner. You can show another bid that should have won the partial or the complete batch to slash him.
2. A winning bidder who doesn’t claim himself as a winner. Anyone who has seen sufficient attestation on this bid can use it to slash him.

User Orderbook

The Octopod already handles user orders and is discussed in Appendix Section A of the paper. The frontend locks stake in the protocol to ensure that user orders are submitted to the batch within the batch deadline. If all frontends behave honestly, all solvers will always see the same set of orders and have the knowledge that all other solvers see the same as well. If a solver proposes a solution that uses an order that wasn’t seen by any solver, they can dispute, in which case the frontend would have shown the certificate or will get slashed.

Final Thoughts

The paper presents a simple construction that is easy to understand and analyse. pod itself is programmable and allows for arbitrary smart contracts. For example, we could implement the two-round construction you described above by simply performing two transactions on the pod: one to bid and another to confirm the bid. Of course, we would have to understand if that provides any additional benefits over the single-round construction.

Lastly, we propose a design that not only works for Ethereum but also for CoW protocol deployments in other faster networks, and potentially for faster future Ethereum. Therefore, we assume that the auction duration should be as low as possible to be future-proof.

[AndreaC]

@_shresth

There are still only two possible dispute cases:

1. A bidder who maliciously claimed himself as the winner. You can show another bid that should have won the partial or the complete batch to slash him.
2. A winning bidder who doesn’t claim himself as a winner. Anyone who has seen sufficient attestation on this bid can use it to slash him.

Here is an example that I don’t think fits in these two cases. There are three solvers and two orders. Solver 1 bids on orders [a, b], and Solver 2 bids only on order [b]. The third solver behaves maliciously and, in collaboration with the malicious validators, convinces Solver 1 that it didn’t produce any meaningful bid, and Solver 2 that it made a great bid on order [a]. You can produce values such that solver 1 is convinced to have won both orders, while solver 2 is convinced to have won order [b]. There is ambiguity wrt who should settle order [b], but, importantly, neither of the two solvers claiming to be the winner of that order is malicious, and slashing one of them doesn’t seem to work as deterrent.

[AndreaC]

BTW, I don’t want to sound negative: I believe that decentralizing CoW Auction using Pod would be a super positive development for the protocol. I just think that more research is needed before your proposal can become actionable (for example, by turning it into a CIP)

[_shresth]

@AndreaC thanks for the example!

The protocol needs a slight massaging to make it work for the combinatorial auction. The trick is that a winning bid settling on-chain must submit other winning bids (or their commitments) that together make up the complete winning solution in their local view. If some of the winning bidders didn’t show up to settle on-chain, they should be slashed. This way protocol still ensures that either someone malicious is slashed or the protocol terminates with the correct result.

So in your example, there will indeed be a race condition in case of a malicious solver 3:

1. Solver 1 settles on-chain first. This is the highest honest complete solution. No one is slashed.
2. Solver 2 settles on-chain first with a commitment that solver 3 is part of the winning bidder set. Solver 3 is slashed as it can’t present a valid certificate.

We will update the document to reflect the extension to combinatorial auctions. We will also take a look if adding an additional round of communication might avoid this race condition.

I agree with you that this is the first step. We are excited to improve the protocol to get it ready for the CiP stage. We appreciate all the constructive feedback so far.