Pathfinding bug

[s-a-y]

I believe there is a bug in horizon's pathfinding mechanism.
I was playing with different paths, trying to find if there are arbitrage opportunities within stellar network, for example BTC -> XLM -> EUR -> BTC would give me >1.

Strangely, using paths endpoint I came across the path 0.0085936 BTC -> XLM -> 0.01 BTC, which doesn't make any sense, as there can't be negative spread in BTC <-> XLM trading:
paths request

{
        "source_asset_type": "credit_alphanum4",
        "source_asset_code": "BTC",
        "source_asset_issuer": "GAUTUYY2THLF7SGITDFMXJVYH3LHDSMGEAKSBU267M2K7A3W543CKUEF",
        "source_amount": "0.0085936",
        "destination_asset_type": "credit_alphanum4",
        "destination_asset_code": "BTC",
        "destination_asset_issuer": "GAUTUYY2THLF7SGITDFMXJVYH3LHDSMGEAKSBU267M2K7A3W543CKUEF",
        "destination_amount": "0.0100000",
        "path": [
          {
            "asset_type": "native"
          }
        ]
      },

Then I tried to execute such path payment, result is quite predictable

{
  "type": "https://stellar.org/horizon-errors/transaction_failed",
  "title": "Transaction Failed",
  "status": 400,
  "detail": "The transaction failed when submitted to the stellar network. The `extras.result_codes` field on this response contains further details.  Descriptions of each code can be found at: https://www.stellar.org/developers/learn/concepts/list-of-operations.html",
  "instance": "horizon-002c/3HJtFtsszk-59460857",
  "extras": {
    "envelope_xdr": "AAAAAGO4y1nX/lJHn/OKct4JirEoX5n922d7oG7g+NANoCQGAAAAZAC3JiEAAAPZAAAAAAAAAAAAAAABAAAAAAAAAAIAAAABQlRDAAAAAAApOmMamdZfyMiYysumuD7WccmGIBUg0177NK+Ddu82JQAAAAAAAU+xAAAAAGO4y1nX/lJHn/OKct4JirEoX5n922d7oG7g+NANoCQGAAAAAUJUQwAAAAAAKTpjGpnWX8jImMrLprg+1nHJhiAVINNe+zSvg3bvNiUAAAAAAAGGoAAAAAEAAAAAAAAAAAAAAAENoCQGAAAAQMdg8+un6caBH2yNF9sreG/7cgSly1qcthn0n4pnlASu0gFKE6qPnIyP9agoyyfbylNtlewRBWjciPX00dB/Mg8=",
    "result_codes": {
      "transaction": "tx_failed",
      "operations": [
        "op_over_source_max"
      ]
    },
    "result_xdr": "AAAAAAAAAGT/////AAAAAQAAAAAAAAAC////9AAAAAA="
  }
}

With that in mind I have also many cases, when path payments fail for PapayaBot users with op_over_source_max even when I add 0.5% on top of sending amount. Especially for small amounts, for example you can't make path payment BTC -> 1 XLM, it always fails

Please check

[s-a-y]

Can that be prioritized in some way? Can't stress enough how important that is, double digit percent of all path payments in my setup can't be completed because of that bug

[s-a-y]

Fresh

[MonsieurNicolas]

This was probably made obsolete by the combination of the addition of liabilities and rounding fixes in path payment

[s-a-y]

It was definitely still the case after rounding fixes. But I haven't done any testing after protocol v10 kicked in. I'll post here if I can find anything within 48 hrs, otherwise feel free to close the issue. Looks much better at the moment from the first glance.

[bartekn]

I also couldn't find anything obvious, but I'll add more tests to simplepath package next week while working on #685 so hopefully will find a bug (if there is any).

[bartekn]

I finally had more time to debug simplepath package. I think that the issue described in the first comment (#324 (comment)) can still happen because path finding does not run in a DB transaction. So if there's a new ledger with trades updating affected order books during a search you may see negative spreads etc. The results were improved by #508 but it still can happen if the change in price between ledgers is bigger.

#324 (comment) looks like a rounding issue fixed in V10. Horizon release with these changes was released in September so after your comment.

There are big improvements possible with very little dev time needed in the current algorithm:

• Not searching for Destination Asset -> X -> Destination Asset paths as it doesn't make sense.
• Not searching for A -> B -> A -> Destination Asset paths as you will always have less A after exchanging B to A (popular case when A is XLM as there are a lot of XLM markets and every source account has XLM). Many search results contain even 10 paths (50% as max is 20) like this!
• Limiting number of results: 20 is way too much.

I hope to submit a PR with the changes tomorrow.

[s-a-y]

Thanks, awesome.
20 is not too much. Let's say I have 30 trustlines
GBR3RS2Z277FER476OFHFXQJRKYSQX4Z7XNWO65AN3QPRUANUASANG3L

how can I find specific path A -> ... -> B if I can't see all options? There is a need for a way to specify outgoing currency then or pagination mechanism (complicated).
Of course in most cases right now I'm satisfied with A -> XLM -> B path, but that's just because there is no strong USD asset on the network, and I still need it to be present to estimate amounts.

I have this workaround for a long time, where I use special 30 accounts with 1 trustline, just to estimate paths and force user to choose outgoing asset beforehand. I was thinking I can get rid of it, because now it returns 1 path per asset, which is better than before, but I guess workaround stays, as I won't be able to list all paths.

[bartekn]

PR ready: #719

[bartekn]

New path finding algorithm (#719) has been deployed to https://horizon-dev-pubnet.stellar.org/ (you can test it using Laboratory too!).

Please check it out and let me know if it's better. @s-a-y if you could switch to it temporarily in your app and check if the returned paths are better I would be grateful.

[s-a-y]

Thanks, I'll give it a try

[bartekn]

It's been a week. Has anyone checked the new results in path finding endpoint?

[tomquisel]

Just checking in @s-a-y, is this still a major pain point for you?

[s-a-y]

@tomquisel I believe this bug is resolved, haven't seen it in a while.
lack of pagination or ability to specify sending currency is still an issue for me.

https://stellar.expert/explorer/public/account/GBR3RS2Z277FER476OFHFXQJRKYSQX4Z7XNWO65AN3QPRUANUASANG3L
PapayaBot account now has 50 trustlines and I need to add another 50, have been delaying it

[tomquisel]

That's great to hear! I'll close this issue. Feel free to add issues describing what you'd like to see for pagination and specifying sending currency, and we'll look into them.