Hacker News Reader

Comment by grenoire | Hacker News Reader

Like Bitcoin, you can ask clients to find a hash of a string (in the format of, say, 'server_key' + 'random_number' + 'client_adjusted_nonce') with the value of the last four bytes being higher than say 50,000. You can increase the value until 0xFFFFFFFE, where only 1 in 4294967296 hashes would 'pass' the test.

Your client will basically be working on passing the test for a predictable amount of time, dependent on the difficulty threshold.

The neat thing about this method is that although it takes a while to pass the test, it's very fast and easy to check if a test is passed. You'll simply ask the client for the client_adjusted_nonce which gets a value higher than 50,000 (or whatever difficulty threshold you choose). As the author has stated, you can adjust the threshold depending on the strength of the DDOS.

View on HN

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.

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

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.

I remember first seeing such a proof-of-work in the network protocol layer of the game Tribes 2. They opened up the source code for that, named OpenTNL (seems abandoned now) where you could see how it's done. Here's the part that verifies a puzzle:

https://github.com/kocubinski/opentnl/blob/master/tnl/client...

Reply on news.ycombinator.com