CosmosアビトラBotの作り方 その３【コード付き】

前回の続きです

各トークンのDecimals(小数点以下の桁数)を取得する

さて、前回の記事でプールの情報からスポット価格を算出できそうということは分かりましたが、これをこのまま使うことはできません。なぜかと言うと、それぞれのトークンのDecimals(小数点以下の桁数)が異なってくるからです。

例えば、Decimalが6のOSMOトークンの本当の価格はプールから得られた価格を$10^6$で割って得られることが出来ます。

では、このDecimalsの情報はどこで手に入るかと申しますと、osmosisの公式githubに上がっております。今回はこれをうまいこと整形して{denom:decimal}のような辞書を作ってみましょう。

以下にPythonのコード例を貼っておきます。

import json

with open('osmosis-1.assetlist.json') as datafile:
    data = json.load(datafile)

decimals = {d["denom_units"][0]["denom"]:d["denom_units"][-1]["exponent"] for d in data['assets']}

with open('decimals.json',mode="w") as datafile:
    json.dump(obj=decimals,fp=datafile)

こうしてできたjson形式のファイルをGoで読み込みます

func GetDecimalMap() map[string]int {
	decimalMap := make(map[string]int)
	raw, _ := ioutil.ReadFile("./decimals.json")
	json.Unmarshal(raw, &decimalMap)

	return decimalMap
}

各トークンをナンバリングする。ついでに諸々

これは別に必須事項ではないですが、アルゴリズムを扱う際に各トークンにナンバーを振った方が良いので振っておきます。ついでに、後で使う機能もディクショナリにしてまとめておきます。

priceMap

その１の記事で扱ったGetActivePools()という関数を見てみると、Priceという変数があるのが分かります。このPriceとは何の価格かと申しますとCoinGeckoのオラクル価格です。後々使うことができるかもしれないので取っておきます。

type PoolCandidates struct {
	Symbol string  `json:"symbol"`
	Denom  string  `json:"denom"`
	Price  float64 `json:"price"`
	Fees   string  `json:"fees"`
}

instrumentMap

コインをナンバリングします

vertices

コインのナンバーの集合です

func getInstrumentDictionaries(pools map[int][2]PoolCandidates) (map[string]float64, map[string]uint, []uint) {
	//モジュール内でよく使うマップ群。
	//PriceMapは各コインの対ドルでのプライス（オラクルはCoinGecko)
	//InstumentMapは各コインにナンバーを割り当てたもの。ベルマンフォード法で使用
	//Verticlesはコインナンバーの集合(Set)。ベルマンフォード法で使用

	priceMap := make(map[string]float64)

	for _, pool := range pools {

		priceMap[pool[0].Denom] = pool[0].Price
		priceMap[pool[1].Denom] = pool[1].Price

	}
	instrumentMap := make(map[string]uint)
	vertices := []uint{}

	var i uint = 0
	for k := range priceMap {
		instrumentMap[k] = i
		vertices = append(vertices, i)
		i = i + 1
	}

	return priceMap, instrumentMap, vertices
}

これで一旦はプールの情報を扱う上での準備が出来ました。

ベルマンフォード法

さて、アービトラージの本題に入ります。 今まで取得してきた情報を見てきて分かります通り、DEXには様々なプールが存在し、絶えず取引が行われています。それぞれのプールでイベントが起こる度にプール内に存在するトークンのバランスは変化し、それによってトークンの交換比率(価格)も変わります。大きな取引が生じれば、それだけトークンの価格へのインパクトも大きくなり、裁定機会が生じる頻度も上がります。例えば、OSMO→ATOMの交換比率が他の市場に比べて有利になった時、OSMOをATOMに交換し、そのATOMをATOM→JUNO→OSMOのように再度両替すれば、元々持っていたOSMOの量より交換後のOSMOの量が増えるというようなケースが考えれます。こういったOSMO→ATOM→JUNO→OSMOの交換によって儲けるような仕組みを 三角裁定 と言います。そして、この三角裁定を同一トランザクション内で行うことを業界用語で Atomic Arbitrage ということがあります。

では、OSMO→ATOM→JUNO→...→OSMOのように交換したときにOSMOの量が増えるような経路を見つけるには、どうしたら良いでしょうか。こういった場合に有効なのがベルマンフォード法のようなグラフアルゴリズムです。

問題を一般化しましょう。それぞれの通貨の交換レートを$w_1,w_2,w_3 ...$とした時、我々のゴールは$w_1 w_2 w_3 ...w_n > 1$となるような経路を見つけることになると分かります。

この式を少し変形して、

$$w_1 w_2 w_3 ...w_1 > 1$$ $$\Leftrightarrow \log{w_1} + \log{w_2} + \log{w_3} + ... + \log{w_n} > 0$$ $$\Leftrightarrow (-\log{w_1}) + (-\log{w_2}) + (-\log{w_3}) + ... + (-\log{w_n}) < 0$$

この最後の式のように一周して重みがマイナスになるようなパスを負の閉路と言います。ベルマンフォードアルゴリズムを使うことでこの負の閉路を見つけることが出来ます。

---

補足

ベルマンフォード法はアービトラージの経路探索において計算効率もよく、最も一般的な方法です。しかし、DEXにおけるアービトラージにおいては深さ優先探索(DFS)を使うことも考えられます。AMMではスワップするトークンの量によって得られるトークンの量も変わってくるため、トークンの交換レートを一定として計算するベルマンフォードでは最適とは言えない場合が出てくるためです。DFSやベルマンフォード法の他にも、Dexのアービトラージに特化したアルゴリズムも開発されていて、より効率の良いアルゴリズムを見つけることは熾烈な競争となっています。

---

ベルマンフォード法の説明はググれば山ほど出てくるので、それら先人たちの記事にお任せします。 (wikipedia)

algorithmsという新しいディレクトリを作り、その中にbellmanford.goというスクリプトを作りましょう。ここでベルマンフォード法を定義して行きます。 以下は負の経路を探索してアービトラージの機会を探知するGoのコードの一例です。

package algorithms

import (
	"math"
)

type Graph struct {
	edges    []*Edge
	vertices []uint
}

type Edge struct {
	From, To uint
	Weight   float64
}

func NewEdge(from, to uint, weight float64) *Edge {
	return &Edge{From: from, To: to, Weight: weight}
}

func NewGraph(edges []*Edge, vertices []uint) *Graph {
	return &Graph{edges: edges, vertices: vertices}
}

func (g *Graph) FindArbitrageLoop(source uint) []uint {
	size := len(g.vertices)
	distances := make([]float64, size)
	predecessors := make([]uint, size)
	loop := make([]uint, size)
	indices := make([]uint, size)
	exists := make([]bool, size)

	for _, v := range g.vertices {
		distances[v] = math.MaxFloat64
	}
	distances[source] = 0
	exists[source] = true

	for i := 0; i < size-1; i++ {
		changed := false
		for _, edge := range g.edges {
			newDist := distances[edge.From] + edge.Weight
			if newDist < distances[edge.To] {
				distances[edge.To] = newDist
				predecessors[edge.To] = edge.From
				changed = true
			}
		}
		if !changed {
			break
		}
	}

	for _, edge := range g.edges {
		if distances[edge.From]+edge.Weight < distances[edge.To] {
			loop[0] = source
			next := edge.From
			var index uint = 1
			for {
				loop[index] = next
				if exists[next] {
					return g.reverseSlice(loop[indices[next] : index+1])
				}
				indices[next] = index
				exists[next] = true
				next = predecessors[next]
				index++
			}
		}
	}
	return nil
}

func (g *Graph) reverseSlice(slice []uint) []uint {
	reversed := make([]uint, len(slice))
	for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
		reversed[i], reversed[j] = slice[j], slice[i]
	}
	return reversed
}

次回の記事ではこのコードを用いて実際にベルマンフォード法を実行して行きます。

---

その１

その２

その４