In order for Bitcoin to work, the electricity and resources for the computation needs to be "wasted" in a way. If there was some additional value to the computation, then people would just be able to afford to node more for the same amount of reward, including the attacker.
You say that the the electricity and resources need to be "wasted" for BitCoin to work. Well this is already not the case as, over time, the electricity and resources yield BitCoins which are valuable. If the reward for generating BitCoins doubled would that make the system more secure, less secure or would it leave it essentially unchanged. If the answer is anything but the latter then what do you suggest the generation reward be set to in order to maximise security?
You say that if there was some additional reward for the computation then people would be able to afford more nodes for the same reward. Since the same financial incentives operate on both sides of the security equation, the effect is cancelled out.
You also neglect that the most powerful incentives for both participation in the system and attacks on it are not financial. If the bulk of the proof of work contributed to something that gives geeks warm and fuzzy feelings like factoring numbers or folding proteins but which could not be translated into money then you'd get many people participating in supporting BitCoin.
On the other hand, I doubt that attackers would be increasingly incentivised into defrauding the system if their attempts at fraud had the pleasant side effect of folding a few proteins.
I admit though that suitable useful proof of work functions would have to be vetted so that they did not facilitate or incentivise fraud .. so attempting to find private keys is right out.
The verification and proof of work have to be one and the same problem, so that you can't do one (thus getting paid for your verification service), without doing the other (thus ensuring you're not cheating the system).
They do not have to be the same problem. The proof of work would be the "useful" computation. People would check that to see that the work had been done. The hash at the end just verifies that the block hasn't been tampered with and would not have a long run of leading zeros.
So block n+1 contains a nonce and the transactions that have arrived since the publication of block n plus a "useful" proof of work using the hash of block n and the nonce in n+1 as the relevant starting condition. This would all be hashed together ONCE and the hash appended would be used as the part of the starting conditions for the useful work for block n+2. The nonce is necessary so that not all clients are racing to complete the same piece of work. Ideally the nonces would be unique to prevent work being duplicated or the nonce space should be large enough that this is rare.
Additional qualities required for a suitable "useful" proof of work is that one should be able to ascribe it a probablisitic "quality" rating. For hash functions we say that a hash with a smaller value has a higher quality.
It also needs to be smoothly decreasingly useful even if you terminate the work early. This means that all the clients who weren't lucky enough generate work with a good enough quality rating stop what they are doing and send the results of their useful work to some suitable useful work collecting server and then pick up the new hash value and roll the dice again with a new batch of useful work.
It's a bit complicated but worth it I think. I have a longer post in development which outlines the security case for it being desirable.
ByteCoin
