To formulate this question precisely, I will define an idealized hypothetical "perfect" hash function H(n) which has nice scalability properties, and will formulate a problem PERFECT HASHCASH in terms of that, understanding that practical considerations may end up yielding only an approximation of this ideal.
To keep it simple, we will say that our hash function H(n) takes as input a single natural number n. Then we say that H(n) is a perfect hash function iff:
- H(n) maps each natural number to an infinite binary sequence, of which the time complexity to compute any initial segment s is polynomial in the size of n and s, (making it a sponge function).
- For any initial segment of length d, the set of all natural numbers n such that H(n) shares that initial segment has natural density = 1/(2^d).
The first thing formalizes the scalability of our function, and the second thing formalizes the idea that we want all hashes to appear roughly "equally often" as an output. Other than that, our perfect hash function is a black box, and we don't care much about exactly how it works, so long as it meets the above properties, as well as the usual desiderata applying to hash functions (easy to compute, hard to invert, hard to find collisions, etc).
Predicated on the assumption that a perfect hash function exists, we can now define the problem PERFECT HASHCASH as follows: PERFECT HASHCASH takes as input a perfect hash function H, a natural number n, and an all-zeroes vector 0^d of length d, which can be thought of as a unary representation of d. A solution to PERFECT HASHCASH consists of an n and d such that H(n) starts with 0^d.
Given those inputs, it is clear that PERFECT HASHCASH is in the complexity class TFNP, since this is a function problem and a solution is guaranteed to exist.
Can we also identify PERFECT HASHCASH as a member of any complexity class finer than TFNP?
Could it perhaps be in PPP? PPA? PPAD? Something else?
For background, see Complexity class on Wikipedia.
EDIT: the above question has been overhauled, as in the way that I originally formulated it I assumed that SHA256 is what I'm now calling a perfect hash function. Many people have noted in the comments that this may not be true, so rather than place the emphasis in this question on whether SHA256 specifically has the nice scaling properties we want, I defined an idealized hash function that we hope SHA256 at least approximates nicely enough for real-world purposes, and rephrased the question in terms of that.
As a final note to clear up any potential confusion, to make PERFECT HASHCASH resemble real Hashcash, we'd have to make one more assumption: that there exists some way to start with a block of data (an email, a Bitcoin block, etc) and somehow derive a characteristic perfect hash function from that, perhaps by "salting" a different perfect hash function in a way that the result is also another perfect hash function. So in the case of a "perfect Bitcoin," all of the miners on the bitcoin network would be working with their own unique perfect hash functions H'(n) which are somehow tied to the block they're working on, and each miner would simply try H'(0), H'(1), H'(2), ... in order until they find something starting with enough 0's. Each H' would be a different input to PERFECT HASHCASH.