Finite State Machines in Script

This note provides methods for constructing deterministic and non-deterministic finite state automata in Bitcoin Script. The “best” method produces a one-to-one relation between the definition and the state table of the automaton. An important feature of the technique is the absence of nested IF clauses.

In this post, I seek to start introducing people to the basics of the Bitcoin Script language (a Forth-like language) and how it can be used in the creation of a new type of computation.

1. Introduction

Certain programming problems are difficult to solve procedurally even using structured code, but simple to solve using abstract finite state machines (FSMs) [1].

For example,

    • a compiler must distinguish a text string representing a floating point number from an algebraic expression that might well contain similar characters in similar order;
  • a machine controller must select responses to pre-determined inputs that occur in random order.

Such problems are interesting as a program that responds to indefinite input is closer to a “thinking machine” than a mere sequential program. Thus, a string that represents a floating point number is defined by a set of rules; it neither has a definite length, nor do the symbols appear in a definite order. Further, more than one form for the same number may be permissible — user-friendliness demands a certain flexibility of format.

Although generic pattern recognition can be implemented through logical expressions (i.e. by concatenating sufficiently many IFs, ELSEs, and THENs), the resulting code is difficult to parse, debug, or modify. Such an approach is highly unstructured.

Programs consisting mainly of logical expressions are often slow as many processors dump their pipelines upon branching [2]. Using a series of Bitcoin Script to solve each possibility in parallel, it leads to a different process and dynamic.

Bitcoin Script can be implemented as a well-structured language that encourages natural, readable ways to generate FSMs. The present note describes several high-level Bitcoin Script implementations.

2. Case

A puzzle can be used in Bitcoin Script in conjunction with a key for the payment based on a series of output steps. Where oracles are trusted or at least share-known keys, the system allows for input and output to be created between systems and/or devices.

For instance, if we consider the common task of inputting numerical input, a poorly formatted system and program allows for the user to enter the entire number before informing him that he typed two decimal points after the first digit. A friendly program, by contrast, refuses to recognise or display illegal characters. It waits instead for a legal character or carriage return (signifying the end of input). It permits backtracking, allowing erasure of incorrect input.

Using the alt statement, in Bitcoin Script, a switch or case statement can be simulated.

A state table.

An example of an FSM is defined in Wikipedia:

http://en.wikipedia.org/wiki/Event-driven_finite-state_machine

An example of an FSM is defined in Wikipedia.

Here, the use of values stored in the alt stack allows for the creation of a switch or case statement.

A switch statement is a more structured way (than multiple if-else statements) to express conditional logic in C-like languages. It usually looks something like:

A language system that converts case statements into alt statements in Bitcoin Script simplifies the process of creating FSMs.

It allows us to have a simplified means of creating Bitcoin Script case statements:

which is semantically equivalent to cascading if statements:

Such a form of implementation has many uses. For example, we can use it in the creation of policy contracts.

evaluate policy-holder-age also policy-holder-sex also smoking-flag
 when 20 thru 40    also "F"  also ANY  perform young-female-policy
 when 65 thru 999   also "M"  also "Y"  perform old-smoker
 when other                             perform all-other-cases
end-evaluate

In such an FSM example, the “preform” state would be a token sent to a start oracle or agent. It is defined as a deterministic switch.

The implementation of a transition table becomes a useful method for programming Bitcoin Script. It is straightforward in Script to define and program something that resembles a tabular representation. Each row corresponds to a possible input.

From the current state of the Agent/Script, selecting a column that specifies a cell that contains the subsequent action to be undertaken is followed by the corresponding state transaction. From a programming perspective, the distinction between an FSM and a jump table is that the FSM maintains a state variable his current value specifies from which row the next input will select an action and transition. As such, a mini compiler for FSMs can be programmed simply to create the desired outcome in Bitcoin Script.

We may then create more complex algorithms such as the one given in the example above. In the example, code can be determined that increases payments on successful results or reduces the payment when things are not favourable.

The agent would take the initialisation payment and output and reset on a repeat.

We can see the example defined in a state table below:

3. Fuzzy State Machines

A means of reducing the predictability of the AI behaviours is to allow an AI agent to combine multiple behaviours at the same time — which is achieved through the use of fuzzy logic to implement a Fuzzy State Machine (FuSM). It differs from binary logic in that states in an FuSM are not restricted to being on or off; instead, they can hold an intermediate value.

So at any point in time, more than one state may be active and to some degree on and off. If we go back to our police-character AI in the open city game, there may be a chasing-the-player state which can be combined with either the on-foot state or the in-vehicle state.

Counter-intuitively, such an approach can reduce the complexity of the Script state machine, while adding more complexity to the behaviour. A FuSM will typically require fewer states, due to the possibility of combinations. Utilising a Fuzzy State Machine allows the combination of actions that can be less deterministic and predictable.

The engine code providing the means to change states based on fuzzy logic is more complex than the straightforward code needed for binary decisions. But, assuming that it is implemented in a suitable manner, the state machines can be expanded upon, or rearranged, with no changes required on the engine.

An approach for converting a deterministic FSM into a non-deterministic FSM is to simply use a random number generator to select a triggered rule. It may not be necessary to implement a deterministic finite state machine to have a perceived level of unpredictability; the same can be achieved by a system or object that has a large number of defined states and a complex mesh of transitions, giving the appearance of being unpredictable.

Finite state machines are a simple and effective artificial-intelligence technique for controlling a system and providing the appearance of intelligence. In some cases, the perceived appearance of intelligence is more important than the actual intelligence, and it is more important that FSMs are able to provide such a perception.

Randomness can be seeded through block hashes and depth with the addition of address and value input and a hash randomisation process. After a value has been “randomised,” the 8th digit, for instance, of the hash can be evaluated in Script as a FuSM.

A further example would be the implementation of a “Range” [3] function where the case is decided in the value of the hash lying within a determined range.

4. Why Bitcoin FSMs

FSMs and even FuSMs are simple, and can be predictable (that is, a deterministic FSM; as noted, an FuSM would add a degree of randomness). In each case, given a set of inputs and a known current state, the state transition can be predicted, allowing for easy testing. In an FuSM, the state can be determined and tested probabilistically.

Due to their simplicity, FSMs are quick to design, quick to implement, and quick in execution.

FSMs are an old-knowledge representation and a system-modelling technique, and they have been around for a long time; as such, they are well proven even as an artificial-intelligence technique, with lots of examples to learn from. And it is easy to transfer from a meaningful abstract representation to a coded implementation.

Bitcoin Script takes things from a simple and straightforward approach to defining finite state machines. The implementation of a mini compiler that transforms the tabular representation of an FSM to Script allows for the simplified creation of smart contracts. Extended, such an approach could be implemented allowing any object-orientated language to be converted into Bitcoin Script. Such an approach can be implemented on both deterministic and non-deterministic FSMs. In non-deterministic ones, we use additional information beside the current state and current input to decide on the next transition. Such additional information can be anything from block height to calculated random values.

An FSM that passes over an exponent field in a string that could be a floating point number is represented in the state-transition table above.

As can be noted, the creation of a system to convert simple state tables into more complex FSMs greatly increases the value of Bitcoin Script, and allows for the creation of complex smart contracts.

Example: Quake

The full life cycle of a Shambler monster from Quake is defined below.

A Shambler is a monster entity from the single-player component of Quake. Its mission in life is to kill the player, once it is aware of the player.

Example of sub-states: the monster can only perform one attack per execution of the attack state; Melee — close, Missile — far, depending on inputs. We can use a random number in Melee to add unpredictability.

    • Blue: states.
    • Orange: triggers.
    • Black: entry and exit point.
  • Arrows: state transitions.

Each monster object, for instance, can be defined as an agent/oracle, and in such a manner, a series of parallel scripts could even be used to create a Quake Computer Game through the implementation of a series of layered/hierarchical FSMs.

A further example is the full life cycle of a Rocket from Quake:

A Rocket in Quake is fired from the Rocket Launcher weapon which may be possessed and operated by a human player.

    • Blue: states.
    • Orange: triggers.
    • Black: entry and exit point.
  • Arrows: state transitions.

Each agent runs a script. It in effect creates a system similar to objects in OOP forms of coding.

Parallel Code

In the Shambler example, we can send a series of payment-channel-based communications back and forth between the parties. Code can be included that allows for the spawn state and then the initial-move state. At such a point, the system starts acting as a payment channel. And if-then conditions determine whether the move state or the die state occurs. Where the move state is set to send information to the touch state, a payment channel is used that is based on an nSequence update between the parties.

A fairly standard concept of a Bitcoin payment channel is linked in an image below:

Transactions are only immutable when they have been sent to a miner. That is, if we have Alice and Bob interacting, and Alice is seeking to run her programme on Bob’s server, each iteration is an updated version of the protocol used in the computer programme, such as the one in our Quake example.

The input from one transaction can be used in the calculations of a new under-broadcast transaction.

Each of the simple steps updates the last nSequence time value, and allows for a series of transactions between the parties that will eventually settle. In the context of a game, we could have a series of updates that are replaced one by one allowing concepts such as shadowing to be built into Script.

At any particular time, we have a series of templates being updated between the parties.

It can be unidirectional or bidirectional, and it can involve updates using secured information so that Bob and Alice can only act sequentially. One example of such a system would be to integrate a hash chain allowing Bob and Alice to update an index in order using a hash puzzle to prove that no transaction is out of order.

As each transaction is sent, the nSequence values are updated — which leads to miners replacing the previous version if they see it. When signed using a series of hash puzzles, incremental payments, or even a dual signature, the system is safe. Alice could, for instance, send to Bob’s server using a two-of-two signature scheme. Alice sends a partially signed transaction to Bob in CTx1, which is then replaced with a further series of partially signed transactions (CTx2 — CTx4…) that consist of updated data and nSequence numbers.

Periodically, Bob’s server will save the data by signing the last transaction in sending it to the blockchain. Alice cannot cheat, and she does not have a completely signed version.

The result is one of the simplest ways of looping a Bitcoin transaction.

Later in the year, I will explain the use of OP_CodeSeparator, and once you start to see what it does, you will understand how powerful some of the methods can be. Luckily for us, nobody managed to grasp any of it, and many called it all a fraud allowing us to file a number of patents on topics that would have been available freely had I not been attacked.

Many transactions at once…

What many people fail to grasp is that Bitcoin transactions can also act in parallel with multiple transactions running in multiple parallel channels. That is, we can code systems in the same way that CuDA-based scientific programmes or GPU games are developed.

Looking at some early Forth coding techniques, we can embed multiple sets of data in multiple transactions.

Transactions can be used to immutably store any data and as a series of linked functions that can run individual components that are stored and accessed on the blockchain. Unfortunately, far too many people have been trained and brought up on the concept of code that does not thread. In particular, the methodologies used within Windows and Intel-based systems are incredibly different to those within Bitcoin and older systems — many of which ran across many parallel systems and processes.

The concept of looping within Bitcoin incorporates both unrolling as occurs in GPU-based compilation now and running multiple threads in parallel. Importantly, if we take something as simple as a for-each loop, we create the concepts by sending it back and forth between elements. It can even be done in an individual wallet. If we take the wallet itself as the programme, we can utilise a variety of both online and offline calls to securely create input and output signals that link to transactions.

We can imagine our for-each loop waiting for input for the wallet. Each time the user hits a particular key, information is sent back to the wallet that tests a statement. It could be conducted on the user’s machine or even on a remote machine. For instance, the user types in a particular password which is securely sent to a remote server and validated against a hash-puzzle solution, to see whether it is in the required element, where the system can give different results and continue based on input or end.

We could, for instance, have a transaction that collects and updates information on a IoT system that monitors energy use. It could collate information from multiple servers and agents either by direct communication or by monitoring other transactions on the blockchain and collating information from within the same. The in-state could be writing a payment to an energy company or turning off the device.

I would recommend people have a look at the Starting Forth site:

And:

http://galileo.phys.virginia.edu/classes/551.jvn.fall01/primer.htm

The true reality is that Bitcoin is far more powerful than people imagine. In the coming weeks, I will start to detail a number of simple Forth-like instructions and lessons involving Bitcoin Script.

Notes

[1] E.G., A. V. Aho, R. Sethi and J.D. Ullman, Compilers: Principles, Tools and Techniques (Addison Wesley Publishing Company, Reading, MA, 1986); R. Sedgewick, Algorithms (Addison Wesley Publishing Company, Reading, MA, 1983).

[2] J. V. Noble, “Avoid Decisions”, Computers in Physics 5:4 (1991) p 386.

[3] http://dxforth.mirrors.minimaltype.com/miser.html



Never miss a story from Craig Wright (Bitcoin SV is the original Bitcoin)