Proving convex optimization algorithms and solutions with EZKL, applied to AMMs

cocswap

In our previous post, we explored how EZKL enables advanced automated market making (AMM). Here, we’ll cover how EZKL can prove general convex optimization algorithms and solutions across different domains; and in particular how this can be applied to AMMs. Convex Optimization solves practically useful problems in finance and industry. Its applications range from portfolio optimization to control systems and with EZKL, we can create proofs that validate optimization processes and solutions.

In particular, EZKL allows us to generate zero-knowledge cryptographic proofs that demonstrate:

  • A solution is optimal
  • A specific optimization algorithm was followed
  • Each step of an optimization was correctly computed

Note that not all optimization problems require proving every step and that some problems have explicit conditions that define optimality. For instance, in matrix inversions, we can prove that a matrix B is a valid inverse of A without revealing the specific algorithm used, see [here](generalized inverse) for an example we released a year ago.

This approach is particularly valuable for closed-source optimization solvers, where we can only verify the solution’s optimality. As a proof of concept of this approach, two EZKL team members developed COCSwap (Convex Optimization Calculation Swap) at the ETHGlobal Singapore hackathon in 2024. COCSwap introduces new trade and liquidity provision strategies that improve capital efficiency through zero-knowledge proofs.

A Gentle Introduction to Convex Optimization

Parabola and Gradient Descent

Optimization problems are usually described as follows.

  1. Maximize/Minimize some kind of objective
  2. Subject to a list of constraints
  3. GOAL: Figure out what to do in order to satisfy 1, 2

Some problems might simply end up undecidable or are simply too complex to solve when large (NP problems, for example). But for some optimization problems, including convex optimization, solutions are reliably easy to compute in practice. A convex optimization problem is one where we try to optimize over a convex function with some linear constraints and inequalities.

More on Convex Functions

Wikipedia Example Image from Wikipedia https://en.wikipedia.org/wiki/Convex_function

Imagine drawing a curve on a graph. Now, pick any two points on this curve and connect them with a straight line. If for every pair of points you choose, the line segment between them always stays above or on the curve (never below it, an intersection means that the curve is below the line), then the function represented by this curve is convex.

A function is strictly convex if it has only one minimum point. This property is particularly useful in optimization problems because it guarantees that there’s only one global minimum – the best possible solution we can find.

The convexity property makes these types of problems relatively straightforward to solve, as we don’t have to worry about getting stuck in local minima. This characteristic is particularly valuable in the construction of Automated Market Makers (AMMs), where we want to efficiently find optimal trading solutions.

For more details on convex optimization, the canoncical reference is Boyd, S., Vandenberghe, L. (2009). Convex Optimization [1].

Applying Convex Optimization to AMM using EZKL

Automated Market Makers (AMMs) are a crucial component of decentralized finance (DeFi). While there have been ideas about using optimization techniques in AMMs [2], implementing arbitrary optimization techniques has been challenging due to Ethereum Virtual Machine (EVM) limitations, such as gas costs and the inability to implement long-running loops.

With EZKL and Zero Knowledge Proofs (ZKPs), we can now run optimizations off-chain and verify the results on-chain. This approach allows us to use the results in a trustless manner within smart contracts, opening up new possibilities for AMM utility functions.

One interesting application we could call Markowitz trading, which aims to maximize the risk-return tradeoff of an accepted trade from the point of view of the AMM. The use of Markowitz optimization in AMMs is described in [2].

For this hackathon, we created a simplified test implementation which just reexpresses the CFMM as an optimization problem, to focus on the change in perspective [3]. The optimization problem is:

minimize

$$(a - (a0 + \delta_a))^2 + (b - (b0 + \delta_b))^2$$

where

$$ a \cdot b = c, a >= 0, \text{and } b >= 0. $$

a0 and b0 are the initial conditions for a and b a0 >= 0 b0 >= 0

Here the deltas represent the change in pool values. This optimization problem is convex and can be solved using gradient descent.

Initial Insights and Findings

  • It’s feasible to run a ‘for loop’ in an ONNX graph to compute the gradient descent which can be exported to a circuit to generate a ZKP.

    • This also means that general proof of training is also feasible!

  • While we chose Convex Optimization problems for their guaranteed convergence and understandability, EZKL’s flexibility allows for optimization over other types of functions as well.

  • The gas cost of the ZKML-verified swap is higher compared to a Uniswap swap (~600k gas vs. 184,523 gas).

    • While it is feasible to run a ‘for loop’ it is not necessary to do so. In some classes of optimization problems, we can run tests to show that a set of solutions are optimal so by simply calculating that some conditions are true. This helps us avoid the costly ‘for loop’. It’s possible to reduce the gas costs further.
    • Some examples of these conditions are the KKT Conditions [4]

  • To mitigate high gas costs, it might be possible to implement a batching mechanism to distribute the cost across multiple users.

Conclusions and Further Work

The proof of concept (POC) in the COCSwap repository is still incomplete and requires additional work, particularly in improving usability and refining the curves being used. However, this project demonstrates the potential of ZKML as a means of introducing advanced optimization techniques to DeFi.

Future improvements in usability will be crucial for making such techniques viable in DeFi applications.

References

  1. Boyd, S., Vandenberghe, L. (2009). Convex Optimization. https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
  2. Angeris, G., Agrawal, A., Evans, A., Chitra, T., & Boyd, S. (2021). Constant Function Market Makers: Multi-Asset Trades via Convex Optimization. arXiv preprint arXiv:2107.12484. https://doi.org/10.48550/arXiv.2107.12484
  3. Jseam, Cemer, E. (2024). COCSwap. https://github.com/jseam2/cocswap
  4. Karush-Kuhn-Tucker conditions. https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions