That method seems closer to PoW (as is being done by TOR) than attestation.

The strongest privacy guarantee I've heard behind attestation is it would require two parties to collaborate to break it. If Google attests to a Cloudflare protected site, they can determine who you are by cooperating.