Access to some aspect of a service may be limited until a user has invested in performing some amount of computation. Legitimate users typically have excess cycles on their machines, which can be used to perform computation at little or no cost to the user. By contrast, computation is expensive for for-profit internet abusers (e.g., spammers). These abusers typically use all of their computing resources to run “bots” that carry out their schemes, so computation increases the abuser's cost by forcing him or her to acquire new computing resources or to rent computer time. Thus, the providers of free services (e.g., web mail services, blogging sites, etc.), can allow newly registered users to use some limited form of the service upon registration. However, in order to make more extensive use of the service, the user can be asked to prove his legitimacy by investing in some amount of computation.