How to implement Finite State Machines into a CC

jl777
jl777
Oct 24, 2019 · 4 min read

First a brief review of what a Finite State Machine (FSM) is https://medium.com/@mlbors/what-is-a-finite-state-machine-6d8dec727e2c

https://ucsb-cs64-s18.github.io/lectures/CS64_Lecture16.pdf

There are many other resources on what a FSM is and what they can do as it is a well established field. The important thing to note is that FSM can be mapped into a transactionalized CC. What that means is that with a single CC, unlimited numbers of different FSM instances can be defined and used.

I will try to show a very simplistic example to illustrate what a blockchain FSM CC would be like. Since the “events” that can happen can be an arbitrary one, the possibilities of what can be handled are vast. Also notice that once the FSM CC is done, then there is no need to make any new CC modifications to get a new FSM instance. It isnt quite a turing machine, but the FSM has enough power for a lot of the decentralized applications running on the blockchain.

At the high level, we need to define the FSM, this will be done by storing the state transition table in an opreturn. The size limit of 10kb will limit the complexity of any specific FSM, but by allowing an FSM to refer to other FSM, it is expected that any level of complexity will be able to be defined in 10kb.

All the FSM instances will need to keep track of its current state, with each state transition denoted on the blockchain via a transaction of some sort. It could be that there will be some side effects that are defined that will also happen, but they also need to have a blockchain event to allow all nodes to validate the current state of all FSM. Rather than require all nodes to keep track of all states of all FSM, each FSM instance will be required to update the current state with each transaction. Then as long as validation makes sure it is the proper state value, there is no need for any node to store the current states.

We thus have the state transition table that defines the FSM. In that will be specific events and side effects that happen (or are triggered) as the FSM instance changes state. Each event and side effect, will need to have a verifiable blockchain txid.

Let us start with a milestone payment release FSM. When the FSM instance is created, it is funded with 100% of the funds for completion of all the milestones. As milestones are achieved, a specified percentage of payments are released. In the event that the next milestone is not delivered before the expiration time, then the initial funder of the FSM can reclaim all the remaining funds.

The exact number of milestones and percentages released at each milestone and expiration time for that milestone, should all be part of the FSM definition. Additionally, most FSM will need some external (to the blockchain) events to trigger the release of the milestones, so we need to connect the FSM instance to specific oracles CC in the FSM definition. That means the required oracles need to be setup before the FSM instance is created.

Substituting the specific txid of an oracle does not change the FSM state transition table at all, other than having the exact oracle txid that is needed. For such things, it can be put into the FSM definition as a variable that is defined at FSM creation time.

To be clear, there is an FSM template that defines the state transitions, and this definition does not need to include all the details. The finalized FSM instance of course needs all the details resolved when it is created (funded). By having a standard interface between oracles and FSM instances, and also FSM instances and FSM instances!, we can create very powerful combinations. However, let us first complete the milestones payment FSM example.

define milestones FSM template

create required oracles

create milestones FSM instance with oracle txid specified, along with funding and percentages.

Now, the FSM instance will be dormant until a state transition transaction is used to spend the appropriate percentage of funds. All the nodes validate this spend against the FSM template and creation parameters, including the next state.

Now that we have the context of a specific FSM instance, we can also see that given a FSM creation txid and each state transition txid, we have blockchain record of a specific FSM reaching specific states. What that means is that we can define a set of standard states and then have other FSM accept as their input events, specific state transitions of other FSM.

I will leave to the reader to think about the possibilities this nesting of FSM will allow to achieve.

In addition to input events from oracles and other FSM, it makes sense to have various blockchain specific data to be an input event. For blockchains with DTO, the price of whatever is supported can be used to trigger events. Specific blockchain heights, unspent status of a utxo, balance of an address, total reserves the system has for pegs, etc, etc. Basically whatever is available to the blockchain as verifiable data, can be used as an event that causes a state transition.

Another thing that a FSM can do is have a predefined side effect happen on a specific state transition. This event can simply be the spending of locked funds, but that can be constrained further to have a specific destination, or a specific value can be written to an oracle, and in a crosschain environment, the initial transaction of the crosschain sequence can be the side effect. It seems possible for the side effect to just be some internet GET/POST request, which in turn can be devised to trigger external events. This however wont have an execution guarantee and also might end up being saturated if there are a lot of nodes, but if these are not significant issues, then it can be considered.

Of course, the initial implementation will limit itself to the 100% blockchain verifiable events that dont have much complexity to implement.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade