Verifying work performed by untrusted computing nodes

1. A method for a computing system to verify work performed by two or more untrusted computing nodes, the method comprising:

determining, at the computing system, a first computation;

applying, at the computing system by one or more processors, a transformation function to the first computation to produce a second computation that is different from the first computation;

assigning, at the computing system, the first computation to be performed by a first untrusted computing node;

assigning, at the computing system, the second computation to be performed by a second untrusted computing node while keeping the transformation function secret from the first untrusted computing node and the second untrusted computing node;

receiving, at the computing system, a first result for the first computation determined by the first untrusted computing node and a second result for the second computation determined by the second untrusted computing node;

analyzing, at the computing system by one of the one or more processors, the first and second results to verify the work performed by the first and second untrusted computing nodes;

storing, at the computing system, the first result and the second result in a storage unit that includes results from past computations performed by the first and second untrusted computing nodes; and

determining, at the computing system by one of the one or more processors, whether the first and second untrusted computing nodes are deemed to be trustworthy based on total results for each of the first and second untrusted computing nodes stored in the storage unit, wherein the first and second untrusted computing nodes are deemed to be trustworthy in response to a majority of the total results for each of the first and second untrusted computing nodes being valid, and wherein the first and second untrusted computing nodes are deemed to not likely be trustworthy in response to the majority of the total results for each of the first and second untrusted computing nodes being invalid.

2. The method of claim 1 , wherein the analyzing, at the computing system, the first and second results to verify the work performed by the first and second untrusted computing nodes comprises:

removing the transformation function from the second result by applying an inverse of the transformation function to the second result; and

comparing the first result with the second result after the transformation is removed,

wherein the first result being substantially the same as the second result after the transformation is removed implies the first and second computations have each been correctly performed and valid results have been provided by the first or second untrusted computing nodes, and

the first result not being substantially the same as the second result after the transformation is removed implies that either the first untrusted computing node or the second untrusted computing node, or both the first and second untrusted nodes, have provided an invalid result.

3. The method of claim 1 , wherein the first computation is one of a plurality of computation components that form a third computation.

4. The method of claim 1 , further comprising:

determining the transformation function applied to the first computation, the transformation function including a plurality of transformation function components;

selecting a first transformation function component of the plurality of transformation function components; and

applying the selected first transformation function component to the first computation to produce the second computation.

5. The method of claim 1 , wherein:

each of the first and second untrusted computing nodes is one of a plurality of untrusted computing nodes,

the assigning, at the computing system, the first computation to be performed by the first untrusted computing node comprises randomly selecting, at the computing system, the first untrusted computing node from the plurality of untrusted computing nodes, and

the assigning, at the computing system, the second computation to be performed by the second untrusted computing node comprises randomly selecting, at the computing system, the second untrusted computing node from the plurality of untrusted computing nodes.

6. The method of claim 1 , wherein the analyzing, at the computing system, the first and second results to verify the work performed by the first and second untrusted computing nodes comprises applying one or more probability functions to the first and second results to determine if the first and second results are valid.

7. The method of claim 6 , further comprising, after determining that the first and second results are invalid, randomly selecting a third untrusted computing node and a fourth untrusted computing node to perform the first computation and the second computation, respectively.

8. A non-transitory computer-readable media having stored thereon computer-executable instructions that, in response to execution by a processor, cause a computing system to:

determine a first computation;

apply a transformation function to the first computation to produce a second computation that is different from the first computation;

assign the first computation to be performed by a first untrusted computing node;

assign the second computation to be performed by a second untrusted computing node while keeping the transformation function secret from the first untrusted computing node and the second untrusted computing node;

identify a first result for the first computation determined by the first untrusted computing node;

identify a second result for the second computation determined by the second untrusted computing node;

analyze the first and second results to verify the work performed by the first and second untrusted computing nodes;

store the first result and the second result in a storage unit that includes results from past computations performed by the first and second untrusted computing nodes; and

determine whether the first and the second untrusted computing nodes are deemed to be trustworthy based on total results for each of the first and second untrusted computing nodes stored in the storage unit, wherein the first and second untrusted computing nodes are deemed to be trustworthy in response to a majority of the total results for each of the first and second untrusted computing nodes being valid,

and wherein the first and second untrusted computing nodes are deemed to not likely be trustworthy in response to the majority of the total results for each of the first and second untrusted computing nodes being invalid.

9. The non-transitory computer-readable media of claim 8 , wherein to analyze the first and second results to verify the work performed by the first and second untrusted computing nodes, the computer-executable instructions are executable by the processor to cause the computing system to:

remove the transformation function from the second result by applying an inverse of the transformation function to the second result; and

compare the first result with the second result after the transformation is removed,

wherein the first result being substantially the same as the second result after the transformation is removed implies the first and second computations have each been correctly performed and valid results have been provided by the first or second untrusted computing nodes, and

the first result not being substantially the same as the second result after the transformation is removed implies that either the first untrusted computing node or the second untrusted computing node, or both the first and second untrusted nodes, have provided an invalid result.

10. The non-transitory computer-readable media of claim 8 , wherein the first computation is one of a plurality of computation components that form a third computation.

11. The non-transitory computer-readable media of claim 10 , wherein the computer-executable instructions, in response to execution by the processor, further cause the computing system to:

determine the transformation function applied to the first computation, the transformation function including a plurality of transformation function components;

select a first transformation function component of the plurality of transformation function components; and

apply the selected first transformation function component to the first computation to produce the second computation.

12. The non-transitory computer-readable media of claim 8 , wherein:

each of the first and second untrusted computing nodes is one of a plurality of untrusted computing nodes,

assignment of the first computation to be performed by the first untrusted computing node comprises random selection, at the computing system, of the first untrusted computing node from the plurality of untrusted computing nodes, and

assignment of the second computation to the second untrusted computing node comprises random selection, at the computing system, of the second untrusted computing node from the plurality of untrusted computing nodes.

13. The non-transitory computer-readable media of claim 8 , wherein to analyze the first and second results to verify the work performed by the first and second untrusted computing nodes, the computer-executable instructions are executable by the processor to cause the computing system to apply one or more probability functions to the first and second results to determine if the first and second results are valid.

14. The non-transitory computer-readable media of claim 13 , wherein, after the determination that the first and second results are not valid, the computer-executable instructions, in response to execution by the processor, further cause the computing system to randomly select a third untrusted computing node and a fourth untrusted computing node to perform the first computation and the second computation, respectively.

15. A system comprising:

a computer processor;

a first module operatively coupled to the computer processor and configured to generate a first computation;

a second module operatively coupled to the computer processor and configured to generate a transformation function configured to be applied to the first computation to produce a second computation that is different from the first computation;

a third module operatively coupled to the computer processor and configured to assign the first computation to be performed by a first untrusted node and configured to assign the second computation to be performed by a second untrusted node while the transformation function is kept secret from the first and second untrusted nodes;

a fourth module operatively coupled to the computer processor and configured to receive a first result for the first computation determined by the first untrusted node and a second result for the second computation determined by the second untrusted node;

a fifth module operatively coupled to the computer processor and configured to analyze the first and second results to verify the work performed by the first and second untrusted nodes; and

a storage unit that includes a history of validity of results provided by the first and second untrusted nodes, wherein the fifth module is further configured to use the history to determine trustworthiness of the first and second untrusted nodes based on total results for each of the first and second untrusted computing nodes stored in the storage unit, wherein the first and second untrusted computing nodes are deemed to be trustworthy in response to a majority of the total results for each of the first and second untrusted computing nodes being valid, and wherein the first and second untrusted computing nodes are deemed to not likely be trustworthy in response to the majority of the total results for each of the first and second untrusted computing nodes being invalid.

16. The system of claim 15 , wherein:

the first result includes a series of first intermediate results;

the second result includes a series of second intermediate results; and

the fifth module is further configured to compare the first intermediate results with the second intermediate results to determine if the first untrusted node or the second untrusted node has provided invalid results.

17. The system of claim 16 , wherein the fifth module is further configured to apply an inverse of the transformation function to the second intermediate results and then compare the first intermediate results with the second intermediate results.