CoW：Batch AuctionとSolverの役割

---

目次

1. はじめに
2. SolverとBatch Auction
   　1. トレードの注文の定式化
   　　a. 売り指値注文
   　　b. 買い指値注文
   　　c. マーケットメイク（Liquidity Orders）
   　　d. 手数料
   　2. Batch Auctionの解と制約
   　3. Solverに支払われる報酬
   　　a. Per-Auction Rewards
   　4. Solverのビットと勝利期待値
3. おわりに
   参考文献

1. はじめに

このレポートでは、CoW Protocolが導入するバッチ・オークションと、Solverの役割について掘り下げて解説する。CoWはトレーダーの注文を一定の時間内で集めてバッチ処理し、フロントランニング（MEV）などの問題を軽減することを目指している。バッチ内の注文はSolverと呼ばれるエンティティが最適な配分を行うため、複数のトレーダーの利益を最大化しつつ、流動性の損失を抑えることが可能である。このレポートでは、Coincidence of Wantsの概念に続いて、Solverの仕組みとBatch Auctionの詳細を解説する。

2. SolverとBatch Auction

CoWにおいてトレーダーの発注はSolverがバッチを最適化してから、CoWのSettlementコントラクトで執行される。本章の目的は、Solverがトレードの執行のために解く流動性損失最小化問題に関する概要を次回以降のレポートのために説明することである。

まず、Solverとは、Batch Auction Instanceをインプットとして受け取り、Batch Auction Solution（各トレードの執行価格や執行量を決定）をアウトプットする主体である。各Solverの解はDriverにかけられ、トレーダーの効用が最も高くなる順番に注文が並べ変えられ、トレードの執行量や価格が決定される。

2.(1)トレードの注文の定式化

本節では、CoWの流動性損失最小化問題を定式化する前に、トレーダーの注文を定式化する。

トークンが {1,2,…,k} 種類存在すると仮定する。このとき、トレーダーの注文は集合 $S⊂\mathbb{R}^k$ と定義することができ、SolverにとってBatch Auction Instanceのインプットとなる。集合 S は正と負の値を持ち、正の値は購入するトークン量（購入トークン建て）を表し、負の値は売却するトークン量（売却トークン建て）を表す。トレーダーの効用を踏まえた場合、集合 S は $\mathbb{R}_+^k⊂S$ 及び $\mathbb{R}_-^k∩S=0$ となり、 $S$ は少なくとも1つは正の値を、1つは負の値を持つ。また、トレーダーの注文が執行されない可能性もあるので、 $0∈S$ も満たされるとする。Solverのアウトプットは効用関数 $U_S:S→\mathbb{R}$ で定義され、必ずBatch Auction Instanceに対し、数値を出力するものとし、その数値はトレーダーの効用を表すものとする。また、トレーダーが注文を発注していない状態は$U_S (0)=0$ となる。本レポートでは説明の簡素化とCoWの仕様に対応するため、ユーザーのトークンは $b$ （買う”buy”トークン）と $s$ （売る”sell”トークン）の2種類 $（k=2）$ のみ存在するとし、量をそれぞれ $x\in\{0,X\}$,$ｙ\in\{0,Y\}$ とする。

2.(1).a 売り指値注文

LOBにおける売り指値注文とは、指値価格 $π$ でトークン $s$ の最大売却量 $（Y>0）$ を定めるものである。CoWのプロトコル上で売り指値注文は、注文がトレーダー間で全て執行される場合（売却量は$Y$）、全て執行されない場合（売却量は 0 ）及び一部執行される場合（売却量は$Y$ 未満 0 以上）の3つの場合に分けられる。最初に、注文が全て執行されるもしくは全て執行されない注文（fill-or-kill）は

$$S=\begin{bmatrix} x \\ -y \end{bmatrix} s.t. \frac{y}{π}≤x\ and\ y∈\{0,Y\}\}$$

となる。次に、部分的に執行される（partially-fillable）注文は

$$S=\begin{bmatrix}x\\-y\end{bmatrix} s.t. \frac{y}{π}≤x\ and\ y∈[0,Y]\}$$

となる。このとき、双方の注文に対して効用関数は

$$U(x,-y)=(x-\frac{y}{π})p(b)$$

と定義される。上式において$(x-\frac{y}{π})$は売り指値注文が指値で売れた際に得られる余剰購入トークン量を表し、$p(b)$は購入トークンをヌーメレール建てで表している。そのため、効用関数はヌーメレール建てで非負となる。
CoWにおける売り指値注文の定式化により、partially-fillableの注文については文字通り、複数バッチにまたがってトレードが執行されることが示される。また、fill-or-killの注文については単一バッチ内で処理が執行されなければトレードが執行されない。

2.(1).b 買い指値注文

LOBにおいて買い指値注文とは、指値価格πでトークンbの最大購入量（X>0）を定めるものである。売り指値注文と同様に、買い指値注文は3種類の状態に場合分けされる。最初に、注文が全て執行されるもしくは全て執行されない注文（fill-or-kill）は

$$S=\{\begin{bmatrix}x\\-y\end{bmatrix} s.t.y≤xπ\ and \ x∈\{0,X\}\}$$

となる。次に、部分的に執行される（partially-fillable）の注文は

$$S=\{\begin{bmatrix}x\\-y\end{bmatrix} s.t.y≤xπ\ and \ x∈\{0,X\}\}$$

となる。このとき、双方の注文に対して効用関数は

$$U(x,-y)=(xπ-y)p(s)$$

と定義される。上式において$(xπ-y)$は買い指値注文が指値で売れた際に得られる余剰売却トークンの量を表し、$p(b)$は購入トークンをヌーメレール建てで表している。そのため、効用関数はヌーメレール建てで非負となる。売り指値注文と同様に、買い指値注文も複数バッチにわたって有効となりうる。

2.(1).c マーケットメイク注文（Liquidity Orders）

Liquidity Ordersとは、他のDEXやプライベートプールを利用した注文のことである。Liquidity Ordersが存在する理由は、Solverがバッチ・オークションに集められた売買の注文をCoWのユーザー間のトレードのみで突合して執行しきれない場合があり、その際には外部のDEX等に頼る必要があるからだ。Liquidity Ordersの集合は$L⊂\mathbb{R}^k$と定義され、効用関数は $U_L:L→0$となる。

2.(1).d 手数料

すべての注文には、プロトコルに支払う手数料が売却トークンで徴収される。手数料は任意のトレード $S$ に対する関数$f_S:S→\mathbb{R}_+^k$として定義でき、トレードがない場合には $f_S (0)=0$となる。

CoWプロトコルの運営上、手数料の決定されるタイミングはfill-or-killとparitally-fillableの注文によって異なる。fill-or-killの指値注文の場合、プロトコルが注文をあるバッチに入れる前に計算を行い、トレードの執行前に決まる。一方で、partially-fillableの指値注文については、Solverが手数料を計算することとなり、トレードの執行後に決まる。

2.(2) Batch Auctionの解と制約

SolverはBatch内の注文を並び替え、トレーダーの効用を最大化するBatch Auction問題を解くことによって、Solverは報酬を得る。本節では、[6]が提示する一般的なBatch Auctionにおける制約と、CoWでSolverがBatch Auctionを解く際の制約を説明する。
まず、バッチにユーザーが$I$人と外部流動性（DEXなどの流動性を提供する存在）が$J$個在る、と仮定する。Batch Auctionの解はトレードの組み合わせ$\{o_1,o_2,…,o_I,l_1,l_2,…,l_J \}$となり、$o$はユーザーの注文を、$l$は使った外部流動性の数を示す。このとき、Batch Auctionの解は下記の制限を受ける：

• 解に定められるトレード数：解における執行されたトレード数（$o$の数）と使った外部流動性（$l$の数）の数には最大値が決まっている。なぜなら、ブロックチェーンのブロックには記録できる注文数が決まっているから。
• 解は必ずバッチが参照できるプロトコルとトレーダーの注文から構成される：解として並び替えられたトレードは、バッチが参照できるトレーダーの注文と外部流動性を優先する。つまり、$o_i∈S_i, ∀i≤I, l_j∈L_j$及び$∀j≤J$となる。
• バッチ内の同じトークンの注文は均一の執行価格：全てのユーザーは実際にスワップがなされる（トレードが執行される）とき、同じ通貨に関する注文は同じ価格で執行される。CoWでは、これをRing-Tradeと呼んでいる。例えば、ユーザーiがトークン1を$x$個受取り、トークン2を$y$個手数料とともに売却したとし、スワップされる価格を $p_{1,2}=\frac{y-f_2}{x}$と定義する。また、同じバッチ内の注文に任意のユーザーがトークン2とトークン3をスワップし、$p_{2,3}$が定義できる注文が存在すると仮定する。このとき、 $p_{1,2} p_{2,3}=p_{1,3}$と循環法則が成り立たなければならない。つまり、2章の図3.において執行されるトレードの間ではトレード価格が統一となるように各通貨ペアの間で循環法則（Ring-Trade）が成り立つ。
• 売り指値注文はパレート最適：売り指値注文がパレート最適であれば、CoWを利用するトレーダーとその相手方の双方にとって注文の執行が最適な状態である。つまり、双方にとって効用がより高くなるような注文の執行方法はなく、CoWのトレーダーの売り指値注文は執行され、相手方の人の買い注文も執行される。
• トークンの総量は変化しない：Batch内に含められた注文のトークンは、増加・減少せず、一定となる。
• Social consensus rulesに則ること：Solverはコミュニティのルールに則って、解を作成する。つまり、上の4つの制限を守っていたとしても、モラルに反するような解答を提供することは軽減される。
  Social Consensus Rulesには下記のものがある。

Solverは上記の制限を満たした解を作成し、$p$を外部（オラクル）から与えられた通貨の価格だとすると

$$\sum_{o}U(o) +p\sum_{o}f(o)$$

として解の値は計算される。このとき、Solverの解は上記の式を最大化し、流動性の損失は最小化される。

4.(3) Solverに支払われる報酬

Social Consensus RulesのCIP-20に決められているように、Solverの報酬はper-auction rewards（オークション毎の勝利報酬）とconsistency rewards（前週のオークションで勝った回数に応じて毎週支払われる6か月に一度見直しのある報酬）に分けられる。また、Solverの報酬のうち、per-auction rewardsは$ETHもしくは$COW（CoWのガバナンストークン）で、consistency rewardsは$COWで支払われる。報酬についてはCoW DAO Proposals[7]で変更される可能性があるため、定期的に確認をする必要がある。

4.(3).a Per-Auction Rewards

本節ではPer-Auction Rewardsの報酬決定について解説する。
Per-Auction Rewardsはsecond-price auctionに則って決まる。まず、バッチ・オークションにおいてSolverは解としてトレードの組み合わせ$\{o_1,o_2,…,o_I,l_1,l_2,…,l_J \}$とスコアを提出する。バッチ・オークションに参加しているユーザーのうち、最も高いスコアを提出したSolverの解に従い、注文の執行が行われる。

このとき、Solverの報酬は下記のように

$$payment=cap(observedQuality-referenceScore)$$

定義される。このとき、$referenceScore$はバッチ・オークションに提出された2番目に高いスコアで、$observedQuality$はブロックの質を指す。ブロックの質のスコアには2種類あり、成功した決済にはCoWに支払われるユーザーの手数料の和とユーザーによる総余剰（total surplus generated by the users）して計算され、正の値となる。一方で、不採用のブロックの$observedQuality$は0となり、$payment$が負となりうる。

また、CoWに採用されるバッチを提出したSolverへの報酬は下記のように

$$cap(x)=max(-c,min(c+observedCost,x))$$

上限が決まっている。上式において、c=0.01ETHとなっており、$observedCost$はSolverが支払うブロックのトレードを執行する際のガス代である。また、Solverが提出するスコアは$successfulQuality$（ブロックのトレードが執行されるときの$observed Quality$）よりも小さくなることが求められる。ブロックのトレードが決済される際の$successfulQuality$は、先ほど述べたようにブロックの解によるtotal surplusと手数料の総和として計算される。一方で、ブロックのトレードがチェーンに加えられない場合、Solverは報酬を受け取れないどころか、cとガス代の量をプロトコルに支払う可能性がある。また、Solverにはトレードの執行時にスリッページが発生した場合には追加コストが発生する。
Per-Auction-Rewardsの支払はSolver受け取る通貨の種類が多くならないように、ETHもしくはCOWで支払われる。Solverが受け取る$min(payment,observedCost)$はガスの補償としてETHで支払われ、$payment-min(payment,observedCost)$はCOWで報酬が支払われる。

4.(4) Solverのビッドと勝利期待値

本節では、Solverがバッチ・オークションに勝利することで得られる期待値を計算する。
Solverはバッチ・オークションのビッドに対して$referenceScore$を$0<refernceScore<successfulQuality$の間で自由に決められ、確率$p$で勝利する、と仮定する。Solverがバッチ・オークションで勝つ際に発生するコストには、変動コスト$SC$と固定コスト$C$（勝利することと関係なく発生）が挙げられる。最高勝利収入の上限を無視して、以上を定式化すると

$$p(successfulQuality-SC)-referenceScore-C$$

となる。Solverがバッチ・オークションに参加し、勝利収入がコストを上回るときの最適スコアoptimalScoreは、

$$optimalScore=p(successfulQuality-SC)-C$$

と与えられる。勝利時の最高収入の上限を考慮した際の、Solverの期待収入は

$$p(max(-c,min(c+observedCost,successfulQuality - referenceScore)-SC)-$$ $$(1-p)min(c,referenceScore)-C$$

となる。Solverがバッチ・オークションに参加するとき、上式は$referenceScore$を変数とする期待収入に関する単調減少する式であることを踏まえると、$referenceScore$に対して上式は正の値を取る必要がある。Solverがバッチ・オークションで勝つためには、期待収入の式が0となるような$referenceScore$に近い値を提出することになることがCoWでは提案されている。CoWのドキュメント上書かれていないが、Solverが競争状態にあり、Solverに期待収入が残る状態はトレードがもたらす取引市場への利得の一部がSolverに流れてしまい、トレーダーの効用を下げてしまうからだと考えられる。

5.おわりに

本レポートでは、CoWのバッチ・オークションの仕組みとSolverが果たす役割について説明した。Batch Auctionによる取引メカニズムは、DeFiにおけるフロントランニング対策として有望であり、さらにSolverが最適化を行うことでトレーダーの効用が向上する。

参考文献

[6]：Geoffrey Ramseyer, Mohak Goyal et al. Augmenting Batch Exchanges with Constant Function Market Makers, arXiv.org, arXiv:2210.04929v5, 2023.
[7]：Snapshot Labs. “CoW DAO Proposals”. snapshot.org. 2023. https://snapshot.org/#/cow.eth, （参照：2023年11月5日）