Blog > Alternative Coins & Systems

DFA compilation and execution

By Craig Wright | 19 Oct 2018 | Alternative Coins & Systems

We present an analysis of the establishment and execution of contractual agreements embodied as deterministic finite automata (DFA). The contract for a European call option is used as an example for the high-level description of the technology.

Background

In a series of papers, see [1] and references therein, we are presenting a novel technology for the establishment and execution of contractual agreements based on the realisation of the commitments of the different parties (and other clauses and provisions) as a computational structure modelled as a state machine.

The present paper deals with one component of that system, namely the establishment and execution of such a contract, i.e. the flow of information between the different (computer) agents which will effectively implement the contract. Although the detailed specification of such a computer system is of obvious practical relevance as well, it is not the topic of this paper; an example of such a system has been presented elsewhere, see [2] and references therein. Very generally, we will refer to this system as a Botman (agent), often without specifying which agent actually carry out the actions described, this could be one of the lower-level bots, a bot manager or any other appropriate entity as, for example, those specified in [2].

As mentioned, we will use the contract for a European call option as an example to illustrate our technology through the paper. A European call option is an agreement that gives an investor the right, but not the obligation, to buy a stock, bond, commodity or other asset at a specified price (strike price) on a specified date (exercise date). The writer (seller) of the option commits himself to sell the asset to the holder (buyer) on that date, at that price, if the buyer decides to exercise it, which (rationally) happens if the price of the asset on that date is higher than the strike. Given this, we assume that the contract can alternatively be settled by the payment to the holder of an amount equal to the market price of the asset on the exercise date minus the strike, no payment is needed otherwise and the option expires unexercised.

Functional Specification

The standard way of establishing and executing a (financial) contract is to sign a legal document and have its provisions interpreted and executed (and sometimes contested) by humans. These contracts can be regarded as composed of text, defining the terms, and a set of values for the parameters particular to the contract at hand (exercise date, writer, public keys, etc.). These distinct elements have been separated in our system, where the essence of the contractual text is captured as an abstract machine, a DFA, and the set of values for the parameters of the particular instance of a contract is provided independently, see [1] and references therein. We will start by describing the information on different elements of the state machine, and turn to the actual generation and execution of the contract in the next section.

The DFA computational system 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 accept states. In addition, and not essential to the DFA structure in [1], we consider here a set of actions (a) which the agents are required to carry out in parallel to submitting the transactions. In the following, as is conventional, the current time (date) will be noted by t, the maturity date by T, the price of the asset at maturity by ST, and the strike price by K.

The main proposal/invention in this paper is the establishment of computer agents (scripts) associated with the states of the DFA machine. These are able to change the state, implement a transition, and in parallel spin-off other (sets of) scripts associated with the subsequent state. The dynamic (run time) identification of a DFA state with a computer script with the appropriate capabilities is the main inventive element in the paper. For our streamlined example, the possible states of the contract and sufficient conditions for their definition are given in Table 1, where also (XML) labels for the states and a natural (human) language description of the states is given.

Note that not all imaginable states have been considered in the contract (e.g. what would happen in the event of bankruptcies, death of the holder, shutdown of Internet, etc.), however, since the main purpose of this paper is the analysis of the compilation and execution of the contract, and not of the complexities of the abstract DFA itself, our example is appropriate (as simple as possible but not more); the reader interested in more complex examples is referred to [1], and the references therein.

Table 1: State definition table. Each condition can be true (T), false (F), or irrelevant (-) for a particular state, which is thus defined by this set of values, one for each condition (not that, in turn, a condition can have multiple components).

Continuing with the description of the different elements of the abstract DFA we turn now to the list of inputs (also called the event alphabet). This is a list of the events that can happen in relation to the contract (maturity reached, payment received, etc.). These inputs, together with the set of current states of the DFA, determine the transaction to be submitted to the blockchain, as well as the parallel actions to be carried out by the agents; note, however, that although technically the transition function is a S × I → S mapping, not all inputs are relevant for all states. In our streamlined example these, together with a (XML) label and a natural language description of the event, are given in Table 2.

Table 2: List of contract inputs (event alphabet).

Computationally, the events can also be regarded as a change in the conditions defining the state, although, as mentioned, some events are irrelevant for some (or all) states and do not cause a state transition. In the same spirit, a list of possible actions, not all relevant for all states, can be specified as in Table 3.

Table 3: List of contract actions.

All these elements converge in the so-called state transition table [3], in which the current (initial) state of the system (rows) together with the appropriate input (columns) determine, according to the table, the next (final) state of the system as well as the actions to be carried out in parallel to the transition. Note that in our DFA, besides transition transactions, we also contemplate completion transactions, which instead of placing the system in a subsequent state place it in an accepting state (f), which is a virtual (e.g. not incarnated on the blockchain and not associated with any script) state that represents the termination of the execution of the contract. An example for our European call option is given in Table 4, in which initial states are associated with rows, inputs with columns, and each cell contains subsequent state/action fields.

Table 4: State transition table of the contract.

In addition, it is common to represent the abstract DFA by a state diagram, shown in Figure 1 for our example. Note that there is a correspondence between this diagram and the (computationally useful) state transition table, so no additional information is included in the diagram itself.

Figure 1: State diagram for a European call option showing the states (blobs) and the blockchain transactions (triangles) to be submitted: origination (o), transitions (t) and completions ©.

Technical Specification

The DFA compilation mechanism consists of different elements and files which will be discussed in turn. The computational structure embedded in these files, how the scripts associated with different states spin-off not only the blockchain transactions, but also subsequent scripts which in turn completely execute the contract, is the main invention proposed in the paper. To start with, the system uses two source files; in our example:

· DFA European call option — parameters.xml

· DFA European call option — script.py

Here we are assuming, for concreteness, that the main language to be used for the generation of subsequent files and execution of the contract is Python 3.5 [4], and that the parameters are provided in an XML 1.0 [5] document. Of course these details are not essential to the invention and using other standards would be equally acceptable.

The XML document contains a list of parameter fields (specified by the XML tags) and values for the particular contract at hand, one particular European call option. In our example it has been written by hand, but it could also be created automatically, i.e. by agents (computers), or by a human entering the appropriate values via a graphical user interface (GUI), which can also be easily created in Python.

The main file for the technical specification of the system is the (Python) main script. This file contains (or inserts upon execution) a hard-coded version of the abstract state transition table (possible states, inputs and actions) and hard-coded functions specifying the DFA inputs and actions to be considered (e.g. how to check the stock price, clock, etc.). If relevant, i.e. for blockchain-based DFA implementations, it may contain hard-coded templates of the (Bitcoin) transactions to be submitted by the scripts to the network.

As explained in [1] and references therein, the state transition table completely determines the DFA at an abstract level, and is the only element needed for its functioning. Note, however, that there is a correspondence between the legal text and the DFA state transition table. In addition to these necessary elements, optionally, the script can also contain/generate different human-readable documentation, e.g. the state diagram, the alphabet, etc.

In order to compile and execute a blockchain-based DFA contract the user (human or computer) needs to fill the values of the parameters and run the main script. Using this hard-coded information on the script and the values for the parameters, upon execution, the script will establish the contract (e.g. place it on the blockchain), and spin-off a (set of) computer programs (other scripts) which will continuously be run by the system of (computer) agents executing the contract [2]. A possible sequence of instructions that accomplish this is as follows:

1. Read parameter values (or input the values directly from a GUI). This loads the parameter values in memory, e.g. in a hash table (HT) [6] structure (which in Python is called a dictionary) or in a distributed hash table (DHT) [7], e.g. the bitTorrent network [8], if this offers some advantages.

2. Use the parameters and the hard-coded contract template to produce the legal contract as detailed in [ref]. This document needs to be (digitally) signed by the writer of the option.

3. (Optionally) create the human-readable documentation for the contract.

4. Use the parameters and the hard-coded input and action functions to generate instances of these functions, with the appropriate parameter values.

5. Load in memory (HT, or DHT) the state transition table.

6. If relevant, create the origination transaction as specified and submit it to the (Bitcoin) network. This can be done by using the Pybitcointools library [9]. This creates a UTXO in the blockchain associated with a specific state of the contract on the Bitcoin blockchain [1].

7. Create a Python script associated with the origination state (s0) and run it (on the same or other computers). This agent (or set of agents) will receive/produce the appropriate inputs, execute the appropriate actions, the ones compatible with the state, and eventually either complete the execution of the contract or produce a transition transaction to another state, as well as spin-off subsequent scripts controlling those states.

8. Terminate the compilation (main script).

Upon termination of the compiling phase the system will thus be up and running (e.g. there will be a UTXO on the blockchain associated with the initial state of the contract), and one or several agents (Python scripts running on Botman agents [2]), which will be monitoring for inputs, ready to take actions, and to produce the appropriate transitions, which would either change the state of the DFA to another state or terminate it.

The sequence of instructions for a transition is:

1. Monitor or produce DFA inputs (function calls like check the clock, receive messages, etc.)

2. Once the input is determined read the transition table for the current state, this determines the next state and possibly an action to be taken.

3. Take the action if anything (possibly to a function call, depending on the complexity).

4. When relevant, create a transition transaction according to and submit it to the blockchain.

5. Create and run a Python script associated with the next state

6. Terminate the current script

The sequence of instructions for the completion of the contract is:

1. Monitor or produce DFA inputs (function calls like check the clock, receive messages, etc.)

2. Once the input is determined read the transition table for the current state, this determines that the contract is to be completed and possibly an action taken.

3. Take the action if anything (possibly to a function call, depending on the complexity).

4. If relevant, create a completion transaction according and submit it to the blockchain (this will spend the last UTXO associated with the contract).

5. Terminate the current (and last) script

The DFA is therefore executed by a set of independent agents (scripts), which receive enough information in turn from previous agents, thus going back to the initial main script and parameter files. This constitutes the second invention proposed in the paper.

To summarize, we proposed in this paper to have the contracts executed by a set of agents (scripts) generated dynamically as the system moves from state to state. These agents need to have access to the current state of the system (e.g. as incarnated by a UTXO on the blockchain), receive or generate the proper inputs according to the events happening in the real world, take the proper actions, and carry out the adequate transactions. All of this can be easily achieved within Python scripts using the appropriately defined functions and existing libraries.

For example, in our European call option case, it should have access to a clock, to check whether the maturity of the contract has been reached, and to the current price of the asset. Given this information it can decide which is the appropriate input to consider according to the parameters. Given this, and the actions specified in the transition matrix, the agent can decide which transaction to produce, thereby placing the system in the next state (in our case there is only one) or complete the execution of the contract appropriately.

References

[1] nCrypt, Realizing state machines, WP0307 (2016).

[2] nCrypt, Botman: Umbrella document, WP0238 (2016).

[3] http://en.wikipedia.org/wiki/State_transition_table

[4] http://www.python.org

[5] http://www.w3.org/XML

[6] http://en.wikipedia.org/wiki/Hash_table

[7] http://en.wikipedia.org/wiki/Distributed_hash_table

[8] http://en.wikipedia.org/wiki/BitTorrent

[9] http://github.com/vbuterin/pybitcointools