Quote from: Gpx on December 06, 2017, 04:21:37 PM

What is the proof of work?

A partial preimage attack on (double) SHA-256, done by brute force.

Quote from: Gpx on December 06, 2017, 04:21:37 PM

When a miner solves the nonce value, is that the proof of work or is there some other process that has to be done in addition to solving the nonce to complete the block?

It is not a matter of solving the nonce value. The nonce is meaningless, in and of itself; that is why its called a nonce. Or perhaps it may be said, the nonce is meaningfully meaningless. The only means of bruteforcing a hash (partial) preimage is to repeatedly change the input until you get the desired output. The nonce is the part which gets changed; it is really a sort of a throwaway value, only there to provide arbitrarily changeable input bits.

SHA-256 is assumed (or pretended, depending on whom you ask) to have the properties of a random oracle. Simply for the sake of understanding, pretend that for each increment of the nonce, you are generating a random number. If target difficulty requires an unbroken string of x zeroes in the highest digit positions, then imagine how many times youd need to generate a 256-bit random number before you have the luck to draw one which starts with x zeroes. Alternatively, think of it as a 256-bit string of coin flips with H=0 T=1. How long will it take you by random chance to get a string starting with x heads in a row?

(Question for anybody: Would the probability equal that of simply flipping x heads in a row, or would you need to repeatedly flip whole 256-bit strings of flips until you get one which starts with x heads in a row? I seem to have temporarily confused myself here. Checked in in alpha state. May be patched.)

Another interesting way to look at it: If SHA-256 has good avalanche (as we suppose), then for a single-bit flip in its input, each bit of output has a 50% probability of flipping. Implications for bruteforcing a partial preimage are left as an exercise to the reader.

(I used several basic/intermediate level cryptography terms of art here. I tried to pinpoint those in boldface so you can look them up if youre unfamiliar with them.)