I'm toying around a distributed computing project. The client application asks for a problem to solve. The server returns a problem description from a "problems pool". When the client finishes, it sends back the solution.
I cannot trust my users, and so I cannot trust their solutions. I need somehow to validate their solutions are correct (for some definition of "correct"). Anyone could send a wrong solution to the problem they are assigned. I want to validate two things:
- No one can post a solution for a problem that I have not give them. I think this one is easy: I give a them an HMAC of the problem ID plus my secret, and check that they send the same tokens with the solution.
- I want to check that the user's solution is correct. I want to do this check without solving the problem by myself. And more important, I don't want the solution to be problem-specific, so I cannot use some property of the problems, which could work for NP-(Complete/Hard) problems, for instance.
Suppose, for the sake of the discussion, I want to compute the digits of PI. So how can I be sure that some user's response for the nth digit of PI is correct? Should I give the same problem to several users and cross validate? How is this problem handled in projects like SETI@home and others?