When I first heard about coins like curecoins where the proof of work is actually useful, the first thing that came to my mind is that the reason why hashing works is because hashing enforces that the block rewards goes to the person that found the hash. When the miner informs his peers of his block, his peers cannot steal his block. Whereas with a useful proof of work, the peers can just modify the block to make it seem like they found it. "Oh you found a prime that's this difficult and has these properties? Wait, I found the same exact one a minute earlier!" Granted I didn't spend too much time trying to figure out a way around it. Maybe there's a way to encode the the address of the person that found it in the prime. Looking forward to see what Sunny King came up with.
IE: the content of the hash is dependent on the content of the block header which (because of the merkle root) ensures the coinbase pays the miner.
It could be that the proof of work algorithm is something like:
Generate a prime number in the form:
k * 256 ^ n + b
where k is the merkle root + nonce, etc.
EG: k = blockheader (presumably prefixed or something to ensure consistent number of digits; as this will have some effect on the difficulty)
That would be one way because the prime found would depend on (or rather part of it is) the blockheader. Similar to SHA256 you don't know if there's a solution with the particular blockheader you're using (so you have to search the space - well, if things are done 'right').
I was going to say verifying the prime is difficult; but it's not. Verification of primes can be done in polynomial time, so it's not so bad. Factorizing is the hard bit.
So we can have quick to verify, contains the blockheader.
The difficulty is easy to integrate; but unfortunately will have a negative effect on verification time (the only way to make prime generation more difficult is to make the primes bigger, so they take longer to verify). Remember that verification is part of the mining process, so there has to be few enough solutions out there to make looking for them harder to ensure consistent verification times; not sure how this will interact with this PoW style.
So, issues I can see: overcoming the relationship between the difficulty and verification time (if there is one) and ensuring that there are few enough primes out there to find.
The first means the difficulty should shrink the size of the acceptable solution pool (as opposed to making bigger numbers), and the second means arbitrary conditions will need to be chosen by which to define the solution pool.
Anyway, curious to see how the PoW works, and as to why there hasn't been any info made open about it yet.
