Patent ID: 7363244

Claim:
A method comprising: providing, by a service provider, a service responsive to one or more service requests from one or more of a plurality of serviced clients, wherein the plurality of serviced clients including an audit client which audits the services provided by the service provider, and the service provider maintains a Bloom filter which is a bit-vector of length m; and wherein the service requests include a plurality of audit client requests, by the audit client, to the service provider; negotiating, between the service provider and the one or more requesting clients in the plurality of serviced clients, one or more service request tags which represent the one or more service requests, wherein the service request tags include audit client tags associated with the audit client request; inserting the service request tags associated with the one or more service requests into the Bloom filter, wherein inserting a tag into the Bloom filter involves: inputting the tag into a set of hash functions associated with the Bloom filter; generating a set of bit positions based on the outputs of the set of hash functions; and setting the bits corresponding to the generated bit positions in the Bloom filter; sending the Bloom filter from the service provider to the audit client; computing an estimated number of the one or more serviced requests, by the audit client, based on the Bloom filter which contains both the service request tags and the audit client tags, wherein computing the number of serviced requests by the audit client prevents the service provider from cheating.