Learning #4: A Side Project, Path Payment Arbitrage on Stellar

With some free time this weekend, I decided to test out something I had seen circling around the Stellar world a month or two back, path payment arbitrage. To start, I’ll explain the basics.


Path Payments

Path Payment Diagram

Stellar is a decentralized network that facilitates the transaction of various digital asset across the internet via distributed ledger, or blockchain technology. Stellar transactions are made up of numerous operations which change the state of the global ledger. The simplest operation is a payment, an operation that moves some asset from an account Alice to an account Bob.

Another operation is an offer, a create/modify/delete entry into the Stellar distributed exchange’s orderbook. Unlike most other DLT’s, Stellar not only maintains a ledger of transactions, but also a ledger of orders. Thus, in fancy blockchain terminology, Stellar has a built-in DEX.

Utilizing this DEX, we get a more complex operation, a path payment. Let’s say Alice wants to send Bob 10 USD tokens, but Alice only holds BTC. There may not be a market between BTC and USD, so in any other crypto ecosystem, Alice would need to exchange BTC for XLM (the native Stellar Asset and the most common medium of exchange) and then exchange her XLM for USD. Since this is such a common operation, Stellar came up with the Path Payment that basically does all this for the user. A Path Payment is an operation that allows Alice to Send Bob whatever asset she wants (Destination Asset) using whatever asset she holds (Source Asset). To quote the Stellar Documentation ” A path payment specifies a series of assets to route a payment through, from source asset (the asset debited from the payer) to destination asset (the asset credited to the payee).”

There is some built-in support to find these paths of liquidity using Horizon, however it is pretty basic and more complex path finding is left to the intrigued developer.


Arbitrage

Arbitrage Image

To quote Wikipedia “in economics and finance, arbitrage is the practice of taking advantage of a price difference between two or more markets: striking a combination of matching deals that capitalize upon the imbalance, the profit being the difference between the market prices.”

Basically, by finding inefficencies in the market, you can take advantage and make small amounts of profit. This is not cheating the market, but instead an act of more or less balancing everything out.


Breadth-first Search (BFS)

BFS Diagram

BFS is a graph traversal algorithm to discover any and all paths between two nodes in a graph. The algorithm basically visits every node’s neighbors and then neighbor’s of neighbors whereas Depth-first Search (DFS) search’s a single path to completion before search the node’s next neighbor. Since graphs (unlike trees… although trees are graphs) have cycles, we must keep track of the nodes we have visited, or else we will end up in an infinite loop.

The basic algorithm (imperative) is:

// define start values
visited = []
paths   = []
START   = some node
END     = some node

// define a recursive function
function bfs (visited, current_path, node):
    add node to visited
    add node to current_path

    if (node == END):
        add current_path to paths

    else:
        for every neighbor of node:
            if neighbor is not visited:
                bfs(visited, (copy)current_path, neighbor)

// call bfs on start values
bfs(visited, [], START)

Path Payment Arbitrage

My goal here was to search for paths such that I would end up with more of a given asset A than I started with; I was searching for a path from some asset A back to itself and looking for an opportunity to arbitrage.

Basic Algorithm

To do this, I first booted up a Stellar-core instance. Once the core node connected and synced with the network, I then had a postgres database filled with the current state of the Stellar orderbook. From here I constructed a graph of all assets to other assets, where edges represented a sell order to a buy order (all orders on the Stellar network are sell orders). Once I had this, I calculated all the paths from every asset to itself. With all the paths, I then simulated filling each order backwards, starting with varying amounts of each asset to see if I could start with less than I ended with (this is how Stellar-core does path payments). Finally, I displayed the results (ideally this would be programmed to automatically execute trades).

An example output looks like this:

__________ ARBITRAGE at 0.0001 asset amount __________

Path #1 cost per 0.0001 = 0.00001342894736842105 USDF2U
1. CLUB : GDH2X4FLGF4JL3XLL6DOFNUIQMDBQ2HNCZT45A6VMXUQSXO3WAMBZNZ2
2. XLM : native
3. F2UPAY : GBH5RZC6JGIPT34ZEPXJNEVL6KZGEBD7QBAQ636VEHZDGHFVF4L32WHN
4. USDF2U : GBEL3DHNP6STJSK7S2XJM66BHSO6KTWSJM5GJGJ3YFV7FJE4U7SY2OWZ

Path #2 cost per 0.0001 = 0.00009139033753473609 BOT
1. OLA : GDH2JM2IR63ZJBXDQDIW4HUEYW65X5JLXLNLUSTUPXTG3H7W6JALEPHW
2. XLM : native
3. BOT : GBBBFR3WP5JY272TUM4J5Z3HY2FSRNWSWKUQMSPWZC2EL6RT2KWJW2MC

Path #3 cost per 0.0001 = 0.00009139033753473609 OLA
1. XLM : native
2. BOT : GBBBFR3WP5JY272TUM4J5Z3HY2FSRNWSWKUQMSPWZC2EL6RT2KWJW2MC
3. OLA : GDH2JM2IR63ZJBXDQDIW4HUEYW65X5JLXLNLUSTUPXTG3H7W6JALEPHW

---------------------------------------------------------

Stellar Path Payment Finder (PPF)

Since I do not have the liquidity to perform a profitable arbitrage campaign, and I am also more interested in feedback at this point than making a few extra lumens, I have open sourced this side project. I think this may be the beginning of some interesting path payment and/or orderbook analysis and will lead to some interesting realizations about the state of offers on the network.

The code is availible on my Github.

Click the link GIF


Note: none of the images are my own. See the source for links.