# Complexity class of an idealised version of Bitcoin's proof-of-work (hashcash)? [closed]

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:

1. $H:\mathbb N \to \{0,1\}^\infty$; That is, $H$ maps each natural number to an infinite binary sequence, and which the time complexity to compute any initial segment $s$ is polynomial in the size of $n$ and $s$, (making it a sponge function).
2. 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 $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 the zero 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.

• 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 '13 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 '13 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 – Cryptographeur Nov 15 '13 at 9:47
• This question is a duplicate of bitcoin.stackexchange.com/q/13796/488 on our sister site Bitcoin SE. – Paŭlo Ebermann Feb 11 '14 at 21:28
• They told me to repost it here, so I did. I've also edited it to be a bit more mathematically precise about where asymptotics are involved. – Mike Battaglia Feb 12 '14 at 1:37