HTML reading edition · 87 source pages · Open the source PDF

Consistent histories: enforcing linearity and excluding double-spending amongst collaborating controllers

Murdoch J. Gabbay Heliax and Isaac Sheff Heliax aHeliax AG * E-Mail: jamie@heliax.dev,isaac@heliax.dev

Abstract

We address the consistent histories problem: how to ensure that linear digital resources (such as tokens of fiat currency, of cryptocurrency, records of title, exclusive locks, and so on) remain linear across execution traces that span multiple independent collaborating controllers (state machines), without a single trusted global authority. This problem underlies a wide range of practical challenges, including atomic swaps, cross-chain bridges, interchain messaging, and tokenised settlement. A solution to this problem would address an important outstanding theoretical issue in the mathematics of banking and cryptocurrency. We propose a mathematical framework based on a novel notion of sequential located semilattices with Cut. In this model, each controller (communicating state machine) maintains a bounded semilattice of times (= some abstraction of controller state), such that incomparable elements join to a distinguished top element representing inconsistency. Controllers attest to each other’s times via an attestation operation that is controller-preserving, expansive, and contradiction-preserving. A carefully designed family of flags on times enables us to introduce a Cut operation, which prunes history, thus reducing storage cost. Our main result states that any inconsistent execution trace contains an active inconsistent index (an inconsistency that has not been cut away). We further provide an even stronger absolute consistency criterion, which has the advantage of being independent of trust assumptions, at the expense of being a little harder to prove. In particular, Cut is safe: the only way to remove byzantine behaviour from history is to introduce new byzantine behaviour into the history, so that if a pruned history is safe, then the original history must have been safe. Our framework is constructive in the sense that we exhibit explicit models, including one which is close to a realistic implementation, such that times are tuples carrying cryptographic digests of attested controller states. The mathematics in this paper has been formalised in Lean 4 and the formalisation is available online.

Keywords: Consistent history ; controllers ; distributed systems ; decentralised computation

References 84

1. Introduction

1.1. Setting the scene

The reader has probably lain awake at night worrying how we can solve the consistent histories problem: how multiple independent state machines (‘controllers’) can collaborate on linear resources without a single trusted authority, while excluding double-spends.

If the reader has not worried about this, then they probably should, because this is arguably the fundamental problem of digital assets, and digital assets run (large parts of) the world, and the world has multiple controllers.

It is the recurring safety problem behind atomic swaps [Tyg96][BHG87, §7.3], cross-domain asset transfers [Com92] and cross-chain bridges [Her18, Goe24], interchain messaging [Goe20], and tokenised asset settlement [Ban23, Ban25, BB23, BBE25]: excluding double-spends and ensuring consistent spend histories. To this difficult and vital problem, we offer the following response:

Use sequential located semilattices with Cut, as per the mathematics in this paper.

The definitions and proofs in this paper have been formalised in the Lean 4 theorem prover, complete with instructions for use and linkages between the results in this paper and their formalised Lean code. The interested reader can download the files [Har26] and run the verification locally.

We will now explain the issue and unpack the jargon.

1 2 3a bcd efgh
Figure 1. The exponential cake (Example 1.2.1)

1.2. The exponential cake

Example 1.2.1

Figure 1 illustrates the problem of non-linearity with a cake that you can have, and also eat. This is of course ridiculous, which is our point. We spell out the sequence of events:

• Controller 1 sends a cake to Controller 2.

• Controller 2 illegally copies the cake. This is a non-linear operation:

– It is non-linear in the ‘linear logic’ sense that the cake is ‘spent’ more than once, thus treated as an exponential resource [Gir87].1

– It is non-linear in the geometric sense that the two spends cannot legally exist on a single, sequential (thus linear), timeline.

Accordingly, Controller 2 creates two distinct timelines, one for each of the two copies of the cake, as illustrated.2

• From the first timeline, Controller 2 sends the cake back to Controller 1.

• From the second timeline, Controller 2 sends the cake to Controller 3.

• Controller 3 passes the cake back on to Controller 1.

Note here that:

1. Controller 1 never directly interacts with the second timeline of Controller 2. As far as Controller 1 is concerned, it has simply received two cakes: one from Controller 2 and another from Controller 3. How nice!
The only way for Controller 1 to detect that a double-spend has occurred is to compare the two cakes’ histories and note that their provenance goes back to 𝑐 and 𝑓, a non-sequential pair of events (i.e. a forked timeline) from Controller 2.

2. There is no global Controller (state machine). This example happens across multiple independent interacting state machines: Controllers 1, 2, and 3. They have no visibility of each other, aside from the tokens they exchange.

Thus, the double-spend on Controller 2 makes Controller 2 faulty, but Controllers 1 and 3 are honest. Yet, Controller 2’s double-spend has propagated, via the tokens it has sent, to affect the other controllers.

This paper provides mathematics that allows Controllers 1 and 3 to detect that an illegal operation has occurred — as in the case of Controller 2’s construction of an exponential cake — while imposing minimal costs and restrictions on the system. Examples of costs that are not minimal include: all controllers trust one another because it is assumed that only incorruptible institutions are allowed to become controllers; there is only One Controller, so the problem is trivial; tokens are stateless and all token transfers are symmetrically reversed (i.e. token transfers should be ‘perfectly bracketed’); or, everything that ever happens to a resource gets recorded on that resource and stored, for every resource, forever. As we will see, our solution is both more efficient and more flexible than all of the above. And while the maths to prove this is highly nontrivial, the actual construction is quite simple, involving just three flags and a so-called Cut rule.

1.3. Jargon: linear tokens across independent controllers

A linear token is just some digital resource that is supposed to be used once. The word ‘token’ may have connotations of blockchains, but here we intend the word more generally: examples include cryptocurrency tokens; or tokens of some fiat currency;3 a record of a title to a house; a digital record of some item on a container ship; or even a digital permission, such as an exclusive write lock.

A controller is an independent state machine.4 This could be a blockchain; or the accounts ledger of a bank; or a national Land Register (a national database of home ownership); or a shipping company’s database. A controller is anything that can evolve its own state, without necessarily depending on anything external.

By independent collaborating controllers we mean that there are multiple controllers — multiple independent state machines — each evolving their local state independently of the others, but in collaboration with them by exchanging messages and/or tokens.

Immediately, a problem arises: digital resources can be copied. In technical jargon, they are naturally non-linear. There is no a priori reason that a token that is supposed to be linear (= used once), could not be copied and used twice. In the blockchain literature this is called a double-spend (see Subsection 1.4).

We can now abstract to the following mathematical scenario:

• We fix a set P of state machines which we call controllers.

• Controllers perform state transitions, and may collaborate by sending each other tokens (= resources).

This abstraction of communicating state machines is a simple but fair representation of how tokenised systems actually collaborate. And even in this simple model, we see the problem: if controller 𝑝 sends a token to controller 𝑞, and controller 𝑞 is unsafe and breaks linearity by double-spending that token, then the entire system is at risk of becoming unsafe, because any action that requires multiple tokens might use tokens whose provenance includes both sides of the double-spend, i.e. which are dependent on two spends that cannot be put in linear order (because they both spend the same token).

1.4. Existing work

The precise term ‘double spend’ predates blockchain. The first use we can find in print is a conference paper presented in 1989 and published in conference proceedings in 1990 [Cdv+90] (see page 298 item 3, “When double spending of a check is found”). The term appeared in a popular science article in Scientific American in 1992 [Cha92] and was standard by the time Nakamoto used it in 2008 [Nak08]. The actual concept of a double spend in the context of digital tokens seems to originate in a paper from 1983 [Cha83] (see page 202, subsection 3.3 ‘Deposit Transaction’, item 11: “Bank adds note to comprehensive list of cleared notes and stops if note already on list”).5

The consistent-histories problem has many names. In blockchain systems it is studied as atomic cross-chain swap, bridge, wrapper, and general cross-ledger communication safety [Her18, HLS22, ZABZ+21, BVGC21, ZHL+19]. In distributed databases and distributed systems, related concerns appear as serialisability, atomic commitment, consensus-based transaction commit, and linearisability [Pap79, BG81, GL06, HW90]. In financial-market infrastructure, the same family of problems is discussed using the vocabulary of delivery-versus-payment, payment-versus-payment, tokenised deposits, tokenised reserves, unified ledgers, and atomic settlement [Com17, BE18, SKL20, Ban23, KLRZ25, Adr26]. Finally, the linear-resource aspect of the problem is naturally related to the vocabulary of linear logic [Gir87], which is part of why we name our Cut rule ‘Cut’ (the other reason being, of course, that it literally does cut controllers); and the exponential cake from Figure 1 is thus called because (like the exponential modality of linear logic) it can be copied and deleted.6

In this paper, we abstract away from domain-specific mechanisms. We give an order-theoretic treatment of independently evolving controllers connected by attestation, which we use to study how we can compress local history using Cut, while retaining the ability to detect contradictory spend histories.

1.5. The One True Controller (isn’t there)

Can we dissolve the problem by assuming all transactions settle on a single global controller? We argue that this is not realistic, because:

1. Major institutions — banks, central banks, blockchain communities — will not delegate their state to a common authority, for cultural and competitive reasons.

2. A successful candidate One True Controller would face prohibitive congestion and rent-seeking pressure: see the recent BIS working report [Shi26] and accompanying Financial Times analysis [Nan26].

3. Even if the One True Controller were built, applications benefiting from weaker trust models would split off, recreating the multi-controller world. The plural in “consistent histories” is essential: we need consistency across controllers, not consistency within one (which is a distinct and easier problem).

1.6. Outline of the solution: reducible controller tags

We start with a naive solution to the consistent histories problem:

Tag every resource with its complete history. These tags are carried around with the resource, and grow with each operation on it.

With the naive solution, it is easy to check for double-spends: for any two resources, just check their resource tags to see if they share an ancestor, or more generally, if they share an ancestor that was supposed to be linear but which was consumed by two distinct transactions.

Unfortunately, the naive solution is quite expensive. Every resource has to carry a complete history of everything that has happened to it, and everything it depends on, and everything that happened to its dependencies, and everything they depend on, and so on, transitively. Every token transfer imposes a cost not just now but on everything that comes after that transfer, cumulatively and forever. Can we do better?

We propose a more sophisticated solution, which comes in two parts:

1. Tags carry a reduced (= edited) version of the resource’s history. This reduced history tag grows as the resource evolves ...

2. ...but in certain circumstances controllers may carry out a Cut operation to edit (‘cut out’) parts of a tag that are no longer necessary, thus reducing its size.7

Concretely, a tag is structured as a path of times carrying flags which record each controller’s role in the history (a ‘next-index pointer’ to the next controller in the chain). The Cut operation (precise definition in Section 4) is a fully asynchronous operation which locally contracts three consecutive entries in a tag into two, eliminating a middle index while preserving contradiction structure.

Remark 1.6.1

The fundamental results of Cut are as follows:

• Theorem 5.6.2 and Corollary 5.6.3.
Consider the exponential cake example from Figure 1 and Example 1.2.1. Note that on the right-hand side of the Figure, we have two cakes, and the issue with this is not each individual piece of cake but the fact that the history of these two resources taken together is not consistent: it contains an illegal double-spend (specifically: 𝑐 and 𝑓 are contradictory).
So we want to analyse when a user can trust that their set of resources, taken together, has a consistent history.
Theorem 5.6.2 and Corollary 5.6.3 state that if the user trusts all of the active controllers in the tags of all of the resources in their current set of resources, then those resources have a consistent history, and in particular it contains no double-spends.
The power and the beauty of this is that the user does not need to trust controllers of cut tags: to ensure consistent histories, it is enough to trust what is active (and be right in those trust assumptions; but see next item).8

• Theorem 6.4.3 and Corollary 6.4.6.
These strengthen the previous results, at the cost of a bit more computation (a discussion is in Subsection 6.1 and Example 6.4.9). We show how one can prove — without trust assumptions on correct behaviour by controllers, but at the cost of a bit more work — that a set of tagged resources has a consistent history, even when the tags have been reduced using Cut operations.

Symbol Meaning ReferenceBounded semilattices & top-trees L = (X, ∨, ⊥, ⊤) bounded semilattice with join, bottom, top D.2.1.1𝑡∨𝑡′semilattice join D.2.1.1𝑡⪯𝑡′, 𝑡≺𝑡′derived (strict) partial order on times D.2.1.1⊤, ⊥ top (inconsistent) and bottom (consistent) elementsD.2.1.1𝑡⚡ 𝑡′𝑡contradicts 𝑡′, i.e. 𝑡∨𝑡′ = ⊤ D.2.1.3Located semilattices Ctrl, Time sets of controllers and times D.2.2.2ctrl(𝑡) the controller of time 𝑡 D.2.2.2𝑡#𝑠 attestation: “𝑡attests to 𝑠” D.2.2.2Time@𝑝times controlled by 𝑝 D.2.2.2⊤𝑝, ⊥𝑝top and bottom of Time@𝑝D.2.2.2CTime, CTime@𝑝consistent times (overall, and at 𝑝) N.2.2.4Flags and Cut Q : Time →Time a flag: controller-preserving, expansive D.3.1.1𝑡= Q𝑡has the flag Q (and is consistent) D.3.1.2flag(𝑡) the (unique) flag of 𝑡, or undef D.3.1.4↰𝑖,⋊𝑖,⋉𝑖nextindex-𝑖, cutme-𝑖, cutyou-𝑖flags D.3.2.1CuttingFlag the flag-set ⋃𝑖∈N{↰𝑖,⋊𝑖,⋉𝑖} D.3.2.1Paths, derivations, circuits 𝑇, Path(L) a path (right-to-left tuple of times); set of pathsD.4.1.1Π a derivation deriving a path 𝑇= root(Π) D.4.1.1𝑇[𝑖], Π[𝑖] 𝑖-th element of 𝑇, of root(Π) D.4.1.1index(𝑇), index(Π) the set of indexes of 𝑇, of Π D.4.1.1𝑇{𝑗:=𝑡} 𝑇with the 𝑗-index value replaced by 𝑡 N.4.1.2(𝑇,𝑇′), (Π, Π′) circuit; circuit-derivation D.4.3.1Active machinery and closure |𝑇|𝐶the 𝐶-closure of a set of times 𝑇 D.6.2.1actIndex(Π, Π′) active indexes of a circuit-derivation D.6.4.1actTime(Π, Π′), actCtrl(Π, Π′) active times; active controllers D.6.4.1Alternative presentation Expan(X) expansive functions X →X, pointwise or- deredD.7.2Y ⇒X attestations from Y to X D.7.2𝑥#𝑦 attestation, written postfix #(𝑦)(𝑥) D.7.2separating, monotone optional properties of an attestation D.7.5#𝑞,𝑝: Time@𝑞⇒Time@𝑝component attestation D.7.6CuttingPoset cutting-flag poset D.7.7𝑡#Q = 𝑡#ctrl(𝑡)Q induced flag action by the alternative Cut presentationD.7.7
Figure 2. Map of notation, with pointers (Subsection 1.7)

The power of this is that no trust assumptions (whether correct or not) are required, and furthermore, consistency can be demonstrated between users who might not share the same trust assumptions.

The overall effect of this mathematics is to provide a space-efficient operation Cut which, in senses we make mathematically formal, safely minimises trust assumptions. With Cut, tokens need not be forever burdened with detailed tracing of the controllers through which they have travelled. This makes cross-controller transfers more economical, since they need not impede the fungibility of the token.

We can view Cut as a potent generalisation of the token-wrapping technique used in ICS-20 [Goe24]. This was originally designed to make it possible for an application to temporarily transfer tokens to another controller (perhaps for speed or co-location with other tokens), and then transfer them back. This is a common and desirable pattern. The generalisations here, which are significant, are that:

1. Cut is not a wrapper and does not require tokens to necessarily be immediately unwrapped in the same order they were wrapped, and

2. Cut allows stateful tokens whereas wrapping cannot (i.e. our cake can transition to an ‘eaten’ state).

So Cut is more general and more powerful than ICS-20; but still, it is in a similar spirit.

1.7. Map of paper

1. Section 1 is the Introduction. You Are Here.

2. Section 2 introduces the notion of a top-tree (sequential bounded semilattice) in Definition 2.1.1. This is a model of sequential computation, possibly with non-sequential behaviour. We also introduce the notion of a located semilattice in Definition 2.2.2, which is a suitable notion of forest of top-trees.

3. Section 3 introduces a located semilattice with Cut in Definition 3.2.1.

4. Section 4 introduces paths 𝑇, derivations Π, initial prefixes, circuits (Π, Π′), active indexes, and (active) inconsistency of circuit-derivations.

5. Section 5 proves many results (a map of them is at the start of the Section), including Theorem 5.6.2 and corollaries, that an inconsistent circuit-derivation has an active inconsistent index.

6. Section 6 strengthens this to an absolute criterion using a notion of C-closure of a set of times, in Theorem 6.4.3 and corollaries.

7. In Section 7 we return to the notion of located semilattice and give an alternative, and in a sense more abstract, characterisation of its structure.

8. Section 8 concludes with a discussion of the mathematics, and comments on related and future work.

9. For the reader’s convenient reference, we collect the main definitions and notation of this paper in Figure 2, with pointers.

List of Figures

1The exponential cake (Example 1.2.1)4

2Map of notation, with pointers (Subsection 1.7)9

3Example of a top-tree (a sequential bounded semilattice; Remark 2.1.5)12

4A sequential located semilattice as a forest of top-trees with controller-preserving, expansive, contradiction-preserving attestation (Remark 2.2.3)17

5The exponential cake as a sequential located semilattice (Example 2.3.4).20

6Flag ordering in Definition 3.2.128

7Times (Definition 3.4.3(2))36

8Attestation (Definition 3.4.3(3))36

9Derivations (Definition 4.1.1(4))38

10Two visualisations of (Cutk,j,i) (Remark 4.1.4(7))43

11Proof dependency diagram for Section 547

12Illustration of Lemma 5.2.249

13C-closure of T (Definition 6.2.1)64

14Future work: the exponential bike (Remark 8.4.1)84

2. Located semilattices

2.1. Top-trees (sequential bounded semilattices)

We start with a very simple model of sequential computation with ‘algebraic fork detection’. Definition 2.1.1 is an abstract description of the transition system of a single controller (= state machine); the reader who prefers diagrams might find it helpful to look at Figure 3 and at the worked example in Example 2.1.4.

Definition 2.1.1

1. A bounded semilattice is a tuple

L = (X, ∨, ⊥, ⊤)

such that:

(a) X is a set of elements which we may call states or times.

Above, elements increase left-to-right, so that intuitively time flows from left to right.

(b) ∨ : X2 → X is an idempotent, commutative, and associative binary operation which we may call the join of the semilattice.

(c) As standard, write 𝑡≤𝑡′ when 𝑡∨𝑡′ = 𝑡′, and note that this gives L the structure of a partial order. We may also write 𝑡< 𝑡′ or 𝑡< 𝑡′ when 𝑡≤𝑡′ ∧𝑡≠𝑡′.

(d) ⊥, ⊤∈ X are bottom and top elements such that

∀𝑥∈X.⊥≤𝑥≤⊤.

2. Call 𝑡 and 𝑡′ incomparable when 𝑡≰𝑡′ ∧𝑡′ ≰𝑡.

3. Call a bounded semilattice L sequential when for every 𝑡,𝑡′ ∈ X we have

𝑡∨𝑡′ ∈{𝑡,𝑡′, ⊤}.

4. We may call ⊤ the inconsistent element and we may call a 𝑡∈L such that 𝑡≠⊤ consistent.

5. We may call a sequential bounded semilattice a top-tree for short; see Remark 2.1.5.

⊥ ⊤
Figure 3. Example of a top-tree (a sequential bounded semilattice; Remark 2.1.5)
Lemma 2.1.2

Suppose that L = (X, ∨, ⊥, ⊤) is a bounded semilattice (Definition 2.1.1(1)), and write ≤ for the partial order on X defined by 𝑡≤𝑡′ when 𝑡∨𝑡′ = 𝑡′. Then the following are equivalent:

1. L is sequential (Definition 2.1.1(3)).

2. For every 𝑡,𝑡′ ∈ X, (𝑡≰𝑡′ ∧𝑡′ ≰𝑡) =⇒𝑡∨𝑡′ = ⊤. In words: incomparable elements have an inconsistent join.

3. (X∖{⊤}, ≤) is a tree with ⊥ as its root. More formally: for every 𝑥∈ X∖{⊤}, ≤ is a linear order on {𝑥′ ∈ X | 𝑥′ ≤𝑥} with ⊥ as a least element.9

In words: a top-tree is a tree with a top.

Proof

By routine calculations. □

Definition 2.1.3 (Contradiction).

Suppose L = (X, ∨, ⊥, ⊤) is a bounded semilattice and suppose 𝑡,𝑡′ ∈ X.10 Define that 𝑡 contradicts 𝑡′, or that 𝑡 and 𝑡′ contradict, and write 𝑡⚡ 𝑡′, as follows:11

𝑡⚡ 𝑡′when 𝑡∨𝑡′ = ⊤.
Example 2.1.4 (Worked example of a top-tree and its joins and contradictions).

Define X = {⊥,𝑎,𝑏,𝑐,𝑑, ⊤} and order these elements by the reflexive-transitive closure of

⊥< 𝑎< 𝑏< ⊤ ⊥< 𝑎< 𝑐< ⊤ ⊥< 𝑑< ⊤.

Thus 𝑏 and 𝑐 are incomparable continuations of the partial history 𝑎, while 𝑑 lies on a separate branch.

⊥𝑎 𝑑𝑏 𝑐⊤

Some example joins (least upper bounds) are:

𝑎∨𝑏= 𝑏 𝑎∨𝑐= 𝑐 ⊥∨𝑥= 𝑥𝑏∨𝑐= ⊤ 𝑏∨𝑑= ⊤ 𝑐∨𝑑= ⊤ 𝑥∨⊤= ⊤

Thus when two consistent elements lie on the same branch, their join is the later one. When two consistent elements lie on different branches, their join is ⊤, reflecting that the two histories are incomparable and cannot be placed on a single sequential branch. For example 𝑏⚡ 𝑐 and 𝑏⚡ 𝑑, but not 𝑎⚡ 𝑏.

Remark 2.1.5

We can think of a sequential bounded semilattice structurally as a tree representing the branching structure of possible evolutions of some sequential process, with a top element ⊤ adjoined to represent computations that have deviated from admissible paths, as illustrated in Figure 3 and in Example 2.1.4.12

Why do we call ⊤ ‘inconsistent’, and ⊥ (if ⊥≠⊤) ‘consistent’?13 We can reply that ⊥ and ⊤ are just bounding elements in the semilattice: we can call them what we want. Fair enough, the reader might respond, but by what intuition would we want to call ⊤ ‘inconsistent’, and ⊥ (if not equal to ⊤) ‘consistent’?

We are interested in modelling Byzantine (= faulty / hostile) behaviour, thus, we want our branching structure to reflect the possibility that the process might not be sequential (even though this is faulty behaviour). So we need a top value, to represent nonsequentiality.14

Thus, a sequential bounded semilattice is a tree, with a top element; thus, a top-tree.

The top element is the least upper bound of any pair of elements coming from distinct branches of the body of the tree. This neatly represents non-sequential behaviour, i.e. behaviour that is ‘inconsistent’ with being on any single branch of the behaviour tree.

Or to put it another way, ⊤ is an ‘algebraic fork detector’; it is where we go when we detect a fork.

Conversely ⊥ describes a process that has displayed no behaviour, or no behaviour aside from initialising, and this behaviour is ‘consistent’ with being on any branch of the behaviour tree, i.e. it is the root of the tree.

The reader is welcome to think of ⊤ however they find most intuitive: e.g. as a top element, as an exception value, as a point at infinity, as a fork detector, or as a final element.

We mention two elementary lemmas which will be useful later:

Lemma 2.1.6 (Monotonicity of contradiction).

Suppose L = (X, ∨, ⊥, ⊤) is a bounded semilattice and suppose 𝑡,𝑡′,𝑢,𝑢′ ∈ X. Then

(𝑡≤𝑢∧𝑡′ ≤𝑢′) =⇒𝑡⚡ 𝑡′ =⇒𝑢⚡ 𝑢′.
Proof

𝑡⚡ 𝑡′ just means 𝑡∨𝑡′ = ⊤ and similarly for 𝑢⚡ 𝑢′. The result follows by monotonicity of join. □

Lemma 2.1.7

Suppose L = (X, ∨) is a sequential bounded semilattice and suppose 𝑡,𝑡′ ∈ X and 𝑡,𝑡′ ≠⊤ (so 𝑡 and 𝑡′ are consistent). Then 𝑡 and 𝑡′ are incomparable if and only if they contradict.

Proof

By routine arguments from Definitions 2.1.3 and 2.1.1(3). □

Remark 2.1.8 (Design alternatives: preorders vs posets).

Definition 2.1.1 makes a top-tree a poset (with antisymmetry: 𝑡⪯𝑡′ ∧𝑡′ ⪯𝑡=⇒𝑡= 𝑡′). Relaxing to a preorder would permit coequal but non-equal elements — that is, two elements each of which is ⪯ the other, but which differ. This is distinct from a fork, in which neither element is ⪯ the other.

Coequality might be useful, e.g. when two changes to unrelated state commute, or when a concrete model carries intensional structure that is not visible to ⪯.

Since any preorder quotients to a poset, there is no essential mathematical difference here. We choose posets here as a simple and convenient design point.

Remark 2.1.9

Top-trees are not a complicated idea — just a tree with a top element — but to our knowledge they have not previously been precisely identified in the literature as an algebraic definition. A notion of top-tree appears in [AHLT05] as a data-structure interface for fully dynamic forests; this is not connected to the top-trees from Definition 2.1.1.

2.2. Located semilattices

Remark 2.2.1 (Top-trees + attestation).

Top-trees from Definition 2.1.1(5) arise very naturally from sequentiality/serialisability: they abstract the state of a sequential, possibly Byzantine process.

We now add a notion of attestation to our model. Intuitively, attestation is how one location (or process) can update its view of the state of another location (or process).

A special feature of how we formulate attestation is that

controllers can attest to each other opportunistically: attesting to some other controller does not limit a controller’s future actions (aside from not being able to consistently attest to directly contradictory states from that same other controller).

This matters. It ensures that cross-controller applications can operate swiftly and smoothly (or at least, if they do not, it is not because any controller feels reluctant to make attestations).

For example, in Figure 1, if controller 1 attests to one fork of controller 2, and controller 3 attests to another fork of controller 2, it is crucial that controllers 1 and 3 can still attest to each other. Attesting to one controller never limits your ability to attest to another controller.

The only thing a controller cannot consistently do is to attest to directly contradictory states at the same controller: if, in Figure 1, controller 1 attests to 𝑐, then it cannot later attest to 𝑓 (or any element after 𝑓). But this does not inherently limit the actions of controller 1; it just makes controller 1 a

good observer of the world around it, and able to detect Byzantine behaviour. In particular, it is not contradictory for controller 1 to attest to 𝑐 and also to attest to controller 3 having attested to 𝑓. We will return to this point in Subsection 8.2.3 (non-transitivity of attestation).

We are now ready to formally define located semilattices and attestation:

Definition 2.2.2

A located semilattice consists of a tuple

L = (CtrlL, TimeL, #L : Time2 L →TimeL, ctrlL : TimeL →CtrlL)

— we may drop the L subscripts henceforth — where

1. Ctrl is a set of controllers, and Time is a set of times.

2. ctrl : Time → Ctrl assigns to each time 𝑡∈ Time a controller ctrl(𝑡), which we call the controller or the location of 𝑡.

3. # : Time2 → Time is an attestation function. By convention # associates to the left, so that 𝑠#𝑡#𝑢 means (𝑠#𝑡)#𝑢.

4. If 𝑝∈ Ctrl then we define Time@𝑝 the times at 𝒑 by

Time@𝑝= {𝑡∈Time | ctrl(𝑡) = 𝑝}.

5. For each controller 𝑝∈ Ctrl,

(Time@𝑝, #|Time@𝑝)

(i.e. the set of times controlled by 𝑝, where #|Time@𝑝 is # restricted to times in Time@𝑝) forms a bounded semilattice (Definition 2.1.1), with # as its join.

6. In view of point 5 above, we may use notation as follows, for 𝑡,𝑡′ ∈ Time and ctrl(𝑡) = 𝑝= ctrl(𝑡′):

(a) We may write 𝑡#𝑡′ as 𝑡∨𝑡′, because as per point 5 the times controlled by the controller 𝑝= ctrl(𝑡) = ctrl(𝑡′) form a semilattice under #.

(b) We may write ⪯ for the partial order of Time@𝑝, thus for 𝑡,𝑡′ ∈ Time@𝑝 we have 𝑡′ ⪯𝑡 when 𝑡∨𝑡′ = 𝑡 (and equivalently, when 𝑡#𝑡′ = 𝑡). We may also write 𝑡′ ≺𝑡 to mean 𝑡′ ⪯𝑡∧𝑡≠𝑡′.

(c) We may write ⊤𝑝 for the top element and ⊥𝑝 for the bottom element in Time@𝑝.

(d) Following Definition 2.1.1(4) and Remark 2.1.5, we may call ⊤𝑝 the inconsistent time at 𝑝, and we may call any 𝑡∈ Time@𝑝 such that 𝑡≠⊤𝑝 a consistent time. We may drop the 𝑝 subscript where this is unimportant or clear from context, writing just ⊤ and ⊥. For example, 𝑡= ⊤ is short for 𝑡= ⊤𝑝 (where recall that 𝑝= ctrl(𝑡)).

7. We assume the following properties of # for every 𝑡,𝑡′,𝑠,𝑠′ ∈ Time such that ctrl(𝑡) = ctrl(𝑡′) and ctrl(𝑠) = ctrl(𝑠′):

(a) Attestation is controller-preserving:

ctrl(𝑡#𝑠) = ctrl(𝑡)

(b) Attestation is expansive:15

𝑡⪯𝑡#𝑠

or equivalently: (𝑡#𝑠)#𝑡= 𝑡#𝑠.

(c) Attestation is contradiction-preserving (⚡ is from Definition 2.1.3): 𝑠⚡ 𝑠′ implies 𝑡#𝑠⚡ 𝑡′#𝑠′ Intuitively: attesting to a contradiction is a contradiction; in the language of blockchain, attesting to a fork is a fork; and in the language of order-theory, attesting to incomparable times leads to incomparable times.

8. If Time@𝑝 is sequential for every 𝑝∈ Ctrl, then we may call L a sequential located semilattice.

⊥𝑝⊤𝑝𝑡𝑡#𝑣 𝑡#𝑢⊥𝑞⊤𝑞𝑢𝑢#𝑣𝑢#𝑣′⚡⊥𝑟⊤𝑟𝑣𝑣′⚡####𝑣⚡ 𝑣′ =⇒𝑢#𝑣⚡ 𝑢#𝑣′Above, times increase horizontally left-to-right from ⊥to ⊤. The vertical organisation of controllers 𝑝, 𝑞and 𝑟is not significant; they are not ordered. Dashed arcs represent selected attestations across controllers. The 𝑞-controlled tree attests to contradictory times 𝑣and 𝑣′ from the 𝑟-controlled tree, producing contradictory times 𝑢#𝑣and 𝑢#𝑣′ in the 𝑞-controlled tree. The 𝑝-controlled tree illustrates additional incoming attestations from both 𝑟and 𝑞.
Figure 4. A sequential located semilattice as a forest of top-trees with controller-preserving, expansive, contradiction-preserving attestation (Remark 2.2.3)
Remark 2.2.3

1. Visually, we can imagine a sequential located semilattice from Definition 2.2.2 as a forest of top-trees (sequential bounded semilattices), as illustrated in Figure 4 (note: we illustrated a top-tree in Figure 3).

2. The diagram also illustrates what makes a sequential located semilattice more than just a forest of top-trees: the attestation function #. Attestation # plays a dual role in a located semilattice:

(a) Within a single controller (i.e. a controller attesting to itself), # behaves like semilattice join. So if ctrl(𝑡) = ctrl(𝑡′) = 𝑝∈ Ctrl then 𝑡#𝑡′ is the semilattice join ∨ on Time@𝑝. It is idempotent, commutative, and associative, with bottom ⊥𝑝 and top ⊤𝑝. It is also the mechanism by which sequential histories are compared: 𝑡#𝑡′ is equal to 𝑡 (when 𝑡′ precedes 𝑡), or equal to 𝑡′ (when 𝑡 precedes 𝑡′), or equal to ⊤𝑝 (when 𝑡 and 𝑡′ are on distinct branches of the top-tree (Time@𝑝, ∨).

(b) Across distinct controllers (i.e. a controller attesting to a distinct controller) # is how one controller records information about (‘attests to’) another controller. So if 𝑝= ctrl(𝑡) ≠ ctrl(𝑠) then 𝑡#𝑠 is a 𝑝-controlled time. The operator # is not necessarily commutative or associative, but it is expansive, meaning that 𝑡⪯𝑡#𝑠, and this encodes that 𝑝 advances its local time by recording information about 𝑠. Contradiction is transported across #: if 𝑠⚡ 𝑠′ then 𝑡#𝑠⚡ 𝑡′#𝑠′.

Some notation will be useful:

Notation 2.2.4

1. Suppose L = (CtrlL, TimeL, #, ctrlL) is a located semilattice. We may drop the L subscripts. Write CTime for the set of consistent times in Time, and if 𝑝∈ Ctrl then we may write CTime@𝑝 for the consistent times in Time controlled by 𝑝. In symbols:

CTime = Time ∖{⊤𝑝| 𝑝∈Ctrl} CTime@𝑝= CTime ∩Time@𝑝= {𝑡∈Time | ctrl(𝑡) = 𝑝∧𝑡≠⊤𝑝}

2. Recall that Definition 2.1.3 defines 𝑡⚡ 𝑡′ to mean 𝑡∨𝑡′ = ⊤ where 𝑡 and 𝑡′ are elements of a bounded semilattice. However, in Definition 2.2.2(7c) we write 𝑠⚡ 𝑠′ for 𝑠 and 𝑠′ elements of a located semilattice (not a bounded semilattice). We can do this, because in that Definition we also assumed ctrl(𝑠) = ctrl(𝑠′), and we insisted in Definition 2.2.2(5) that for a controller 𝑝, (Time@𝑝, #|Time@𝑝) (the set of times controlled by 𝑝) does indeed form a sequential bounded semilattice, with # as its join. So far, so good.

We extend 𝑠⚡ 𝑡 to the case where 𝑠,𝑡∈ Time and 𝑠 and 𝑡 do not necessarily have the same controller, as follows:

(a) If ctrl(𝑠) = ctrl(𝑡) then 𝑠⚡ 𝑡 when 𝑠∨𝑡= ⊤ctrl(𝑠), just as in Definition 2.1.3.

(b) If ctrl(𝑠) ≠ ctrl(𝑡) then ¬(𝑠⚡ 𝑡). In words: times at distinct controllers cannot contradict.

Lemma 2.2.5

Suppose L = (CtrlL, TimeL, #, ctrlL) is a located semilattice and 𝑠,𝑡∈ TimeL. Then

• if 𝑠⚡ 𝑡

• then ctrl(𝑠) = ctrl(𝑡) and 𝑠∨𝑡= ⊤ctrl(𝑠).

Proof

This just repackages the discussion in Notation 2.2.4(2). □

Remark 2.2.6 (A note on terminology).

Attestation is an expansive operator, as per Definition 2.2.2(7b). Later on we will encounter flags, which are also expansive, as per Definition 3.1.1(2). So expansivity is a recurring theme in our development.

The property of an operator 𝑃 being expansive — 𝑥≤𝑃𝑥 — is also called inflationary or extensive in the literature. We prefer expansive because: ‘expansive’ has a convenient noun ‘expansivity’, whereas arguably ‘inflationary’ does not (‘inflationarity’? ‘inflativity’? ‘inflation’ would work but is less direct); and it is unambiguous (‘extensive’ and ‘extensivity’ sound like ‘extensional’ and ‘extensionality’). Tastes differ so if the reader prefers inflationary or extensive then they are welcome to mentally translate and no harm will come of it.

Remark 2.2.7 (Design alternatives).

Definition 2.2.2 will serve our needs very well in what follows, but there are certainly ways we can imagine to reformulate or generalise it. Two may deserve particular mention:

1. A slightly different way of looking at the same ideas is presented in Section 7. Depending on taste, the reader might prefer it, and if so they are welcome to skip ahead.

2. Attestation # from Definition 2.2.2(3) is single-shot: it takes one time 𝑡 and one time 𝑠 and forms one time 𝑡#𝑠. We could structurally generalise this to a multi-shot version 𝑡#𝑆, where 𝑆 is a set of times — perhaps 𝑆 is some set of prerequisites or preconditions for the controller of 𝑡 to make progress, and this set does not come in any particular order and perhaps it is convenient for this to be structurally reflected in the attestation. We do not do this here because the single-shot version will be entirely sufficient for our needs. Should our needs change in future work, there would be no structural barrier to such a generalisation.

⊥1⊤1𝑎 𝑑 𝑒 ℎ⊥2⊤2𝑏𝑐𝑓⚡⊥3⊤3𝑔####Above, times increase left-to-right. Dashed arcs represent selected attestations, mirroring the cake-passing arrows of Figure 1. Controller 2 forks at 𝑏into branches ending at 𝑐(upper) and 𝑓(lower). These branches are incomparable, so 𝑐⚡ 𝑓and their join is ⊤2, witnessing the double-spend.
Figure 5. The exponential cake as a sequential located semilattice (Example 2.3.4).

2.3. Examples of located semilattices

Remark 2.3.1

Located semilattices may be motivated by interacting state machines, but as a mathematical framework they have their own quite interesting identity. We give some examples to indicate how they can accommodate aspects of logical connectives, the exponential cake, games, state machines, and closure operators:

1. Example 2.3.2 is a simple but not self-evident example of a located semilattice attestation with two controllers and an attestation # whose cross-controller behaviour has the flavour of a simple three-valued logic connective.

2. Example 2.3.3 is an even simpler example, where the attestation # is just identified with logical ∨, regardless of whether it is cross-controller or not.

3. Example 2.3.4 moves away from truth-tables: we render the exponential cake as a located semilattice.

4. Example 2.3.5 moves further towards process-flavoured examples: we render the children’s game of paper-scissors-stone as a located semilattice.

5. Example 2.3.6 illustrates a state machine as a located semilattice. There are two participants: one represents the state machine, and the other represents inputs to that machine, via attestation.

6. Example 2.3.7 takes a new direction and has a more order-theoretic flavour. Attestation is identified with a closure operator.

This should give some sense for some of the things to which located semilattices can be applied.

Example 2.3.2 (A simple example).

Define a sequential located semilattice L = (Ctrl, Time, #, ctrl) such that:

• Ctrl = {P, Q} (so there are two controllers).

• Time = Ctrl × 3 where 3 = {f, b, t}. We endow 3 with the order

f < b < t

so that (𝑝, f) = ⊥𝑝 and (𝑝, t) = ⊤𝑝 for 𝑝∈ Ctrl. We let tv (short for ‘truth-value’, because 3 looks like values of a three-valued logic), and we define ∨ : 32 → 3 to be least upper bound and ¬(t) = f and ¬(f) = t and ¬(b) = b:

• ctrl(𝑝,𝑥) = 𝑝.

• We define # as follows:

(𝑝, tv)#(𝑝′, tv′) ={(𝑝, tv ∨tv′) 𝑝= 𝑝′(𝑝, tv ∨¬tv ∨tv′ ∨¬tv′) 𝑝≠𝑝′

Thus when 𝑝≠𝑝′, we have that (𝑝, tv)#(𝑝′, tv′) is equal to (𝑝, t) if tv ≠ b ∨ tv′ ≠ b, and is equal to (𝑝, b) if tv = tv′ = b.

This is a located semilattice:

• # is controller-preserving.

• # is expansive because (𝑝, tv)#(𝑝′, tv′) either returns (𝑝, t) or (if tv = tv′ = b) it returns (𝑝, tv).

• It is easy to check that # is contradiction-preserving.

Attestation is not monotone in either component. For example:

1. (𝑝′, f) ⪯(𝑝′, b) but

(𝑝, b)#(𝑝′, f) = (𝑝, t) ⪯̸ (𝑝, b) = (𝑝, b)#(𝑝′, b).

2. (𝑝, f) ⪯(𝑝, b) but

(𝑝, f)#(𝑝′, b) = (𝑝, t) ⪯̸ (𝑝, b) = (𝑝, b)#(𝑝′, b).
Example 2.3.3 (An even simpler example).

A simple variant of Example 2.3.2 is monotone. We take everything as in that example, except that we define (𝑝, tv)#(𝑝′, tv′) by

(𝑝, tv)#(𝑝′, tv′) = (𝑝, tv ∨tv′).

This too is controller-preserving, expansive, and contradiction-preserving. We will generalise this when we consider the principal attestation in Example 7.4(2).

Example 2.3.4 (The exponential cake as a sequential located semilattice).

We return to Figure 1 and interpret it as a located semilattice (Definition 2.2.2). We illustrate this in Figure 5.

The three Controllers correspond to Ctrl = {1, 2, 3}. Nodes 𝑎,𝑏,𝑐,𝑑,𝑒, 𝑓,𝑔,ℎ are times in Time, with ctrl(𝑎) = ctrl(𝑑) = ctrl(𝑒) = ctrl(ℎ) = 1, and similarly for Controllers 2 and 3.

Write 𝑐, 𝑓∈ Time@2 for Controller 2’s state on the forked branches sending the cake toward Controllers 1 and 3 (Figure 5 labels the pre-fork time 𝑏). By construction 𝑐 and 𝑓 are incomparable, so 𝑐∨𝑓= ⊤2, i.e. 𝑐⚡ 𝑓.

The dashed lines in Figure 5 are attestations. When Controller 2 receives the cake at event 𝑏, it advances its local time by attesting to Controller 1’s state at 𝑎. When Controller 1 receives a cake back at 𝑑, it attests to 𝑐 (along the upper branch); when Controller 1 later receives a cake via Controller 3 at ℎ, it attests to a state 𝑔 that transitively depends on 𝑓.

Example 2.3.5 (Paper-scissors-stone).

Define a sequential located semilattice L = (Ctrl, Time, #, ctrl) such that:

• Ctrl = {Alice, Bob} (so there are two controllers).

• Time = Ctrl × Play where Play = {⊥, paper, scissors, stone, ⊤}.
It is convenient to give Play a bounded semilattice structure such that ⊥≤ play ≤⊤ for every play ∈ Play, and there are no other comparisons (so for example paper ∨ scissors = ⊤)

• We define # as follows:

– (𝑝, play)#(𝑝, play′) = (𝑝, play ∨ play′) for 𝑝∈ Ctrl and play, play′ ∈ Play.

– For 𝑝≠𝑝′ ∈ Ctrl and play ∈ Play we define:

(𝑝, play)#(𝑝′, play′) = (𝑝, play) (play, play′) ∈{(paper, stone), (stone, scissors), (scissors, paper)}(𝑝, ⊤) otherwise

• ctrl(𝑝, play) = 𝑝.

Intuitively, this represents a simplified paper-scissors-stone game where attestation represents a play of the game:

• If a play survives the attestation unchanged, as in (𝑝, paper)#(𝑝′, stone) = (𝑝, paper) then this is a win.

• If a play goes to ⊤, then this represents a loss, a draw, or an invalid round.

This is a located semilattice:

• # is controller-preserving.

• # is expansive because (𝑝, play)#(𝑝′, play′) either returns (𝑝, play) or (𝑝, ⊤).

• # is contradiction-preserving. The argument is by cases. The nontrivial case is when 𝑝≠𝑝′ and play′ 1 ≠ play′ 2 ∈{paper, scissors, stone} so that

(𝑝′, play′ 1) ⚡ (𝑝′, play′ 2)

(meaning: (𝑝′, play′ 1) ∨(𝑝′, play′ 2) = ⊤𝑝′). Define

𝑣1 = (𝑝, play1)#(𝑝′, play′ 1) and 𝑣2 = (𝑝, play2)#(𝑝′, play′ 2).

– If 𝑣1 = (𝑝, ⊤) = ⊤𝑝 or 𝑣2 = ⊤𝑝 then 𝑣1 ⚡ 𝑣2 is immediate.

– If 𝑣1, 𝑣2 ≠⊤𝑝 then it must be that

(play1, play′ 1), (play2, play′ 2) ∈ {(paper, stone), (stone, scissors), (scissors, paper)}.

But we assumed play′ 1 ≠ play′ 2 and therefore play1 ≠ play2, and thus 𝑣1 ⚡ 𝑣2.

Note that attestation is not monotone in either component. For example:

1. (𝑝′, ⊥) ⪯(𝑝′, stone) but

(𝑝, paper)#(𝑝′, ⊥) = (𝑝, ⊤) ⪯̸ (𝑝, paper) = (𝑝, paper)#(𝑝′, stone).

2. (𝑝, ⊥) ⪯(𝑝, paper) but

(𝑝, ⊥)#(𝑝′, stone) = (𝑝, ⊤) ⪯̸ (𝑝, paper) = (𝑝, paper)#(𝑝′, stone).
Example 2.3.6 (The bureaucracy).

Define a sequential located semilattice L = (Ctrl, Time, #, ctrl) such that:

• Ctrl = {JosefK, Prozess} (so there are two controllers).

• Time = Ctrl × State where State = N ∪{⊤}. We let 𝑛 range over N = {0, 1, 2, . . . } and 𝑥 range over all of State. We endow State with the usual order on numbers, with ⊤ as a top element:

0 < 1 < 2 < · · · < ⊤.

• ctrl(𝑝,𝑥) = 𝑝.

• We define # as follows:

(𝑝, ⊤)#(𝑝′,𝑥) = (𝑝, ⊤) (𝑝,𝑛)#(𝑝′, ⊤) = (𝑝, ⊤) (𝑝,𝑛)#(𝑝′,𝑛′) = (𝑝, max(𝑛,𝑛′)) 𝑝= 𝑝′(𝑝,𝑛′) 𝑝≠𝑝′ ∧𝑛′ = 𝑛+1(𝑝, ⊤) otherwise

The reader can check that each Time@𝑝 is just ordered as State:

(𝑝, 0) ≺(𝑝, 1) ≺(𝑝, 2) ≺· · · ≺(𝑝, ⊤)

and this is clearly a sequential bounded semilattice. It is easy to check that # is controller-preserving and expansive. # is also contradiction-preserving, for suppose (𝑝,𝑥1) ⚡ (𝑝,𝑥2). It follows that 𝑥1 = ⊤ or 𝑥2 = ⊤ (or both). Then (𝑝′,𝑥′ 1)#(𝑝,𝑥1) = ⊤𝑝′ or (𝑝′,𝑥′ 2)#(𝑝,𝑥2) = ⊤𝑝′ as required.

# is not monotone in the first component. For each 𝑝≠𝑝′ ∈ Ctrl,

(𝑝, 0) ⪯(𝑝, 1) = (𝑝, 0)#(𝑝′, 1) yet (𝑝, 0)#(𝑝′, 2) = (𝑝, ⊤) ⪯̸ (𝑝, 2) = (𝑝, 1)#(𝑝′, 2).

This is non-monotonicity of a particularly illuminating kind. Attestation has a flavour of moving a sequential process forward: each (𝑝,𝑛) can only be moved forward by attesting to (𝑝′,𝑛+1); otherwise the attestation fails.

Imagine that 𝑝= Prozess is a bureaucratic system, implementing some process. 𝑝′ = JosefK is the person trying to navigate it. The state (𝑝,𝑛) represents that 𝑝 has correctly received (here modelled by ‘attested to’) forms 1 up to 𝑛, and in this state, 𝑝 is waiting for 𝑝′ to provide form 𝑛+1. There are infinitely many forms for 𝑝′ to fill in, and at each step 𝑝′ has to perfectly fill in precisely the correct next form or 𝑝 will reject it (this rejection is modelled mathematically by 𝑝 transitioning to ⊤𝑝= (𝑝, ⊤)).16 Thus for 𝑝≠𝑝′,

((𝑝, 0)#(𝑝′, 1))#(𝑝′, 2) = (𝑝, 2) yet ((𝑝, 0)#(𝑝′, 2))#(𝑝′, 1) = (𝑝, ⊤).

So “form 1, then form 2” succeeds (or at least, it does not fail), while “form 2, then form 1” fails.

We highlight this example because the non-monotonicity of attestation is (or rather, can be) here a feature of what we want to model. It reflects our underlying interest in modelling sequential processes. Thus, non-monotonicity is not a bug.

Lest Examples 2.3.5 and 2.3.6 give an impression that a monotone attestation would a priori be bad, we give an example in which on the contrary this is possible and meaningful:

Example 2.3.7 (Closure operators).

Define a structure L = (Ctrl, Time, #, ctrl) as follows:

• Fix some set Fact of facts.

• Let Ctrl be any nonempty set.

• For each 𝑝∈ Ctrl fix some set Infer𝑝⊆ pow(Fact) such that Infer𝑝 is closed under arbitrary (possibly empty, possibly infinite) set intersection, and ∅, Fact ∈ Infer𝑝 (the technical term for this is a closure system or Moore family [CM03, DP02]).
We call 𝐶∈ Infer𝑝 an inference. Thus, every inference is a set of facts, but not every set of facts is an inference.

• If 𝑋⊆ Fact then define

|𝑋|𝑝=⋂{𝐶∈Infer𝑝| 𝑋⊆𝐶}

and call this the 𝒑-closure of 𝑋. We think of |-|𝑝 as a notion of deduction by 𝑝; given a set of facts 𝑋, |𝑋|𝑝 is the inference that 𝑝 can draw from 𝑋. Note that each 𝑝 has its own notion of inference.17

• Time = {(𝑝,𝐶) | 𝑝∈ Ctrl,𝐶∈ Infer𝑝}. We endow Time with a partial order by

(𝑝,𝐶) ≤(𝑝,𝐶′) when 𝐶⊆𝐶′.

• ctrl(𝑝,𝐶) = 𝑝.

• We define # as follows:

(𝑝,𝐶)#(𝑝′,𝐶′) = (𝑝, |𝐶∪𝐶′|𝑝)

It is routine to check that # is controller-preserving and expansive. It is also routine to check that # is idempotent, commutative, and associative on each Time@𝑝, with (𝑝, ∅) as bottom element and (𝑝, Fact) as the top element.

We give the core of the proof of associativity. First, we note two very simple facts:

• If 𝑋,𝑋′ ⊆ Fact and 𝐷∈ Infer𝑝 then 𝑋∪𝑋′ ⊆𝐷 if and only if 𝑋⊆𝐷∧𝑋′ ⊆𝐷.

• 𝑋⊆𝐷 if and only if |𝑋| ⊆𝐷:

We now reason as follows on 𝐶,𝐶′,𝐶′′, 𝐷∈ Infer𝑝 (where we omit the 𝑝 subscript for clarity):

|𝐶∪𝐶′ ∪𝐶′′| ⊆𝐷⇐⇒(𝐶∪𝐶′) ∪𝐶′′ ⊆𝐷 ⇐⇒(𝐶∪𝐶′) ⊆𝐷∧𝐶′′ ⊆𝐷 ⇐⇒|𝐶∪𝐶′| ⊆𝐷∧𝐶′′ ⊆𝐷 ⇐⇒|𝐶∪𝐶′| ∪𝐶′′ ⊆𝐷 ⇐⇒||𝐶∪𝐶′| ∪𝐶′′| ⊆𝐷.

Taking 𝐷 to equal each side in turn, we conclude that |𝐶∪𝐶′∪𝐶′′| = ||𝐶∪𝐶′|∪ 𝐶′′|, and by similar reasoning we also conclude |𝐶∪𝐶′ ∪𝐶′′| = |𝐶∪|𝐶′ ∪𝐶′′||. Thus ||𝐶∪𝐶′| ∪𝐶′′| = |𝐶∪|𝐶′ ∪𝐶′′||, and associativity follows.

# as defined above is not in general contradiction-preserving, which means by Definition 2.2.2(7c) that we do not quite have a located semilattice (yet).

Let us note that this is not necessarily a bad thing. It usefully illuminates a design space of generalisations of Definition 2.2.2.

To now obtain contradiction preservation and thus a located semilattice, we mention three options:

1. A necessary and sufficient condition is just to insist for every 𝑝′ ∈ Ctrl that

∀𝐶′ 1,𝐶′ 2 ∈Infer𝑝′. |𝐶′ 1 ∪𝐶′ 2|𝑝′ = Fact =⇒∀𝑝∈Ctrl.|𝐶′ 1 ∪𝐶′ 2|𝑝= Fact.

2. A stronger condition is to insist that all notions of inference are identical: |𝑋|𝑝= |𝑋|𝑝′ always. This is perhaps a bit stronger than we might like here.

3. An arguably more interesting condition is this:

∀𝐶′ 1,𝐶′ 2 ∈Infer𝑝′. |𝐶′ 1 ∪𝐶′ 2|𝑝′ = Fact =⇒ ∃{𝑥′ 1,𝑥′ 2} ⊆𝐶′ 1 ∪𝐶′ 2.∀𝑝∈Ctrl.|{𝑥′ 1,𝑥′ 2}|𝑝= Fact.

Intuitively, this is a well-pointedness condition: controllers may have different notions of inference, but any contradiction is witnessed by (at most) two globally contradictory facts.18

Further examples of located semilattices appear throughout the body of this text, and in Section 7 (alternative presentation).

3. Located semilattices with Cut

3.1. Flags and flag-sets

Definition 3.1.1

A flag on a located semilattice L = (Ctrl, Time, #, ctrl) is a function

Q : Time →Time,

which we write in the style of a modality as Q 𝑡 (rather than as a function Q(𝑡)), such that for every 𝑡∈ Time:

1. Q is controller-preserving: ctrl(Q 𝑡) = ctrl(𝑡).

2. Q is expansive: 𝑡⪯ Q 𝑡.

So in words: a flag is a controller-preserving, expansive operator on times.

Definition 3.1.2

Suppose L = (Ctrl, Time, #, ctrl) is a located semilattice with a flag Q, and suppose 𝑡∈ TimeL. Write that

𝑡 has the form Q or just 𝑡= Q

when the following hold:

1. 𝑡≠⊤ctrl(𝑡) (so 𝑡 is a consistent time), and

2. 𝑡= Q𝑡′ for some 𝑡′ ∈ Time.

When 𝑡= Q is consistent, we may say that 𝑡 has the flag 𝑄.

Definition 3.1.3

A flag-set Q on a located semilattice L is a set of flags on L (Definition 3.1.1) such that for every Q, Q′ ∈Q and 𝑡,𝑡′ ∈ TimeL we have:

Q𝑡= Q′𝑡′ ∈CTime implies Q = Q′.

We say that flag application is injective where consistent. Put another way: if two times (Q𝑡 and Q′𝑡′ above) have flags and are equal, then those flags are equal.

Definition 3.1.4

Suppose L = (Ctrl, Time, #, ctrl) is a located semilattice with a flag-set Q, and suppose 𝑡∈ TimeL. Define flag(𝑡) by

• flag(𝑡) = Q when 𝑡= Q for Q ∈Q.

• flag(𝑡) = undef when ¬(𝑡= Q) for every Q ∈Q.

Above, undef is a special value used to represent a partial function as a total function. Traditionally in programming this would be written ⊥, but we are already using ⊥ for ‘false’, and ⊥ for ‘the least element of a bounded semilattice’ (Definition 2.1.1(1)).

We warm up with an easy lemma:

Lemma 3.1.5

Suppose L = (Ctrl, Time, #, ctrl) is a located semilattice with a flag-set Q, and suppose 𝑝∈ Ctrl. Then:

1. Q⊤𝑝= ⊤𝑝 for every Q ∈Q.

2. As a corollary, flag(⊤𝑝) = undef .

Proof

By Definition 3.1.1(1) ctrl(Q⊤𝑝) = 𝑝 (note that Q⊤𝑝 is controlled by 𝑝) and by Definition 3.1.1(2) ⊤𝑝⪯ Q⊤𝑝. By Definition 2.2.2(6c) ⊤𝑝 is greatest amongst elements controlled by 𝑝, and Q⊤𝑝= ⊤𝑝 follows.

The corollary follows by routine reasoning unpacking Definitions 3.1.2 and 3.1.4. □

Remark 3.1.6

Lemma 3.1.5 demonstrates that ‘𝑡= Q’ and ‘flag(𝑡) = Q’ — in words: 𝑡 has the flag 𝑄 — from Definitions 3.1.2 and 3.1.4 are not quite equivalent to ‘𝑡= Q𝑡′ for some 𝑡′’.

For example: if 𝑝∈ CtrlL then by Lemma 3.1.5 ⊤𝑝= Q⊤𝑝, but by Definition 3.1.2(1) it is not the case that ⊤𝑝= Q.

We make a couple of simple observations about flags’ behaviour:

Lemma 3.1.7

Suppose L is a located semilattice with a flag-set Q. Then:

1. It is possible for a time to not have any flag.

2. It is possible for a flag to exist but no time to have it.

↰𝑗⋉𝑗⋊𝑗↰𝑗−1⋉𝑗−1⋊𝑗−1↰𝑗−2⋉𝑗−2⋊𝑗−2↰𝑗−3⋉𝑗−3⋊𝑗−3↰0⋉0⋊0· · ·· · · Above, an arrow Q →Q′ represents that Q𝑡⪯Q′𝑡is guaranteed for every 𝑡∈Time.
Figure 6. Flag ordering in Definition 3.2.1
Proof

We consider each part in turn:

1. Consider the inconsistent time ⊤𝑝 for some 𝑝∈ Ctrl. This has no flag, as noted in Remark 3.1.6.

2. To illustrate the design space, we provide an even more extreme counterexample, of a flag on a located semilattice such that no time has that flag. Let the inconsistent or top flag TopFlag : Time → Time be such that TopFlag(𝑡) = ⊤ctrl(𝑡) always. Then TopFlag is a flag by our definition, but by construction no time has it. □

Remark 3.1.8 (Design alternatives).

More liberal notions of flag-set are possible. For instance we could permit multiple flags on a time. However, Definition 3.1.3 as written will suit our purposes here.

3.2. Located semilattices with Cut: the flag-set {↰,⋊,⋉}

3.2.1. The definition

Definition 3.2.1

A located semilattice with Cut is a located semilattice L with the cutting flag-set (we discuss why this flag-set in Remark 3.2.3)

CuttingFlag =⋃𝑖∈N{↰𝑖,⋊𝑖,⋉𝑖}

where for each 𝑖∈N the three flags

• ↰𝑖, read nextindex-𝑖,

• ⋊𝑖, read cutme-𝑖, and

• ⋉𝑖, read cutyou-𝑖

have the following properties for every index 𝑖, 𝑗∈N and every time 𝑡,𝑡′ ∈ Time such that ctrl(𝑡) = ctrl(𝑡′):

1. ↰𝑗𝑡⪯⋊𝑗𝑡.

2. ↰𝑗𝑡⪯⋉𝑗𝑡.

3. If 𝑖< 𝑗 then ⋉𝑗𝑡⪯↰𝑖𝑡.

4. ⋊𝑗𝑡⚡⋉𝑗𝑡′.

5. The mapping

(Q,𝑖) ∈{↰,⋊,⋉} × N ↦−→ Q𝑖∈CuttingFlag

is injective. In words: flags with distinct symbol-index pairs, are distinct flags.19

Remark 3.2.2

For the reader’s convenience, we present Definition 3.2.1 as a diagram:

• A representation of properties 1 to 4 is sketched in Figure 6.

• Arrows indicate ⪯-relations coming from properties 1, 2, and 3.

• Property 4 is represented by the absence of a ⪯-directed path between ⋊𝑗 and ⋉𝑗 (they always lie on distinct branches).

Also, we give pointers to where each of the properties is technically used in the proofs to follow:

1. Property 5 gives Lemma 3.2.5 and ensures that any consistent time always has at most one flag.

2. Property 1 allows a process to use (Inc) to ready itself to be Cut. We use it in Lemma 4.2.2 (times increase) for the case of (⋊Intro).

3. Property 2 allows a process to use (Inc) to ready itself to execute a Cut. We use it in Lemma 4.2.2 (times increase) for the case of (⋉Intro).

4. Property 3 allows a process to complete a Cut. We use it in Lemma 4.2.2 (times increase) for the case of (Cut), and also in Lemma 3.2.4, which is key to creating active inconsistent indexes in the proof of Corollary 5.5.3.

5. Property 4 is arguably the most technically subtle condition. It plays a key role in Proposition 5.5.4, where we use it to derive a contradiction from right-incompatible cuts.

Remark 3.2.3 (What the cutting flag-set means).

Intuitively, the flags in Definition 3.2.1 are an abstract protocol for Cut (= edge-contraction) in a linear path:

1. The flag ↰𝑗 means my successor is index 𝑗.

2. The flag ⋉𝑗 means my successor is index 𝑗, and I am ready to cut 𝑗 from my path. The inequality ↰𝑗⪯⋉𝑗 is the preparation step, where the process asserts its readiness to cut. The symbol ⋉represents a raised pair of scissors, about to cut.

3. The flag ⋊𝑖 means my successor is index 𝑖, and I am ready to be cut. The inequality ↰𝑗⪯⋊𝑗 is the preparation step, where the process asserts its readiness to be cut. The symbol ⋊ represents a lowered pair of scissors, in the process of cutting.

4. The idea of the (Cut) rule is that two polarities ⋉𝑗 and ⋊𝑖 cancel out to make a ↰𝑖:

⋉𝑗𝑡𝑘. . .⋊𝑖𝑡𝑗. . .𝑡𝑖𝑐𝑢𝑡=⇒↰𝑖𝑡𝑘. . .⋊𝑖𝑡𝑗. . .𝑡𝑖.

The inequalities ⋉𝑗⪯↰𝑖 for 𝑖< 𝑗 represent possible completion steps, such that 𝑗 gets cut and the cutting index (written 𝑘 above) continues to point to index 𝑖 as its new successor.

5. The contradiction ⋊𝑗⚡⋉𝑗 is a consistency condition: it ensures that ⋊𝑗⪯⋉𝑗 and ⋉𝑗⪯⋊𝑗 are impossible (i.e. we have to pick whether to cut or be cut), and furthermore it ensures that ⋊𝑗≺↰𝑗 and ⋉𝑗≺↰𝑗 are impossible, meaning that once we enter a cut-me or a cut-you state, we are committed to this and cannot back out.

The details of making this all work are quite involved (see Figure 9), but that is the intuition.

Lemmas 3.2.4 and 3.2.5 will be useful later. The proof of Lemma 3.2.4, while simple enough, is geometrically clear from Figure 6; there is no path from a ⋊-node to a lesser ↰-node:

Lemma 3.2.4

Suppose L is a located semilattice with Cut and suppose 𝑡,𝑡′ ∈ Time and ctrl(𝑡) = ctrl(𝑡′), and suppose 𝑖< 𝑗∈N. Then

⋊𝑗𝑡⚡↰𝑖𝑡′.
Proof

By Definition 3.2.1(3) (since 𝑖< 𝑗) ⋉𝑗𝑡′ ⪯↰𝑖𝑡′. By Definition 3.2.1 ⋊𝑗𝑡⚡⋉𝑗𝑡′, meaning by Notation 2.2.4(2) that⋊𝑗𝑡∨⋉𝑗𝑡′ = ⊤ctrl(𝑡). By semilattice properties it follows that ⋊𝑗𝑡∨↰𝑖𝑡′ = ⊤ctrl(𝑡), meaning that ⋊𝑗𝑡⚡↰𝑖𝑡′ as required. □

Lemma 3.2.5 is a convenient wrapper for Definition 3.2.1(5). It just states that flags with different names do generate distinct times, always (so that for example ⋉𝑖𝑡=↰𝑖′𝑡′ is never possible, provided all times concerned are consistent):

Lemma 3.2.5

Suppose L is a located semilattice with Cut and suppose 𝑡,𝑡′ ∈ Time and 𝑖,𝑖′ ∈N and Q, Q′ ∈{↰,⋊,⋉}. Then

Q𝑖𝑡, Q′ 𝑖′𝑡′ ∈CTime ∧Q𝑖𝑡= Q′ 𝑖′𝑡′implies Q = Q′ ∧𝑖= 𝑖′.
Proof

Suppose that Q𝑖𝑡, Q′ 𝑖′𝑡′ ∈ CTime (i.e. they are consistent times) and suppose Q𝑖𝑡= Q′ 𝑖′𝑡′. By Definition 3.1.3 Q𝑖= Q′ 𝑖′. By Definition 3.2.1(5), Q = Q′ and 𝑖= 𝑖′ as required. □

Remark 3.2.6 (Design alternatives).

The conditions above — particularly those in Definitions 3.2.1 and 3.1.1 — are what we need for the proofs below.

But we can imagine further properties, which might be relevant in future work. We list some here:

1. If 𝑡#𝑠= 𝑡′#𝑠′ then 𝑡= 𝑡′ and 𝑠= 𝑠′.

2. 𝑡#𝑠#𝑢= 𝑡#𝑢#𝑠.

3. 𝑡#𝑠#𝑠′ = 𝑡#(𝑠∨𝑠′), provided ctrl(𝑠) = ctrl(𝑠′) (required so that the ∨ is well-defined).

4. If 𝑠⚡ 𝑠′ then 𝑡#𝑠#𝑠′ = ⊤ctrl(𝑡).

5. ...and so on.

Note that these extra properties are not forbidden; our results below will be valid whether or not they hold.

3.2.2. Scope-extrusion: a computational rule for flags

Definition 3.2.7 extends the notion of flag with an additional well-behavedness property:

Definition 3.2.7

Suppose L = (Ctrl, Time, #, ctrl) is a located semilattice. Say that a flag Q : Time → Time has (lax) scope-extrusion or is scope-extruding when for every 𝑠,𝑡∈ Time

(Q 𝑡)#𝑠⪯Q (𝑡#𝑠).
Lemma 3.2.8

Suppose L = (Ctrl, Time, #, ctrl) is a located semilattice and suppose Q : Time → Time is a scope-extruding flag on L in the sense of Definition 3.2.7. Suppose 𝑡,𝑠∈ Time. Then

Q𝑡⪯Q(𝑡#𝑠).

As a corollary, the following derivation-step is valid on paths:

(. . . , Q𝑡𝑗, . . . ) (. . . , Q(𝑡𝑗#𝑠), . . . )
Proof

Using Definitions 2.2.2(7b) and 3.2.7 we have this:

Q𝑡𝐷2.2.2(7𝑏)⪯ (Q𝑡)#𝑠𝐷3.2.7⪯ Q(𝑡#𝑠). (1)

The corollary follows using (Inc), noting using Definitions 2.2.2(7a) and 3.1.1(1) (attestation and flags preserve controllers) that ctrl(Q𝑡) = ctrl(Q(𝑡#𝑠)), so that the side-condition in (Inc) is indeed satisfied. □

Remark 3.2.9 (On scope-extrusion).

We call the scope-extrusion property in Definition 3.2.7 lax, because this is an inequality, not an equality. We discuss why, in part 2 below.

1. Lemma 3.2.8 gives scope-extrusion a strong computational interpretation: it means that flags really do behave like flags, in the sense that a controller can attest to a time without changing its flag (provided no inconsistency is introduced). This intuition becomes structurally important in Remark 4.1.4(7c), where it gives a nice computational interpretation to (Cut).
Another way to see the value of scope-extrusion is to look at Figure 10. If we want controllers to be able to evolve between adopting one of the flags in that Figure, and the other steps necessary for the cut, then scope-extrusion and Lemma 3.2.8 would allow us to do that.

2. Why is scope-extrusion lax? Suppose we take an equality in Definition 3.2.7. We want to permit ↰ to evolve into ⋊ via some internal computation (a computation which our logic abstracts over), thus we assume ↰𝑡⪯⋊𝑡 (Definition 3.2.1(1)), i.e. ↰𝑡∨⋊𝑡=⋊𝑡 or equivalently ↰𝑡#⋊𝑡=⋊𝑡. But scope-extrusion interacts with the rest of our system in perhaps unexpected ways. Suppose we have that ↰ scope-extrudes over⋊𝑡 (Definition 3.2.7) strictly, i.e. with an equality, and note that 𝑡∨⋊𝑡=⋊𝑡 by Definition 3.1.1(2). Then we could reason as follows, for ⋊𝑡∈ CTime:

⋊𝑡= (↰𝑡) ∨(⋊𝑡) Definition 3.2.1(1)=↰(𝑡∨⋊𝑡) Definition 3.2.7 (with an equality)=↰⋊𝑡 Definition 3.1.1(2)⋊𝑡= (↰𝑡) ∨(⋊𝑡) Definition 3.2.1(1)= (⋊𝑡) ∨(↰𝑡) Commutativity of ∨=⋊(𝑡∨↰𝑡) Definition 3.2.7 (with an equality)=⋊↰𝑡 Definition 3.1.1(2)

Thus ⋊↰𝑡=↰⋊𝑡 and by Definition 3.1.3 ⋊=↰, contradicting the distinctness condition in Definition 3.2.1(5).

3. Intuitively, # serves a dual purpose:

• 𝑡#𝑠 is how ctrl(𝑡) accepts (attests to) information from ctrl(𝑠), and

• 𝑡#𝑡′ where ctrl(𝑡) = ctrl(𝑡′) is how we partially order states of ctrl(𝑡) (as per Lemma 2.1.2 and Definition 2.2.2(6b)).

Now a flag represents, intuitively, an ‘operating mode’ of a controller, and ≺ represents a (very abstract notion of) state transition. Using ⪯ in the scope-extrusion principle (Q𝑡)#𝑠⪯ Q(𝑡#𝑠) separates inputting information from taking a computational step to integrate that information.

4. We never actually use scope-extrusion in the proofs.
That reflects that it has computational meaning, but this paper is about proof, not computation. The weaker our assumptions are — while still deriving the

main result Theorem 5.6.2 — the more powerful that result is.20 We see from part 2 of this Remark and from Remark 4.1.4(7c) that there is a non-trivial interaction between the computationally relevant principle of lax scope-extrusion and the rest of our framework — but the maths in this paper will not need to know whether our located semilattices with Cut are computational, or not.21 Accordingly, for generality and simplicity, we omit scope-extrusion from Definition 3.1.1 even though computationally relevant flags will likely have the property.

3.3. Consistency

Remark 3.2.9(2) should give us pause for thought: the incompatibility of scope-extrusion-up-to-equality with the other axioms, is not evident. We should prove consistency. We will do this by constructing various models of our axioms. We will produce four, of increasing levels of complexity and realism:

1. In Proposition 3.3.1 we present a simple and accessible model which is sufficient to prove consistency.

2. Definition 3.3.2 shows how to leverage the simple model to something more elaborate, in a pleasingly modular manner.

3. Definition 3.4.3 and Proposition 3.4.5 present a more elaborate construction.

4. Definition 3.4.3 presents a version which (modulo some practical considerations, like hashing some data values) is close to how we envisage a practical implementation might look.

3.3.1. Consistency

Proposition 3.3.1 (Consistency).

A (sequential) located semilattice with Cut as per Definition 3.2.1 exists.

Proof

We must exhibit a concrete instance of L = (Ctrl, Time, #, ctrl) with Cut. We provide the following relatively simple and compact example:

1. Ctrl = {∗} (so there is only one controller; we consider a multiple-controller extension in Definition 3.3.2).22

2. Time = {⊤, ⊥} ∪⋃𝑖∈N{ni𝑖, cm𝑖, cu𝑖} (ni stands for ‘next index’, cm stands for ‘cut me’, and cu stands for ‘cut you’).

3. We define ctrl : Time → Ctrl by ctrl(𝑡) = ∗.

4. We endow Time with a partial order ⪯⊆ Time2 defined as the least transitive reflexive relation such that for every 𝑖, 𝑗∈N and every 𝑡∈ Time we have:

⊥⪯𝑡⪯⊤ ni𝑗⪯ cm𝑗 ni𝑗⪯ cu𝑗 cu𝑗⪯ ni𝑖 for 𝑖< 𝑗

5. We define # : Time2 → Time by

𝑡#𝑡′ = 𝑡∨𝑡′.

Above, ∨ refers to least upper bound in Time according to the ⪯ partial order from part 4 of this example.

6. We specify flags by letting symbols 𝑓∈⋃𝑖∈N{ni𝑖, cm𝑖, cu𝑖} act on times as follows:

𝑓𝑡={𝑓 𝑡= ⊥⊤ 𝑡≻⊥

We briefly sketch why this structure is indeed a located semilattice with Cut:

1. Time (at the unique controller ∗) is a top-tree by construction in clause 4 above.

2. Attestation (at the unique controller ∗) is a semilattice join operation by construction.

3. Attestation is controller-preserving (there is only one controller), expansive (because it is a join operation) and contradiction-preserving (because it is a join operation), as per Definition 2.2.2(7).

4. Flag application is expansive by construction, as per Definition 3.1.1(2).

5. Flag application is injective where consistent as per Definition 3.1.3. We indicate why. Suppose Q𝑡= Q′𝑡′ ≺⊤. It follows from the flag action in clause 6 above that 𝑡= 𝑡′ = ⊥ and Q𝑡= Q and Q′𝑡′ = Q′. Thus Q = Q′ and 𝑡= 𝑡′ as required. □

The model given in Proposition 3.3.1 has only one controller. However, this paper is motivated by how digital resources can move across controllers, so it would be nice to see a concrete model in which this could happen. Fortunately, we can just use our existing one-controller model and systematically multiply it with itself:

Definition 3.3.2

Suppose L∗= (Ctrl∗={∗}, Time∗, #∗, ctrl∗) is a located semilattice with Cut with just one controller. Define a located semilattice with Cut

L× = (Ctrl×=N, Time×, #×, ctrl×)

as follows:

1. Ctrl× = N = {0, 1, 2, 3, . . . }.

2. Time× = N × Time∗.

3. (𝑝,𝑡)#×(𝑝′,𝑡′) = (𝑝,𝑡#∗𝑡′), or equivalently (since L∗ has one controller) (𝑝,𝑡)#×(𝑝′,𝑡′) = (𝑝,𝑡∨∗𝑡′).

4. ctrl×(𝑝,𝑡) = 𝑝.

5. Q (𝑝,𝑡) = (𝑝, Q 𝑡), for each flag Q.

Lemma 3.3.3

Continuing the notation of Definition 3.3.2, L× = (Ctrl× = N, Time×, #×, ctrl×) is indeed a located semilattice with Cut.

Proof

First, note that for each 𝑝∈ Ctrl×, (Time×)@𝑝 is just a copy of Time∗ (so single-controller behaviour is as in Proposition 3.3.1). The only difference now is that controllers can also attest to one another’s times. We check the rules for attestation and flag application from Definitions 2.2.2(7), 3.1.1, and 3.1.3, and we see that they all hold. □

3.4. An inductive construction

Subsection 3.3.1 exhibits single-controller and multi-controller located semilattices. The notion of attestation in those models is simple: the state of a controller is a local view of a global notion of state, in the sense that attestation just updates local state with the view of another controller.

We now give another construction with a more sophisticated notion of attestation. A time consists of a tuple (𝑗,𝑥,𝑙) where 𝑗 is a controller identifier, 𝑥 is a local state, and 𝑙 is a list of views into the times of the other controllers.

This is closer to what a realistic implementation would look like. In a real implementation, for efficiency reasons, we might prefer to store 𝑙 as a list of cryptographically succinct digests of the other controllers’ times. Aside from that, the construction which now follows is essentially a realistic rendering of what a real-life located semilattice (with or without Cut) might look like.

Some notation will be helpful:

Notation 3.4.1

Suppose 𝑋 is a set and 𝑛≥ 1 and 𝑙∈𝑋𝑛 is an 𝑛-tuple of elements of 𝑋. We may switch freely between function and tuple notation for 𝑙. Suppose 1 ≤𝑖≤𝑛 and 𝑥∈𝑋. Then define list update 𝑙[𝑖:=𝑥] ∈𝑋𝑛 by

𝑙[𝑖:=𝑥] = 𝜆𝑗∈[1...𝑛].{ 𝑙(𝑗) 𝑗≠𝑖𝑥 𝑗= 𝑖

This is the tuple obtained by updating the 𝑖th entry to 𝑥. For example:

(1, 2, 3)[2:=0] = (1, 0, 3).
Definition 3.4.2

For this subsection we fix the following data:

𝑡#⊤𝑖= ⊤𝑗𝑡#⊥𝑖= 𝑡 (𝑡≠⊥𝑗)⊤𝑗#𝑠= ⊤𝑗 ⊥𝑗#𝑠= 𝑠 𝑖=𝑗⊤𝑗𝑖≠𝑗,𝑠=⊤𝑖(𝑗, ⊥X, (⊥𝑖′ | 𝑖′ ∈𝑁𝑗)[𝑖:=𝑠]) 𝑖≠𝑗,𝑠≠⊤𝑖𝑡#𝑠= ⊤𝑗𝑖=𝑗∧(𝑥𝑡∨X𝑥𝑠= ⊤X)⊤𝑗𝑖=𝑗∧∃𝑖′ ∈𝑁𝑗.𝑙(𝑖′)#𝑚(𝑖′) = ⊤𝑖′(𝑗,𝑥𝑡∨X 𝑥𝑠, (𝑙(𝑖′)#𝑚(𝑖′) | 𝑖′ ∈𝑁𝑗)) 𝑖=𝑗∧(𝑥𝑡∨X𝑥𝑠≠⊤X)∧ ∀𝑖′ ∈𝑁𝑗.𝑙(𝑖′)#𝑚(𝑖′) ≠⊤𝑖′⊤𝑗𝑖≠𝑗∧𝑙(𝑖)#𝑠=⊤𝑖(𝑗,𝑥𝑡,𝑙[𝑖:=𝑙(𝑖)#𝑠]) 𝑖≠𝑗∧𝑙(𝑖)#𝑠≠⊤𝑖
(𝑗∈[1...𝑛]) ⊥𝑗∈CTime@𝑗∀𝑖∈[1...𝑛]∖{𝑗}.𝑡𝑖∈CTime@𝑖(𝑥∈X∖{⊤X}) (𝑗,𝑥, (𝑡𝑖| 𝑖∈[1...𝑛]∖{𝑗})) ∈CTime@𝑗(𝑗∈[1...𝑛]) ⊤𝑗∈Time@𝑗𝑡∈CTime@𝑗𝑡∈Time@𝑗
Figure 7. Times (Definition 3.4.3(2))

Above, 𝑡= (𝑗,𝑥𝑡,𝑙) ∈ Time@𝑗 so that ctrl(𝑡) = 𝑗, and 𝑠= (𝑖,𝑥𝑠,𝑚) ∈ Time@𝑖 so that ctrl(𝑠) = 𝑖. We write 𝑁𝑗= [1...𝑛]∖{𝑗} for compactness.

Figure 8. Attestation (Definition 3.4.3(3))

1. We fix some number 𝑛≥ 1, and we define [1...𝑛] by

[1...𝑛] = {1, 2, . . . ,𝑛}.

[1...𝑛] will be the set of controllers in the located semilattice which we are about to construct.

2. We fix (X, ∨X, ⊥X, ⊤X) a bounded semilattice such that ⊥X ≠⊤X (we call this nondegenerate).

Definition 3.4.3

Define a located semilattice L = (Ctrl, Time, #, ctrl) as follows:

1. Ctrl = [1...𝑛]: controllers are natural numbers.

2. Times 𝑡∈ Time are defined following the rules in Figure 7.

In particular, every time has the form ⊥𝑗, or ⊤𝑗, or (𝑗,𝑥,𝑙) where 𝑗∈[1...𝑛] and 𝑥∈ X and 𝑙 is a list of 𝑛−1 times (but not every such tuple is a time; only the ones that can be derived using the rules in Figure 7). There, consistent with Definition 2.2.2(4) and Notation 2.2.4(1), we write Time@𝑗 for the times controlled by controller 𝑗, and CTime@𝑗 for the consistent times controlled by controller 𝑗 (so CTime@𝑗= Time@𝑗∖{⊤𝑗}).

3. Attestation # is defined for 𝑡= (𝑗,𝑥𝑡,𝑙) ∈ Time@𝑗 and 𝑠= (𝑖,𝑥𝑠,𝑚) ∈ Time@𝑖 as per the rules in Figure 8.

Lemma 3.4.4

Suppose 𝑡∈ Time, for Time from Definition 3.4.3(2). Then 𝑡#𝑡= 𝑡.

Proof

We reason by induction on 𝑡, following the clauses in Figure 7:

• Suppose 𝑡= ⊥𝑖 for some 𝑖∈ Ctrl. Then ⊥𝑖#⊥𝑖= ⊥𝑖 as required.

• Suppose 𝑡= ⊤𝑖 for some 𝑖∈ Ctrl. Then ⊤𝑖#⊤𝑖= ⊤𝑖 as required.

• Suppose 𝑡= (𝑗,𝑥𝑡,𝑙) for some 𝑗∈ Ctrl. Then 𝑡#𝑡= (𝑗,𝑥𝑡∨X 𝑥𝑡, (𝑙(𝑖)#𝑙(𝑖) | 𝑖∈[1...𝑛]∖{𝑗})) and we use facts of semilattices and the inductive hypothesis.

□

Proposition 3.4.5

L from Definition 3.4.3 is indeed a located semilattice (Definition 2.2.2).

Proof

We must prove # is controller-preserving, expansive, and contradiction-preserving, and that (Time@𝑖, #|𝑖) is a bounded semilattice for each 𝑖∈[1...𝑛].

• Controller-preserving. ctrl(𝑡#𝑠) = ctrl(𝑡) is a fact of Figure 8.

• Expansive: (𝑡#𝑠)#𝑡= 𝑡#𝑠. We work by induction on 𝑡.

– Suppose 𝑠= ⊤𝑖. Then 𝑡#𝑠= ⊤𝑗= (𝑡#𝑠)#𝑡 and we are done.

– Suppose 𝑠= ⊥𝑖 and 𝑡≠⊥𝑗. Then 𝑡#𝑠= 𝑡 and (𝑡#𝑠)#𝑡= 𝑡#𝑡 and by Lemma 3.4.4 𝑡#𝑡= 𝑡, so we are done.

– Suppose 𝑡= ⊤𝑗. Then 𝑡#𝑠= ⊤𝑗= (𝑡#𝑠)#𝑡 and we are done.

– Suppose 𝑡= ⊥𝑗 and ctrl(𝑠) = 𝑗. Then 𝑡#𝑠= 𝑠= (𝑡#𝑠)#𝑡 and we are done.

– Suppose 𝑡= ⊥𝑗 and ctrl(𝑠) = 𝑖≠𝑗. Then 𝑡#𝑠= (𝑗, ⊥X, (⊥𝑖| 𝑖∈ [1...𝑛]∖{𝑗})[𝑖:=𝑠]) (as per the second subcase of the fourth clause in Figure 8), and then (𝑡#𝑠)#𝑡= 𝑡#𝑠 and we are done.

– Suppose ctrl(𝑡) = 𝑗= ctrl(𝑠) and 𝑡= (𝑗,𝑥𝑡,𝑙) and 𝑠= (𝑗,𝑥𝑠,𝑚). There are two clauses for this in Figure 8 depending on whether 𝑥𝑡∨X 𝑥𝑠= ⊤X, or 𝑙(𝑖)#𝑚(𝑖) = ⊤𝑖 for some 𝑖∈[1...𝑛]∖{𝑗} (the first clause, which returns ⊤𝑗) — or not. We consider just this latter case. Then

(𝑡#𝑠)#𝑡= (𝑗,𝑥𝑡∨X 𝑥𝑠∨X 𝑥𝑡, (𝑙(𝑖)#𝑚(𝑖)#𝑙(𝑖) | 𝑖∈[1...𝑛]∖{𝑗}))

and we use facts of semilattices and the inductive hypotheses on the 𝑙(𝑖).

– Suppose ctrl(𝑡) ≠ ctrl(𝑠) and 𝑡= (𝑗,𝑥𝑡,𝑙) and 𝑠= (𝑖,𝑥𝑠,𝑚) where 𝑗≠𝑖. Then using facts of semilattices and Lemma 3.4.4 we calculate that

(𝑡#𝑠)#𝑡= (𝑗,𝑥𝑡,𝑙[𝑖:=(𝑙(𝑖)#𝑠)#𝑙(𝑖)]).

We use the inductive hypothesis on 𝑙(𝑖).

• Contradiction-preserving: if ctrl(𝑠) = ctrl(𝑠′) and ctrl(𝑡) = ctrl(𝑡′) then 𝑠⚡ 𝑠′ implies 𝑡#𝑠⚡ 𝑡′#𝑠′. By a routine induction on times in Figure 8. Suppose 𝑠= (𝑖,𝑥𝑠,𝑚) ⚡ 𝑠′ = (𝑖,𝑥𝑠′,𝑚′). Following the structure of Figure 8, it must be that 𝑥𝑠∨X 𝑥𝑠′ = ⊤X or that 𝑚(𝑖′) ⚡ 𝑚′(𝑖′) for some 𝑖′ ∈[1...𝑛]∖{𝑖}. It is then routine to check that 𝑡#𝑠⚡ 𝑡′#𝑠′ follows.

• (Time@𝑖, #|𝑖) is a bounded semilattice for each 𝑖∈[1...𝑛]. By a routine induction on times in Figure 8, taking 𝑖= 𝑗. We just note that when 𝑖= 𝑗, # acts as semilattice join ∨X on 𝑥𝑡 and 𝑥𝑠, and acts componentwise and inductively on the lists, and it defaults to ⊤𝑗 when it detects a contradiction in any component. □

(. . . ,𝑡𝑗, . . . ) (𝑡𝑗≺𝑡′ 𝑗, flag(𝑡𝑗)=flag(𝑡′ 𝑗))(Incj)(. . . ,𝑡′ 𝑗, . . . )(Init)(↰𝑛−1𝑡𝑛,↰𝑛−2𝑡𝑛−1, . . . ,↰1𝑡2,𝑡1)(. . . ,↰𝑖𝑡𝑗, . . . )(⋊Introj)(. . . ,⋊𝑖𝑡𝑗, . . . )(. . . ,↰𝑖𝑡𝑗, . . . )(⋉Introj)(. . . ,⋉𝑖𝑡𝑗, . . . )(. . . ,⋉𝑗𝑡𝑘, . . . ,⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), . . . , 𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), . . . )(Cutk,j,i)(. . . ,↰𝑖𝑡𝑘, . . . ,⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), . . . , 𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), . . . ) Above: 𝑘, 𝑗,𝑖are indexes such that 𝑘> 𝑗> 𝑖. Lower dots ‘. . . ’ indicate (possibly zero many) unchanged times. We may omit subscripts where they are unimportant or understood, e.g. writing (Incj) just as (Inc) or (Cutk,j,i) just as (Cut). Subscripts on times, as in 𝑡𝑖, 𝑡𝑗, and 𝑡𝑘, are just hints for which index (position in the path) the time appears. By Definition 4.1.1(1) prepaths are tuples of consistent times; thus as a structural fact, an instance of a rule is only well-formed provided it has consistent times above and below the line.
Figure 9. Derivations (Definition 4.1.1(4))

4. Paths and circuits

4.1. Paths

Throughout this Section, we assume that L = (Ctrl, Time, #, ctrl) is a located semilattice with Cut.

Definition 4.1.1

1. Define an L-prepath 𝑇 to be an 𝑛-tuple of consistent times, for 𝑛≥ 1. (Following Definition 2.2.2(6d), a time 𝑡 is consistent when 𝑡≠⊤ctrl(𝑡).) In symbols and using Notation 2.2.4(1):

Prepath(L) =⋃𝑛≥1CTime𝑛 L.

2. It will be convenient to write prepaths right-to-left, so that the first element of a prepath is written on the right, not on the left:

If 𝑇= (𝑡𝑛,𝑡𝑛−1, . . .𝑡1) then 𝑇[1] = 𝑡1 and 𝑇[𝑛] = 𝑡𝑛.

This might seem odd until we realise that this is the ordering that a list would have if we first push 𝑡1, then we push 𝑡2, then 𝑡3, and so on until 𝑡𝑛. Thus 𝑡𝑛 is the 𝑛th element to be pushed on the list and it is on the left, and 𝑡1 is the first element to be pushed on the list and it is on the right.

3. Suppose 𝑇 is an L-prepath. We introduce some notation:

(a) We may call 𝑖∈N an index in 𝑇 when 1 ≤𝑖≤ length(𝑇).

(b) We write index(𝑇) for the set of indexes in 𝑇.

(c) We write length(𝑇) for the number of indexes in 𝑇 (i.e. for the size of index(𝑇)).

(d) We write𝑇[𝑖] for the value at the 𝑖-th index of𝑇 (thus: the 𝑖th projection of 𝑇).

4. Define derivation-trees, or just derivations, inductively by the rules in

Figure 9. We introduce some notation:

(a) Write root(Π) for the prepath that is at the root of Π.

(b) Write index(Π) for index(root(Π)) (the set of indexes of the prepath which Π derives).

(c) If 𝑖∈ index(Π) then write Π[𝑖] for root(Π)[𝑖] (the 𝑖-index value of the prepath which Π derives).

(d) In Figure 9 we insert subscripts to record the indexes involved in the derivation step as appropriate, as in (Incj) or (Cutk,j,i). We may omit these indexes where they are unimportant or understood. This is just because, usually, when we discuss Cut we typically want to prove something for which the choice of index really matters23 whereas when we discuss other rules, the index (while still necessary) is not typically central to the discussion.

(e) Disambiguation alert. (Injj) in Figure 9 has a side-condition flag(𝑡𝑗) = flag(𝑡′ 𝑗). For clarity, we will unpack what precisely this means. Not every time has a flag, and as per Definition 3.1.4, flag is a total function which returns a special value undef if its argument has no flag to return. Thus, both sides of the condition flag(𝑡𝑗) = flag(𝑡′ 𝑗) are defined, always, and unpacking what this means: if 𝑡𝑗 has a flag then 𝑡′ 𝑗 has the same flag, and if 𝑡′ 𝑗 has a flag then 𝑡𝑗 has the same flag, and if 𝑡𝑗 has no flag then 𝑡′ 𝑗 has no flag, and if 𝑡′ 𝑗 has no flag then 𝑡𝑗 has no flag.

5. Define Path(L) the set of L-paths to be the set of L-prepaths that are equal to root(Π) for some valid derivation Π. That is: Path(L) is the set of L-prepaths that are inductively derivable by the rules in Figure 9.

6. We may omit the L annotations on prepaths and paths, if L is unimportant or understood.

Notation 4.1.2

Suppose 𝑇 is a prepath of length 𝑛 (so 𝑇 is an 𝑛-tuple of consistent times; see Definition 4.1.1(1)) and suppose 𝑗∈ index(𝑇) (so 1 ≤𝑗≤ 𝑛), and 𝑡∈ CTime and ctrl(𝑡) = ctrl(𝑇[𝑗]). Then define 𝑇{𝑗:=𝑡}, read 𝑻 with the 𝒋 index set to 𝒕, to be the prepath of length 𝑛 such that 𝑇{𝑗:=𝑡}[𝑖] = 𝑇[𝑖] for every 1 ≤𝑖≠𝑗≤𝑛, and 𝑇{𝑗:=𝑡}[𝑗] = 𝑡.

Remark 4.1.3

We take a moment to rephrase Figure 9, less diagrammatically and more programmatically.

We can specify the derivation rules in Figure 9 using Notation 4.1.2 as follows, where we write 𝑇 for the path above the line in the derivation rule (if there is one) and we write 𝑇′ for the path below the line:

1. (Incj) 𝑇′ = 𝑇{𝑗:=𝑡′ 𝑗} where 𝑇[𝑗] = 𝑡𝑗, provided 𝑡𝑗≺𝑡′ 𝑗 and flag(𝑡𝑗) = flag(𝑡′ 𝑗) (and provided 𝑡′ 𝑗 is consistent).

2. (Init) There is no𝑇 above the line. 𝑇′ = (↰𝑖−1𝑡𝑖| 2 ≤𝑖≤𝑛)::(𝑡1), where :: denotes concatenation of tuples (provided 𝑡1 is consistent and ↰𝑖−1𝑡𝑖 is consistent for every 2 ≤𝑖≤𝑛).

3. (⋊Introj) 𝑇′ = 𝑇{𝑗:=⋊𝑖𝑡𝑗} where 𝑇[𝑗] =↰𝑖𝑡𝑗 (provided ⋊𝑖𝑡𝑗 is consistent).

4. (⋉Introj) 𝑇′ = 𝑇{𝑗:=⋉𝑖𝑡𝑗} where 𝑇[𝑗] =↰𝑖𝑡𝑗 (provided ⋉𝑖𝑡𝑗 is consistent).

5. (Cutk,j,i) 𝑇′ = 𝑇{𝑘:=↰𝑖𝑡𝑘} where 𝑇[𝑘] =⋉𝑗𝑡𝑘 and 𝑇[𝑗] =⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘) and 𝑇[𝑖] = 𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), provided 𝑘> 𝑗> 𝑖∈ index(𝑇) (and provided ↰𝑖𝑡𝑘 is consistent).

6. The bracketed consistency conditions above spell out conditions which technically we do not need to state because they are structurally built in to our definitions — but we mention them anyway, for clarity: in Definition 4.1.1(1)

a prepath is defined to be an 𝑛-tuple of consistent times for 𝑛≥ 1, and in the definition of {𝑗:=𝑡} we assume 𝑡 is a consistent time. Thus, the derivation rules are subject to a well-formedness condition that times remain consistent below the line, so that a derivation rule can only be applied where it does not introduce an inconsistent time ⊤𝑝 below the line, for any controller 𝑝∈ Ctrl.

Remark 4.1.4

We discuss the derivation rules in Figure 9 in turn:

1. Each of the derivation rules with a path above the line — (Inc), (⋊Intro), (⋉Intro), and (Cut) — changes precisely one index of the path. This is a deliberate choice which reflects that we are modelling a distributed system. A rule that modifies two path indexes simultaneously would be a rule whose implementation might require synchronous coordination between controllers. Synchronous coordination would by definition undermine the ‘distributed’ nature of our ‘distributed system’. Part of the point of inventing located semilattices with Cut was precisely to implement a Cut-like structure such that synchronous coordination between controllers is not required.

2. (Init) starts a derivation with a path in which each time points to the previous time.

3. (Incj) allows a controller at index 𝑗 to evolve to any later time with the same flag (if any), subject only to a restriction that doing so must retain consistency. In an implementation, controllers would not just evolve times randomly, but our mathematics is designed to be general, so it makes no restrictions here. For our purposes this is a good thing, because it minimises our assumptions and so maximises the applicability of our results.

4. The same-flag restriction in (Inc) is very important, because we use other flags to control flag-transitions: (⋊Intro) for transitioning from ↰ to ⋊; (⋉Intro) for transitioning from ↰ to⋉, and (Cut) for transitioning from (⋉j) to (↰i) for 𝑖< 𝑗. No derivation rule lets us transition from ⋊ to ↰, and this matters: see Lemma 5.1.1.

5. (⋊Introj) allows a controller to transition from a ‘↰’-state to a ‘⋊’-state, meaning intuitively that 𝑗 is ready to be cut by some 𝑘 to its left.

6. (⋉Introj) allows a controller to transition from a ‘↰’-state to a ‘⋉’-state, meaning intuitively that 𝑗 is ready to cut some 𝑖 to its right.

7. The (Cut) rule. We reproduce the rule here for convenient reference:

(. . . ,⋉𝑗𝑡𝑘, . . . ,⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), . . . , 𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), . . . )(Cutk,j,i)(. . . ,↰𝑖𝑡𝑘, . . . ,⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), . . . , 𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), . . . )

In words, we will say that in this rule index 𝒌 cuts index 𝒋 to 𝒊. This might look a bit complicated, so we read through it. Encoded in the pattern of attestations above is the following sequence of actions, which we also draw diagrammatically in Figure 10:

(a) Index 𝑘 transitions from ↰𝑗𝑡𝑘 to ⋉𝑗𝑡𝑘 using (⋉Intro).

(b) In parallel with the previous step, index 𝑗 transitions from ↰𝑖𝑡𝑗 to ⋊𝑖𝑡𝑗 using (⋊Intro).

(c) Index 𝑗 attests to⋉𝑗𝑡𝑘 the state of (the controller at) index 𝑘, using (Inc) with expansivity (Definition 2.2.2(7b)) and then scope-extrusion (see Definition 3.2.7 and subsequent discussion). We illustrate this step in detail:

⋊𝑖𝑡𝑗𝐷2.2.2(7𝑏)⪯ (⋊𝑖𝑡𝑗)#(⋉𝑗𝑡𝑘)𝐷3.2.7⪯⋊𝑖(𝑡𝑗#(⋉𝑗𝑡𝑘)).

(See also equation (1) in Lemma 3.2.8 and Remark 3.2.9(4).)

(d) Index 𝑖 attests to ⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘) using (Inc) with Definition 2.2.2(7b).

(e) Index 𝑘 transitions to ↰𝑖𝑡𝑘 using (Cutk,j,i).

Note: when we write ‘index’ above, we should more precisely write ‘the controller at index’; e.g. “Index 𝑘 transitions” should be “The controller at index 𝑘 transitions”. However, this may look messy so we omit it for clarity. The reader is welcome to mentally restore ‘the controller at’ everywhere, if preferred.

8. We use the specific pattern of attestations of Cut at three points in our proofs below:

(a) In point 4 in the proof of Lemma 5.5.1, we use the fact that the time at the 𝑖-index has the form 𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘).

(b) In point 1 in the proof of Proposition 5.5.4, we use the fact that the time at the 𝑖-index has (in the notation used for Cut in Figure 9) the form 𝑡𝑖#⋊𝑖𝑡𝑗.

(c) In point 2 in the proof of Proposition 5.5.4, we use the fact that the time at the 𝑗-index has (in the notation used for Cut in Figure 9) the form ⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), which by flag expansivity is ⪰ to 𝑡𝑗#⋉𝑗𝑡𝑘.

Definition 4.1.5 will become important later, but we mention it here:

Definition 4.1.5

Suppose Π is a derivation of a path 𝑇.

1. Call an index 𝑗∈ index(𝑇) 𝒌, 𝒊-inactive when 𝑘,𝑖∈ index(𝑇) and 𝑘> 𝑗> 𝑖 and 𝑇[𝑘] = Q𝑖 for some Q ∈{↰,⋊,⋉}. For clarity, we give an illustration of a path 𝑇 such that indexes 3 and 2 are 4, 1-inactive. Arrows are just annotations to illustrate intuitively to which index a flag points:

↰1𝑡4⋊2𝑡3⋊1𝑡2 𝑡1

Path 𝑇: ↰4𝑡5

2. Call an index 𝑗∈ index(Π) 𝒌, 𝒊-inactive when 𝑗 is inactive in root(Π) — thus, when 𝑘,𝑖∈ index(Π) and 𝑘> 𝑗> 𝑖 and Π[𝑘] = Q𝑖 for some Q ∈{↰,⋊,⋉}.

3. If 𝑘 and 𝑖 are unimportant or understood then we might just call 𝑗 inactive.

4. If 𝑗 is not inactive then call 𝑗 active.

(...,⋉𝑗𝑡𝑘,...,⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘),...,𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘),... )(Cutk,j,i)(...,↰𝑖𝑡𝑘,...,⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘),...,𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘),... )[a] 𝑘:↰𝑗𝑡𝑘;⋉𝑗𝑡𝑘[b] 𝑗:↰𝑖𝑡𝑗;⋊𝑖𝑡𝑗[c] 𝑗:⋊𝑖𝑡𝑗;⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘)[d] 𝑖: 𝑡𝑖; 𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘)[e] 𝑘:⋉𝑗𝑡𝑘;↰𝑖𝑡𝑘start prepare attest 𝑘at 𝑗 attest 𝑗at 𝑖 cut𝒌 𝒋 𝒊↰𝑗𝑡𝑘⋉𝑗𝑡𝑘· · · · · ·↰𝑖𝑡𝑘↰𝑖𝑡𝑗⋊𝑖𝑡𝑗⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘)· · · · · ·𝑡𝑖· · · · · ·𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘)· · ·[a] [b] [c][d][e]Three dots mean “unchanged since the previous column”. Dotted arrows show attestation dependencies.
Figure 10. Two visualisations of (Cutk,j,i) (Remark 4.1.4(7))

4.2. Initial prefixes

The derivations specified in Figure 9 are tree structures, but furthermore they are nonbranching trees — also known as lists — since every derivation rule has either zero (for (Init)) or one assumption (all other rules). This justifies a definition which will prove very useful, starting with Definition 4.3.2:

Definition 4.2.1

1. Call a derivation Π1 an initial prefix of a derivation Π when Π1 viewed as a list is a nonempty initial segment of Π.

2. Call a pair of derivations (Π1, Π′ 1) an initial prefix of another pair (Π, Π′) when Π1 is an initial prefix of Π and Π′ 1 is an initial prefix of Π′ (these will be circuit-derivations from Definition 4.3.1(3)).

Lemma 4.2.2 (Times increase).

Suppose Π1 and Π are derivations and Π1 is an initial prefix of Π, and suppose 𝑖∈ index(Π1). Then Π1[𝑖] ⪯Π[𝑖].

Proof

We check each of the rules in Figure 9 and note that times always increasing is a fact from the inequalities in Definition 2.2.2:

• (Inc) follows from the side-condition 𝑡𝑗≺𝑡′ 𝑗 in that rule.

• (Init) has no assumptions so there is nothing to prove.

• (⋊Intro) follows from Definition 3.2.1(1), that ↰𝑖𝑡⪯⋊𝑖𝑡.

• (⋉Intro) follows from Definition 3.2.1(2), that ↰𝑖𝑡⪯⋉𝑖𝑡.

• (Cut) follows from Definition 3.2.1(3), that ⋉𝑗𝑡⪯↰𝑖𝑡, provided 𝑖< 𝑗. □

4.3. Circuits

Definition 4.3.1 (Circuits and circuit-derivations).

Recall from Definition 4.1.1(3d) that if 𝑇 is a path and 𝑖∈ index(𝑇) then 𝑇[𝑖] denotes the 𝑖th element of 𝑇 (which is just a length(𝑇)-tuple of times).

1. Define a circuit (𝑇,𝑇′) to be a pair of paths with the same length and such that ctrl(𝑇[𝑖]) = ctrl(𝑇′[𝑖]) for every 1 ≤𝑖< 𝑛,

where 𝑛= length(𝑇) = length(𝑇′). Note that the controllers of 𝑇[𝑛] and 𝑇′[𝑛] need not be equal.

2. Define the length of a circuit length(𝑇,𝑇′) to be length(𝑇) = length(𝑇′) the common length of its two paths.

3. Define a circuit-derivation (Π, Π′) of a circuit (𝑇,𝑇′) to be a pair of derivations deriving 𝑇 and 𝑇′ respectively.

4. (a) Suppose (Π, Π′) is a circuit-derivation of a circuit (𝑇,𝑇′). We define index(Π, Π′) and index(𝑇,𝑇) to be equal to index(𝑇) (or equivalently equal to index(𝑇′)), which following Definition 4.1.1(3b) is just the set {1, . . . , length(𝑇)}.

(b) Call an index 𝑗 in a circuit-derivation (Π, Π′) active when 𝑗 is active in at least one of Π and Π′ in the sense of Definition 4.1.5.

(c) Call 𝑗 doubly active when 𝑗 is active in both Π and Π′ (so doubly active implies active).

(d) Call 𝑗 inactive when 𝑗 is inactive in both of Π and Π′ (so 𝑗 is inactive when it is not active).

Definition 4.3.2 ((In)consistency of circuit-derivations).

1. Call an index 𝑗 in a circuit-derivation (Π, Π′) inconsistent when there exist initial prefixes Π1 of Π, and Π′ 1 of Π′, such that:

(a) 𝑗 is doubly active in (Π1, Π′ 1) in the sense of item 4c of this Definition.

(b) Π1[𝑗] ⚡ Π′ 1[𝑗], thus by Notation 2.2.4(2) that ctrl(Π1[𝑗]) = ctrl(Π′ 1[𝑗]) and Π1[𝑗] ∨Π′ 1[𝑗] = ⊤ctrl(Π1[𝑗]). Note: recall that ctrl(Π1[𝑗]) = ctrl(Π′ 1[𝑗]) is guaranteed from Definition 4.3.1(1) for 𝑗< length(Π1, Π′ 1), but not if 𝑗= length(Π1, Π′ 1).

2. Call a circuit-derivation (Π, Π′) inconsistent when it contains an inconsistent index as per item 1 of this Definition, and call (Π, Π′) not inconsistent or just consistent when it does not contain any inconsistent index.

3. Call an index 𝑗 in a circuit-derivation (Π, Π′) active inconsistent when:

(a) 𝑗 is active in (Π, Π′) in the sense of Definition 4.3.1(4b), and

(b) 𝑗 is inconsistent in (Π, Π′) in the sense of item 1 of this Definition.

4. Call a circuit-derivation (Π, Π′) active inconsistent when it contains an active inconsistent index.

Remark 4.3.3

A few notes on Definition 4.3.2(1) (inconsistent index in a circuit):

1. 𝑗 being inconsistent in (Π, Π′) does not necessarily imply that 𝑗 is active in (Π, Π′). For instance, 𝑗 might have been doubly active and inconsistent in some initial prefix, and then it got Cut and became inactive.

2. Π[𝑗] ⚡ Π′[𝑗] does not necessarily imply that 𝑗 is inconsistent in (Π, Π′). The condition is stronger than that: a contradiction has to arise in an initial prefix of the circuit-path (Definition 4.2.1(2)) in which 𝑗 is doubly active.

3. As per Definition 4.3.1(1) if 𝑗< length(Π, Π′) then ctrl(Π[𝑗]) = ctrl(Π′[𝑗]), but if 𝑗= length(Π, Π′) then it may be that ctrl(Π[𝑗]) ≠ ctrl(Π′[𝑗]).

Proposition 4.3.4 is a useful repackaging of Lemma 2.2.5:

Proposition 4.3.4

Suppose (Π, Π′) is a circuit-derivation and suppose (Π1, Π′ 1) is an initial prefix of (Π, Π′) (Definition 4.2.1(2)), and suppose 𝑗∈ index(Π1, Π′ 1). Then:

1. If Π1[𝑗] ⚡ Π′ 1[𝑗] then Π[𝑗] ⚡ Π′[𝑗].

2. If 𝑗 is inconsistent in a circuit-derivation (Π, Π′) then Π[𝑗] ⚡ Π′[𝑗].

Proof

We consider each part in turn:

1. By Lemma 2.2.5 ctrl(Π1[𝑗]) = ctrl(Π′ 1[𝑗]) and Π1[𝑗] ∨Π′ 1[𝑗] = ⊤ctrl(Π1[𝑗]). We use Lemma 4.2.2.

2. We just combine part 1 of this result with Definition 4.3.2(1). □

Remark 4.3.5

This is a good place to take stock. Our main result will be Theorem 5.6.2, that an inconsistent circuit-derivation is active inconsistent: i.e. part 2 of Definition 4.3.2 implies part 4.

The mathematics from here to that Theorem exists to prove this implication, and we have set up our definitions and notations so as to make this proof as slick as possible. Yet even so, the argument is far from obvious.

Where does the complexity (and subtlety!) come from?

One reason is that it is an inherently nontrivial result. But there is another reason: there are many moving parts to keep track of: notions of active vs. inactive index, notions of instances of Cut and how these can (and cannot) nest, notions of path and path evolution and derivation, and so on.

The definitions have several layers and moving parts, so that even though we have set up our definitions so that the result we want can be quite plainly stated as above, this simple statement stands in front of a detailed structure in a rich design space, which we will need to carefully navigate in the proofs so as to arrive at the result that we want.

We conclude with some notation which will be useful shortly. We collect it here, for easy reference:

Definition 4.3.6

Suppose Π and Π′ are derivations.

1. Write (Cutk,j,i) ∈Π when an instance of (Cutk,j,i) appears in Π, and say that Π contains a cut centred on 𝒋.

2. For (rulename) ∈{(Inc), (⋊Intro), (⋉Intro)}, write (rulenamej) ∈Π when an instance of (rulenamej) appears in Π, and say that Π contains an instance of (rulename) centred on 𝒋.

3. Say that a circuit-derivation (Π, Π′) contains a right-incompatible pair of cuts at some 𝑗∈ index(Π, Π′) when (Cutk,j,i) ∈Π and (Cutk′,j,i′) ∈Π′ and 𝑖≠𝑖′.

4. Say that (Π, Π′) contains right-compatible cuts at some 𝑗∈ index(Π, Π′) when if (Cutk,j,i) ∈Π (for some 𝑘 and 𝑖) and also (Cutk′,j,i′) ∈Π′ (for some 𝑘′ and 𝑖′) then 𝑖= 𝑖′. Note that if (Π, Π′) contains right-compatible cuts at 𝑗, then it does not follow that 𝑗 is actually cut in Π or Π′: it just means that if 𝑗 is cut in both Π and Π′, then the rightmost indexes in both cuts (the 𝑖 and 𝑖′ above) are equal.

5. Properties of paths and circuits

The proofs of this section have a nice shape, but there is a lot of detail. For the reader’s convenient reference, we include a mini-map of this Subsection:

1. Subsection 5.1: ⋊ persistence. Lemma 5.1.1 and its corollaries. Once a ⋊𝑖 flag appears on a time, later derivation steps cannot change it. Thus, once a controller enters the ‘ready to be cut’ state, it can never leave it.

2. Subsection 5.2: flag nesting and affine cuts. Lemma 5.2.2, Proposition 5.2.3 and Lemma 5.2.5. Pointer jumps must be properly nested; an index can be cut at most once; and the endpoints of a cut remain active immediately after that cut.

3. Subsection 5.3: inactive if and only if cut. Lemma 5.3.1 and Proposition 5.3.3. This has the flavour of a soundness and completeness result: an index is inactive in the final path of a derivation (a condition with a semantic flavour) if and only if some cut centred on that index occurs in the derivation (a condition with a syntactic flavour).

Lem 5.1.1⋊persistsLem 5.2.2, Prop 5.2.3flags nest & affine cutsProp 5.3.3inactive iff cutProp 5.4.1Matryoshka cutsProp 5.5.2 & 5.5.4(in)compatible cutsThm 5.6.2active inconsistency remains
Figure 11. Proof dependency diagram for Section 5

4. Subsection 5.4: Matryoshka cut geometry. Proposition 5.4.1 and corollaries. Cuts cannot cross one another: cuts are either disjoint, equal, or nested, and furthermore we have a ‘Matryoshka doll’ property that every index inside a cut interval must itself be the midpoint of some nested cut.

5. Subsection 5.5: (in)compatible cuts. Lemma 5.5.1 and Proposition 5.5.2, and Corollary 5.5.3 and Proposition 5.5.4. If two derivations cut the same inconsistent index to the same right endpoint (a ‘compatible’ pair of cuts) then the inconsistency propagates to the smaller index. Thus cutting an inconsistency with a compatible cut creates a new inconsistency closer to the right end of the path. If two derivations cut the same index to different right endpoints (an ‘incompatible’ pair of cuts) then the incompatibility of the cutme and cutyou flags creates an active inconsistency at a lesser index. Thus cutting an inconsistency with an incompatible cut also creates a new inconsistency closer to the right end of the path.

6. Subsection 5.6: inconsistent implies active inconsistent. Theorem 5.6.2 and its two corollaries. Choose the least inconsistent index. As per Subsection 5.5, this index cannot be inactivated without creating a smaller active inconsistency. Thus the least inconsistent index is active inconsistent, and if any inconsistent index appears, then an active inconsistent index is present.

We sum this up as a diagram in Figure 11, from Lemma 5.1.1 through to Theorem 5.6.2.

Throughout this Section, we will assume that L = (Ctrl, Time, #, ctrl) is a (not necessarily sequential) located semilattice with Cut.

5.1. Persistence of ⋊

Lemma 5.1.1 (⋊ persists).

Suppose Π is a derivation and 𝑗∈ index(Π) and Π1 is an initial prefix of Π (Definition 4.2.1; a nonempty initial segment of Π). Then

Π1[𝑗] =⋊𝑖implies Π[𝑗] =⋊𝑖.
Proof

Note from Definition 3.1.3 that each time has at most one flag, so we can sensibly talk about ‘the flag of a time at an index’ and how a derivation-rule from Figure 9 can (and can not) modify it.

We work by induction on derivations: we consider each rule from Figure 9 and check that it cannot turn a time with a ⋊𝑖-flag into a time with a different flag.

• Rule (Inc). By the construction of the rule and its assumption that the flag does not change.

• Rule (Init). Trivial from the form of the rule: (Init) has no assumptions, so Π here has no initial segments other than itself, as per Definition 4.2.1.

• Rule (⋊Intro). Routine from the form of the rule.

• (⋉Intro). Routine from the form of the rule. Note from Lemma 3.2.5 that we cannot use (⋉Intro) to turn a ⋊𝑗-flagged time at some index into a ⋉𝑗-flagged time, because this would require an equality of the form ⋊𝑗𝑡=↰𝑗𝑡′, which by the Lemma is impossible.

• Rule (Cut). Routine from the form of the rule, again using Lemma 3.2.5. □

Corollary 5.1.2 (Inactive implies ⋊).

Suppose Π is a derivation and suppose 𝑗′ ∈ index(Π). Then

• if 𝑗′ is 𝑘,𝑖-inactive (Definition 4.1.5)

• then Π[𝑗′] =⋊𝑖′ for some 𝑖′ such that 𝑗′ > 𝑖′ ≥𝑖.

Proof

Let Π1 be the least initial prefix of Π such that 𝑗′ is 𝑘′,𝑖′-inactive for some 𝑘≥𝑘′ > 𝑗′ > 𝑖′ ≥𝑖 (one such prefix exists, namely Π itself with 𝑘′ = 𝑘 and 𝑖′ = 𝑖, but it might not be least). By the form of the rules in Figure 9 and Lemma 3.2.5, the final derivation-step in Π1 must be an instance of (Cutk′,j′,i′). It follows from the form of the Cut derivation rule that Π1[𝑗′] =⋊𝑖′. We now use Lemma 5.1.1. □

Corollary 5.1.3 (Cut implies ⋊).

Suppose Π is a derivation and 𝑗′ ∈ index(Π). Then

• if (Cutk,j,i) ∈Π and 𝑘> 𝑗′ > 𝑖

• then Π[𝑗′] =⋊𝑖′ for some 𝑖′ such that 𝑗′ > 𝑖′ ≥𝑖.

Proof

Suppose (Cutk,j,i) ∈Π. Let Π1 be the initial prefix of Π consisting of all derivation steps up to and including the Cut. Then 𝑗′ is 𝑘,𝑖-inactive in Π1. By Corollary 5.1.2 (for Π1) Π1[𝑗′] =⋊𝑖′ for some 𝑗′ > 𝑖′ ≥𝑖. We use Lemma 5.1.1. □

Remark 5.1.4

The reverse implication for Corollaries 5.1.2 and 5.1.3 does not hold: it is possible for Π[𝑗] =⋊𝑖 yet 𝑗 is active and uncut.

To see how, just consider a trivial derivation consisting of (Init) from Figure 9, followed by an instance of (⋊Introj): then 𝑗 is active, uncut, and Π[𝑗] =⋊𝑗−1.

We can use a path with two indexes and one controller 𝑝, as illustrated:

Π =(Init)(↰1⊥𝑝, ⊥𝑝)(⋊Intro2)(⋊1⊥𝑝, ⊥𝑝)

Then both indexes 1 and 2 are active and uncut, yet Π[2] =⋊1.

𝑘′ · · · 𝑗2· · ·𝑘· · ·̸̸𝑗2· · ·𝑖· · · 𝑗2candidate 𝑗2 ≥𝑘forbidden zone 𝑖< 𝑗2 < 𝑘candidate 𝑗2 ≤𝑖𝑘′ ↦→𝑗2𝑘′ ↦→𝑗2given 𝑘↦→𝑖̸̸̸𝑘′ ↦→𝑗2Above, the pointer from 𝑘′ ≥𝑘may point to 𝑗2 such that 𝑘′ > 𝑗2 ≥𝑘or 𝑖≥𝑗2, but not 𝑘> 𝑗2 > 𝑖.
Figure 12. Illustration of Lemma 5.2.2

5.2. Flag nesting and affine cuts

Lemma 5.2.2 is a simple property with a straightforward proof, but it is very useful. We need a helper lemma first:

Lemma 5.2.1 (Flag of non-initial index).

Suppose Π is a derivation and suppose 𝑗∈ index(Π) and 𝑗> 1. Then Π[𝑗] = Q𝑖 for some 𝑖∈ index(Π) such that 𝑗> 𝑖.

Proof

By a routine induction on derivations. We consider only instances of derivation rules that might affect the index 𝑗:

• The case of (Incj) follows by the inductive hypothesis and the condition that the flag of the index is unchanged.

• The case of (Init) is a structural fact of the rule.

• The cases of (⋊Introj) and (⋉Introj) are routine from the inductive hypothesis.

• The case of (Cutj,i,i′) is routine from the structure of the derivation rule. □

Lemma 5.2.2 (Flags nest).

Suppose Π is a derivation and Π1 is an initial prefix of Π and 𝑘′ ≥𝑘> 1 ∈ index(Π1). Then

• if Π1[𝑘] = Q𝑖 for some Q ∈{↰,⋊,⋉} and some 𝑖∈ index(Π),

• then Π[𝑘′] = Q′ 𝑗′′ for some Q′ ∈{↰,⋊,⋉} and for some 𝑗′′ ∈ index(Π) such that ¬(𝑘> 𝑗′′ > 𝑖) (equivalently: (𝑗′′ ≥𝑘) ∨(𝑖≥𝑗′′)).

This is illustrated for the reader’s convenience in Figure 12.

Proof

We work by induction on the length of Π. We consider possibilities:

• Suppose Π = Π1. We consider cases for 𝑘′:

– Suppose 𝑘′ = 𝑘. Then we take Q′ = Q and 𝑗′′ = 𝑖.

– Suppose 𝑘′ > 𝑘. By Lemma 5.2.1 Π[𝑘′] = Q′ 𝑖′ for some flag Q′ and some 𝑖′ < 𝑘′. If we can now prove that ¬(𝑘> 𝑖′ > 𝑖) then we can take 𝑗′′ = 𝑖′ and we are done. So suppose not: suppose 𝑘> 𝑖′ > 𝑖. By Corollary 5.1.2 Π[𝑘] = Q′′ 𝑖′′ for some Q′′ and some 𝑖′′ such that 𝑘> 𝑖′′ ≥𝑖′. But we assumed Π[𝑘] = Q𝑖 and we have 𝑖′′ ≥𝑖′ > 𝑖, so 𝑖′′ ≠𝑖. This contradicts injectivity of flag application (Definition 3.1.3), so we are done.

• Suppose Π ≠Π1 (so Π1 is a proper initial prefix of Π). Then we consider subcases for the final derivation rule in Π, writing Π2 for the initial prefix of Π up to but not including its final derivation-rule. We consider only instances of derivation rules that might affect the index 𝑘′:

– The case of (Inck′). By the side-condition flag(Π2[𝑘′]) = flag(Π[𝑘′]).

– The case of (Initk′). There is nothing to prove because in this case Π cannot have a proper subderivation.

– The cases of (⋊Introk′) and (⋉Introk′). From the fact that these rules do not change the index on the flag.

– The case of (Cutk′,j′,i′) for some 𝑗′ and 𝑖′ such that 𝑘′ > 𝑗′ > 𝑖′. By inductive hypothesis (because Π2 is shorter than Π) Π2[𝑘′] =⋉𝑗′ where ¬(𝑘> 𝑗′ > 𝑖). There are now two further subcases: ∗ Suppose 𝑗′ ≥𝑘. Then by inductive hypothesis (since Π1 is an initial prefix of Π2) Π2[𝑗′] = Q𝑗′′ for some Q and some 𝑗′′ ∈ index(Π) such that ¬(𝑘> 𝑗′′ > 𝑖). ∗ Suppose 𝑖≥𝑗′. Then by Lemma 5.2.1 (noting that 𝑗′ > 𝑖′ so 𝑗′ > 1), Π2[𝑗′] = Q𝑗′′ for some Q and some 𝑗′′ ∈ index(Π) such that 𝑗′ > 𝑗′′, so that ¬(𝑘> 𝑗′′ > 𝑖). In either case, after the Cut we have that Π[𝑘′] = Q𝑗′′, and the result follows. □

Proposition 5.2.3 (Affine cuts).

Suppose Π is a derivation. Then for each 𝑗∈ index(Π), Π contains at most one cut centred on 𝑗.

Proof

Consider two distinct instances of Cut in Π, centred on 𝑗:

• (Cutk,j,i) ∈Π for some 𝑘 and 𝑖. Write Π1 for the initial prefix of Π up to and including this Cut.

• (Cutk′,j,i′) ∈Π for some 𝑘′ and 𝑖′. Write Π2 for the initial prefix of Π up to and not including this Cut.

We will show that this is impossible.

For concreteness — and without loss of generality, since Π is non-branching as observed in Definition 4.2.1 — suppose Π1 is an initial prefix of Π2. We now consider cases:

• Suppose 𝑘= 𝑘′ and 𝑖= 𝑖′. By the structure of the Cut rule, Π1[𝑘] =↰𝑖. By the structure of the Cut rule again, Π2[𝑘] =⋉𝑗. But we see from the derivation rules that this is impossible: none of (⋊Intro), (⋉Intro), or (Cut) can transform a time of the form ↰𝑖 into a time of the form Q𝑗 (for any flag Q) for 𝑗> 𝑖.

• Suppose 𝑘= 𝑘′ and 𝑖′ ≠𝑖. Then Π1[𝑗] =⋊𝑖 and Π2[𝑗] =⋊𝑖′ and 𝑖′ ≠𝑖. This contradicts Lemma 5.1.1, so this case is impossible.

• Suppose 𝑘> 𝑘′ > 𝑗. Then Π1[𝑘] =↰𝑖 and Π2[𝑘′] =⋉𝑗 and 𝑘> 𝑘′ > 𝑗> 𝑖. This contradicts Corollary 5.1.2, so this case is impossible.

• Suppose 𝑘′ > 𝑘> 𝑗. Then Π2[𝑘′] =⋉𝑗 and Π1[𝑘] =↰𝑖 and 𝑘′ > 𝑘> 𝑗> 𝑖. This contradicts Lemma 5.2.2, so this case is impossible. □

Corollary 5.2.4 is a technical property which will be useful later: if the flag of active 𝑗 points at 𝑖, then 𝑖 is active. We mention it here because it follows directly from Lemma 5.2.2:

Corollary 5.2.4 (Active points to active).

Suppose Π is a derivation and 𝑗> 𝑖∈ index(Π). Then

• if 𝑗 is active in Π (Definition 4.1.5) and Π[𝑗] = Q𝑖,

• then 𝑖 is active in Π.24

Proof

We reason by contradiction. Suppose 𝑗 is active and Π[𝑗] = Q𝑖 and suppose 𝑖 is inactive, meaning by Definition 4.1.5 that there exists 𝑗′,𝑖′ ∈ index(Π) such that 𝑗′ > 𝑖> 𝑖′ and Π[𝑗′] = Q𝑖′. There are now three subcases:

• Suppose 𝑗′ > 𝑗. Then 𝑗 is inactive, contradicting our assumption.

• Suppose 𝑗′ = 𝑗. Then Π[𝑗] = Q𝑖 and also Π[𝑗] = Q𝑖′ where 𝑖≠𝑖′. This contradicts Lemma 3.2.5.

• Suppose 𝑗> 𝑗′ > 𝑖. Then Π[𝑗] = Q𝑖 and Π[𝑗′] = Q𝑖′ and 𝑗> 𝑗′ > 𝑖> 𝑖′. This contradicts Lemma 5.2.2.

All three subcases are impossible, so we have a contradiction as required. □

We mention one more small observation, with a slightly non-obvious proof:

Lemma 5.2.5 (Cut endpoints active).

Suppose Π is a derivation and suppose that the final derivation-step in Π is (Cutk,j,i). Then 𝑘 and 𝑖 are active in Π.

Proof

We will prove this by contradiction.

Suppose 𝑘 is inactive in Π. By Corollary 5.1.2 Π[𝑘] =⋊𝑖′ for some index 𝑖′. However, we assumed that the final derivation-step in Π is (Cutk,j,i), and it follows from the structure of the Cut rule in Figure 9 that Π[𝑘] =↰𝑖. This contradicts injectivity of flag application (Definition 3.1.3).

The slightly non-obvious part of the proof is that the Cut rule does not place restrictions on the flag of 𝑖, so we cannot use the same argument to derive that 𝑖 is active. However, with our results so far another slick argument does work: we now know that 𝑘 is active in Π, and that Π[𝑘] =↰𝑖, so we can use Corollary 5.2.4 to conclude that 𝑖 is active in Π. □

5.3. Inactive if and only if Cut

Lemma 5.3.1 (Cut implies inactive) is straightforward given the machinery we have built already. The other direction (inactive implies Cut) is just a bit harder, and we prove it in Proposition 5.3.3:

Lemma 5.3.1 (Cut implies inactive).

Suppose Π is a derivation and 𝑗∈ index(Π). Then

• if (Cutk′,j′,i′) ∈Π for some 𝑘′, 𝑗′,𝑖′ ∈ index(Π) such that 𝑘′ > 𝑗> 𝑖′ (in words: if 𝑗 is bracketed by some Cut in Π),

• then 𝑗 is inactive in Π.

Proof

Let Π1 be the initial prefix of Π up to and including the (by Proposition 5.2.3 unique) instance of (Cutk′,j′,i′). By the structure of the Cut rule, Π1[𝑘′] =↰𝑖′. By Lemma 5.2.2 Π[𝑘′] = Q′′ 𝑖′′ for some Q′′ ∈{↰,⋊,⋉} and some 𝑖′′ ∈ index(Π) such that 𝑖′ ≥𝑖′′. Because 𝑘′ > 𝑗> 𝑖′ ≥𝑖′′, by Definition 4.1.5 𝑗 is inactive in Π. □

Lemma 5.3.2 (Jump implies Cut exists).

Suppose Π is a derivation and 𝑘∈ index(Π). Then

• if Π[𝑘] = Q𝑖 for some 𝑖∈ index(Π) such that 𝑘≥𝑖+2 — note: it follows from this assumption that 𝑘≥ 3, since the least possible value for 𝑖∈ index(Π) is 1 —

• then (Cutk,j,i) ∈Π for some 𝑗∈ index(Π) such that 𝑘> 𝑗> 𝑖.

Proof

We reason by induction on Π. Write Π1 for the initial prefix of Π up to and not including its final derivation step (if such an initial prefix exists). We consider possibilities for the final derivation step in Π:

• Suppose Π concludes with (Incj) (where 𝑗 may or may not equal 𝑘). By assumption in (Inc) the flag of 𝑡𝑗 is equal to the flag of 𝑡′ 𝑗. We use the inductive hypothesis on Π1.

• Suppose Π concludes with (Init). Then Π1 does not exist but there is nothing to prove because Π[𝑘] = Q𝑘−1 is guaranteed.

• Suppose Π concludes with (⋊Introj). By the structure of the rule, this derivation rule may change a ↰𝑖-flagged time in Π1[𝑗] into a ⋊𝑖-flagged time in Π[𝑗], but it does not change the index pointer 𝑖. We use the inductive hypothesis on Π1.

• Suppose Π concludes with (⋉Introj). As for the case of (⋉Introj).

• Suppose Π concludes with (Cutk′,j′,i′). If 𝑘= 𝑘′ then we can just take 𝑗= 𝑗′ and 𝑖= 𝑖′ and our instance of Cut is the final derivation step in Π and we are done. If 𝑘≠𝑘′ then we use the inductive hypothesis on Π1. □

Proposition 5.3.3 presents the reverse implication to Lemma 5.3.1, as promised:

Proposition 5.3.3 (Inactive implies Cut).

Suppose Π is a derivation and 𝑗∈ index(Π). Then

• if 𝑗 is 𝑘,𝑖-inactive (Definition 4.1.5) for some 𝑘 and 𝑖,

• then Π contains a (by Proposition 5.2.3 unique) cut (Cutk′,j,i′) for some 𝑘′,𝑖′ ∈ index(Π) such that 𝑘≥𝑘′ > 𝑗> 𝑖′ ≥𝑖.

Proof

We reason by induction on Π.

Unpacking Definition 4.1.5, 𝑗 is inactive when there exist 𝑘> 𝑗> 𝑖 such that Π[𝑘] = Q𝑖 for Q ∈{↰,⋊,⋉}. By Lemma 5.3.2 there is a 𝑗′ ∈ index(Π) such that 𝑘> 𝑗′ > 𝑖 and (Cutk,j′,i) ∈Π. Let Π1 be the initial prefix of Π up to but not including that instance of Cut.

There are now three cases depending on whether 𝑗′ = 𝑗, 𝑗′ > 𝑗, or 𝑗> 𝑗′. We consider each in turn:

• Suppose 𝑗= 𝑗′. Then we have found our instance of (Cutk′,j,i′), where 𝑘′ = 𝑘 and 𝑖′ = 𝑖, and we are done.

• Suppose 𝑗′ > 𝑗. From the form of (Cutk,j′,i), it must be that Π1[𝑗′] = Q𝑖 and 𝑗′ > 𝑗> 𝑖. So by Definition 4.1.5 𝑗 is 𝑗′,𝑖-inactive in Π1. By inductive hypothesis

(Cutk′,j,i′) ∈Π1 for some 𝑘′,𝑖′ ∈ index(Π1) such that 𝑗′ ≥𝑘′ > 𝑗> 𝑖′ ≥𝑖. We note that 𝑘> 𝑗′ ≥𝑘′ > 𝑗> 𝑖′ ≥𝑖 so 𝑘≥𝑘′ > 𝑗> 𝑖′ ≥𝑖 and we are done.

• Suppose 𝑗> 𝑗′. From the form of (Cutk,j′,i), it must be that Π1[𝑘] = Q𝑗′ and 𝑘> 𝑗> 𝑗′. So by Definition 4.1.5 𝑗 is 𝑘, 𝑗′-inactive in Π1. By inductive hypothesis (Cutk′,j,i′) ∈Π1 for some 𝑘′,𝑖′ ∈ index(Π1) such that 𝑘≥𝑘′ > 𝑗> 𝑖′ ≥𝑗′. We note that 𝑘≥𝑘′ > 𝑗> 𝑖′ ≥𝑗′ > 𝑖 so 𝑘≥𝑘′ > 𝑗> 𝑖′ ≥𝑖 and we are done. □

Corollary 5.3.4 is a convenient wrapper for Proposition 5.3.3:

Corollary 5.3.4 (Inactive implies Cut (refined version)).

Suppose Π is a derivation and 𝑗∈ index(Π). Then

• if 𝑗 is 𝑘,𝑖-inactive (Definition 4.1.5) for some 𝑘 and 𝑖,

• then there exist initial prefixes Π2 of Π, and Π1 of Π2, such that:

– 𝑗 is active in Π1.

– Π2 extends Π1 with an instance of (Cutk′,j,i′) for some 𝑘′,𝑖′ ∈ index(Π) such that 𝑘≥𝑘′ > 𝑗> 𝑖′ ≥𝑖 (so that by Lemma 5.3.1 𝑗 is inactive in Π2).

Proof

Suppose 𝑗 is 𝑘,𝑖-inactive in Π, for some 𝑘 and 𝑖. By Proposition 5.3.3 we obtain (Cutk′,j,i′) ∈Π. We set Π1 to be the initial prefix of Π up to and not including the Cut, and Π2 to be the initial prefix of Π up to and including the Cut.

We note that 𝑗 is active in Π1. Because, if 𝑗 were inactive then by Proposition 5.3.3 it would be cut, meaning that Π would contain two cuts centred on 𝑗, which is impossible by Proposition 5.2.3. □

5.4. Matryoshka cut geometry

A Matryoshka doll is a traditional wooden figurine which opens to contain a smaller figurine inside it, which itself opens up, nesting recursively all the way down until there is no space left. Cuts display similar geometric structure:

Proposition 5.4.1 (Matryoshka Cuts).

Suppose Π is a derivation. Then for every 𝑘> 𝑗> 𝑖∈ index(Π),

• if (Cutk,j,i) ∈Π (i.e. if Π contains an instance of Cut),

• then for every 𝑖′ ∈ index(Π) we have:

– If 𝑗> 𝑖′ > 𝑖 then there exist 𝑗′′,𝑖′′ ∈ index(Π) such that 𝑗≥𝑗′′ > 𝑖′ > 𝑖′′ ≥𝑖 and Π contains a (by Proposition 5.2.3 unique) cut (Cutj′′,i′,i′′).

– If 𝑘> 𝑖′ > 𝑗 then there exist 𝑗′′,𝑖′′ ∈ index(Π) such that 𝑘≥𝑗′′ > 𝑖′ > 𝑖′′ ≥𝑗 and Π contains a (by Proposition 5.2.3 unique) cut (Cutj′′,i′,i′′).

Proof

Let Π1 be the initial prefix of Π up to and not including the instance of (Cutk,j,i), and suppose 𝑗> 𝑖′ > 𝑖 or 𝑘> 𝑖′ > 𝑗.

By the form of the Cut rule, Π1[𝑘] =⋉𝑗 and Π1[𝑗] =⋊𝑖. Thus by Definition 4.1.5 𝑖′ is 𝑘, 𝑗-inactive or 𝑗,𝑖-inactive in Π1. We use Proposition 5.3.3.

□

Remark 5.4.2

It might be helpful to illustrate Proposition 5.3.3 with a diagram:

8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1

Above, we assume we know that a (Cut8,3,1) exists. We illustrate this with a pair of upper braces.

Then within this Cut must be nested — all the way down, like a series of Russian (Matryoshka) dolls — some structure of cuts cutting every index between 8 and 3, and every index between 3 and 1. We illustrate this with pairs of lower braces.

We emphasise that the point here is that cuts nest and also that this nesting is ‘space-filling’ in the sense that every index between the outermost cut indexes (8 to 1, in this example) is cut.

The lower braces are vertically offset so they do not overlap, but note that there is no external sense of time in which they must be totally ordered; there is just the times and the nesting implicit in the indexes themselves (as we make formal in a moment in Corollary 5.4.3). For example: the (Cut3,2,1) must occur at times before the times of the (Cut8,3,1), but there is no external sense in which it must necessarily occur before or after (say) the (Cut6,5,4).

Corollary 5.4.3 makes formal an observation in Remark 5.4.2, and it will be useful later on in Proposition 5.5.4:

Corollary 5.4.3 (Cuts are ordered by derivation).

Suppose that:

• Π is a derivation.

• 𝑘> 𝑗> 𝑖∈ index(Π) and 𝑘′ > 𝑗′ > 𝑖′ ∈ index(Π), and furthermore 𝑘> 𝑗′ > 𝑖.

• (Cutk,j,i), (Cutk′,j′,i′) ∈Π.

Then there exist initial prefixes Π2 of Π, and Π1 of Π2, such that:

• Π1 ends with the (by Proposition 5.2.3 unique) instance of (Cutk′,j′,i′).

• Π2 ends with the (likewise unique) instance of (Cutk,j,i).

• 𝑘= 𝑘′ ∧𝑗= 𝑗′ ∧𝑖= 𝑖′ or 𝑘≥𝑘′ > 𝑗′ > 𝑖′ ≥𝑗 or 𝑗≥𝑘′ > 𝑗′ > 𝑖′ ≥𝑖.

Intuitively: if (Cutk,j,i) appears in Π then any distinct cut centred on indexes between 𝑘 and 𝑖 must come before and nested inside that Cut.

Proof

The machinery we have built so far gives a slick proof.

Let Π2 be the initial prefix of Π up to and including the instance of (Cutk,j,i). Because 𝑘> 𝑗′ > 𝑖 and also 𝑘> 𝑗> 𝑖, either 𝑘> 𝑗′ > 𝑗 or 𝑗= 𝑗′ or 𝑗> 𝑗′ > 𝑖. We consider each possibility:

• Suppose 𝑗= 𝑗′. Then by affine cuts (Proposition 5.2.3) 𝑘= 𝑘′ and 𝑖= 𝑖′ and the result follows trivially.

• Suppose 𝑗> 𝑗′ > 𝑖. By Matryoshka cuts (Proposition 5.4.1) there is some cut in Π2 centred on 𝑗′ and nested between 𝑘 and 𝑗, and by affine cuts (Proposition 5.2.3) that cut must be the instance of (Cutk′,j′,i′).

• Suppose 𝑘> 𝑗′ > 𝑗. As for the previous case. □

Corollary 5.4.4 (Cuts nest).

Suppose that:

• Π is a derivation.

• (Cutk,j,i) ∈Π and (Cutk′,j′,i′) ∈Π for 𝑘> 𝑗> 𝑖∈ index(Π) and 𝑘′ > 𝑗′ > 𝑖′ ∈ index(Π).

Then precisely one of the following conditions must hold:

𝑘=𝑘′ ∧𝑗=𝑗′ ∧𝑖=𝑖′𝑘′> 𝑗′>𝑖′≥𝑘> 𝑗>𝑖 𝑘≥𝑘′> 𝑗′>𝑖′≥𝑗>𝑖 𝑘> 𝑗≥𝑘′> 𝑗′>𝑖′≥𝑖𝑘′≥𝑘> 𝑗>𝑖≥𝑗′>𝑖′𝑘′> 𝑗′≥𝑘> 𝑗>𝑖≥𝑖′𝑘> 𝑗>𝑖≥𝑘′> 𝑗′>𝑖′

This is just a symbolic way of saying that the two cuts must either be equal, side-by-side, or nested.

Proof

By routine arguments from Corollary 5.4.3. □

5.5. (In)compatible cuts

5.5.1. Compatible cuts

Lemma 5.5.1 is a technical property which will help us prove Proposition 5.5.2:

Lemma 5.5.1

Suppose that:

• (Π1, Π′ 1) is a circuit-derivation.

• 𝑗∈ index(Π1, Π′ 1) is doubly active in (Π1, Π′ 1) (Definition 4.3.1(4c); 𝑗 is active in both Π1 and Π′ 1 as per Definition 4.1.5).

• Π2 extends Π1 with one derivation step (Cutk,j,i), and Π′ 2 extends Π′ 1 with one derivation step (Cutk′,j,i). Note that these two Cuts are both centred on 𝑗, and are right-compatible (i.e. they both cut 𝑗 to the same right index 𝑖).

• Π1[𝑗] ⚡ Π′ 1[𝑗].

Given the above, we have that:

1. 𝑗 is inactive in (Π2, Π′ 2).

2. 𝑖 is doubly active in (Π2, Π′ 2).

3. 𝑖, 𝑗< length(Π1, Π′ 1), so by Definition 4.3.1(1) ctrl(Π1[𝑗]) = ctrl(Π′ 1[𝑗]) and ctrl(Π1[𝑖]) = ctrl(Π′ 1[𝑖]).

4. 𝑖 is inconsistent in (Π2, Π′ 2).

Proof

The proof is just a matter of chasing definitions and checking structure, but we have built up quite a lot of structure and definitions by now, so we give full details. We consider each part in turn:

1. 𝑗 is Cut in both derivations of (Π2, Π′ 2), so it is inactive by Lemma 5.3.1.

2. 𝑖 is doubly active in (Π2, Π′ 2) by Lemma 5.2.5 (cut endpoints active).

3. By construction 𝑘∈ index(Π1) = index(Π2), and it follows using Definition 4.3.1(1) that 𝑘≤ length(Π1). Furthermore 𝑘> 𝑗> 𝑖.

4. By the form of the Cut rule, Π2[𝑖] = 𝑡𝑖#Π1[𝑗] and Π′ 2[𝑖] = 𝑡′ 𝑖#Π′ 1[𝑗] for suitable 𝑡𝑖 and 𝑡′ 𝑖. We assumed Π1[𝑗] ⚡ Π′ 1[𝑗] so by Definition 2.2.2(7c) (since ctrl(Π1[𝑗]) = ctrl(Π′ 1[𝑗]) and ctrl(Π1[𝑖]) = ctrl(Π′ 1[𝑖])) Π2[𝑖] ⚡ Π′ 2[𝑖] as required.25 □

Proposition 5.5.2

Suppose (Π, Π′) is a circuit-derivation and 𝑗′ ∈ index(Π, Π′), and suppose (Π, Π′) has right-compatible cuts at all indexes up to and including 𝑗′. Then

• if 𝑗′ is inconsistent in (Π, Π′) (Definition 4.3.2(1)),

• then there exists 𝑙∈ index(Π, Π′) such that 𝑗′ ≥𝑙 and 𝑙 is active inconsistent in (Π, Π′).

Proof

Let 𝑗≤𝑗′ be the least inconsistent index in (Π, Π′); note by construction that (Π, Π′) has right-compatible cuts at all indexes up to and including 𝑗. There are now two cases:

• Suppose 𝑗 is active in (Π, Π′). Unpacking Definition 4.3.1(4b), 𝑗 is active in at least one of Π or Π′ in the sense of Definition 4.1.5. Then we set 𝑙= 𝑗 and by Definition 4.3.2(3) we are done.

• Suppose 𝑗 is inactive in (Π, Π′) meaning by Definition 4.3.1(4d) that 𝑗 is inactive in both Π and Π′ in the sense of Definition 4.1.5. We will derive a contradiction. By Corollary 5.3.4 (since 𝑗 is inactive in Π and Π′), we have the following data:

– Instances of Cut: (Cutk,j,i) ∈Π for some 𝑘> 𝑗> 𝑖; and (Cutk′,j,i′) ∈Π′ for some 𝑘′ > 𝑗> 𝑖′. By our assumption of right-compatible cuts, 𝑖′ = 𝑖.

– An initial prefix Π1 of Π, consisting of derivation-steps from Π up to and not including the instance of (Cutk,j,i), such that 𝑗 is active in Π1.

– An initial prefix Π′ 1 of Π′, consisting of derivation-steps from Π′ up to and not including the instance of (Cutk′,j,i), such that 𝑗 is active in Π′ 1.

– Initial prefixes Π2 of Π and Π′ 2 of Π′ consisting of the initial prefixes of Π and Π′ respectively including the cuts.

– Note by Lemma 5.3.1 that 𝑗 is inactive in Π2 and Π′ 2 and in all initial prefixes of Π and Π′ respectively that contain them.

Now we assumed that 𝑗 is inconsistent in (Π, Π′), so by Definition 4.3.2(1) there exist initial prefixes Π∗ of Π and Π′ ∗ of Π′ such that 𝑗 is active in both, and Π∗[𝑗] ⚡ Π′ ∗[𝑗]. Furthermore Π1 and Π′ 1 are the greatest initial prefixes of Π and Π′ respectively at which 𝑗 is active, so that (Π∗, Π′ ∗) must be an initial prefix of (Π1, Π′ 1). It follows by Proposition 4.3.4(1) that Π1[𝑗] ⚡ Π′ 1[𝑗]. Thus, the conditions of Lemma 5.5.1 are satisfied — we have a circuit-derivation (Π1, Π′ 1) in which 𝑗 is doubly active and Π1[𝑗] ⚡ Π′ 1[𝑗] and Π2 and Π′ 2 extend Π1 and Π′ 1 with (Cutk,j,i) and (Cutk′,j,i) — and so we have that 𝑖 is (doubly) active inconsistent in (Π2, Π′ 2). It follows from Definition 4.3.2(1) that 𝑖 is inconsistent in (Π, Π′). However, we assumed that 𝑗 is the least inconsistent index in (Π, Π′), so the existence of this lesser inconsistent 𝑖< 𝑗 contradicts leastness of 𝑗, and we are done. □

5.5.2. Incompatible cuts

Corollary 5.5.3

Suppose that:

1. (Π, Π′) is a circuit-derivation of (𝑇,𝑇′).

2. Π contains an instance of (Cutk,j,i) where 𝑘> 𝑗> 𝑖∈ index(Π, Π′).

3. Π′ contains an instance of (Cutk′,j,i′) where 𝑘′ > 𝑗> 𝑖′ ∈ index(Π, Π′).

4. 𝑖′ > 𝑖 (it will not matter whether 𝑘= 𝑘′, 𝑘< 𝑘′, or 𝑘′ > 𝑘).

5. (Π, Π′) has right-compatible cuts at all indexes strictly less than 𝑗.

Then we have:

1. either Π contains an instance of (Cutj,i′,i′′) for some 𝑖′′ ∈ index(Π, Π′) such that 𝑖′ > 𝑖′′ ≥𝑖,

2. or (Π, Π′) contains an active inconsistent index 𝑗′′′ such that 𝑗> 𝑗′′′.

Proof

For clarity and to help with intuition, we illustrate the situation considered in this Corollary. In the diagram below, pairs of braces denote instances of Cut ((Cutk′,j,i′) in path 𝑇′ and (Cutk,j,i) in path 𝑇):

Π′ derives path 𝑇′𝑘′′ 𝑘′· · · 𝑗 · 𝑖′ 𝑖Π derives path 𝑇 𝑘′′ 𝑘′ 𝑘 · · 𝑗 · · 𝑖

This diagram suggests that in path 𝑇, either 𝑗 is the index that cut 𝑖′, or some other index has been inconsistent. This result proves that this intuition is accurate.

By assumption Π contains an instance of (Cutk,j,i), so by Proposition 5.3.3 (since 𝑗> 𝑖′ > 𝑖) Π contains an instance of (Cutj′′,i′,i′′) for some 𝑗′′,𝑖′′ ∈ index(𝑇) such that 𝑗≥𝑗′′ > 𝑖′ > 𝑖′′ ≥𝑖.

• Suppose 𝑗= 𝑗′′. Then Π contains an instance of (Cutj,i′,i′′) and 𝑖′ > 𝑖′′ ≥𝑖, so we are done.

• So now suppose 𝑗> 𝑗′′. By the form of (Cutj′′,i′,i′′) we know that there is an initial prefix Π1 of Π (up to and including the instance of (Cutj′′,i′,i′′) in Π), such that Π1[𝑗′′] =↰𝑖′′. By Lemma 5.2.5 (cut endpoints active) 𝑗′′ is active in Π1. By (Cutk′,j,i′) ∈Π′ and Proposition 5.4.1 (Matryoshka cuts) (because 𝑘′ > 𝑗> 𝑗′′ > 𝑖′) there exists an initial prefix Π′ 1 of Π′ up to and not including some instance of Cut centred on 𝑗′′, and by the form of the Cut rule Π′ 1[𝑗′′] =⋊𝑖′′′ for some 𝑖′′′ ≥𝑖′. By Lemma 3.2.4 (since 𝑖′′′ > 𝑖′′) ⋊𝑖′′′⚡↰𝑖′′, thus Π1[𝑗′′] ⚡ Π′ 1[𝑗′′] and 𝑗′′ is inconsistent in (Π, Π′).
By Proposition 5.5.2 (since 𝑗> 𝑗′′ and (Π, Π′) has right-compatible cuts at all indexes strictly less than 𝑗) there exists 𝑗′′′ an active inconsistent index in (Π, Π′) such that 𝑗′′ ≥𝑗′′′, and since 𝑗> 𝑗′′ also 𝑗′′′ is active inconsistent such that 𝑗> 𝑗′′′, and again we are done.
□

Proposition 5.5.4

Suppose (Π, Π′) is a circuit-derivation. Then

• if (Π, Π′) contains a right-incompatible pair of cuts at some 𝑗∈ index(Π, Π′) (Definition 4.3.6(3)),

• then (Π, Π′) has an active inconsistent index (Definition 4.3.2(3)) 𝑗′′′ such that 𝑗> 𝑗′′′, and (Π, Π′) has right-compatible cuts at all indexes no greater than 𝑗′′′.

Proof

Let 𝑗 be the least index such that (Π, Π′) contains a right-incompatible pair of cuts (Cutk,j,i) in Π and (Cutk′,j,i′) in Π′. By our assumption of right-incompatibility 𝑖≠𝑖′, so without loss of generality suppose 𝑖′ > 𝑖. Write

• Π1 for the initial prefix of Π (Definition 4.2.1) up to the (by Proposition 5.2.3 unique) instance of (Cutk,j,i) in Π, and

• Π′ 1 for the initial prefix of Π′ up to the instance of (Cutk′,j,i′) in Π′.

Because 𝑗 is the least index with a right-incompatible cut pair in (Π, Π′), any cut-pairs in (Π, Π′) at indexes less than 𝑗 are right-compatible.

Now by Corollary 5.5.3,

• either (Π, Π′) contains an active inconsistent index 𝑗′′′ such that 𝑗> 𝑗′′′.

• or (Cutj,i′,i′′) ∈Π for some 𝑖′ > 𝑖′′ ≥𝑖,

In the former case we are done: 𝑗′′′ is an active inconsistent index, and (Π, Π′) has right-compatible cuts at all indexes less than 𝑗, and thus at all indexes no greater than 𝑗′′′ < 𝑗.

So suppose we are in the latter case and (Cutj,i′,i′′) ∈Π. We note that

(Cutj,i′,i′′) ∈Π1 by Corollary 5.4.3 (since Π1 concludes with (Cutk,j,i) and 𝑘> 𝑗> 𝑖′ > 𝑖′′ ≥𝑖).

We note that:

1. Π′ 1 concludes with (Cutk′,j,i′) and from the structure of the Cut rule in Figure 9 it follows that

Π′ 1[𝑖′] = 𝑡′ 𝑖′#⋊𝑖′(𝑡′ 𝑗#⋉𝑗𝑡′ 𝑘′)

for some 𝑡′ 𝑖′,𝑡′ 𝑗,𝑡′ 𝑘′ ∈ CTime (cf. Remark 4.1.4(8b)).

2. Π1 contains an instance of (Cutj,i′,i′′). Write Π2 for the initial prefix of Π1 up to and not including that Cut. From the structure of the Cut rule

Π2[𝑖′] =⋊𝑖′′(𝑡𝑖′#⋉𝑖′𝑡𝑗)

for some 𝑡𝑖′,𝑡𝑗∈ CTime.

3. By Definition 3.2.1(4)

⋉𝑖′𝑡𝑗⚡⋊𝑖′(𝑡′ 𝑗#⋉𝑗𝑡′ 𝑘′).

We now reason as follows:

Π2[𝑖′] =⋊𝑖′′(𝑡𝑖′#⋉𝑖′𝑡𝑗)⪰𝑡𝑖′#⋉𝑖′𝑡𝑗Definition 3.1.1(2) (cf. Remark 4.1.4(8c))⚡ 𝑡′ 𝑖′#⋊𝑖′(𝑡′ 𝑗#⋉𝑗𝑡′ 𝑘′) Def. 2.2.2(7c) (# contradiction-preserving)= Π′ 1[𝑖′]

By Lemma 2.1.6 (contradiction is monotone) we conclude that

Π2[𝑖′] ⚡ Π′ 1[𝑖′].

Now 𝑖′ is active in Π2 by construction, and by Lemma 5.2.5 (cut endpoints active) 𝑖′ is active in Π′ 1 because it is the endpoint of (Cutk′,j,i′). Π2 is an initial prefix of Π and Π′ 1 is an initial prefix of Π′, thus 𝑖′ is an inconsistent index in (Π, Π′).

Since 𝑖′ < 𝑗, the leastness of 𝑗 implies that (Π, Π′) has right-compatible cuts at all indexes no greater than 𝑖′. Thus by Proposition 5.5.2 there is an active inconsistent index 𝑗′′′ ≤𝑖′ < 𝑗 such that (Π, Π′) has right-compatible cuts at all indexes no greater than 𝑗′′′. □

5.6. Main result: inconsistent index implies active inconsistent index

Remark 5.6.1

We are now ready to prove our main result, Theorem 5.6.2, that if a circuit-derivation contains an inconsistent index, then it contains an active inconsistent index. Before we get to the Theorem, it might be helpful to recall some intuitions about what ‘inconsistent index’ and ‘active inconsistent index’ mean (which are made precise in Definition 4.3.1):

• An index 𝑗 is inconsistent in (Π, Π′) when there are initial prefixes of Π and Π′ at which 𝑗 was active in both derivations and inconsistent.

• An index 𝑗 is active inconsistent when it is inconsistent and, in at least one of the derivations, 𝑗 has not yet been cut.

Note that:

• ‘Being inconsistent’ is not the same thing as Π[𝑗] ⚡ Π′[𝑗]; to be inconsistent, there must be a contradiction at two times during which 𝑗 was active (whence the mention of initial prefixes).

• The import of Theorem 5.6.2 is not “You cannot inactivate an active inconsistency”. It is “inactivating an active inconsistency, itself creates another active inconsistency”. It might be helpful to think of this in terms of cover-ups. Recall the expression “it’s not the crime, it’s the cover-up”: committing a crime is one thing, but covering up a crime is in itself a crime. The proof of Theorem 5.6.2 has a similar flavour, that you cannot just eliminate an active inconsistency by cutting it away; the act of cutting an inconsistency, itself creates an active inconsistency elsewhere.

Theorem 5.6.2

Suppose (Π, Π′) is a circuit-derivation. Suppose 𝑗∈ index(Π, Π′) is an inconsistent index (Definition 4.3.2(1)). Then there exists 𝑙∈ index(Π, Π′) such that:

• 𝑙≤𝑗 and

• (Π, Π′) has right-compatible cuts at all indexes no greater than 𝑙 (Definition 4.3.6(4)) and

• 𝑙 is active inconsistent in (Π, Π′) (Definition 4.3.2(3)).

For clarity, we unpack this result in more detail:

• if there exist initial segments Π1 of Π and Π′ 1 of Π′ and an index 𝑗∈ index(Π1, Π′ 1) such that 𝑗 is active in both Π1 and Π′ 1, and Π1[𝑗] ⚡ Π′ 1[𝑗],

• then there exists some index 𝑙∈ index(Π, Π′) which is no greater than 𝑗, such that 𝑙 is active in at least one of Π and Π′, and (Π, Π′) has right-compatible cuts up to 𝑙, and there exist initial segments Π2 of Π and Π′ 2 of Π′ such that Π2[𝑙] ⚡ Π′ 2[𝑙].

Proof

Let 𝑗′ ∈ index(Π, Π′) be the least inconsistent index in (Π, Π′).

We note from Proposition 5.5.4 that (Π, Π′) has right-compatible cuts at all indexes no greater than 𝑗′, because otherwise by that Proposition there would be a lesser active inconsistent index in (Π, Π′).

Then we use Proposition 5.5.2. □

Corollary 5.6.3 might look abstract, but it is actually a very practical result. Participants can prove the consistency of a circuit-derivation, provided that their trust assumptions are valid: if they trust every active controller in the circuit to never produce conflicting times, and if this trust assumption is correct, then the circuit-derivation is indeed consistent.

Corollary 5.6.3

Suppose (Π, Π′) is a circuit-derivation. Then

• if (Π, Π′) is inconsistent (Definition 4.3.2(2))

• then (Π, Π′) is active inconsistent (Definition 4.3.2(4)).

Intuitively: we cannot use the rules in Figure 9 to remove an active inconsistency.

Proof

We just unpack the definition of inconsistent and active inconsistent circuit in Definition 4.3.2(2&4) and use Theorem 5.6.2. □

Corollary 5.6.4 will be useful later:

Corollary 5.6.4

Suppose (Π, Π′) is an inconsistent circuit-derivation. Then the least inconsistent index 𝑗 is active inconsistent, and (Π, Π′) has right-compatible cuts at all indexes no greater than (i.e. up to and including) 𝑗.

Proof

Suppose 𝑗 is inconsistent. By Theorem 5.6.2 there exists a no greater active inconsistent index 𝑙≤𝑗 such that (Π, Π′) has right-compatible cuts at all indexes no greater than 𝑙. But an active inconsistent index is also an inconsistent index, so by leastness of 𝑗 we have that 𝑙= 𝑗. □

6. A Stronger Safety Property

6.1. Motivation

Corollary 5.6.3 allows participants to prove the consistency of a circuit-derivation (Π, Π′) based on trust assumptions:

• if they correctly trust every active controller in (Π, Π′) to never produce conflicting times,

• then the circuit-derivation (Π, Π′) is consistent.

Recall that this matters because our circuit evolution rules from Figure 9 generalise token (un)wrapping to a local, non-blocking (Cut) operation.

We now improve on Corollary 5.6.3 by removing its trust requirement. With a bit more work we can strengthen its guarantee such that participants can prove absolutely — without needing to trust any other controllers — that a circuit-derivation (Π, Π′) is consistent. For example, this would be useful for proving things to participants with different trust assumptions.

In particular, if we prove that, among active controllers, all the times that they have attested to (and all the times they have attested to, and so on) are consistent, then the circuit-derivation must be consistent (Theorem 6.4.3). In principle, creating this proof requires only information about past times of active controllers.

Taking a step back, we see a tradeoff:

• Proofs-with-trust as per Corollary 5.6.3 are fast, but they are contingent on trust assumptions. This has two effects: if participant A’s trust assumptions are wrong then Corollary 5.6.3 cannot protect it; and A’s proofs might not compose with proofs of other participants, if these other proofs are contingent on trust assumptions that are not a superset of A’s trust assumptions.

• Absolute proofs as per Theorem 6.4.3 are somewhat slower and harder to produce, but in return we obtain better composability properties: participants can provide absolute correctness proofs (with no trust required!), which are convincing even across different trust assumptions.

6.2. Additional machinery: C-closure of T

Definition 6.2.1

Suppose L = (Ctrl, Time, #, ctrl) is a located semilattice and T ⊆ Time is a set of times and C ⊆ Ctrl is a set of controllers. Define |T |C the C-closure of T, to be the least set of times with the following properties, also illustrated in Figure 13:

1. Contains the C-controlled subset of T.

If 𝑡∈T and ctrl(𝑡) ∈C then 𝑡∈|T |C.

2. Closed under C-attestation.

If 𝑡#𝑠∈|T |C and ctrl(𝑠) ∈C then 𝑠∈|T |C.
Lemma 6.2.2

Suppose L = (Ctrl, Time, #, ctrl) is a located semilattice and T ⊆ Time and C ⊆ Ctrl. Then:

1. If 𝑡∈|T |C then ctrl(𝑡) ∈C.

2. If 𝑡′ ⪯𝑡∈|T |C then 𝑡′ ∈|T |C.

3. If 𝑡#𝑠∈|T |C then 𝑡∈|T |C, and if furthermore ctrl(𝑠) ∈C then also 𝑠∈|T |C.

𝑡∈T ctrl(𝑡) ∈C(CInit)(𝑡∈|T |C)𝑡#𝑠∈|T |C(ctrl(𝑠) ∈C)(CAttest)𝑠∈|T |C
Figure 13. C-closure of T (Definition 6.2.1)
Proof

We consider each part in turn:

1. We examine the two clauses in Definition 6.2.1 or Figure 13 and see that they only add times whose controllers are in 𝐶.

2. Suppose 𝑡′ ⪯𝑡. By Definition 2.2.2(6b) this means precisely that ctrl(𝑡) = ctrl(𝑡′) and 𝑡= 𝑡#𝑡′. We use Definition 6.2.1(2).

3. Suppose 𝑡#𝑠∈|T |C. By expansivity of attestation (Definition 2.2.2(7b)) 𝑡⪯𝑡#𝑠 so by part 2 of this result 𝑡∈|T |C. If furthermore ctrl(𝑠) ∈C then by (CAttest) in Figure 13 (equivalently: Definition 6.2.1(2)) 𝑠∈|T |C. □

6.3. Additional machinery: chain of cuts

Here and for the rest of this Section we suppose L = (Ctrl, Time, #, ctrl) is a located semilattice with Cut.

A notion of a chain of cuts will help us in Lemma 6.3.3 and Theorem 6.4.3:

Definition 6.3.1

Suppose Π is a derivation and 𝑖∈ index(Π) and 𝑖 is inactive in Π. Define the chain of cuts of 𝑖 in Π to be a tuple (𝑖= 𝑖1,𝑖2, . . . ,𝑖𝑛) such that:

1. 𝑖= 𝑖1.

2. 𝑖1, 𝑖2, ..., 𝑖𝑛−1 are inactive in Π.

3. 𝑖𝑛 is active in Π.

4. There exist 𝑘1, . . . ,𝑘𝑛−1 ∈ index(Π) such that for each 1 ≤𝑙< 𝑛 we have (Cutkl,il,il+1) ∈Π.

Lemma 6.3.2

Suppose Π is a derivation and 𝑖∈ index(Π) and 𝑖 is inactive in Π. Then (𝑖= 𝑖1,𝑖2, . . . ,𝑖𝑛) the chain of cuts of 𝑖 in Π from Definition 6.3.1 is well-defined.

Proof

By an easy induction on the index 𝑖.

By Proposition 5.3.3 (inactive implies cut) 𝑖 is cut to some lesser 𝑖2 < 𝑖. By Proposition 5.2.3 (affine cuts) that cut is unique, so 𝑖2 is uniquely defined. There are now two possibilities:

• If 𝑖2 is active in Π then the chain of cuts from 𝑖 is (𝑖= 𝑖1,𝑖2).

• If 𝑖2 is inactive then we use the inductive hypothesis on 𝑖2 < 𝑖. We let 𝐼= (𝑖2, . . . ,𝑖𝑛) be (by inductive hypothesis well-defined) chain of cuts from 𝑖2. Then 𝑖::𝐼 (𝑖 prepended to 𝐼) is the chain of cuts from 𝑖. □

Lemma 6.3.3

Suppose that:

• (Π, Π′) is a circuit-derivation.

• 𝑖 is the least inconsistent index in (Π, Π′), thus by Corollary 5.6.4 it is also active.

• 𝑖 is inactive in Π and active in Π′.

• (𝑖= 𝑖1,𝑖2, . . . ,𝑖𝑛) is the chain of cuts of 𝑖 in Π (Definition 6.3.1).

Then {𝑖1,𝑖2, . . . ,𝑖𝑛−1} are all active in Π′.

Proof

Note by Corollary 5.6.4 that (Π, Π′) has right-compatible cuts at all indexes no greater than 𝑖. Also recall from Lemma 5.3.1 and Proposition 5.3.3 that an index is inactive if and only if it is cut; we may use ‘inactive’ and ‘cut’ synonymously.

Suppose there exists some 𝑖𝑙∈{𝑖1,𝑖2, . . . ,𝑖𝑛−1} such that 𝑖𝑙 is inactive in Π′. Let 1 ≤𝑙< 𝑛 be least such (so that 𝑖𝑙 is greatest in {𝑖1,𝑖2, . . . ,𝑖𝑛−1} such that 𝑖𝑙 is inactive in Π′). We will derive a contradiction.

Note that 𝑖𝑙 is cut to 𝑖𝑙+1 in both Π and Π′, because we have assumed right-compatible cuts at all indexes up to and including 𝑖. So we assume there exist 𝑘′,𝑘> 𝑖𝑙 such that

(Cutk′,il,il+1) ∈Π′and (Cutk,il,il+1) ∈Π.

We assumed that 𝑖 is active in Π′, so by Lemma 5.3.1 𝑖≥𝑘′ > 𝑖𝑙 (cut implies inactive; if 𝑘′ > 𝑖 then 𝑖 would be cut and thus inactive). Also by the chain of cuts (𝑖= 𝑖1, . . . ,𝑖𝑛) which we assumed exists in Π, by Lemma 5.3.1 (cut implies inactive) every index from 𝑖 (inclusive) to 𝑖𝑛 (exclusive) is inactive in Π. Since 𝑖≥𝑘′ > 𝑖𝑙> 𝑖𝑛, we have that 𝑘′ is inactive and thus cut in Π.

We now examine 𝑘′:

• Let 𝑙′ < 𝑙 be the index such that 𝑖𝑙′ ≥𝑘′ > 𝑖𝑙′+1 ≥𝑖𝑙 (𝑖𝑙′+1 ≥𝑖𝑙 because 𝑙′ < 𝑙).

• Using Corollary 5.4.4 (cuts nest) 𝑘′ must get cut to an index no less than 𝑖𝑙′+1 in Π, because (Cutkl′,il′,il′+1) ∈Π for some 𝑘𝑙′ ∈ index(Π), and 𝑖𝑙′ ≥𝑘′ > 𝑖𝑙′+1. Let Π1 be the initial prefix of Π up to and not including that (by Proposition 5.2.3 unique) instance of Cut. So 𝑘′ is active in Π1 and Π1[𝑘′] =⋊𝑖′𝑡𝑘′ for some 𝑖′ ≥𝑖𝑙 and some consistent time 𝑡𝑘′.

• But also (Cutk′,il,il+1) ∈Π′. Let Π′ 1 be the initial prefix of Π′ up to and including the (by Proposition 5.2.3 unique) instance of (Cutk′,il,il+1). By Lemma 5.2.5 (cut endpoints active) 𝑘′ is active in Π′ 1, and by the structure of the Cut rule Π′ 1[𝑘′] =↰𝑖𝑙+1𝑡′ 𝑘′ for some consistent time 𝑡′ 𝑘′.

• By Lemma 3.2.4 (since 𝑖′ ≥𝑖𝑙> 𝑖𝑙+1) ⋊𝑖′𝑡𝑘′ ⚡↰𝑖𝑙+1𝑡′ 𝑘′, meaning that 𝑘′ is an inconsistent index in (Π, Π′). By leastness of 𝑖, it follows that 𝑘′ = 𝑖.

So we have concluded that 𝑘′ = 𝑖. Now because 𝑖𝑙′ ≥𝑘′ > 𝑖𝑙′+1 it must be that 𝑙′ = 1 and 𝑘′ = 𝑖𝑙′ = 𝑖1 = 𝑖. Furthermore recall:

• 1 = 𝑙′ < 𝑙< 𝑛.

• (Cutk′,il,il+1) = (Cuti,il,il+1) ∈Π′ and ‘cut’=‘inactive‘, so that every 𝑖𝑙′′ for 𝑙′ < 𝑙′′ < 𝑙+1 is inactive.

• We chose 𝑙 least such that 𝑖𝑙 is inactive in Π′.

Putting this all together, it must be that 𝑙= 2.

Thus we have established that for some index 𝑘𝑙′ (we do not care what it is precisely)

(Cutk′,il,il+1) = (Cuti,i2,i3) ∈Π′ and (Cutkl′,il′,il′+1) = (Cutkl′,i,i2) ∈Π.

Let Π′ 2 be the initial prefix of Π′ up to and not including the (by Proposition 5.2.3 unique) instance of (Cuti,i2,i3). Write Π2 for the initial prefix of Π up to and including the (by Proposition 5.2.3 unique) instance of (Cutkl′,i,i2).

It follows from the structure of the Cut rule for (Cuti,i2,i3), and from Definition 3.1.1(2) (flags are expansive), that

Π′ 2[𝑖2] ⪰𝑡′ 𝑖2#𝑠′ 𝑖 for some 𝑠′ 𝑖=⋉𝑖2𝑖,

and by construction 𝑖2 is active in Π′ 2. It follows from the structure of the Cut rule for (Cutkl′,i,i2) that

Π2[𝑖2] = 𝑡𝑖2#𝑠𝑖 for some 𝑠𝑖=⋊𝑖2𝑖,

and by Lemma 5.2.5 (cut endpoints active) 𝑖2 is active in Π2.

By Definition 3.2.1(4) ⋉𝑖2𝑖⚡⋊𝑖2𝑖. By contradiction-preservation (Definition 2.2.2(7c))

Π′ 2[𝑖2] ⪰𝑡′ 𝑖2#𝑠′ 𝑖⚡ 𝑡𝑖2#𝑠𝑖= Π2[𝑖2].

By Lemma 2.1.6 (contradiction is monotone) we obtain

Π′ 2[𝑖2] ⚡ Π2[𝑖2].

By construction 𝑖2 is active in Π′ 2 and Π2, and the former is an initial prefix of Π′ and the latter is an initial prefix of Π, and it follows that 𝑖2 is an inconsistent index in Π, Π′. This contradicts the leastness of 𝑖> 𝑖2. □

6.4. Absolute consistency results

Recall from the start of Subsection 6.3 that we have supposed that L = (Ctrl, Time, #, ctrl) is a located semilattice with Cut.

Definitions 6.4.1 and 6.4.2 will help us to express our results:

Definition 6.4.1

Suppose (Π, Π′) is a circuit-derivation of a circuit (𝑇,𝑇′). Then:

1. Write actTime(𝑇) for the set of active times in 𝑇 (Definition 4.1.5(4)), and actCtrl(𝑇) for the set of active controllers in 𝑇. In symbols:

actIndex(𝑇) = {𝑖∈index(𝑇) | 𝑖active} actTime(𝑇) = {𝑇[𝑖] ∈CTime | 𝑖∈actIndex(𝑇)} actCtrl(𝑇) = {ctrl(𝑡) ∈Ctrl | 𝑡∈actTime(𝑇)}

2. We define actIndex(Π) = actIndex(𝑇) (where recall that 𝑇 is the path derived by Π), and similarly for actTime(Π), and actCtrl(Π). We also define

Active indexes actIndex(Π, Π′) = actIndex(𝑇) ∪actIndex(𝑇′)Active times actTime(Π, Π′) = actTime(𝑇) ∪actTime(𝑇′)Active controllers actCtrl(Π, Π′) = actCtrl(𝑇) ∪actCtrl(𝑇′)

3. Note that actIndex(Π, Π′), actTime(Π, Π′) and actCtrl(Π, Π′) are not the set of indexes, times, and controllers respectively that have been active at some initial prefixes of Π and Π′; they are the sets of active indexes, times, and controllers in the paths derived by the circuit-derivation (Π, Π′).

Definition 6.4.2

Suppose T ⊆ Time is a set of times.

1. Call T inconsistent when there exist 𝑡,𝑡′ ∈T with 𝑡⚡ 𝑡′. (Note that ctrl(𝑡) = ctrl(𝑡′) follows from 𝑡⚡ 𝑡′, as per Notation 2.2.4(2).)

2. Call T consistent when it is not inconsistent: i.e. if 𝑡,𝑡′ ∈T then ¬(𝑡⚡ 𝑡′). (Note that if T is consistent then 𝑡≺⊤ctrl(𝑡) for every 𝑡∈T.)

Theorem 6.4.3 provides a method to prove that a circuit-derivation (Π, Π′) is consistent, using only information from its active controllers — specifically, the actCtrl(Π, Π′)-closure of actTime(Π, Π′). Recall from Lemma 5.3.1 and Proposition 5.3.3 that an index is inactive if and only if it is cut, so putting this together with Theorem 6.4.3, it means that for the purposes of determining whether a circuit-derivation is consistent, we really can cut out, in the sense of delete, the inactive controllers from a circuit-derivation, if we wish:

Theorem 6.4.3

Suppose (Π, Π′) is a circuit-derivation and write

T = actTime(Π, Π′) and C = actCtrl(Π, Π′).

(actTime and actIndex are from Definition 6.4.1.) Then:

1. If (Π, Π′) is inconsistent in the sense of Definition 4.3.2(2), then |T |C (Definition 6.2.1) is inconsistent in the sense of Definition 6.4.2.

2. As a corollary using the contrapositive, if |T |C is consistent then (Π, Π′) is consistent.

Before we give the proof of Theorem 6.4.3, it might be helpful to give an intuition for how this proof works. There are a lot of symbols but the geometry of it is quite simple: suppose an index 𝑗 is active inconsistent, and suppose we cut it with (Cutk,j,i). Consider the Cut rule in Figure 9 and note that the time at index 𝑖 (the right-hand end of the Cut) has the form 𝑡𝑖#𝑡′ 𝑗 where 𝑡′ 𝑗=⋊𝑗(𝑡𝑗#⋉𝑗𝑡𝑘) is the time of the cut index. The reader can check that 𝑡′ 𝑗 is preserved, in the sense that 𝑡′ 𝑗 is in the C-closure of the active times after the Cut. So this Theorem works because the C-closure is (by design) precisely what is required to ‘remember’ times of all cut indexes.

Proof

Suppose (Π, Π′) is inconsistent.

Recall from Lemma 5.3.1 and Proposition 5.3.3 that an index is inactive if and only if it is Cut.

Let 𝑙 be the least inconsistent index in (Π, Π′). By Corollary 5.6.4 𝑙 is active inconsistent.

If 𝑙 is active in both Π and Π′ then Π[𝑙], Π′[𝑙] ∈|T |C by Definition 6.2.1(1) and |T |C is inconsistent and we are done.

So without loss of generality suppose 𝑙 is active in Π′ and inactive (thus cut, by Proposition 5.3.3) in Π. Unpacking Definition 4.3.2(3), let Π1 be the initial segment of Π up to the (by Proposition 5.2.3 unique) Cut at which 𝑙 is cut in Π. Write

𝑡1 = Π1[𝑙] and 𝑡′ = Π′[𝑙].

We assumed that 𝑙 is inconsistent, so some initial prefix Π′ 1 of Π′ exists such that 𝑡1 ⚡ Π′ 1[𝑙]. By Lemma 4.2.2 (times increase) and Lemma 2.1.6 (contradiction is monotone) we have that

𝑡1 ⚡ 𝑡′.

Let (𝑙= 𝑙1, . . . ,𝑙𝑛) be the chain of Cuts from 𝑙 in Π (Definition 6.3.1). By Lemma 6.3.3 we have that 𝑙1, . . . ,𝑙𝑛−1 are all active in Π′, and by Definition 6.3.1(3) we have that 𝑙𝑛 is active in Π, and by Definition 4.3.1(1) we have that ctrl(Π[𝑙𝑛]) = ctrl(Π′[𝑙𝑛]). Thus following Definition 6.4.1(2) we have that

{ctrl(Π′[𝑙1]), . . . , ctrl(Π′[𝑙𝑛])} ⊆C = actCtrl(Π, Π′). (2)

Some notation will be helpful:

• For each 𝑟∈[1...𝑛]∖{𝑛} write Π− 𝑟 for the initial prefix of Π up to and not including the instance of (Cutkr,lr,lr+1) in Π (for some 𝑘𝑟; we do not care what it is), and

• write Π+ 𝑟 for the initial prefix of Π up to and including that Cut.

• Write 𝑡𝑟= Π− 𝑟[𝑙𝑟], so this is the (by Lemma 4.2.2 ⪯-greatest) active time at index 𝑙𝑟 in Π.

• Write Π− 𝑛= Π and write 𝑡𝑛= Π[𝑙𝑛] (𝑙𝑛 is not Cut in Π).

Note that ctrl(𝑡𝑟) = ctrl(Π[𝑙𝑟]) (not ctrl(𝑡𝑟) = ctrl(Π[𝑟])).

We prove by reverse induction on 𝑟∈[1...𝑛] that 𝑡𝑟∈|T |C. In words: the time at index 𝑙𝑟 immediately before it is cut in Π, is in |T |C.

• If 𝑟= 𝑛 then by Definition 6.3.1(3) 𝑙𝑛 is active in Π so 𝑡𝑛∈T𝐷6.2.1(1)⊆ |T |C.

• For the induction step, suppose 1 ≤𝑟< 𝑛 and suppose 𝑡𝑟+1 ∈|T |C. We note by the form of the Cut rule in Figure 9 and Lemma 4.2.2 (times increase) that

Π− 𝑟[𝑙𝑟+1] = 𝑠𝑟+1#𝑡𝑟𝐿4.2.2⪯ 𝑡𝑟+1 ∈|T |C

for some ctrl(𝑡𝑟+1)-controlled time 𝑠𝑟+1 (cf. Remark 4.1.4(8b)). Given equation (2) above, ctrl(𝑡𝑟) ∈C. By Lemma 6.2.2(2) 𝑠𝑟+1#𝑡𝑟∈|T |C and by Lemma 6.2.2(3) (since ctrl(𝑡𝑟) ∈C) 𝑡𝑟∈|T |C as required.

Now we assumed that 𝑙 is active in Π′ and 𝑡′ = Π′[𝑙], so we have

𝑡′ = Π′[𝑙] ∈T = actTime(Π, Π′) and ctrl(𝑡′) ∈C = actCtrl(Π, Π′).

Thus 𝑡′ ∈|T |C by Definition 6.2.1(1). Our induction above proves that 𝑡1 ∈|T |C, and 𝑡1 ⚡ 𝑡′, so |T |C is inconsistent in the sense of Definition 6.4.2 as required. □

Corollary 6.4.6 is a helpful wrapper for Theorem 6.4.3. Notation 6.4.4 and Definition 6.4.5 will help us to state it:

Notation 6.4.4

Suppose R, T ⊆ Time and 𝑡∈ Time. Then:

1. Say that 𝑡 is upper-bounded by R, and say that R upper-bounds 𝑡, and write 𝑡⪯R, when 𝑡 precedes some element of R. In symbols:

𝑡⪯R when ∃𝑟∈R.𝑡⪯𝑟.

2. Say that T is upper-bounded by R, and say that R upper-bounds T, and write T ⪯R, when 𝑡⪯R for every 𝑡∈T.

Definition 6.4.5

Suppose T, R ⊆ Time and C ⊆ Ctrl. Call R a consistent C-attestation-closed set of upper bounds for T when:

1. R is consistent (Definition 6.4.2).

2. If 𝑡∈T then 𝑡⪯R. In words: T is upper-bounded by R. Unpacking Notation 6.4.4, there exists 𝑟∈R such that 𝑡⪯𝑟.

3. If 𝑟′#𝑞′ ⪯R and ctrl(𝑟′), ctrl(𝑞′) ∈C then 𝑞′ ⪯R. In words: if 𝑟′#𝑞′ is upper-bounded by R then so is 𝑞′.

Corollary 6.4.6

Suppose (Π, Π′) is a circuit-derivation and write

T = actTime(Π, Π′) and C = actCtrl(Π, Π′).

Then:

1. If R ⊆ Time is a consistent C-attestation-closed set of upper bounds for T, then R is also a consistent C-attestation-closed set of upper bounds for |T |C.

2. As a corollary, if

• (Π, Π′) is a circuit-derivation (Definition 4.3.1(3)), and

• a consistent actCtrl(Π, Π′)-attestation-closed set of upper bounds (Definition 6.4.5 ) can be given for actTime(Π, Π′), then

• (Π, Π′) is consistent (Definition 4.3.2(2)).

Proof

We consider each part in turn:

1. By a routine induction on |T |C, matching clauses 1 and 2 of Definition 6.2.1 with clauses 2 and 3 in Definition 6.4.5.

2. Suppose R is a consistent C-attestation-closed set of upper bounds for T. By part 1 of this result R is a consistent C-attestation-closed set of upper bounds for |T |C. It follows using Lemma 2.1.6 (contradiction is monotone) that |T |C is consistent, so by Theorem 6.4.3(2), (Π, Π′) is consistent. □

Remark 6.4.7

Corollary 6.4.6 provides an absolute (= not requiring trust assumptions) way to prove that a circuit-derivation (Π, Π′) is consistent: just provide a consistent actCtrl(Π, Π′)-attestation-closed set of upper bounds for actTime(Π, Π′)!

It only remains to show how to construct a consistent actCtrl(Π, Π′)-attestation-closed set of upper bounds for actTime(Π, Π′). We give a scheme for this now. A definition will be helpful:

Definition 6.4.8

Suppose C ⊆ Ctrl and R ⊆ Time and 𝑝∈C and 𝑠∈ Time. Say that 𝑠 is the most recent ctrl(𝒔)-time attested to by 𝑝 in R when:

∃𝑟∈R. (ctrl(𝑟)=𝑝∧𝑟#𝑠⪯R) ∧ ∀𝑟′,𝑠′∈Time.(ctrl(𝑟′)=𝑝∧ctrl(𝑠′)=ctrl(𝑠) ∧𝑟′#𝑠′⪯R) =⇒𝑠′⪯𝑠

In words, the most recent time ctrl(𝑠)-attested by 𝑝 is the most recent ctrl(𝑠)-time for which some attestation to that time, by a time controlled by 𝑝, is upper-bounded by R.26

Example 6.4.9 (Algorithm to compute a 𝐶-attestation-closed set of upper bounds). Suppose we are given (Π, Π′) and write C = actCtrl(Π, Π′) for the set of active controllers and T = actTime(Π, Π′) for their times in (Π, Π′). We proceed according to the following algorithm:

1. Message all the controllers in C — that is, message the active controllers in the circuit-derivation — and ask them for their set of most recent times

{𝑡𝑝∈Time@𝑝| 𝑝∈C}

and ask for the most recent times they have attested to for each other

{𝑡𝑝𝑝′ ∈Time@𝑝′ | 𝑝, 𝑝′ ∈C}

(so 𝑡𝑝𝑝′ is the 𝑝′-controlled time that controller 𝑝 reports as being the most recent time it has attested to for 𝑝′).27 If any of the 𝑡𝑝 and 𝑡𝑝𝑝′ are inconsistent (i.e. equal to ⊤𝑝 or ⊤𝑝′ respectively) then fail. Otherwise, proceed. Note that these times may arrive as succinct digests in the cryptographic sense (e.g. some kind of hash), not as the original data structure. So in fact what we might actually have is sig(𝑡𝑝) and sig(𝑡′ 𝑝𝑝′), where sig is short for ‘signature’. This will not be a problem, as we shall see.

2. For each controller 𝑝′ ∈C, request the following proofs:28

(a) Proofs of 𝑡⪯𝑡𝑝′ for every 𝑡∈T such that ctrl(𝑡) = 𝑝′. Thus, the controller 𝑝′ must prove that the most recent time that it reported, is later than all of the active times in (Π, Π′) that are controlled by 𝑝′.

(b) Proofs of 𝑡′ 𝑝𝑝′ ⪯𝑡𝑝′ for every 𝑝∈C. Thus, the controller 𝑝′ must prove that the most recent time that it reported, is later than all of the times that the other controllers report having attested to for 𝑝′.

We cannot prove this ourselves because we might only have sig(𝑡′ 𝑝𝑝′) and sig(𝑡𝑝′), but we can send those signatures to 𝑝′ and expect it to look them up, recognise the corresponding full times, and provide cryptographically verifiable digests of the corresponding proofs. If any of the controllers fails to provide all of the requested proofs, then fail. Otherwise, proceed.

3. Succeed and output

R = {𝑡𝑝| 𝑝∈C}.

We claim that if the algorithm above succeeds, then the R that it computes is a consistent C-closed set of upper bounds for T, in the sense of Definition 6.4.5. We must prove that

• R is consistent in the sense of Definition 6.4.2, and

• it upper-bounds T in the sense of Notation 6.4.4, and

• it is a C-attestation closed set of upper bounds in the sense of Definition 6.4.5.

R is consistent by construction because if 𝑡𝑝= ⊤𝑝 above then the algorithm fails and returns no output.

R upper-bounds T by construction because the algorithm requires proofs of 𝑡⪯𝑡ctrl(𝑡) for every 𝑡∈T = actTime(Π, Π′).

We now argue that R is a C-attestation closed set of upper bounds. Suppose 𝑟′#𝑞′ ⪯R where ctrl(𝑟′), ctrl(𝑞′) ∈C; write 𝑝= ctrl(𝑟′) and 𝑝′ = ctrl(𝑞′). Suppose 𝑡𝑝𝑝′ is the most recent time attested to for 𝑝′ by 𝑝.

By the second conjunct in the definition of ‘most recent’ in Definition 6.4.8, we have that 𝑞′ ⪯𝑡𝑝𝑝′. But we also have 𝑡𝑝𝑝′ ⪯𝑡𝑝′ ∈R, so we are done.

Remark 6.4.10

This almost completes our argument, but there remains one outstanding detail: we write above that 𝑡𝑝𝑝′ should be the most recent time that controller 𝑝 has attested to for controller 𝑝′, and we assume the ‘most recent’ property when we appeal to Definition 6.4.8 above.

How can we be sure that 𝑡𝑝𝑝′ really is the most recent time that 𝑝 attests to for 𝑝′? We know that 𝑡𝑝𝑝′ ⪯𝑡𝑝′, but there is no proof of the ‘most recent’ property.

This is not obvious in general, but for the ‘practical’ located semilattice in Definition 3.4.3 this can be proved: just check that (for proj2 being second projection of a tuple)

𝑡𝑝= (𝑝, proj2(𝑡𝑝), (𝑡𝑝𝑝′ | 𝑝′ ∈[1...𝑛]∖{𝑝})).

In words: just check that the time reported by 𝑝 is equal to some local state plus the times that 𝑝 reports having attested to for the other controllers’ times. This might seem tautological — why not just go into 𝑡𝑝 directly? — but remember that these times might be delivered as a compact cryptographic digest, such that we can check that the digests compose correctly without necessarily knowing directly what is inside them.

7. Alternative presentation of located semilattices with

Cut

Remark 7.1

We will now reformulate the notions of located semilattice and located semilattice with Cut from Definitions 2.2.2 and 3.2.1. We do not use these reformulated versions in the main proofs, but it is still interesting to revisit the definitions.

There are two nice things about this reformulation (which is why we present it here), and one less nice thing (which is why we did not take this as a primitive definition).

1. The reformulation is compact, and arguably elegant. This is nice.

2. The reformulation unifies the ‘located semilattice’ structure with the ‘with flags’ structure. These are now both manifestations of a single abstraction, which we call an attestation Y ⇒ X. This is also nice.

3. The presentation in Definitions 2.2.2 and 3.2.1 is more verbose, concrete and accessible.

It may be best to think of this Section as being retrospective: in retrospect we gain an interesting view of what we have been doing.29

Definition 7.2 (Attestation Y ⇒ X).

Suppose (X, ∨X, ⊥X, ⊤X) and (Y, ∨Y, ⊥Y, ⊤Y) are bounded semilattices and suppose 𝑥,𝑥′ ∈ X.

1. Say that 𝑥 contradicts 𝑥′ and write 𝑥⚡ 𝑥′ when 𝑥∨X 𝑥′ = ⊤X.

2. The set Y → X of all functions from Y to X inherits a natural pointwise bounded semilattice structure from X, as follows:

(a) 𝐹≤Y→X 𝐹′ ∈ Y → X when ∀𝑦∈ Y.𝐹(𝑦) ≤X 𝐹′(𝑦).

(b) ⊥Y→X = 𝜆𝑦.⊥X.

(c) ⊤Y→X = 𝜆𝑦.⊤X.

(d) 𝐹∨Y→X 𝐹′ = 𝜆𝑦.(𝐹(𝑦) ∨X 𝐹′(𝑦)).

3. Call a function 𝐹 : Y →(X → X) strongly contradiction-preserving when30

∀𝑦,𝑦′ ∈Y.𝑦⚡ 𝑦′ =⇒∀𝑥,𝑥′ ∈X.𝐹(𝑦)(𝑥) ⚡ 𝐹(𝑦′)(𝑥′).

4. Call 𝑓 : X → X expansive when

∀𝑥∈X.(𝑥≤X 𝑓(𝑥)).

Write Expan(X) for the set of expansive functions from X to itself

Expan(X) = {𝑓: X →X | 𝑥≤X 𝑓(𝑥)},

considered as a bounded semilattice with the pointwise ordering from part 2 as follows:

⊥Expan(X) = 𝜆𝑥: X.𝑥 ⊤Expan(X) = 𝜆𝑥: X.⊤X𝑓∨Expan(X) 𝑔= 𝜆𝑥: X.𝑓(𝑥) ∨X 𝑔(𝑥) 𝑓≤Expan(X) 𝑔⇐⇒∀𝑥: X.𝑓(𝑥) ≤X 𝑔(𝑥)

5. An attestation from Y to X is a not necessarily monotone, strongly contradiction-preserving map from Y to Expan(X). Write Y ⇒ X for the set of attestations from Y to X.

6. Call 𝑓 : X ⇒ X a self-attestation. So a self-attestation is a strongly contradiction-preserving map from X to expansive functions from X to itself.

7. We may sometimes write # : Y ⇒ X (rather than 𝑓 : Y ⇒ X) for a function that is an attestation, and we may write application of attestation postfix as 𝑥#𝑦. So 𝑥#𝑦 is shorthand for #(𝑦)(𝑥).

Remark 7.3

Note that attestation is not necessarily monotone in either component: 𝑥≤𝑥′ does not imply 𝑥#𝑦≤𝑥′#𝑦 in general, and 𝑦≤𝑦′ does not imply 𝑥#𝑦≤𝑥#𝑦′ in general. This will be of some interest as an additional property; see Definition 7.5(2).

Example 7.4 (Examples of attestations).

Suppose (X, ∨X, ⊥X, ⊤X) and (Y, ∨Y, ⊥Y, ⊤Y) are bounded semilattices and suppose 𝑥,𝑥′ ∈ X (we may drop the X and Y subscripts).

1. The function

𝜆𝑥′ : X.𝜆𝑥: X. 𝑥 𝑥′ ≤𝑥𝑥′𝑥≤𝑥′⊤ ¬(𝑥′ ≤𝑥∨𝑥≤𝑥′): X →(X →X)

is an attestation in X ⇒ X. We may call this the linear attestation. This example easily instantiates to many concrete examples, just by concretely instantiating X to any datatype that admits some kind of sensible ordering

— possibly after adjoining a top and/or bottom element to make it into a bounded semilattice if it is not one already. Examples include:

(a) Finite lists or finite trees with a top element, ordered by is-initial-prefix-of.

(b) Possibly inconsistent propositional theories ordered by subset inclusion.

(c) The real line with endpoints.

(d) ...and so on.

2. Let 𝑓 : Y → X be any bounded semilattice morphism. Then

𝜆𝑦: Y.(𝜆𝑥: X.(𝑥∨𝑓(𝑦))) : Y →Expan(X)

is an attestation in Y ⇒ X. We may call this a principal attestation.

3. Semilattice join ∨X: X →(X → X) is an attestation function

𝜆𝑥′ : X.𝜆𝑥: X.(𝑥∨X 𝑥′) : X →Expan(X)

in X ⇒ X. We may call this the join attestation and we may write it #∨X. The join attestation is just a special case of a principal attestation where we take Y = X and 𝑓= id : X → X (identity function).

4. Let 𝑓 : Y → X be a bounded semilattice morphism. Then

𝜆𝑦: Y.𝜆𝑥: X.{𝑓(𝑦) 𝑥= ⊥X⊤X𝑥> ⊥X

is an attestation in Y ⇒ X.

5. Let X ⊆ pow(Pnt) be any join-semilattice in the powerset of a set Pnt such that ∅, Pnt ∈ X — another word for this is that X is a semitopology [Gab24, Gab25]. Let R ⊆ X × X be any relation. Then

#R = 𝜆𝑂′ ∈X.𝜆𝑂∈X.{ 𝑂∪𝑂′(𝑂,𝑂′) ∈RPnt (𝑂,𝑂′) ∉R

is an attestation. In some sense which we will not make formal here, this seems to be the only parametric scheme for attestations on X. We give the intuition. Given parametricity (so we cannot use any particular structure of 𝑂 and 𝑂′ aside from knowing that they are sets), expansiveness forces 𝑂⊆𝑂#R𝑂′ and contradiction-preservation forces 𝑂′ ⊆𝑂#R𝑂′, so 𝑂∪𝑂′ ⊆𝑂#R𝑂′; and if we are parametric in the sense that we are not allowed to examine at any specific structure of X or Pnt, the only remaining choice is whether to return 𝑂∪𝑂′ or all of Pnt, and this choice is made by R.

6. We give an example of a non-attestation. Note that Expan(X) (the set of expansive functions from X to itself) has a bounded semilattice structure defined pointwise as per Definition 7.2(2). Then the identity function

𝜆𝑓: Expan(X).𝜆𝑥: X.𝑓(𝑥) : Expan(X) →Expan(X)

is not an attestation in Expan(X) ⇒ X, because it is not strongly contradiction-preserving. Suppose 𝑓⚡ 𝑓′. Then the reader can check that it does not in general follow that 𝑓(𝑥) = 𝑥#𝑓⚡ 𝑥′#𝑓′ = 𝑓′(𝑥′).

Definition 7.5

Suppose (X, ∨X, ⊥X, ⊤X) and (Y, ∨Y, ⊥Y, ⊤Y) are bounded semilattices and suppose # : Y ⇒ X is an attestation.

1. Call # separating when for every 𝑦,𝑦′ ∈ Y∖{⊥Y}

∀𝑥,𝑥′ ∈X. 𝑥#𝑦= 𝑥′#𝑦′ =⇒𝑥#𝑦≠⊤X =⇒𝑦= 𝑦′equivalently (∃𝑥,𝑥′ ∈X.𝑥#𝑦= 𝑥′#𝑦′ ∧𝑥#𝑦≠⊤X) =⇒𝑦= 𝑦′.

In words: if 𝑥#𝑦 and 𝑥′#𝑦′ are equal and consistent (non-⊤) then 𝑦= 𝑦′. Note that being separating is not just the condition of being injective.

2. Call # monotone when

∀𝑦,𝑦′ ∈Y.𝑦≤𝑦′ =⇒∀𝑥∈X.𝑥#𝑦≤𝑥#𝑦′.

In words: # : Y → Expan(X) is monotone from Y to Expan(𝑋) with the pointwise ordering.

We are now ready to propose our alternative versions of the notions of located semilattice from Definition 2.2.2, and located semilattice with Cut from Definition 3.2.1:

Definition 7.6

A located semilattice (contrast with Definition 2.2.2) consists of a tuple

L = (Ctrl, (Time@𝑝| 𝑝∈Ctrl), # : ∏𝑞,𝑝∈Ctrl(Time@𝑞⇒Time@𝑝))

where

1. Ctrl is a set of controllers,

2. (Time@𝑝| 𝑝∈ Ctrl) is a Ctrl-indexed set of pairwise disjoint bounded semilattices. For 𝑝∈ Ctrl we may call Time@𝑝 a 𝒑-component (or just a component, if 𝑝 is unimportant or understood), and we may call 𝑡∈ Time@𝑝 a time. When 𝑡∈ Time@𝑝 we say that 𝑡 is controlled by 𝑝, and we may write ctrl(𝑡) = 𝑝.

3. # : ∏𝑞,𝑝∈Ctrl(Time@𝑞⇒ Time@𝑝) is a (𝑞, 𝑝) ∈ Ctrl2-indexed family of attestations from Time@𝑞 to Time@𝑝.

4. We further restrict # so that #𝑞,𝑞= #∨Time@𝑞. Here #∨Time@𝑞 is the join self-attestation from Example 7.4(3). In words: the self-attestations in the indexed family are just the join attestation from Example 7.4(3).

5. If every component Time@𝑝 is a sequential bounded semilattice — i.e. a top-tree — then call L sequential.

Definition 7.7

1. Define CuttingPoset the cutting-flag bounded semilattice to be the top-tree (= sequential bounded semilattice) generated as the reflexive transitive closure of Figure 6, with top and bottom elements ⊤CuttingPoset and ⊥CuttingPoset adjoined.

2. A located semilattice with Cut (contrast with Definition 3.2.1) is a located semilattice such that:

(a) For each 𝑝∈ Ctrl, the 𝑝-component Time@𝑝 is equipped with a separating monotone attestation #𝑝 : CuttingPoset ⇒ Time@𝑝.

(b) If 𝑡∈ Time@𝑝 then 𝑡#𝑝⊥CuttingPoset = 𝑡 and 𝑡#𝑝⊤CuttingPoset = ⊤𝑝.

(c) Define a function # : CuttingPoset → Time → Time by

𝑡#Q = 𝑡#ctrl(𝑡)Q.

We insist # is injective on CuttingPoset∖{⊤CuttingPoset, ⊥CuttingPoset}, in the strong sense that

∀𝑡,𝑡′ ∈Time@𝑝.𝑡#Q = 𝑡′#Q′ ∈CTime =⇒Q = Q′.

(Recall that CTime is from Notation 2.2.4(1) and this just means that 𝑡#Q and 𝑡′#Q′ are consistent, i.e. not equal to ⊤𝑝.)

Remark 7.8

Definitions 7.6 and 7.7 are appealing, but they come with a price:

1. Definitions 7.6 and 7.7 are compact and identify the recurring abstraction of an attestation (Definition 7.2(5)). This is an interesting mathematical object which is worth pointing out.

2. This way of setting up the definitions highlights some structure that was always clearly present, but had perhaps been somewhat buried under notation. For example: by ordering flags explicitly into a poset CuttingPoset in Definition 7.7 following Figure 6, we turn that Figure from something illustrative into something definitive, so that properties 1 to 4 in Definition 3.2.1 become geometric observations about CuttingPoset as a top-tree. In particular, attestation is strongly contradiction-preserving as per Definition 7.2(3), so the geometric fact that ⋊𝑗 and ⋉𝑗 are on distinct branches in CuttingPoset as a top-tree gives us the important and characteristic cross-controller contradiction axiom ⋊𝑗𝑡⚡⋉𝑗𝑡′ (Definition 3.2.1(4)). This is very nice.

3. However, the original notion of located semilattice in Definition 2.2.2 has its own appeal.

(a) It is arguably more accessible to a first-time reader.

(b) In Definition 2.2.2 the join structure is derived from the attestation #, so there is just a singular notion of ‘attestation’. In Definition 7.6 the join structure of each Time@𝑝 is primitive, then a family of cross-controller attestations #𝑝,𝑞 is introduced ...which we then have to assemble into a single function # in order to express the injectivity condition in Definition 7.7(2c).

There is no right or wrong here. There is a design space of definitions here, whose shape remains to be explored.

8. Conclusions

8.1. Many controllers is not a problem, if they can collaborate

In 1983 Chaum noticed a problem that in a system of communicating state machines (‘controllers’), one of those machines might send messages that are both consistent with its history up to that point, but that are inconsistent with each other [Cha83]. This is the consistent histories problem, of which the classic instance is spending the same unit of money more than once: the ‘double-spend’. We discuss existing solutions to this in Subsection 1.4.

We have seen how located semilattices model multiple independent but collaborating controllers, and located semilattices with Cut provide a solution to the consistent histories problem. In located semilattices with Cut, tags recording a resource history can be pruned, and — provided that this pruning follows the rules of Cut which we propose and analyse — the existence of inconsistency is preserved even after forgetting. That is, in a sense made formal by Theorems 5.6.2 and 6.4.3 (as discussed in Subsection 1.6), we can safely forget history.

This is a technical and mathematical answer to the core practical problem of fragmentation [Shi26].31 In fact, fragmentation is only a problem if controllers struggle to collaborate, and forgetting history is only a problem if it creates a danger that histories that were visibly unsafe, become (after forgetting/reduction) not visibly unsafe. If histories are safely reducible and controllers can collaborate efficiently and within well-understood and properly-controlled safety parameters, then this ceases to be a problem and becomes an innocuous technical fact, or even a performance feature.32

At this point it might be useful to return to the BIS working report, which approaches this issue from the point of view of collaborating central banks rather than collaborating blockchains.

Remark 8.1.1

The BIS working report [Shi26] notes the impossibility of the One True Controller, but it goes beyond this to critique blockchains as currently constituted. The paper is academic in tone and content, but its critique is valid and cuts deep. It is worth reading the final paragraphs of the Conclusion:

The analysis of this paper [meaning [Shi26] -authors’ note] underlines the importance of going back to the basics of money as a coordination mechanism. The classical insight – from Menger to Jevons to Kiyotaki and Wright – is that money is valuable because of the breadth of its acceptance network. The modern insight, developed here, is that decentralised consensus mechanisms systematically undermine this breadth by fragmenting the user base across competing platforms. The feedback loop runs in the wrong direction: instead of greater acceptance leading to greater use (the virtuous circle of money), congestion on one chain leads to exit to another chain. This is not to deny the genuine innovations of blockchain technology [but] A purely decentralised monetary system, without the anchor of a trusted central authority, is structurally predisposed to fragmentation. The question for policymakers is whether the genuine innovations of blockchain technology can be harnessed while preserving the institutional foundations that make a unified monetary system possible.

In short, the BIS report proposes a model of a small number of completely trusted controllers (e.g. national banks). The problem of fragmentation is ‘solved’ by assuming that these banks never misbehave. This is not quite the One True Controller, but it is the One Small Clique of True Controllers, which really amounts to the same thing. Their critique of blockchains is that blockchains cannot make this trust assumption, so fragmentation becomes dangerous.

To this passage we would note that located semilattices with Cut from this paper – while also academic – can be viewed precisely as a technical answer to the challenge posed by fragmentation.

We would argue that the issue is not really whether there is a One True Controller (‘the anchor of a trusted central authority’ as the BIS report puts it) nor multiple controllers (a ‘fragmented user base’). Fragmentation is not inherently bad, but it may be perceived as bad if it means that controllers cannot collaborate.

Located semilattices with Cut are a mathematical, yet real and implementable, schema to help address this. With the mathematics of this paper, we would not need to insist that the world agree on a single controller. Instead, we can organise our system so that resource histories are composable and reducible. We would argue that this looks past the symptoms and directly addresses the root problem and cause.

8.2. Design alternatives: other Cut rules

Our Cut rule from Figure 9 is carefully designed to be local and asynchronous (as per Section 1.6 and Remark 4.1.4) while making Theorems 5.6.2 and 6.4.3 hold. The rule certainly exists in a design space, and it is almost certainly not the only possible working design. We briefly consider the design space, including one possibility that probably works (left-handed cut) and some possibilities that probably do not (rightmost attestation and transitive attestation).

8.2.1. Cut is chiral: right vs left

Our flag system requires that if multiple adjacent active controllers are flagged ⋊, then the leftmost must be cut first: a controller to its left must be flagged ⋉, and then the leftmost⋊ time can be cut, followed by the next leftmost, and so on. Call this Cut a left-handed Cut.

This forced ordering helps to enforce consistency: different paths in a circuit cutting in different orders (disallowed by our flags) can produce circuits with an inconsistent derivation but no active inconsistent controller.33

However, we just need adjacent ⋊ times to be cut in the same order. It is likely possible to design an alternative right-handed Cut that enforces that in multiple adjacent ⋊-flagged controllers, the rightmost adjacent ⋊ time must be cut.

With left-handed Cut, we ended up reasoning about right-compatible cuts (see Definition 4.3.6). With right-handed Cut, proofs would probably reason about left-compatible cuts instead. The resulting system would have many of the same desirable properties.

We have seen no compelling reason to prefer one over the other.

8.2.2. Rightmost Attestation

Our paths represent (compressed) histories of objects, with the rightmost path element representing the controller where the object started: it is always active.

We could require that before cutting time 𝑡, the rightmost time must have attested to 𝑡. In practice, this corresponds to requiring the ‘issuer’ of the object to sign off on (and check consistency of) any cuts. This preserves the consistency property nicely: if our circuit has an inconsistent derivation, then it has two inconsistent (possibly inactive) controller times in it, and if they’re both inactive, that means the rightmost controller attested to both, and so is active inconsistent.

Unfortunately, this sacrifices the locality of cuts, which was one of our goals. By ‘locality’ we mean that we want a group of controllers to be able to receive an object, transfer it among themselves, and then be able to cut as much as possible — without having to communicate outside the group.

For example, a farmer might issue crop futures, which are then owned and traded by any number of markets and people. The farmer does not want to be bothered whenever traders want to do a cut. They only need to review the crop future when it is time to collect the crops.

8.2.3. Transitive Attestation

We return to a discussion in Remark 2.2.1. Attestation is not transitive:

𝑡#𝑢⪯̸ 𝑡#(𝑠#𝑢)

in general. Suppose it were. Then we would have this lovely property (where 𝑢 and 𝑢′ are at the same controller):

𝑢⚡ 𝑢′ =⇒𝑡#(𝑠#𝑢) ⚡ 𝑡#(𝑣#𝑢′).

In an implementation, it would suffice to insist that before a controller can attest to time 𝑡, it must attest to all times attested to in (times preceding) 𝑡.

This gives some very nice properties. It becomes easy to design cut rules that preserve consistency properties: so long as someone active must attest to a time before it is cut, then the cut time is forever ‘remembered’ by someone active.

Unfortunately, transitive attestations have a drawback: attestation is technically more expensive (because we cannot just ‘attest to stuff’; we have to find out the transitive closure of that stuff), and worse, attestation becomes much more of a commitment, which is problematic.

Suppose some controller forks into times 𝑡 and 𝑡′ where 𝑡⚡ 𝑡′. Now, any controller 𝑎 who attests to 𝑡 cannot later attest to a controller 𝑏 who attested to 𝑡′. Furthermore, with transitive attestations, any controller who attests to 𝑎’s time cannot later attest to a controller who attested to 𝑏’s time (because the former transitively depends on 𝑡 and the latter transitively depends on 𝑡′). So because one controller forked, the system can end up partitioned into subsets of (correct) controllers who can no longer attest to each other.

We want an attestation system that encourages communication: controllers should feel confident in attesting to each other opportunistically, without fear that this might limit their options later. Transitive attestations ruin that: every attestation means potentially cutting off communication with other controllers.

The lack of structure of the not-necessarily-transitive attestations used in this paper is a feature, not a bug: it permits and encourages consequence-free opportunistic attestation.

8.3. Consistent history

Consistent history is one of the most basic properties digital objects can have. Given two digital objects, we may want to know if they contradict in the deep sense that in order to have both, some controller must misbehave. The maths in this paper is parametric over what ‘misbehaviour’ means precisely, but we have in mind in particular the canonical example of an illegal double-spend.34

We have shown that in order to check for consistent history, it is not necessary to know (or store) all the times of all the controllers involved in the production of a pair of resources. It can suffice merely to know the active times from a path corresponding to each object. Naively, this path corresponds to an upper bound on the most recent time each controller affected the object’s history, but we have shown how, with a little work, we can cut controllers from this path.

For a given set of objects, a user who trusts all the controllers of all the active times from the object’s paths knows (from Subsection 5.6) that the objects’ history is consistent. If there is some contradictory fork, then it is impossible that all dishonest controllers are inactive in all the paths. This is the key connection between paths and trust assumptions. With Theorem 6.4.3, it is even possible to prove that the objects have consistent history (without trust assumptions), although assembling this proof may require requesting new “⪯” proofs from the active controllers.

Our mathematics is parametric over the precise bookkeeping systems used to track and update objects’ paths, perform attestations, and prove serialisability. This is certainly implementable and picking optimal choices for given use cases is future work. However, we note that the mathematical framework presented here is applicable to extremely general classes of interacting systems — they just have to be located semilattices. We have also shown that tracking — and crucially, cutting — trust assumptions across heterogeneous trust domains is possible, even in an open system with few constraints on how objects behave. We are not aware of other frameworks with this level of generality and power.

Today’s interacting systems typically do not track trust assumptions, and do not use attestations and cuts to remove trust assumptions that are no longer necessary. Instead, they rely on blind trust (e.g. US banks must trust assets given to them by the Federal Reserve); or on precisely matched trust assumptions (e.g. applications on Ethereum can rely precisely on Ethereum’s trust assumptions, and so interacting with each other does not change trust assumptions). But blind trust is not scalable, is not possible for all applications, and can be expensive and slow, since the trusted controller must be extremely trustworthy, and will have a lot of demand. Existing trust assumption trackers generally cannot remove the requirement to trust a controller that has affected an object’s history (e.g. taint tracking [WGDW22] or IFC [LAGM17]), unless the application can somehow check all the integrity properties it needs from available data (e.g. balance checks in wrapped tokens [Goe24]).

Our mathematics opens the door for something better: cross-controller applications with the ability to cut trust assumptions. Applications can run on whatever controllers suit them best according to their tradeoffs for cost, speed, and trustworthiness. With accurate trust tracking, attestations, and Cut, applications are much more free to interact, safely and effectively.

8.4. Future work

Much remains to be done, especially to take the mathematical foundation of this paper and engineer it to a practical and useful implementation.

We hypothesise that objects can carry tags which track active controllers in a path corresponding to their history. The design of these tags, and proof that they correspond to such paths, is future work. These tags would resemble taint tracking [WGDW22] or IFC Integrity labels [LAGM17], but controller tags are not quite either. Comparison (and possible combination with) taint tracking or IFC techniques is future work.

Remark 8.4.1 (Concrete use-cases: e.g. the exponential bike).

Our paths model the history of a single (possibly stateful) object: a linear path from controller to controller. Thus the exponential cake from Figure 1 may move between controllers, and may change state (i.e. get eaten).

But in practice, digital objects may also be combined, so that the integrity of a single object may depend on multiple source objects. Consider for example the exponential bike in Figure 14. This depends on two wheels (and a frame, whose source is not illustrated). The exponential bike is ‘inconsistent’ all by itself, because its two wheels were generated by double-spending one wheel.35 We believe that the mathematics in this paper can be extended to address the exponential bike. Just follow the paths of the two wheels, in the sense of Definition 4.1.1, and detect the contradiction. Our theory of controller tags should be compatible with this natural example.

More generally, it remains future work to explore how the mathematics in this paper will interact with the design space of all possible transformations of digital tokens, and possible use-cases for these ideas. As we consider these, it may emerge that a single framework can encompass many or all use-cases of interest, or perhaps different extensions will be in some sense intrinsically different, e.g. requiring intrinsically different notions of Cut.36

Remark 8.4.2 (Attestation + IVC).

It may be that attestation can be implemented with Incrementally Verifiable Computation [KST22] similar to roll-up blockchains [TSH22], but we have not implemented or formally modelled any specific real system. Studying a possible correspondence with available verifiable computation techniques, and possibly exploiting it for implementation, is future work.

A B C D01 23 45 6 78Above, 𝐴sends one wheel to 𝐵and some time later receives a bicycle with two copies of that wheel. This is an inherently contradictory resource, whose construction depends on a double-spend by 𝐵.
Figure 14. Future work: the exponential bike (Remark 8.4.1)

The problem that this paper addresses is real. The mathematical ideas which we propose in this paper stand as pure mathematics in their own right, and correctness of the results has been checked in a Lean formalisation [Har26]. It is reasonable to speculate that, with some further investment in research and software engineering, these ideas could become a foundation for practically useful systems.

References

Adr26. Tobias Adrian, Tokenized finance, IMF Notes 2026/001, International Monetary Fund, 2026. doi:10.5089/9798229042468.068 (cit. on p. 6.)

AHLT05. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup, Maintaining information in fully dynamic trees with top trees, ACM Transactions on Algorithms (TALG) 1 (2005), no. 2, 243–264. doi:10.1145/1103963.1103966 (cit. on p. 15.)

Ban23. Bank for International Settlements, Blueprint for the future monetary system: Improving the old, enabling the new, Annual economic report 2023, chapter iii, Bank for International Settlements, Basel, June 2023. https://www.bis.org/publ/arpdf/ar2023e3.htm (cit. on pp. 3 and 6.)

Ban25. , The next-generation monetary and financial system, Annual economic report 2025, chapter iii, Bank for International Settlements, Basel, June 2025. https://www.bis.org/publ/arpdf/ar2025e3.htm (cit. on p. 3.)

BB23. BIS Innovation Hub and Bank of England, Project meridian: Innovating transactions with synchronisation, Tech. report, Bank for International Settlements, Basel, April 2023. https://www.bis.org/about/bisih/topics/fmis/meridian.htm

(cit. on p. 3.)

BBE25. BIS Innovation Hub, Bank of England, and European Central Bank, Project meridian FX: Exploring synchronised settlement in FX, Tech. report, Bank for International Settlements, Basel, April 2025. https://www.bis.org/publ/othp94.htm (cit. on p. 3.)

BE18. Bank of Japan and European Central Bank, Securities settlement systems: Delivery-versus-payment in a distributed ledger environment, Project stella report, Bank of Japan and European Central Bank, 2018. https://www.ecb.europa.eu/pub/pdf/other/stella_project_report_march_2018.pdf (cit. on p. 6.)

BG81. Philip A. Bernstein and Nathan Goodman, Concurrency control in distributed database systems, ACM Computing Surveys 13 (1981), no. 2, 185–221. doi:10.1145/356842.356846 (cit. on p. 6.)

BHG87. Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley, Reading, Massachusetts, 1987. https://www.microsoft.com/en-us/research/people/philbe/book/ (cit. on p. 3.)

BVGC21. Rafael Belchior, André Vasconcelos, Sérgio Guerreiro, and Miguel Correia, A survey on blockchain interoperability: Past, present, and future trends, ACM Computing Surveys 54 (2021), no. 8, 1–41. doi:10.1145/3471140 (cit. on p. 6.)

Cdv+90. David Chaum, Bert den Boer, Eugène van Heyst, Stig Fr. Mjølsnes, and Adri Steenbeek, Efficient Offline Electronic Checks (extended abstract), Advances in Cryptology – EUROCRYPT ’89: Workshop on the Theory and Application of Cryptographic Techniques, Houthalen, Belgium, April 10– 13 (Berlin, Heidelberg) (Jean-Jacques Quisquater and Joos Vandewalle, eds.), Lecture Notes in Computer Science, vol. 434, Springer, 1990, pp. 294–301. doi:10.1007/3-540-46885-4_31 (cit. on p. 6.)

Cha83. David Chaum, Blind signatures for untraceable payments, Advances in Cryptology: Proceedings of Crypto 82 (Boston, MA) (David Chaum, Ronald L. Rivest, and Alan T. Sherman, eds.), Springer, 1983, pp. 199–203. doi:10.1007/978-1-4757-0602-4_18 (cit. on pp. 6 and 78.)

Cha92. , Achieving electronic privacy, Scientific American 267 (1992), no. 2, 96–101. doi:10.1038/scientificamerican0892-96 (cit. on p. 6.)

CM03. Nathalie Caspard and Bernard Monjardet, The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Applied Mathematics 127 (2003), no. 2–3, 241–269. doi:10.1016/S0166-218X(02)00209-3 (cit. on p. 25.)

Com92. Committee on Payment and Settlement Systems, Delivery versus payment in securities settlement systems, CPSS Publications 6, Bank for International Settlements, Basel, September 1992. https://www.bis.org/cpmi/publ/d06.htm (cit. on p. 3.)

Com17. Committee on Payments and Market Infrastructures, Distributed ledger technology in payment, clearing and settlement: An analytical framework, CPMI report 157, Bank for International Settlements, 2017. https://www.bis.org/cpmi/publ/d157.htm (cit. on p. 6.)

DP02. Brian A. Davey and Hilary A. Priestley, Introduction to lattices and order, 2nd ed., Cambridge University Press, Cambridge, 2002. doi:10.1017/CBO9780511809088 (cit. on p. 25.)

Gab24. Murdoch J. Gabbay, Semitopology: decentralised collaborative action via topology, algebra, and logic, College Publications, August 2024, ISBN: 9781848904651. (cit. on p. 75.)

Gab25. , Semitopology: a topological approach to decentralised collaborative action, The Journal of Logic and Computation (2025), https://doi.org/10.1093/logcom/exae050. doi:10.1093/logcom/exae050 (cit. on p. 75.)

Gir87. Jean-Yves Girard, Linear logic, Theoretical Computer Science 50 (1987), no. 1, 1–101. doi:10.1016/0304-3975(87)90045-4 (cit. on pp. 4 and 7.)

GL06. Jim Gray and Leslie Lamport, Consensus on transaction commit, ACM Transactions on Database Systems 31 (2006), no. 1, 133–160. doi:10.1145/1132863.1132867 (cit. on p. 6.)

Goe20. Christopher Goes, The Interblockchain Communication Protocol: An Overview, May 2020, https://github.com/cosmos/ibc/blob/8d9d3b6fe7309b034df8457760b3bbd11d24b8e1/archive/papers/2020-05/build/paper.pdf#L2. (cit. on p. 3.)

Goe24. , Draft Spec for Multi-Denom Packets ICS20 v2, March 2024, https://github.com/cosmos/ibc/blob/main/spec/app/ics-020-fungible-token-transfer/README.md. (cit. on pp. 3, 10, and 82.)

Har26. Anthony Hart, Consistent Histories in Lean 4, July 2026, Direct download of zip archive: https://zenodo.org/api/records/21074395/files-archive. doi:10.5281/zenodo.21074395 (cit. on pp. 3 and 84.)

Her18. Maurice Herlihy, Atomic cross-chain swaps, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (New York, NY, USA), PODC ’18, Association for Computing Machinery, 2018, p. 245–254. doi:10.1145/3212734.3212736 (cit. on pp. 3 and 6.)

HLS22. Maurice Herlihy, Barbara Liskov, and Liuba Shrira, Cross-chain deals and adversarial commerce, The VLDB Journal 31 (2022), no. 6, 1291–1309. doi:10.1007/s00778-021-00686-1 (cit. on p. 6.)

HW90. Maurice P. Herlihy and Jeannette M. Wing, Linearizability: A correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems 12 (1990), no. 3, 463–492. doi:10.1145/78969.78972 (cit. on p. 6.)

Kap04. Michael Kaplan, Three blind phreaks, Wired 12 (2004), no. 02, Archived copy available at https://www.social-engineer.org/wiki/archives/Hackers/hackers-The-Badir-Brothers-Social-Engineer.htm. (cit. on p. 78.)

KLRZ25. Tansaya Kunaratskul, Ashley Lannquist, Andre Reslow, and Nicolas Zhang, Central bank exploration of tokenized reserves, Fintech Notes 2025/011, International Monetary Fund, 2025. doi:10.5089/9798229025324.063 (cit. on p. 6.)

KST22. Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla, Nova: Recursive zero-knowledge arguments from folding schemes, Advances in Cryptology – CRYPTO 2022, Lecture Notes in Computer Science, vol. 13510, Springer, 2022, Cryptology ePrint Archive, Paper 2021/370, pp. 359–388. doi:10.1007/978-3-031-15985-5_13 (cit. on p. 83.)

LAGM17. Jed Liu, Owen Arden, Michael D. George, and Andrew C. Myers, Fabric: Building open distributed systems securely by construction, J. Comput. Secur. 25 (2017),

no. 4–5, 367–426. doi:10.3233/JCS-15805 (cit. on pp. 82 and 83.)

Nak08. Satoshi Nakamoto, Bitcoin: A peer-to-peer electronic cash system, https://bitcoin.org/bitcoin.pdf, 2008. (cit. on p. 6.)

Nan26. Toby Nangle, Stablecoin = fracturedcoin, Alphaville, Financial Times, 10 March 2026, Available at https://www.ft.com/content/4724ae3f-04a7-4ca3-8221-2244c7644faa. (cit. on p. 7.)

Pap79. Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM 26 (1979), no. 4, 631–653. doi:10.1145/322154.322158 (cit. on pp. 6 and 81.)

Ros71. Ron Rosenbaum, Secrets of the little blue box, Esquire (1971), 116ff, Reprinted in Slate, 2011. Scan available via the History of Phone Phreaking archive: https://historyofphonephreaking.org/docs.php. https://www.slate.com/articles/technology/the_spectator/2011/10/the_article_that_inspired_steve_jobs_secrets_of_the_little_blue_.html (cit. on p. 78.)

Shi26. Hyun Song Shin, Tokenomics and blockchain fragmentation, Bank for International Settlements (2026), no. 1335, Available at https://www.bis.org/publ/work1335.pdf (permalink). (cit. on pp. 7, 78, and 79.)

SKL20. Ghiath Shabsigh, Tanai Khiaonarong, and Harry Leinonen, Distributed ledger technology experiments in payments and settlements, FinTech Notes 2020/001, International Monetary Fund, 2020. doi:10.5089/9781513536330.063 (cit. on p. 6.)

TSH22. Louis Tremblay Thibault, Tom Sarry, and Abdelhakim Senhaji Hafid, Blockchain scaling using rollups: A comprehensive survey, IEEE Access 10 (2022), 93039– 93054. doi:10.1109/ACCESS.2022.3200051 (cit. on p. 83.)

Tyg96. J. D. Tygar, Atomicity in electronic commerce, Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing (PODC ’96), ACM, 1996, pp. 8–26. doi:10.1145/280449.280458 (cit. on p. 3.)

WGDW22. Dong Wang, Yu Gao, Wensheng Dou, and Jun Wei, Dista: Generic dynamic taint tracking for java-based distributed systems, 2022 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), 2022, pp. 547–558. doi:10.1109/DSN53405.2022.00060 (cit. on pp. 82 and 83.)

ZABZ+21. Alexei Zamyatin, Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris-Kogias, Pedro Moreno-Sanchez, Aggelos Kiayias, and William J. Knottenbelt, SoK: Communication across distributed ledgers, Financial Cryptography and Data Security (Nikita Borisov and Claudia Diaz, eds.), Lecture Notes in Computer Science, vol. 12675, Springer, 2021, pp. 3–36. doi:10.1007/978-3-662-64331-0_1 (cit. on p. 6.)

ZHL+19. Alexei Zamyatin, Dominik Harz, Joshua Lind, Panayiotis Panayiotou, Arthur Gervais, and William J. Knottenbelt, XCLAIM: Trustless, interoperable, cryptocurrency-backed assets, 2019 IEEE Symposium on Security and Privacy (SP), IEEE, 2019, pp. 193–210. doi:10.1109/SP.2019.00085 (cit. on p. 6.)

Thanks. We are very grateful to Christopher Goes, Tobias Heindel, and Anthony Hart for support and feedback on this paper.

Notes

1Linear logic has a connective ! which permits copying and erasing a logical resource. It is called the exponential. ↩

2This process of creating two distinct timelines from one timeline is often called a fork. Thus we can truly say that you can have your cake and eat it too, provided you have a fork. ↩

3After all, most fiat balances are just digital ledger entries. ↩

4The word ‘sovereign’ is sometimes used here, as in ‘sovereign controller’. This is not quite what we intend. For example: a child is an independent entity from its parents, in the sense that the child has its own mental state and can emit and receive messages and exchange tokens as such. However, the child would not normally be called ‘sovereign’. For a nice worked example of the economic and political consequences of jumbling up the notions of independence, freedom, and sovereignty, see https://www.lrb.co.uk/blog/2021/january/sovereign-britain. ↩

5Arguably, a deeper reason that double-spend became a noun in its own right, is that the double-spend is the canonical simplest inconsistent pair of actions. Using the notation of this paper, the double-spend (𝑡,𝑡′) is the conceptually simplest pair of times such that 𝑡∨𝑡′ = ⊤. As such, one can argue that double-spend is to electronic cash, as excluded middle ‘P or not-P’ is to logic. In this view, the evolution of the terminology from 1983 to 1992 from ‘stops if note already on list’ to ‘double-spend’, reflects a real deepening of understanding of what is mathematically essential to the 1983 observation. This way of thinking of about things is mathematically suggestive. There is a field of logic called paraconsistent logic, which permits 𝑃 and ¬𝑃 to exist without full contradiction. In the notation of this paper (where ⊤is the inconsistent element) this would amount to permitting 𝑡∨𝑡′ < ⊤, even where 𝑡 and 𝑡′ are two halves of a double-spend. This would correspond to a system that might (but is not obliged to) try to reconcile an inconsistency somehow, short of simply rejecting it outright. Exploring paraconsistent electronic cash, and seeing if this might even be practically useful, is out-of-scope for this paper, but it would be an interesting concept for future research. ↩

6...as per the illustration, by converting it into a plate of crumbs and then removing the plate. ↩

7The terminology ‘Cut’ is a deliberate riff on cuts in proof-theory, which make long derivations shorter. Our Cut rule is not a logical cut, but there are some structural similarities between them. ↩

8The English phrases “Keep your friends close, and your enemies closer” and “I’ve got my eye on you” both reflect this. We supervise what we distrust. ↩

9The word ‘tree’ has surprisingly many possible meanings. A tree is: a type of plant (if you are a botanist); or a connected acyclic graph (if you are a graph theorist and don’t mind picking a root); or a poset such that for every 𝑥, 𝑥↓= {𝑥′ | 𝑥′ ≤𝑥} is linearly ordered (if you are an order theorist or combinatorialist); or a poset such that every 𝑥↓ is well-ordered (if you are a set theorist); or a special case of a Hasse diagram (if you are an automata theorist). These can mean different things: e.g. Q≥0 (nonnegative rationals) is a tree to an order theorist (it is a linear order with a least element), but not to a graph theorist (there is no useful covering relation between nodes) or a set theorist (it is not well-ordered). Here, we mean ‘tree’ in the order-theoretic sense, though if X is finite then this coincides with the graph-theoretic and set-theoretic notions. (The botanical use of the word ‘tree’ is on its own strange branch and we are at a loss to explain it. Perhaps an early botanist read a mathematics textbook?) ↩

10We will care most about the case that L is also sequential (Definition 2.1.1(3)), but this definition does not require that. ↩

11The ⚡ symbol (here denoting contradiction) quotes a standard symbol for proof by contradiction, where we write a lightning bolt when we arrive at a contradiction from our assumptions. The literature contains numerous symbols for this. The first author was taught to use , but this clashes visually with the # symbol we use for attestation in Definition 2.2.2. Another common symbol for this is 𝑡⊥𝑡′. Should we use that instead? No, no, no! We are already using ⊥ for the bottom element of a top-tree; we would get notational pathologies like ⊤⊥⊤ and ¬( ⊥⊥⊥) (instead of ⊤⚡ ⊤ and ¬( ⊥⚡ ⊥)); because we are calling ⊥ the consistent element, so using the same or similar symbol to denote contradiction seems an invitation to confusion; and finally because 𝑡⊥𝑡′ might suggest 𝑡∧𝑡′ = ⊥ whereas 𝑡⚡ 𝑡′ means 𝑡∨𝑡′ = ⊤, which is in fact the precise dual to that notion. ↩

12Subtlety alert: when we describe the process as ‘sequential’, we do not intend that its state space is just a straight line from ⊥ to ⊤ with no forks. We mean, as per the definition, that all paths back to ⊥ from a non-⊤state, are straight lines with no forks. ↩

13The condition ⊥≠⊤excludes the degenerate case of the one-element bounded semilattice, in which every element is inconsistent, because every element is equal to ⊤. Thanks to Anthony Hart for pointing this out. We could exclude the one-element model by insisting on ⊥≠⊤, but such a condition would not be algebraic (i.e. it would not be expressed purely in terms of a positive equality), so we should avoid doing this if possible. Furthermore, the one-element model seems to be harmless, in the sense that it does not invalidate any of the results we want to prove. So, we do not exclude it. ↩

14...or more generally, we need a value to represent Byzantine behaviour. The Byzantine behaviour we will care most about, for now, is nonsequentiality, so in the end this will amount to the same thing. ↩

15It might be helpful to recall that by part 6b, ⪯ denotes the partial order of times at the same controller, so property 7b only makes sense because of property 7a. ↩

16Because State = N ∪{ ⊤} it is also never-ending (because N is infinite) and without purpose (because there is no terminal value aside from failure ⊤). ↩

17For example: Alice (who is British) might observe Bob slurping noodles and infer that Bob is rude and uncouth, so |{Bob slurps}|Alice = {Bob slurps, Bob rude}. In contrast, Akiko (who is Japanese) might observe the same slurping and infer that Bob enjoyed his noodles and is being quite polite, so |{Bob slurps}|Akiko = {Bob slurps, Bob not rude}. ↩

18One might like to say that everybody agrees that 𝑃 and ¬𝑃 is inherently contradictory, in some global sense. Oh, if only. ↩

19Our cutting flags are indexed from 0 but our path indexes in Definition 4.1.1(3a) will be indexed from 1. Is this an off-by-one error? Yes and no. There is a mismatch, but it is deliberate. We leave 0 in here, so that in the later Definition, index 1 elements in paths can still have a cutting flag ↰0, ⋉0, or ⋊0 — even if the index 0 happens to be off the edge of the path. This is just like a train line map with arrows to stations that are off the map. ↩

20In the game of proving theorems, using fewer assumptions to prove the same conclusion, is a win. ↩

21Perhaps we just want to sit around a whiteboard proving theorems. Some people (including the first author) may enjoy this for its own sake. ↩

22...but for consistency the model does not have to be fancy. It just has to exist. ↩

23There are many examples of such results, but see Proposition 5.3.3 for a particularly clear example of the genre. ↩

24Insisting on 𝑗> 𝑖∈ index (Π) avoids an edge case where 𝑗= 1 and 𝑖> 𝑗 and Π[1] = Q𝑖. This could happen because the (Init) rule in Figure 9 does not restrict 𝑡1. We will not need the Corollary in this edge case (which seems to do our proofs no harm otherwise), so we exclude it here. ↩

25As per Remark 4.1.4(8a), here we use the structure of the Cut rule from Figure 9, that the 𝑖-index has the form 𝑡𝑖#⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘) where ⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘) is precisely the time at the 𝑗-index. We can see that what really matters is that the 𝑖-index has a time of the form 𝑡𝑖#𝑡′ where 𝑡′ ⪰⋊𝑖(𝑡𝑗#⋉𝑗𝑡𝑘), but that condition is a little bit longer to write out. ↩

26In the equation above, we can (equivalently, and without loss of generality) limit the universal quantification over 𝑟′ to be over all 𝑟′ ⪯R. This is because we assume 𝑟′#𝑠′ ⪯R in the implication, and by Definition 2.2.2(7b) (attestation expansive) 𝑟′ ⪯𝑟′#𝑠′. ↩

27In principle we could unify 𝑡𝑝 with 𝑡𝑝𝑝. That is, we could argue that the most recent time that 𝑝 attests to for itself, should be the most recent time for 𝑝. But for purposes of exposition we keep 𝑡𝑝 and 𝑡𝑝𝑝 separate. ↩

28These proofs of ⪯ are exactly the same kind of proofs a (non-⊤) controller needs to perform attestation: it must know that the new time 𝑡𝑝 it is attesting to does not conflict with previous attestations. In sequential systems (where any unordered times conflict), this means the new time is after the most recent time 𝑡′ 𝑝 (from the same controller) it attested to: 𝑡′ 𝑝⪯𝑡𝑝. So in an implementation, collecting these proofs requires no special machinery beyond what is already required to support attestations. ↩

29Similarly, in school we learn about addition and multiplication of numbers, and in university we may learn about groups, rings, and fields, as clean retrospective algebraic generalisations. ↩

30This is clearly related to the condition of being contradiction-preserving from Definition 2.2.2(7c). So why is it called ‘strong‘ here? This is just a fussy point of terminology. Morally Definitions 7.2(3) and 2.2.2(7c) are indeed the same, but technically they are not: in the former, 𝐹 is curried from some Y to some X → X; in the latter, # is a function in (Time × Time) → Time. The word ‘strong‘ is just to remind ourselves that 𝐹 preserves contradictions in Y and also X. The reader might call us pedants, but we would take that as a compliment. ↩

31In the vocabulary of this paper we can sum up ‘fragmentation’ (in the sense it is used in finance and cryptocurrency, usually with negative connotations) as “a tendency for real-life systems to develop multiple independent controllers”. We discuss how this happens in our discussion of the One True Controller in Subsection 1.5). ↩

32For example, we do not complain that there are multiple telephone networks and standards (each optimised for local conditions, hardware, and economic circumstances), because we have good mathematics and engineering to make them collaborate seamlessly for the user. It was not always thus. Some readers might remember that when you placed a long distance call, you could actually hear the connections being made — and, famously, even hijack the process. In fact this system, and its exploits, are an important part of early computing history, as described in [Ros71]. For further reading on a true story from the 1990s which beggars belief yet is strangely reminiscent of some modern stories from blockchain, see [Kap04]. We mention this particularly to illustrate that while the 2020s are not the 1970s or the 1990s, issues with multiple controllers on digital networked computing systems are not at all new. On the contrary, this is a recurrent problem ...and it can be and has been overcome. ↩

33This insight was hard-won: we spent many hours staring at broken lemmas until we understood this. ↩

34A special case of this is serialisability: can the history of the objects be phrased as a serial order of events, each of which is correct given all that have gone before [Pap79]. ↩

35The reader who objects here that it is not the bike that is exponential, but its wheel, so that this should really be called ‘the exponential-wheeled bike’ — is correct. Congratulations! You have qualified for a career in logic. ↩

36An analogy: set theory is a foundation for all of mathematics; on the other hand natural numbers generalise in many ways, including to complex numbers, rings, and lattices. It remains to be understood whether Figure 9 will, within its own application domain, behave more like set theory, or more like numbers. ↩