The growth of computations distributed over the Internet, while spectacular, is held back by the risk that dishonest participants might claim credit for work they have not done. This type of cheating is of particular concern in commercial settings where participants get paid for their contribution. In this talk, we will only consider cheaters who are motivated by financial gain.

Consider a distributed effort to break a DES-challenge. The goal is to find the key that matches a given plaintext to a given ciphertext. The keyspace is partitioned into shares. Each participant gets paid to test all the keys in one share. If the search were to end without revealing the solution to the challenge, we would want a way to track the cheaters.

To discourage and detect cheating, we propose schemes that let participants prove that they have done almost all the work they were assigned with high probability. In this talk, we use as our canonical example of a distributed computation the inversion of a one-way-function f on one of its outputs.

A simple solution is to reward with a prize the discovery of the key (the inversion of the one-way-function). This scheme is currently used to encourage participation in distributed cipher-cracking. The user who discovers the correct key wins a prize, while the others get nothing. Since the expected pay-off is proportional to the amount of work done, this scheme eliminates cheating motivated by financial gain. In a setting where millions of participants are involved however, it is not acceptable that the compensation for work should have the high variance of a prize.

Our basic approach is to expand the set of values whose discovery is rewarded with a prize. The supervisor of the computation defines for each participant a set of "ringers". Ringers are images by f of values in the domain to be searched by a participant. Participants are rewarded not only for finding the correct key, but also for finding any pre-image of a ringer by the function f. The ringers do not contribute to our main goal of inverting f on a certain input. Rather, they act like milestones along the computation, which let us estimate the progress of a participant and pay him accordingly.

The weakness of this basic ringer scheme is that a participant knows when the last ringer is found. There is no incentive to proceed with the computation beyond that point, since cheating will go undetected. As a result, the maximum expected coverage we can enforce with n ringers is 1-1/n. Observe that we want to keep the number of ringers as low as possible to limit the communication overhead between the supervisor and the participants.

To fix this weakness, we propose to hide the number of ringers from participants by adding a random number of "bogus" ringers. Unlike true ringers, bogus ringers do not have a preimage by f in the interval given to a participant. With the "proper" distribution of true and bogus ringers, we can enforce with n ringers a coverage exponentially close to one (as a function of n.)

Another way of enforcing a coverage constant exponentially close to one is to "blur" the ringers. Participants are required not only to report the preimages of ringers, but all the preimages of values that "look like" ringers. To "look like" could mean for example to agree on the first 20 bits.

To conclude, we propose an efficient scheme to protect a certain type of distributed computations against cheating motivated by financial gain. Our scheme has minimal computational and communication overhead, yet provides guarantees that almost all the work has been done. Other applications of our schemes include uncheatable benchmarks for distributed computer clusters of estimation of the size of a proprietary database. Further work is needed to extend our results to more general classes of distributed computations.