[throwaway2016a]

Two solutions:

1. As other posters pointed out. The blacklist is probably pretty small and can live in memory on your apps servers. If you have a distributed raft network or something to keep it in sync across nodes, even better.

2. You can avoid checking it against the DB unless the API call is sensitive (example: modifies data).

[floatboth]

Yeah, of course you can do these things. I really meant to say, "there now exists server-side state for this" — I'm bothered by how existence of that state defeats the statelessness benefits of signature-based schemes, not the fact that I have to query a remote database.

Oh, and also: "only store a blacklist" does not work if you want to provide the "revoke this app you gave access to a while ago and now it's spamming" functionality like in most social networks.