💱 Any (marketable) pathfinding documentation?

[JFWooten4]

This is just a touch out of scope for my #723 timeframes. Briefly, pathfinding without route specification has a lot of under-the-hood mechanics. The present page only explains path-payment route options.

What problem does your feature solve?

Document the sheep-wheat exchange pathfinding logic. Users can confidently transact with more info on order matchmaking. I find it particularly important to explain how this works for market orders taking liquidity.

Namely, market orders are the most common for individuals uninformed about spreads or slippage. For an easy remittance payment, they offer the simplest instant transfer conversion. Regulators care a lot about fair execution, and I don’t like the growing alternative of private implementations which tend towards off-chain calculations.

What would you like to see?

To start, a page explaining the routing of offers which consummate in ClaimAtom responses. This could explain, e.g., the CAP-38 solo-pool path execution before worse offers. We could differentiate the DEX via further information about this in the dev docs.

Generally, the network's liquidity allows for a deep reliance on conversion, especially for native assets. But the present documentation doesn't get this point across. Perhaps we could move pathfinding logic into a standalone Encyclopedia > SDEX page referencing paths.

See also #944 in re consolidating liquidity documentation. There's already so much on transaction ordering fairness, as showcased in Straight Facts earlier this year. It'd be great to have equivalent detailed public information for order hopping.

What alternatives are there?

I'm mostly concerned with how validators treat unspecified trade routing, since users share the common goal of best execution. This doesn’t stand out in one sentence and subsection example on independent hops at Txs (specialized) > Path Payments. To reiterate the prescient words of a meaningful early developer:

Pathfinding is key for devs making wallets that support remittance payments. It's worth doing it right, since that's a central goal of Stellar.
— Tom Quisel

Some clients currently offload this to a custom implementation.¹ This is a lot of extra work to squeeze the most out of execution. Systems like these could serve as documentation inspiration.

Namely, I know Silence and Orbit work on contract-based best execution. We could have a page more geared towards community pathfinding solutions, explaining their open-source code. This would be a stark contrast from the protocol-level Horizon implementation now documented.

Footnotes

1. Looking at community members like @johansten who’ve been helping me further understand the nuances here 💜 and built their own Horizon comparison servers. 🧠 ↩

[johansten]

Since you referenced me, and my custom pathfinder, is that something you think could be used as a start? From what I remember that's about a page of code, the central parts. I have no idea what Horizon ended up using after they rewrote it, but I'm assuming a depth-first search, just as I used.

Starting with X amount of asset A as a source asset, trying to get to B:

1. You enumerate all assets you can trade to in one step, be it DEX order books, or AMMs.
2. For each asset in step 1, you calculate how much of this asset the trade gets you.
   • If you've encountered this asset before, and your total was higher then, move on to the next asset, because you already got here in a cheaper way, and continuing on this path is a waste of time.
   • If there's not enough liquidity, you stop, and move on to the next asset.
3. If the asset is B, record the path it took you to get here
4. Unless you've exhausted all the hops, go to step 1 but with this current asset as your source asset.
5. When you've enumerated all you can, your best path from A to B is the last path recorded in step 3.

Dumbed down a bit: you start trying all possible paths you can go from A, but you stop each path if there's not enough liquidity, or if you've been to an asset before and you got there in a cheaper way.

[JFWooten4]

Hi Johan,

Based on limited investigation, your implementation might just be the first custom pathfinding implementation. Pathfinding matters a lot in the traditional financial system—which perhaps you've seen firsthand with extractive conversion rates. Access to exchanges themselves is one main reason I’ve found increasing costs through middlemen over the years.

That’s the easy explanation: nobody can directly transact with each other sans brokers. But pathfinding is the more sinister hidden evil corrupting Wall Street and others. Given its significance and common misunderstandings, I’d sincerely appreciate your help continuing past efforts. 💜

Existing Limitations

I approach pathfinding from the perspective of traditional stock-market order routing. This is a really big problem.¹ What we have with the DEX stands as the only option distributed as a truly free market.

The root of problems across markets comes from capitalist competition for a public good and natural monopoly. The referenced study extensively finds that a single market for the stocks of the world would yield at least 20% lower effective spreads than a duopoly. Americans are all too familiar with two prominent competing firms, but much of the same can be said about private exchanges extracting rents abroad.

I really appreciated your help understanding the DEX last year. There’s no one I can think of across the ecosystem more adept at explaining the existing pathfinding than yourself. 💜 I know we saw some misunderstandings about the existing pathfinding in discussions at the end of last year in Global and a liquidity-incentive server, so how about helping clear things up for everyone?

Present Confusion

I regularly exchange with the government. Representatives and team leads sit at a crucial policy crossroads between centralized and decentralized exchange. We have a limited window to sway them towards the option that provides everyone with the freedom to access markets.

The core of existing routing happens through financial middlemen, as we know. These legacy for-profit firms can make money skimming off trades. Sometimes we see this as trading fees, and other times it's much more complicated.

One obvious conflict can be front-running, which we’ve seen abundantly on other chains. Briefly, this has always been a problem on Wall Street. And it’s still extracting wealth thanks to the insane complexity of exchange infrastructure.

Existing Regulations

The top American market maker is opening a new stock exchange just so they can make more money. This works because of nonstandard trade routing. By having more venues connected to their fiber-optic cables, the assholes can fuck you over nanoseconds faster.

The system is so bloated that the present regulations globally just can’t protect users from this exploitation. The governance is so difficult that the only choice is to leave everyone’s portfolios teetering on the trust of a select few enterprises—conglomerates with the same institutional interests who took everything from us when Nakamoto started up.

But here in Core, we have a solution which doesn’t serve the Rothschilds. A framework which favors efficiency, egalitarianism, and excellence at the highest technical standards. And, quite differently from even other “decentralized exchanges,” it’s a model poised to finally take away their choking reins.

Profit Center

Trust, especially in the SCP context, is super nuanced. Without proper safeguards, we risk centralization at the social layer. Now, imagine that quandary scaled to infinity for an established routing system.

That’s what Apes saw in 2021 when one agency disabled stock trading. This Establishment handled order routing for hundreds of brokers with more users than existing network accounts. In later Congressional investigation, they received no disciplinary action.

The exchange of one asset to another is so simple. Yet it’s the first place many companies exploit to profit off their customers. We are all too conditioned into paying fees which fundamentally conflict with using path payments everywhere.

Unbreaking Horizon

We can overcome our challenges paying for everyday items with real-world assets. 🧠 To make this happen, we’ll need Stellar protocol routing. This pathfinding holds the key to unlocking liquidity in the DEX.

I love everything about Horizon. It's bizarre to me that major blockchains don't have canonical API implementations. Briefly, I'm not a massive tech guy.²

But when I learned about APIs my first year of college, a whole new world of development opportunities unfolded right in front of my eyes. It was finally possible to build really interconnected things by using the open interfaces pioneered by dedicated engineers. I feel we have a unique opportunity to do the same, bringing masses of new energies into the network by offering permissionless, quality information about the incredible protocol.

Collaboration Opportunity

I've been working on the DEX and liquidity pool documentation page for a few months. In fleshing out the interfacing examples, it's become abundantly apparent that the present documentation does not explain core pathfinding. I find this problematic because the select few who understand these routing nuances wind up creating blocks full of failed swaps while they wastefully send circular conversions to themselves for an excess 1,500 stroops.

In discussion, @rahimklaber comments that "they made some changes to core to filter out some of the arb transactions. But a lot still go through" as notably protold by Orbit during the revolutionary Protocol 18 upgrades.

It is not clear what changes have been made over the years to get us to ExchangeV3, even if someone reads all the CAPs and community posts about fixes. See your own exceptional past work cleaning up DEX certainty as just one example of something every network user has to appreciate today.³ While it might not look like much, non-IEIF orders literally created our entire industry.

Given your experience, would you be ever so kind as to consider adding a page for pathfinding? At the risk of oversimplifying things, you can just create a new file with your thoughts like in #1496. In past discussions, it's become clear to me that you have such a unique ability to explain complex topics succinctly, and I can think of no more hazy topic throughout the developers' site which urgently needs new clarification.⁴

Footnotes

1. While this video focuses on the American market where I work, the problem is just as bad everywhere else on the planet. And for the countries not fortunate enough to have a central stock exchange, we see the horrific effects of malinvestment and unfunded innovation. I think it'd be cool if the whole world was on the same playing field when it comes to entrepreneurial creativity, the core tenet of a marketplace for capital. ↩

2. I remember trying to learn HTML and CSS in high school through online courses. I was so bad at it that I'd stare at coding screens for hours just to get simple headings to render. And don't even get me started on the number of hours I've spent troubleshooting Truffle, literally just to compile code. ↩

3. Notably, Jed suggests offloading order book cleanup to service providers processing information updates which are "expensive to prevent." We have seen this same argument made for native pathfinding, and I would suggest community members contemplating routing services ask themselves what might happen to the remarkable existing liquidity if all users had to use "StellarBroker.com" Inc. I love the debiting DEX stability we uniquely enjoy. ↩

4. See, e.g., how Tyler believes "path payments to be one of the most interesting and important aspects of the Stellar blockchain." Even your own past work with Stargazer dove into the details at a level uncommon throughout network applications. 🚀 See also the core team referencing path payments as a means to implement FoK orders common in institutional adoptions of market-making algorithms. ↩