2.1 What this paper is (not) about

We are parametric across possible data.

Blockchains are best-known as stores of value but it is widely appreciated in the industry that a blockchain is just a particular kind of distributed database and that the data stored on it, and consistency conditions imposed on its transactions, can vary with the application.

This paper (in common with many real-life blockchain implementations) is parametric in the type of data stored on it. Specifically, we include as a parameter an uninterpreted type $\beta$ of ‘data’ in our ‘Idealised IEUTxO’, as a user-determined black box, and we admit a choice of admissible transactions and validators (this is the subset inclusions in the last two lines of Figure 1). ^{Footnote 3}

We do not consider networks or security.

Real blockchains rightly work hard to be efficient and secure. In the real world, we hash data, network latency matters, as do good cryptography, incentives, permissions, user training, passwords, privacy, and more.

Again, we are parametric in these concerns. We include an uninterpreted type $\alpha$ of ‘keys’, but do not force any particular cryptographic content on them. ^{Footnote 4}

We do have validators, but we elide their computational content.

The UTxO model of adding a block to a chain is that the chain has ‘unspent outputs’ – meaning output ports that have not yet engaged in interaction – and at each unspent output o is located at some data d and a validator v.

A validator is a machine that takes data-key pairs as input and decides whether they are ‘good’ or ‘bad’. Good data-key pairs let the user interact with the blockchain; bad ones get rejected. In more detail, to append a block to the blockchain, we

• • find a validator v on an unspent output o with data d and present it with a suitable key k such v considers (d,k) to be ‘good’;

• • the output is now considered ‘spent’ and our block is attached to the chain. ^{Footnote 5}

This is much like putting a key into a lock to open a door, except that appending a block is irreversible: an output, once spent, cannot be unspent. ^{Footnote 6} The idea is that our newly attached block may introduce fresh outputs with validators which we designed and to which we have the keys; ^{Footnote 7} these are new ‘unspent’ outputs on the chain. ^{Footnote 8}

We do model validators in this paper, but mathematically – meaning that a validator is not a code-script (as it would be in real life). Instead, we identify a validator directly with the set of data-key pairs that it accepts.^{Footnote 9}

This basic idea of block combination and validation might not seem like much. ^{Footnote 10} However, this is the fundamental operation of the UTxO architecture, and we shall find many interesting and unexpected observations to make about it.

So if there is one question that this paper addresses, it is this: What does it mean, mathematically, when we append a transaction to a UTxO blockchain?

Our answer occupies the rest of this paper.

In the rest of this Section, we will set up some basic mathematical machinery. The reader is welcome to skip or skim it and refer back to it as required.

2.2 Basic data structures

We will use atoms to locate inputs and outputs on a blockchain. More on this in Subsection 2.3.

Notation 2.2.3

1. (1). Write $\mathbb N=\{0,1,2,\dots\}$ .

2. (2). If $\textsf X$ is a set, write $\textit{fin}(\textsf X)$ for the finite power set of $\textsf X$ , and $\textit{fin}_!(\textsf X)$ for the pointed finite power set. In symbols:

   \begin{align*}\textit{fin}_!(\textsf X) = \{ (X,x)\in \textit{fin}(\textsf X)\times \textsf X\mid x\in X\}.\end{align*}
   Above, (X,x) is a pair, and $\textit{fin}(\textsf X)\times\textsf X$ is a Cartesian product.

3. (3). If $\textsf X$ and $\textsf Y$ are sets, we use a convenient shorthand in Figure 1 by writing

   \begin{align*}(\textit{fin}(\textsf X),\textsf Y)_!\quad\text{as shorthand for}\quad(\textit{fin}(\textsf X)_!,\textsf Y) .\end{align*}
   That is, we take $(\text{-})_!$ to act on a pair functorially, on the first component. We do this in Figure 1 when we write $\textsf{Transaction}_!$ in the definition of $\textsf{Validator}$ .

4. (4). If $\textsf X$ is a set then write $[\textsf X]$ for the set of (possibly empty) finite lists of elements from $\textsf X$ . We write $\bullet$ for list concatenation, so $l\bullet l'$ is l followed by l’. More generally, we will write $\bullet$ for any monoid composition; list concatenation is one instance. It will always be clear what is intended.

5. (5). If $\textsf X$ is a set then order $l,l'\in [\textsf X]$ by the sublist inclusion relation, where $l\leq l'$ when l can be obtained from l’ by deleting (but not rearranging) some of its elements.

6. (6). If $\textsf X$ is a set and $x\in\textsf X$ then we may call the one-element list $[x]\in[\textsf X]$ a singleton.

7. (7). If $V\in \textsf X\to\textsf{Bool}$ and $x\in\textsf X$ then we may write V(x) or $V\,x$ for $V\,x = \textsf{True}$ .

2.3 The permutation action

1. (1). To state the key Definition 4.3.6.

2. (2). To prove Lemma 5.2.1, and thus Proposition 5.2.2.

Because we assume atoms and are working in a ZFA universe, everything has a standard permutation action. We describe it in Definition 2.3.3. Programmers can think of the permutation action as a generic definition in the ZFA universe (given below in this Remark), which is sufficiently generic that it exists for all the data types considered in this paper. By this perspective, Definition 2.3.3 specifies how this generic action interacts with the specific type-formers of interest for this paper.

Definition 2.3.2 For reference, we write out the ZFA generic definition, which is by $\epsilon$ -induction on the sets universe:

\begin{align*}\begin{array}{r@{\ }l@{\qquad}l}\pi{\cdot} a=&\pi(a) & a\in{\mathbb A}\\\pi{\cdot} X =& \{\pi{\cdot} x\mid x\in X\} &X\text{ a set}.\end{array}\end{align*}

More information on this sets inductive definition is in Gabbay (Reference Gabbay2001, Reference Gabbay2020a). Definition 2.3.3 can be usefully viewed as a collection of concrete instances of Definition 3.2 for the data types of interest in this paper:

1. (1). If $\pi\in\textit{Perm}$ and $a\in\mathbb A$ then $\pi$ acts on a as a function:

   \begin{align*}\pi{\cdot} a=\pi(a) .\end{align*}

2. (2). If $\pi\in\textit{Perm}$ and X is any set then $\pi$ acts pointwise on X as follows:

   \begin{align*}\pi{\cdot} X=\{\pi{\cdot} x\mid x\in X\} .\end{align*}
   Note as a corollary of this that $x\in X \Longleftrightarrow \pi{\cdot} x\in\pi{\cdot} X$ .

3. (3). If $\pi\in\textit{Perm}$ and $(x_1,\dots,x_n)$ is a tuple then $\pi$ acts pointwise on $(x_1,\dots,x_n)$ as follows:

   \begin{align*}\pi{\cdot}(x_1,\dots,x_n) = (\pi{\cdot} x_1,\dots,\pi{\cdot} x_n) .\end{align*}
   Note therefore that $\pi{\cdot}((x_1,\dots,x_n)!!i)=\pi{\cdot} x_i$ , where $1\leq i\leq n$ and $!!$ indicates lookup.

4. (4). If $\pi\in\textit{Perm}$ and $i\in\mathbb N$ then $\pi{\cdot} i = i$ .

5. (5). If $\pi\in\textit{Perm}$ and (X,x) is a pointed set (Notation 2.2.3(2)) then $\pi$ acts pointwise on (X,x) as follows:

   \begin{align*}\pi{\cdot} (X,x) = (\pi{\cdot} X,\pi{\cdot} x) .\end{align*}
   (This is indeed just a special case of the previous case, for tuples.) If $\pi\in\textit{Perm}$ and f is a function, then $\pi$ has the conjugation action on f as follows:
   \begin{align*}(\pi{\cdot} f)(x) = \pi{\cdot}(f(\pi^{\text{-}1}{\cdot} x)) .\end{align*}
   Note therefore that $\pi{\cdot} (f(x))=(\pi{\cdot} f)(\pi{\cdot} x)$ , and $\pi{\cdot} f$ maps $\pi{\cdot} x$ to $\pi{\cdot} (f(x))$ .

6. (6). In particular, $\pi$ acts as the above on the inputs, outputs, sets of inputs, sets of outputs, transactions, and validators from Figure 1.

7. (7). If $\pi\in\textit{Perm}$ and R is a relation, then $\pi$ acts pointwise such that

   \begin{align*}\pi{\cdot} R = \{(\pi{\cdot} x,\pi{\cdot} y)\mid (x,y)\in R\}\end{align*}
   so that
   \begin{align*}x\mathrel{\pi{\cdot} R} y\Longleftrightarrow\pi^{\text{-}1}{\cdot} x\mathrel{R} \pi^{\text{-}1}{\cdot} y .\end{align*}

We use Definition 2.3.4 in Definition 4.3.6, but it is a useful concept so we include it here:

Definition 2.3.4 If $a\in{\mathbb A}$ then write $\textit{fix}(a)$ for the set of permutations $\pi\in\textit{Perm}$ such that $\pi(a)=a$ . In symbols:

\begin{align*}\textit{fix}(a) = \{\pi\in\textit{Perm} \mid \pi(a)=a\} .\end{align*}

1. (1). ${\mathbb A}$ is equivariant, and no individual atom $a\in{\mathbb A}$ is equivariant.

2. (2). A set X is equivariant when

   \begin{align*}\forall{\pi{\in}\textit{Perm}}(x\in X \Longleftrightarrow \pi{\cdot} x\in X).\end{align*}
   In words: A set is equivariant precisely when it is closed in the orbits of its elements under the permutation action.

3. (3). $(x_1,\dots,x_n)$ is equivariant precisely when $x_i$ is equivariant for every $1\leq i\leq n$ .

4. (4). $\mathbb N$ is equivariant, and every $i\in\mathbb N$ is equivariant.

5. (5). A pointed set (X,x) is equivariant precisely when X and x are equivariant.

6. (6). A function f is equivariant when $\pi{\cdot} (f(x))=f(\pi{\cdot} x)$ for every x and every $\pi$ .

7. (7). A relation R is equivariant when

   \begin{align*}\forall{\pi{\in}\textit{Perm}}\forall{x,y}(x\mathrel{R} y \Longleftrightarrow \pi{\cdot} x\mathrel{R}\pi{\cdot} y) .\end{align*}

3.1 IEUTxO equations and solutions

Definition 3.1.2 Let a solution or model of the IEUTxO type equations in Figure 1 be a tuple

\begin{align*}\mathbb T=(\alpha,\beta,\textsf{Transaction},\textsf{Validator},\nu : \textsf{Validator}\hookrightarrow \textit{pow}(\beta\times\textsf{Transaction}_!))\end{align*}

where

1. (1). $\alpha$ is an uninterpreted ^{Footnote 12} equivariant (Definition 2.3.5(2)) set of keys,

2. (2). $\beta$ is an uninterpreted equivariant set of data,

3. (3). $\textsf{Validator}$ is an equivariant set of validators.

4. (4). $\textsf{Transaction}$ is an equivariant subset of $\textit{fin}({\mathbb A}\times\alpha)\times\textit{fin}({\mathbb A}\times\beta\times\textsf{Validator}),$ and we disallow the empty transaction, having no inputs or outputs.

5. (5). $\nu$ is an equivariant injective function (Definition 2.3.5(3)) from $\textsf{Validator}$ to $\textit{pow}(\beta\times\textsf{Transaction}_!)$ .

Some notation will be helpful:

Notation 3.1.3 If $\textit{tx}=(I,O)\in\textsf{Transaction}$ and $i\in I$ then write $\textit{tx}\text{@} i\in\textsf{Transaction}_!$ for the input-in-context ((I,i),O) obtained by pointing I at $i\in I$ (Notation 2.2.3). In symbols:

\begin{align*}\text{if }\textit{tx}=(I,O)\in\textsf{Translation}\ \text{and}\ i\in I\quad\text{then}\quad\textit{tx}\text{@} i = ((I,i),O) \in \textsf{Transaction}_!\end{align*}

Example 3.1.4 In Figures 2 and 3, we take a short diagrammatic tour of Definition 3.1.2, before continuing with the technical development. Since we have yet to build our machinery, this discussion is informal and intuitive. We include precise forward pointers to later definitions where appropriate; additional diagrams will be discussed in detail in Example 3.4.11.

Figure 2. A pair of transactions $\textit{tx}$ and $\textit{ty}$ .

$\textit{tx}\in\textsf{Transaction}$ in Figure 2 is a pair of a set of three inputs, and a set of two outputs:

\begin{align*}\textit{tx}\ =\ \Bigl(\{(a,x_1),(b,x_2),(c,x_3)\}\ ,\ \{(d,y_1,v_1),(e,y_2,v_2)\}\Bigr) .\end{align*}

Above:

• • a, b, c, d and e are atoms in $\mathbb A$ . They serve as unique labels for the inputs and outputs. Note that every input and output in $\textit{tx}$ has a distinct label. This is not directly enforced in the raw data type in Figure 1, but it will follow as a consequence of well-formedness conditions which we introduce later, in Definition 3.4.1. Since each input is labelled with a unique atom, and similarly for each output, we may treat atoms as positions, locations or channels. Thus for example, the input $(a,x_1)$ is labelled with a and so we can think intuitively that it is located at position a; or waiting to communicate its data $x_1$ on channel a.

• • $x_1$ and $x_2$ are elements of $\alpha$ . This is just an uninterpreted data type, but a good intuition is that these are cryptographic keys.

• • $y_1$ and $y_2$ are elements of $\beta$ . This is just an uninterpreted data type: the intuition is that $y_1$ and $y_2$ are fragments of state data. Note that state data are stored per-output and not per-transaction. We suppose for concreteness that $\beta=\mathbb N$ , so state data can be summed (as we do in the output f of $\textit{ty}$ ; more in this shortly). Note that $\textsf{Transaction}$ is a subset of $\textit{fin}(\textsf{Input})\times\textit{fin}(\textsf{Output})$ in Figure 2; which subset, is a parameter of the model selected. So for example, we could enforce that all state data on all inputs and outputs should be equal, and this would in effect ensure that state data are a per-transaction quantity. This may or may not be what we want: the definition allows us to choose.

• • $v_1$ and $v_2$ are validators. Their role is, intuitively, to decide which transactions $\textit{tx}$ will interact with (precise definition in Definition 3.4.1(4)).

$\textit{ty}\in\textsf{Transaction}$ is another transaction, with two inputs and one output. Note that its inputs are located at d and e, meaning that the inputs of $\textit{ty}$ point to the outputs of $\textit{tx}$ (Definition 3.2.6). Note also that it performs an addition, in the sense that the state data of its single output are the sum of the state data on its two inputs.

If in addition the following validation conditions are satisfied (@ from Notation 3.1.3)

• • $(y_1,\textit{ty}\text{@} (d,x_4))\in \nu(v_1)$ (in words: validator $v_1$ in state $y_1$ validates the pointed transaction $\textit{ty}\text{@} (d,x_4))$ ), and

• • $(y_2,\textit{ty}\text{@} (e,x_5))\in \nu(v_2)$ (in words: validator $v_2$ in state $y_2$ validates the pointed transaction $\textit{ty}\text{@} (e,x_5)$ ) then the two-element sequence $[\textit{tx},\textit{ty}]$ is considered to be a valid combination. In the terminology, we define later, this is called a chunk (Definition 3.4.1).

Supposing this is so. Then, we can join the two transactions as illustrated in Figure 3, using blue circles to indicate successful validations. Congratulations: we have performed our first blockchain concatenation.

Note that both validations must succeed for the combination $[\textit{tx},\textit{ty}]$ to be considered a valid chunk. More diagrams and discussion follow in Example 3.4.11. We now return to the definitions.

Notation 3.1.5 Sets that do not include atoms – including $\mathbb N$ , inductive types built using $\mathbb N$ , and function types built using $\mathbb N$ – are automatically equivariant. Thus, if the reader unfamiliar with nominal techniques and ZFA wonders whether particular choices they need for $\alpha$ , $\beta$ and $\textsf{Validator}$ are equivariant – then the answer is ‘yes’.

We may elide equivariance conditions Definition 3.1.2 henceforth. Any such type-like definition will be equivariant – that is closed under taking orbits of the permutation action – unless stated otherwise.

This paper will be light on sets and categorical foundations: we use just enough so that readers from various backgrounds get a hook on the ideas that speaks to them, and so it is always clear what is meant and how it could be made fully formal.

Note that just because a set is equivariant does not mean all its elements must be; for instance, $\mathbb A$ is equivariant (and consists of a single permutation orbit), but none of its elements $a\in{\mathbb A}$ are equivariant.

Also, sets are well-founded, so a pure subset inclusion solution to Figure 1, for both clauses, would be difficult; we use $\nu$ to break the downward chain of sets inclusions. ^{Footnote 14} Yet just as we may write

\begin{align*}\mathbb N\subseteq\mathbb Q\subseteq\mathbb R,\end{align*}

eliding (or neglecting to consider) that their realisations may differ (finite cardinals vs. equivalence classes of pairs vs. Dedekind cuts), so – since $\nu$ is an injection – it may be convenient to treat $\textsf{Validator}$ as a literal subset of $\textit{pow}(\beta\times\textsf{Transaction}_!)$ . ^{Footnote 15} This is standard, provided we clearly state what is intended and are confident that we could unroll the injections if required.

Thus, Definition 3.1.9 rephrases Definition 3.1.2, with a focus on extensional sets behaviour rather than on internal structure (and for reference, see Definition 6.2.1 for an example of where the internal structure is required):

Definition 3.1.9 An IEUTxO model $\mathbb T$ from Definition 3.1.2 can be presented modulo Remark 3.1.8 as a tuple

\begin{align*}\mathbb T=(\alpha_{\mathbb T},\beta_{\mathbb T},\textsf{Transaction}_{\mathbb T},\textsf{Validator}_{\mathbb T})\end{align*}

of sets that solves the equations in Figure 1. We may drop the $\mathbb T$ subscripts where these are clear from the context.

3.3 Why we have $\alpha$ and $\beta$

We are now ready to more rigorously explain the roles of $\alpha$ and $\beta$ in Figure 1. We touched on this already in Subsection 2.1 ( $\alpha$ is ‘keys’; $\beta$ is ‘data’), but now we can be more specific in our discussion:

• • $\alpha$ is intuitively a data type for keys. If $i=(a,k)$ , then k is supposed to be a cryptographic secret that we need to attach to a suitable unspent output (e.g. a solution to a cryptographic puzzle posted by its validator).

• • $\beta$ is intuitively a data type of abstract data. If $o=(p,d,V)$ then d stores some kind of state (for instance, an account balance).

We should note:

1. (1). Nothing mathematical enforces this usage. $\alpha$ and $\beta$ are abstract type parameters, to instantiate as we please.

2. (2). $\beta$ is redundant and can be isomorphically removed. We briefly sketch a suitable isomorphism: We set $\textsf{Output}={\mathbb A}\times\textsf{Validator}$ and $\textsf{Validator}\subseteq{pow}(\textsf{Transaction}_!)$ in Figure 1. $\alpha$ is replaced by $\alpha\times\beta$ , and information that was stored as $d\in\beta$ on an output would instead be stored in the validator of that output, which would be set to accept only inputs with $\beta$ -component d. If we only care about countable data types and computable data (a reasonable simplification), then everything could be GÖdel encoded into $\mathbb N$ . So we could then just fix $\alpha=\mathbb N$ .

But there is a design tension here: we want something that is compact, but also implementable (e.g. as proof-of-concept reference code; see Remark 3.3.1). Having explicit types of keys $\alpha$ and data $\beta$ is useful for clarity, so even though $\alpha$ and $\beta$ introduce (a little) redundancy, the cost is minimal and the practical returns worthwhile.

Furthermore, in the real world validators are generated by code. This validator code is typically given state data which is carried on the same output as the validator is stored, to help the validator decide whether to validate prospective input. So when we write $\textsf{Validator}\subseteq{pow}(\beta\times\textsf{Transaction}_!)$ , this effectively makes the validator into a function over local state data and a transaction input.

We see this happen concretely in equation (1) in Definition 3.2.6: we have $o=(p,d,V)$ and we pass the state data d of o to V the validator of o –

\begin{align*}(d,{tx}\text{@} i)\in V\end{align*}

– even though this is mathematically redundant, since d and V are both in o so the d could in principle be curried into the V. We retain $\beta$ and set $\textsf{Validator}\subseteq{pow}(\beta\times\textsf{Transaction}_!)$ rather than just $\textsf{Validator}\subseteq{pow}(\textsf{Transaction}_!)$ , to reflect this practical architecture.

3.4 Chunks and blockchains

3.4.1 Chunks

Definition 3.4.1 (chunks) is a central concept in this paper, so we will summarise it twice: once now and again after the definition: A list of transactions is a chunk when all input positions are distinct, all output positions are distinct, and all inputs point to at most one earlier validating output. Examples are illustrated in Example 3.4.11 (along with examples of blockchains). In formal detail:

Definition 3.4.1 Suppose $\mathbb T=(\alpha,\beta,\textsf{Transaction},\textsf{Validator})$ is an IEUTxO model. Call a transaction-list ${txs}\in[\textsf{Transactions}]$ a chunk when:

1. (1). Distinct outputs appearing in ${txs}$ have distinct positions.

2. (2). Distinct inputs appearing in ${txs}$ have distinct positions. It may be that the position of an input $i\in{tx}\in{txs}$ equals that of some output $o\in{tx}'\in{txs}$ , or using the notation of Definition 3.2.6(1): $i\mapsto o$ . If so, by condition 4.1 there is at most one such. We write the unique output pointed to by i

   \begin{align*}{txs}(i)\in\textsf{Output}\end{align*}
   where it exists, so $o={txs}(i)\in{tx}'\in{txs}$ .

3. (3). For every input $i\in{tx}\in{txs}$ , if the output ${txs}(i)$ is defined then that output must occur in a transaction ${tx}'$ that is strictly earlier than ${tx}$ in ${txs}$ .

4. (4). For every $i\in{tx}\in{txs}$ , if ${txs}(i)$ is defined then ${validates}({txs}(i),{tx}\text{@} i)$ (Definition 3.2.6(2)).

Remark 3.4.2 So to sum Definition 3.4.1 up in a single line: a chunk is a list of transactions such that a position can only ever be shared between a single pair of an earlier output o to a later input i, which o validates – and otherwise positions are distinct.

Notation 4.3

1. (1). Write

   \begin{align*}\textsf{Chunk}_{\mathbb T}\subseteq[\textsf{Transaction}_{\mathbb T}]\quad\text{for the set of chunks over $\mathbb T$.}\end{align*}
   We may drop the $\mathbb T$ subscripts; the meaning will always be clear.

2. (2). We may also call a transaction-list valid, when it is a chunk. That is, chunks are precisely the valid transaction-lists.

Remark 3.4.4 The way we have formulated the structure of chunks in Definition 3.4.1 reminds this author of the $\pi$ -calculus, where positions correspond to $\pi$ -calculus channel names (and outputs are outputs and inputs are inputs).

When we have this intuition in mind, we may occasionally call positions channels, as in the blocked channels of Subsection 5.5. See also the discussion in Remark 4.3.4.

With the intuition of Remark 3.4.4 in mind, we give a simple definition, which refines Definition 3.2.3:

Definition 3.4.5 Suppose $\mathbb T=(\alpha,\beta,\textsf{Transaction},\textsf{Validator})$ is an IEUTxO model and suppose ${tx}=(I,O)\in\textsf{Transaction}$ is a transaction. Then define

• • the input channels or positions ${input}({tx})\mathbin{\subseteq_{\text{\it fin}}}{\mathbb A}$ of ${tx}$ to be the finite set of atoms that are positions of inputs in ${tx}$ , and

• • the output channels or positions ${output}({tx})\mathbin{\subseteq_{\text{\it fin}}}{\mathbb A}$ of ${tx}$ to be the finite set of atoms that are positions of outputs in ${tx}$ . In symbols:

  \begin{align*}\begin{array}{r@{\ }l}{input}({tx}) =& \{p \mid (p,k)\in I\}\\{output}({tx}) =& \{p \mid (p,d,V)\in O\} .\end{array}\end{align*}

An important special case of Notation 3.4.3 is when the chunk is a singleton list, that is it contains just one transaction:

Lemma 3.4.6 Suppose $\mathbb T$ is an IEUTxO model and suppose ${tx}\in\textsf{Transaction}$ . Then

\begin{align*}[{tx}]\in\textsf{Chunk}\quad\text{if and only if}\quad{input}({tx})\cap{output}({tx})=\varnothing.\end{align*}

Proof. We consider the conditions in Definition 3.4.1 and see that condition 3 forces the input and output channels of the transaction to be disjoint, and then none of the other conditions are relevant.

Remark 3.4.7 Definition 3.4.5 refines Definition 3.2.3, and another way to phrase Lemma 3.4.6 is that $[{tx}]$ is a chunk precisely when ${pos}({tx})={inputs}({tx})\uplus{outputs}({tx})$ , where $\uplus$ denotes disjoint sets union.

3.4.3 …. and blockchains

With the machinery we have now have, it is quick and easy to define blockchains:

Definition 3.4.10 A blockchain is a chunk ${ch}\in\textsf{Chunk}$ such that ${utxi}({ch})=\varnothing$ . In words: a blockchain is a chunk with no unspent inputs. Diagrammatic examples follow in Example 3.4.11:

Example 3.4.11 Recall we observed in Subsection 2.1 that (in the terminology that we now have) the key operation of an IEUTxO is to attach a transaction’s inputs to a chunk’s outputs.

Example transaction-lists, blockchains and chunks are illustrated in Figures 2, 3, 5, 6, 7 and 8. ^{Footnote 20}

Figure 5. A blockchain $\mathcal B=[{tx}_1,{tx}_2,{tx}_3,{tx}_4]$ .

Figure 6. $\mathcal B$ chopped up as a blockchain $[{tx}_1,{tx}_2]$ and a chunk $[{tx}_3,{tx}_4]$ .

Figure 7. $\mathcal B$ chopped up as a blockchain $[{tx}_1,{tx}_3]$ and a chunk $[{tx}_2,{tx}_4]$ .

Figure 8. The blockchain $\mathcal B'=[{tx}_1,{tx}_3,{tx}_2,{tx}_4]$ .

In the Figures, a blue circle denotes a validator on an output at some position ( $a,b,c,\dots$ ) that has accepted an input and connected to it, and a red circle denotes an unspent input or output, meaning one that has not connected up with a validator to form a spent output-input pair:

1. (1). $\mathcal B$ , $\mathcal B'$ , $[{tx}_1,{tx}_2]$ and $[{tx}_1,{tx}_3]$ are blockchains, because they have unspent outputs (in red) but no unspent inputs. In these blockchains, ${tx}_1$ is what is called the genesis block, meaning the first block in the chain. It follows from the definitions that the genesis block has no inputs. ^{Footnote 21}

2. (2). $[{tx}]$ (Figure 2) and $[{tx}_1]$ , $[{tx}_3,{tx}_4]$ and $[{tx}_2,{tx}_4]$ are chunks, but not blockchains because they have unspent inputs (in red).

3. (3). $[{tx}_2,{tx}_1]$ is neither a blockchain nor chunk, because the b-input of ${tx}_2$ points to the later b-output of ${tx}_1$ . It is just a list of transactions.

We note two alternative characterisation of blockchains (Definition 3.4.10):

Lemma 3.4.12 A chunk is a blockchain when ….

1. (1). …. the ‘at most one’ in Definition 3.4.1(2) is strengthened to ‘precisely one’.

2. (2). …. the function $i\mapsto{txs}(i)$ (Definition 3.4.1(2)) is a total function on the inputs in ${txs}$ (so that every input points to precisely one output in an earlier transaction).

Remark 3.4.13 We step back to reflect on Definition 3.4.10. This is supposed to be a paper about blockchains; why did it take us this long to get to them? Because they are a special case of something better and more pertinent: chunks.

A blockchain is just a left-closed chunk. There is nothing wrong with blockchains, but mathematically, chunks seem more interesting:

1. (1). A sublist of a blockchain is a chunk, not a blockchain (we prove this in a moment, in Corollary 3.5.2).

2. (2). A composition of blockchains is possible, but uninteresting, whereas composition of chunks is clearly an interesting operation. ^{Footnote 22}

3. (3). If we cut a blockchain into n pieces then we get one blockchain (the initial segment) …. and $n-1$ chunks.

4. (4). Chunks can in any case be viewed as a natural generalisation of blockchains, to allow UTxIs as well as UTxOs.

Definitions and results like Definition 3.5.3, Theorem 3.5.4 and Lemma 3.5.9 inhabit a universe of chunks, not blockchains.

Even in implementation, where we care about real blockchains on real systems, a lot of development work goes into allowing users in practice to download only partial histories of the blockchain rather than having to download and store a complete record – the motivation here is practical, not mathematical – and in the terminology of this paper, we would say that for efficiency we may prefer to work with chunks where possible, because they can be partial and so can be more lightweight.

So the focus of this paper is on chunks: they generalise blockchains, have better mathematical structure, and chunks are in any case where we arrive even if we start off asserting (de)compositional properties of blockchains, and finally – though this is not rigorously explored in this paper, but we would suggest that – chunks are also where we arrive when we consider space-efficient blockchain implementations.

Finally, we mention that blockchains have a right monoid action given by concatenating chunks. Thus, by analogy here with rings and modules, we could imagine for future work a mathematics of blockchains generalising Definition 4.10 such that a ‘blockchain set’ is just any set with a suitable chunk action.

3.5 Properties of chunks and blockchains

3.5.1 Algebraic and closure properties of chunks

Lemma 3.5.1 expresses that a list of transactions is a valid chunk if and only if every sublist of it of length at most two is a valid chunk. In this sense, (in)validity is a local phenomenon:

Lemma 3.5.1 Suppose $\mathbb T=(\alpha_{\mathbb T},\beta_{\mathbb T},\textsf{Transaction}_{\mathbb T},\textsf{Validator}_{\mathbb T})$ is an IEUTxO model, and suppose $[{tx}_1,\dots,{tx}_n]\in[\textsf{Transaction}]$ . Then the following conditions are equivalent:

• • $[{tx}_i,{tx}_j]\in\textsf{Chunk}$ for every $1\leq i< j\leq n$ ^{Footnote 23}

• • $[{tx}_1,\dots,{tx}_n]\in\textsf{Chunk}$

Proof. We note of the well-formedness conditions on chunks from Definition 3.4.1 that they all concern relationships involving at most two transactions.

Corollary 3.5.2 ((Validity is down-closed)) Suppose we have an IEUTxO model $\mathbb T=(\alpha,\beta,\textsf{Transaction},\textsf{Validator})$ and $l,l'\in[\textsf{Transaction}]$ .

Recall from Notation 2.2.3 that we order lists by sublist inclusion, so $l'\leq l$ when l’ is a sublist of l. Then

\begin{align*}{ch}\in\textsf{Chunk}\ \land\ l'\in[\textsf{Transaction}]\ \land\ l'\leq {ch}\quad\text{implies}\quad l'\in\textsf{Chunk} .\end{align*}

In words: every sublist of a chunk, is itself a chunk.

Proof. From Lemma 3.5.1.

We can wrap up Corollary 3.5.2 in a nice mathematical package:

Definition 3.5.3 Suppose $(X,\leq,\bullet,\textsf{e})$ has the following structure:

1. (1). X is a set.

2. (2). $(X,\leq)$ is a partial order, for which $\textsf{e}$ is a bottom element.

3. (3). $\bullet$ is a partial monoid action on X, meaning that $(x\bullet y)\bullet z$ exists if and only if $x\bullet (y\bullet z)$ exists, and if both exist then they are equal.^{Footnote 24}

4. (4). $\bullet$ is down-closed, meaning that if $x'\leq x$ and $x\bullet y$ exists, then so does $x'\bullet y$ , and similarly for $y\bullet x$ and $y\bullet x'$ .

5. (5). $\bullet$ is monotone where defined, meaning that if $x'\leq x$ then $x'\bullet y\leq x\bullet y$ (provided $x\bullet y$ exists), and similarly for $y\bullet x$ and $y\bullet x'$ . In this case, call $(X,\leq,\bullet,\textsf{e})$ a partially ordered partial monoid.

Theorem 3.5.4 Suppose $\mathbb T$ is an IEUTxO model (Definition 3.1.9).

Then, its set of chunks $\textsf{Chunk}_{\mathbb T}$ (Definition 3.4.1) forms a partially ordered partial monoid (Definition 3.5.3), where

• • $\leq$ is sublist inclusion,

• • $\bullet$ is list concatenation, and

• • the unit element is [] the empty set.

Proof. By facts of lists, and Corollary 3.5.2.

3.5.2 Some observations on observational equivalence

Remark 3.5.5 Lemmas 3.5.6 and 3.5.9 apply to IEUTxO models and essentially give criteria for observational equivalence when positions are disjoint.

We find them echoed in the theory of abstract chunk systems as Definitions 4.4.1(5) and 4.4.1(4), and we need them for Proposition 4.4.8.

Lemma 3.5.6 Suppose $\mathbb T=(\alpha,\beta,\textsf{Transaction},\textsf{Validator})$ is an IEUTxO model and ${ch},{ch}'\in\textsf{Chunk}_{\mathbb T}$ . Then

\begin{align*}{pos}({ch})\cap{pos}({ch}')=\varnothing\quad\text{implies}\quad{ch}\bullet{ch}'\in\textsf{Chunk}_{\mathbb T}.\end{align*}

Proof. By routine checking of possibilities, using the fact that if ${pos}({ch})\cap{pos}({ch}')=\varnothing$ (Definition 3.2.3) then they have no positions in common, so no output in one can be called on to validate an input in the other.

Definition 3.5.7 Suppose ${ch},{ch}'\in\textsf{Chunk}_{\mathbb T}$ . Then call ${ch}$ and ${ch}'$ commuting when

\begin{align*}\begin{array}{l}{ch}\bullet{ch}'\in\textsf{Chunk}_{\mathbb T}\Longleftrightarrow{ch}'\bullet{ch}\in\textsf{Chunk}_{\mathbb T} .\end{array}\end{align*}

Remark 3.5.8 Definition 3.5.7 is clearly a notion of observational equivalence between ${ch}\bullet{ch}'$ and ${ch}'\bullet{ch}$ where the observable is ‘forms a valid chunk with’. This observable does not depend on internal structure, so we will develop it further once we have abstract chunk systems; see Definition 4.3.16.

For now, Definition 3.5.7 gives us just enough of the background theory of observational equivalence, to state and prove Lemma 3.5.9, Proposition 3.5.12, and Theorem 3.6.1.

Lemma 3.5.9 Suppose $\mathbb T=(\alpha,\beta,\textsf{Transaction},\textsf{Validator})$ is an IEUTxO model. Then:

1. (1). If ${tx},{tx}'\in\textsf{Transaction}$ and ${pos}({tx})\cap{pos}({tx}')=\varnothing$ (Definition 3. 2.3) then the following all hold:

   $$[tx,t{x^\prime }] \in {\rm{Chunk}}\; \Leftrightarrow [t{x^\prime },tx] \in {\rm{Chunk}}\; \Leftrightarrow [tx],[t{x^\prime }] \in {\rm{Chunk}}$$

2. (2). As a corollary, if ${ch},{ch}'\in\textsf{Chunk}$ and ${pos}({ch})\cap{pos}({ch}')=\varnothing$ then ${ch}$ and ${ch}'$ are commuting (Definition 3.5.7).

Proof.

1. (1). By routine checking of possibilities, using the fact that if ${pos}({tx})\cap{pos}({tx}')=\varnothing$ then they have no positions in common, so no output in one can be called upon to validate an input in the other.

2. (2). It is a fact that if ${tx}\in l$ then ${pos}({tx})\subseteq{pos}(l)$ and similarly for ${tx}'\in l'$ . The corollary now follows by a routine argument from part 1 of this result and Lemma 3.5.1.

3.5.3 Properties of UTxOs and UTxIs

We return to Definition 3.4.8: Lemma 3.5.10 uses Definition 3.4.8 to note some simple properties of Definition 3.4.1.

Lemma 3.5.10 Suppose $\mathbb T$ is an IEUTxO model and ${ch},{ch}'\in\textsf{Chunk}_{\mathbb T}$ Then:

1. (1). ${utxi}({ch})\cap{utxo}({ch})=\varnothing$

2. (2). If ${ch}\bullet{ch}'\in\textsf{Chunk}_{\mathbb T}$ then ${pos}({ch})\cap{pos}({ch}')\subseteq{utxo}({ch})\cap{utxi}({ch}')$ .

3. (3). $\eqalign{ & \emptyset = utxi(ch) \cap stx(ch) \cr & \emptyset = utxo(ch) \cap stx(ch) \cr & pos(ch) = utxi(ch) \uplus utxo(ch) \uplus stx(ch)\,\,\,is{\rm{ }}disjo{\mathop{\rm int}} {\rm{ }}union \cr} $

Proof.

1. (1). An input cannot point to a later output, because of Definition 3.4.1(3), and if it points to an earlier output then by construction in Definition 3.4.8 this position no longer labels a UTxO or UTxI. Furthermore a position can be used at most once in an input-output pair, by Definition 3.4.1(2).

2. (2). From Definition 3.4.1(3), as for the previous case.

3. (3). All facts of Definition 3.4.8 and Figure 4.

Remark 3.5.11 Proposition 3.5.12 can be viewed as a stronger version of Lemma 3.5.6. It is an important result because it relates the following apparently different observables:

1. (1). A statically observable property, that ${ch}$ and ${ch}'$ mention disjoint sets of positions.

2. (2). A locally observable property, that ${ch}$ and ${ch}'$ compose in both directions.

3. (3). An abstract global observable, that ${ch}\bullet{ch}'$ and ${ch}'\bullet{ch}$ can be commuted in any larger chunk.

Compare also with Proposition 4.4.8, which is a similar result but for the differently-constructed abstract chunk systems.

Proposition 3.5.12 Suppose $\mathbb T=(\alpha,\beta,\textsf{Transaction},\textsf{Validator})$ is an IEUTxO model and ${ch},{ch}'\in\textsf{Chunk}_{\mathbb T}$ . Then the following are equivalent:

1. (1). ${pos}({ch})\cap{pos}({ch}')=\varnothing$

2. (2). ${ch}\bullet{ch}'\in\textsf{Chunk}_{\mathbb T} \land {ch}'\bullet{ch}\in\textsf{Chunk}_{\mathbb T}$ .

3. (3). ${ch}$ and ${ch}'$ are commuting.

Proof. The top-to-bottom implication is Lemma 3.5.6.

For the bottom-to-top implication, suppose that ${ch}\bullet{ch}',{ch}'\bullet{ch}\in\textsf{Chunk}_{\mathbb T}$ . From Lemma 3.5.10(2) we have

\begin{align*}{pos}({ch})\cap{pos}({ch}')\subseteq ({utxo}({ch})\cap{utxi}({ch}'))\cap({utxo}({ch}')\cap{utxi}({ch})) .\end{align*}

We can rearrange this:

\begin{align*}{pos}({ch})\cap{pos}({ch}')\subseteq({utxi}({ch})\cap{utxo}({ch}))\cap({utxi}({ch}')\cap{utxo}({ch}')) .\end{align*}

Now we use Lemma 3.5.10(1).

The final part is direct from Lemma 3.5.9(2).

Remark 3.5.13 Proposition 3.5.12 is a resource separation result: if two chunks depend on disjoint resources (disjoint sets of positions) then they commute. This is in the spirit of separation logic (Reynolds 2002), which is a family of logics for reasoning about programs with resource separation in programs – intuitively, that if two programs depend on disjoint resources (e.g. channels or pointers), then they should not interfere with one another, just as we see in Proposition 3.5.12.

It is also in the spirit of a short paper Nester (Reference Nester2021) (which appeared after this paper went into initial review) which uses monoidal categories to reason on resources in a broadly similar spirit, albeit using different methods. A quote from that paper makes a related point: We have seen how the resource theoretic interpretation of monoidal categories, and in particular their string diagrams, captures the sort of material history that concerns ledger structures for blockchain systems. More on this in the Conclusions.

We conclude with Lemma 3.5.14, which we will need later in Lemma 5.2.1:

Lemma 3.5.14 Suppose $\mathbb T\in\textsf{IEUTxO}$ is an IEUTxO model and $\pi\in{Perm}$ is a permutation of atoms and ${txs}\in[\textsf{Transaction}_{\mathbb T}]$ . Then:

\begin{align*}\begin{array}[t]{r@{\ }l}f(\pi{\cdot}{txs}) =&\pi{\cdot} f({txs})\\=& \{\pi(a)\mid a\in f({txs})\}\end{array}\quad\text{for}\ f\in\{{utxi},{utxo},{stx},{pos}\}\end{align*}

In the terminology of Definition 2.3.5: ${utxi}$ , ${utxo}$ , ${stx}$ , and ${pos}$ are all equivariant.

Proof. Direct from Figure 4 and Definitions 3.4.8 and 2.3.3.

3.6 An application: UTxO systems are ‘Church-Rosser’, in a suitable sense

We now come to Theorem 3.6.1 which is an application of our machinery so far:

Theorem 3.6.1 (Church-Rosser for UTxO) Suppose $\mathbb T\in\textsf{IEUTxO}$ and $y,x,x'\in\textsf{Chunk}_{\mathbb T}$ . Suppose further that

\begin{align*}y\bullet x\bullet x'\in\textsf{Chunk}_{\mathbb T}\quad\text{and}\quad{utxi}(y\bullet x') = {utxi}(y\bullet x\bullet x') .\end{align*}

Then we have that:

1. (1). x and x’ are commuting (Definition 3.5.7).

2. (2). $y\bullet x'\bullet x\in\textsf{Chunk}_{\mathbb T}$ .

Proof. We know by Corollary 3.5.2 (because $y\bullet x\bullet x'$ is a chunk) that $x\bullet x'$ is a chunk, so ${pos}(x)\cap{pos}(x')\subseteq{utxo}(x)\cap{utxi}(x')$ .

We also know that ${utxi}(y\bullet x')={utxi}(y\bullet x\bullet x')$ and it follows from Definition 3.4.8 that ( ${utxo}(y)\cap{utxi}(x)=\varnothing$ and) ${utxo}(x)\cap{utxi}(x')=\varnothing$ . ^{Footnote 25}

Therefore, ${pos}(x)\cap{pos}(x')=\varnothing$ . By Proposition 3.5.12, x and x’ are commuting, and it follows (since $y\bullet x'\bullet x\in\textsf{Chunk}_{\mathbb T}$ ) that $y\bullet x\bullet x'\in\textsf{Chunk}_{\mathbb T}$ .

Recall the definition of a blockchain (Definition 3.4.10) as being a chunk with empty ${utxi}$ . Then, we can specialise Theorem 3.6.1 as follows:

1. (1). If $y\bullet x\bullet x'$ is a blockchain then x and x’ commute.

2. (2). If x and x’ do not commute then $y\bullet x\bullet x'$ is not a blockchain.

Proof. Direct from Theorem 3.6.1, for the case that ${utxi}(y\bullet x')={utxi}(y\bullet x\bullet x')=\varnothing$ .

Then this can only happen if x and x’ are commuting; conversely, if x and x’ are not commuting then one of $y\bullet x\bullet x'$ or $y\bullet x'$ must fail to be a blockchain.

What makes this interesting is that it is an important correctness property from the point of view of the user who created x’: if x’ is accepted onto both y and $y\bullet x$ without failure, then it does not matter that x got in first – $y\bullet x\bullet x'$ and $y\bullet x'\bullet x$ are equivalent up to observable behaviour.

Note that:

• • Theorem 3.6.1 and Corollary 3.6.2 do not state that $\textsf{IEUTxO}$ systems are insensitive to order, and

• • Theorem 3.6.1 and Corollary 206.2 do not state that all transactions always commute (this is simply not what is written on the page).

Theorem 3.6.1 and Corollary 3.6.2 can be viewed as a purity property, in the sense of functional programming: if x’ successfully combines with y, then inputs to x’ may not be modified by an intervening environment x – there are no side-effects!

More specifically, these results can be viewed as playing a role analogous to a ‘Church-Rosser’ or ‘confluence’ property. To see why, contrast with the situation in an accounts-based system – corresponding to an imperative paradigm – where a transaction may be successfully appended even if parameters to it on the blockchain get modified by intervening transactions.

To take a concrete scenario: I could check my bank account, observe I have enough money for a purchase, submit my transaction – and then go into overdraft and be subject to overdraft fees, because a direct debit happened to arrive in-between (a) my checking my balance and designing my purchase transaction and (b) the payment request for the purchase transaction arriving at my account. This error clearly comes from the use of a stateful, imperative programming style and Theorem 6.1 expresses a rigorous sense in which a corresponding phenomenon is impossible in a UTxO style system. ^{Footnote 26}

With this comparison in mind, we see that Theorem 6.1 is a purity result: state is local, and composition of chunks succeeds or fails locally.

We can organise our IEUTxO models into a category:

1. (1). Objects $\mathbb S,\mathbb T$ are IEUTxO models (Definition 3.1.2).

2. (2). An arrow $f:\mathbb S\to\mathbb T$ is a map

   \begin{align*}f:\textsf{Transaction}_{\mathbb S}\to\textsf{Chunk}_{\mathbb T}\end{align*}
   such that if ${tx},{tx}'\in\textsf{Transaction}_{\mathbb S}$ then
   (2) \begin{equation}[{tx},{tx}']\in\textsf{Chunk}_{\mathbb S}\quad\text{implies}\quad f({tx})\bullet f({tx}')\in\textsf{Chunk}_{\mathbb T}.\end{equation}
   Above, $\bullet$ denotes monoid composition, which on chunks is list concatenation; see Notation 2.2.3(4).

3. (3). The identity arrow maps ${tx}$ to $[{tx}]$ .

4. (4). Composition of arrows is pointwise, meaning that if

   \begin{align*}\begin{array}{r@{\ }l@{\qquad}r@{\ }l}f:&\mathbb S\to\mathbb S'&{tx}\in&\textsf{Transaction}_{\mathbb S}\\f':&\mathbb S'\to\mathbb S''&f({tx})=&[{tx}'_1,\dots,{tx}'_n]\end{array}\end{align*}
   then $f'f :\mathbb S\to\mathbb S''$ is such that
   \begin{align*}{tx}\in\textsf{Transaction}_{\mathbb S} \longmapsto f'({tx}'_1)\bullet\ldots\bullet f'({tx}'_n)\in\textsf{Chunk}_{\mathbb S''} .\end{align*}
   We prove this mapping is indeed an arrow – thus, it maps to chunks – in Corollary 3.7.4.

Lemma 3.7.2 An arrow $f:\mathbb S\to\mathbb T$ (Definition 3.7.1(2)) induces a mapping of chunks $\textsf{Chunk}_{\mathbb S}\to\textsf{Chunk}_{\mathbb T}$ , by acting on the individual transactions and composing the results:

\begin{align*}f([{tx}_1,\dots,{tx}_n]) = f({tx}_1)\bullet \ldots\bullet f({tx}_n) .\end{align*}

Proof. The nontrivial part is to check that

• • if ${ch}=[{tx}_1,\dots,{tx}_n]$ is a valid chunk in $\textsf{Chunk}_{\mathbb S}$ ,

• • then $f({tx}_1)\bullet\ldots\bullet f({tx}_n)$ is a valid chunk in $\textsf{Chunk}_{\mathbb T}$ .

This follows by combining condition 2 of Definition 3.7.1 with Lemma 3.5.1 and Corollary 3.5.2.

1. (1). $[{tx}_1,\dots,{tx}_n]\in\textsf{Chunk}_{\mathbb S}$ implies $f({tx}_1)\bullet\ldots f({tx}_n)\in\textsf{Chunk}_{\mathbb T}$ .

2. (2). f induces a monoid homomorphism on chunks.

Proof. The equivalence of conditions 1 and 2 above is routine, given that every chunk factors into singletons. Then, condition (2) in part 2 of Definition 3.7.1 is just a special case of condition 1 above, and the reverse implication is Lemma 3.7.2.

Proof. Continuing the notation of Definition 3.7.1(4), by assumption f maps ${tx}\in\textsf{Transaction}_{\mathbb S}$ to some $f({tx})\in\textsf{Chunk}_{\mathbb S'}$ , and then by Lemma 3.7.2 the action of f’ maps $f({tx})$ to a valid chunk $f'(f({tx}))\in\textsf{Chunk}_{\mathbb S''}$ .

1. (1). The conditions in Corollary 3.7.3 are more readable than condition (2) of Definition 3.7.1(2), but this comes at the cost of an additional universally quantified parameter n. It is a matter of taste which version we take as primitive: the one in the Definition has fewest parameters and is easiest to check (a higher-level view will be taken later when we develop abstract chunk systems in Section 4).

2. (2). We could relax the condition to allow f to be a partial map. This would exhibit $\textsf{IEUTxO}$ as a subcategory of a larger category with the same objects but more arrows, and in particular, it would allow chunks in $\mathbb S$ to cease to be valid when mapped to $\mathbb T$ – we would still insist that f be a partial monoid homomorphism on chunks, where everything is defined. We did not choose this design for this paper, but it might be useful for future work; for example following an intuition that $\mathbb S$ is a liberal universe of chunks, and f maps it to a stricter universe $\mathbb T$ in which additional restrictions are appended to validators. Thus, chunks in the liberal world might cease to be valid in the stricter universe.

3. (3). We could also restrict f further so that $f:\textsf{Transaction}_{\mathbb S}\to\textsf{Transaction}_{\mathbb T}$ . This would yield fewer arrows, and we prefer to allow the flexibility of mapping a single transaction in $\mathbb S$ to a chunk of transactions in $\mathbb T,$ following an intuition that $\mathbb S$ is a coarse-grained representation which f maps into a finely grained representation where something that was considered a single transaction is now a chunk.

3.8 Idealised UTxO

One special case of IEUTxO deserves its own discussion:

Remark 3.8.1 ((Idealised UTxO)) Recall from Figure 1 that validators take as input a pointed transaction:

\begin{align*}\textsf{Transaction}_!\subseteq {fin}_!(\textsf{Input})\times{fin}(\textsf{Output}) .\end{align*}

Recall also from Notation 2.2.3(2) and that a pointed transaction is a transaction with one distinguished input of that transaction. For convenience, we will call this the input-point of the transaction.

The UTxO model – on which Bitcoin is based – is the special case of EUTxO where validators just examine the input-point. So intuitively, in the UTxO model a validator of an output sees just the input that points to that output, in the sense of Notation 3.1.3, and it does not pay any attention to the transaction in which that input occurs.

We therefore obtain an Idealised UTxO (IUTxO) model from Figure 1 just by changing the line for validators to:

\begin{align*}\textsf{Validator} \subseteq {pow}(\beta\times\textsf{Input}) .\end{align*}

There is an easy embedding map which we can write 1, taking an IUTxO model to an IEUTxO model, derived from the embedding

\begin{align*}{pow}(\beta\times\textsf{Input}) \longrightarrow{pow}(\beta\times\textsf{Transaction}_!)\end{align*}

which is itself derived from the projection taking a pointed transaction to its input-point:

\begin{align*}\textsf{Transaction}_! \longrightarrow\textsf{Input} .\end{align*}

Then we can define a category of IUTxO models such that

• • objects are IUTxO models, and

• • arrows are functions exactly as defined in Definition 3.7.1.

Proof. Direct from the construction, since an $\textsf{IUTxO}$ model is identified with an $\textsf{IEUTxO}$ model whose validators ignore the transaction and just look at the input-point.

4.1 Basic definitions

However, IEUTxOs are concrete. An IEUTxO model is full of internal structure, by its very construction as a solution to type equations in Figure 1. We will now set about developing an axiomatic, algebraic account of the essential features that make IEUTxOs interesting.

We recall some basic definitions:

1. (1). $\leq$ is a partial order (reflexive, transitive, anti-symmetric), and

2. (2). $\leq$ is well-founded (every descending chain is eventually stationary). ^{Footnote 28} As per Notation 3.1.5, $\textsf X$ and $\leq$ are also assumed equivariant.

• • $(\mathbb Z,\leq)$ is not well-founded.

• • $({pow}({\mathbb A}),\subseteq)$ and $({fin}({\mathbb A}),\subseteq)$ are well-founded.

• • $[\mathbb N]$ (lists of numbers) with sublist inclusion is well-founded.

1. (1). $\textsf{e}\lneq x\lneq \textsf{f}$ and

2. (2). for every $x'\in\textsf X$ if $x'\leq x$ then either $x'=\textsf{e}$ or $x'=x$ . Write ${atomic}(\textsf X)$ for the set of atomic elements of $\textsf X$ (see also Definition 4.2.5).

If we call $x\in\textsf X$ proper when it is neither $\textsf{e}$ nor $\textsf{f}$ (following the standard terminology of proper subset), then an atomic element is “a minimal proper element”.

Lemma 4.1.6 will be useful later:

Then the atomic elements in $(\textsf{Chunk}_{\mathbb T},\leq)$ are precisely the singleton chunks (Notation 3.4.3).

Proof. Using Corollary 3.5.2.

4.2 Monoid of chunks

• • $\textsf X$ is a set.

• • $\textsf{e},\textsf{f}\in\textsf X$ are called unit and fail respectively.

• • ${\leq} \subseteq\textsf X^2$ is a relation.

• • $\bullet : \textsf X^2\to\textsf X$ is a composition.

Call $(\textsf X,\textsf{e},\textsf{f},\leq,\bullet)$ a monoid of chunks when:

1. (1). $\textsf{e}\bullet x=x=x\bullet \textsf{e}$ .

2. (2). $\textsf{f}\bullet x=\textsf{f}=x\bullet\textsf{f}$ .

3. (3). $\leq$ is a well-ordering for which the unit $\textsf{e}$ is a bottom element and the paradoxical element $\textsf{f}$ is a top element.

4. (4). Composition $\bullet$ is associative, and monotone in both components, meaning that

   \begin{align*}\begin{array}{r@{\ }l@{\quad\text{implies}\quad}r@{\ }l}x'\leq& x & x'\bullet y\leq& x\bullet y\quad\text{and}\\y\leq& y' & x\bullet y\leq& x\bullet y'.\end{array}\end{align*}

5. (5). Composition is increasing in the sense that

   \begin{align*}x\leq x\bullet y\quad\text{and}\quad y\leq x\bullet y.\end{align*}

6. (6). If $x_1,\dots,x_n\in\textsf X$ and $x_1\bullet \ldots\bullet x_n=\textsf{f}$ , then there must exist $1\leq i< j\leq n$ such that $x_i\bullet x_j=\textsf{f}$ .

1. (1). This is a clearly an abstraction of IEUTxO structure, where $\bullet$ is chunk composition and $\leq$ is list inclusion (proof in Proposition 5.1.3). This is the key instance of the axioms that motivates the definition – IEUTxOs have more structure, but monoids of chunks is where we start. See also Example 4.2.6(6).

2. (2). $x\bullet y$ is not necessarily a least upper bound for $\{x,y\}$ . Take $X=\{1,2\}$ and $x=[1]$ and $y=[2]$ in Example 4.2.6(4) (finite lists with a top element). Then $x\bullet y$ and $y\bullet x$ are distinct and incomparable, so both are upper bounds for $\{x,y\}$ but $x\bullet y\not\leq y\bullet x$ and $y\bullet x\not\leq x\bullet y$ .

3. (3). We see that condition 6 of Definition 4.2.1 closely resembles Lemma 3.5.1, and indeed, the condition is inspired by that very Lemma. We will use this in Proposition 5.1.3.

Notation 4.2.3 As is standard, we may write $\textsf X$ for both a monoid of chunks and its carrier set. See for instance the first line of Definition 4.2.4.

1. (1). If $x\in \textsf X$ and $[x_1,\dots,x_n]\in[{atomic}(\textsf X)]$ is a finite list of atomic elements^{Footnote 29} in $\textsf X$ and

   \begin{align*}x = x_1\bullet\ldots\bullet x_n\quad\text{then say that}\quad\text{{x} \textbf{factorises} as $[x_1,\dots,x_n]$.}\end{align*}

2. (2). Say that $\textsf X$ is generated by its atomic elements when every $x\in\textsf X\setminus\{\textsf{f}\}$ has a (possibly non-unique) factorisation into atomic elements.

1. 1. ${pow}(X)$ forms a monoid of chunks, where $\textsf{e}=\varnothing$ and $\textsf{f}=X$ , and $\leq$ is subset inclusion, and composition $\bullet$ is sets union. It is atomic if and only if X is finite (recall: factorisations must be finite). We obtain a factorisation function by choosing any order on X, and listing elements of any $X'\subseteq X$ in order.

2. 2. ${pow}(X)$ forms a monoid of chunks, where:

3. − $\textsf{e}=\varnothing$ and $\textsf{f}=X$ .

4. − $\leq$ is subset inclusion.

5. − $x\bullet y=x\cup y$ if $x\cap y=\varnothing$ , and $x\bullet y=\textsf{f}$ otherwise. It is atomic if and only if X is finite.

6. (3). ${fin}(X)\cup \{X\}$ (finite sets of atoms, with a top element) forms an atomic monoid of chunks, using either of the two definitions above for ${pow}(X)$ .

7. (4). Finite lists with a top element $[X]^\top$ – meaning finite lists of elements from X, plus one extra ‘top’ element $\top$ – form a perfectly atomic monoid of chunks as follows:

8. − $\textsf{e} = []$ and $\textsf{f} = \top$ .

9. − $\leq$ is sublist inclusion (Notation 2.2.3(5)) and $l\leq\textsf{f}$ for every finite list l.

10. − Composition $\bullet$ is list concatenation on lists, and $x\bullet \textsf{f} = \textsf{f} = \textsf{f}\bullet x$ for any x (list, or $\textsf{f}$ ).

11. (5) Finite lists with a top element $[X]^\top$ form an atomic (but not perfectly atomic) monoid of chunks as above, where $\leq$ and $\bullet$ are defined as follows:

12. − $l\leq l'$ holds when l is not a singleton list and l is a sublist of l’.So $[]\leq [x]$ and $[]\leq [x,z]\leq [x,y,z]$ but $[x]\not\leq [x,y]$ ; and the proper atomic elements are singleton and two-element lists.

13. − $[]\bullet l = l\bullet [] = l$ for any list.

14. − $\textsf{f}\bullet x = \textsf{f} = x\bullet\textsf{f}$ for any x.

15. − If l and l’ are nonempty lists, then $l\bullet l'$ is $l_{init}$ concatenated with $l'_{tail}$ , where $l_{init}$ is everything except for the last element of l, and $l'_{tail}$ is everything except for the first element of l’.

16. (6) As touched on above, if $\mathbb T$ is an IEUTxO model then $\mathbb T$ gives rise to a perfectly atomic monoid of chunks. See Proposition 5.1.3.

We have a concrete reason for this: our canonical IEUTxO models are based on lists ordered by sublist inclusion, so bottom is already occupied by the empty list [] which plays the role of $\textsf{e}$ (see Definition 5.1.1).

But also we have abstract justifications: if we think of a chunk system as a many-valued logic (in which truth-values are chunks or blockchains and $\leq$ reflects how they accumulate transactions over time), then to exhibit a $\top$ is to fail to exhibit a concrete witness. Or (thinking perhaps of callCC Clinger et al. Reference Clinger, Friedman and Wand1986) we can think of $\textsf{f}$ as a ‘final’ or ‘escape’ element.

4.3 Behaviour, positions and equivalence

4.3.1 Left and right behaviour

Definition 4.3.1 Suppose $\textsf X=(\textsf X,\textsf{e},\textsf{f},\leq,\bullet)$ is a monoid of chunks. Then we have natural left- and right-behaviour functions:

\begin{align*}\begin{array}{l@{\ }c@{\ }l@{\qquad}l@{\ }c@{\ }l}{leftB}:\textsf X&\to& {pow}(\textsf X)&{rightB}:\textsf X&\to& {pow}(\textsf X)\\{leftB}: x &\mapsto&\{y{\in}\textsf X \mid y\bullet x<\textsf{f}\}&{rightB}:x &\mapsto&\{y{\in}\textsf X \mid x\bullet y<\textsf{f}\}\end{array}\end{align*}

Lemma 4.3.2 Suppose $\textsf X$ is a monoid of chunks. Then we have:

1. (1). ${leftB}(\textsf{e})={rightB}(\textsf{e})=\textsf X\setminus\{\textsf{f}\}$ .

2. (2). ${leftB}(\textsf{f})={rightB}(\textsf{f})=\varnothing$ .

Proof. A fact of Definition 4.2.1(1&2).

Remark 4.3.3 If we think of $\textsf{f}$ as a failure element, and we think of $x\bullet y$ as being a composition of which we can observe whether it fails or succeeds, then

• • ${rightB}$ maps $x\in\textsf X$ to its right-observational behaviour, and

• • ${leftB}$ maps $x\in\textsf X$ to its left-observational behaviour.

Remark 4.3.4 Parallels can be made in Definition 3.1 with the $\lambda$ -calculus (Barendregt 1984) and the $\pi$ -calculus (Milner 1999):

1. (1). In the $\lambda$ -calculus, a standard observable is non-termination. Here we are doing something similar, except that (as noted in Remark 4.3.3) instead of failure to terminate ( $\bot$ ) we observe failure to compose ( $\textsf{f}$ ), and we consider combination both to the left and to the right. Continuing the analogy, in the untyped $\lambda$ -calculus, the left-behaviour set of a term t would be those s such that st terminates; and the right-behaviour set of t would be those s such that ts terminates.

2. (2). The $\pi$ -calculus has notions of communications across channels, and as noted in Remark 3.4.4, we see a resemblance with communication of an input and output on a position. However there are differences, including:

3. a. Validation is not primitive in the $\pi$ -calculus but it is a core precept here.

4. b. Communication in the plain $\pi$ -calculus (without considering dialects) is non-deterministic – one channel name can be invoked by multiple inputs and outputs – whereas here a key assumption is that every channel name (i.e. position) must have one input and one output – and if not, the chunk collapses to a failure error-state $\textsf{f}$ (cf. the conditions in Definitions 3.4.1 and 3.4.10).

5. c. Name restriction in the $\pi$ -calculus is not automatic but instead is managed by an explicit restriction term-former. In contrast here, a communicating channel (an output-input pair) automatically closes when used once. We say ‘closed’ and not ‘bound’ because the name remains visible in ${up}$ (see also ${stx}$ in the IEUTxO models); it is just that no further communication may occur along it. We discuss garbage-collecting names in chunks in Subsection 8.2.

Remark 4.3.5 Definitions 4.3.6 and 4.3.9 will build on Definitions 4.2.1 and 4.3.1 to derive a full notion of an observable interface of a monoid element, all derived just from the partiality of composition. We will make good use of this in the rest of the development, for instance Definition 6.2.1 depends on it.

4.3.2 Positions

Definition 4.3.6 Suppose $\textsf X$ is a monoid of chunks. Define ${posi}(x)\subseteq{\mathbb A}$ the positions of $x\in\textsf X$ as follows:

\begin{align*}\begin{array}{r@{\ }l}{posi}(\textsf{f}_{\textsf X})=&\varnothing\\{posi}(x)=&\{a\in{\mathbb A} \mid \forall{\pi{\in}{fix}(a)}\pi{\cdot} x\not\in{leftB}(x)\cup{rightB}(x) \}\quad (x\in\textsf X\setminus\{\textsf{f}_{\textsf X}\}).\end{array}\end{align*}

( ${fix}(a)$ from Definition 2.3.4.)

Thus, $a\in{posi}(x)$ when $x\neq\textsf{f}_{\textsf X}$ and $\pi{\cdot} x\not\in{leftB}(x)\cup{rightB}(x)$ , for any $\pi$ such that $\pi(a)=a$ .

Remark 4.3.7 Note that the ${\cdot}$ in $\pi{\cdot} x$ in Definition 4.3.6 above refers to the atoms-permutation action from Definition 2.3.2, not to the partial monoid action $\bullet$ from Definition 3.5.3.

Remark 4.3.8 In words, ${posi}(x)$ from Definition 4.3.6 is those atoms such that there is no permutation fixing a such that $\pi{\cdot} x$ can be successfully combined (left or right) with x.

What is the intuition here?

The name ${posi}$ reminds us of ${pos}$ from Definition 3.2.3, though the definitions are quite different. They are indeed related; in fact, they are equal in a sense made formal in Proposition 5.2.2 (see also Lemma 6.3.2(2)).

We do not have all the machinery in place yet, so it may be helpful to point forwards here and observe that conditions 3 and 4 of Definition 4.4.1 can be read as a way to make name-clash into an observable.

So intuitively, Definition 4.3.6 – once combined with the notion of an oriented monoid from Definition 4.4.1 – can use permutations to observe name-clash: it measures the live communication channels $a\in{\mathbb A}$ in an element x by forcing name-clashes between a-channels with $\pi$ -renamed variants $\pi{\cdot} x$ for $\pi\in{fix}(a)$ . More details will follow, and see Remark 5.2.3.

Definition 4.3.9 Suppose $\textsf X=(\textsf X,\textsf{e},\textsf{f},\leq,\bullet)$ is a monoid of chunks, and suppose $x\in \textsf X$ and $a\in{\mathbb A}$ .

1. (1). If

   \begin{align*}a\in{posi}(x)\quad\text{and}\quad\exists{y{\in}{leftB}(x)}a\in{posi}(y),\end{align*}
   then say that a points left in x. Write ${left}(x)\subseteq{\mathbb A}$ for the set of atoms that point left in x.

2. (2). If

   \begin{align*}a\in{posi}(x)\quad\text{and}\quad\exists{y{\in}{rightB}(x)}a\in{posi}(y),\end{align*}
   then say that a points right in x. Write ${right}(x)\subseteq{\mathbb A}$ for the set of atoms that point right in x.

3. (3). If a points neither left nor right in a and yet $a\in{posi}(x)$ , so that

   \begin{align*}a\in{posi}(x)\quad\text{and}\quad\forall{y{\in}{leftB}(x)\cup{rightB}(x)}a\not\in{posi}(y),\end{align*}
   then say that a points up in x. Write ${up}(x)\subseteq{\mathbb A}$ for the set of atoms that point up in x.

Lemma 4.3.10 expresses intuitively that atoms that point ‘up’ in a transaction cannot engage in successful (non-failing) combination; they are ‘stuck interfaces’:

Lemma 4.3.10 Suppose $\textsf X$ is a monoid of chunks and $x,y\in\textsf X$ and $a\in{up}(x)$ . Then

\begin{align*}a\in{posi}(y)\quad\text{implies}\quad x\bullet y=y\bullet x=\textsf{f}.\end{align*}

Proof. Direct from Definition 4.3.9(3).

Remark 4.3.11 The reader who sees similarities between the ${left}$ , ${right}$ and ${up}$ of Definition 4.3.9, and the ${utxi}$ , ${utxo}$ and ${stx}$ of Definition 3.4.8 is right: see Proposition 5.2.2, Lemma 5.3.1, and Proposition 5.5.4.

A simple lemma will be helpful:

Lemma 4.3.12 Suppose $\textsf X$ is a monoid of chunks and $x\in\textsf X$ . Then:

\begin{align*}\begin{array}{r@{\ }l}{up}(x)=&{posi}(x)\setminus({left}(x)\cup{right}(x))\\\varnothing=&{left}(x)\cap{up}(x)\\\varnothing=&{right}(x)\cap{up}(x)\\{posi}(x)=&{left}(x)\cup{right}(x)\cup{up}(x)\end{array}\end{align*}

Proof. This just rephrases clause 3 of Definition 4.3.9.

Remark 4.3.13 Lemmas 4.3.12 and 3.5.10(3) are similar but note that the status of the underlying data types is somewhat different:

• • A chunk ${ch}\in\textsf{Chunk}$ of an IEUTxO model is full of internal structure, and operations on it are defined in terms of that structure, whereas

• • an element $x\in\textsf X$ in a monoid of chunks is an abstract entity and we assume nothing about its internal structure.

Thus, a similarity between them has significance: it is a sanity check on our model and indicates that something rather abstract (monoids of chunks) is accurately following the behaviour of something more concrete (IEUTxO models).

Remark 4.3.14 Lemma 4.3.12 expresses that every position in some $x\in\textsf X$ (Definition 4.3.6) must point in a direction in $\{{left},{right},{up}\}$ , and it cannot point both left and up, or both right and up.

Note that Definition 4.3.9 admits a possibility that an atom could point both left and right; this cannot happen in the IEUTxO models (see Lemma 3.5.10(1)). We will exclude this when we introduce the notion of an oriented monoid of chunks; see Corollary 4.4.5.

Lemma 4.3.15

1. (1). ${left}(\textsf{e})={right}(\textsf{e})={up}(\textsf{e})=\varnothing$ .

2. (2). ${left}(\textsf{f})={right}(\textsf{f})={up}(\textsf{f})=\varnothing$ .

3. (3). As a corollary using Lemma 4.3.12, ${posi}(\textsf{e})={posi}(\textsf{f})=\varnothing$ .^{Footnote 30}

Proof. We check the behaviour of $\textsf{e}$ and $\textsf{f}$ as specified in Definition 4.2.1 against the definitions of ${left}$ , ${right}$ , and ${up}$ in Definition 4.3.9 and see that this is true.

4.3.3 Observational equivalence

Definition 4.3.16 Suppose $\textsf X$ is a monoid of chunks.

1. (1). Call x and x’ in $\textsf X$ observationally equivalent and write

   \begin{align*}x\sim x'\quad\text{when}\quad{leftB}(x)={leftB}(x')\land {rightB}(x)={rightB}(x') .\end{align*}

2. (2). Say that x and y commute (up to observational equivalence) when

   \begin{align*}x\bullet y\sim y\bullet x .\end{align*}

We start with a simple but useful sanity check:

Lemma 4.3.17 Suppose $\textsf X$ is a monoid of chunks and $x,y\in\textsf X$ . Then if x and y commute then

\begin{align*}x\bullet y<\textsf{f} \Longleftrightarrow y\bullet x<\textsf{f}\quad\text{and}\quad x \bullet y=\textsf{f} \Longleftrightarrow y\bullet x=\textsf{f} .\end{align*}

Proof. We unpack Definitions 4.3.16(1&2) and 4.3.1 and conclude that

\begin{align*}x\bullet y\bullet\textsf{e} <\textsf{f} \Longleftrightarrow y\bullet x\bullet\textsf{e} <\textsf{f} .\end{align*}

The result follows, since $\textsf{e}$ is the unit for $\bullet$ .

Lemma 4.3.18 Suppose $\textsf X$ is a monoid of chunks. Then if $x\sim x'$ (Definition 4.3.16) then

\begin{align*}{left}(x)={left}(x')\quad\text{and}\quad{right}(x)={right}(x')\quad\text{and}\quad{up}(x)={up}(x').\end{align*}

Proof. A fact of Definitions 4.3.16(1) and 4.3.9.

4.4 Oriented monoids

4.4.1 Definition and properties

Definition 4.4.1 Suppose $\textsf X=(\textsf X,\textsf{e},\textsf{f},\leq,\bullet)$ is a monoid of chunks.

Call $\textsf X$ oriented when for all $x,y\in\textsf X$ :

1. (1). ${posi}(x)\mathbin{\subseteq_{\text{\it fin}}}{\mathbb A}$ .

2. (2). If ${posi}(x)=\varnothing$ then $x\in\{\textsf{e},\textsf{f}\}$ .

3. (3). If ${left}(x)\cap{right}(y)\neq\varnothing$ then $x\bullet y=\textsf{f}$ .

4. (4). If ${posi}(x)\cap{posi}(y)=\varnothing$ then x and y commute up to observational equivalence (Definition 4.3.16(2)).

5. (5). If ${posi}(x)\cap{posi}(y)=\varnothing$ and $\textsf{f}\not\in\{x,y\}$ then $x\bullet y<\textsf{f}$ .

Remark 4.4.2 We discuss the conditions of Definition 4.4.1 in turn:

1. (1). An element $x\in\textsf X$ can only be accessible on finitely many channel interfaces.

2. (2). The only elements without any interface (meaning atoms that point left right or up) are the unit element ( $\leq$ -bottom) and the failure element ( $\leq$ -top). Compare with the IEUTxO property Lemma 3.2.5. We use this in Lemmas 4.4.6 and 6.3.1.

3. (3). Interfaces always try to connect, but can only successfully connect if the directions of their interfaces match up; if not, the whole combination fails. We use this in Lemma 4.4.6, which is required for Proposition 4.4.8.

4. (4). This condition echoes Lemma 3.5.9(2). We use it in Proposition 4.4.8.

5. (5). Elements with no channels in common, cannot fail to compose.

We will show later that the IEUTxO models from Definition 3.1.9 are models of Definition 4.4.1 in a suitable sense; see Proposition 5.3.3.

We can strengthen Definition 4.4.1(2) to a logical equivalence:

Lemma 4.4.3 Suppose $\textsf X$ is an oriented monoid of chunks and $x\in\textsf X$ . Then

\begin{align*}{posi}(x)=\varnothing\quad\text{if and only if}\quad x\in\{\textsf{e},\textsf{f}\} .\end{align*}

Proof. The right-to-left implication is direct from Definition 4.4.1(2). The left-to-right implication is Lemma 4.3.15.

Lemma 4.4.4 is a nice way to repackage Definition 4.4.1(2) in a slightly more accessible wrapper. In its form it resembles Lemma 4.5.10(2), and we use it for Corollary 4.4.5:

Lemma 4.4.4 Suppose $\textsf X$ is an oriented monoid of chunks and suppose $x,y\in\textsf X$ . Then

\begin{align*}x\bullet y<\textsf{f}\quad\text{implies}\quad{posi}(x)\cap{posi}(y)\subseteq{right}(x)\cap{left}(y).\end{align*}

Proof. We consider the possibilities, using Lemma 4.3.12:

• • Suppose $a\in{left}(x)\cap{posi}(y)$ . From Definition 4.4.1(3) $a\not\in{right}(x)$ , and by Lemma 4.3.12 $a\in{posi}(x)$ . It follows from Definition 4.3.9(2) that $x\bullet y=\textsf{f}$ .

• • Suppose $a\in{right}(y)\cap{posi}(x)$ . From Definition 4.4.1(3) $a\not\in{left}(y)$ , and by Lemma 4.3.12 $a\in{posi}(y)$ . It follows from Definition 4.3.9(1) that $x\bullet y=\textsf{f}$ .

• • Other cases are from Lemma 4.3.10 (or by direct reasoning from Definition 4.3.9(3)).

Corollary 4.4.5 is a slightly magical result, in the sense that it is perhaps not immediately obvious that it should follow from our definitions so far. In its form, if not its proof, it clearly resembles Lemma 3.5.10(1). We need it for Lemma 6.2.5, that atomic elements in $\textsf X$ generate valid singleton chunks under a mapping to IEUTxO models F:

Corollary 4.4.5 Suppose $\textsf X$ is an oriented monoid of chunks and $x\in\textsf X$ . Then:^{Footnote 31}

\begin{align*}{left}(x)\cap{right}(x)=\varnothing .\end{align*}

Proof. Suppose $a\in{left}(x)$ , we will show that $a\in{right}(x)$ is impossible. Consider some $y\in\textsf X$ with $a\in{posi}(y)$ , so that by Lemma 4.3.12 $a\in{left}(y)\cup{right}(y)\cup{up}(y)$ . Then:

• • If $a\in{left}(y)$ then $a\in{left}(x)\cap{left}(y)$ and by Lemma 4.4.4 $x\bullet y=\textsf{f}$ .

• • If $a\in{right}(y)$ then $a\in{left}(x)\cap{right}(y)$ and by Lemma 4.4.4 $x\bullet y=\textsf{f}$ .

• • If $a\in{up}(y)$ then $a\in{left}(x)\cap{up}(y)$ and by Lemma 4.4.4 $x\bullet y=\textsf{f}$ .

Thus, $a\in{posi}(y)$ implies $x\bullet y=\textsf{f}$ and so $y\not\in{rightB}(x)$ . It follows from Definition 4.3.9(2) that $a\not\in{right}(x)$ as required.

We use Lemma 4.4.6 for Proposition 4.4.8:

Lemma 4.4.6 Suppose $\textsf X=(\textsf X,\textsf{e},\textsf{f},\leq,\bullet)$ is an oriented monoid of chunks. Then at least one of the following must hold:

\begin{align*}x\bullet y=\textsf{f}\qquad y\bullet x=\textsf{f}\qquad{posi}(x)\cap{posi}(y)=\varnothing\end{align*}

Proof. If x or y are equal to $\textsf{e}$ or $\textsf{f}$ then ${posi}(x)\cap{posi}(y)=\varnothing$ is immediate from Lemma 4.3.

So suppose $x,y\not\in\{\textsf{e},\textsf{f}\}$ , from which it follows by Lemma 4.4.3 (or direct from Definition 4.4.1(2)) that ${posi}(x)\neq\varnothing$ and ${posi}(y)\neq\varnothing$ . Suppose we have some $a\in{posi}(x)\cap{posi}(y)$ . We reason by cases using our assumption that $\textsf X$ is oriented (Definition 4.4.1):

• • If $a\in{left}(x)\cap{right}(y)$ then $x\bullet y=\textsf{f}$ by Definition 4.4.1(3).

• • If $a\in{right}(x)\cap{left}(y)$ then $y\bullet x=\textsf{f}$ by Definition 4.4.1(3).

• • If $a\in{up}(x)$ or $a\in{up}(y)$ then $x\bullet y=y\bullet x=\textsf{f}$ by Lemma 4.3.10.

• • Other cases are no harder.

Remark 4.4.7 Proposition 4.4.8 is a partial converse to Definition 4.4.1(4) (compare also with Proposition 3.5.12, which is the same result but for a different structure, and with a very different proof). It is significant because it equates

• • a static property of positions, with

• • a local property of being combinable in either order, with

• • a global operational property of being commutative up to observation. Commutativity is of particular interest in the context of blockchains, because they are by design intended to be distributed, so that we cannot in general know or assume in what order transactions get appended.

Proposition 4.4.8 Suppose $\textsf X=(\textsf X,\textsf{e},\textsf{f},\leq,\bullet)$ is an oriented monoid of chunks, and $x,y\in\textsf X$ . Suppose further that $x\bullet y<\textsf{f}$ or $y\bullet x<\textsf{f}$ (not necessarily both). Then, the following conditions are equivalent:

1. (1). ${posi}(x)\cap{posi}(y)=\varnothing$ .

2. (2). $x\bullet y<\textsf{f} \land y\bullet x<\textsf{f}$ .

3. (3). x and y commute up to observational equivalence (Definition 4.3.16(2)).

Proof. First, note that since $x\bullet y<\textsf{f}$ or $y\bullet x<\textsf{f}$ , it must from Definition 4.2.1(1) be the case that $x<\textsf{f}$ and $y<\textsf{f}$ .

If $x\bullet y<\textsf{f}\land y\bullet x<\textsf{f}$ then ${posi}(x)\cap{posi}(y)=\varnothing$ by Lemma 4.4.6. Conversely if ${posi}(x)\cap{posi}(y)=\varnothing$ then (since $x<\textsf{f}$ and $y<\textsf{f}$ ) by Definition 4.4.1(5) $x\bullet y<\textsf{f}$ and $y\bullet x<\textsf{f}$ .

If ${posi}(x)\cap{posi}(y)=\varnothing$ then x and y commute by Definition 4.4.1(4). Conversely, if ${posi}(x)\cap{posi}(y)\neq\varnothing$ then by Lemma 4.4.6 (since $x\bullet y<\textsf{f}$ or $y\bullet x<\textsf{f}$ ) we have that $y\bullet x=\textsf{f}$ or $x\bullet y=\textsf{f},$ respectively, and in particular, we have that $x\bullet y\neq y\bullet x$ . Using Lemma 4.3.17 we conclude that x and y do not commute.

Remark 4.4.9 ((Comment on design)) There is design freedom to Definition 4.1, and we mention this briefly for future work. One plausible condition is:

\begin{align*}{up}(x\bullet y)\subseteq{up}(x)\cup{up}(y)\cup({right}(x)\cap{left}(y)).\end{align*}

Intuitively, this states that combining x and y can only bind positions that point right in x and point left in y. An even stricter variant would be to insist on equality provided that $x\bullet y\neq\textsf{f}$ .

4.5 The category $\textsf{ACS}$ of abstract chunk systems

We are now ready to give the algebraic account of IEUTxOs promised in Remark 4.1.1: ^{Footnote 32}

1. (1). Objects are abstract chunk systems (Definition 4.5.1).

2. (2). Arrows $g:\textsf X\to\textsf Y$ are sets functions from $\textsf X$ to $\textsf Y$ such that:

   1. a. $g(\textsf{e}_{\textsf X})=\textsf{e}_{\textsf Y}$ and $g(\textsf{f}_{\textsf X})=\textsf{f}_{\textsf Y}$

   2. b. $x\leq y<\textsf{f}_{\textsf X}$ implies $g(x)\leq g(y)<\textsf{f}_{\textsf Y}$

   3. c. $g(x)\bullet g(y)= g(x\bullet y)$

Composition of arrows is composition of functions, and the identity arrow is the identity function.

1. (1). We do not insist in Definition 4.5.2 that g(x) must be atomic if x is. This corresponds to our choice in Definition 4.7.1(2) to let f map from transactions to chunks, and not from transactions to transactions.

2. (2). We do insist in Definition 4.5.2(2) that if x is not the failure element $\textsf{f}_{\textsf X}$ in $\textsf X$ then g(x) is also not the failure element $\textsf{f}_{\textsf Y}$ in $\textsf Y$ . This corresponds to our choice in Definition 3.7.1(2) to make f a total function from transactions to chunks, rather than a partial one (cf. discussion in Remark 3.7.5(2)).

We could relax this condition by allowing g to map $x<\textsf{f}_{\textsf X}$ to $\textsf{f}_{\textsf Y}$ . There would be nothing wrong with this, and it would just exhibit $\textsf{ACS}$ as embedded in a larger category with the same objects but more arrows.

Lemma 4.5.4 just repackages Definition 4.2.5 for objects in $\textsf{ACS}$ :

• • If $x\neq\textsf{f}$ then there exists some finite (possibly empty, possibly non-unique) list of atomic elements $x_1,\dots,x_n\in {atomic}(\textsf X)$ such that $x=x_1\bullet\ldots\bullet x_n$ .

• • If $x\neq\textsf{f}$ (and in particular by Definition 4.1.4(1) if x is atomic) then there exists some finite (possibly empty, possibly non-unique) list of atomic elements $y_1,\dots,y_n\in {atomic}(\textsf Y)$ such that $g(x)=y_1\bullet\ldots\bullet y_n$ .

Proof. Immediate since by Definition 4.5.1 $\textsf X$ is atomic (Definition 4.2.5).

Proof.

1. (1). Consider some $x\in\textsf X$ . If $x\in\{\textsf{f},\textsf{e}\}$ then the action of f is determined by Definition 4.5.2(2a).Otherwise, using Lemma 4.5.4 write $x=x_1\bullet \dots \bullet x_n$ for atomic $x_1,\dots,x_n\in {atomic}(\textsf X)$ . We then have from Definition 4.5.2(2c) that

   \begin{align*}f(x_1)\bullet\ldots\bullet g(x_n)= g(x).\end{align*}
   Thus g(x) is determined by the values of $g(x_1)$ , …., $g(x_n)$ .

2. (2). By a routine argument from Definition 4.2.5 (since $\textsf X$ is atomic) and Definition 4.5.2(2c).

4.6 Examples of abstract chunk systems

We created abstract chunk systems in (Definition 4.5.1) to abstract away the internal structure of IEUTxO models (Definition 3.1.2).

This is a standard move in mathematics: axiomatise, then generalise. As we argued in Subsections 1.1 and 4.4.2, even if the reader only cares about practical hands-on implementation, for which internal structure is available because we have the code, it is still useful – and arguably indispensable – to take a moment to get a good higher-view of what it is that is implemented, since axioms provide a language for the higher-level enterprises of comparison, description, specification, correctness, testing and exposition.

Now we take a moment to go back and consider what the space of concrete models of the ACS axioms looks like. We give a list of examples, which is not intended to be exhaustive but which we hope may illustrate the scope, character, and structure of our definition:

1. (1). Consider the set of all finite sets of atoms $A=\{a_1,\dots,a_n\}\mathbin{\subseteq_{\text{\it fin}}}\mathbb A$ and ${\mathbb A}$ itself:

   \begin{align*}\textsf X={fin}({\mathbb A})\cup\{{\mathbb A}\} .\end{align*}
   $\textsf X$ forms an ACS such that

2. − $A\leq B$ when $A\subseteq B$ .

3. − $A\bullet B=A\uplus B$ (disjoint union) if A and B are disjoint, and $A\bullet B=\mathbb A$ otherwise. Unpacking definitions, we can check that:

4. − Atomic elements are singletons $\{a\}$ .

5. − A factorisation function ${factor}$ (Definition 4.2.5(1b)) is obtained by ordering atoms and listing the finite set in order.

6. − ${posi}(A)={up}(A)=A$ and ${left}(A)={right}(A)=\varnothing$ .

7. (2). Consider some data type $\textsf{Terms}$ of term syntax over variable symbols $a,b,c,\dots$ (terms of first-order logic $s,t::= a \mid f(t,\dots,t)$ for some term-formers f, or terms of the untyped $\lambda$ -calculus $s,t::=a \mid ss\mid\lambda a.s$ would suffice). Let finite substitutions be finite partial maps from variable symbols to terms generated by atomic substitutions

   \begin{align*}\sigma=[a{{:}\text{=}} t] .\end{align*}
   Composition is defined in a standard way by acting on terms as $s\sigma$ . If $a\not\in{dom}(\sigma)$ then $a\sigma=a$ (so the substitution acts as the identity on variable symbols not in its domain). Now, add a fail top element $\textsf{f}$ , such that $s\textsf{f}=s$ always (so $\textsf{f}$ is a formal element that acts as the identity). If the reader likes, we could take $\textsf{f}$ to be $[a{{:}\text{=}} a\mid \text{ all }a]$ . Then substitutions with $\textsf{f}$ form an ACS, where

8. − $\sigma\leq\sigma'$ when ${dom}(\sigma)\subseteq{dom}(\sigma')$ , and $\sigma\leq\textsf{f}$ always.

9. − If ${dom}(\sigma)\cap{dom}(\sigma')=\varnothing$ then $\sigma\bullet\sigma'$ is the finite substitution that maps a to $a\sigma\sigma'$ for each $a\in{dom}(\sigma)\cup{dom}(\sigma')$ , and

10. − if ${dom}(\sigma)\cap{dom}(\sigma')\neq\varnothing$ then $\sigma\bullet\sigma'=\textsf{f}$ The ‘disjoint domains or fail’ condition ensures that composition is monotone in $\leq$ . Unpacking definitions, we check that:

11. − Atomic elements are the generators $[a{{:}\text{=}} s]$ .

12. − A factorisation function ${factor}$ (Definition 4.2.5(1b)) is obtained by ordering atoms and listing a substitution as a list of atomic substitutions in order of the atom on the left.^{Footnote 33}

13. − ${posi}(\sigma)={left}(\sigma)={dom}(\sigma)$ and ${right}(\sigma)={up}(\sigma)=\varnothing$ .

5.1 Action on objects

Definition 5.1.1 Suppose $\mathbb T=(\alpha,\beta,\textsf{Transaction},\textsf{Validator})\in\textsf{IEUTxO}$ is a model (Definition 3.1.9) and recall $\textsf{Chunk}_{\mathbb T}$ from Notation 4.3. Then, we define an abstract chunk system

\begin{align*}F(\mathbb T) = (\textsf{Chunk}_{\mathbb T}\cup\{{fail}\},[],{fail},\leq,\bullet) \in \textsf{ACS}\end{align*}

as follows:

• • The underlying set is $\textsf{Chunk}_{\mathbb T}\cup\{{fail}\}$ – so if we write “ $x\in F(\mathbb T)$ ” this means “either $x={fail}$ or $x\in\textsf{Chunk}_{\mathbb T}$ ”.

• • $\textsf{e}=[]$ and $\textsf{f}={fail}$ .

• • $\leq$ is sublist inclusion (Notation 2.2.3(5)) on chunks that are lists of transactions, with $\textsf{f}$ as a top element, so ${ch}\leq\textsf{f}$ always.

• • $x\bullet\textsf{f}=\textsf{f}=\textsf{f}\bullet x$ , and if x and y are both chunks then $\bullet$ is validated concatenation of chunks, defaulting to the failure element $\textsf{f}$ if validation fails.

$F(\mathbb T)$ resembles $\mathbb T$ , except with an explicit failure element ${fail}$ added. This makes monoid composition total: not every pair of chunks composes to form a list of transactions that is a chunk – as per the criteria in Definition 3.4.1 – thus any combination of chunks that is not a chunk, can be set to ${fail}$ .

We still need to prove that $F(\mathbb T)$ is an abstract chunk system (Definition 4.5.1) in the category $\textsf{ACS}$ (Definition 4.5.2(1)) thus:

• • $F(\mathbb T)$ is a monoid of chunks (Definition 4.2.1),

• • $F(\mathbb T)$ is atomic (Definition 4.2.5) – in fact it is perfectly atomic (Definition 4.2.5(2)) – and

• • $F(\mathbb T)$ is oriented (Definition 4.4.1).

We do this next, culminating with Theorem 5.3.4.

Note that this gives us a dual view of a chunk:

• • as a chunk in the IEUTxO universe, and

• • as an abstract element in the ACS universe.

To what extent do these two views correspond, and how can we make this formal? We prove Proposition 5.2.2, which verifies that the positions in a chunk as an element in the IEUTxO universe, coincide with its positions as an element in the ACS universe. This is refined in further results; notably Lemma 5.3.1 and its sharper corollary Proposition 5.5.4.

Proof. Most of the properties in Definition 4.2.1 are facts of sublist inclusion and concatenation. Condition 6 of Definition 4.2.1 is Lemma 3.5.1.

Recall that being a chunk is down-closed by Corollary 3.5.2, so in a perfectly atomic monoid of chunks, every chunk is above its atomic chunks. It is just a fact of lists, sublist inclusion and the construction in Definition 5.1.1 that $F(\mathbb T)$ is perfectly atomic with atomic elements singleton chunks of the form $[{tx}]$ for ${tx}\in\textsf{Transaction}_{\mathbb T}$ .

5.2 Relation between the partial monoid $\textsf{Chunk}_{\mathbb T}$ and the monoid of chunks $F(\mathbb T)$

• • $T\in\textsf{IEUTxO}$ and ${ch}\in\textsf{Chunk}_{\mathbb T}$ and $a\in{pos}({ch})$ .

• • $\pi\in{Perm}$ is a permutation and $\pi(a)=a$ , and write ${ch}'=\pi{\cdot}{ch}$ (Definition 2.3.3).

It is a structural fact that ${ch}\bullet{ch}',{ch}'\bullet{ch}\in[\textsf{Transaction}_{\mathbb T}]$ since a concatenation of two lists is a list. However:

\begin{align*}{ch}'\bullet {ch} \not\in\textsf{Chunk}_{\mathbb T}\quad\text{and}\quad{ch}\bullet{ch}'\not\in\textsf{Chunk}_{\mathbb T} .\end{align*}

Proof. By assumption $a\in{pos}({ch})$ , so using Lemmas 3.5.10(3) and 3.5.14 (since $\pi(a)=a$ ) precisely one of

\begin{align*}\begin{array}{r@{\ }l}a\in&{utxi}({ch})\cap{utxi}({ch}'),\\a\in&{utxo}({ch})\cap{utxo}({ch}'),\\\text{or}\quad a\in&{stx}({ch})\cap{stx}({ch}')\end{array}\end{align*}

must hold. In each of these three cases, the result follows from Lemma 3.5.10(2).

• • recall ${pos}(x)$ from Definition 3.2.3, and

• • noting from Proposition 5.1.3 that x can also be viewed as an element $x\in F(\mathbb T)$ , recall also ${posi}(x)$ from Definition 4.3.6. Then

  \begin{align*}{pos}(x) = {posi}(x) .\end{align*}

Proof. By a routine calculation from Definitions 3.4.1 and 4.3.6 using Lemma 5.2.1.

We continue Remark 4.3.8:

${pos}$ is intensional – it has and requires full access to the internal structure of its argument – whereas ${posi}$ is extensional – it treats its argument as a black box in which it can only permute atoms and observe compositional behaviour. See also a similar observation in Remark 4.3.13.

A significance of Proposition 5.2.2 is as a (nontrivial) correctness assertion about the overall algebraic framework in which these definitions have been embedded: that the abstract interface of x viewed extensionally matches the concrete interface of x when viewed intensionally.

Put another way, Proposition 5.2.2 has the flavour of being a weak but indicative soundness and completeness result relating a class of concrete models with a class of abstract ones.

Lemma 5.3.1 refines this, and we will continue to build on these ideas, culminating with Theorem 7.3.4.

5.3 $F(\mathbb T)$ is oriented, so $F(\mathbb T)\in\textsf{ACS}$ in ACS

Then for $x\in\textsf{Chunk}_{\mathbb T}$ we have: ^{Footnote 34}

\begin{align*}\begin{array}{r@{\ }l}{left}(x)\subseteq& {utxi}(x)\\{right}(x)\subseteq& {utxo}(x)\\{stx}(x)\subseteq&{up}(x)\end{array}\end{align*}

Proof. We consider each line in turn:

1. 1. If $a\in{left}(x)$ then by Lemma 4.3.12 $a\in{posi}(x)$ so by Proposition 5.2.2 also $a\in{pos}(x)$ . By Definition 4.3.9, there exists $y\in\textsf{Chunk}_{\mathbb T}$ such that $a\in{posi}(y)$ , so by Proposition 5.2.2 also $a\in{pos}(y)$ , and $y\bullet x\in\textsf{Chunk}_{\mathbb T}$ . It follows from Lemma 3.5.10(5.10) that ( $a\in{utxo}(y)$ and) $a\in{utxi}(x)$ as required.

2. 2. If $a\in{right}(x),$ then $a\in{pos}(x),$ and by Definition 4.3.9, there exists $y\in\textsf{Chunk}_{\mathbb T}$ such that $a\in{pos}(y)$ and $x\bullet y\in\textsf{Chunk}_{\mathbb T}$ , so by Lemma 3.5.10(2) ( $a\in{utxi}(y)$ and) $a\in{utxo}(x)$ as required.

3. 3. The reasoning to prove ${stx}(x)\subseteq{up}(x)$ is no harder.

1. 1. Consider a chunk ${ch}\in\textsf{Chunk}_{\mathbb T}$ with an IEUTxO output located at a but with an empty validator (one which validates no inputs). Then $a\in{utxo}({ch})$ in $\mathbb T$ , but $a\in{up}({ch})$ in $F(\mathbb T)$ .

2. 2. Similarly consider a chunk ${ch}$ with an input located at a but such that no validator will validate it – just because an input exists, does not mean a validator must exist to accept it. Then $a\in{utxi}({ch})$ in $\mathbb T$ , but $a\in{up}({ch})$ in $F(\mathbb T)$ .

We return to this with the notion of a blocked channel, in Subsection 5.5.

Proof. We check each condition of Definition 4.4.1 in turn:

1. 1. We check that ${posi}(x)\mathbin{\subseteq_{\text{\it fin}}}{\mathbb A}$ . It is a structural fact of Definition 3.2.3 that ${pos}(x)\mathbin{\subseteq_{\text{\it fin}}}{\mathbb A}$ . We use Proposition 5.2.2.

2. 2. We check that ${posi}(x)=\varnothing$ implies $x=\textsf{e}_{F(\mathbb T)}$ or $x=\textsf{f}_{F(\mathbb T)}$ . An element $x\in F(\mathbb T)$ is either a chunk or the failure element:

3. − If x is a chunk and ${posi}(x)=\varnothing$ then by Proposition 5.2.2 ${posi}(x)=\varnothing$ and by Lemma 3.2.5 $x=[]$ , which by Definition 5.1.1 is $\textsf{e}_{F(\mathbb T)}$ .

4. − If $x={fail}$ then there is nothing to prove, since ${fail}=\textsf{f}_{F(\mathbb T)}$ .

5. (3). We check that ${left}(x)\cap{right}(y)\neq\varnothing$ implies $x\bullet y=\textsf{f}$ . If x or y are ${fail}$ then $x\bullet y=\textsf{f}$ . So suppose that x and y are chunks, that is, suppose $x,y\in\textsf{Chunk}_{\mathbb T}$ . By Lemma 5.3.1 ${utxi}(x)\cap{utxo}(y)\neq\varnothing$ . We use Lemma 3.5.10(2).

6. (4). We check that if ${posi}(x)\cap{posi}(y)=\varnothing$ then x and y commute (Definition 4.3.16(2)). From Proposition 5.2.2 and Lemma 3.5.9(2).

7. (5). We check that if ${posi}(x)\cap{posi}(y)=\varnothing$ and $\textsf{f}\not\in\{x,y\}$ then $x\bullet y<\textsf{f}_{F(\mathbb T)}$ . Using Proposition 5.2.2, this just rephrases Lemma 3.5.6 in the language of a monoid of chunks.

Theorem 5.3.4 $F(\mathbb T)$ (Definition 5.1.1) is an abstract chunk system in $\textsf{ACS}$ (Definition 4.5.1). In symbols:

\begin{align*}F(\mathbb T)\in\textsf{ACS} .\end{align*}

Proof. From Propositions 5.1.3 and 5.3.3.