Systems and methods for implementing deterministic finite automata (DFAS) via a blockchain

Patent metadata

Field	Value
Publication number	US-12530205-B2
Application number	US-201716345517-A
Country	US
Kind code	B2
Filing date	Oct 27, 2017
Priority date	Oct 28, 2016
Publication date	Jan 20, 2026
Grant date	Jan 20, 2026

Abstract

The invention relates to a technique for implementing, controlling and automating a task or process on a blockchain such as, but not limited to, the Bitcoin blockchain. The invention is particularly suited for, but not limited to, automated execution of contracts such as smart contracts for financial agreements. However, other types of tasks and non-financial contracts can be implemented. The invention can be viewed as the implementation or incarnation of a state machine or DFA on a blockchain by using the unspent outputs of blockchain Transactions to represents the states of the machine, and spending of those outputs as the transition of the machine from one state to another. The invention provides a technical realisation and implementation of 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 of a finite set (called input) occurs. The invention comprises compilation and codification techniques for the DFA implementation.

First claim

The invention claimed is:

1 . A method of implementing a deterministic finite automata (DFA) on a blockchain, comprising steps of:
storing a state transition table for the DFA in a storage resource external to the blockchain; associating a portion of data in a locking script of an unspent output (UTXO 1 ) of a blockchain transaction (Tx 1 ) with a state of the DFA in the state transition table; monitoring, by a program executing on a hardware processing element of the blockchain, based on the association of the unspent output (UTXO 1 ) with the state of the DFA, for a trigger for a transition from the state of the DFA to a further state in the state transition table; detecting, by the program, the trigger; and automatically spending, by the program, the unspent output (UTXO 1 ) of the blockchain transaction (TX 1 ) in response to the trigger, wherein the automatic spending comprises:
transmitting the blockchain transaction (TX 1 ) over a network connection to a blockchain node of the blockchain; and
recording in the blockchain, by the blockchain node in response to the automatic spending, the transition of the DFA to the further state.

2 . A method according to claim 1 and further comprising the step of:
using a further transaction (TX 2 ) to make another transition from the state of the DFA to a second further state,
wherein the second further state is associated with a portion of data provided within a locking script of another unspent output (UTXO 2 ) of the further transaction.

3 . A method according to claim 1 and further comprising the step of:
using a portion of code to implement or represent at least one state transition trigger.

4 . A method according to claim 3 wherein:
the portion of code comprises a machine-testable condition which provides a Boolean result based upon an input.

5 . A method according to claim 4 wherein the input is determined at run time and is used by the portion of code to determine whether or not the unspent output (UTXO 1 ) should be spent so as to move the DFA to the other state.

6 . A method according to claim 1 wherein the portion of data in the unspent output (UTXO 1 ) is provided in a locking script.

7 . A method according to claim 6 wherein the portion of data is a tag, label or a portion of metadata.

8 . A method according to claim 1 wherein: the DFA is a model of a machine-executable smart contract.

9 . A method according to claim 1 wherein: the unspent output (UTXO 1 ) comprises a locking script which includes a hash of a puzzle, a solution of which must be provided by an input of a further transaction in order to spend the output (UTXO 1 ) and transition the DFA to another state.

10 . A method according to claim 1 wherein:
the unspent output (UTXO 1 ) comprises a locking script which includes a hash of a redeem script which must be provided by an input of a further transaction in order to spend the output (UTXO 1 ) and transition the DFA to another state.

11 . A method according to claim 10 wherein the redeem script comprises a cryptographic key.

12 . A method according to claim 1 and further comprising the step of:
using one or more computing agents to perform the step of associating the portion of the data in the locking script.

13 . The method according to claim 1 wherein:
the program, as a result of being executed, further monitors for an input signal; and

the trigger is activated by the input signal.

14 . A system for implementing a deterministic finite automata (DFA) on a blockchain, the system comprising:
at least one blockchain node of the blockchain; a non-transitory memory for storing machine executable instructions; and a processor for accessing the memory and executing the machine executable instructions, wherein the machine executable instructions, when executed cause the processor to execute first operations for implementing a deterministic finite automata (DFA) on a blockchain, the first operations comprising:
storing a state transition table for the DFA in a storage resource external to the blockchain; and
associating a portion of data in a locking script of an unspent output (UTXO 1 ) of a blockchain transaction (Tx 1 ) with a state of the DFA in the state transition table;
wherein the machine executable instructions further comprise a program of the blockchain, that when executed by the processor cause the processor to execute second operations, the second operations for the program comprising:
monitoring based on the association of the unspent output (UTXO 1 ) with the state of the DFA, for a trigger for a transition from the state of the DFA to a further state in the state transition table;
detecting the trigger;
automatically spend the unspent output (UTXO 1 ) of the blockchain transaction (Tx 1 ) in response to the trigger, wherein the automatic spending comprises:
transmitting the blockchain transaction (Tx 1 ) over a network connection to the at least one blockchain node of the blockchain; and

automatically cause the transition of the DFA to the further state to be recorded in the blockchain by the at least one blockchain node in response to the automatic spending.

15 . A system according to claim 14 wherein the system comprises:
a blockchain platform; and
at least one computing agent arranged to implement the DFA via the blockchain.

Assignees

• Nchain Licensing Ag

Inventors

• Wright Craig Steven
• Jimenez-Delgado Pedro

Classifications

• H04L63/1416

  Event detection, e.g. attack signature detection · CPC title

• G06Q20/389

  Keeping log of transactions for guaranteeing non-repudiation of a transaction · CPC title

• H04L9/0637

  Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM] · CPC title

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F9/4498 Primary

  Finite state machines · CPC title