This article builds on the ideas and techniques from the article ‘Finite State Machines in Script’ written by Dr Craig Wright.
In computer programming there are usually many different ways to solve any given problem. Every programmer has their own preferred methods of attacking a given type of problem, and even their own methods of implementing certain types of solution. In this article, Dr Wright outlines several ways to build an automation structure known as a ‘Finite State Machine’ using Bitcoin as the computing interface.
Finite State machines
At it’s core a finite state machine is exactly what it’s name suggests. A programmatical machine that has a finite number of states, each of which engenders different behaviours from a given set of feedback, and each of which transitions into a defined ‘next state’ for a given sequence of events occurring.
To give a simple example of a Finite State Machine, let us look at a simple movement detecting light. The light starts in the Off State. When the switch is turned from off to on, it transitions into the lighting state and starts a count down timer. After a given period of time, it transitions to scanning state with the light off. The light will continually transition between these two states based on the detection of movement until it’s switch is turned off at which point it goes back into OFF state.
As shown, this finite state machine has just three states, with different events acting as triggers for transitions to occur.
These basic types of Finite State Machine live all throughout the modern world, and most people would interact with many of them on a daily basis without ever realising. Ovens, phones, cars, televisions and more are all driven by these powerful programming constructs.
With Bitcoin, we now have the ability to build these state machines in such a way that the state transitions and management of datum is performed by the Bitcoin network using transactions as the state change drivers. A given set of conditions are fed to a UTXO which contains the state machine script. In this way, a live FSM can be shown a given set of inputs, which can be evaluated against a set of possible output transitions, and the transaction will only return as spendable if all the conditions are met.
Looking at our example, the status of the FSM is held in a UTXO that resides on the Bitcoin network, When the light is in the Off State, the redeem script for the UTXO would need a spend script that provably showed that the switch had been turned on to be spent. This could come in the form of a hash that can only be generated by the toggling of the light switch. If the transaction sees this hash as an input, it knows that the light switch has been set to On and allows itself to be spent into a new UTXO with an updated redeem script defining the state as ‘Lighting State’ and which looks for either a transition of the switch back to Off, or a for the timer to reach zero. The controller that runs the FSM would turn on the light using a relay and start the timer. The timer would cycle through a hashtable, giving a new hash to the controller for every second the light is on. When the correct hash is found, this is the end of the timer and the UTXO can be spent into the Scanning State. From here, the scanner must return a hash derived from a true condition to go back to the Lighting State, or the switch must return an off condition to move the light back to the Off State.
Each update to the FSM state is captured in a transaction allowing the full history of the machine’s operation to be mapped on-chain. The FSM runs whenever it has the funds to pay for its state transitions and simply stops when it runs out. Once the correct transition state has been found, the FSM simply waits until it has funding to pay for the next transition.
The device running the FSM can validate its own transactions or send them to a validation service. The service would process millions of validations a second, automatically sending any transactions that resolve as true onto the network for settlement. In this way, the management of thousands or millions of devices can be managed by distributed worker farms, each testing millions of transactions for validity and only allowing those that pass the test to be sent for mining.
Fuzzy State Machines
Finite state machines are fantastic for things such as appliances, and devices which have simple operating parameters and are expected to act in an exact and repeatable way every time. As we move more towards Artificial intelligence, we need to create ways for machines to act in ways that are not only creative, but optimised for their task. When you have a state machine that can transition to thousands or millions of valid states at each point, this becomes something much more achievable through the use of a Fuzzy State Machine (FuSM).
A Fuzzy State Machine is different to a Finite State Machine in two key ways:
1. A FuSM can be in many states at once
2. A state’s influence over the final behaviour can be defined as a gradient
This means that the outcome of the Fuzzy State Machine can be defined by a small number of states but derive from those states a very large number of possible behaviours and even allow it to behave in new ways each time it is presented with the same conditions.
An example of this could be an adaptive lighting system for an office building.
The lobby controller might exhibit certain behaviours to promote the enhancement of the mood of its workers, using tonal lighting to change the way people feel. In the morning it might use a high kelvin blue/white light to elevate people’s awakeness, and transition to a warmer white or even orange later in the day.
The system might have a camera that can see the lobby and count both the number of people moving through and the number of people who have stopped moving either to talk or wait in the lobby zone. The behaviour might have a slower feedback loop as it dims, meaning that if there has been enough activity for high brightness to be activated, the lobby might take a reasonable amount of time to transition back to dim, so given the same set of feedback (10am with nobody in the lobby), the FuSM driven lights can have two very different behaviours, and given enough gradients of colour and brightness, an active lobby would always look different. As you can see, from two simple inputs (time of day, number of people) we are able to create a complex and nuanced set of behaviours, giving a normally sterile space a sense of animation and life.
Why in Bitcoin?
State machines are one of the oldest ways of programming systems that operate in different modes for different sets of inputs. The Bitcoin scripting language gives us ways of building FSMs and FuSMs which offer developers access to massively parallel processing of state information and outcomes, allowing service providers new and more efficient ways of calculating information, managing the flow of that information between themselves and their users, and attaching that flow of information to financial outcomes that settle as Bitcoin transactions.
As developers learn these techniques, expect new applications to emerge for Bitcoin that are smarter, more efficient and cheaper than anything on the market today.
New to Bitcoin? Check out CoinGeek’s Bitcoin for Beginners section, the ultimate resource guide to learn more about Bitcoin—as originally envisioned by Satoshi Nakamoto—and blockchain.