# What complexity class is Bitcoin's proof-of-work (hashcash) in?

It's clear that, as a first pass, Hashcash is in FNP.

For instance, say that R(x,y) is a binary relation, where x is a "maximum" target hash, and y is an input string (working block + nonce), R(x,y) is true iff hash(y) < x. Since SHA256 can be computed in polynomial time, proposed solutions can be checked in polynomial time.

It's also clear that, furthermore, it's in TFNP, since for any x (hash target number), a string y that hashes to less than it is guaranteed to exist.

It's also clear that, furthermore, an infinite number of such y exist for any x - there are an infinite number of strings, but a finite number of hashes, so a solution to this problem is guaranteed via the pigeonhole principle.

Can we use this, or any other similar insights, to identify hashcash as a member of a complexity class finer than TFNP? Would it be in PPP? PPA? PPAD? Something else?

-
Without analyzing the specific hash function used, I don't see how we can even show totality. For an arbitrary hash function (or a random oracle), there's no a priori guarantee that any input hashes to a value less than $x$, although it's extremely likely that one in fact does. –  Ilmari Karonen Oct 20 at 18:42
The problem here is that the nonce usually has a fixed (limited) length, so any asymptotic complexity examinations have no really useful applications to reality. –  Paŭlo Ebermann Oct 21 at 17:02
@PaŭloEbermann: I don't quite see how that's true. I mean, for a fixed collection of transactions then yes, but as I understand it you could accept further transactions into the block and hash more data at once? As such, if you ran out of nonses you could add another transaction to the end of the block –  figlesquidge Nov 15 at 9:47