Distributed computing system and method

Abstract

The invention relates to distributed processing systems that involve the distribution of computational tasks to one or more untrusted worker computer systems. When an untrusted worker computer system performs a calculation on behalf of a requesting computer system, the requesting computer system (or other verifying computer system) is provided with information that allows the requesting computer system to cryptographically verify that that task has been correctly completed. After completing the calculation, the worker computer system provides information to the requester that includes a proof and I/O data. The requesting computer system may use a set of public verification key parameters, the proof, and the I/O data to verify that the computation performed by an untrusted worker computer system is correct. In some examples, the calculation performed by the worker is associated with the verification of a blockchain transaction. For example, the verification of the computation performed by the untrusted worker computer system may occur as part of validating a transaction on a blockchain node.

1 . A computer-implemented method comprising:
 providing a task to a set of independent computer systems which are able to compete to provide outcome of the provided task, the task specifying a computation to perform; and   verifying, at a verifying computer system, that the computation is correctly performed by a worker computer system in the set of independent computer systems, the computation based on a circuit having a set of multiplication gates, by at least:
 generating an evaluation key; 
 providing the evaluation key to the worker computer system; 
 receiving a proof from the worker computer system, the proof based at least in part on the evaluation key; 
 generating a verification key; and 
 verifying that the computation is correct using the proof and the verification key. 
   
     
     
         2 . The computer-implemented method claimed in  claim 1 , wherein the verification key is based on inputs to the set of multiplication gates and outputs of the set of multiplication gates. 
     
     
         3 . The computer-implemented method claimed in  claim 1 , wherein the proof is based at least in part on a set of intermediate outputs of the set of multiplication gates. 
     
     
         4 . The computer-implemented method claimed in  claim 1 , wherein the proof is based at least in part on a public evaluation key. 
     
     
         5 . The computer-implemented method claimed in  claim 1 , wherein the proof and the verification key are based at least in part on a first generator and a second generator that generate different groups. 
     
     
         6 . The computer-implemented method claimed in  claim 1 , further comprising verifying that elements of the proof are consistent with elements of the evaluation key. 
     
     
         7 . The computer-implemented method claimed in  claim 1 , further comprising verifying that elements of the proof are constructed using matching coefficients. 
     
     
         8 . The computer-implemented method claimed in  claim 1 , further comprising verifying a divisibility requirement on a term of the proof. 
     
     
         9 . The computer-implemented method claimed in  claim 1 , wherein the worker computer system provides a set of I/O values corresponding to input and output values of the circuit. 
     
     
         10 . The computer-implemented method claimed in  claim 1 , wherein the circuit includes one or more addition gates which are modelled with their contributions to the multiplication gates. 
     
     
         11 . The computer-implemented method claimed in  claim 1 , wherein the computation is part of a bitcoin transaction validation. 
     
     
         12 . The computer-implemented method claimed in  claim 1 , wherein verifying that the computation is correct is accomplished by at least:
 providing the proof, the verification key, and a set of I/O values to a verification computer system; and   receiving an indication from the verification computer system that the computation is correct.   
     
     
         13 . The computer-implemented method claimed in  claim 1 , wherein the verification computer system is a blockchain node. 
     
     
         14 . A system, comprising:
 a processor; and   memory including executable instructions that, as a result of being executed by the processor, causes the system to perform the computer-implemented method of  claim 1 .   
     
     
         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 the computer-implemented method of  claim 1 . 
     
     
         16 . A system, comprising:
 a processor; and   memory including executable instructions that, as a result of being executed by the processor, causes the system to perform the computer-implemented method of  claim 2 .   
     
     
         17 . A system, comprising:
 a processor; and   memory including executable instructions that, as a result of being executed by the processor, causes the system to perform the computer-implemented method of  claim 3 .   
     
     
         18 . A system, comprising:
 a processor; and   memory including executable instructions that, as a result of being executed by the processor, causes the system to perform the computer-implemented method of  claim 4 .   
     
     
         19 . 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 the computer-implemented method of  claim 2 . 
     
     
         20 . 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 the computer-implemented method of  claim 3 .