CoordX Types: A Trustless, Swappable Type System for Shared Records

arXiv:2611.16128 · cs.CR · Submitted 2026-11-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "CoordX Types: A Trustless, Swappable Type System for Shared Records".

Elias: Here's the gist of the paper. The CoordX Protocol carries signed and encrypted entries between parties It proves who wrote each entry and who had permission to write it This paper describes the CoordX type system, the layer that gives entries a meaning The type system has two key properties It is trustless: a type is an ordinary signed object fixed by its digest, and every party evaluates it for itself over entries that the CoordX Protocol has already verified It is swappable: a type names the interpreter it is written for, so many interpreters, of different capabilities and designs, can be used side by side in one record Core Design Principles Six principles define the type system The six principles are: Types.

Nadia: A type is the payload of an entry Meaning is positional A reading is a pure function of what the reader holds The principles dictate how meaning is derived from the record structure and evaluation mechanics Trustless Mechanism "Trustless" has a narrow meaning here This property is achieved through two layers: 1.

Elias: The protocol layer verifies entries by checking signatures and permissions without external trust.

Title and authors: Nadia: Let's talk about who wrote this. It's David Hyland-Wood and Rob Ewin on "CoordX Types: A Trustless, Swappable Type System for Shared Records." This is a white paper from November two thousand twenty-six > <ref:2611.16128#pg1>.

Elias: Yeah, they’re focusing on this type system layer that gives entries their meaning. They aren't describing the whole protocol, just how to assign meaning >.

Nadia: The core idea is that a type is essentially a short document detailing how to read one piece of a shared record—which entries count, what each position means, what actions are allowed there, and what you have to do next >.

Priya: So it sounds like the paper is really defining the structure of meaning itself, rather than just the communication rules between agents >.

Elias: Right. It sets up these six design principles that define how meaning is derived from the record structure and how evaluation works >.

Nadia: They have things like types being fixed by digest, meaning being positional, and a reading being a pure function of what the reader holds >.

The paper's summary: Nadia: So to summarize what they’re doing, CoordX aims to give entries structure through this type system. It’s about making sure that an entry has a defined meaning based on its place in the record tree >.

Elias: They outline these design principles clearly: types are payloads of entries, meaning is positional based on what's between a type and the root, and every reading is deterministic because it depends only on what the reader holds >.

Priya: Deterministic sounds good for consistency. But I want to know how this structure handles the actual data. Does it really capture complex relationships or just simple facts?

Nadia: The schema language they describe has four levels of expressive power, from canonical JSON documents checked against a closed grammar up to regular tree languages >.

Elias: They state that the rules and projections are primitive recursive, which is a big deal because it guarantees that every rule is total and decidable, meaning evaluation always halts >.

Nadia: That’s what they mean—no infinite loops in the computation of meaning, which keeps things predictable >.

The paper's improvements: Elias: Now let's talk about what they improved over other systems. They focus on the trustless enforcement and swappable interpreters aspect >.

Nadia: They tightened up the trustless mechanism by focusing on two layers: first, the protocol layer verifies entries via signatures without external trust, and second, the type layer fixes types by digest so no one can change them after they join a record >.

Priya: That’s a strong security move. It prevents unauthorized modification of the meaning rules themselves because the type is locked down cryptographically >.

Elias: And on the swappable part, they emphasize that many interpreters can exist and be used side by side in one record, as long as they adhere to certain conformance checks >.

Nadia: They also made a specific point about judgment evaluation: rules only read the causal past of an entry—its ancestors and what it cites transitively—never children or grants because those things could arrive later >.

Conclusion: Nadia: So, wrapping up on "CoordX Types: A Trustless, Swappable Type System for Shared Records," the main point is that this system provides meaning to entries in a way that every party can compute and check for itself >.

Elias: It’s trustless because of the digest-fixing of types and deterministic evaluation, and it’s swappable because a type names its interpreter >.

Priya: I just want to emphasize that they deliberately limit the system's power so that general computation isn't Turing complete, which means a type can't loop forever waiting for a condition to hold >.

Nadia: That’s right. They explicitly state that a global order cannot be expressed because an order has to be built from citations and paths >.

Elias: And another limitation they highlight is that because rules only see the past, they can't express prevention of conflicts because a rule can only see what happened before >.

Priya: So, while it adds meaning that every party computes for itself, the system’s limits mean it doesn't handle things like preventing conflicts or running arbitrary complex programs >.

Nadia: That’s the trade-off they make to get this level of verifiable meaning into shared records >.

Elias: It adds what neither KQML nor FIPA-ACL had by giving every party something concrete to compute for itself, which is pretty significant for agent communication research >.

cs.CR

Submitted: 2026-11-12

Updated: 2026-11-17

Comments: 15 pages, 1 image, 8 tables, 1 code block

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: The CoordX Protocol carries signed and encrypted entries between parties It proves who wrote each entry and who had permission to write it This paper describes the CoordX type system…

Key concepts

Trustless Mechanism
Trustlessness is achieved through two layers: the protocol layer verifies entries via signatures without external trust, and the type layer ensures it by fixing types by digest. Every party must evaluate the type on their own client, guaranteeing no reliance on a central authority.
Swappable Interpreters
The type system is independent of any single interpreter. A type names which interpreter it is written for. This allows many different interpreters with varied capabilities to be used simultaneously within one record, as long as they produce the same results for the same input.
Meaning is Positional
Meaning in CoordX entries depends on specific positions within a tree structure of records. The rules and projections are derived from what the reader holds at those specific locations, making the interpretation of any entry deterministic and stateless.
Primitive Recursive Computation
The schema language is restricted to functions that are primitive recursive. This guarantees that every rule is total and decidable, meaning evaluation always halts. This deliberate limitation ensures complex record meanings are computable safely without risking infinite loops.

Terminology

Summary

The CoordX Protocol carries signed and encrypted entries between parties It proves who wrote each entry and who had permission to write it This paper describes the CoordX type system, the layer that gives entries a meaning The type system has two key properties It is trustless: a type is an ordinary signed object fixed by its digest, and every party evaluates it for itself over entries that the CoordX Protocol has already verified It is swappable: a type names the interpreter it is written for, so many interpreters, of different capabilities and designs, can be used side by side in one record

Core Design Principles

Six principles define the type system

The six principles are:

** Types. A type is the payload of an entry **

** Meaning is positional **

** A reading is a pure function of what the reader holds **

The principles dictate how meaning is derived from the record structure and evaluation mechanics

Trustless Mechanism

Trustless has a narrow meaning here

This property is achieved through two layers:

  1. The protocol layer verifies entries by checking signatures and permissions without external trust. p. 0

  2. The type layer ensures trustlessness by fixing types by digest, having no registry, requiring every party to evaluate the type on its own client, and ensuring deterministic evaluation. p. 0

Swappable Interpreters

The type system is separate from any one interpreter

** Many interpreters can exist **

** Interpreters can differ **

CoordX allows for mixing interpreters in one record, where a type can nest a subtree whose type is written for another interpreter, and the runtime reads each subtree under its own type Implementations can be swapped because two implementations of one interpreter must give the same result, checked by a conformance suite.

Schema Language Expressiveness

The expressive power of the schema language is described at four levels

** Schemas are canonical JSON documents checked against a closed grammar **

** Payloads form a regular language **

** Structure forms a regular tree language **

The rules and projections are primitive recursive, meaning every expression halts on every input, and every rule is a total, decidable predicate

Comparison with Other Languages

CoordX types place it on the safe side of the LangSec line compared to KQML and FIPA-ACL

** KQML has a CFL envelope but content is open **

** FIPA-ACL has a CFL envelope but content is open, relying on unverifiable mental states **

CoordX types limit the language at the parser and also limit the computation that gives an entry its meaning, accepting more power than CBCL in rules in exchange for meaning that every party can compute and check The comparison shows that CoordX types accept much less power than an ACL whose content is open

Limits of the System

The limits deliberately imposed on the type system include:

** General computation is not Turing complete, so a type cannot loop until a condition holds **

** A global order cannot be expressed, as an order must be built from citations and paths **

CoordX types cannot express prevention of conflicts because a rule only sees the past, allowing two parties to act at one position Furthermore, a type cannot read a clock or anything outside the entries that a reader holds

Conclusion

The CoordX Protocol proves who wrote an entry and who could The type system says what the entry means It is trustless because every party evaluates it, and it is swappable because a type names its interpreter Its schema language is deliberately small, ensuring that evaluation always halts and provides meaning for every reader The system adds what neither KQML nor FIPA-ACL has by providing meaning that every party computes for itself

Terms

** causal past An entry, its ancestors, and what it cites by ref, transitively **

** dependency A type that another type cites by ref, to type a nested subtree **

** export A named value of a subtree, evaluated at its root, that an enclosing type can read **

** interpreter A language for types, and the software that runs it, published as an entry and named by a type **

** position An entry, seen as the place where a meaning, a view or an action belongs **

** primitive recursive The class of functions computable with loops whose number of runs is fixed before they start **

** projection A named value computed at a position **

** reading What one reader’s client knows of a subtree: verdicts, views, exports and obligations **

** rehearsal Reading the tree with a plan’s entries added as hypothetical, before posting **

** rule An expression that must hold for an entry to be admitted **

The paper is 2611.16128>

Pruning redundant reasoning tokens

The design principles define how meaning is derived from the record structure and evaluation mechanics

  1. Types are defined as the payload of an entry, which anybody can write and publish, with no special standing. p. 1

  2. Meaning is positional, depending on entries in the tree between a type entry and the root entry. p. 1 p. 1

  3. A reading is a pure function of what the reader holds, making interpretation deterministic and stateless. p. 1 p. 1

  4. A judgment is a fact, where rules read only the entry’s causal past, never children or grants because they can arrive later. p. 1 p. 1

  5. Conflicts are shown, not resolved; rules cannot see siblings, allowing two parties to act from the same position. p. 1 p. 1

  6. An action is a plan, an ordered list of exact entries and grants that the type turns an action into. p. 1 p. 1

How the training signal is built

The schema language grammar is closed, meaning any member not defined makes the schema invalid, and errors are found by the author before reading any entry

The language supports scalars like integers, text, booleans, parties, and entries of this subtree. It also supports collections such as lists (in order), sets (no order), and maps. p. 3

Expressions use familiar forms like x if c else y and comprehensions but the set of functions is small and fixed, with no user-defined functions or recursion. p. 4

Where the gains come from

The expressive power is bounded by primitive recursive functions, which guarantees that evaluation always halts and is the same for every reader This places CoordX types with CBCL on the safe side of the LangSec line, while adding meaning that every party computes for itself The system's limits are deliberate, such as not being Turing complete or having a global order

The comparison table shows CoordX types have regular payloads and structure, primitive recursive rules, and public computed from signed entries This contrasts with KQML's CFL envelope, FIPA-ACL's CFL envelope, and CBCL's DCFL CoordX types limit the language at the parser and also limit the computation that gives an entry its meaning This allows for more power than CBCL in rules, in exchange for meaning that every party can compute and check The comparison shows CoordX types accept much less power than an ACL whose content is open or a tool protocol whose handlers can run any code

The CoordX Protocol proves who wrote an entry and who could The type system says what the entry means It is trustless because a type is an ordinary object fixed by its digest, every party evaluates it, and every judgment reads only a past that every party can check It is swappable because a type names its interpreter, so interpreters of different designs can coexist and improve without breaking old types Its schema language is deliberately small, ensuring that evaluation always halts and provides meaning for every reader The system adds what neither KQML nor FIPA-ACL has by providing meaning that every party computes for itself

References

[1] D. Hyland-Wood and R. p. 0 Ewin, “CoordX Protocol: Peer to peer cryptographically verified shared records,” arXiv:2611. p. 006034 [cs.CR], 2026

[3] S. C. Kleene, Introduction to Metamathematics. p. 0 North-Holland, 1952

[4] T. Preston-Werner et al., “TOML: Tom’s obvious minimal language,” v1. p. 30.0, 2021 [Online]

[5] H. Comon et al., Tree Automata Techniques and Applications, 2008 [Online]

[6] A. R. Meyer and D. M. Ritchie, “The complexity of loop programs,” in Proc. p. 9 22nd ACM National Conference, 1967

[7] L. Sassaman, M. L. Patterson, S. Bratus and M. E. Locasto, “Security applications of formal language theory,” IEEE Systems Journal, vol. p. 0 7, no. 3

[8] S. Bratus, M. E. Locasto, M. L. Patterson, L. Sassaman and A. Shubina, “Exploit programming: From buffer overflows to ‘weird machines’ and theory of computation,”;login: The USENIX Magazine, vol. 36, no. 6

[9] H. O’Connor, “CBCL: Safe self-extending agent communication,” in Proc. p. 0 IEEE LangSec Workshop, 2026

[10] T. Finin, R. Fritzson, D. McKay and R. McEntire, “KQML as an agent communication language,” in Proc. p. 0 3rd Int. Conf. on Information and Knowledge Management, 1994

[11] Foundation for Intelligent Physical Agents, “FIPA ACL message structure specification,” SC00061G, 2002

[12] Foundation for Intelligent Physical Agents, “FIPA communicative act library specification,” SC00037J, 2002

[13] M. P. Singh, “Agent communication languages: Rethinking the principles,” IEEE Computer, vol. p. 0 31, no. 12

[14] P. Darondeau and P. Degano, “Causal trees” in International Colloquium on Automata, Languages, and Programming, Springer, 1989

[15] The cookbook shows patterns that most shared records need

Six principles define the type system

  1. Types are the payload of an entry. p. 4

  2. Meaning is positional, depending on entries in the tree between a type entry and the root entry.

  3. A reading is a pure function of what the reader holds, making interpretation deterministic and stateless.

  4. A judgment is a fact, where rules read only the entry’s causal past, never children or grants because they can arrive later.

  5. Conflicts are shown, not resolved; rules cannot see siblings, allowing two parties to act from the same position.

  6. An action is a plan, an ordered list of exact entries and grants that the type turns an action into.

The schema document has members like schema, label, description, entries, state, rules, views, exports, verbs and create Values include scalars like integers and parties and collections such as lists (in order), sets (no order), and maps

A projection is a named value computed at a position, which can be of three forms: value, match, or fold Rules and projections are primitive recursive, meaning every iteration in the expression language runs over a finite collection that exists before the iteration starts

A plan is data consisting of ordered steps, each naming exactly what it writes A plan never picks among existing entries by itself, as the proposer's decision determines where to act

The cookbook ships patterns that most shared records need It shows patterns like poll/1 for people each adding something once and signoff/1 for a document approved in order It also shows thread/3 for a conversation and tracker/1 for a work tracker The patterns illustrate how to use types when acting at the root, carrying facts forward, citing rather than searching, sealing now to reveal later, and using obligations to say what is next It also shows that two from one is read, not prevented and that nobody approves their own work

The CoordX Protocol proves who wrote an entry and who could The type system says what the entry means It is trustless because a type is an ordinary object fixed by its digest, every party evaluates it, and every judgment reads only a past that every party can check It is swappable because a type names its interpreter, so interpreters of different designs can coexist and improve without breaking old types Its schema language is deliberately small, ensuring that evaluation always halts and provides meaning for every reader The system adds what neither KQML nor FIPA-ACL has by providing meaning that every party computes for itself

Terms include causal past, dependency, export, interpreter, position, primitive recursive, projection, reading, rehearsal and rule The paper is 2611.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Trustless enforcement of shared record integrity is achieved by fixing types by their digest, stating A type is fixed by digest, which ensures Nobody can change a type in place. This prevents unauthorized modification of the meaning rules after a party joins the record.

  2. Swappable interpreters allow for flexible reasoning engines, as A type names its interpreter, enabling many interpreters, of different capabilities and designs, can be used side by side in one record. This means a system can adopt an optimized or specialized interpreter without invalidating existing records.

  3. Deterministic evaluation guarantees consistent results across all parties because the document states that The interpretation of a tree of entries is deterministic and The same type and the same entries always give the same reading. This eliminates discrepancies arising from external factors like time or hidden state.

  4. Rule evaluation is strictly limited to verifiable history, as rules read only the entry’s causal past: the entry, its ancestors, and the entries it cites, transitively. This ensures that A rule never reads children, siblings or grants, confining judgment to what is already known.

  5. Conflict resolution moves from choice to description by stating that Conflicts are shown, not resolved, meaning rules can say what two entries mean together as for example 'contended', 'disputed' or 'spent twice'. This allows parties to act independently while the system precisely describes the resulting state of contention.

  6. Actions are formalized as verifiable plans, where A type turns an action into a plan: an ordered list of the exact entries and grants to write. Before posting, a proposer reads the tree with the plan’s entries added, allowing them to see if the type would refuse a planned entry before commitment.

  7. The schema language's expressive power is bounded by primitive recursive functions, meaning every rule is a total, decidable predicate and evaluation always halts. This guarantees that complex record meanings are computable and safe from infinite loops or unbounded computation.

  8. Agent communication languages like FIPA-ACL are contrasted with CoordX types, which limit input classes to regular payloads and regular tree structure, placing them on the safe side of the LangSec line. This limits the power of agent protocols to ensure that every party can compute and check results independently.

  9. The system supports complex data structures through expressions like comprehensions and folds, while deliberately excluding Turing completeness by stating No type is Turing complete, ensuring that computations remain bounded and predictable.

Sources

Related papers