Secure Token Bucket Rate Limiter

Meta Graph API services often enforce per-client request limits using a token bucket. Implement a secure in-memory rate limiter that validates a request signature and then decides whether the request is allowed under a per-key token bucket.

Write a function that processes a list of request events in timestamp order. Each event contains timestamp, key, cost, and signature. A request is valid only if its signature matches the expected signature for that key. Invalid signatures must be rejected and must not consume tokens. Valid requests consume cost tokens only if enough tokens are available at that timestamp.

Formal Specification

Input:

• capacity: integer bucket size
• refill_rate: integer tokens added per second
• secrets: map from string key to string secret
• requests: list of [timestamp, key, cost, signature]

Output:

• Return a list of booleans where each value indicates whether the corresponding request is allowed.

The expected signature for a request is the string: key + ":" + str(timestamp) + ":" + str(cost) + ":" + secret

Each key has its own bucket. Buckets start full at capacity. On each request, refill based on elapsed whole or fractional seconds since that key's previous valid request processing time, capped at capacity.