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:

  1. 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.
  2. 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?

1 Answer 1


Distributed.net solved this by assigning the same search space to multiple users, and validated them that way. (They are probably still doing it.)

Depending on computation cost and participation levels, you might wish to double check only a fraction of packets. Comparing 5% should give you a statistically valid chance of catching a cheater. Be sure to randomly distribute the duplicate challenge blocks around, so that you don't only have User A validating User B's packets. Don't identify the test blocks in any way, such as sending a different size or range, or a cheater may tamper with them. And finally, know that one positive result does not indicate a malicious cheater. It could be a hardware or software problem. You need to see a pattern of abuse before you pull the plug on someone.


Here's a link to distributed.net's Operational Code Authentication document. It describes the security mechanisms by which they handle validating work work distributed to untrustable clients. Of particular interest are some of the other security problems they've identified, such as "solution stealing", where a malefactor distributes a modified client to someone else. The modified client suppresses the "winning results" signal, and instead sends the results to the attacker, who unfairly claims and collects the reward for the find.

  • Thanks, I like this approach. It is very close to what I have thought, but I like the idea of validating only a fraction of the packets. Can you provide some links? Nov 15, 2013 at 20:33
  • I edited the question. Regarding statistical validation, you'll have to find a book on the topic yourself - I rely on an old copy of the Datamyte Handbook for Statistical Process Control methods for a lot of that kind of stuff. Nov 15, 2013 at 21:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .