<p>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.</p>

<p>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 <strong>perfect hash function</strong> iff:</p>

<ol>
<li>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 <a href="http://en.wikipedia.org/wiki/Sponge_function" rel="nofollow">sponge function</a>).</li>
<li>For any initial segment of length d, the set of all natural numbers n such that H(n) shares that initial segment has <a href="http://en.wikipedia.org/wiki/Natural_density" rel="nofollow">natural density</a> = 1/(2^d).</li>
</ol>

<p>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).</p>

<p>Predicated on the assumption that a perfect hash function exists, we can now define the problem <strong>PERFECT HASHCASH</strong> 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.</p>

<p>Given those inputs, it is clear that PERFECT HASHCASH is in the complexity class <a href="http://en.wikipedia.org/wiki/TFNP" rel="nofollow">TFNP</a>, since this is a function problem and a solution is guaranteed to exist.</p>

<p><strong>Can we also identify PERFECT HASHCASH as a member of any complexity class finer than TFNP?</strong></p>

<p>Could it perhaps be in <a href="http://en.wikipedia.org/wiki/PPP_%28complexity%29" rel="nofollow">PPP</a>? <a href="http://en.wikipedia.org/wiki/PPA_%28complexity%29" rel="nofollow">PPA</a>? <a href="http://en.wikipedia.org/wiki/PPAD" rel="nofollow">PPAD</a>? Something else?</p>

<p>For background, see <a href="http://en.wikipedia.org/wiki/Complexity_class" rel="nofollow">Complexity class</a> on Wikipedia.</p>

<hr>

<p><strong>EDIT</strong>: 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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-10-16T14:09:20.230Z
+1 though not everyone on this site is a cryptographer; it may be beneficial to describe the acronyms (FNP, TFNP, etc) or to ask on crypto.stackoverflow.com
makerofthings7
CC BY-SA 3.0
2013-10-25T10:33:53.723Z
I think it is the responsibility of the asker to make his question understandable to potential experts answering the question, giving all background information shouldn't be necessary in every question, it would inflate questions too much.
Murch
CC BY-SA 3.0
2014-02-01T20:47:38.920Z
Polynomial in what value? What's playing the role of input size here?
Nate Eldredge
CC BY-SA 3.0
2014-02-02T00:21:16.067Z
Nate: Difficulty.
Mike Battaglia
CC BY-SA 3.0
2014-02-03T14:12:16.763Z
The pigeonhole principle guarantees that there are an infinite number of solutions for some x. It does not guarantee an infinite number of solutions for every x - I'm not sure we can disprove that there is some x for which there is no solution.
Meni Rosenfeld
CC BY-SA 3.0
2014-02-03T14:15:01.963Z
I'm not sure it makes sense to consider difficulty (or its log) as input size. In particular because if the hash function is fixed as SHA-256, difficulty values above 2^256 are meaningless so you can't talk about asymptotics.
Meni Rosenfeld
CC BY-SA 3.0
2014-02-03T19:45:21.187Z
@pyramids: The pp guarantees there is a solution for some x. Not for every x.
Meni Rosenfeld
CC BY-SA 3.0
2014-02-05T07:00:08.467Z
Many of the questions here are particular to the real-world limitations of using SHA-256, so I overhauled the question to consider an idealized perfect hash function which scales perfectly and which we hope SHA-256 at least approximates decently in real-world situations.
Mike Battaglia
CC BY-SA 3.0
2014-02-06T07:45:26.943Z
@pyramids: My comments were a reply to the OP. The OP said there are infinitely many preimages, which results from the fact that the input string to SHA-256 can be arbitrarily long (it's not confined to any particular input size). This is true and I only contested the "for all x" part. The OP then said that the input size is difficulty, which I said makes no sense. I see no errors in my statement, so I expect an apology for your disrespectful comment and failure to follow the conversation.
Meni Rosenfeld
CC BY-SA 3.0
2014-02-12T08:22:28.843Z
@pyramids: I suggest you read https://en.wikipedia.org/wiki/Pigeonhole_principle. The PP definitely applies for sets of different size and infinite sets. In a bijection from an infinite set to a finite set, there must be an element in the output range with infinitely many preimages.
This argument is pointless - you're not engaging in the technical discussion, you ignore your own faults and you blame me for things I didn't do. "I see no errors" doesn't mean "there must be none", it means the onus on finding errors is on you if you wish to speak disrespectfully as you did.
Meni Rosenfeld
CC BY-SA 3.0
2014-02-12T22:32:46.773Z
@pyramids: Ok. PPP is an interesting read which I was not previously familiar with, but it's an esoteric concept. What I linked to is what is commonly known as the pigeonhole principle. PPP is so called because of its use of the PP. Note that a solution to PC is "either a preimage of 0, or two preimages of an output". The PP guarantees a solution to this because if there is no preimage of 0, the effective output range is reduced by 1 element - hence there are more input values than output values, the PP applies and there are two preimages to some output.
Meni Rosenfeld
CC BY-SA 3.0
2014-02-12T22:37:47.900Z
(PS - Where I said above "bijection" it should have been instead just "function")
Meni Rosenfeld
CC BY-SA 3.0
2014-02-14T09:51:27.497Z
@pyramids: We can agree that there were misunderstandings.
Meni Rosenfeld
<hash><cryptography><algorithms>
What complexity class is Bitcoin's proof-of-work (hashcash) in?
Mike Battaglia
# What complexity class is Bitcoin's proof-of-work (hashcash) in?

(Asked by: username_0 on 2013-10-16)

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(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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/PPP_%28complexity%29)? [PPA](http://en.wikipedia.org/wiki/PPA_%28complexity%29)? [PPAD](http://en.wikipedia.org/wiki/PPAD)? Something else?

For background, see [Complexity class](http://en.wikipedia.org/wiki/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.

**Tags:** hash, cryptography, algorithms

> **Comments:**
> **username_1**: +1 though not everyone on this site is a cryptographer; it may be beneficial to describe the acronyms (FNP, TFNP, etc) or to ask on crypto.stackoverflow.com  
> **username_2**: I think it is the responsibility of the asker to make his question understandable to potential experts answering the question, giving all background information shouldn't be necessary in every question, it would inflate questions too much.  
> **username_3**: Polynomial in what value? What's playing the role of input size here?  
> **username_0**: username_3: Difficulty.  
> **username_4**: The pigeonhole principle guarantees that there are an infinite number of solutions for some x. It does not guarantee an infinite number of solutions for every x - I'm not sure we can disprove that there is some x for which there is no solution.  
> **username_4**: I'm not sure it makes sense to consider difficulty (or its log) as input size. In particular because if the hash function is fixed as SHA-256, difficulty values above 2^256 are meaningless so you can't talk about asymptotics.  
> **username_4**: @pyramids: The pp guarantees there is a solution for some x. Not for every x.  
> **username_0**: Many of the questions here are particular to the real-world limitations of using SHA-256, so I overhauled the question to consider an idealized perfect hash function which scales perfectly and which we hope SHA-256 at least approximates decently in real-world situations.  
> **username_4**: @pyramids: My comments were a reply to the OP. The OP said there are infinitely many preimages, which results from the fact that the input string to SHA-256 can be arbitrarily long (it's not confined to any particular input size). This is true and I only contested the "for all x" part. The OP then said that the input size is difficulty, which I said makes no sense. I see no errors in my statement, so I expect an apology for your disrespectful comment and failure to follow the conversation.  
> **username_4**: @pyramids: I suggest you read https://en.wikipedia.org/wiki/Pigeonhole_principle. The PP definitely applies for sets of different size and infinite sets. In a bijection from an infinite set to a finite set, there must be an element in the output range with infinitely many preimages. This argument is pointless - you're not engaging in the technical discussion, you ignore your own faults and you blame me for things I didn't do. "I see no errors" doesn't mean "there must be none", it means the onus on finding errors is on you if you wish to speak disrespectfully as you did.  
> **username_4**: @pyramids: Ok. PPP is an interesting read which I was not previously familiar with, but it's an esoteric concept. What I linked to is what is commonly known as the pigeonhole principle. PPP is so called because of its use of the PP. Note that a solution to PC is "either a preimage of 0, or two preimages of an output". The PP guarantees a solution to this because if there is no preimage of 0, the effective output range is reduced by 1 element - hence there are more input values than output values, the PP applies and there are two preimages to some output.  
> **username_4**: (PS - Where I said above "bijection" it should have been instead just "function")  
> **username_4**: @pyramids: We can agree that there were misunderstandings.  

---

## 0 answers

