Implement automatic on-chain arbitrage

[maltekliemann]

General Notes

Details found in ZIP-1.

The implementation of the bisection method is roughly based on the implementation in boost, which is licensed under the Boost License 1.0, which is GPL-3.0-or-later compatible according to this.

Concerns

• I would feel more comfortable if we had a simple interface for minting/burning complete sets. The way things are right now, we have to be absolutely sure that the modifications I made here don't result in imbalances between complete sets of tokens and the available collateral in the prize pool. In hindsight, it may have been better to put the cache of pools for arbitrage in market-commons and execute the arbitrage in prediction-markets so that we can use the rudimentary prize pool API already present in prediction-markets.

  The question of "what goes where" in our code base is becoming a more and more serious painpoint to me. The mistake would probably not have happened if do_buy_complete_set and do_sell_complete_set were available in swaps. I see a major problem that prediction-markets and swaps are so intertwined because the scoring rule affects the market as much as it does the pool.

• The arbitrage calculations are heavier than I anticipated. Still seems fine to me, but I think the maximum number of assets allowed in CPMM pools should be reduced.

Technical Addendum to ZIP-1

The test on_idle_arbitrages_pools_with_buy_burn demonstrates one particular inconvenience that you can run into when using bisection: The arbitrage amount should be 12.5 (i.e. 125_000_000_000 as fixed point number), and the starting interval is [0, 50], which means that the mid of bisection should it 12.5 exactly after two iterations. The Python prototype, which uses floating point math, does exactly that.

When using fixed points, you instead get the arbitrage amount 12.5007629394 (125_007_629_394). The reason is that when mid = 125_000_000_000, the total spot price is calculated to be 0.9999999999 (9_999_999_999) instead of 1, which doesn't trigger the break. Why not use a PRECISION parameter here to detect these small imprecisions?

Let's answer a different question first: Do we want the arbitrage amount to be precise as possible (so that the pool balances are as precise as possible), or do we want the price to be as close to 1 as possible? Of course, the more precise the amount is, the more precise the price will be. But depending on the derivative of f, it is possible for one of them to be "quite precise" and the other to actually be off pretty bad, so the question is important.

I think we need to go for a precise arbitrage amount, which will result in precise pool balances. Arbitrage is basically the result of moving funds, so the fewer funds can be moved, the better. If the balances are huge, the arbitrage amounts can be huge even if the price is very close to 1, so making sure that the amounts are actually correct is more important.

Going back to the original question, using a PRECISION parameter would solve the particular "problem", but introducting that parameter will also result in situations where arbitrage amounts are off pretty bad because we broke from the loop because the price was already "fairly correct". I think we're much better off without these types of micro optimizations.

[maltekliemann]

~~Closing because I want to clean up the history.~~ Nevermind, too much work.

[Chralt98]

Starting review now..

[Chralt98]

Starting my review now..

[Chralt98]

The way things are right now, we have to be absolutely sure that the modifications I made here don't result in imbalances between complete sets of tokens and the available collateral in the prize pool. In hindsight, it may have been better to put the cache of pools for arbitrage in market-commons and execute the arbitrage in prediction-markets so that we can use the rudimentary prize pool API already present in prediction-markets.

These are well-thought design decisions. To have a good design in blockchain development is especially important. When I think about it right now: The automatic arbitrage is a transitory solution as long as Rikiddo is not applied, right? Maybe it's sufficient to avoid massive developer time for refactoring purposes.

When I think about the code design I would propose the following: Each new conceptional addition to the codebase, should be considered to be in a new pallet (like for example global-disputes). It depends from case to case, I know, but my main argument is, that we could maintain the hard-to-restructure legacy code and rather add better designed new code.

When the code, that we write is transitory, I could live with spaghetti code, but sure, better to have well-written code.