[Pricegraph] Implement Orderbook "view"

[fleupold]

We are currently using the js based "transitive orderbook" logic to visualize the orderbook in the frontend (cf. https://mesadev.eth.link/#/book)

The problem with this is that it takes up to 10s to load. The graph based system is already superior for price estimates. The goal of this issue is to also use this approach to display the orderbook (list of pairs of price and available volume at that price).

[bh2smith]

Could potentially limit ourselves to a specific spread for improved accuracy and speed.

Limiting the number of hops wouldn't improve performance (using Bellman-Ford algorithm). However, there are some other algorithms (adaptations of BF - #875) that might be advantageous.

[nlordell]

Transitive Orderbooks

I'm doing some investigation around using a graph approach to calculating transitive orderbooks. Unfortunately it isn't very obvious to me what the "correct" and "expected" mean for transitive orderbooks, specifically when two sides of the transitive orderbook share orders. Consider the following order graph (assuming 0 fees) where nodes represent tokens and directed edges are orders starting at the sell token with a weight of sell amount over buy amount, so: SELL ---sellAmt:buyAmt---> BUY.

What is special about this orderbook is that the transient orders A -> C -> D -> B (with a total price of 1:2) and B -> C -> D -> A (also with a total price of 1:2) both require the same order C -> D. What does this mean when calculating the transient orderbook? Assuming sufficient balances:

Is this the orderbook?

amount
  ^
  |
2 |----+                                       +----
  |####|                                       |0000
  |####|                                       |0000
  |####|                                       |0000
1 |####+---------+                   +---------+0000
  |##############|                   |00000000000000
  |##############|                   |00000000000000
  |##############|                   |00000000000000
0 +----+---------+---------+---------+---------+----> price
       0.25      0.5       1         2         4

The issue is that this is a bit misleading. If we place an A -> B order for 2:1, then the orderbook would become:

amount
  ^
  |
3 |----+
  |####|
  |####|
  |####|
2 |####+---------+                             +----
  |##############|                             |0000
  |##############|                             |0000
  |##############|                             |0000
1 |##############+-------------------+---------+0000
  |##################################|00000000000000
  |##################################|00000000000000
  |##################################|00000000000000
0 +----+---------+---------+---------+---------+----> price
       0.25      0.5       1         2         4

A solver would then, theoretically, be able to match the new A -> B order with the B -> C -> D -> A transient order (for 1:2, making a nice ring trade). This would completely use up the C -> D order and our transient orderbook in the next batch would end up being:

amount
  ^
  |
1 |----+                                       +----
  |####|                                       |0000
  |####|                                       |0000
  |####|                                       |0000
0 +----+---------+---------+---------+---------+----> price
       0.25      0.5       1         2         4

However, in a traditional market with only direct trades, then spread would look like this instead:

amount
  ^
  |
2 |----+
  |####|
  |####|
  |####|
1 |####+---------+                             +----
  |##############|                             |0000
  |##############|                             |0000
  |##############|                             |0000
0 +----+---------+---------+---------+---------+----> price
       0.25      0.5       1         2         4

This makes these spread graphs a little counter intuitive. Let me know what you guys think, and if this aligns with your expectations.

As a closing note, computing transient orderbooks with a graph approach only really presents benefits if we limit the spread. Otherwise, I don't think we wouldn't really gain any runtime performance over calculating transitive hulls (as we would calculate the same orderbook in the end). I think this is an acceptable trade-off since I don't think traders are interested in transitive orders trading, for example, 6000 USDC for 1 DAI (for which transitive orders currently exist :smile:).

[fleupold]

I think that behaviour is expected. In a traditional market you would also not expect a bid on USD<->ETH to affect the liquidity of MKR<->GNO but in our mechanism this is effectively the case (as USD <-> ETH might use offers from the MKR <-> GNO pair).

That's because:

The case here might be particularly weird because we are drawing the lines in the same graph and thus we might actually see the bid curve reducing although we added a bid (if the added bid "eats" an ask that is using the same underlying order as another bid).

Taken for themselves the bid and ask curves are still coherent.

I wonder if the orderbook should actually be reduced for visualisation purposes or left overlapping. Because, even if orders could be matched at the current state, someone can still place a better offer to "outbid" some already covered liquidity.

[anxolin]

Great example Nick!

I'm not sure I understood what you meant, but the reasoning and the representation look good to me in the case of someone placing A->B order, and the matching using the B -> C -> D -> A one.

Do you mean with this example, that when there's an overlap (A->B was placed, but the solver didn't submited a solution for that), a trader would see a 0 spread, so he would think he can place an order B-A at 1:2, but it cannot be necesarily the case

If the batch is closed, it's likely the solver will find the solution, making C->D not usable any more

However, I believe we need to represent the current vision of the order book, without assuming that a solver would find the solutions. The most important reason for this, is that during these 4min we want to create a competition to get this C->D trade (maybe 2nd trader accepts 2:3 for B->A)

[nlordell]

@anxolin: If the batch is closed, it's likely the solver will find the solution, making C->D not usable any more

Yes, my point is that these market spread graphs don't behave in the usual way: when an overlap is "reduced" at the end of the batch (by the solver submitting a solution), the volumes don't just decrease by the overlapping amount - it can have secondary effects in the spread chart. As @fleupold mentioned - it's all connected!

However, I believe we need to represent the current vision of the order book, without assuming that a solver would find the solutions.

Yes, I agree, this was more of a meta-question about the current representation of a A - B market. The reduced graphs are, in theory, how the spread would look like in the next batch. I'll update my comment to make that more clear.

edit: This is is what I meant:

The solver would then be able to match the new A -> B order with the B -> C -> D -> A transient order (for 1:2, making a nice ring trade). This would completely use up the C -> D order and our transient orderbook in the next batch would end up being:

[nlordell]

@fleupold I wonder if the orderbook should actually be reduced for visualisation purposes or left overlapping. Because, even if orders could be matched at the current state, someone can still place a better offer to "outbid" some already covered liquidity.

I'm writing another segment about this, there are some other complications here.

[anxolin]

he reduced graphs are, in theory, how the spread would look like in the next batch.

Cool. Does it mean there's 2 visions of this system for any token A-B:

• Current state: As it is, with it's overlaps. Perfect for the first minutes. Encourage competition.
• Reduced graph: Try to remove overlaps. Perfect for the last minutes to prepare to next batch. It looks like a hard problem to me, cause I understand that can be problematic to decide when there's multiple paths. It would be a solver on it's own. Probably for most of the cases could be a good view of the system --> clear cases of overalp would be removed

[nlordell]

Overlapping Orders

In general, we want to show orderbook overlaps. They provide important information to traders (as in how to outbid an existing order to scoop up some liquidity that may already be overlapping by paying a higher price).

There is, however, some complication with transitive orderbook calculation from a graph perspective is regarding overlapping orders. Specifically when dealing with ring trades that share an order in the overlapping ring trade (common theme :stuck_out_tongue:).

Consider the following orderbook:

We have a transitive order from A -> B with A -> C -> D -> B with amounts 2:1 (that is selling 2A for 1B), and a direct order from B -> A for 1:1.

Is this the transitive A - B orderbook?

amount
  ^
  |
2 |--------------+
  |##############|
  |##############|
  |##############|
1 |####+---------+----
  |####|XXXXXXXXX|0000
  |####|XXXXXXXXX|0000
  |####|XXXXXXXXX|0000
0 +----+---------+----> price
       1         2     

There are two issues here:

1. The overlap may be "fake", in that it requires an order that may not be available for this token pair, as it may be used as part of another trade that generates more utility and/or less disregarded utility; in this example the solver might prefer the E -> C -> D -> E ring trade over A -> C -> D -> B -> A ring trade (or not perform any trades at all). In general, any overlap represented here is inaccurate and may not actually be possible to match in a solution.
2. It cannot be reliably calculated with Bellman-Ford, since it just finds a negative cycle, and not a specific negative cycle, and depending on the order in which it finds these cycles, it can affect the final results; specifically the transitive orderbook might looks like the following if the E -> C -> D -> E ring trade gets found first:

   amount
   ^
   |
   1 |    +----
   |    |0000
   |    |0000
   |    |0000
   0 +----+----> price
      1     

The limitation with Bellman-Ford is that it cannot find paths between A -> B (i.e. transitive orders) as long as there are negative cycles (i.e. overlapping transitive orders) in the graph. Furthermore, the order in which these negative cycles are discovered and subsequently removed, is not guaranteed. This means that you cannot guarantee that all negative cycles from A -> B will be considered.

Are we OK with this approximation (that the overlap might appear smaller than it actually is)? Note that for a given orderbook graph, the Bellman-Ford result is deterministic [*], so while the approximation may be inaccurate, it is extremely precise.

[*] NOTE: We had some issues with inconsistency calculating price estimates with CI - this is caused because of how the orderbook is read. Specifically orders were being considered in different order depending on the run. This should not be a problem once the orderbook has already been read into a graph though. We should definitely look a little deeper into this though.

[nlordell]

@anxolin: Cool. Does it mean there's 2 visions of this system for any token A-B:

Yes, and we already have solutions for computing the reduced orderbook (which we use for price estimation).

[twalth3r]

The overlap may be "fake", in that it requires an order that may not be available for this token pair, as it may be used as part of another trade that generates more utility and/or less disregarded utility; in this example the solver might prefer the E -> C -> D -> E ring trade over A -> C -> D -> B -> A ring trade

Just want to note that we can never guarantee the execution of someones order even if there is a significant overlap on just a single token pair since we have several additional restrictions:

• max nr of orders per solution = 30
• min tradable amount = 10000
• economic viability

So any view on the orderbook can just be an indication/approximation to what is expected to happen :man_shrugging:

[nlordell]

Just want to note that we can never guarantee the execution of someones order

Yes! This will always just be an approximation - adding the full constraints to the order graph is a MUCH more complicated problem (akin to implementing a different kind of solver).

So any view on the orderbook can just be an indication/approximation to what is expected to happen

Yes, the point I was trying to make was the overlapping orderbook spread chart might be an inaccurate approximation because the E -> C -> D -> E ring trade might be preferred.

edit: @twalth3r I updated the comment to the following, let me know if its better:

The overlap may be "fake", in that it requires an order that may not be available for this token pair, as it may be used as part of another trade that generates more utility and/or less disregarded utility; in this example the solver might prefer the E -> C -> D -> E ring trade over A -> C -> D -> B -> A ring trade (or not perform any trades at all). In general, any overlap represented here is inaccurate and may not actually be possible to match in a solution.

[fleupold]

Let me summarize the section of overlapping orders, to see if I understood it correctly:

1. We need to reduce the graph first, because otherwise bellmann-ford cannot find paths between A->B which is what we need to plot the bid/ask curve
2. During this reduction we can find negative cycles A->A and B->B which we can plot into the overlapping area of the orderbook
3. However, we might not find all such cycles, since other cycles C->C might also be found and use up orders that would otherwise facilitate another A->A or B->B cycle (or even non overlapping liquidity between A and B)

Point 3. in particular makes it so that our overlap might appear smaller than it actually is.

Regarding 2, I wonder how exactly can we translate a negative cycle into steps on the orderbook? My understanding is a negative cycle yields a volume and a surplus, but how does this translate to an overlapping step on the bid and ask curve? Let's say we found a cycle A -> A, would we check if B is on the path and then split the cycle into A->B + B->A to get the price/volume of the bid (transitive order A->B) and ask (transitive order B->A)?

[twalth3r]

@nlordell - fully agree with that! I guess my point was that the additional constraints of our protocol yield the same category of uncertainty as the potential preference of another ring trade, so I'd be fine with seeing an orderbook with overlaps as an approximation/indication of the current state of what's going on in the batch.

[nlordell]

@fleupold Great summary! It really sums up every single one of my points, and even adds some very important insight that "even non overlapping liquidity between A and B" might be affected by reducing other negative cycles.

I wonder how exactly can we translate a negative cycle into steps on the orderbook? My understanding is a negative cycle yields a volume and a surplus, but how does this translate to an overlapping step on the bid and ask curve?

Note that any A -> A cycle that contains B is also a B -> B cycle. This means we can produce 2 transitive orders by:

• Taking the A -> ... -> B portion of the path in the A -> A cycle
• Rotating the A -> A cycle to be a B -> B cycle and taking the B -> ... -> A portion of the path.

This would allow us to approximate the overlap that is caused by a negative cycle that goes through both A and B.

For negative cycles that just touch A or just touch B, they would be ignored and cause similar inaccuracies to negative cycles that include neither A nor B.

[nlordell]

To elaborate more on my previous point, the A -> A that goes through B (which is equivalent to a B -> B cycle that goes through A, by rotating the cycle). Can be split into two sub-paths: A -> ... -> B and B -> ... -> A. Note that since we know the complete cycle is negative, then there must be some overlap between the two transitive orders created from the two sub paths.

Once we collect all transitive orders produced from these negative cycles, we can just sort on price and produce the spread graph that we have from before.

edit:

Let's say we found a cycle A -> A, would we check if B is on the path and then split the cycle into A->B + B->A to get the price/volume of the bid (transitive order A->B) and ask (transitive order B->A)?

That is correct, and what I was trying to explain in so many words...

[marcovc]

Hi! Just to point out that finding the negative cycle which has the most negative sum can apparently be done efficiently for the current instance sizes. The problem is NP-hard though. There is a PR with some experimental code for this in the standard solver repo: https://github.com/gnosis/dex-solver/pull/251

[nlordell]

This has been implemented by #997