Complexity class of an idealised version of Bitcoin's proof-of-work (hashcash)?
Bitcoin's proof-of-work problem is solved in constant time, since there is no asymptotics. Complexity classes are irrelevant here.