As you know many people don't like the idea of using CPU power in order to make so-called "useless" computations.
I suspect it is possible to rigorously prove that any cryptocurrencies, providing it fulfills a few conditions, has to be based on proof-of-work, and thus on CPU.
So far I can't prove it seriously, so it is just a conjecture. I'd be glad if someone with a solid maths and IT background could bring a demonstration.
So it would look like:
If a cryptocurrency respects the folowing criteria:
* it doesn't discriminate any node of the network ;
* the initial monetary amount available in the network is zero (apart from the genesis block) ;
Then at any time, the probability of generation of a new monetary unit for any node is proportionnal to the CPU of this node.
Obviously this relies on a theoretical, more general definition of "cryptocurrency". I won't give such a definition here but I guess you get the idea.
Every node that wishes to mine proposes a new block-candidate (chained into previous blocks but with no difficulty so that you're not burning CPU power). Say n nodes participate.
They run a protocol to choose a definitive block-candidate. This is not competitive since no one is declared the winner yet. Simple majority vote for a well formed block-candidate is sufficient. All n participants share a hash of the blessed block-candidate.
Then the step I don't know how to do
: Run a cooperative cryptographic protocol that that simulates a fair dice toss, somehow involves the hash of the blessed block-candidate, and ends up randomly selecting 1 of n. This is the next BLOCK and the selected number indicated the owner of the reward for mining the BLOCK.
Rinse and repeat every 10 minutes.
------------------
Now I don't have such a protocol but here's an example of n nodes randomly selecting one of their numbers.
Each secretly chooses a number between 0 and n-1. Each hashes that with a public key he wishes to use to receive the reward. This is his commitment. When he reveals his chosen number later anyone can check that he didn't cheat and change the number.
After all are committed, all reveal their chosen number and check the others for honesty. The sum of the honest revealed numbers modulo the number of honest participants is a random number. Call it the selector.
Sort all the honest keys that were revealed. The selector tells us which key in the sorted list gets the reward.
n nodes cooperated and a new block is generated and one of the nodes randomly received the reward. Low CPU nodes have an equal chance. They just have to have enough power to keep up with the protocol.
-------------------
Useless of course, now that I review this. A newly started node would not know who to trust if the block chain had split recently. Oh well.
