Modeling blockchains as a Deterministic Finite Automata

Before diving any further into this let us understand Finite Automata(FA).

A finite automaton is a modeling tool that allows us to model a computational problem.

A FA that accepts the word for. [1]

The circle with numbers within them are states. The alphabets are inputs or stimuli that can change the states. When state 0 the starting/ default state is provided with the letter f it goes to state 1. State 3 is the final/ accepting state.

Now, onto Deterministic Finite Automata(DFA).

A DFA is a FA where each state has only one next state. The example above is a DFA whereas the one below isn’t.

An example of a non-DFA

In the example above state 0 has two possible states, state1 and state 2 for input 1 and 0 or 1 respectively. Such an FA is called a Non-Deterministic Finite Automata and will not be used as a modeling technique.

Blockchains as DFA

Facts about blockchains that will assist in modeling it as a DFA.

1. For a specific state, an input will always produce the same output.
2. For this modeling, the blockchain is considered to be forkless because a forked blockchain will violate fact 1 and will not be a DFA.
3. A blockchain modeled in such a way can also be described as a Moore Machine.

Let M be the model of the blockchain such that

M = {S, S(0), I, Ftransition}

State Domain S

A state domain is the current state of a blockchain.

Initial State S(0)

S(0) is the genesis block of a blockchain. Or in other words the starting state. Each block will point to the one before it but the genesis block points to nothing.

Hence, S(0) = null or empty

Input Alphabet I

An input that will change the state of the blockchain is an input alphabet.

Transition Function Ftransition

The transition function will handle state transition when an input I is applied to a current state S. The new state as given by the function will be S1.

Conclusion

The above is an easier and simpler way to represent blockchain as a DFA. The modeling does not take into account block, block headers, and more. For more comprehensive modeling read the Polynetwork’s whitepaper. That is where I was introduced to this modeling for the very first time. This article is the simpler, easier, and maybe even incorrect way of how I remember what I read.

References

1. Introduction to compilers and language design by Prof. Douglas Thain University of Notre Dame. (Where I got the first figure from, and where I revised about FAs, DFAs, NDFAs)
2. Polynetwork’s whitepaper.