The Infinite State Machine

Blockchain: the Infinite State Machine

Introduction


Blockchain: the Infinite State Machine

Posted by on .
Featured

Blockchain: the Infinite State Machine

Posted by on .

morpheus-003

Part 1: Blockchain: the Infinite State Machine

tl;dr - blockchains are fundamentally systems for managing valid state transitions. To get the best from blockchain, the problem should first be defined in terms of a state machine.

Satoshi's seminal innovation in his Bitcoin whitepaper has inspired a surge of derivative invention, but also an unhealthy dose of technology hype over the past few years. It is then important for us to be able to stay grounded in technological reality and apply good mental frameworks to both understanding and defining a problem before we attempt to fit an appropriate solution.

Whatever blockchain technology you might be considering, the goal of this post is to equip you with a greater understanding of its fundamental nature so that it can be more critically evaluated. I hope that by the end of this post you will have gained an appreciation of the concept of 'state machines', and why it is useful to think about blockchain technology as a method to manage valid state transitions.

Electrical and software engineers will be immediately familiar with this idea as they would have come across discrete time systems and state machines in their university studies, however it will be a tantalisingly new concept to many others.

As an engineer, I like to solve a problem exactly once. So here it is: blockchains are, fundamentally, systems for managing valid state transitions.

Thinking in systems: discrete time and state machines

Okay, so what is a state transition? What is a state machine?

First, let us define what we mean by a discrete system. A discrete system is simply a system which has a countable number of well-defined states. Discrete systems are everywhere. They're all around us. Even now, in this very room (alright enough with the Matrix references!).

One can think of discrete systems as being either deliberately designed and managed (such as a traffic light), or as being constructed to be placed over the top of a more complex system in order to provide some structure. This enables the underlying complexity to be better understood, and thus build new things upon its underlying behaviour.

Consider for example the days of the week: in physical reality, daylight is a continuous sinusoidal transition with any moment in time virtually indistinguishable from the next. However, humans clearly define two binary states: night and day. If you consider the days of the week more broadly, any arbitrary period in time is made up of an infinite number of moments (any finite thing is made up of an infinite number of things). However if we overlay a calendar, any time during the week is now very clearly defined as being in one of seven distinct states, known as 'days'. The days of the week form a unidirectional ring topology. They are a string of items linking back into a loop, meaning that only certain state transitions are allowed, e.g. Friday -> Saturday, but not Friday -> Monday. Calendars are incredibly useful, and when globally defined such that everyone uses the same model, we can build upon this structure to manage complexity and make even more useful things.

We interact with discrete systems every day, but while it is not such an expressly used paradigm, it can often be very useful to think in terms of a discrete set of (valid) states for a given system. And so, any abstract system that manages the transition between valid states is referred to as a state machine.

Let's look at a simple example of another such 'overlay' system designed to manage the transition between valid states:

State 0 (starting state):
I have some money and a shopkeeper owns some T-shirts.

State 0 in preparation for a state change:
I want one of the T-shirts and plan to make a state transition to obtain one. Let's consider our options for making the transition to the next state.

State 1 (option A):
I steal the T-shirt and make a dash for it. This new state where I obtain the T-shirt but do not pay for it is invalid according to the rules of the system (the laws governing commerce and trade). Let's say in this case that the shopkeeper grabs me, takes back the shirt, and throws me out of the shop.

State 1 (option B):
I initiate a transition to a new, valid state by paying the requested amount and taking possession of the T-shirt. At the finalisation of the financial transaction, the state change has completed.

One could argue that stealing the shirt and getting away is also a valid state. This is completely true on one level, but the point is that the resultant state is not valid according to the rules and intention of the governing system. Modelled as a state machine, such a transition is invalid. Under the rules-based system of law and commerce, a valid state transition is for me to pay the requested amount in exchange for taking ownership of the t-shirt.

Our example can continue:

(Assuming State 1, option B):
State 2 (option A):
I discover the shirt has a flaw. Under our rules-based system, we in fact don't revert the state (as each state is always unique due to the time-respective nature of the real world), but instead we make a new, valid state entry: one where at some time in the future I return the shirt and a new transaction is made - a return for a refund. This is a valid state transition because the rules of the system account for my ability to return goods that are not of merchantable quality. In the case of a dispute, we can resolve to a valid state through some pre-agreed mechanism (e.g. a legal judge or jury).

State 2 (option B):
The shirt is fine and I continue happily enjoying my new purchase while the merchant considers to use the funds to buy more shirts to sell.

And so it goes.

This is an example of a state machine: an abstract system that has a set of rules governing the transactions / transitions that occur within that system.

Practical blockchain definitions:

Now that we have a little more intuition for state machines, let's look at some more formal definitions that we can use in our mental framework for blockchain problem-solving:

Finite state machine:

  • A system managing the orderly transition between a finite number of known abstract states. Each state is labeled, but is irrespective to time (i.e. future states can be the same as previous states). State relationships have a pre-configured graph structure (such as a ring topology or matrix). Example: traffic light.

Infinite state machine, or state transition system:

  • A state machine with a starting state, but no end state. Each state is valid and countable, but infinite. Each new state is typically unique. State relationships are not necessarily known due to complexity (e.g. cellular automata). Example: the orderly flow of vehicular traffic.

Blockchain:

  • A (centrally controlled) infinite state machine with a regular transition time. Uses cryptography to immutably link new states to the chain of old states ever block time period (discrete system). States are counted, unique, and are arranged in a directed graph structure (that is, a single in-line chain). Example: double-entry book-keeping.

Distributed blockchain:

  • A blockchain using consensus methods for agreeing on each new state in a distributed, peer-to-peer network. States form a tree structure given the possibility of valid states according to the rules of the system that are not agreed by all participants, resulting in a fork. Example: Bitcoin.

  • My friend and fellow blockchain enthusiast Nick Addison, (now CTO of Agridigital), gives us a similar working definition of a (distributed) blockchain:

    "A peer-to-peer, append-only datastore that uses consensus to synchronise cryptographically-secure data."

I've attempted to structure these definitions so that each builds upon the last and takes on more specific properties. This gives us a path back to a more fundamental definition that we can apply.

Generally, our final definition of a 'distributed blockchain' is what most people understand a blockchain to be, and Bitcoin is the prototypical example. However, in the wider class of problems we wish to apply blockchain technology to, we sometimes need to revert to a higher, broader definition in order to fundamentally understand the problem before we embark on designing the solution. Thus the path back up the definitions becomes useful.

Segmentation between time-respective and time-irrespective state machines

One other useful segmentation we can apply is whether there is a need to keep an internal clock. For the traffic light, there is no need; a red light at time _t_1 is the same as a red light at time _t_2. However, with our T-shirt example, there is clearly a need to maintain a forward direction of causality.

Adding this time-series element and incorporating the history of the state transitions opens the door to blockchain solutions encompassing provenance and identity. These use cases specifically care about the history of the data, in addition to whether or not the next (proposed) state is valid.

Conclusion

Blockchains are simply an engineering implementation of something more fundamental - that of a rules-based state transition system. However, most technology solutions proposed in the wild do not apply these useful formalisms, potentially leading to unnecessary debate and hindering the technical discourse.

Perhaps blockchain is the wrong word for all this stuff; after all, 'blockchain' really just describes the underlying structure of the data. It may be more appropriately called a 'cryptographic state machine', but as @trbouma has rightly pointed out: that's a whole 5 extra syllables.

View Comments...