A codification scheme for state machines
We define a codification scheme for the states of deterministic finite automaton (DFA) [1]. Contrary to usual practice, the codification itself is machine-readable, i.e., there is an algorithm associated with it that can dynamically determine the state of the machine. Such a codification is well suited for a distributed implementation of a finite state machine, for example the blockchain implementation described in [2, 3]. A coupon bond will be used as an example of the use of the technology through the paper.
Background
A DFA [1] is a mathematical model of computation conceived as an abstract machine that can be in one of a finite set of states, and can change from one state to another (transition) when a triggering event or condition occurs. Its computational capabilities are more than those of combinational logic but less than those of a stack machine. In addition, although not essential to the structure itself, it can carry out a given set of actions while transiting from one state to the next.
In the conventional way of regarding such a machine, states are defined statically (a priori) and represent some particular configuration of the system or have some particular meaning, for example they can be given a set or names, be associated with a set of tags, or with a set of unspent transaction outputs (UTXO) as proposed in [3] for a blockchain-based DFA. This is enough for the system to work, since the (output of) computation itself is determined by how the system moves between states while it accepts the chain of inputs.
In this sense, a DFA (i.e. the sets of states, transitions, etc.) is not unique, and two DFA can be equivalent, i.e. produce the same output for each given chain of inputs, even though it is possible that the interpretation a priori conceived for the states is very different (say they are deployed in different physical machines, or conceived for solving different problems). This also leads naturally to the concept of DFA minimisation [4].
Although the static determination (tagging) of states is enough for the abstract functioning of the state machine itself, and enough for many problems in which only the output of the calculation is relevant, there are cases in which the meaning of the states themselves is of practical importance and cannot be inferred from the tags of the states, for example because it is purposely hidden for privacy or confidentiality reasons. An example of this is the system described in [2], in which the computation is distributed and carried out by agents which (purposely) do not have complete information on the system. In this cases a dynamical determination of the state of the system is necessary.
The main invention in this paper is a codification scheme which allows the dynamical (on-the-fly) determination of the state of a DFA, for example (but not exclusively) those associated with the (distributed) execution of a contract as described in [2]. For the description and illustration of the codification scheme we will use as examples a coupon bond and a perpetuity, although the invention is by no means limited to these examples.
A coupon bond is a debt obligation with periodic interest payment (coupons) that the holder receives from the issuance of the contract until its maturity, when in addition to the last coupon the principal of the bond is paid as well. In the last part of the paper we will also consider a perpetuity, which is a stream of payments with no end, i.e. the coupon payments continue (in principle) forever. In practice, due to the effect of (positive) interest rate compounding, at some point the amount of the coupons is of no practical significance, so that the (discounted) value of the contract is finite.
Straightforward specification
A DFA consists of the finite sets {S, I, t, s0, F}, representing respectively the possible states (S), inputs (I), transitions (t), initial state (s0), and final states (F), also called accepting states. In addition, a set of actions (a) can be defined, these represent side effects of the execution and do not determine the output of the computation.
For the description and illustration of our codification scheme we will consider a 3-period coupon bond. The elements (and notation) of the DFA that we will consider for such a contract can be (statically) defined as given in Tables 1 to 3. Note that the initial state is designed by S in our notation, and the accepting states are F0 and F1.
Once these elements have been defined, the functioning of the system can be completely specified [5] by the so-called state transition table, in which the current (initial/from-) state of the system (rows) together with the appropriate input (columns) determine, according to the table, the next (final/to-) state of the system as well as the actions to be carried out in parallel to the transition; for our example it is given in Table 4. Note that the execution is understood to start in the initial state (S), and the only possible final (accepting) states are F0 and F1. Since these states mark the finalization of execution, i.e. there is no transition associated with them, they can be omitted from the rows of the table. An alternative format for the transition table is given in table
Another (equivalent) way of specifying the functioning of the state machine is the so-called state diagram [6], in which the states of the system are represented by blobs, the input and actions are given by the attached labels, and the transitions are represented by the connecting arrows; for our example it is given in Figure 1. Note that the final (accepting) states F0 and F1 are, by convention, indicated with a double line for the blob. For simplicity, since they are not relevant for the execution of the system, the actions have been omitted from this diagram. The meaning of the dashed box (recurrent states) will be clarified below.
As stated in the background section, although not strictly necessary for the functioning of an abstract DFA, a dynamical determination of the state of the system which is both human and computer readable can be a practical necessity and constitutes the main invention described in this paper. Each state is characterized by a unique set of conditions that either do or do not ensue, or are irrelevant for the particular state. Each condition must be something explicit and testable, i.e., there is a definite (computational) way to tell if the condition ensues or not.
In our example this can be achieved by the set of conditions presented in Table 5, in which the states to be tested are given in rows and the conditions we have defined are given in columns. Each t condition indicates whether a particular date has come (for example the condition denoted t0 means t > t0), and each ci (or p) condition whether the corresponding payment has been made. Note that the payment of coupons (or principal) which are not yet due are irrelevant for states occurring before the corresponding maturities have been reached.
Of course, whether this or an equivalent set of conditions is used is irrelevant as long as they uniquely determine all possible states, i.e. the chain of True, False or irrelevant values for each state is unique. Note as well that although in this example we have considered only binary (True or False) or irrelevant conditions, these could in principle take multiple values. In addition, besides atomic conditions as considered here, each condition could in turn represent a composed condition, made out of several (sub)conditions in turn. All these variations are trivial in nature and should also be considered as cover by the present invention.
A last point to address is the meaning of the dashed box in Figure 1. Although as it stands the diagram is perfectly valid and should describe correctly the dynamics of the coupon bond, note that there is an intriguing similarity among states Ti and states Ci; i.e. they are very similar in meaning, differing only in the number of the time period or coupon to which they refer (i). Therefore, they could also be represented by a common repeating or recurrent state, plus additional information indicating to which coupon/period they refer. This can be naturally extended to states with repeat themselves indefinitely, thus opening the possibility for the codification of a perpetuity. The definition of a codification scheme with such recurrent states will be addressed in the next section below.
Specification with recurrent states
As mentioned earlier, some subsets of the states of the coupon bond DFA from last section or the coupon-bond (the Ti and Di states) correspond to very similar interpretations of the status of the state machine, differing only in the number of the time period or coupon to which they refer (i); i.e., in a certain sense they can be regarded as a state that repeat itself a number of times (say from i=1 to a given imax, with imax=3 in our case). Given this, it makes sense to simplify the representation of DFA by including all those states in a recurrent state (R) to be treated separately. With this simplification we present below the list of contract states (Table 6), the state transition table (Table 7), the equivalent state diagram (Figure 2), and the state definition table (Table 8) of the DFA for our example coupon bond; note that the other elements of the DFA (inputs and actions) do not change with respect to the previous section.
Of course all this merely hides the complexities of the bond dynamics inside of the recurrent state, which has to be specified separately. This simplification can be important, however, in the case of complex state machines. An obvious analogy is that of the introduction of loops in programming languages. The recurrent state itself is also defined as a state machine, note however that initial and accepting states are replaced in this context by entry and exit points, since the execution of the abstract computation is not meant to start or finish inside the recurrent state. We present below the list of contract states (Table 8), the state transition table (Table 9), and the state diagram (Figure 3) for the recurrent state.
A novelty of this approach is the introduction of an index (i), which keeps track of how many times the states have been occupied. The increase of this index, and analogous quantities (for example the total amount of money paid), can be either calculated externally (as below for the codification scheme), or achieved by additional DFA actions, as indicated in Table 9 for the state C. Note as well that the inputs (alphabet) for the internal states of this recurrent state can potentially depend on the internal index (i) and/or similar quantities. As explained before, the would-be accepting states of the system have been replaced by exit points. The corresponding equivalent state diagram is presented in Figure 3.
The codification scheme for such a recurrent state would look, when expanded, very similar to the relevant parts of Table 5. However, since the spirit of this approach is not to expand and treat each internal (sub-) state separately, it seems more natural no to present it explicitly in a table. Instead, we present in Figure 4 the pseudocode for an algorithm which would assign the correct vales (True or False) to the variables associated with the conditions of the state machine codification. Variables associated with irrelevant conditions do not need to be assigned any value, of course. In Figure 4, as in Table 5 above, each ti condition indicates whether a particular date has come (that is, ti = T means t ≥ ti), and each ci condition whether the corresponding (i-th) coupon has been paid.
A last point to be addressed is the need for a termination point, represented by the index imax. Although usual coupon bonds do have a finite maturity, a perpetuity is similar instruments that (in principle) run for ever. With our codification of the recurrent state this can be achieved by a simple modification of the pseudocode as presented in Figure 5. Note that in this case the while loop will end when it encounters the first period which maturity has not been reached, of course these variables are irrelevant and at that point all the states are uniquely defined by the codification scheme, i.e. there is a combination of true and false values unique to each state.
Specification with recurrent states
The fun thing, we started patenting these ideas before people thought that this was possible on Bitcoin. So, a lot of existing projects, banks etc are going to be on BCH. This is the fun of IP, you do not get to just do as you will without paying the inventors.
References
[1] https://en.wikipedia.org/wiki/Deterministic_finite_automaton.
[2] nCrypt, Realizing state machines, WP0307 (2016).
[3] nCrypt, Blockchain-based deterministic finite automata, WP0032 (2016).
[4] https://en.wikipedia.org/wiki/DFA_minimization
