Optimal Quadratic Solver Algorithm for All Ethereum Smart Contracts
The new quadratic solver algorithm yields the theoretically best (most accurate possible) result.
Guys, we did not expect to do this, but we just invented the theoretically optimal quadratic solver algorithm for all ethereum smart contracts.
Because we need to approximate any Orderbook shape, we can't just use stuff like x*y=k. In order to fit to an Orderbook shape, we need a quadratic solver. For anyone who's run a regression, you know this is even doable from excel. But smart contracts have crazy numerical errors, and as a result, normal run-of-the-mill quadratic solvers yield un-bounded margin-of-errors especially when you can compose a chain of trades.
Our smartest guys (not me) spent the last 3 weeks working on a new quadratic solver and we have it:
- The new quadratic solver algorithm yields the theoretically best (most accurate possible) result.
- The margin-of-errors are exactly understood 100% of the time, without a single uncovered case, even with the most pathological examples.
- The algorithm we have is provably stable: any further composition is always exactly stable; i.e. if you keep composing the chain, it will become stable not just eventually, but immediately stable (except for the very initial state which is theoretically impossible to get back).
We will publish a detailed technical paper on this. This is the foundational algorithm to all regressions that need to be run on smart contracts going forward.
Some Empirical Results and Commentary (before we publish a formal paper)
Some empirical evidence for one of the most pathological Dai-wETH run (with tiny prices that caused huge round trip errors for smart contract):
Round trip absolute error comparison between Smart Contract (SC) and Python (Python with the theoretical best quadratic solver): for Python worst error is ~ 1e14 (we will see this is all from tradeX->tradeY).
Ratio of absolute error of Python over SC: huge improvement factor.
Python (optimized solver) absolute error in log scale (14 means 10^14 error): note that tradeToken == 0 corresponds to tradeX then tradeY, while tradeToken == . corresponds to tradeY then tradeX, and we see that for the tradeY -> tradeX direction all errors are exactly 0.
This is the round trip difference (Python optimized) for the direction tradeX->tradeY. Notice that the difference is roundtrip after - before (not absolute value), and they are all non-negative, which means the algorithm is protecting LP (always favor a solution that is in favor of the LP, when multiple solutions are available)
Diagonal counts indicates that original SC and optimized Python agree on the error category for a particular input; this means that for most cases, original SC and optimized Python have the same exceptions (revert IO overflow or IO negative X etc) for the same input; except for 36 cases where the origial SC reverts while optimized python goes through (probably due to better rounding error). But notice that there is not a single case where original SC is successful while optimized Python fails.
Graph of log_abs_difference for the tradeX->tradeY direction as a function of log_price; a clear pattern that smaller price leads to higher error for this direction; again for the other direction roundtrip error is always exactly 0 for any input.
Graph for log_abs_difference (optimized Python) against the number of iterations in our piecewise integral function. There is no clear pattern, which indicates that the iteration depth is not a factor causing the roundtrip error for tradeX->tradeY.
The result of tradeX for original SC and optimized Python is always identical; all the improvement comes from the optimized quadratic solver.
Again, tradeToken = 0 corresponds to tradeX->tradeY, dir = 1 corresponds to (for tradeX) xAfter > xBefore and dir = -1 corresponds to xAfter < xBefore. Notice that there is not clear pattern regarding which trade direction (putting in X or taking out X) is causing more of less round trip x errors.
log_abs_difference (roundtrip error for optimized python tradeX->tradeY) as a function of the log trade size of Y: Notice that the larger the absolute trade size of Y is, the smaller the roundtrip error for tradeX->tradeY.
log_abs_difference (roundtrip error for optimized python tradeX->tradeY) as a function of the log trade size of X: Notice there is no pattern here; tradevsize in X does not affect the roundtrip error.
in the above,
+ means calling tradeX (or tradeY) with a value After that is bigger than Before
- means the other way around
I don't know about you guys, but
My body is ready.