Arithmetic enhancement of C-like smart contracts for verifiable computation

Abstract

A system converts high level source code into an arithmetic circuit that represents the functionality expressed in the source code, such as a smart contract as used in relation to a blockchain platform. The system processes a portion of high level source code to generate an arithmetic circuit. The arithmetic circuit comprises one or more arithmetic gates arranged to represent at least some of the functionality expressed in the source code.

Claims

1. A computer-implemented method comprising the steps: processing a portion of source code to generate an arithmetic circuit, including evaluating one or more constants provided in the source code to provide one or more expressions comprising Boolean and/or arithmetic operators, wherein: the source code is written in a high level programming language and further wherein the source code represents a smart contract; and the arithmetic circuit comprises one or more arithmetic gates arranged to represent some or all of the functionality expressed in the source code, wherein the arithmetic circuit is a machine executable version of the source code, and is arranged to compute a result.

2. A method according to claim 1 and further comprising the step of: using the arithmetic circuit to provide a hardware and/or software circuit.

3. A method according to claim 1 wherein: the arithmetic circuit comprises n-bit wires connected to arithmetic gates.

4. A method according to claim 1 wherein: the arithmetic circuit is architecture independent.

5. A method according to claim 1 wherein the method further comprises pre-processing of the source code to determine one or more constants, the pre-processing comprising one or more of the following steps: removing comments; importing header declarations from header files to source files; merging multiple source files; and solving or evaluating directives and macros.

6. A method according to claim 1 wherein the method further comprises the step of detecting all global variables declared in the source code, wherein a global variable relates to a function, a structure or class, a constant and/or an entry point for execution.

7. A method according to claim 1 wherein the method further comprises the step of: generating a table of symbols to associate each symbol provided in the source code with declaration information provided in the source code, the symbols in the table being global and or local symbols.

8. A method according to claim 1 wherein the method further comprises the step of performing a line-by-line evaluation of the source code which results in an arithmetic and/or logic expression which expresses one or more output variables as a combination of logic and/or arithmetic operations applied on one or more input variables.

9. A method according to claim 8 wherein the line-by-line evaluation of the source code comprises the sub-steps of: decoding of types; decoding of expressions; evaluation of expressions; and/or allocation of memory for data structures required by said functionality.

10. A method according to claim 8 and further comprising the step of: mapping the arithmetic and/or logic operations of the expression to arithmetic gates.

11. A method according to claim 10 wherein the mapping step comprises the sub-step of: performing a wire expansion; and/or performing a wire compression.

12. A method according to claim 1 and further comprising the step: using the arithmetic circuit to generate a quadratic program comprising a set of polynomials which provide a description of the arithmetic circuit.

13. A method according to claim 12 and further comprising the step: providing the quadratic program to an entity for execution of the quadratic program using one or more inputs.

14. A computer-implemented system arranged to perform the steps of claim 1, wherein the system comprises an interpreter arranged to perform the processing of the source code, wherein the interpreter comprises instructions stored in memory and executed by a processor.

15. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform claim 1.

Description

(1) These and other aspects of the present invention will be apparent from and elucidated with reference to, the embodiment described herein. An embodiment of the present invention will now be described, by way of example only, and with reference to the accompany drawings, in which:

(2) FIG. 1 illustrates a protocol of the verifiable computation and actors involved in an illustrative use and embodiment of the invention. These actors are the: Client, Worker (also known as the “prover”) and Verifier.

(3) FIG. 2 shows the translation process from DSL contracts to Quadratic Arithmetic Programs (QAPs) in accordance with an embodiment of the invention.

(4) FIG. 3 shows an example of an arithmetic circuit in accordance with an embodiment of the invention.

(5) FIG. 4 shows a high-level description of a packet (header+body) containing a circuit representation in accordance with an embodiment of the invention.

(6) FIG. 5 shows an implementation of a 4-bit wire expander representing the statement “Check if variable <a> is even”, as per the example described below.

(7) FIG. 6 shows a building block in accordance with an illustrative implementation of the invention, wherein the building block implements a conditional statement.

(8) FIG. 7 illustrates how a constants generator module in accordance with an embodiment of the invention may be responsible for the creation of the constants used by the arithmetic circuit. In the example used, three constants (C.sub.1, C.sub.2 and C.sub.3) plus default one (1) and zero (0) values are generated.

(9) FIG. 8 is a schematic diagram illustrates a computing environment in which various embodiments can be implemented.

OVERVIEW

(10) We now provide an illustration of how the invention may be put into working practice according to one embodiment. In this example, we describe a possible implementation of an interpreter arranged to convert a high-level language contract (e.g. C/C++ language) to a circuit comprising arithmetic gates. However, the invention may be arranged to translate other HLL languages. Specific structures or building blocks can be used to facilitate this conversion. In one or more embodiments, this representation can be seen as the first step for the construction of a comprehensive pipeline able to provide a distributed verifiable computation.

(11) The building blocks presented in this example are not intended to be an exhaustive list of all possible high-level language constructs handled by an embodiment of the invention. Moreover, alternate implementations of the presented examples can be provided. These fall within the scope of the person skilled in the art.

(12) We now provide an illustrative embodiment of the invention. It is important to note, however, that this is an example of an application to which the invention may be put to use. The skilled person will understand that the invention can be put to advantageous use in other contexts and applications. The invention is not limited to use in relation to smart contracts or financial instruments.

Illustrative Embodiment of the Invention & Example Use Case

(13) For our example, consider a protocol which allows users to generate contracts for financial instruments using a Domain Specific Language (DSL). Once the contract has been generated, its execution can be outsourced to untrusted parties (called “workers” or “provers”), while its correctness can be publicly verified. The protocol makes use of cryptographic primitives that ensure: Completeness, i.e. the honest verifier will be convinced of the validity of the output if the protocol is correctly followed; Soundness, i.e. no cheating prover can convince the honest verifier about the authenticity of the output; Zero-knowledge, i.e. no cheating verifier learns anything other than the validity of the output.

(14) The principal benefits of the protocol are: Man-in-the-middle attacks are prevented since no communication between the participants is requested. It makes hard for malicious nodes to tamper with the data due to the use of the blockchain technologies. Trusted third parties such as trusted hardware devices are avoided Contract validations do not imply code re-execution. Computations are not replicated by every node in the network. Instead, proofs of honest execution are stored in the public blockchain and used for validation purposes only.

(15) Such a system would be capable of handling various types of smart contracts, corresponding to various types of tasks and products, and not limited to financial applications or uses. Due to its decentralized and distributed nature, the (Bitcoin) blockchain provides a well-suited environment for settling agreements between two or more parties.

(16) Such a system needs to provide and facilitate programmability in a decentralized cryptocurrency system. However, it is recognised in the art that smart contract programming is an error-prone process. See Delmolino, K., et al. (2015). Step by Step Towards Creating a Safe Smart Contract: Lessons and Insights from a Cryptocurrency Lab, and Juels, A., et al. (2013). The Ring of Gyges: Using Smart Contracts for Crime.

(17) Therefore, it would be advantageous to be able to use DSLs that make smart contracts easier to write and to read by programmers, thus reducing error, reducing time, effort, cost and resources during the programming process. Ideally, non-specialist programmers would be able to write contracts without having to implement any cryptography. Instead, a compiler/interpreter would automatically compile the source code to a cryptographic protocol between the users and the blockchain. These are among the technical problems solved by the present invention. Such advantages are not provided by prior art techniques for verification and generation of proofs.

(18) The framework uses state-of-the-art cryptographically verifiable computations (see Gennaro, R., et al. (2013). Quadratic Span Programs and Succint NIZKs without PCPs) and ensures correct function evaluation: an adversary obtaining sensitive information will be unable to manipulate the results thanks to the use of verifiable computations. This model makes use of blockchain technologies to store proof-of-correctness and it combines the “correct-by-construction” cryptography approach with smart contracts.

(19) In this example, we focus on an implementation of a translation component able to convert a high-level language contract (e.g. C/C++ language) to a circuit comprising arithmetic gates. The resulting circuit is a machine executable representation of the HLL source code (as opposed to a proof for verification purposes). Specific structures or building blocks are used to facilitate this conversion. In our example, the invention can be used to provide the first step in the construction of a pipeline which is arranged to implement a distributed verifiable computation system. Note, however, that we again point out that the invention is not limited to this use case and can be used to effect in a wider range of applications and contexts.

(20) In order to describe an illustrative implementation, we provide an overview of a framework for verifiable computations, followed by an introduction to circuit representations of smart contracts in accordance with the present invention.

(21) Illustrative Use: Verifiable Computation: Framework

(22) Problem Statement.

(23) A client sends the specification of a computation P and input x to an untrusted prover (worker). The worker computes an output y and returns it to the client. If y=P(x), then a correct prover should be able to produce a certificate of correctness and convince anyone (not just the client) of y's correctness. Otherwise, the verifier should reject y with high probability.

(24) The protocol should be cheaper for the verifier than executing P(x)locally, or the protocol should handle computations P that the verifier could not execute itself. Moreover, no assumptions about the correctness of the worker's behaviour is needed.

(25) Data Access.

(26) There are two distinct decentralized databases living in the system (i) DHT—off-chain data are stored on the DHT. Data are sufficiently randomized across the nodes and replicated to ensure high availability—and (ii) Public ledger—proofs of correct execution are stored on the blockchain and can be audited.

(27) Protocol.

(28) The steps required by the protocol are depicted in FIG. 1. A computation P is represented by a circuit C. The client supplies the input x, and the worker executes the circuit on the input and claims the output is y. The prover is expected to obtain a valid transcript for {C, x,y}. A valid transcript for {C,x,y} is an assignment of values to the circuit wires such that: the values assigned to the input wires are those of ; the intermediate values correspond to the correct operation of each gate in C; the values assigned to the output wires is .

(29) If the claimed output is incorrect, i.e. ≠(), then a valid transcript for {, , } does not exist.

(30) The setup phase involves writing contracts in a formal language with a precise semantics. In accordance with the present invention, the interpreter takes as input the source code and produces an arithmetic circuit which consists of wires that carry values from a field and connect to addition and multiplication gates. In some embodiments, arithmetic circuit optimisation techniques such as those described in U.K. Pat. Application No. 1718505.9 may be utilized in order to reduce the required resources necessary during determination of an outcome of the smart contract.

(31) From the circuit , the system generates a quadratic program Q, i.e. contains a set of polynomials that provides a complete description of the original circuit C. Then, the public parameters to be used by all provers and verifiers are generated.

(32) A public evaluation key EK and the public verification key VK are derived using a secret value s selected by the client. The worker uses these public information to evaluate the computation on a particular input . The output , the values of the internal circuit wires and EK are used to produce the proof-of-correctness π. The proof π can be stored on the blockchain and verified by multiple parties without requiring the prover to separately interact with each of these entities.

(33) All the bitcoin nodes can validate the payment transaction using the public verification key VK and the proof π, thus validating the contract.

(34) Smart Contracts and Circuit Representation

(35) Although domain-specific languages (DSL) are required to implement a smart contract, e.g. Actulus Modeling Language (AML), Digital Asset Modeling Language (DAML), Financial Products Markup Language (FpML), for the sake of simplicity of illustration we describe herein the use of a more generic language able to provide a higher range of types, operators and constructs such as the High Level Language (HLL), C. The invention can be arranged, however, to convert different DSL languages to C (or another HLL) using dedicated tools.

(36) In the example used herein, the interpreter processes source code written in C. The invention could be adapted to work with other High Level Languages (which may also be referred to as “general-purpose languages” (GPLs). Examples of general-purpose programming languages include Ada, ALGOL, Assembly language, BASIC, Boo, C, C++, C#, Clojure, COBOL, Crystal, D, Dart, Elixir, Erlang, F#, Fortran, Go, Harbour, Haskell, Idris, Java, JavaScript, Julia, Lisp, Lua, Modula-2, NPL, Oberon, Objective-C, Pascal, Perl, PHP, Pike, PL/I, Python, Ring, RPG, Ruby, Rust, Scala, Simula, Swift, and Tcl.

(37) A comprehensive pipeline for the translation of a high-level language to a logic circuit is shown in FIG. 2. In accordance with the present invention we focus on the module highlighted in the dotted line box in FIG. 2. The high-level C program containing the contract and the required external libraries are linked together to make the stand-alone pre-processed contract. In this stage, the C pre-compiler is responsible for checking that all the required resources are available. Pre-processor directives are also evaluated. Constant expressions are evaluated and all symbols are registered. The outcome is a set of expressions of C-like operators, such as addition (+), multiplication (*), comparison (<), equality (==), conditional statements (?, :) and logic operators (and, or, not, xor). We require the main function to have a predefined name and format. The arithmetic circuit (see FIG. 3) is built by representing symbols with n-bit wires connected to elementary arithmetic gates, e.g. addition and multiplication. The polynomials in the Quadratic Arithmetic Program (QAP) are defined in terms of their evaluations at the roots of the arithmetic circuit as introduced in Gennaro, R., et al (2013) Quadratic Span Programs and Succinct NIZKs Without PCPs.

(38) FIG. 3 shows an example of an arithmetic circuit. Each wire comes from, and all operations are performed over, a field F. This circuit computes y=x.sub.1+x.sub.2.Math.x.sub.3.Math.(x.sub.3+x.sub.4). Since the final output of the circuit is a sum, an additional multiplication gate (multiply by constant one) is required.

(39) C-Language Interpreter

(40) In accordance with one illustrative embodiment of the invention, we now describe an interpreter able to recognize a subset of instructions defined for the C programming language, including: pre-processor directives, conditionals, arithmetic and bitwise Boolean operators, global functions. Support for arrays and structs can be also provided with no extra logic, as readily understood by the skilled person.

(41) The interpreter enhances expression into the arithmetic gate language using multiplications, additions and specific building blocks presented in the section below entitled “Generation of arithmetic primitives”. Each wire will have a specified bit-width. In case of 1-bit width, the wire represents a binary variable.

(42) Arithmetic Enhancement of C-Like Programs for Implementation on a Blockchain

(43) We now detail the process for the construction of an arithmetic circuit representing the functionality expressed by a C source code. At each stage of the process, an unexpected behaviour (e.g. missing symbol, wrong syntax or unknown operator) will result in the immediate termination of the program execution with an appropriate code error.

(44) Pre-Processing

(45) As shown in FIG. 2, a smart contract may consist of multiple files and libraries. The first step of the protocol involves the creation of a single source file containing the full set of instructions required to implement the contract. The individual sub-steps can be listed as follows: All comments are removed. Headers declarations are imported from the header files to the source files. All source files are merged. Pre-processor C directives and macros are solved or evaluated. They include #define directives and conditional #ifdef directives.

(46) At the end of this step, the actual value of all pre-processor constants must be known. The value of the variables used in the source code must depend only on the values of the inputs of the contract. Moreover, the declaration of the entry point in the source code must have the following syntax: void contract(inputType *in, outputType *out)

(47) Types inputType and outputType are defined by the user. The following source code box shows a simple example of a smart contract containing a single sum operation between two unsigned integer inputs.

(48) TABLE-US-00001 struct inputType { unsigned int i1; unsigned int i2; }; struct outputType { unsigned int o; }; void contract(struct inputType *in, struct outputType *out) { unsigned int val = in−>i1 + in−>i2; out−> o = val; }

(49) The output can be represented by different types of variables, depending on the specific contract. In the case above, a single output is simply connected to the result of the arithmetic operation.

(50) Integer and Real Numbers

(51) In this illustrative embodiment, for the sake of simplicity, we assume that only operations between (signed or unsigned) integers are available. If this assumption is removed, the circuit building blocks (see Section “Generation of the arithmetic primitives”) must be extended. Therefore, operations between real numbers must be converted into operations between integers. Let us consider the following portion of a contract: “Check if the average salary of the employees is greater than $32.5K.”

(52) This statement requires a division (by N employees) in order to compute the average value. However, the statement can be converted into the following expression between integers:

(53) $\underset{i=1}{\overset{N}{.Math.}}{s}_i>32500.Math.N$

(54) Where s.sub.i represents the salary of the i-th employee.

(55) Creation of the Global Table of Symbols

(56) In computer science, a Table of Symbols is a data structure used by a compiler/interpreter to associate each identifier (symbol) in the source code with information relating to its declaration. In this second step, the interpreter detects all the global symbols declared in the source file: Functions Structures (or classes) Note: The use of classes (OOP languages such as C++) requires additional logic to check the scope of public, protected and private sections. Constants (Global variables are also allowed but not recommended. The scope of contract( . . . ) function should be treated as an independent black box. Its behaviour should not depend on external variables).

(57) For each of these symbols, a hierarchy of local symbols representing the internal declarations of their identifiers is built. At the end of this stage, each global symbol (name, type and value) in the table can be directly addressed for further processing.

(58) Detection of the Entry Point of the Contract

(59) One of the global symbols must be the entry point of the contract (Contract function in “pre-processing” Section). Name, number and type of its parameters are checked against the expected syntax. Additional logic may consist in checking that all inputs structures are used within the contract and all output structures are linked to some portions of the contract.

(60) Line-by-Line Evaluation

(61) Each code line is analysed independently. Local symbols, representing the internal declarations of identifiers, are included in the hierarchy of the global table of symbols. In more detail, this stage is responsible for the following tasks: Decoding of types, including the declaration of structures and array, elementary types (Booleans, integers, etc.) and pointers. Decoding of expressions, e.g. unary or binary operations, constants, identifiers, data structures and function calls. Evaluation of expressions, i.e. evaluation of (numeric) expressions which do not depend on the input values. Memory allocation, i.e. temporary storage allocation for the data structures required by the contract functionality.

(62) This stage links all the statements of the arithmetic expression from a spatial (i.e. memory used) and temporal (i.e. operators precedence) point of view. Therefore, each output variable is expressed as combination of logic and arithmetic operations applied on the input variables.

(63) Creation of the Explicit Arithmetic Expressions Using the data structures defined in the “line-by-line” Section, a generic arithmetic/logic expression e is collapsed in order to be represented in explicit form according to the following syntax: OP.sub.N (OP.sub.N−1 ( . . . (OP.sub.1 (OP.sub.0)) . . . ))

(64) According to this syntax, an arbitrary operator OP.sub.i+1 is applied to e after the operator OP.sub.i.

(65) For instance, given the following code:

(66) TABLE-US-00002 void contract(struct inputType *in, struct outputType *out) { unsigned int val = in−>i1 + in−>i2 + in−>i1 + in−>i2; val = (val > 15) ? 44 + 6 : in−>i1 * in−>i2 * in−>i2; out−> o = val; }

(67) The explicit expression e can be represented as: out.sub.0=(?(<15 (ADD(ADD(ADD in.sub.0 in.sub.1)in.sub.0)in.sub.1))50 (MUL(MUL in.sub.0 in.sub.1)in.sub.1))

(68) As explained in Section “Generation of the arithmetic Primitives”, the expression e is used to create the arithmetic primitives required to represent the contract functionality.

(69) Generation of the Arithmetic Primitives

(70) At this stage, the interpreter is ready to make a one-to-one mapping between the operations used to generate the expression e and the structures required to implement these functionalities on circuit.

(71) An important parameter required to create the circuit is the bit-width n.sub.bit, i.e. the number of bit used to represent a signed (or unsigned) integer number. Different computer architectures are characterised by different n.sub.bit values. If a client does not know a preferred bit-width value of a worker, its value will be arbitrarily chosen and specified in the header of the circuit along with additional information, as shown in FIG. 4. (Just as compilation is performed for a specific target architecture, knowing the bit-width value may result in a more efficient implementation and execution of the circuit).

(72) The version field gives important information about the specific algorithm used to create a specific building block in the circuit. In our illustrative implementation we chose the two's complement binary representation of signed integers.

(73) Addition and Multiplication Operations

(74) Addition and multiplication operations are mapped one-to-one into addition and multiplication gates in the circuit. Given two n-bit wire inputs, an addition wire output requires n+1 bit and a multiplication wire output requires 2n bit. For instance, a multiplication between two n.sub.bit wires a and b can be represented as: MUL [id.sub.a id.sub.b] TO [id.sub.c]

(75) (Every arithmetic or Boolean wire x in the circuit can be univocally identified by a value id.sub.x. As for binary variables, we start to count from value zero). The result c will be automatically represented on 2n.sub.bit bit.

(76) Boolean Operations

(77) The full set of Boolean gates can be computed using arithmetic gates. Given two Boolean values a and b, the following equivalences are valid: AND(a, b)=ab NAND(a, b)=1−ab OR(a, b)=1−(1−a)(1−b) NOR(a, b)=(1−a)(1−b) XOR(a, b)=(1−a)b+(1−b)a

(78) Beside the XOR operator, each Boolean gate requires only one multiplication. All the arithmetic operations are perform on 1-bit width wires.

(79) Bitwise Boolean operations on n-bit width inputs require n 1-bit multiplications (for AND) or additions (for OR). Starting from the least significative output bit, each element is then multiplied by two and added to the next element to build the resulting n-bit integer value (see Section “Wire Compression”).

(80) Wire Expansion

(81) Wire expansion is usually used to translate an arithmetic wire a to an n.sub.a-bit output wire, where n.sub.a is the base-2 logarithm of the maximum value which can be expressed by a. For instance, let us consider the following portion of a contract: “Check if variable <a> is even.”

(82) If n.sub.a=4, this statement is implemented using the wire expansion as shown in FIG. 5. Assuming that a.sub.0 represents the least significative bit of a, the output of the statement is equal to a.sub.0 itself. This circuit building block can be expressed as: EXPAND [id.sub.a] TO [id.sub.a3 id.sub.a2 id.sub.a1 id.sub.a0]

(83) Taking a closer look at the circuit, it is clear that only one bit of a is required for further processing, while the remaining 1-bit wires can be removed. The interpreter may generate only the individual 1-bit wires used in the rest of the contract. FIG. 5 shows an implementation of a 4-bit wire expander representing the statement “Check if variable <a> is even”.

(84) The interpreter applies a specific syntax for the optimised wire expander: EXPAND [id.sub.a] TO [0->id.sub.a0]

(85) That is, only the least significative 1-bit wire (i.e. identifier number zero) is taken, and identifier id.sub.a0 is assigned to it. The greater n.sub.a, the more effective the optimisation may be. (In this context, we define optimisation as the possibility to save space to store or transmit the low-level directives used to represent the arithmetic circuit).

(86) Wire Compression

(87) Wire compression is used to combine 1-bit wires a.sub.i back to an n.sub.a-bit output wire:

(88) $a=\underset{i=0}{\overset{n_a-1}{.Math.}}{2}^i{a}_i$

(89) This building block consist of additions and multiplications by constants, therefore the size of the QAP polynomial is not affected (See Genaro R., et al (2013) Quadratic Span Programs and Succinct NIZKs Without PCPs). Assuming that n.sub.a=256 and identifiers in the range [id.sub.a0, id.sub.a255] are consecutive, an optimised way to represent this building block is the following: COMPRESS [id.sub.a0:id.sub.a255] TO [id.sub.a]

(90) The resulting wire a will be then identified by id.sub.a.

(91) Negate Operation

(92) The negate operation is necessary to compare two variables, since their difference can be compared to the value zero. Negating an n.sub.bit-bit wire can be implemented as multiplication by constant −1. This constant must be represented as:

(93) $-1_{n_{\mathrm{bit}}}\stackrel{\Delta }{=}\underset{i=0}{\overset{n_{\mathrm{bit}}-1}{.Math.}}{2}^i$

(94) Equal to Zero Operation

(95) This building block for an n.sub.bit-bit wire a can be implemented as follows: Wire expansion on n.sub.bit bit (a.sub.0, . . . a.sub.nbit−1); Negate each 1-bit wire (a.sub.i.fwdarw.b.sub.i); Multiply the resulting b.sub.i wires: c=Π.sub.i=0.sup.n.sup.bit.sup.−1b.sub.i

(96) Therefore, 1-bit variable c=1 if and only if a=0.

(97) Compare to Zero Operation

(98) A “greater than” operation can be transformed in a “lower than” operation using simple equation rules. In the two's complement representation, this operations corresponds to check if the difference between two signed integers is positive or negative (or equal to zero in the case of “lower or equal than” operation). The discriminant of the sign of the difference c=a−b is given by the most significative bit x in the binary representation: negative numbers are characterised by x=1, while positive numbers are characterised by x=0: EXPAND [id.sub.c] TO [n.sub.bit−1->x]

(99) Depending on the type of comparison (positive vs negative), the binary value x is required to be negated.

(100) Conditional Statement

(101) A conditional statement in a high-level language can be expressed in the following form: IF (S.sub.c) S.sub.a ELSE S.sub.b

(102) Since the statement S.sub.c depends on the input of the contract, both branches S.sub.a and S.sub.b must be implemented in the circuit. The logic flow is depicted in FIG. 6. Depending on the (binary) output of statement S.sub.c, statement S.sub.a or statement S.sub.b will be executed. The binary operation x+1 is used to negate x.

(103) Generation of Constants

(104) Constant values do not depend on the input wires of the circuit. Using dedicated unary multiplication gates in the form mul-by-const-c, we provide the following additional circuitry to generate the constant values required by the contract: The constant zero is computed by multiplying an input wire by zero. (The contract must have at least one input. Therefore, the input with identifier 1 (e.g. in.sub.1 in FIG. 7) can be used to generate the constant zero). The constant one is computed by adding one to the constant zero. Any additional constant c.sub.i is computed by using mul-by-const-ci on the constant one.

(105) Since constants zero and one are always added to the circuit, the implementation of k arbitrary constants requires k+2 gates. This process is depicted in FIG. 7. A constants generator module provided in accordance with an embodiment of the invention is responsible for the creation of the constants used by the arithmetic circuit. In the example, three constants (C.sub.1, C.sub.2 and C.sub.3) plus default one (1) and zero (0) values are generated.

(106) Constants have a known bit-width as specified by the two's complement standard.

(107) Turning now to FIG. 8, there is provided an illustrative, simplified block diagram of a computing device 2600 that may be used to practice at least one embodiment of the present disclosure. In various embodiments, the computing device 2600 may be used to implement any of the systems illustrated and described above. For example, the computing device 2600 may be configured for use as a data server, a web server, a portable computing device, a personal computer, or any electronic computing device. As shown in FIG. 8, the computing device 2600 may include one or more processors with one or more levels of cache memory and a memory controller (collectively labelled 2602) that can be configured to communicate with a storage subsystem 2606 that includes main memory 2608 and persistent storage 2610. The main memory 2608 can include dynamic random-access memory (DRAM) 2618 and read-only memory (ROM) 2620 as shown. The storage subsystem 2606 and the cache memory 2602 and may be used for storage of information, such as details associated with transactions and blocks as described in the present disclosure. The processor(s) 2602 may be utilized to provide the steps or functionality of any embodiment as described in the present disclosure.

(108) The processor(s) 2602 can also communicate with one or more user interface input devices 2612, one or more user interface output devices 2614, and a network interface subsystem 2616.

(109) A bus subsystem 2604 may provide a mechanism for enabling the various components and subsystems of computing device 2600 to communicate with each other as intended. Although the bus subsystem 2604 is shown schematically as a single bus, alternative embodiments of the bus subsystem may utilize multiple busses.

(110) The network interface subsystem 2616 may provide an interface to other computing devices and networks. The network interface subsystem 2616 may serve as an interface for receiving data from, and transmitting data to, other systems from the computing device 2600. For example, the network interface subsystem 2616 may enable a data technician to connect the device to a network such that the data technician may be able to transmit data to the device and receive data from the device while in a remote location, such as a data centre.

(111) The user interface input devices 2612 may include one or more user input devices such as a keyboard; pointing devices such as an integrated mouse, trackball, touchpad, or graphics tablet; a scanner; a barcode scanner; a touch screen incorporated into the display; audio input devices such as voice recognition systems, microphones; and other types of input devices. In general, use of the term “input device” is intended to include all possible types of devices and mechanisms for inputting information to the computing device 2600.

(112) The one or more user interface output devices 2614 may include a display subsystem, a printer, or non-visual displays such as audio output devices, etc. The display subsystem may be a cathode ray tube (CRT), a flat-panel device such as a liquid crystal display (LCD), light emitting diode (LED) display, or a projection or other display device. In general, use of the term “output device” is intended to include all possible types of devices and mechanisms for outputting information from the computing device 2600. The one or more user interface output devices 2614 may be used, for example, to present user interfaces to facilitate user interaction with applications performing processes described and variations therein, when such interaction may be appropriate.

(113) The storage subsystem 2606 may provide a computer-readable storage medium for storing the basic programming and data constructs that may provide the functionality of at least one embodiment of the present disclosure. The applications (programs, code modules, instructions), when executed by one or more processors, may provide the functionality of one or more embodiments of the present disclosure, and may be stored in the storage subsystem 2606. These application modules or instructions may be executed by the one or more processors 2602. The storage subsystem 2606 may additionally provide a repository for storing data used in accordance with the present disclosure. For example, the main memory 2608 and cache memory 2602 can provide volatile storage for program and data. The persistent storage 2610 can provide persistent (non-volatile) storage for program and data and may include flash memory, one or more solid state drives, one or more magnetic hard disk drives, one or more floppy disk drives with associated removable media, one or more optical drives (e.g. CD-ROM or DVD or Blue-Ray) drive with associated removable media, and other like storage media. Such program and data can include programs for carrying out the steps of one or more embodiments as described in the present disclosure as well as data associated with transactions and blocks as described in the present disclosure.

(114) The computing device 2600 may be of various types, including a portable computer device, tablet computer, a workstation, or any other device described below. Additionally, the computing device 2600 may include another device that may be connected to the computing device 2600 through one or more ports (e.g., USB, a headphone jack, Lightning connector, etc.). The device that may be connected to the computing device 2600 may include a plurality of ports configured to accept fibre-optic connectors. Accordingly, this device may be configured to convert optical signals to electrical signals that may be transmitted through the port connecting the device to the computing device 2600 for processing. Due to the ever-changing nature of computers and networks, the description of the computing device 2600 depicted in FIG. 8 is intended only as a specific example for purposes of illustrating the preferred embodiment of the device. Many other configurations having more or fewer components than the system depicted in FIG. 8 are possible.

(115) It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be capable of designing many alternative embodiments without departing from the scope of the invention as defined by the appended claims. In the claims, any reference signs placed in parentheses shall not be construed as limiting the claims. The word “comprising” and “comprises”, and the like, does not exclude the presence of elements or steps other than those listed in any claim or the specification as a whole. In the present specification, “comprises” means “includes or consists of” and “comprising” means “including or consisting of”. The singular reference of an element does not exclude the plural reference of such elements and vice-versa. The invention may be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In a device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

(116) All references, including publications, patent applications, and patents, cited herein are hereby incorporated by reference to the same extent as if each reference were individually and specifically indicated to be incorporated by reference and were set forth in its entirety herein. This includes UK patent application numbers: GB1719998.5, GB 1718505.9, GB 1720768.9.