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.

Onwards!

Tags

Integral Insights

Updates

June 13th, 2024

Integral Insights May ‘24

Business

June 6th, 2024

How to Participate in the Arbitrum Rewards Campaign

125,000 $ARB will be dedicated to a 3-month liquidity mining program focusing on store-of-value (SoV) token pairs such as WETH-USDC, WETH-USDT, WETH-wstETH, and WETH-ARB.

Updates

June 6th, 2024

Unlock High Yields with Integral's $225K ARB Grant from Arbitrum Foundation – Join Our Liquidity Mining Program Today

Integral has been awarded a significant grant of 225,000 $ARB from the Arbitrum Foundation under the Long-Term Incentive Pilot Program (LTIPP). This funding will drive the growth and adoption of Integral on Arbitrum, benefiting the entire ecosystem. With 125,000 $ARB dedicated to a 3-month liquidity mining program focused on key token pairs like WETH-USDC and WETH-ARB, liquidity providers can enjoy high yields and reduced trading costs. Additionally, 100,000 $ARB will be allocated to incentivize integrations with aggregators, solvers, and vaults, fostering a more interconnected DeFi environment. Join us and be part of this exciting journey to enhance liquidity and trading on Arbitrum!

Updates

May 9th, 2024

Integral Insights April ‘24

The combined average daily volume across Ethereum and Arbitrum is now at 8.8 million USD, a remarkable 22% increase compared to last month.

Product

April 25th, 2024

Introducing New Pool Analytics: Elevate Your Liquidity Provision Experience

A standout feature in our latest update is the "LP vs Hold" tab, which provides a comparative analysis of various holding strategies against Integral's LP positions.

Business

April 1st, 2024

Integral Insights March ‘24

We achieved several important milestones, including a new all-time-high daily volume for Arbitrum and the addition of four new pools on the Ethereum mainnet.

Updates

March 4th, 2024

Integral Insights February ‘24

Another milestone was reached on February 21st when Integral processed over $2 billion in cumulative volume.

Updates

February 1st, 2024

Integral Insights: January ‘24

Our initial launch with the ETH-RPL pool was a success, quickly elevating us to the second most utilized liquidity pool for this pair’s trading.

Research

January 17th, 2024

Is Liquidity Fragmentation Really That Bad?

When the token evolves into a store of value, it attracts outside traders, focusing on trading costs and slippage. This is when concentrated liquidity truly shines.

Updates

January 2nd, 2024

2023 Review

At Integral, our focus remains on developing a sustainable product for on-chain trading, serving both traders and liquidity providers.

Updates

December 12th, 2023

Integral Now Rewards Liquidity Providers with Trading Fees on Ethereum Mainnet

This enhancement enables liquidity providers (LPs) to directly receive a portion or all trading fees from Integral pools.

Updates

December 6th, 2023

Integral Insights: November ‘23

During November, Integral processed an average of approximately 6 million in volume with around 1.5 million in TVL. The system’s overall capital utilization sits at around 350%. It is the 10th most used DEX on Ethereum.

Updates

November 28th, 2023

Integral Now Rewards Liquidity Providers with Trading Fees

This enhancement enables liquidity providers (LPs) to directly receive a portion or all trading fees from Integral pools.

Research

November 15th, 2023

How Do University Blockchain Societies Gain So Many Votes?

Explore how university blockchain societies like FranklinDAO and Michigan Blockchain have grown into influential players in DAO governance, utilizing delegated votes and strategic partnerships to shape the future of DeFi protocols like Uniswap, Compound, and Aave.

Updates

November 6th, 2023

Integral Insight: October ‘23

We give an update for our work in October and highlight a profitable LP position from a long-term user.

Research

October 26th, 2023

Understanding the Stakes in Lido’s Growing Share of Staked ETH

The community is arguing whether a protocol may have too much control over the Ethereum network. Lido controls a large percentage of staked ETH, which could have consequences for the network’s future security and neutrality.

News

October 14th, 2023

Changes to Staking and Farming

Looking back at our progress so far and to the future with new updates to staking and farming.

Updates

October 11th, 2023

Integral Insight: September ‘23

We give an update for our work in September with utilization going up on higher volume for our new pools.

Research

October 11th, 2023

The Hottest Narratives of the Summer

What were the hottest narratives of the summer? Our DeFi research team delves into the growth of trading bots, RFV traders and more in this overview.

Research

October 2nd, 2023

Uniswap Governance: A Deep Dive

Governance is considered a critical component for the decentralization and community-driven development of DeFi protocols. We take a look at one of the largest goverance ecostystems in DeFi, Uniswap. In this blog post, we'll discuss the landscape of Uniswap's governance, pulling data from empirical research to dissect the system's delegates and proposals, revealing some interesting findings.