Hacker News Reader

Comment by chmike | Hacker News Reader

Sorry, my age may be lower than five. I don't understand. You explain that a hash is computed over a string that is the concatenation of a server key, a random number and a client adjusted nonce. you then lost me with the four bytes. I thought that we were talking about a string of chars, not an array of bytes. The nonce is an integer value ? The client then increases the nonce value I guess. But how does the client know it has finished the work ? In the article it is said that the hash value should start with a number of 0 bits. But this occurence is random by definition of the hash. It could never occur with the nonce tested. So sorry, I still don't understand it.

View on HN

The basic idea is: The client has to create a hash that satisfies a certain condition: Like the first n-digits must be 0, or maybe "the last bytes (when interpreted as a single 32 number) must be larger than x".

So the client does this:

    from itertools import count
    import hashlib

    for i in count():
        h = hashlib.md5("some-nonce:%d" % i).hexdigest()
        if h.startswith("000000"):
            print i
            break

The value "some-nonce" is provided by the server. It also provides the difficulty by saying: I need you to find i which generates a hash that starts with 6 zeros.

So the client calculates hashes for a while, and then submits the value 2652076 to the server. The server can the trivially check if the client did its work correctly:

    $ echo -en "some-nonce:2652076" | md5sum
    00000066adb2fb37a8460da553721c39 # ok, the first 6 digits are 0

The server can simply increase the difficulty by requiring the client to return more leading zeros. Or, if it should be more finegrained, a value below a certain threshold.

Your explanation is fine but this summary will confuse people:

> The client has to create a hash that satisfies a certain condition

What you really want is to create a string whose hash matches the PoW challenge hash.

Maybe I'm taking your example a bit far, but it seems like you'd have to choose the hashing function carefully, correct?

To use your example, it must be 100% certain that a hash with 6 leading zeros is possible to generate with md5.

Also, I'm assuming you don't want clients spending too long on the problem, so it seems like you'd want to have a prediction of roughly how long it would take to compute the answer. Otherwise one client may get lucky after 10 iterations whist another may take 10 million. Are hashing functions predictable in that manner?

Reliable hash functions must be able to map to all combinations of 256, 512, or however many bits they are using.

Thank you very much. That was very clear. In the mean time I searched around on google.

The property of this proof of work is that the duration of the work is random.

How is it possible to know the average work time duration, without doing the measurement ? Is it possible to provide a work time limit so that if a client has really bad luck and can't find the solution in that period can he can issue another question ?

From the ur perspective, this varying work time duration may be an unpleasant experience.

> The nonce is an integer value?

An array of bytes is an integer value - just an arbitrarily large one. You could also just tack the bytes of a 64-bit uint onto the end of the nonce instead of incrementing the nonce (I'm not sure if that is secure, it's just an explanation).

A real example of this is RSA. The length of the key is in bits (and therefore bytes) but is still a representation of a really big integer.

> how does the client know it has finished the work ?

Let's remove hashing from the equation. I, as the server, say to you I've got the following equation:

    Y = (5 + X) * 10

Please solve it so that the last 3 digits of Y are greater than 100 and tell me what you used for X. The simplicity of this equation means that you can easily solve for Y and respond with `12335`. With that response I can just plug X into the equation and see that you've done the work. Now, imagine that there is no such thing as division. Being unable to solve the equation, you'd be forced to brute force each value of X - but proving that you've found X only requires that you run the equation once because we can still multiply:

    Y = (5 + 12335) * 10

With POW, you say that you are looking for a specific pattern of bits or bytes. The pattern can be quite arbitrary: "I want the last 8 bytes to be a 64-bit integer larger than 12345" or even just "the last 64 bits must all be 0." The client will have to try multiple values of X to see which satisfies that constraint. Once the client knows X you no longer need to go through the effort of finding out the value for yourself, you just need to plug X into the equation and see that they found a valid value for X:

    POW = HASH(NONCE & X)

It's like salting a password, but requiring that a portion of the final result has a specific pattern. This forces the client to do a lot of work in a way that is cheap to verify from a computational standpoint.

Reply on news.ycombinator.com