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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Oct 20 '13 at 18:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Paŭlo Ebermann Oct 21 '13 at 17:02
  • $\begingroup$ @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 $\endgroup$ – Cryptographeur Nov 15 '13 at 9:47
  • 1
    $\begingroup$ This question is a duplicate of bitcoin.stackexchange.com/q/13796/488 on our sister site Bitcoin SE. $\endgroup$ – Paŭlo Ebermann Feb 11 '14 at 21:28
  • $\begingroup$ 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. $\endgroup$ – Mike Battaglia Feb 12 '14 at 1:37

Bitcoin's proof-of-work problem is solved in constant time, since there is no asymptotics. Complexity classes are irrelevant here.

| improve this answer | |
  • $\begingroup$ I don't understand how you arrived at the conclusion that complexity classes are irrelevant with an algorithm? Finding a correct hash is an algorthm after all. $\endgroup$ – user10775 Dec 7 '13 at 19:04
  • $\begingroup$ It is an algorithm, but it finishes in constant time. $\endgroup$ – Dmitry Khovratovich Dec 8 '13 at 11:18
  • 1
    $\begingroup$ Two points: (1) With the clarified question this is out of date; (2) I'm sure its my error, but this seems incorrect. Why should it be solved in constant time? Yes there are only finitely many nonces, but there are infinitely many transactions the block might contain $\endgroup$ – Cryptographeur Feb 12 '14 at 1:55
  • $\begingroup$ Because the condition is that a certain subset of the 256-bit hash value is equal to 0. Of course it is satisfied in constant time. $\endgroup$ – Dmitry Khovratovich Feb 12 '14 at 9:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.