ART: What is a Solver?

In a discussion with @degregat @nikete @cwgoes @apriori discussed this report. In this thread, we’ll outline who will contribute what to the ART. Will discuss with @AHart later today.

For context: Original Proposal

Proposal

What is a solver?

The term in the cryptocurrency research/builder discourse arises when used to discuss intent-centric protocols. Typically, the term solver is meant to encompass an entity that does:

  • computation search,
  • liquidity provision,
  • and transaction submission.

In our thinking , these roles can be unbundled. Different actors can fill each of these functions. In addition, our notion of a solver requires proving of transactions (producing zero-knowledge proofs). With the emergence of proving marketplaces and shared aggregation / verification techniques, it makes sense to discuss our opinion(s) here.

In particular, the goal of this ART is to outline our current understanding of the entity we refer to as “solver” by defining the roles and responsibilities clearly, and perhaps briefly speculating on how a “solver” could be composed of different actors.

The report should also touch on the different ways that intents can be “solved”:

  • coincidence of wants (cycles / ring trades).
  • market maker.
  • users matching their own intents.

Other topics of interest:

  • economic pre-confirmations :roll_eyes:.
  • trade-off b/w latency and information disclosure.
  • solver interface.
  • collaborative solving economics.
  • solving for different application types.

Proposed authors: @apriori @AHart

My part:

  • introduce the concept of a solver and review (literature) how the term is used in the context of existing Ethereum-based protocols
  • outline what the report aims to achieve.

@cwgoes and I will contribute two sections for refining the analysis of the game:

Role Separation

Starting from the notes here we should check wether this role separation for solving is complete and refine the analysis of their composition with each other and internally.

Given no further refinement of the basic roles solvers are composed of is necessary, the broad problem fields to be treated will be:

  • Selectors will deal mostly with time sensitive things like intent flow influenced by network traffic and other lower layers: They choose which intents to include in the batch.
    Examples:
    • One node that has a wall clock and creates a batch for every minute that passes.
    • Three nodes that pick intents, compute a union and run consensus over that.
  • Searchers will be concerned with computationally intensive matching.
  • Pickers will require most mechanism design work, since there will be questions on how to choose utility functions to pick amongst the possible solutions for state updates.
  • Provers can be used to outsource computation of proofs.

@AHart as far as I understand right now, this role separation should not affect the formalization of the solving itself.
The solver decomposition might require some refinement, in the sense of modeling distributed solving, but Selectors and Pickers should “just” happen before and after solving and are more mechanism design problems.

Market Structure Taxonomy

Given the above roles, refine solver composition (section 4 of the intent machines ART) and analyze which market structures can potentially be induced.
Then, work out a mapping from the example applications (from earlier sections) to entries of the taxonomy.

1 Like

I’ve been thinking about what a general answer to “What is a solver” might look like. Here’s a sketch of my thoughts.

I’m going to make a few simplifying assumptions. I’ll assume that intents are “floating in the void”, so to speak. So a solver may pull an intent from a global pool of intents in the network (this isn’t needed, but it helps to not have to think about batching and whatnot). Worst case, this can be bootstrapped into a “batched” version by adding “trusted/chosen solver” requirements into the intent’s satisfaction predicate and asserting that all intents have requirements like this.

I want to think in terms of “Transition Relations”. That is, predicates over pairs of states which characterize what transitions are possible. So, I’m not thinking of a specific transition function, just a relation that restricts transitions. This coincides with the way HPaxos is formulated in the formalization; the actors (learners and acceptors) don’t have transition functions, just relations between subsequent states.

Each agent (engine, actor, node, etc) has control over some portion of the network, defined by a set of “permitted” transitions. These are, for each a, a relation P_a : \text{State} \times \text{State} \rightarrow \text{Bool}. These are the transitions that a has permission to initiate. As a basic example, if a controls a resource, then the transition that just burns this resource may be among the permitted transitions (so long as it’s allowed by the resource logic). Permitted transitions that only require one agent I’ll call “solitary” transition relations. I am assuming that these relations modify something while explicitly leaving everything else on the network unchanged, since that’s all a can do to the parts of the network it has not control over.

Actors will issue intents. These intents have two transition relations associated with them;

  • S_i, defining which transitions satisfy intent i. (Note, not all satisfying transitions are permitted or respect resource logics; if you can cast magic to satisfy an intent, then it will satisfy this relation).
  • P_{a, i} ⊆ P_a, the transition relations permitted by the intent. Essentially, these are the transitions which a would allow to happen on their behalf if the intent is trying to be satisfied by some solver. These, by definition, only include things that a already has control over.

A reasonable basic assumption is that x S_i y \rightarrow \neg x P_a y, (in other words, S_i ⊆ P_a^−). That is, an agent issuing an intent should not be able to solve their own intent just by manipulating stuff they have full control over. If they can do that, then why are they issuing the intent in the first place? One might imagine a scenario where a could satisfy an intent, but there’s a good reason not to do it, and they want to see if an alternative could be proposed by a solver. In that case, they would add what they find undesirable to the requirements of the intent, and it would satisfy S_i ⊆ P_a^−, and that’s what they’d give to solvers. Although, I’m not sure this should be part of the definition of an intent, anyway, but it’s good for intuition to assume this.

We can explicate what a solver can do by asserting that \left(\bigcup_i S_i ∩ P_{a, i}\right)^+ ⊆ P_s; that is, the transitions a solver is permitted to make are, at least, (the transitive closure of) those which satisfy an intent and are allowed by that intent. This does not completely define the solver’s permitted action. The solver has control of its own resources, and it may do what it wishes with them even if it has no intents under consideration. Assuming the intents were made properly (i.e. the intent does actually grant permissions for the resources the intent cares about), then this property should guarantee that the solver always has the resources necessary to solve the intents its given, if a solution is possible at all.

This does implicitly assume that, for any resource that might be handled by a solver, it’s always possible to simply consume a resource without producing anything (that is, without transferring it to a new owner, for instance). This allows the consumption of the resource (which is controllable by the owner) to be present in P_a while the creation of a successor resource (outside the control of the owner) is not. Of course, an intent should be structured so that the mere consumption of a resource is never sufficient to satisfy the intent. Or maybe this isn’t a necessary assumption? I’ll have to think about it.

I will also assume that reward is offloaded into the network, so every solver can assess preferences over transitions with a function, u_s : \text{State} \times \text{State} \rightarrow \mathbb{R}. This means the rewards granted to a solver are on the network and are a consequence of the chosen transition. In that case, the reward a solver gets emerges from what the solver is permitted to take according to each P_{i, a}. Each solver then seeks to pick;

  • \text{max}_{t∈ P_s} u_s(t)

The permitted transitions may entirely be functions of the resource logics (not sure, but it makes sense to me). A resource logic for a resource, r, can be characterized as a transition relation, L_r. This relation should pertain to the creation, destruction, and alteration of resource r while leaving everything not relevant on the network unchanged. In general, we may have a condition that, for any actual transition the networks undergoes, T, T ⊆ \left(\bigcup_{r ∈ R} L_r\right)^+, where R is the set of all resources on the network. Most resource logics will not actually be relevant; but all resource logics should always hold anyway, and we can narrow from there where needed.

This is assuming that networks states are only distinguishable up to resource content. That is, if two states have agents with different internal states but otherwise identical resources, then the two states are considered indistinguishable.

This may be used to completely characterize the permitted transitions. The solitary permitted transitions for an agent, a, are those transitions associated to the set of resources a controls, R_a (if that’s not too restrictive). Given that, we can simply define the permitted (solitary) transitions of a as

  • P_a = \left(\bigcup_{r ∈ R_a} L_{r}\right)^+.

The solver permitted actions would then be

  • P_s = \left(\bigcup_i (S_i ∩ P_{a, i}) \cup \bigcup_{r ∈ R_s} L_{r}\right)^+

Some examples;

  • A liquidity pool. This could satisfy a simple trade intent without matching it with another intent. It just takes an intent and uses the permissions granted by that intent to trade resources the solver owns with those made available by the permissions; satisfying the intent.
  • “coincidence of wants”; a solver uses permissions for many intents simultaneously to trade resources.
  • Individuals can simply pull existing intents to make individual trades; in this case, the individual is acting as a solver.

Essentially all services may be viewed as solvers for some narrow kind of intent. One may imagine an agent acting like an investment brokerage satisfying intents asking for resources to be invested under certain requirements, for example. This should cover auctions and broader financial services as special cases of solvers.

A lot of the logic underlying these services I imagine being encoded into the resource logics; that’s where full trades vs temporary investment would be enforced, for example. So maybe it’s the resource kinds which should be identified with particular services, and some solvers may specialize in dealing with certain resource kinds. This is a semantics issue, so I won’t dwell on it.

So, what is a solver? It’s an agent which uses the transitions permitted by intents as part of its own chosen transition. At least, that’s the answer suggested by the above commentary.

2 Likes

I think this is a great way of framing the functionality, since it seems to maximize options for composition and mechanism design by not specifying anything regarding the concrete interactions of solvers amongst each other and with the distributed state machines that order solver results (the boundary here being the “picker” role mentioned above)!

I’ll try to phrase the missing roles (“selector” and “picker”) in the terms you have introduced here. That should also be a good check if they are sensible and exhaustive in respect to the required functionality.

See below some input to two questions you asked in the post:

I agree that this is good for intutition, but I don’t think we should make it a requirement, as I don’t see any problem with already satisfied intents and it might give us some options we didn’t think of to not add this constraint.

I think we want to have the option to state this very simple type of “burn” intents. They should be possible if not prevented by the logic of the resource itself. Or make it the default that they are not possible, unless the logic explicitly states it, for developer safety (but sounds like the model would be more complex)?

Notes from An Analysis of Intent-Based Markets

Dropping relevant notes in this thread that I will consult for background writing. Not all is in-scope (touches on mechanism design) but still worth noting here.

  • Solvers are agents who compete to satisfy user orders which may include complicated user specified conditions
    • cryptographic primitives ensure that solvers cannot violate user-specified conditions, and the validators of the blockchain verify that these conditions were satisfied
  • CFMMs deterministically quote prices based on liquidity, whereas intent-centric markets pricing is not necessarily known publicly
  • Intent-centric markets generalize RFQ (request for quote) systems.
    • Intents allow users to specify arbitrary covenants, whereas RFQ systems do not.
      • these covenants are guaranteed to hold throughout the execution of the transaction.
  • Solvers are assumed to be rational economic actors who seek to satisfy a user’s order if it benefits them
  • Solvers can hold or acquire information about the state of external markets that unsophisticated users cannot acquire
  • Is a Solver incentivized to execute the user’s order at an optimal price?
    • intent markets are principle-agent problems in which the user is a principle who employs an agent - the solver - to execute their order under the intent covenants
      • maximum output intents (preferences)
      • variance limited transfer intents (constraints)

UniswapX and other intent-based markets

  • incentivizes off-chain agents to provide users with better execution prices than those provided by CFMMs introducing the maximum output intent preference
  • the solver who wins the auction commits to filling the order at an execution price equal to their bid
  • the winning solver has to deliver the specified number of tokens within a fixed time interval.
  • if the solver delivers the assets within the time-interval, the transaction is settled
    • the user receives the delivered assets less the payment to the solver
      • the payment is a fee to the solver for their work in finding the best price
  • If a solver fails to deliver, they are penalized and the user’s trade is sent to a CFMM such as Unsiwap V3
  • In CowSwap solvers participate in an auction to execute user orders at a uniform clearing prices, a “batch auction”

Questions/ Analysis

  • intent-based systems are not necessarily guaranteed to perform significantly better than existing atomic mechanisms such as CFMMs
    • understanding conditions under which intent-based systems provide improvement to existing mechanisms is crucial to designing welfare-maximizing systems
  • reliance on a newtowrk of solvers for fulfillment and execution in an intent market raises questions
    • will the market remain competitive or concrete to a few specialized actors?
    • how would such concentration affect user welfare?
  • In UniswapX the Solver or Filler role is permissioned by Uniswap Labs, there is no free entry into the market
    • there is a heavy concentration of 12/2000 participating addresses which suggests that the market has a barrier to competition even among the existing set of entrants
    • the user only trades with the solver if they offer price improvement above the public (on-chain) market
  • Solvers face a sequence of choices when attempting to fill user orders
    • choose whether to enter the auction or not
      • choice is driven by their initial setup and infrastructure costs that are required to bid on and execute a user’s orders (entry costs)
    • how to bid in the auction
      • solvers expend costly effort to search for a price to win and satisfy a user’s order, which modifies the distribution of prices to F(p, e) where e is the effort level chosen by the solver.
      • in this case, solvers may attempt to source liquidity from external markets, which may cause congestion.

Notes From Redefining Blockchain Interactions: The Crucial Role of Solvers in an Intent-Focussed Future

  • Intents enable the repurposing of existing MEV infrastructure for more useful ends (searchers work for users instead of the other way around)
  • Users at a minimum should be able to receive the best on-chain AMM pricing for a swap minus fees paid to the solver
  • Solvers can provide private mempool and gas optimizations
  • An intent-centric future will impact value capture, the role of liquidity providers (LPs), designs of protocols (chain abstraction), and user experience
  • Protocols will now have to compete on efficiency rather than relying on user acquisition via frontend.
    • DEX aggregators started this trend
      • DEX aggregator is a “solver”
      • pulls the best quotes from several DEXes in combination with RFQs

Role of Solver Today

  • Solvers are market participants who provide counterparty discovery for user intents
  • users express their desired end states and solvers find the optimal path of execution while earning a fee for their work
  • In theory solvers have many paths to solver user intents (preferences and constraints) however some applications place specific constraints by imposition of their auction designs

Execution Quality

  • Intent protocols today are mostly protocol or application-specific swap intent protocols, not generalized
    • UniswapX
    • CowSwap
    • 1inch Fusion
  • User intents can be satisfied by finding coincidence of wants, ring trades, external liquidity (private and on-chain), or p2p (self-solving)
    • w.r.t ring trades and COWs
      • user’s intents get matched with one or more intents of other users
    • all users get execution without incurring fees or slippage
  • In batch auctions (CowSwap) orders are not executed instantly, orders from all users are aggregated over a specified time interval, creating a batch
    • slow settlement can benefit execution quality
    • the longer a user is willing to wait, the higher the chance that a COW or ring trade or aggregation of orders with the same direction can be bundled for gas efficiency
  • Protocol specific intent systems suffer from a lack of compossibility of intents
    • an intent from one intent venue cannot compose with an intent from another intent venue
    • this limits unlocking the full potential of intents and solvers
    • generalized intent networks can “solve” this :wink:

User Experience

  • Learning curve for users is relatively easy, sign some off-chain message for example
  • Solvers act as an abstraction layer as “mediators of expertise”
    • the goal is to enable unsophisticated users to receive better or optimal execution by improving the quality of transactions
      • users express the end-state without having to know the optimal path to take

How Solvers Operate

  • Solvers maintain flexibility over how to satisfy a user’s intent
    • compete through on-chain routing
    • optimize gas efficiency
    • cross-chain execution
    • access to off-chain liquidity
    • RFQ systems
    • private order flow
  • Solvers are sophisticated and will need to optimize over all layers of the stack
    • build out efficient on-chain routing
    • maintain off-chain liquidity sources
    • source private order flow
    • optimize for latency (solve intents fast!)
    • manage personal inventory
    • explore vertical integration

Just had a discussion with @nikete and @cwgoes about role separation for solving and @nikete suggested the solution approach and incentive structure below (modulo errors introduced in my writeup and details to be added later):

Solution Approach

To derive a model with role separation that enables us to implement desirable incentive structures we first describe the properties we want the protocol to have which are: A permissionless (or continuously permissioned), welfare maximizing transaction ordering mechanism.

Then we model the game that happens at the gossip layer, since that is the layer of abstraction, where players will concretely interact. We should not presuppose a concrete protocol that constrains the game, but construct the strategy sets of players from the actions they would take and how they would be rewarded and derive the game from them.

In the third iteration we would describe a concrete implementation of this protocol by using the primitives available to anoma, e.g. cryptographic operations and distributed systems components like distributed state machines and P2P communication protocols.

Candidate Model

One potential model has entities operating on the gossip layer taking on one or multiple of the following roles:

Gossipers: Any entity that wants to participate on the gossip layer. Sends messages containing TXs around.

Selector: A node that takes a set of messages (e.g. bounded by a time interval) from the gossip layer and hands them to searchers.

Searcher: Produces orderings of messages from the sets and hands these non-unique solutions to the picker.

Picker: Chooses one solution from the above options.

A Solver is composed of Gossiper, Selector, Searcher and Picker and in practice at least some solvers will exist where all the roles are performed by a single entity and proving separation is a hard problem.

Incentive Structure

We now present a sketch on how to enforce welfare maximizing ordering:

For any ordered bundle of messages a Solver (or just the Picker) computes from a sufficiently gossiped set of messages chosen by a Selector, Counterfactual Solvers can search for alternative solutions to the initially proposed one, starting from the same message set (or an epsilon larger one, to account for the possibility of strategic censorship). Should they find solutions that are better (e.g. more welfare maximizing) and are able to prove it by providing the program and a verifiable computational trace for their solution, they can contest the solution candidate. Rewards for the counterfactual solvers could be derived from the welfare gap between the proposal and improved counterfactual.

Note: To prevent griefing, this cutoff for punishing specific Solvers/Pickers should likely not be when anyone can just provide better solution, only in cases where they can prove that the solution was maliciously suboptimal, e.g. prove that they were able to find a better result with a “baseline” publicly available search algorithm. Since they need to publish the code, the baseline public technique also improves over time. Slashing could also be contingent on repeated infractions.

The above should inform our analysis of market structures. Later posts will elaborate on how to implement this concretely using the primitives we have available.

1 Like

Here is my attempt to writeup the proposal, appologies that I did not use exactly the same nonmeclature, and just clal the consolidated entities builders, but wanted to writ eit in a way tha tis inmediatly clear to MEV people.

The key is to combine incentives across the p2p and block proposals, and I conjecture that this is necessary and that attempting to separate them will always lead to perverse incentives.

Here I tried to write up the idea in a bit more generality, but might have messed it up. WIP.

In the simplest version: The protocol consensus is that builders have to use a protocol specified function that maps the candidate set of “sufficiently gossiped transactions” to a block. Ex-post auditing where other members of the p2p poo can prove via hash licking that a participant beyond a reasonable doubt violated protocol and used a different function can be slashed.

If one seeks to ossify the base layer, then this is a problem because it prevents future improvements. A more sophisticated approach is then to allow for improvement in the function by requiring the block builders produce a block that generates at least as much welfare as the best block that can be found on a epsilon set of substrees around the candidate set used (as shown by the hash lick) by a open source solver. One can open source a solver and claim the bounties of those who had proposed it.
This leads to a situation where MEV is bound to a small amount since you cant jiggle thinigs in the unobseravbles too much without one of your gossip neighbors being able to out do you. It also creates a positive externality in pushing foward the development of better open solvers.

The big apparent drawback of the more sophisticated approach is the need the application-to-welfare simulators beyond the normal decentralized infra from the dapp. Through notice this is making explcit something that might not be well formed otherwise and that brings it own set of troubles. Not being able to express wha the global value the protocol/network is trying to express by leaving it ill defined is not clear is going to be any better.

Self-resolving mechanisms are something I want to think about more in relationship to this.

2 Likes

Just as a note, the basic mechanism I had in mind for collection of ordering information is the following:

  • For whatever classes of messages we want to collect this information for (could be all P2P messages, or some subset relevant to transactions, e.g. all intents), each message must include a set of ancestors (referenced by hash).
  • Honest nodes - when sending a message - will include as ancestors all messages they have received since the last message they sent, plus a reference to the last message they sent.
  • Any node who sends two messages, neither of which references the other, can be caught and punished by anyone who sees both messages (this is considered a violation of local total order).
  • Nodes who frequently omit received messages in the set of ancestors they reference can (eventually) be statistically identified and punished by other nodes (perhaps just by a refusal to send messages to them in the future).
  • When processing groups of messages, e.g. transactions in a block, the protocol can use this partial ordering information to constrain what solutions are permissible, e.g. by requiring that solutions include (or prove impossible to include) all transitively referenced messages, by requiring that individual intent matches with preference differences favor earlier intents, etc. Note that there is also a data availability requirement here, the economics of which we will need to think through in more detail.

tagging @nzarin @tg-x for more input here as well

1 Like