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

Patent metadata

Field	Value
Publication number	US-2019279197-A1
Application number	US-201716345517-A
Country	US
Kind code	A1
Filing date	Oct 27, 2017
Priority date	Oct 28, 2016
Publication date	Sep 12, 2019
Grant date	—

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

1 . A method of implementing a deterministic finite automata (DFA) on a blockchain, comprising the steps:
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.

2 . A method according to claim 1 and further comprising the step of:
using a further transaction (Tx 2 ) to make a transition from the state of the DFA to a further state by spending the unspent output (UTXO 1 ) of the blockchain transaction (Tx 1 ); and
wherein the further state is associated with a portion of data provided within a locking script of an 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 which, when executed, causes a further transaction (Tx 2 ) to spend the unspent output (UTXO 1 ) of the blockchain transaction (Tx 1 ) and thus move the DFA to another state.

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 claim.

13 . A method of implementing a DFA on a blockchain, the method comprising the steps of:
executing a program which is arranged to monitor for and/or receive an input signal and, responsive to the input signal, generate a blockchain transaction Tx 2 which comprises an unspent output (UTXO) and spends an output of a previous transaction Tx 1 ; wherein:
an output of previous transaction Tx 1 comprises a locking script which includes an identifier associated with a first state of the DFA, and
the unspent output (UTXO) of transaction Tx 2 comprises a locking script which includes a further identifier associated with a further state of the DFA.

14 . A method of implementing a DFA on a blockchain, comprising the steps:
using at least one input signal to execute at least one condition and, based on the outcome of the execution of the condition, perform an action in accordance with a state transition table for the DFA; wherein performance of the action is identifiable from a blockchain ledger.

15 . A system arranged to implement the method of claim 1 .

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

17 . A system arranged to implement the method of claim 13 .

18 . A system arranged to implement the method of claim 14 .

Assignees

• Nchain Holdings Ltd

Inventors

• Wright Craig Steven
• Jimenez-Delgado Pedro

Classifications

• H04L9/0637

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

• G06F9/4498 Primary

  Finite state machines · CPC title

• G06Q20/3672 Primary

  initialising or reloading thereof · CPC title

• 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