ART: Scope & Goals of the Anoma Protocol [braindump]

[cwgoes]

Reader beware: this is currently a braindump, and may not be clear at all. Here be dragons!

Prior context:

• Scope section of the Anoma specs
• This old HackMD
• This other old HackMD

The reader who has not already read the scope section of the specs linked above should do so first. The following should be understood as an addendum to the content therein.

Concepts which need to be developed & defined

• “What is a protocol?” - a protocol is a box (algorithm to be run on a non-deterministic Turing machine) inside an agent, “through which” the agent can send and receive messages, and which can automatically respond to messages “on behalf” of the agent (including complex responses, not just request-response).
• “What is an equilibrium protocol?” - an equilibrium protocol is a protocol such that, for a specific set of requirements, either:
  • there exists no protocol which better satisfies those requirements, up to implementation details (e.g. choice of cryptographic primitives), or
  • agents who start using this protocol for purposes within those requirements will never have a reason to switch to any other protocol / uses of this protocol will be incentive-compatible
  • (I am not sure which definition is correct here, we might need multiple ones for different purposes)
• Agent identity. In particular, agent identity is - from the physical perspective - fluid, as the “zone of control” definition is neither fixed nor verifiable. Zone of control is preserved through time through control of private information, which is what we use to reason about agent identity at higher levels (cryptographic identity), and we should spell this out in detail. I wonder if this report can get to a point where we can detail what “composition of agency” means in this context, which is related to this question (see also this SFI paper)
• Semantics of promises w.r.t. messages in/out on other protocols (e.g. one can understand “arm lifting up boulder” as a protocol, the semantics of which are opaque to Anoma the protocol but meaningful to the agents themselves vis-a-vis their access to this other protocol, I think). This is related to what is sometimes called “the oracle problem”.
• The difference between “direct” coordination of object-manipulation actions (representing objects as resources and using intents to agree on what to do with them) vs. “symbolic / delegated agency” coordination of object-manipulation actions (scale-free money, i.e. coordination on values-alignment and decision-making power).

Protocol requirements

The key set of requirements to lay out is: what is it that we think that the Anoma protocol must do? Several things come to mind:

• sharing observations (already mentioned in the specs) (here we need to define in more detail what sharing observations means and requires, e.g. perhaps partial-order linkage using one-way functions to collate “intersubjective time” information)
• sharing compute, storage, and network resources (already mentioned in the specs) (this is related to service commitments) (we need to clarify what “network resources” are)
• providing a virtual plane of agent-to-agent communication which adapts to a dynamic underlying physical network where the agents are moving about in the physical plane and their physical communication links/speeds/capacities etc. are always changing (this is the sort of “heterogeneous Perigee” area of requirements)
• providing a distributed intent machine, such that Anoma provides a distributed state with configurable rules as to how parts of that state can change (applications), and abstractions so that agents can agree on those changes using the interface of an intent machine (see: intent machine ART report)
  • I think this is a mechanism-by-which the direct & symbolic coordination may be implemented

I think it will also be helpful to investigate whether it makes sense to “layer” these requirements - e.g. if service commitments are understood as a sort of metaprotocol, subsequent protocols (distributed intent machine) depend on service commitments, but not vice-versa.

[cwgoes]

I think one contrast we can draw viz-a-viz the question of “equilibrium protocols” is of syntax/semantics - e.g. when particular symbols acquire semantic content, they become valuable to use strategically (to misrepresent), which then reduces the precision of the semantic content - so these are unstable in the sense that we care about.

[cwgoes]

I think initially it will be most helpful to focus the collective discussion on aligning on a set of requirements for the protocol, which we should be able to phrase in terms of interface requirements on the protocol “box”, i.e.:

In general, requirements describe what interfaces should be available to Alice and Bob when sending and receiving messages to and from their protocol boxes (treating the interior of the protocol box as opaque), and what properties those interfaces should have.

I think we will need to get a bit more specific about the physical network model. One way of modeling it would be something like:

• Agents have a (dynamic) set of physical network addresses (e.g. IP address, Bluetooth address), which are names that they can communicate to other agents, and may be (but are not required to be) global.
• Agents can send messages through the abstract network to names that they know. These messages may be arbitrarily delayed, re-ordered, and mis-delivered (but liveness properties will require some form of eventual correct delivery).
• Typically, latencies of transmission from one agent to another agent on a particular address will change slowly (i.e. the rate of change in latency will be low compared to the latency itself - we should make this a bit more formal). note from D: sometimes there are sudden 0/1 changes (links up/down)

I think that this is close, although not quite identical to, the graph model of P2P networks that @Jamie and @nzarin investigated a few months back - as I recall it, the main difference here would just be that nodes (agents) can have multiple edges between them (different physical transport links).

With requirements that talk about distributed state and distributed intent machines, I think we can craft an “omniscient observer model” very similar to the one used in @Jamie and @nzarin’s paper on Service Commitments.

I also realized while trying to decompose the requirements here that there should be a clear distinction between:

1. Requirements which talk about what the system is at this level of protocol boxes, agents, and messages
2. Requirements which talk about what the system should allow agents to do (e.g. coordination)

– and I think we should focus first exclusively on (1), and leave (2) for later work (which this model will be a necessary prerequisite for in any case).

[cwgoes]

An approach suggested by @jonathan in our last meeting was to clearly delineate the various levels of abstractions and assumptions in play here. I think a starting point here could be (in order from the basic agent model up):

1. Basic agent model (outlined in the links above)
   • Agents have physical addresses.
2. Abstract agent-to-agent network
   • For anything built on top of this abstraction, agents have cryptographic addresses.
   • Requirements here are precisely those requirements needed in order for the higher-level interface (send-to-cryptographic-identity) to work as desired.
3. Abstract agent-to-agent network w/service commitments
   • Requirements here are precisely those requirements needed in order for the higher-level interface (request, track service commitments) to work as desired.
4. Distributed intent machine
   • Requirements here are precisely those requirements needed in order for the higher-level interface (send intent to intent machine) to work as desired.

What do the distributed intent machine layer requirements look like exactly? Broadly, we want the ability to guarantee that, subject to certain assumptions, an observer (an agent) who treats a group of networked agents as a distributed intent machine will observe properties consistent with modeling that group as a simple (non-distributed) intent machine, within some tolerance.

Recall the definitions from the Intent Machines ART report:

I think we can split the properties we care about into a few groups:

• Correctness, namely, given input intents, will the future observed states be consistent with behaviour as an intent machine?
• Liveness, namely, given input intents, will the input intents be processed “as much as possible” (e.g. it may be necessary to make assumptions about the existence of other matching intents)?
• Alignment, namely, given input intents, to what degree will the preference functions of the input intents be respected (here we enter the questions of iterated games / MEV / slow game / etc.)?

Miscellaneous notes, not yet organized:

• At what level of granularity do we want to reason about state here? Do we want to be able to talk about resources? Do we want to be able to talk about the ability to build restrictions into state changes (resource logics)?
• At what level of granularity do we want to be able to reason about information flow control here?

[cwgoes]

One meta-procedural note: the kinds of requirements we’re talking about here are in a certain sense requirements for model accuracy: given a model of how another part of the network graph will behave, where the model is a lens through which messages are sent and received, and which has certain behavioural properties, under what assumptions can we guarantee that this model will actually be instantiated by the real agent graph (perhaps within certain tolerances)?

[cwgoes]

Notes from brainstorming:

• We can segment / split the agent-local state based on protocol layers, for example:
  • Network-level state includes metadata about physical connection <> external identity relationships, metadata about physical connection latencies & reliabilities.
  • Service commitment - level state includes historical data about which service commitments have been made, historical data about which messages have been sent and received, computed aggregates of performance, etc.
  • Distributed storage - level state includes metadata on which content-addressed blobs are where.
  • Pub/sub - level state includes metadata on which nodes have which preferences, efficient broadcast topologies.
  • Distributed indexing - level state includes metadata on which nodes have which intermediate states.
  • Distributed intent machine - level state includes RM state (commitments, nullifiers), in-flight intents & transactions.
  • Kudos - level state includes kudo balances, transfers, swaps, etc.
• With the lower-level protocols, we should get an optimality / convergence criterion that holds modulo appropriate incentives, which will typically be instantiated at higher levels (so this should be abstracted out somehow).
• Protocol layers should be separated such that - modulo incentive requirements - they form a interface dependency DAG (I think, not 100% on this).

[cwgoes]

The astute reader (such as @graphomath) may inquire as to what the difference is between these “segmented agent state components” and “engines”. I think the answer is - nothing! - except for here we are reasoning top-down, articulating desiderata based on the intended behaviour of many engines “of the same type” across nodes talking to one another, and that the appropriate separations of concerns here will often end up referring to groups of engines.

[cwgoes]

Notes from brainstorming 2024.10.07 (need to be collated + organized, likely will not be legible):

• Question: what is it, ultimately, that we aim to allow agents to do?
  • Possible avenue (rejected, but kept as a sub-goal): share and update a virtual, shared state space in an incentive-compatible way, synchronize the virtual shared state space to physical locations given (varying) access needs.
• Fundamental topic: composition of agency, where agency is understood as the ability to take inputs, model, plan, and act. Consider a hypothetical world where two agents can instantaneously communicate and share a locus of control - i.e. where they are in fact really one agent. The goal of a protocol should be to:
  • Allow potentially coordinating (composing) agents to discover each other, discover in which situations they really can “act as one”, and reason about incentive-compatibility of such.
  • Allow potentially coordinating (composing) agents to build a shared model, by sharing observational data.
  • Approximate this world as closely as possible, in the cases where agents wish to act as one.
  • At least for now, bracket out the question of semantics - we care only about what is necessary to allow agents to agree on shared state changes and make those changes visible / common knowledge as they wish. What those state changes “mean” in the world, measuring whether or not agents kept their promises of acting in the world in a particular relation to the state changes, making promises about how to act in the world in relation to state changes, etc. are all out-of-scope for now (but maybe we can bracket these out as “somehow measurable”, i.e. specify the interface).
• What is the difference between this approach and natural language?
  • In this computational commitment approach, we have an exact split between syntactical rulesets, agreements, and changes - which have no fixed, a priori relation to anything in the world at all - and semantical rulesets, agreements, and changes.
  • In the natural language approach, there are degrees of syntax vs semantics but there is no intrinsic, computational meaning of terms, and typically / in practice syntax and semantics are mixed (as is checking whether or not previous promises were consistent with observed behavior).
  • Something something computational capability.

[graphomath]

While I have not understood the following (draft of a?) definition for model, stating that

the model is a lens through which messages are sent and received,

completely yet, I am jumping to the point that I find most important: the definition of protocol.

To get started, I would like to pick up the slogan that we are “moving from an imperative to a declarative paradigm”. In particular, I wonder what is the quickest way to “de-algorithmize” the above definition,^[1] i.e., the following:

@cwgoes

a protocol is a box (algorithm to be run on a non-deterministic Turing machine) inside an agent, “through which” the agent can send and receive messages, and which can automatically respond to messages “on behalf” of the agent (including complex responses, not just request-response).

In short, the plan is to avoid the jargon “ɴᴅᴛᴍ” and decouple the definition from any of the various entities that one may want to call an “agent”.

So, for starters, let us put aside the question of whether a protocol (instance) has to run inside agents and defer the question of whether or not a first definition of protocol requires agents; I would think that all we need are primitive notions of receiving and sending of messages (w/o mention of who is sending or receiving) — very much in the spirit of the basics of service commitments (cc @Jamie @nzarin). But maybe not even that!

Candidate for an abstract protocol definition

Notation

• \wp powerset: \wp(A) ≔ \{ A' \mid A' \subseteq A\}
• \wp_f finite powerset: \wp_f(A) ≔ \{ A' \mid A' \subseteq A, A' \text{ is finite }\}
• A^B function space: A^B ≔ \{ f \mid f \colon B \to A\}

Also, suppose we have an arbitrary but fixed set of messages \mathbb M.

Def. Protocol

A protocol endpoint^[2] is a function e \colon \wp_f(\mathbb{M}) → \wp\bigl(\wp_f(\mathbb{M})\bigr) that takes a finite set of messages M —think received ones, for the sake of intuition— as input and outputs a set of finite sets of messages e(M) —think all possible options for message sets to be sent as correct reaction, out of which one set must be chosen. A protocol is a pair (E, r), consisting of a finite set of protocol endpoints E and a function r \colon M \to \wp_f \left( \left(\wp\bigl(\wp_f(\mathbb M)\bigr)\right)^{\wp_f(\mathbb M)}\right), which maps each message to a finite set of protocol endpoints-- (think of it as the receivers).

Exercise: describe protocol state as a pair of a set of messages in transit and sets of received messages at their endpoint (a map from endpoints to their received messages).

Best solution goes here!

Exercise: describe protocol evolution as a transition system whose set of states are all possible protocol states.

The idea is that one message at a time gets delivered. See the WiP ART report (please dm me for details.)

What about computable endpoints?

Once we have a definition of protocol in place, we sure want to have restrictions such that we can implement “sub-endpoints” of type \wp_f(\mathbb{M}) → \wp_f(\mathbb{M}), which is what Anoma’s engines do.^[3]

What’s next: properties – but wait!

So, now, if we think about properties of protocols, likely we want to have this is sync with the current research on service commitments. Next up is the question of how to “upgrade” the above candidate definition with time, but one step at a time …

TL;DR

I think, with little effort, we can find a way to polish our definition of protocol such that it is in line with Anoma’s philosophical underpinning, but independent of it and has clear links to published papers on the topic of protocol endpoints. In the end, engine instances should amount to implementations of protocol endpoints (cf. protocol instances in the above post).^[4]

References

• Secure Synthesis of Distributed Cryptographic Applications
• Hybrid Multiparty Session Types - Full Version

---

1. Mainly, I want to put aside any ontological commitments, for the time being, being agnostic so to speak. Also, I think, some of the above text may already hint at some aspects of what I am after: the “boxing things up” and the occurrence of protocol instances – as opposed to something else ↩︎

2. The terminology protocol endpoint is borrowed from two papers: the viaduct paper and Nobuko’s paper (see also ᴍᴘꜱᴛ)—without considering specifics of these papers. ↩︎

3. I think, we can even encode the spawning of new endpoints in that we send messages to endpoints that are not yet present. However, No semantics given! ↩︎

4. In fact, the above idea of protocol could end up being extremely useful for setting the stage before we turn to the arduous definitions in the engine ART report (@jonathan @AHart). ↩︎

[graphomath]

@cwgoes

Distributed indexing - level state includes metadata on which nodes have which intermediate states.

There is indeed a close resemblance between protocol instance^[1] and engine intance in the context of the above illustration:

The blue arrows in this picture could be used to illustrate the idea of local interactions of engines (and a comparison with interaction trees is overdue). The current version of engines in the spec does not have any non-trivial interactions with Alice and Bob, except for that Alice and Bob “run” these engines in their boxes and can stop and restart them.

On the topic of state: the main state of interest to engine instances is the set of received messages (as all initial state could be “hard coded” in the function)—and access to local time. Leaving out local time, a very abstract view on engine instances is as computable protocol endpoints. To be continued …

---

1. A protocol instance may consist of several “composed” engines though. ↩︎

[cwgoes]

Thanks for the feedback! I will take a look at the links. In general, I am in favor of divorcing the concepts and language here from any unnecessary philosophical commitments, and we certainly don’t need ontological ones - no claims are being made about the nature of being or existence - but we do want to be able to make claims about what kinds of protocols are possible and incentive-compatible given a certain understanding of parties running the protocols who have, always, the ability to do otherwise - so an “agent”-concept of some sort is inescapable, I think…

[cwgoes]

I think as a next step here it would make sense for me to attempt to organize the content thus far into a structured document, which might as well be in ART format, with holes for the parts we have yet to figure out - and then seek feedback on and contributions to that. That document should rigorously define, at minimum, the following concepts:

• Agent
  • and what it means to be “inside” or “outside” an agent (locus of control)
• World
• Network
• Input
• Output
• Time
• Agency
• Coordination (composition of agency)
• Protocol
• Predictability (and “trust”, at least for our purposes)