The client performs work given to it by the server and then sends back the work unit. We further assume that we have the ability to make a transcript of a computation. Protocol Server sends work unit to client. Client performs work on work unit. Client creates transcript S of computation.
Server flips a coin at random to decide whether to audit client.
Alternatively, the server selects a random subset of clients to audit and checks whether this client is in that set. Alternatively, server asks Client to send a transcript S' for the specified work unit. If they do then client is considered compliant. If they do not, then client is considered cheating. Paul Crowley on sci.crypt suggested that producing a fake transcript must be at least as expensive as producing a real one.