We describe a new network service, the “ticket server”. This service provides “tickets” that a client can attach to a request for a network service (such as sending email or asking for a stock quote). The recipient of such a request (such as the email recipient or the stockbroker) can use the ticker server to verify that the ticket is valid and that the ticket hasn’t been used before. Clients can acquire tickets ahead of time, independently of the particular network service request. Clients can maintain their stock of tickets either on their own storage, or as a balance recorded by the ticket server. Recipients of a request can tell the ticket server to refund the attached ticket to the original client, thus incrementing the client’s balance at the ticket server. For example, an email recipient might do this if the email wasn’t spam. This paper describes the functions of the ticket server, defines a cryptographic protocol for the ticket server’s operations, and outlines an efficient implementation for the ticket server.