Algebras of UTxO blockchains
We condense the theory of UTxO blockchains down to a simple and compact set of four type equations (Idealised EUTxO), and to an algebraic characterisation (abstract chunk systems), and exhibit an adjoint pair of functors between them. This gives a novel account of the essential mathematical structures underlying blockchain technology, such as Bitcoin.
1. INTRODUCTION
Blockchain is a young field — young enough that no consensus has yet developed as to its underlying mathematical structures. There are many blockchain implementations, but what (mathematically) are they implementations of ?
Two major blockchain architectures exist:
— UTxO-based blockchains (like Bitcoin), and
— accounts-based blockchains (like Ethereum).
We consider UTxO-style blockchains in this paper, and specifically the Extended UTxO-style model [CCM20], which as the name suggests extends the UTxO structure (how, is described in Remark 3.8.1) of Bitcoin, which is still the canonical blockchain application.
So our question becomes: what, mathematically speaking, is an EUTxO blockchain?
In the literature, Figure 3 of [CCM20] exhibits Extended UTxO as an inductive datatype, designed with implementation and formal verification in mind. Most blockchains exist only in code, so to have an inductive specification to work from in a published academic paper is a luxury for which we can be grateful.
However, this does not answer our question.
It would be like answering “What are numbers?” with the inductive definition : this an important structure (and to be fair, it yields an important inductive principle) but this does not tell us that is a ring; or about primes and the fundamental theorem of arithmetic; or that is embedded in and ; or even about binary representations. In short: Figure 3 of [CCM20] gives us the raw data structure of one particular blockchain implementation, which is certainly important, but this is not a mathematics of blockchains.
As we shall see, there is more to be said here.
1.1. Map of the paper
A map of this paper, and our answer, is as follows:
(1) In Section 3 we present Idealised EUTxO (Definition 3.1.1), which is four type equations (Figure 1). This captures the essence of [CCM20, Figure 3], but far more succinctly — four lines vs. one full page.1 So: EUTxO is a solution to the IEUTxO equations in Figure 1.
(2) The approach to blockchain in this paper is novel — we concentrate not on blockchains but on blockchain segments, which we call chunks (Definition 3.4.1). Chunks have many properties that blockchains do not have: if you cut a blockchain into pieces you get chunks, not blockchains; and chunks have more structure, e.g. they form a partially-ordered partial monoid (Theorem 3.5.4) which communicate across channels (much like the -calculus [Mil99]) and they display resource separation properties reminiscent of known systems such as separation logic (Remark 3.5.13). A blockchain is the special case of a chunk with no active input channels (Definition 3.4.10). So: EUTxO is a system of chunks (a partially-ordered partial monoid with channels).
(3) IEUTxO models form a category (Definition 3.7.1). So now EUTxO is the category of partially-ordered partial monoid solutions to the IEUTxO models, and arrows between them.
(4) Our answers are still quite concrete, in the sense that objects are solutions to type equations. To go further, we use algebra. We introduce abstact chunk systems (Definition 4.5.1), which are oriented atomic monoids of chunks (Definitions 4.4.1, 4.2.5, and 4.2.1). These too form a category (Definition 4.5.2), with objects and arrows. Thus, we extract relevant properties of what makes solutions to the IEUTxO equations in Figure 1 interesting, as explicit and testable algebraic properties (see the discussion in Subsection 8.3). Several design choices exist in this space: we discuss some of them in Remarks 6.4.4 and 7.1.5 and Proposition 7.3.6. So now EUTxO is a bundle of abstract algebraic, testable properties, which exists in a clean design space which could be explored in future work.
(5) Finally, we pull this all together by constructing functors between the categories of IEUTxO models and of abstract chunk systems (Definitions 5.1.1 and 6.2.1), and we exhibit a cycle of categorical embeddings between them (Theorem 7.3.4).
So finally, EUTxO becomes a pair of categories — one of concrete solutions to some type equations, and this embedded in a category of abstract algebras — related by adjoint functors mapping between them; or if the reader prefers, it becomes a loop of embeddings (illustrated in Remark 7.3.5), cycling between the concrete and abstract algebras.
There are many definitions and results in this paper, and this leads to a broader point of it: that the mathematics we observe is possible. There is a mathematics of blockchain here which we have not seen commented on before.
This may help make blockchain more accessible and interesting to a mathematical audience, and improve communication — since there is no more effective language for handling complexity than mathematics. Furthermore, as we argue in Subsections 4.4.2 and 8.3, our analysis of blockchain structure in this paper is not just of interest to mathematicians — it may also be of practical interest to programmers — by suggesting ways to structure and transform code, and establishing properties for unit tests, property-based testing, and formal verification of correctness — and to designers of new UTxO-based systems, wishing to attain good design and security by working from a (relatively compact) mathematical reference model.
More exposition and discussion is in the body of the paper and in Section 8, including discussions of future work.2
2. SOME BACKGROUND
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 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).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 of ‘keys’, but do not force any particular cryptographic content on them.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 is located some data and a validator .
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 on an unspent output with data , and
— present it with a suitable key such considers () to be ‘good’;
the output is now considered ‘spent’ and our block is attached to the chain.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 un-spent.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;7 these are new ‘unspent’ outputs on the chain.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.9
In summary:
Idealised (E)UTxO is a mathematical model of the structural act of UTxO block combination and validation
and
Abstract chunk systems are an algebraic rendering of the same idea.
This basic idea of block combination and validation might not seem like much.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
(1) Fix a countably infinite set of atoms.
(2) A permutation is a bijection on ; write Perm for permutations.
(1) Write 0 1 2.
(2) If X is a set, write fin(X) for the finite powerset of X, and fin!(X) for the pointed finite powerset. In symbols:
Above, () is a pair, and fin(X) X is a cartesian product.
(3) If X and Y are sets, we use a convenient shorthand in Figure 1 by writing
That is, we take (-)! to act on a pair functorially, on the first component. We do this in Figure 1 when we write Transaction! in the definition of Validator.
(4) If X is a set then write [X] for the set of (possibly empty) finite lists of elements from X. We write
for list concatenation, so is followed by . More generally, we will write for any monoid composition; list concatenation is one instance. It will always be clear what is intended.
(5) If X is a set then order [X] by the sublist inclusion relation, where when can be obtained from by deleting (but not rearranging) some of its elements.
(6) If X is a set and X then we may call the one-element list [] [X] a singleton.
(7) If X Bool and X then we may write () or for True.
2.3. The permutation action
We spend this Subsection introducing permutations and their action on elements. We will need this most visibly in two places:
(1) To state the key Definition 4.3.6.
(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 datatypes 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.
For reference we write out the ZFA generic definition, which is by -induction on the sets universe:
More information on this sets inductive definition is in [Gab20a; Gab01]. Definition 2.3.3 can be usefully viewed as a collection of concrete instances of Definition 2.3.2 for the datatypes of interest in this paper:
Permuations act concretely as follows:
(1) If Perm and then acts on as a function:
(2) If Perm and is any set then acts pointwise on as follows:
Note as a corollary of this that .
(3) If Perm and () is a tuple then acts pointwise on () as follows:
Note therefore that (()!!, where 1 and !! indicates lookup.
(4) If Perm and then .
(5) If Perm and () is a pointed set (Notation 2.2.3(2)) then acts pointwise on () as follows:
(This is indeed just a special case of the previous case, for tuples.)
(6) If Perm and is a function then has the conjugation action on as follows:
Note therefore that (()(), and maps to (()).
(7) In particular, acts as the above on the inputs, outputs, sets of inputs, sets of outputs, transactions, and validators from Figure 1.
(8) If Perm and is a relation, then acts pointwise such that
so that
We use Definition 2.3.4 in Definition 4.3.6, but it is a useful concept so we include it here:
If then write fix() for the set of permutations Perm such that (. In symbols:
Call an element equivariant when for every Perm. Concretely:
(1) is equivariant, and no individual atom is equivariant.
(2) A set is equivariant when
In words:
A set is equivariant precisely when it is closed in the orbits of its elements under the permutation action.
(3) () is equivariant precisely when is equivariant for every 1 .
(4) is equivariant, and every is equivariant.
(5) A pointed set () is equivariant precisely when and are equivariant.
(6) A function is equivariant when ((() for every and every .
(7) A relation is equivariant when
3. IDEALISED EUTXO: IEUTXO
3.1. IEUTxO equations and solutions
Let a solution or model of the IEUTxO type equations in Figure 1 be a tuple
where:
(1) is an uninterpreted12 equivariant (Definition 2.3.5(2)) set of keys.
(2) is an uninterpreted equivariant set of data.
(3) Validator is an equivariant set of validators.
(4) Transaction is an equivariant subset of fin() fin( Validator) and we disallow the empty transaction, having no inputs or outputs.
(5) is an equivariant injective function (Definition 2.3.5(6)) from Validator to pow( Transaction!).
Some notation will be helpful:
If tx ) Transaction and then write tx@ Transaction! for the input-in-context (()) obtained by pointing at (Notation 2.2.3). In symbols:
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.
tx Transaction in Figure 2 is a pair of a set of three inputs, and a set of two outputs:
Above:
— , , , , and are atoms in . They serve as unique labels for the inputs and outputs.
Note that every input and output in tx has a distinct label. This is not directly enforced in the raw datatype 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 () is labelled with and so we can think intuitively that it is located at position ; or waiting to communicate its data on channel .
— and are elements of . This is just an uninterpreted datatype, but a good intuition is that these are cryptographic keys.
— and are elements of . This is just an uninterpreted datatype: the intuition is that and are fragments of state data.
Note that state data is stored per-output and not per-transaction. We suppose for concreteness that , so state data can be summed (as we do in the output of ty; more in this shortly). Note that Transaction is a subset of fin(Input) fin(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 is a per-transaction quantity. This may or may not be what we want: the definition allows us to choose.
— and are validators. Their role is, intuitively, to decide which transactions tx will interact with (precise definition in Definition 3.4.1(4)).
ty Transaction is another transaction, with two inputs and one output. Note that its inputs are located at and , meaning that the inputs of ty point to the outputs of tx (Definition 3.2.6). Note also that it performs an addition, in the sense that the state data of its single output is the sum of the state data on its two inputs.
If in addition the following validation conditions are satisfied (@ from Notation 3.1.3)
— ( ty@()) () (in words: validator in state validates the pointed transaction ty@())), and
— ( ty@()) () (in words: validator in state validates the pointed transaction ty@())
then the two-element sequence [tx 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 [tx ty] to be considered a valid chunk. More diagrams and discussion follow in Example 3.4.11. We now return to the definitions.
Sets that do not include atoms — including , inductive types built using , and function types built using — are automatically equivariant. Thus, if the reader unfamiliar with nominal techniques and ZFA wonders whether particular choices they need for , , and 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 — i.e. closed under taking orbits of the permutation action — unless stated otherwise.
Equivariance comes from the underlying ZFA universe. Notation 3.1.5 can be viewed as an assertion that the definition exists in the category of equivariant ZFA sets and equivariant functions between them (or if the reader prefers: sets with a permutation action, and equivariant functions between them).
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, is equivariant (and consists of a single permutation orbit), but none of its elements are equivariant.
Compare Figure 1 with [CCM20, Figure 3]: here corresponds to redeemer there, here corresponds to datum there (though here lives on inputs and lives on outputs, whereas there both redeemer and datum live on inputs); the by-hash referencing there is replaced here with a nominal treatment using atoms; and validators exist on the output here and on the input there. There is less to this latter difference (validator moving from input in [CCM20] to output here) than meets the eye: what is key is the interaction between an output and a later input, so it a matter of perspective and our convenience whether we view the output as validating the input, or vice versa, or indeed both.
Definition 3.1.2(4) uses a subset inclusion, whereas Definition 3.1.2(5) uses an injection . Why?
First, in practice we would expect () to be a computable subset of Transaction!, since we have implementations in mind (though nothing in the mathematics to follow will depend on this).
Also, sets are well-founded, so a pure subset inclusion solution to Figure 1, for both clauses, would be difficult; we use to break the downward chain of sets inclusions.14
Yet just as we may write
eliding (or neglecting to consider) that their realisations may differ (finite cardinals vs. equivalence classes of pairs vs. Dedekind cuts), so — since is an injection — it may be convenient to treat Validator as a literal subset of pow( Transaction!).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):
3.2. Positions
The positions of a transaction are intuitively the interfaces or channels along which it may connect with other transactions to form a chunk (see next subsection). The notion of connection is called pointing to (Definition 3.2.6).
In Figure 3, the positions of tx and ty are and respectively, and input of ty points to output of tx. Also, tx is earlier than ty, and ty is later than tx.
(1) If tx Transaction appears in txs [Transaction] then write tx txs.
(2) If tx txs and tx appears before in txs, then call tx earlier than and later than tx (in txs).
(3) If tx ) Transaction and Output, say appears in tx and write tx when ; similarly for an input Input. We may silently extend this notation to larger data structures, writing e.g. txs when tx txs for some tx.
Intuitively, pos() collects the positions mentioned explicitly on the inputs or outputs of a structure. Note that validators may also act depending on positions of their inputs, but this
information is not detected by pos. For instance, consider a (arguably odd, but imaginable) output having the form
So this output is at position , and carries data 0, and has a validator that validates an input precisely when it is at position . Then pos(.16
Suppose is an IEUTxO model and txs [Transaction]. Then
(1) Suppose Input and Output. Then say that points to and write when they share a position:
(The use of ‘point’ here is unrelated to the ‘pointed sets’ from Notation 2.2.3.)
(2) Recall the notation tx@ from Notation 3.1.3. Suppose that:
Then write
and say that the output validates the input-in-context tx@.
3.3. Why we have and
We are now ready to more rigorously explain the roles of and in Figure 1. We touched on this already in Subsection 2.1 ( is ‘keys’; is ‘data’), but now we can be more specific in our discussion:
— is intuitively a datatype for keys. If ), then 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).
— is intuitively a datatype of abstract data. If ) then stores some kind of state (for instance, an account balance).
We should note:
(1) Nothing mathematical enforces this usage. and are abstract type parameters, to instantiate as we please.
(2) is redundant and can be isomorphically removed. We briefly sketch a suitable isomorphism: We set Output Validator and Validator pow(Transaction!) in Figure 1. is replaced by , and information that was stored as on an output would instead be stored in the validator of that output, which would be set to accept only inputs with -component .
(3) If we only care about countable datatypes and computable data (a reasonable simplification), then everything could be Gödel encoded into . So we could then just fix .
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 and data is useful for clarity, so even though and 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 Validator pow( 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 ) and we pass the state data of to the validator of —
— even though this is mathematically redundant, since and are both in so the could in principle be curried into the . We retain and set Validator pow( Transaction!) rather than just Validator pow(Transaction!), to reflect this practical architecture.
The discussion above is more than hypothetical and corresponds to the experience of creating executable Haskell code. The IEUTxO type equations in this paper have been realised as a Haskell implementation; a reference system has been implemented following it; and some of the results of this paper converted into QuickCheck properties. The package is on Hackage and GitHub [Gab20b].17
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:
Suppose Transaction Validator) is an IEUTxO model. Call a transaction-list txs [Transactions] a chunk when:
(1) Distinct outputs appearing in txs have distinct positions.
(2) Distinct inputs appearing in txs have distinct positions. It may be that the position of an input tx txs equals that of some output txs, or using the notation of Definition 3.2.6(1): . If so, by condition 1 there is at most one such. We write the unique output pointed to by
where it exists, so txs() txs.
(3) For every input tx txs, if the output txs() is defined then that output must occur in a transaction that is strictly earlier than tx in txs.
(4) For every tx txs, if txs() is defined then validates(txs() tx@) (Definition 3.2.6(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 to a later input , which validates — and otherwise positions are distinct.
(1) Write
[] for the set of chunks over .
We may drop the subscripts; the meaning will always be clear.
(2) We may also call a transaction-list valid, when it is a chunk. That is: chunks are precisely the valid transaction-lists.
The way we have formulated the structure of chunks in Definition 3.4.1 reminds this author of the -calculus, where positions correspond to -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:
Suppose Transaction Validator) is an IEUTxO model and suppose tx ) Transaction is a transaction. Then define
— the input channels or positions input(tx) of tx to be the finite set of atoms that are positions of inputs in tx, and
— the output channels or positions output(tx) of tx to be the finite set of atoms that are positions of outputs in tx.
In symbols:
An important special case of Notation 3.4.3 is when the chunk is a singleton list, i.e. it contains just one transaction:
Suppose is an IEUTxO model and suppose tx Transaction. Then
3.4.2. UTxOs, UTxIs . . .
Suppose is an IEUTxO model and txs [Transaction].
(1) If tx txs and txs() is not defined18 then call the unique atom pos() an unspent transaction input, or UTxI. Write utxi(txs) for the UTxIs of txs.
(2) If tx txs and txs() for all later tx txs 19 then call the unique atom pos() an unspent transaction output, or UTxO. Write utxo(txs) for the set of UTxOs of txs.
(3) If tx txs and txs() for some later tx txs, then call the atom pos() a spent transaction channel, or STx. Write stx(txs) for the set of STxs of txs.
Some comments on the interpretation of utxi and utxo and stx from Definition 3.4.8:
utxi(txs), utxo(txs), and stx(txs) are all finite sets of atoms, but we interpret them somewhat differently:
(1) Intuitively, an atom utxo(txs) identifies an output tx txs with position . So utxo(txs) is a finite set of names of outputs in txs.
(2) Intuitively, an atom utxi(txs) identifies an input-in-context tx@, for tx txs with pos(. We say this because the validator of an output takes as argument an input-in-context tx@ Transaction!. So utxi(txs) is a finite set of names for inputs-in-contexts.
(3) Intuitively, an atom stx(txs) identifies a pair of an output and the input-in-context that spends it. Thus could be thought of as this pair, or could be thought of as an edge in a graph that joins a node representing the output, to a node representing the input. So stx(txs) is a finite set of internal names of already-spent communications between outputs and inputs-in-context within txs.
3.4.3. . . . and blockchains.
With the machinery we have now have, it is quick and easy to define blockchains:
A blockchain is a chunk ch Chunk such that utxi(ch. In words:
a blockchain is a chunk with no unspent inputs.
Diagrammatic examples follow in 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.20 In the Figures, a blue circle denotes a validator on an output at some position ( ) 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) , , [ ] and [ ] are blockchains, because they have unspent outputs (in red) but no unspent inputs. In these blockchains, 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.21
(2) [tx] (Figure 2) and [], [ ] and [ ] are chunks, but not blockchains because they have unspent inputs (in red).
(3) [ ] is neither a blockchain nor chunk, because the -input of points to the later -output of . It is just a list of transactions.
We note two alternative characterisation of blockchains (Definition 3.4.10):
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) A sublist of a blockchain is a chunk, not a blockchain (we prove this in a moment, in Corollary 3.5.2).
(2) A composition of blockchains is possible, but uninteresting; whereas composition of chunks is clearly an interesting operation.22
(3) If we cut a blockchain into pieces then we get one blockchain (the initial segment) ...and 1 chunks.
(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 3.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:
Suppose ) is an IEUTxO model, and suppose [ ] [Transaction]. Then the following conditions are equivalent:
— [ ] Chunk for every 1 23
— [ ] Chunk
We note of the well-formedness conditions on chunks from Definition 3.4.1 that they all concern relationships involving at most two transactions.
Suppose we have an IEUTxO model ( Transaction Validator) and [Transaction].
Recall from Notation 2.2.3 that we order lists by sublist inclusion, so when is a sublist of . Then
In words: every sublist of a chunk, is itself a chunk.
From Lemma 3.5.1.
We can wrap up Corollary 3.5.2 in a nice mathematical package:
Suppose ( e) has the following structure:
(1) is a set.
(2) () is a partial order, for which e is a bottom element.
(3) is a partial monoid action on , meaning that () exists if and only if () exists, and if both exist then they are equal.24
(4) is down-closed, meaning that if and exists, then so does , and similarly for and .
(5) is monotone where defined, meaning that if then (provided exists), and similarly for and .
In this case, call ( e) a partially-ordered partial monoid.
By facts of lists, and Corollary 3.5.2.
3.5.2. Some observations on observational equivalence
Suppose Transaction Validator) is an IEUTxO model and ch . Then
By routine checking of possibilities, using the fact that if pos(ch) pos( (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.
Suppose ch . Then call ch and commuting when
Definition 3.5.7 is clearly a notion of observational equivalence between ch and 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.
(1) By routine checking of possibilities, using the fact that if pos(tx) pos( then they have no positions in common, so no output in one can be called upon to validate an input in the other.
(2) It is a fact that if tx then pos(tx) pos() and similarly for . 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.
Suppose is an IEUTxO model and ch Then:
(1) utxi(ch) utxo(ch
(2) If ch then pos(ch) pos() utxo(ch) utxi().
(3) utxi(ch) stx(ch)
pos(ch utxi(ch) utxo(ch) stx(ch) is disjoint union
(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).
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) A statically observable property, that ch and mention disjoint sets of positions.
(2) A locally observable property, that ch and compose in both directions.
(3) An abstract global observable, that ch and 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.
Suppose Transaction Validator) is an IEUTxO model and ch . Then the following are equivalent:
(1) pos(ch) pos(
(2) ch ch .
(3) ch and are commuting.
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 [Rey02], 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 [Nes21] (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:
Suppose IEUTxO is an IEUTxO model and Perm is a permutation of atoms and txs []. Then:
In the terminology of Definition 2.3.5: utxi, utxo, stx, and pos are all equivariant.
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:
Suppose IEUTxO and . Suppose further that
Then we have that:
(1) and are commuting (Definition 3.5.7).
(2) .
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:
Suppose IEUTxO and and suppose is a blockchain. Then:
(1) If is a blockchain then and commute.
(2) If and do not commute then is not a blockchain.
Direct from Theorem 3.6.1, for the case that utxi( utxi(.
Corollary 3.6.2 models a situation where someone designs a chunk that will successfully attach to a blockchain , but because this is a distributed system, somebody else gets in and attaches first.
Then this can only happen if and are commuting; conversely, if and are not commuting then one of or 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 : if is accepted onto both and without failure, then it does not matter that got in first — and are equivalent up to observable behaviour.
Note that:
— Theorem 3.6.1 and Corollary 3.6.2 do not state that IEUTxO systems are insensitive to order, and
— Theorem 3.6.1 and Corollary 3.6.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 successfully combines with , then inputs to may not be modified by an intervening environment — 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 3.6.1 expresses a rigorous sense in which a corresponding phenomenon is impossible in a UTxO-style system.26
With this comparison in mind, we see that Theorem 3.6.1 is a purity result: state is local, and composition of chunks succeeds or fails locally.
3.7. The category IEUTxO of IEUTxO models
We can organise our IEUTxO models into a category:
Let IEUTxO be a category such that:
(1) Objects are IEUTxO models (Definition 3.1.2).
(2) An arrow : is a map
such that if tx then
Above, denotes monoid composition, which on chunks is list concatenation; see Notation 2.2.3(4).
(3) The identity arrow maps tx to [tx].
(4) Composition of arrows is pointwise, meaning that if
then : is such that
We prove this mapping is indeed an arrow — thus, it maps to chunks — in Corollary 3.7.4.
We briefly discuss the design decisions embedded in Definition 3.7.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 . 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) We could relax the condition to allow to be a partial map.
This would exhibit IEUTxO as a subcategory of a larger category with the same objects but more arrows, and in particular it would allow chunks in to cease to be valid when mapped to — we would still insist that 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; e.g. following an intuition that is a liberal universe of chunks, and maps it to a stricter universe in which additional restrictions are appended to validators. Thus, chunks in the liberal world might cease to be valid in the stricter universe.
(3) We could also restrict further so that : .
This would yield fewer arrows, and we prefer to allow the flexibility of mapping a single transaction in to a chunk of transactions in ; following an intuition that is a coarse-grained representation which 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:
Recall from Figure 1 that validators take as input a pointed transaction:
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:
There is an easy embedding map which we can write 1, taking an IUTxO model to an IEUTxO model, derived from the embedding
which is itself derived from the projection taking a pointed transaction to its input-point:
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.
The mapping e extends to a categorical embedding27 IUTxO IEUTxO.
Direct from the construction, since an IUTxO model is identified with an IEUTxO model whose validators ignore the transaction and just look at the input-point.
For convenience, we may treat IUTxO as a direct subset of IEUTxO — abusing notation we could write IUTxO IEUTxO — thus identifying an IUTxO model with an IEUTxO model whose validators only check the input-point of their transaction. Thus for instance we wrote ‘is identified with’ in Proposition 3.8.2. It will always be clear what is intended and we could always unroll the injections if required.
4. ABSTRACT CHUNK SYSTEMS: ACS
4.1. Basic definitions
IEUTxO models are good, because they abstract key features of blockchain architectures in a simple and (I would argue) clear manner: output, input, and (valid) combination of transactions to form chunks and then blockchains.
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:
Suppose X is a set and X2 is a relation on X. Call (X) a well-ordering when:
(1) is a partial order (reflexive, transitive, anti-symmetric), and
(2) is well-founded (every descending chain is eventually stationary).28
As per Notation 3.1.5, X and are also assumed equivariant.
This should be familiar, but we give examples:
— () is not well-founded.
— (pow()) and (fin()) are well-founded.
— [] (lists of numbers) with sublist inclusion is well-founded.
Suppose (X e f) is a partial order with an equivariant least element e and an equivariant greatest element f. Call X atomic when
(1) e f and
(2) for every X if then either e or .
Write atomic(X) for the set of atomic elements of X (see also Definition 4.2.5).
If we call X proper when it is neither e nor f (following the standard terminology of proper subset), then an atomic element is “a minimal proper element”.
The set of atomic elements atomic(X) is not to be confused with the set of atoms from Definition 2.2.1. This name collision is just a coincidence.
Lemma 4.1.6 will be useful later:
Using Corollary 3.5.2.
4.2. Monoid of chunks
Assume we have equivariant data (X e f) where:
— X is a set.
— e f X are called unit and fail respectively.
— X2 is a relation.
— : X X is a composition.
Call (X e f) a monoid of chunks when:
(1)
(2)
(3) is a well-ordering for which the unit e is a bottom element and the paradoxical element f is a top element.
(4) Composition is associative, and monotone in both components, meaning that
(5) Composition is increasing in the sense that
(6) If X and f, then there must exist 1 such that f.
A few comments on Definition 4.2.1:
(1) This is a clearly an abstraction of IEUTxO structure, where is chunk composition and 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) is not necessarily a least upper bound for . Take 1 2 and and in Example 4.2.6(4) (finite lists with a top element). Then and are distinct and incomparable, so both are upper bounds for but and .
(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.
As is standard, we may write X for both a monoid of chunks and its carrier set. See for instance the first line of Definition 4.2.4.
Suppose X X e f) is a monoid of chunks.
(1) If X and [] [atomic(X)] is a finite list of atomic elements29 in X and then say that factorises as [].
(2) Say that X is generated by its atomic elements when every X f has a (possibly non-unique) factorisation into atomic elements.
(1) Call a monoid of chunks X X e f) atomic when:
(a) X is generated as a monoid by its atomic elements (Definition 4.2.4).
(b) There exists a factorisation function factor : X f [atomic(X)] such that for every X f i. factor() factorises (Definition 4.2.4) and ii. factor( factor() factor() (the right-hand denotes list concatentation; the left-hand is the monoid action in X).
In words we say that X is atomic when there is a homomorphism of partially-ordered monoids from X f to the space of possible factorisations of its elements. The relevance of this condition is discussed in Remark 6.4.4.
(2) Call X perfectly atomic when it is atomic and furthermore:
(a) factorisations into atom elements are unique and
(b) if f and and then [] [] (sublist inclusion).
The relevance of this condition is discussed in Proposition 7.3.6.
Suppose is an equivariant set. Then:
(1) pow() forms a monoid of chunks, where e and f , and is subset inclusion, and composition is sets union. It is atomic if and only if is finite (recall: factorisations must be finite). We obtain a factorisation function by choosing any order on , and listing elements of any in order.
(2) pow() forms a monoid of chunks, where:
— e and f .
— is subset inclusion.
— if , and f otherwise.
It is atomic if and only if is finite.
(3) fin() (finite sets of atoms, with a top element) forms an atomic monoid of chunks, using either of the two definitions above for pow().
(4) Finite lists with a top element [] — meaning finite lists of elements from , plus one extra ‘top’ element — form a perfectly atomic monoid of chunks as follows:
— e and f .
— is sublist inclusion (Notation 2.2.3(5)) and f for every finite list .
— Composition is list concatenation on lists, and f f f for any (list, or f).
(5) Finite lists with a top element [] form an atomic (but not perfectly atomic) monoid of chunks as above, where and are defined as follows:
— holds when is not a singleton list and is a sublist of . So [] [] and [] [] [] but [] []; and the proper atomic elements are singleton and two-element lists.
— [] for any list.
— f f f for any .
— If and are non-empty lists, then is concatenated with , where is everything except for the last element of , and is everything except for the first element of .
(6) As touched on above, if is an IEUTxO model then gives rise to a perfectly atomic monoid of chunks. See Proposition 5.1.3.
It might seem counterintuitive to make failure f a top element in Definition 4.2.1, especially if we are used to seeing domain models where ‘failure’ is intuitively ‘non-termination’ and features as a bottom element.
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 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 reflects how they accumulate transactions over time), then to exhibit a is to fail to exhibit a concrete witness. Or (thinking perhaps of callCC [CFW86]) we can think of f as a ‘final’ or ‘escape’ element.
4.3. Behaviour, positions, and equivalence
4.3.1. Left- and right-behaviour
Suppose X X e f) is a monoid of chunks. Then we have natural left- and right-behaviour functions:
Suppose X is a monoid of chunks. Then we have:
(1) leftB(e rightB(e X f.
(2) leftB(f rightB(f.
If we think of f as a failure element, and we think of as being a composition of which we can observe whether it fails or succeeds, then
— rightB maps X to its right-observational behaviour, and
— leftB maps X to its left-observational behaviour.
Parallels can be made in Definition 4.3.1 with the -calculus [Bar84] and the -calculus [Mil99]:
(1) In the -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 () we observe failure to compose (f), and we consider combination both to the left and to the right.
Continuing the analogy, in the untyped -calculus, the left-behaviour set of a term would be those such that terminates; and the right-behaviour set of would be those such that terminates.
(2) The -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:
(a) Validation is not primitive in the -calculus but it is a core precept here.
(b) Communication in the plain -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 f (cf. the conditions in Definitions 3.4.1 and 3.4.10).
(c) Name-restriction in the -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.
4.3.2. Positions
Suppose X is a monoid of chunks. Define posi() the positions of X as follows:
(fix() from Definition 2.3.4.)
Thus posi() when and leftB() rightB(), for any such that (.
In words, posi() from Definition 4.3.6 is those atoms such that there is no permutation fixing such that can be successfully combined (left or right) with .
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 in an element by forcing name-clashes between -channels with -renamed variants for fix(). More details will follow, and see Remark 5.2.3.
Suppose X X e f) is a monoid of chunks, and suppose X and .
(1) If
then say that points left in . Write left() for the set of atoms that point left in .
(2) If
then say that points right in . Write right() for the set of atoms that point right in .
(3) If points neither left nor right in and yet posi(), so that
then say that points up in . Write up() for the set of atoms that point up in .
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’:
Suppose X is a monoid of chunks and X and up(). Then
A simple lemma will be helpful:
Suppose X is a monoid of chunks and X. Then:
Lemmas 4.3.12 and 3.5.10(3) are similar but note that the status of the underlying datatypes is somewhat different:
— A chunk ch 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 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).
Lemma 4.3.12 expresses that every position in some 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.
4.3.3. Observational equivalence
Suppose X is a monoid of chunks.
(1) Call and in X observationally equivalent and write
(2) Say that and commute (up to observational equivalence) when
We start with a simple but useful sanity check:
Suppose X is a monoid of chunks and X. Then if and commute then
Suppose X is a monoid of chunks. Then if (Definition 4.3.16) then
4.4. Oriented monoids
4.4.1. Definition and properties
We discuss the conditions of Definition 4.4.1 in turn:
(1) An element X can only be accessible on finitely many channel interfaces.
(2) The only elements without any interface (meaning atoms that point left right or up) are the unit element (-bottom) and the failure element (-top). Compare with the IEUTxO property Lemma 3.2.5. We use this in Lemmas 4.4.6 and 6.3.1.
(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) This condition echoes Lemma 3.5.9(2). We use it in Proposition 4.4.8.
(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:
Suppose X is an oriented monoid of chunks and X. Then
Lemma 4.4.4 is a nice way to repackage Definition 4.4.1(3) in a slightly more accessible wrapper. In its form it resembles Lemma 3.5.10(2), and we use it for Corollary 4.4.5:
Suppose X is an oriented monoid of chunks and suppose X. Then
We consider the possibilities, using Lemma 4.3.12:
— Suppose left() posi(). From Definition 4.4.1(3) right(), and by Lemma 4.3.12 posi(). It follows from Definition 4.3.9(2) that f.
— Suppose right() posi(). From Definition 4.4.1(3) left(), and by Lemma 4.3.12 posi(). It follows from Definition 4.3.9(1) that 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 X generate valid singleton chunks under a mapping to IEUTxO models :
Suppose X is an oriented monoid of chunks and X. Then:31
Suppose left(); we will show that right() is impossible. Consider some X with posi(), so that by Lemma 4.3.12 left() right() up(). Then:
— If left() then left() left() and by Lemma 4.4.4 f.
— If right() then left() right() and by Lemma 4.4.4 f.
— If up() then left() up() and by Lemma 4.4.4 f.
Thus posi() implies f and so rightB(). It follows from Definition 4.3.9(2) that right() as required.
We use Lemma 4.4.6 for Proposition 4.4.8:
Suppose X X e f) is an oriented monoid of chunks. Then at least one of the following must hold:
If or are equal to e or f then posi() posi( is immediate from Lemma 4.4.3.
So suppose e f, from which it follows by Lemma 4.4.3 (or direct from Definition 4.4.1(2)) that posi() and posi() . Suppose we have some posi() posi(). We reason by cases using our assumption that X is oriented (Definition 4.4.1):
— If left() right() then f by Definition 4.4.1(3).
— If right() left() then f by by Definition 4.4.1(3).
— If up() or up() then f by Lemma 4.3.10.
— Other cases are no harder.
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.
First, note that since f or f, it must from Definition 4.2.1(2) be the case that f and f.
If f f then posi() posi( by Lemma 4.4.6. Conversely if posi() posi( then (since f and f) by Definition 4.4.1(5) f and f.
If posi() posi( then and commute by Definition 4.4.1(4). Conversely, if posi() posi() then by Lemma 4.4.6 (since f or f) we have that f or f respectively, and in particular we have that . Using Lemma 4.3.17 we conclude that and do not commute.
There is design freedom to Definition 4.4.1, and we mention this briefly for future work. One plausible condition is:
Intuitively, this states that combining and can only bind positions that point right in and point left in . An even stricter variant would be to insist on equality provided that f.
4.4.2. A brief discussion.
We might ask:
Why bother with monoids of chunks? Why not just work with IEUTxOs?
The answer is that we need both: IEUTxOs are the motivating concrete model, and monoids of chunks are their abstraction.
Of course, the IEUTxO equations from Figure 1 themselves are an abstraction and generalisation of a concrete inductive definition in [CCM20, Figure 3], so in overview this paper has the following hierarchy of models, given in increasing order of generality —
— The inductive EUTxO structures from [CCM20].
— IEUTxO models from Definition 3.1.2.
— Abstract chunk systems (ACS) from Definition 4.5.1.
— though there is also more going on, because we also map from ACS back down to IEUTxO (Theorem 7.3.4 and surrounding discussion). Programmers can think of APIs, which abstract away from internal structure of a concrete implementation; this makes programs more modular, and easier to test and document. Modern programming languages make it easier to program efficiently using abstract denotations, instantiating only when needed — one might call this just-in-time instantiation. So even if we have just one concrete model and want one implementation, a good algebraic theory is still relevant to producing working code, because
— it may help structure the mathematics and the code — the algebraic graphs with class Haskell package illustrates how effective this marriage of theory and practice can be [Mok17] — and
— an abstraction can be read as a library of testable properties, against which implementations can be checked. If an implementation fails an axiom — it’s wrong.
So perhaps a better question is this:
What are the essential properties of IEUTxO that make it interesting? How are these properties layered, and nested; and how can they be compactly represented?
Definitions 4.2.1 and 4.4.1 are one set of answers to these questions. And then, a further question is this:
What other models, aside from IEUTxO models, exist of the ACS axioms?
This paper contains one answer (plus examples; see Subsection 4.6): in Definitions 6.2.1 and 6.4.1 and Proposition 6.4.3 we give a functor taking any oriented monoid of chunks to IEUTxOs. We also map functorially in the other direction in Definitions 5.1.1 and 5.4.1 and Theorem 5.4.4.
The overall results are packaged up in Theorem 7.3.4.
4.5. The category ACS of abstract chunk systems
We are now ready to give the algebraic account of IEUTxOs promised in Remark 4.1.1:32
Define ACS the category of abstract chunk systems by:
(1) Objects are abstract chunk systems (Definition 4.5.1).
(2) Arrows : X Y are sets functions from X to Y such that:
(a) ( and (
(b) implies () ()
(c)
Composition of arrows is composition of functions, and the identity arrow is the identity function.
(1) We do not insist in Definition 4.5.2 that () must be atomic if is. This corresponds to our choice in Definition 3.7.1(2) to let map from transactions to chunks, and not from transactions to transactions.
(2) We do insist in Definition 4.5.2(2b) that if is not the failure element in X then () is also not the failure element in Y. This corresponds to our choice in Definition 3.7.1(2) to make 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 to map to . There would be nothing wrong with this and it would just exhibit 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 ACS:
Suppose X Y ACS and X and : X Y ACS. Then:
— If f then there exists some finite (possibly empty, possibly non-unique) list of atomic elements atomic(X) such that .
— If f (and in particular by Definition 4.1.4(1) if is atomic) then there exists some finite (possibly empty, possibly non-unique) list of atomic elements atomic(Y) such that (.
(1) Consider some X. If f e then the action of is determined by Definition 4.5.2(2a). Otherwise, using Lemma 4.5.4 write for atomic atomic(X). We then have from Definition 4.5.2(2c) that
Thus () is determined by the values of (), ..., ().
(2) By a routine argument from Definition 4.2.5 (since 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) Consider the set of all finite sets of atoms and itself:
X forms an ACS such that
— when .
— (disjoint union) if and are disjoint, and otherwise.
Unpacking definitions, we can check that:
— Atomic elements are singletons .
— A factorisation function factor (Definition 4.2.5(1b)) is obtained by ordering atoms and listing the finite set in order.
— posi( up( and left( right(.
(2) Consider some datatype Terms of term syntax over variable symbols (terms of first-order logic () for some term-formers , or terms of the untyped -calculus would suffice). Let finite substitutions be finite partial maps from variable symbols to terms generated by atomic substitutions
Composition is defined in a standard way by acting on terms as . If dom() then (so the substitution acts as the identity on variable symbols not in its domain). Now, add a fail top element f, such that f always (so f is a formal element that acts as the identity). If the reader likes, we could take f to be [: all ]. Then substitutions with f form an ACS, where
— when dom() dom(), and f always.
— If dom() dom( then is the finite substitution that maps to for each dom() dom(), and
— if dom() dom() then f
The ‘disjoint domains or fail’ condition ensures that composition is monotone in . Unpacking definitions, we check that:
— Atomic elements are the generators [:].
— 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.33
— posi( left( dom() and right( up(.
5. THE FUNCTOR : IEUTXO ACS
5.1. Action on objects
Suppose Transaction Validator) IEUTxO is a model (Definition 3.1.9) and recall from Notation 3.4.3. Then we define an abstract chunk system
as follows:
— The underlying set is fail — so if we write “()” this means “either fail or ”.
— e and f fail.
— is sublist inclusion (Notation 2.2.3(5)) on chunks that are lists of transactions, with f as a top element, so ch f always.
— f f f , and if and are both chunks then is validated concatentation of chunks, defaulting to the failure element f if validation fails.
So if but [] in — so the two chunks cannot be validly combined in — then fail in (). We will always be clear whether means ‘concatenate as lists’ or ‘compose in ()’.
() resembles , 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 () is an abstract chunk system (Definition 4.5.1) in the category ACS (Definition 4.5.2(1)) thus:
— () is a monoid of chunks (Definition 4.2.1),
— () is atomic (Definition 4.2.5) — in fact it is perfectly atomic (Definition 4.2.5(2)) — and
— () 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.
(1) () from Definition 5.1.1 is a perfectly atomic (Definition 4.2.5(2)) monoid of chunks (Definition 4.2.1). Unpacking Definition 4.2.5(2), any () f can be uniquely decomposed as a (possibly empty) finite list of atomic elements
and if then the factorisation of is a sublist of the factorisation of .
(2) Furthermore, the atomic elements atomic(()) are singleton lists of the form [tx] for tx .
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 () is perfectly atomic with atomic elements singleton chunks of the form [tx] for tx .
5.2. Relation between the partial monoid Chunk and the monoid of chunks ()
Suppose that:
— IEUTxO and ch and pos(ch).
— Perm is a permutation and (, and write ch (Definition 2.3.3).
It is a structural fact that ch ch [] since a concatentation of two lists is a list. However:
We continue Remark 4.3.8:
pos from Definition 3.2.3 and posi from Definition 4.3.6 have different constructions yet give equal results, in a sense made formal in Proposition 5.2.2. Aside from being a useful equality, what does this tell us?
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 (non-trivial) correctness assertion about the overall algebraic framework in which these definitions have been embedded: that the abstract interface of viewed extensionally, matches the concrete interface of 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. () is oriented, so () ACS
We consider each line in turn:
(1) If left() then by Lemma 4.3.12 posi() so by Proposition 5.2.2 also pos(). By Definition 4.3.9 there exists such that posi(), so by Proposition 5.2.2 also pos(), and . It follows from Lemma 3.5.10(2) that ( utxo() and) utxi() as required.
(2) If right() then pos() and by Definition 4.3.9 there exists such that pos() and , so by Lemma 3.5.10(2) ( utxi() and) utxo() as required.
(3) The reasoning to prove stx() up() is no harder.
Lemma 5.3.1 is interesting as much for what it is not, namely it is not the equality left utxi and right utxi and up stx that one might initially expect. Why?
(1) Consider a chunk ch with an IEUTxO output located at but with an empty validator (one which validates no inputs). Then utxo(ch) in , but up(ch) in ().
(2) Similarly consider a chunk ch with an input located at but such that no validator will validate it
— just because an input exists, does not mean a validator must exist to accept it. Then utxi(ch) in , but up(ch) in ().
We return to this with the notion of a blocked channel, in Subsection 5.5.
We check each condition of Definition 4.4.1 in turn:
(1) We check that posi() . It is a structural fact of Definition 3.2.3 that pos() . We use Proposition 5.2.2.
(2) We check that posi( implies or . An element () is either a chunk or the failure element:
— If is a chunk and posi( then by Proposition 5.2.2 posi( and by Lemma 3.2.5 , which by Definition 5.1.1 is .
— If fail then there is nothing to prove, since fail .
(3) We check that left() right() implies f. If or are fail then f. So suppose that and are chunks, that is, suppose . By Lemma 5.3.1 utxi() utxo() . We use Lemma 3.5.10(2).
(4) We check that if posi() posi( then and commute (Definition 4.3.16(2)). From Proposition 5.2.2 and Lemma 3.5.9(2).
(5) We check that if posi() posi( and f then . Using Proposition 5.2.2, this just rephrases Lemma 3.5.6 in the language of a monoid of chunks.
5.4. Action of on arrows
() from Definition 5.4.1 does indeed map from () to ().
We need to check that validity is preserved, meaning that if [ ] is a chunk then so is () (). This is Lemma 3.7.2.
We check the properties in Definition 4.5.2(2) in turn:
(1) We check that ()( and ()( . This is just the fact that ( and ()( .
(2) We check that implies ()() ()() . It is a fact of the construction in Definition 5.4.1 that ( is a sublist of ) implies ()() ()().
(3) We check that ()() ()(()(). A fact of the first clause of equation (3) in Definition 5.4.1.
We can check (() () and ( by routine calculations which we elide.
5.5. Blocked channels
Recall from Remark 3.4.4 that we can think of positions as communication channels in the -calculus sense. We conclude this Section by taking a little time to refine the subset inclusions from Lemma 5.3.1. For this, we need to consider the possibility of a channel which is (intuitively) blocked, in the sense that no successful validation can occur across it:
Suppose that is an IEUTxO model and ch and .
(1) Suppose that
— utxi(ch) and
— for every with utxo(), ch is not a chunk.
Then call a blocked utxi in ch. Write blockedUtxi(ch) for the blocked utxis of ch.
(2) Similarly define blockedUtxo(ch) the blocked utxos of ch to be those such that
— utxo(ch) and
— for every with utxi(), ch is not a chunk.
So a blocked UTxI or UTxO in a chunk is an input or output that exists, but which fails if you try to interact with it. This could happen for an output whose validator is the empty set (it fails on any input), or for an input such that no validator in exists to validate it (see Remark 5.3.2).
Suppose is an IEUTxO model and and . Then
Suppose IEUTxO and ()f (that is, ). Then:
We know by Lemma 5.3.1 that left() utxi() and right() utxo(). Now suppose utxi() and blockedUtxi(); unpacking Definition 5.5.1 this means that there exists a such that utxo() and . By Lemma 5.5.3 it follows that ( right() and) left().
The case of right() is similar, and the case of up() follows from the previous two cases and Lemma 5.3.1.
6. THE FUNCTOR : ACS IEUTXO
6.1. A brief discussion: why represent?
In Subsection 4.4.2 we observed a hierarchy of models, from concrete EUTxO structures to IEUTxO models to abstract chunk systems.
The mapping from IEUxO to ACS is the functor : IEUTxO ACS from Section 5. We will now exhibit a functor : ACS IEUTxO back down from the abstract to the concrete structures.35
This is interesting for two reasons: one specific, and one general. We consider each in turn. is interesting because:
(1) It gives a sense in which the abstraction reasonably represents the concrete models. That is, there is nothing the abstract model could do that is so crazy that it cannot be engineered back down to a concrete structure. This may involve some ugly concrete fiddling, emulation, and choices — as one might expect going from an abstract to a concrete object — but it can be done, and seeing how, can be helpful for understanding both worlds.
(2) Sometimes, theorems are better proved in the concrete world than the abstract world. This can be particularly useful to prove negative properties, that something cannot happen in the abstract world, because it would correspond to something that would be impossible in the concrete world. A well-known example is that every Boolean Algebra can be represented as a powerset, and thus every finite Boolean Algebra has cardinality a power of two. Thus, to prove that some abstract structure does not admit any Boolean Algebra structure, it suffices if its carrier set is finite and has cardinality that is not a power of two.36
Now to understand the relevance of specifically for this paper, consider the following question:
In what sense is Definition 4.5.1 a good abstraction of Definition 3.1.2?
Design decisions are embedded in the conditions of Definition 4.5.1, and some of these were not trivial and had more than one plausible outcome. Why did we choose as we did? How do these choices interact? In what sense were they appropriate?
To answer these questions, is not necessarily the greatest help on its own. To illustrate why, consider that we can obtain a general ‘theory of blockchains’ merely by insisting that an ‘abstract chunk system’ is a set. We impose no further structure: et voil: instant generality!37 But this tells us little; e.g. would just be the forgetful functor, mapping an IEUTxO model to its underlying set. We could map just to monoids, if we add the failure element, and again an would exist, but this would be only slightly less uninformative.
So where is the sweet spot, and why? As we observed, merely exhibiting an -style functor does not help: we need to get an algebraic measure of what it is about Figure 1 that gives it its essential nature.
We get a formally meaningful measure of an appropriate level of abstraction by locating one at which we can build a sensible functor going back, and seeing how conditions in Definition 4.5.1 interact with its construction — and, we can observe how tweaking them can affect, or even break, these constructions. A discussion of such tweaks, and their effects, is in Remarks 6.4.4 and 7.1.5, and Proposition 7.3.6.
What counts as a ‘sensible’ is a design decision in itself. We consider several options in this paper (listed here in increasing order of size of the category of denotations ACS):
(1) a categorical equivalence (Proposition 7.3.6); or
(2) a categorical embedding (Theorem 7.3.4 and Remark 7.3.5); or
(3) just an injection on objects (Remark 6.4.4).
All these possibilities are justifiable.38 So to be clear: and the choices we make in building it are not intended as direct value judgements; they are a way to measure and explore the structure of a large, abstract, and interesting design space.
6.2. Action on objects
Recall from Definition 3.1.2 the notion of an IEUTxO model, and the accompanying discussion in Remark 3.1.8 about the status of the injection : Validator pow( Transaction!).
Continuing that Remark, in Definition 6.2.1 we must be explicit about :
Suppose (X e f) ACS. We define an IEUTxO model (X)
as follows:
(1) We take atomic(X) (Definition 4.1.4).
(2) We take:
where is a unit type.
(3) For each atomic atomic(X) we admit a transaction
such that:
Thus:
for tx defined as above.
(4) We define : Validator pow( Transaction!) to map Validator as follows (@ from Notation 3.1.3):
Thus, () is the function that inputs and a pointed transaction tx@(), extracts the data from the input, and then checks that f in X.39
Continuing Remark 3.8.1, we see that the validator used by in Definition 6.2.1 is UTxO-style; it only examines the (pointed) input of the transaction to be validated. So in fact, maps not just to IEUTxO models but to the IUTxO models noted in Subsection 3.8. We will use this observation in Theorem 7.3.4(3).
An easy sanity check:
Suppose X ACS and X. Then tx() tx() is a chunk if and only if f.
By construction, unravelling Definition 6.2.1.
— input(tx(() left() and
— output(tx(() right() up().
So up-atoms in map to output-atoms in tx(). Why? For two reasons:
— The short reason is that it makes Lemma 6.3.2 work: all atoms in posi() get recorded in an input or output (even the ones in up(), which cannot participate in a non-failing interaction), along with a copy of (to get injectivity).
— The longer reason is as follows: An ACS element X has no internal structure and thus no explicit structural notion of inputs or outputs. Our only interaction with is by combining it with other elements and observing partiality (cf. Remark 4.3.5). But suppose our ACS X was obtained concretely from an IEUTxO model using from Definition 5.1.1, so that is ‘secretly’ a singleton chunk, presented as an atomic element in an ACS. Then up() could occur for two reasons:
— either is the position of an input which no output will accept (perhaps it is labelled with some data that all validators disapprove of);
— or is the position of an output that will not validate any available input (e.g. it has the empty validator).
When we come to map back to a transaction tx(), the simplest way to record is to attach it to an IEUTxO output located at , with a validator that always fails. The other option would be to attach to an input in tx(), to tag the data carried by that input with some special ‘fail-me’ tag, and remember to create only validators that recognise this tag and reject the input. But this is clearly a more complicated way of doing things, and the design adopted in Definition 6.2.1(3) seems the natural and simple approach.
Several things about Definition 6.2.1 need checked. We start with Lemma 6.2.5:
(1) If X ACS and atomic(X) then tx() has the right type to be a transaction as per Figure 1.
(2) If X ACS and atomic(X) then [tx()] is a chunk.
(3) As a corollary, atomic elements in (X) are precisely the singleton chunks of tx(), where ranges over atomic elements of X — or more concisely in symbols:
(1) From Definitions 4.4.1(1) and 6.2.1(3) and Lemma 4.3.12, tx() has finitely many inputs and outputs; so as per Figure 1 it is indeed a pair of a finite set of inputs and a finite set of outputs.
(2) By Lemma 3.4.6, to show [tx] is a valid chunk it would suffice to show that input(tx()) output(tx(. This follows from Lemma 4.3.12 and Corollary 4.4.5.
(3) By construction and Lemma 4.1.6, noting that in lists ordered by subset inclusion, atomic elements are singleton lists.
We mention an alternative definition of from Definition 6.2.1, just to illustrate that more than one encoding is possible:
(1) We take Validator atomic(X) (Definition 4.1.4).
(2) For each atomic atomic(X) we admit a transaction tx() Transaction such that:
(3) We define : Validator pow( Transaction!) to map Validator as follows:
6.3. is injective
Suppose X ACS (Definition 4.5.2). Then
(1) By Lemma 6.3.1 (since is atomic) posi() , so by Lemma 4.3.12 at least one of left() or right() or up() must be nonempty. If left() is nonempty then tx() has an input and we can read off the data in that input. Otherwise tx() has an output and we can read off the data in that output.
(2) It follows from Definition 6.2.1(3) and Figure 4 that pos(tx( left() (right() up()). Also, by Lemma 4.3.12 pos( left() right() up().
As promised in Remark 6.2.7, we prove:
6.4. Action on arrows
Suppose : X Y ACS and recall from Definition 3.7.1(2) that an arrow
should be a mapping from to . Recall factor from Definition 4.2.5(1b), which factorises non-failure elements into atomic constituents, and recall from Definition 4.5.2(2b) that maps non-failure elements to non-failure elements.
Then define () by
() from Definition 6.4.1 is well-defined.
We must check that tx() tx() is a chunk; this follows by Lemma 3.7.2.
The significance of condition 1b of Definition 4.2.5 is not that elements can be factored into atomic elements — this follows already from condition 1a — but that a factorisation can be selected, as a monoid homomorphism.
We use this condition in just one place: to define the action of on arrows in Definition 6.4.1 and prove it functorial in Proposition 6.4.3.
It would be legitimate to remove condition 1b of Definition 4.2.5. This would exhibit our category ACS as a subcategory of a larger category which would include more objects — ‘even more abstract’ abstract chunk systems — at a cost of no longer being able to functorially map this larger space back down to IEUTxO.
Intuitively, this larger space behaves more like a space of all possible denotations rather than a space of IEUTxO-representable ones, which might be worthwhile if it admits other interesting examples; whether or not this will be the case cannot be predicted at time of writing.
Note that the action on objects from Definition 6.2.1 would still be well-defined even without Definition 4.2.5(1b), so that we can still represent our ‘even more abstract’ abstract chunk systems concretely in IEUTxO models: this just would not correspond to a functor.40
7. AN ADJUNCTION BETWEEN : IEUTXO ACS AND : ACS IEUTXO
7.1. The counit map X : (X) X exists and is a surjection
Suppose X ACS; we wish to define an arrow (X) X ACS. Unpacking Definitions 6.2.1 and 5.1.1, we see that an (X) has one of the following forms:
— fail for fail the failure element added by to in Definition 5.1.1.
— tx() tx()] for some unique [] [atomic(X)].
We also know from Lemma 6.3.2 that tx : atomic(X) Transaction((X)) is injective, and it follows that we can recover each from the unique corresponding [tx()] above.
Let (X) X be determined by:
(1) (this would be a special case of the next clause, for )
(2) ([tx() tx( for 1 and atomic(X)
(3)
Definition 7.1.2 is well-defined and determines an arrow in ACS.
Well-definedness follows as per Remark 7.1.1 from Lemma 6.3.2, since we can recover each from its [tx()]. It remains to check the arrow conditions from Definition 4.5.2(2):
(1) We check that (e and (f . A fact of Definition 7.1.2.
(2) We check that f implies () () . By Proposition 5.1.3 (X) is perfectly atomic, and if f then and factorise uniquely into a composition of lists of singleton chunks, which by construction in Definition 6.2.1(3) have the form tx() and tx(), such that the factorisation of is a sublist of the factorisation of . The result follows by a routine calculation from Definition 7.1.2.
(3)
A fact of Definition 7.1.2, again using the fact that by Proposition 5.1.3 (X) is perfectly atomic.
The counit map (X) X ACS is a surjection on underlying sets.
Suppose we are given X; we want to exhibit an element in (X) that maps to it under .
If then by construction in Definition 5.1.1 fail f and also by construction (fail so we are done.
Otherwise by Proposition 5.1.3 (or just by Definition 4.2.5) we can write
for some atomic atomic(X), and looking at Definition 7.1.2 we immediately have that
By Proposition 7.1.4 surjects (X) onto X as sets, but is it not necessarily surjective on the structure, meaning that (ch) () does not imply ch .
We can have this if we add condition 2b of Definition 4.2.5, that: if f then factor() factor() (the right-hand denotes sublist inclusion; the left-hand is the partial order on X). More on this in Proposition 7.3.6. Further tweaks to the design of abstract chunk systems are also mentioned in Remark 6.4.4.
7.2. The unit map () exists and is an isomorphism
Suppose Transaction Validator) IEUTxO. We wish to define an arrow
We can make some observations:
— By construction in Definition 5.1.1, () is isomorphic as a partial ordering to , with the addition of the fail top element.
As noted in Proposition 5.1.3 it follows that the atomic elements of () correspond precisely with the singleton chunks in , and thus with transactions in .
The chunks in () are then determined by combining the singleton chunks, subject to the well-formedness conditions of Definition 3.4.1 and the locality properties noted in Lemma 3.5.1.
— By construction in Definition 6.2.1 the atomic elements of () are isomorphic to atomic(()), and by Lemma 6.2.5(3) also to .
Let () be determined by mapping tx to [tx(tx)] . Thus using Lemma 3.7.2 we have:
By routine calculations using Proposition 5.5.4.
The unit map IEUTxO is a bijection on underlying sets.
7.3. is left adjoint to
Naturality of and is Propositions 7.3.2 and 7.3.3. The proofs are by diagram-chasing. We do need to be a little careful because of the choice made in the factor function (Definition 4.2.5(1b)), which propagates to the action of on arrows (Definition 6.4.1). In the event, the diagram-chasing is all standard and it works fine.41
The counit map is a natural transformation from to 1ACS.
Consider : and () : () () and some [tx] and (tx [ ] . Then ([ tx() tx()] and
The unit map is a natural transformation from 1IEUTxO to .
Consider some arrow : IEUTxO. We must check a commuting square in IEUTxO that
Using Lemma 3.7.2 it suffices to check for each tx that
Suppose (tx ] . Then
and
as required.
(1) The functors
from Definitions 5.1.1 and 5.4.1 (for ) and from Definitions 6.2.1 and 6.4.1 (for ) form an adjoint pair. In symbols:
(2) is full and faithful (a bijection on homsets), and is full (a surjection on homsets). Thus is a full embedding of IEUTxO into ACS.42
(3) The image (X) of X ACS is in fact a pure IUTxO model — meaning that its validators examine only the input-point of the transaction passed to them, not the entire transaction — and G maps more specifically to the full subcategory IUTxO of IEUTxO (Subsection 3.8). Thus have the following short chain of maps
where on the left e denotes the trivial inclusion/embedding map (Remark 3.8.1) with right adjoint .43
(4) The image () of IEUTxO is a pure IUTxO model and as a corollary, every IEUTxO model is isomorphic via () to an IUTxO model (),
(1) The natural transformations are : 1 and : 1 from Definitions 7.1.2 and 7.2.2. They are natural by Propositions 7.3.2 and 7.3.3.
(2) By Proposition 7.2.5 the unit is a bijection and it follows that is full and faithful. By Proposition 7.1.4 the counit is a surjection and it follows that is full (this also follows from the fact that is a bijection and so an injection).
(3) This is a structural fact of Definition 6.2.1, as observed in Remark 6.2.2.
(4) From Proposition 7.2.5 and part 3 of this result.
Intuitively, ACS denotations seem to be the largest denotational class which conveniently maps back down into IEUTxO models as above (this is an intuitive observation, not a theorem). But if we wish to optimise differently and make our denotation more specific, then we can be rewarded with a tighter result:
If we strengthen Definition 4.5.1 so that an abstract chunk system is a perfectly atomic oriented monoid of chunks (Definition 4.2.5(2)) instead of just being an atomic one, then
— in Proposition 7.1.4 becomes a bijection, and
— the embedding in Theorem 7.3.4 becomes an equivalence of categories, and
— the loop illustrated in Remark 7.3.5 becomes a loop of equivalences.
Thus, the full subcategory in ACS of perfectly atomic abstract chunk systems, and all arrows between them, is the ‘properly IEUTxO-like’ abstract chunk systems.44
The bijection is just a structural fact: if by Definition 4.2.5(2a) an element X ACS factorises uniquely into a list of atomic elements , then can be identified with that list and just maps it to a list of transactions [tx() tx()] — which, by design in Definition 6.2.1, has the same composition behaviour in (X) as does in X.
Then Definition 4.2.5(2b) is exactly what is required for (X) to ‘remember’ all the -structure of X.
8. CONCLUSIONS
We have presented the EUTxO blockchain model in a novel and compact form and derived from it an algebra-style theory of blockchains as partially-ordered partial monoids with channel name communication. This builds on previous work [BG20].
We hope this paper will make two contributions:
(1) its specific definitions and theorems, but also,
(2) an idea that blockchain structures can be subjected to this kind of analysis.
Or to put it another way: we illustrate that an algebraic theory of blockchains is possible, and what it might look like.
The reader can apply these ideas to their favourite blockchain architecture, and if this were widespread practice then this might help make the field accessible to an even broader audience, ease technical comparisons between systems, add clarity to a fast-changing field — and as we have argued, it might suggest structures and tests for practical programs, as is already reflected in a recent work [BG20; Gab20b].
We now reflect on the design decisions made along the way and suggest possibilities for future work.
8.1. Observational equivalence
We touched on notions of observational equivalence in Subsections 3.5.2 and 4.3.3.
The theory of EUTxO observational equivalence is a little weaker than we might like, in the sense that not as many things get identified as one might first anticipate.
This is because a validator gets access to the whole transaction from which an input emanates — see the line for Validator in Figure 1. (This is specific to EUTxO; UTxO is more local, see Remark 3.8.1.)
This makes it hard to factor out internal structure. For instance, even if all but one of the inputs and outputs of a transaction have been spent, so that it has just one dangling input — then that entire transaction is still observable at the final dangling input. Recall Proposition 3.5.12, and consider tx Transaction such that pos(tx) pos(, so that tx and are commuting. We might reasonably wish to identify tx and tx with a composite transaction which we might write tx , but we cannot do this because a validator could see the difference.
Thus, currently the EUTxO framework can observe the difference between
— one large transaction, and
— a composite chain (i.e. a chunk; see Definition 3.4.1) of smaller ones
— even if they are ‘morally’ the same. This is not good for developing compositional theories of observational equivalence. We propose it might be helpful if the EUTxO model allowed us to limit access to the channels in a transaction, such that an input can limit validators to access only certain inputs and outputs in a transaction, e.g. by nominating positions that are ‘examinable’ along that input.45 The pure UTxO model (Remark 3.8.1) would correspond to the special case when an input nominates only itself for validators to access. Then, we would in suitable circumstances be able to switch between a single large transaction, and a composite chunk with the same inputs and outputs. Another observable of a transaction is the names of its spent transaction channels, and this brings us to garbage-collection:
8.2. Garbage-collection
Our model has no garbage-collection of spent positions — where by spent positions we mean the stx-atoms from Definition 3.4.8; see also the up-atoms from Definition 4.3.9 (a connection is precisely stated in Proposition 5.5.4).
There is nothing wrong with this; the EUTxO presentation in [CCM20] does not garbage-collect either (i.e. positions on the blockchain can be occupied at most once, and can never be un-occupied).
However, since we name our positions, it might be nice to consider garbage-collecting (i.e. locally binding) the names of spent positions, by removing or -converting them in some way. We do this in the implementation in [Gab20b].
However, the maths indicates that this does come at a certain price. For instance, consider a very simple model of finite lists of atoms in which the first atom is an ‘input’ and the last atom is an ‘output’, and we garbage-collect by removing matching atoms, like so:
Thus,
Now if we bracket the other way, then [] [] is ill-defined, and therefore so is [] ([] []). We cannot have [] because this would violate the condition that an input must point to an earlier (not a later) output (Definition 3.4.1(3); we consider relaxing this condition in item 2 of Subsection 8.6).
The partiality is no issue — chunks are already a partial monoid (Theorem 3.5.4). But, our monoid of garbage-collecting chunks would not be associative. It would still be nearly associative, meaning that () where both sides are defined. However this is a weaker property that would be messier to work with, and for now we do not need it to make our case.
(This could also be read as a mathematical hint that our uniqueness conditions are a little too strict, and that [] [] should be permitted, where the leftmost does not point to the later but instead points backwards in time to some earlier , and the rightmost points forwards towards some later — in the style of an interleaved scope [GGP15], for example. In the presence of garbage-collection this would make perfect sense, since we would expect both s to eventually get bound, i.e. ‘spent’.)
In this paper we do not garbage-collect. We leave deciding whether we should, and if so how, for future work.
8.3. Tests
A few more words on the equations in Figure 1 (IEUTxO type equations) vs. those in Definition 4.5.2 (its algebraic counterpart of abstract chunk systems).
We want the equations in Figure 1 to be short and sweet, so that the system looks simple and solutions are easy to build and manipulate.
The design parameters in Definition 4.5.2 are somewhat different: we do not mind if there are plenty of algebraic properties, because this means that we have captured as many interesting properties as possible. The adjunction in Theorem 7.3.4 gives a formal sense in which the two correspond.
(This leaves it for future work to see how these conditions could be relaxed, as discussed e.g. in Remarks 6.4.4 and 7.1.5 and Proposition 7.3.6.)
This has mathematical interest, but not only that.
As noted in Subsection 4.4.2, modern programming languages support efficient programming on abstract denotations, thus delaying instantiating to specific instances until truly necessary. Also, they allow us to express and test against properties — and equality properties in particular can be helpful for optimising transformations.
So an algebraic theory can be relevant to producing concrete working code, because:
(1) it can help structure code; and
(2) an axiom can be read both as a testable property and as a program transformation; so that
(3) the more axioms we have, the more transformations and tests are available, and the more scope we have to transform, structure, and test our programs.
8.4. Connections with nominal techniques
This paper borrows ideas from nominal techniques [GP01] and in particular it follows the ideas on Equivariant ZFA from [Gab20a] in handling the atoms which we use to name positions. We use atoms to name positions in IEUTxO models and in abstract chunk systems (ACS).
Partly, this is just using nominal-style names and permutations as a standard vocabulary. We can think of this application of nominal ideas as reaching for a familiar API, typeclass, or algebra, and there is nothing wrong with that.
The reader can find this implemented in [Gab20b], where the IEUTxO equations in Figure 1 are combined with this author’s nominal datatypes package to create first a Haskell typeclass, and then a working implementation of chunks and blockchains, following the IEUTxO model of this paper.
But in parts of this paper, something deeper is also taking place. For example:
(1) The notion of abstract chunk system — which makes up the more abstract half of this paper — depends on that of an oriented monoids of chunks from Definition 4.4.1, which depends on the notion of posi from Definition 4.3.6, whose definition depends on the permutation action. posi is a nameful definition, in the nominal sense, and it is not clear how would express it, and thus the notion of ACS, were it not for our nominal use of names.
(2) In [Gab20b] we go somewhat further than in this paper in developing IEUTxO models, in that we permit -conversion to garbage-collect spent positions as discussed in Subsection 8.2. This too is a fully nominal definition, which uses the nominal model of binding in specific ways.
Experts on nominal techniques should note that no finite support conditions are imposed; for example, there is nothing to insist that a validator () Transaction! should be a finitely-supported subset. This paper is in ZFA, not Fraenkel-Mostowski set theory.
We could construct a finitely-supported account of the theory in this paper in FM, just by imposing finite support conditions appropriately — but it would cost us complexity, and since we do not seem to need this, we do not do it. We hope we have struck a good balance in the mathematics between being rigorous in our treatment of names, and not drowning the reader in detail.
Note that finiteness conditions on sets of names are still important: notably in Definition 4.4.1(1); and name-management is key to some nontrivial results, notably Corollary 4.4.5. So there is a ‘finite support’ flavour to the maths, just not as a direct translation of the Fraenkel-Mostowski notion of finite support.
Continuing the previous remark, ‘freshness-flavoured’ set disjointness conditions like
— input(tx) output(tx in Lemma 3.4.6, and
— pos(ch) pos( in Lemma 3.5.6, and
— posi() posi( in Definition 4.4.1 and elsewhere,
are quite important in this paper.
We could have imported a nominal notation and written these #, as in ch# or #. This would not be wrong, but it might mislead because, as discussed above, we do not assume nominal notions of support and freshness. Thus, pos(ch) and posi() are not necessarily equal to the support of ch and respectively, and if e.g. and were in an abstract chunk system that happened also to be finitely-supported (a plausible scenario), it would not be guaranteed that # would coincide with posi() posi(.46
We could insist that supp() must exist and coincide with posi(), of course — but that would be an additional restriction.
8.5. Concrete formalisation
Can we implement all or parts of this paper in a theorem-prover, and use that to verify properties of a blockchain system?
This paper has a lot of moving parts, and it is not all or nothing: a user can import whichever components (IEUTxO? ACS?) they wish — though we also hope that the overall mathematical vision could provide useful guidance.
How the ideas in this paper might be brought to bear in the setting of a formal verification cannot have a clear-cut answer, because it depends on interactions between the maths, what we want to verify, the resources available,47 and what facilities are offered by a particular theorem-proving environment.
A reasonable (but naive) implementation of the EUTxO inductive definition in [CCM20] would suggest modelling positions by numbers which are essentially de Bruijn indices. The maths in this paper suggests against this:
— We want to talk about chunks. Indices only make sense in a blockchain which has an initial genesis block from which we start to index.
— We want to rearrange transactions and chunks, e.g. to talk about how they commute, as in (for example) Definition 4.3.16. With indices, a transaction in a different place is a different transaction, and potentially subject to different validation if a validator were to directly inspect its indices.
— Because we use names, we never have to worry about reindexing functions, as can be an issue with the de Bruijn indexed approach.
This is borne out by the practice: the developers of the EUTxO implementation underlying [CCM20] have explored theorem-provers and they do not reference transactions by position (even though the mathematical description in the literature makes it look like they do, at least to the uninformed reader).
What they actually do is maintain an explicit naming context. This is ongoing research, but the interested reader can find a brief description in [MSC19].
The difficulty with this hands-on context-based approach is that we end up having to curate our context of names, using explicit context-weakening and context-combining operations. These get limited, extremely tedious to formulate and prove, and clutter the proofs of properties.48
It is standard and known that maintaining contexts of ‘known names’ can get painful. Indeed, this is one of the issues that nominal techniques were developed to alleviate.
In the context of this paper, we would advise looking at how the implementation in [Gab20b] manages names and binding using permutations and the Nom binding context (which is the nominal construct that closely corresponds to a local context of known names).
So it works in Haskell — but determining the extent to which this can be translated to a theorem-prover remains to be seen. We could imitate the nominal datatypes package; there is a nominal package in Isabelle [Urb08]; and this author has written some recommendations on implementing nominal techniques in theorem-proving environments [Gab20a].49 Exploring this is future work.
8.6. Future work
We discussed future work above and in the body of the paper. We conclude with some further observations:
(1) The authors of [CCM20] map their concrete models to Constraint Emitting Machines, which are a novel variant of Mealy machines. It is future work to see whether the idealised EUTxO solutions from Definition 3.1.2 admit corresponding descriptions. For the interested reader, we can note that a body of work on nominal automata does exist [BKL14; Boj18].
(2) In condition 3 of Definition 3.4.1 we restrict inputs to point to strictly earlier outputs. This restriction makes operational sense for a blockchain, and it is unavoidable and required for well-definedness in [CCM20] because of its inductive construction. However, there is no mathematical necessity to retain it here; it would be perfectly valid and possible to contemplate a generalisation of Definition 3.4.1 which permits loops from a transaction to itself, or even forward pointers from inputs to later outputs (i.e. ‘feedback loops’). Mathematically and structurally, loops are perfectly admissible in the framework of this paper. Loops from a transaction to itself are particularly interesting, because this would remove the need for a genesis block — which has no inputs, and therefore exists sui generis in that it is not subject to the action of any validation from other blocks. So, we could insist that all transactions have at least one input, but that input may loop to an output on the same transaction.
This might seem like a minor difference, but it is not, because we control the set of validators (the injection in Definition 3.1.2), so we can enforce checks of good behaviour — even of the first transaction, which would e.g. be forced to validate itself via a loop — by controlling the set of validators.
(3) We have considered EUTxO blockchains in this paper. It would be natural to attempt a similar analysis for an accounts-based blockchain architecture such as Ethereum. A start on this is the Idealised Ethereum equations in [BG20, Figure 4]; developing this further is future work.
(4) As is often the case, in practice there are desirable features of real systems that would break our model. For instance, it can be useful to make transactions time-sensitive using slot ranges, also called validity intervals; a transaction can only be accepted into a block whose slot is inside the transaction’s slot range. Clearly, this could compromise results having to do with chunks and commutations, because these are by design ‘pure’ notions, with no notion of time. It is future work to see to what extent a theory of chunks might be compatible with explicit time dependence constraints. In one sense this temporal aspect should be orthogonal to the nominal techniques used so far, since atoms are just used as positions and we impose no finite support
conditions; however in another sense it may also be possible to usefully import notions of e.g. ordered atoms from nominal automata, as presented in [BKL14; Boj18]. In any case, it is common to find a pure sublanguage with a nice theory embedded in a more expressive and larger language with less good behaviour, as e.g. pure SML is embedded in SML with global variables.
8.7. Final words
The slogan of this paper is blockchains as algebras, and more specifically blockchains as nominal algebras of chunks. Based on the maths above, which substantiates this slogan, we can note that:
(1) UTxO blockchains can be viewed as an algebraic structure, both intensionally (Definition 3.1.2) and extensionally (Definition 4.5.1), and these views are equivalent (Theorem 7.3.4).
(2) The natural and fundamental unit of blockchain algebras is partial blockchains — what we call chunks in this paper — and chunks naturally organise themselves into monoids with extra structure.
(3) It can be convenient to address inputs and outputs by name in a ‘nominal’ style — contrast with a de Bruijn-style index (addressing a location by some kind of offset from a genesis block; cf. Subsection 8.5), or a blockchain hash.
(4) We have proved some high-level properties (some readers might call these meta-theorems). Notably: a kind of Church-Rosser property in Theorem 3.6.1; and Theorem 7.3.4(4) that every IEUTxO system admits a presentation as an IUTxO system; and that both can be presented as Abstract Chunk Systems, in senses made formal by a loop of embeddings in Remark 7.3.5. These capture global properties of how the structures fit together, which are not immediately obvious just reading the definitions.
(5) An open question is how this maths might help the blockchain community to simplify proofs, write better programs, more quickly and safely design new systems, or accommodate existing and new extensions (cf. next point). The results in this paper, coupled with a toy (but perfectly real) blockchain implementation based on these ideas [Gab20b], suggests that these things are plausible — but time and future research will reveal more, and that is as it should be.
(6) We knowingly threw out concrete structure that real blockchains need. Real blockchains have tokens, monetary policies, smart contracts, and more structure that is being invented literally on a daily basis. But instantiating algebraic structures is possible as discussed in Subsection 2.1 and indeed the raison d’être of algebra is just this: abstract, find instances, and extend.
(7) One path to applying this paper is essentially to take Proposition 3.5.12 and Remark 3.5.13 seriously and use them to design domain-specific resource-aware logics for reasoning about algebras of chunks equipped with specific features of possibly industrial relevance. These would be logics for verifying domain-specific elaborations of Theorem 3.6.1, and for tracing resources through the evolution of a blockchain. The nominal method of tracking resources (e.g. as we have seen used to label inputs and outputs and define Abstract Chunk Systems) lends itself naturally to such applications.50 Thus the semantics here, enriched with data structures of practical interest — e.g. currencies, NFTs, or other ‘real’ data coming from specific user needs — could lead to logics that are both powerful and useful, helping to prove commutativity and other resource-based properties, using logics for algebras of chunks in the style of this paper.
In summary: this paper introduces the idea of blockchain algebra, at least as applied to UTxO-style blockchains. It is reasonable to hope that this might provide a convenient target semantics for new programs and logics for building and reasoning about blockchain systems.
ACKNOWLEDGMENTS
I thank the editors and three anonymous referees for their detailed and constructive feedback: thank you for your time and input. Thanks also to Lars Brünjes, without whom this paper might not have been written. I dedicate this paper to the memory of our colleague Martin Hofmann. May he rest in peace.
REFERENCES
[Acz88]Peter Aczel, Non-wellfounded set theory, CSLI lecture notes, no. 14, CSLI, 1988.
[Bar84]Henk P. Barendregt, The lambda calculus: its syntax and semantics (revised ed.), North-Holland, 1984.
[BG20]Lars Brünjes and Murdoch J. Gabbay, UTxO- vs account-based smart contract blockchain programming paradigms, Proceedings of the 9th International Symposium On Leveraging Applications of Formal Methods, Verification and Validation (ISOLA 2020), Springer, October 2020, See arXiv preprint https://arxiv.org/abs/2003.14271.
[BKL14] Mikołaj Bojańczyk, Bartek Klin, and Sławomir Lasota, Automata theory in nominal sets, Logical Methods in Computer Science 10 (2014).
[Boj18]Mikołaj Bojańczyk, Slightly infinite sets (book draft), 2018.
[CCM20] Manuel M.T. Chakravarty, James Chapman, Kenneth MacKenzie, Orestis Melkonian, Michael Peyton Jones, and Philip Wadler, The Extended UTXO model, Proceedings of the 4th Workshop on Trusted Smart Contracts (WTSC’2020), LNCS, vol. 12063, Springer, 2020.
[CFW86] William D. Clinger, Dan P. Friedman, and Mitchell Wand, A scheme for a higher-level semantic algebra, p. 237–250, Cambridge University Press, USA, 1986.
[Gab01]Murdoch J. Gabbay, A Theory of Inductive Definitions with alpha-Equivalence, Ph.D. thesis, University of Cambridge, UK, March 2001.
[Gab20a], Equivariant ZFA and the foundations of nominal techniques, Journal of Logic and Computation 30 (2020), 525–548.
[Gab20b], Implementation of idealised EUTxO in the nominal datatypes package, https://github.com/bellissimogiorno/nominal/blob/6e9c/src/Language/Nominal/Examples/IdealisedEUTxO.hs, June 2020.
[GGP15] Murdoch J. Gabbay, Dan R. Ghica, and Daniela Petrisan, Leaving the Nest: Nominal Techniques for Variables with Interleaving Scopes, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015) (Dagstuhl, Germany) (Stephan Kreutzer, ed.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 41, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015, pp. 374–389.
[GP01]Murdoch J. Gabbay and Andrew M. Pitts, A New Approach to Abstract Syntax with Variable Binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.
[Mil99]Robin Milner, Communicating and mobile systems: the -calculus, Cambridge University Press, 1999.
[Mok17]Andrey Mokhov, Algebraic graphs with class (functional pearl), SIGPLAN Not. 52 (2017), no. 10, 2–13.
[MSC19] Orestis Melkonian, Wouter Swierstra, and Manuel MT Chakravarty, Formal investigation of the Extended UTxO model (Extended Abstract), https://omelkonian.github.io/data/publications/formal-utxo.pdf, 2019.
[Nes21]Chad Nester, A Foundation for Ledger Structures, 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020) (Dagstuhl, Germany) (Emmanuelle Anceaume, Christophe Bisière, Matthieu Bouvard, Quentin Bramas, and Catherine Casamatta, eds.), Open Access Series in Informatics (OASIcs), vol. 82, Schloss Dagstuhl– Leibniz-Zentrum für Informatik, 2021, pp. 7:1–7:13.
[Rey02]John C. Reynolds, Separation logic: A logic for shared mutable data structures, Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), IEEE Computer Society Press, 2002, pp. 55–74.
[Urb08]Christian Urban, Nominal reasoning techniques in Isabelle/HOL, Journal of Automatic Reasoning 40 (2008), no. 4, 327–356.
Notes
1This is not a criticism of the original inductive definition. ↩
2Tip: search the pdf for ‘future work’. ↩
3E.g. currencies and smart contracts are eminently compatible with our models — and most likely other as-yet-unimagined extensions too. Algebra is good at accommodating examples; how many boolean algebras, groups, or vector spaces does the average person encounter in a lifetime (whether they know it or not)? So if this maths stimulates the reader to think “Obviously this model could also accommodate X; why did the author not mention this?”, then everything will be just as it should be. ↩
4It’s not that we don’t care, or think these issues are trivial. But consider: Java disallows pointer arithmetic and presents the user with an abstraction of infinite memory addressed by uninterpreted abstract pointers. This does not imply that Java programmers believe that memory actually is infinite, or that RAM is not linearly addressed. It’s just more productive — and also actually safer — to handle memory-management as a distinct design issue. ↩
5In practice, the code of and is usually public and can be read directly off the blockchain. The cleverness of cryptography is to devise systems such that from and it is not trivial to deduce a such that will accept () — unless you already know a cryptographic secret. ↩
6When we write ‘irreversible’ what we mean in real life is so-called probabilistic finality, that the practical chances of a block append getting reversed decreases rapidly and exponentially as other blocks are added after it. ↩
7The case where we deliberately attach a block that consumes an output and introduces no fresh outputs on the new block to replace it, is in some contexts called a burn, because its effect is to destroy unspent outputs without replacing them with new ones. ↩
8So for instance, if we had an oracle that could solve the cryptographic puzzles currently attached to validators on bitcoin, then we would be able to ‘spend’ bitcoin by attaching new blocks to the chain. As discussed, in the real world these puzzles are designed to be practically impossible to solve unless you have the key. Fun fact: somewhere in a rubbish dump in Newport, UK is a hard drive with the keys to 7,500 bitcoin. ↩
9Contrast with [CCM20, Figure 3], which is truer to how an efficient implementation would actually work: it assumes an “(opaque) type of scripts” and a generic script application function ⟦-⟧ which operates on a general-purpose type Data of data, into which it is assumed that inputs get encoded. The validators-as-graphs-of-function paradigm of this paper rests on two basic observations: 1. we can identify a program-script with the function that it computes (then throw away the script and keep the function); and 2. a function can be represented as its graph () (). (We could further insist that a validator be a computable graph, but we don’t need to for our results here, so we don’t.) We spell out points 1. and 2. here precisely because they may be taken as obvious by some readers, but saying this appears to be novel in the peer-reviewed blockchain literature; and I know from conversations that either point may be novel to some readers. ↩
10...neither did ‘plus one’ when I learned to count in school, and look what comes of that in university. Basic ideas can be tricky like that. ↩
11Also called urelemente or urelements in the set-theoretic literature. ↩
12Uninterpreted means: “Pick whatever you want. We’ll never look inside it so we don’t care. Just make sure this set is large enough and has whatever structure that you need for your application, and the maths will work for that choice.” ↩
13These correspondences are not intended to be read as mathematically precise; they illustrate how a shared intuitive underlying structure manifests itself across the two different definitions. ↩
14A universe of non-wellfounded sets [Acz88] would also solve this. That might be overkill for this paper, but this might become relevant if the theorems of this paper are implemented in a universe with more direct support for non-wellfounded objects than ZFA provides. ↩
15This can also depend on which aspects of a structure we wish to emphasise. For example, and are isomorphic, as are pow() and 2: the usage chosen in context suggests which aspects of the underlying entity (arithmetic vs. ordinals; sets vs. functions) we find most relevant. ↩
16Note to experts in nominal techniques: so the support of validators, if any, is not counted in pos. See also the discussion in Subsection 8.4. ↩
17There is no claim to have created a practical blockchain implementation (there is no cryptographic assurance, for example), but the Haskell code comes out as a surprisingly direct translation of the maths in this paper, and demonstrates that this paper has enough executable content to be a plausible reference implementation, for example, within the framework of its own abstractions. In particular, the design of Figure 1 was informed by the experience of creating executable code, and having types and explicitly available, was useful. ↩
18...so does not point to an earlier validating output in txs... ↩
19...so does not validate some later input in txs ... ↩
20These diagrams are adapted from [BG20], with my coauthor’s agreement. ↩
21If we permitted loops, i.e. connections from a later output to an input that is on the same block or earlier, then a genesis block might have an input that addresses an output on the same or a later block. See Subsection 8.6(2). But for the definitions as set up in this paper, that is not allowed. Note that our definitions admit a blockchain with two genesis blocks; it suffices to have more than one transaction with no inputs. Whether this is a feature or a bug depends on the application. ↩
22Blockchains have no unspent inputs, so if composed they just sit side-by-side and do not communicate. Contrast this with chunks, for which the partial monoidal composition is clearly natural. ↩
23This condition holds trivially if , i.e. for the empty list. ↩
24A slightly weaker possibility is that () and () need not exist or not exist together, but if they both exist, then they are equal. This is the natural notion if we bind names of spent output-input pairs. More discussion in Subsection 8.2. ↩
25We really use here the fact that names can only be used to link an output to an input once. ↩
26In practice, programmers of smart contracts on accounts-based blockchains may write explicit tests into their smart contracts that double-check values of input variables at time of attachment to the blockchain, if they anticipate this might be an issue. More discussion of this is in [BG20]. ↩
27A functor that is injective on objects and bijective on arrows. ↩
28Alternative and equivalent definition: every strictly descending chain is finite. ↩
29Functional programmers, who may be used to distinguishing between types (which are primitive) and sets (which inhabit powerset types), may perceive this definition as subtly broken, since it appears to apply a type-former [ ], to a set atomic(X). This is a culture clash and is not an issue with the maths as set up in this paper. We are working in ZFA; the carrier set X is a set and so is atomic(X) (and both are equivariant); the list set-former [...] is a set-former, not a type-former. Thus, [atomic(X)] is well-defined by Notation 2.2.3(4) as the set of finite lists of atomic elements from X. ↩
30posi(f is also immediate from Definition 4.3.6. ↩
31It would be nice to write this as left()#right() or left()right(), but we prefer to trade off notational elegance for clarity and explicitness here, so we will write out our sets disjointness conditions in full. ↩
32It will take more work to prove that this is so. See the functors and which we define in Sections 5 and 6, and Theorem 7.3.4. ↩
33This can be a little subtle: if is ordered before then [:] [:] would need to be written as [:] [:]. ↩
34...so we are looking at a ‘real chunk’ here, for which utxi, utxo, and stx are defined, and excluding our extra failure element, for which they are not defined ... ↩
35Note that consists of an action on objects, and an action on arrows, and we can usefully have the former without the latter. See Remark 6.4.4. ↩
36We do not exhibit any such application of our result in this paper; we are just making the general observation. Still, it is possible that in future work our constructions might be put to such use. ↩
37This really happened. An author lifted an algebra from one of my papers, deleted crucial structure, and claimed superior generality. When the paper went to me to referee, I observed that deleting this structure also deleted all the interesting theorems. This was not necessarily fatal; but what other theorems or properties were there to replace them? No reply was forthcoming. ↩
38A comparison: when giving a denotation to , the domain of denotations could be (equivalence), ordinals (embedding), or just an arbitrary infinite set (injection on objects). All three possibilities are reasonable, depending on the context. ↩
39In fact, the only pointed transactions possible in this system are tx()@(), so we could also extract from tx. ↩
40Thus, the in the loop of embeddings in Remark 7.3.5 would weaken a mapping on objects. ↩
41Let’s pause on this ‘it works fine’. This paper is populated by structures whose definitions can be quite different, and yet which mesh together: consider Proposition 5.2.2 and Remark 5.2.3, and the adjunction here. If aspects of the proof of the equivalence follow without fuss, then this tells us that the different elements mesh correctly and with minimal friction. It might even have taken much thought by a certain author, and patient finessing of widely-separated definitions and proofs, for us to enjoy this happy state of affairs. Thus: the property of this argument that it is fairly straightforward, may in and of itself have some mathematical significance. ↩
42There seem to be various definitions in the literature of what an ‘embedding of categories’ should mean. By full embedding here, we mean a functor that is injective on objects, and bijective on arrows. ↩
43Does map to IEUTxO, or to IUTxO? Both, because we embedded the latter in the former: IUTxO IEUTxO. See Remark 3.8.3. ↩
and still have non-trivial work to do, as we see e.g. from Propositions 5.5.4 and 5.2.2. ↩
45So a validator would be passed the restriction of a transaction obtained by including only nominated inputs and outputs in that transaction, and withholding the rest. ↩
46posi()#posi() in the nominal sense would still mean posi() posi(, just because nominal freshness coincides with sets disjointness on finite sets of atoms. ↩
47Very important: a single person working alone will make different tradeoffs than a large team, and a short-term project will make different tradeoffs than a longer-term project that can e.g. afford to invest in building basic tooling. ↩
48Properties often get called meta-theorems in this field. So wherever we write ‘(algebraic) property’, a reader with a theorem-proving background can read ‘meta-theorem’, and they will not go too far wrong. ↩
49This last paper essentially says: make sure that permuting names in properties is a pushbutton operation. Once you have that, the rest should follow; and if you do not then there may be trouble. ↩
50Nominal techniques were originally designed to track resources (namely: variable symbols in inductive definitions with binding) and they have been elaborated considerably since e.g. through nominal rewriting, automata, and nominal algebra. So there is a body of theory to draw on. ↩