Interoperability between declarative and imperative paradigms via PA

Protocol Design
1

The goal of this post is to describe the problem of interoperability of different paradigms and propose the short- and long- term solution that involves minimal changes but preserves maximum generality.

Declarative vs imperative

Dividing the execution flow into two parts, we can talk about high-level, specification layer and low-level, execution layer. The execution layer always operates in the imperative paradigm - a specified sequence of commands is executed. In contrast, a declarative paradigm doesn’t require specifying how to do something but only what the start and end states are. The specification layer can be described in both imperative and declarative ways. The ARM operates in declarative specification paradigm. Ethereum and most other blockchains operate in imperative specification paradigm.

Going from imperative specification to imperative execution layer is fairly straightforward: for example, if I say “buy me a red apple from the Rewe nearby”, the execution steps include getting out of the house, going to Rewe, buying an apple, going home, etc.

In the declarative paradigm, I just say “I want a red apple” and another actor figures out how to get it (to buy or to grow?) and where to get it from (Rewe nearby or go to Frankfurt?).

Interoperability scenario: local assets, external services

Let’s consider the following scenario: a user holding assets on Anoma wants to use an application on these assets that is hosted on another chain, for example, Ethereum (from now on we will use Ethereum as a universal example). That requires the following steps:

  1. Off-chain: construct the Anoma transaction that provides the resources and specifies the desired end state
  2. Anoma (declarative step): execute the Anoma transaction, bridging the assets to Ethereum
  3. Ethereum (imperative step[1]): Call the relevant application contracts on the provided assets

The following problem arises: the scenario initiates on the Anoma side - the side that provides the assets, but by definition, an Anoma transaction doesn’t specify how to achieve the state desired by the user. The imperative chain that hosts the application requires a sequence of commands. How do we figure it out?

Who figures out the order?

There are multiple ways. Let’s consider some:

1. The user specifies the order off-chain (during step one: off-chain)

That option is the simplest in the sense of implementation, but does take away the declarative advantage of the ARM design. Each paradigm comes with trade-offs, and if we don’t use the advantage it gives, we are only left with the downside part of the trade-off. However, this might be an acceptable solution in the aforementioned scenario where the user already intends to use an Ethereum dapp (and accepts the trade-offs of the imperative model) and only needs the Anoma part to provide the assets.

2. The solver completes the transaction with ordering information (during step one: off-chain)

This option is most fitting assumption for our (long-term) model: users specify what they want (declarative specification) and solvers figure out the path (imperative execution). However, that solution assumes a solver network (which might consist of a single solver) and solving (no pun intended) some associated safety and privacy problems. Since the solver would have to complete the transaction, the user must either trust the solver to see the transaction and modify it, but not tamper with it, which doesn’t scale, or we need to develop a mechanism that enables selective integrity - modifying the transaction in the allowed ways without modifying it in the disallowed ways. In short, it will take some time to get there.

3. A contract figures out the order (during step three: on Ethereum)

Given an Anoma transaction with multiple resources that perform external contract calls, the PA determines which calls have to be executed in which order to achieve the desired state. Generally, figuring out the order of the external calls is a non-trivial task. However, if in the generic call design we expect the same pattern (move assets - perform various external calls - move new assets back), the task becomes way simpler.

It might be unwise, however, to put this job onto the PA, since the generic call application, even though being called generic, still enables only a subset of what can be done via the protocol adapter. In other words, the protocol adapter design is more generic than the generic call resource design.

On the other hand, it might still be acceptable to do that if:

  1. We don’t expect to go beyond this pattern - if GC affordances is the most we expect of the PA design in the long-term.
  2. We don’t mind including this logic in the PA temporarily until we find other affordances that do not require this step (and then move this logic elsewhere). At the moment, the GC design represents the largest surface of what can be done via the PA.

If we want to preserve architectural generality and don’t want to tweak contracts temporarily, it might be wiser to introduce an intermediate step contract that is responsible for ordering of actions that include GC resources. That, of course, is in conflict with the long-term goal of FP since it is based on the fact that both the PA and contracts can tell the difference between GC resources, asset provisioning resources, and other kinds of resources.

What to actually do?

Having said all that, I propose to move forward with the first option for now and the second in the long-term. The first option is the simplest but still requires changes.

1. Make execution on PA deterministically ordered

The PA will have to check for the provided ordering information in the payload and execute calls in the specified order. For the transactions where order doesn’t matter, a random order should be picked to avoid ordering information leakage - the observer won’t be able to tell if the order is picked or assigned randomly.

2. Lift payload constraints in the TTC circuit

At the moment we strictly constrain all payloads in the TTC circuit to be either empty or contain information for wrap/unwrap. We will have to (partially) lift this requirement in the circuit to allow users add ordering information. It shouldn’t introduce any harmful scenarios since by definition any order should be safe in the declarative paradigm as long as it leads to the desired outcome.

The ordering information should be included in external payload since it is..external. So we just need to make sure this and any other external information that doesn’t need to be constrained could be included in the payload.

3. Avoid overconstraining in circuits

Longer-term supporting solution here would involve the ARM changes that would allow storing arbitrary not constrained information in a transaction / action. As long as this data cannot harm, it should be a fine enhancement.

In the short-term, however, we just need to make sure we don’t constrain the circuits in a way that leaves no space for harmless field usage. Given that we don’t have a lot of active circuits, that should be easy.

Specifically, we need to allow inclusion of external information that we don’t need to constrain but that could be helpful in other contexts (such as imperative ordering information that cannot harm).

4. About the order in the action tree root

It is true that we currently recompute the action tree root based on the order of the resources in the action. While it might turn out fragile in certain contexts in the future, I don’t actually see harm in that in the short-term if it is decoupled from execution. We just need to remember that the order of resources is neither deterministic nor meaningful.

So..why not encode it in resource order within the action?

After writing all this I asked myself the same question. Here is why.

User specifying the order is a hack we want to use in the short term, but in the long term specifying the state and specifying the execution order are decoupled from each other with the latter happening after the actions are “sealed” by the user. The user provides the resources and the desired end state, signs it (or authorizes another binding way) and hands it to the solver.
At that step, the execution order is not known but the order of resources in the action is fixed.
In the next step, the solver will figure out the optimal execution ordering and everything else for the user, add this information to the transaction, and send it further.

Dedicating a separate field for ordering and other solver information will provide not just a cleaner approach. Delegated ordering is simply not possible if the user has to sign the execution order before the solver figures it out, and signing has to happen before to ensure tampering resistance.

It might happen that assumptions will change in the future and the solver’s expected work will include more/less stuff. Either way, separating authorization from figuring out the execution order is architecturally cleaner: the user authorizes the state and the order can be added later.

  1. Anoma and Ethereum interoperate on the same level here, so both steps refer to the high-level paradigm. In the Anoma case it is obvious because high-level and low-level paradigms differ. For Ethereum, they are the same.:right_arrow_curving_left:︎

  1. Anoma and Ethereum interoperate on the same level, so both steps refer to the high-level paradigm. In the Anoma case it is obvious because high-level and low-level paradigms differ. For Ethereum, the paradigms are the same so it might be unclear when we are talking about low- or high-level. ↩︎

2 Likes
2

Thank you for the clear write-up. I agree that we must keep the ARM declarative and with the short-term solution(s) that you propose as well as lifting payload and unnecessary constraints.

We could make ordering information optional. Calls without ordering information will be executed in their order or appearance[1] as it is done now and after the ordered calls.

Do we assume a single user or do we want to allow multiple parties to specify the order?
If the latter is the case, how can we handle conflicts in the order, i.e., a duplicated position[2]?

Let’s discuss the required changes in detail and implement them when we work on the PA v2 upgrade.

  1. that is not fixed ↩︎

  2. For example, two users wanting a call to happen first at position 0 ↩︎

1 Like
3

I thought about this at first, but for privacy we should assign random order when the order doesn’t matter so that an observer couldn’t tell the difference between the transactions where the order matters (GC actions) and other transaction types

We can always have a fallback option of executing in the given order if no order is specified though. This way we are always safe.

I think we should assume single party specifying the order. By the time we enable multi-user situations, we should probably have solver networks and protocols for solvers specify the order (the long-term plan), so that the users won’t have to specify anything anymore

1 Like
4

Which software component will assign the random order? I assume you are thinking about the backend transaction service currently.

Once this moves beyond having a transaction service to solving (or even consensus), the incentives of the party that does the ordering have to be considered thoroughly. A random order might not prevail if there is a possibility for more lucrative ordering. I would like to understand your thoughts about privacy and ordering in more detail here.

1 Like
5

I think we can do that on the frontend.

If we are talking about the long-term solving scenario, pursuing the potentially more profitable order either results in an invalid transaction or a valid transaction. If the transaction is invalid, there is no profit from executing the transaction, even partial, because the transaction is atomic and shouldn’t be executed - this is also a property of the ARM we need to make sure doesn’t break with interop[1]. So the task here is no ensure that there is no profit from failing transactions.

If the transaction is valid, it means the intents are satisfied (when we have solvers, we can assume having intents). If all intents are satisfied, there should be no harm for the users if the solver pursues the more profitable for them order (the intent should be able to capture the desired outcome)

Generally, solvers are assumed to be incentivized by the fees they receive for solving and reputation. So, there is no hard control over what they do, but if they misbehave, they will be punished. I believe, the slow game report can give us some more guidance about regulating solvers.

You may think of the transactions that are so profitable that can cancel out the irrecoverable damage for the solver’s reputation in case they pursue the attack. To take care of this, the user authorization mechanism should be proportional to the risks, so that quick and common transactions are executed seamlessly and the higher the transferred value is, the more complex the authorization mechanism becomes. I assume the user who wants to transfer large amounts or valuable items won’t mind being extra careful.

If we think of extracting value from the Ethereum side, I’m not sure how much control we have here but again this is not my area of expertise.

Solver network setup is a complex topic that we, in my opinion, need to do more research on to be able to introduce it properly. Mechanism design is not my area of expertise either, but I can say that the security and the right incentive design are very important here, even if we don’t assume any privacy.

If we consider interop scenarios like the ones introduced by GC, it becomes even more complex since the solvers may profit from exploiting the design features of the other side, e.g., Ethereum and I cannot say right now if we need to do something about it and if we can to do anything about it.

Privacy for solving is super hard and there are no good solutions for that. I explored that topic a couple of years ago and since then it didn’t change much. Luckily, it is decoupled from the settlement privacy (data on the blockchain stays private) and has different requirements (it is short-term vs long-term for settlement privacy), meaning we can consider different solutions (e.g., TEEs).

To summarise:

  • I don’t see non-trivial solver networks happening soon
  • I don’t know much about the mechanism design of solver networks
  • We need to do more research
  • Private solving is hard

  1. we make judgements and assumptions about what guarantees the ARM can provide based on its design. If we don’t implement the design fully, we cannot necessarily guarantee the same properties ↩︎

3 Likes
6

The decoupling you land on — authorize the state, determine order later — is
clean, and I want to push on where the ordering burden actually comes from. In
your scenario the order has to be reconstructed because the destination is
imperative: Ethereum needs a command sequence, so someone (payload author now,
solver later) must supply one. The declarative side didn’t ask for an order; the
imperative target did.

That suggests the ordering problem isn’t intrinsic to intents — it’s the cost of
settling a declarative object against an imperative execution environment. Which
raises a scope question: there’s a class of coordinations whose satisfaction
condition is not a sequence at all, but a predicate over parties or witnesses —
an N-party coalition that clears once a threshold of distinct commitments exists,
or “a signed attestation of kind K over subject S exists.” For those there’s
nothing to order; they clear on constraint satisfaction, and Michael’s
multi-party ordering-conflict question doesn’t even arise, because no order is
being asserted.

Two genuine questions:

  1. In the PA model, do such non-sequential coordinations enter the same ordering
    machinery (and pay the reconstruction cost), or is there a path where an intent
    that targets no imperative execution clears purely on witnesses/thresholds? I
    can’t tell from the resource framing whether “satisfaction = balanced
    transaction” is meant to subsume “satisfaction = a threshold of attestations,”
    or whether those want a separate predicate class alongside the resource algebra.

  2. On your reply to Michael — that once the intents are satisfied, solver
    ordering discretion causes no harm: that holds for everything the
    satisfaction predicate captures, but the predicate authorizes an end-state,
    and paths have externalities the end-state doesn’t see. An execution order
    can leak information or move prices along the way and still terminate in a
    formally satisfied state — your own point about randomizing order to avoid
    privacy leakage is an instance of this, since it concedes that the order
    choice itself carries information. Is the long-term picture that satisfaction
    predicates grow to constrain paths (which quietly re-imports the imperative),
    or that path-level harm is meant to be bounded by something outside the
    predicate — solver competition, reputation, the atomicity requirement?

Not rhetorical on either — I’m trying to locate where, in the architecture, a
coordination that genuinely has no canonical order is meant to live, and what
the declarative guarantee is quantified over when one does.

2 Likes
7

The simplest application to enable your example would solve off-chain. The host chain would already see an ordered transaction, ordering information is always required for execution. The user doesn’t have to provide ordering instructions though (if we are considering the short-term solution), and a random order can be assigned.

With intents, the user has full agency to decide how far they want to constrain the path. Specifying the full path - going imperative - is an edge case example of an intent that can only be satisfied one way. It may happen that the user only constrains the end state without realizing that some paths are better be avoided. I don’t see the need to attempt preventing every imperfect scenario, but there are some mitigations to avoid common undesirable paths.

  1. Multiple parties and applications are usually involved and some parties might introduce protective measures that allow to avoid the subconsciously undesirable execution path. Application developers specifically may help a lot with identifying the predictably harmful patterns and restricting them.

  2. Solver competition and reputation will be important measures to ensure solvers’ good behavior, and more algorithmic approaches to solving that enable selective integrity and provide some safety features will help in the more distant future.

1 Like
8

To make the discussion concrete, let’s take a general case: a transaction with three actions (A, B, C), each containing two resources / two external calls — A.1, A.2; B.1, B.2; C.1, C.2. Alice creates action A, Bob creates action B, Carol creates action C, and the solver composes the three actions into one transaction.

Alice, Bob, and Carol each fix the resource order within their own action, without knowing the others’ orders. The solver fixes the order of the actions. Today the verification order is the execution order, so if the solver orders the actions as A → B → C, the external calls execute as:

A.1 → A.2 → B.1 → B.2 → C.1 → C.2

What I proposed in the meeting was to keep using the verification order as the execution order, i.e. make no changes. The consequence is that the solver can only permute whole actions. So

B.1 → B.2 → C.1 → C.2 → A.1 → A.2

is reachable, but

A.1 → B.2 → B.1 → A.2 → C.1 → C.2   (interleaved across actions)
A.2 → A.1 → B.1 → B.2 → C.1 → C.2   (reordered within an action)

are not.

So the question is whether we need to support reordering external calls across actions and within an action. As discussed, if we do support fully flexible reordering, then it is the solver who specifies the final execution order. Two things I’d like input on:

  1. Do applications need interleaving? I’d like to collect concrete application requirements: is cross-action interleaving (like A.1 → B.2 → B.1 → A.2 → …) needed, or is permuting whole actions sufficient? We define the action as an atomic execution environment, it seems that allowing interleaved calls would break that atomicity?

  2. Reordering within an action looks risky. Suppose the relative order of A.1 and A.2 is constrained by A.1’s logic. If the solver can still reorder them afterwards, the logic proof verifies and execution succeeds, yet the executed order contradicts the order the logic constrained — the constraint is silently violated. Any design that allows intra-action reordering needs an answer for this.

Worth thinking about and discussing further. The good news is that our product currently only produces single-action transactions and we don’t plan to enable multi-action ones in the near future, so this isn’t that urgent. Of course, if we can come up with a simple and clean solution, I’d rather fix it and support the flexibility earlier.

@vveiln @Michael @graphomath @AHart

I’d love your thoughts as well, especially from the app and product side! @maurice

3 Likes
9

Thank you @xuyang for the very clear write-up.

One point from our meeting that I think is worth mentioning in this thread:

This is not guaranteed. If we would just add the execution order as an additional field in the transaction struct that is not included in any of the proofs, everyone seeing the executable transaction in the public mempool (e.g., Ethereum) can frontrun it with a different execution order, which disincentivizes solving. The execution order info would need to be included in the aggregation or delta instance, which seems not ideal.

I think the ordering information should be included in the external call payloads so that resource logic proofs can bind to it.

My initial thoughts were to encode it in the blob[1] as follows:

(
    address untrustedForwarder,
    bytes   input,
    bytes   expectedOutput,
    bytes32[] afterTags,     //NEW: the calls of these tags must run before this call
    bytes32[] beforeTags     //NEW: the calls of these tags must not run before this call
) = abi.decode(callBlob, (address, bytes, bytes, bytes32[], bytes32[]));

The protocol adapter (as the verifying part of the ARM) would then just need to mark resource tags as executed while iterating over them and verify that the order was followed.
By using intent resources (whose commitments / nullifiers the users know) you can constrain the call execution order across actions.

I also don’t see why we should support interleaving external calls.

I have the same concern.

  1. and include the additional ordering info in a resource field such as value ↩︎

4 Likes
10

Thank you for the write up. Normally, I wouldn’t inject the product perspective here. That’s simply because I have a hard time seeing how the products we currently operate (without significant changes to the feature set) would benefit from the declarative paradigm of the PA.

As of now, AnomaPay does not need external solvers.

At that point, we could all indulge in the virtue of sophisticated product hypothesizing (“if we only had X, then we would use Y”) but that hardly adds any substance to the discussion.

Thus, my perspective is that there is no concrete demand for this change in architecture right now and I don’t see a plausible argument for why we cannot change the architecture in the future, if and only if we see some actual demand for it. Yes, this would again cause breaking changes but let’s be honest, is this realistically going to be the last time a breaking change has to happen? I doubt it.

2 Likes
11

The declarative update doesn’t introduce a new feature. It is a way to tackle the limitation we faced in the process of implementing the original architecture.

I share most of your concerns and agree that it could be delayed until applications that could benefit from it become more realistic.

1 Like
12

Here are the changes this entails:

I wouldn’t delay it as the changes are minimal and it can be useful.

Application Examples

There are a several examples where a different call order would still work, but be less favourable for the participants, for example just-in-time (JIT) liquidity provisioning.

jit_example
jit_example2400×1020 154 KB

Another example would be conditional voting: “I only vote after Bob has voted and if either the quorum or support isn’t met yet.”

I am not saying that this is relevant for AnomaPay at all, but it is certainly relevant in general.

2 Likes
13

TL;DR

the protocol adapter functionality, proposed by @Michael, ideally would already be part of a v1, ɪᴍʜᴏ.

… where the order could be any order compatible with the afterTags and beforeTags fields. We all seem to agree that it would be too strict to only consider transactions for which the order of external calls is irrelevant/random/arbitrary (although this would be the clean solution).[1] So, we are looking for the next best thing.

Big picture

The following picture may be helpful to give a rough idea of what this discussion is about.

image
image2012×682 84.3 KB

We are exploring design choices for the additional logic of the protocol adapter that covers situations where ordering constraints arise due to interaction with state that is external to the protocol adapter; roughly, we have to deal with side effects. To illustrate that additional logic is a necessity, note that even a single external call has two possible outcomes: either the transaction goes through or it fails; the resource machine logic should not need to care about this.

Three-step argument

  1. The general specification of the resource machine does use lists and vectors as concrete data structures for the sake of simplicity; in principle, many data structures should be finite sets rather than lists. There is a simple but important fact that is testimony to this: if two transactions only differ in the order of actions and/or resources within actions, then they are equivalent, in the sense that one of the two transactions is executable if and only if the other one is executable and, most importantly, the effected state change is (essentially)[2] the same.
  2. However, in the context of interacting with external state via external calls, e.g. using the generic call forwarder, the order of calls that are associated with resource tags (in actions) “suddenly” starts to matter. In v1, we may reorder actions in a transaction arbitrarily. So, we should have a mechanism to constrain the order of calls across actions, which is simply not possible using resource logics whose constraints are limited to tags within the same action (and cross-action conditions are insensitive to ordering).
  3. One may push the issue to the application layer, via an extra call-ordering gadget, but it is natural to already provide some additional logic in the protocol adapter. Roughly, the PA is the glue between the pure resource machine state and the “native” state of the chain of a protocol adapter deployment, and thus it has to deal with the order of calls.

Upshot

If nothing else, the proposal by @Michael is a good way to improve the chances that several actions are not accidentally ordered in the wrong way. And he’s even already finished the code while I was revising this post!

  1. Also, how would we even check efficiently that the ordering of the calls does not make any difference?! [EDIT: The only exception is if we only have one resource that leads to an external call.] ↩︎

  2. There is a detail concerning the usage of a commitment tree in the current implementation, but actually one could use an implementation of a cryptographic accumulator that would not even require the parenthetical essentially. ↩︎

2 Likes
14

That would also work for me. I think this exploration was useful in any case, since it reduced the uncertainty about how many changes would be needed.

1 Like