Lots of VPNs do that.

Cryptography where users have to trust the server is a bit funky

Neat idea. Kagi is doing something similar for search, where they can verify that you have paid for the privilege of using the service, but can’t link your actual account.