Bruno Mazorra, Dzmitry Lahoda, Sydney Sweck & 0xbrainjar
Summary
In most intent-centric DeFi architecture, solvers play an important role in ensuring best execution. A solver is an entity that competes to determine an optimal solution (in the form of a transaction execution pathway) for a user’s intent.
Solution optimization poses a mathematical problem, particularly in the context of cross-domain intent settlement. Thus, Composable has collaborated with Bruno Mazorra to research and develop a novel algorithm for determining the optimal pathway for intent settlement across multiple blockchains.
More specifically, this collaboration makes the following contributions to research in the space:
- Introducing intents over the space of digital assets by using utility functions
- Reducing the multi-domain optimal routing to a mixed integer convex optimization problem
- Introducing the Arrow-Debreu model to define frequent batch auctions for multiple domains
We will deploy the resulting algorithm initially for use by solvers in the cross-domain intent settlement framework MANTIS (Multichain Agnostic Normalized Trust-minimized Intent Settlement), demonstrating its utility in practice.
Definitions
The following definitions are used in developing the optimization algorithm:
An intent is an expression of what a user wants to achieve whenever they interact with a blockchain protocol, for instance “transfer X asset from blockchain A to blockchain B” or “trade X asset for Y asset”. Practically, an intent is an off-chain signed message that encodes which state transitions a user wants to achieve. Unlike transactions, intents are partial. Thus, one can think of intents as parts of transactions that require other direct or indirect parts as complements in order to form a final balanced transaction that satisfies all of a user’s constraints.
Let S be all the set of valid states of a public ledger, and let O be the set of all valid state transitions. Then, an intent can be defined through a utility function:
This is a mathematical function that describes an individual’s preference for goods or services by assigning a level of utility or satisfaction to each bundle of goods or services.
A solver can be defined as an entity that competes to determine an optimal solution (in the form of a transaction execution pathway) for a user’s intent.
In this context, an altruistic solver is an agent that ``tries" to find a path γ⋆ such that:
However, in general, solvers are non-altruistic and have their own utility function over the states of the ledger.
A rational solver is thus an agent that has preferences represented by a utility function u over the space of states. A rational solver finds a feasible transition state:
The fundamental difference between a rational and an altruistic solver is which utility function it is trying to maximize.
Frequent Batch Auctions (FBAs) can be defined as uniform-price sealed-bid double auctions conducted at frequent but discrete time intervals. In the present paper, we apply the FBA method to cross-blockchain intents and transactions.
The Arrow-Debreu market model serves as the foundational theory for the Cross-Domain FBA system. In this model, agents with heterogeneous utility functions interact within a market to reach an equilibrium point. The model assumes a set of goods T = {T1, T2, . . . , Tn}, a set of agents A = {1, 2, . . . , m}, and a utility function for each agent concerning the goods:
The objective is to find a set of prices for the goods that equates supply and demand, thereby achieving market equilibrium.
Algorithm Design
To create the current algorithm, we build off of the work of Angeris et al. 2022 on the optimal routing problem. We extend this work to take into account cross-domain Inter-Blockchain Communication (IBC) Protocol transfers.
We can think of IBC transfers from chain i to chain j as a constant sum market maker (with invariant function φ(x, y) = x+(1−γi)y with reserves (Ri, Rj), where R1 is the rate limiter of tokens that can be transferred from the second chain to the first one, and R2 being its analog in the other direction).
If the IBC transfer has a constant cost, then we associate a non-zero fee ηij and CFMM fee γi = 0. If the IBC transfer has a percentage cost, then we associate a non-zero fee ηij = 0 and CFMM fee γi > 0. If the IBC transfer is non-symmetric, then one can model it by considering two different constant sum market makers with one of the reserves being zero. Therefore, when we have an intent of an utility function U, the cross-domain optimal routing problem can be expressed as the following optimization problem:
Here, ψi represents all the CFMM and IBC transfers. The problem is thus a mixed integer convex optimization problem. Now we can apply the approximate solution method proposed before by Angeris et al. 2022, with some alterations to the constraints in this method.
The FBA method and Arrow-Debreu Market Model are then applied to cross-domain intents and transactions to determine an algorithm for optimal routing. Additional components of the model/algorithm are as follows:
The Utility Function is Ui(x1, x2, . . . , xn). This quantifies the satisfaction or utility that agent ai derives from consuming a bundle of goods (x1, x2, . . . , xn). The utility function is assumed to be continuous, strictly increasing, and concave.
The Maximality Condition is defined as follows: Each agent aims to maximize their utility subject to their budget constraint. Mathematically, this can be expressed as maxx1,x2,…,xn Ui(x1, x2, . . . , xn). This is subject to:
Here, pj is the price of good gj and Bi is the budget of agent i.
The budget is:
Here, yij is the number of Tj assets that the agent i has (or commits) in their intent expression.
The Equilibrium Price is defined as follows: A price vector (p1, p2, . . . , pn) is said to be an equilibrium price if, given these prices, every agent maximizes their utility (satisfying the maximality condition) and the market clears, i.e. supply equals demand for each good. Formally, market clearing is expressed as:
Here, xij is the quantity of good gj consumed by agent ai, and yij is the initial endowment of good gj for agent ai.
Applying this to a scenario involving the settlement of an intent with 2 assets and constraints applied, the matching algorithm is as follows:
This allows for partial fills. To fill orders from largest to smallest, a fifth step is also added:
The above algorithm assumes Constant Function Market Makers (CFMMs) are not available. In situations where CFMMs are available, the algorithm becomes:
Here, note that the current price quoted by the CFMM is given by:
Where CFMM reserves are R = (R1, R2) and the trading function is φ.
Also note:
We detail this algorithm in full in our research paper published here, which also includes calculations for:
- Solving single-asset scenarios
- Generalizing the algorithm for 2-asset scenarios
- Calculating solver collateral
- Minimizing IBC transfer costs
Conclusion & Future Investigation
The results of this study demonstrate the effective optimization of cross-blockchain transactions through the proposed algorithm. It showcases enhanced efficiency and interoperability across blockchain networks. The application of the Arrow-Debreu model further contributes to the understanding and efficiency of multi-domain transactions. This research paves the way for more streamlined and effective approaches in the domain of cross-domain transactions.
However, additional research should be done in the following areas to further explore and improve the present approach:
- Generalizing FBAs to more than two assets
- Simulating optimal routing through the proposed algorithm
- Achieving atomicity in cross-domain transactions