Blockchain proof of work needs to be hard to come up with but easy to verify. Captcha solutions are as hard to verify as to find
If the captcha generator is deterministic (always producing the same catcha for a given set of inputs) and the algorithm is shared by the network, then the solution can be trivially and automatically verified by regenerating the captcha from the solution and comparing the outputs.
To prevent attacks using rainbow tables of captcha, the captcha can be generated with two parameters : a "clear text" value to be displayed that must be long enough to make it too complex to bruteforce, and a "salt" value used to alter the distortion of the print, and that would be equivalent to the nonce we are using with the current generation of algorithms.
The clear text can be easily found visually by a human.
The salt is then recovered by brute force.
The difference between a human and a computer is that the human only has to find the salt, which reduces greatly the complexity of the problem.
Having to recover the salt allows to increase the difficulty of resolving the problem versus that of verifying it.
and a captcha problem can't be generated without the generator already knowing the solution.
This can be worked around by inventing a game whereby the generator is positively incentivized as the captcha takes a longer time to resolve.
For instance, the generator of the block is rewarded based on the time taken by the network to resolve his captcha (with an exponentially increasing reward to make it exponentially more interesting to wait just a little bit more rather than submit the solution to his own captcha).
The resolver of the block is rewarded by the right to become the next generator.
This is just an example, but other more complicated games with asymmetrical reward can be designed.
The rule of thumb is to create an equilibrium by setting a positive expectation for respecting the rule, and a negative one for breaking it.
The utility value of the act of resolving a captcha can also be leveraged as an incentive to work around this problem.
Assuming that the agent who inputs the captcha is not able to resolve it himself (a bot for instance), he doesn't know the solution, and therefore cannot give it.
Submitting a captcha for resolution can be implemented as a transaction on the network, with a commission in CaptchaCoin that will subsidize the network.
The problem of this second approach is that, unlike the first one where the captcha is generated, it cannot be verified automatically.
This again can be worked around by setting the rule that a block generated with a false solution is illegal and will be rejected by other "miners", entailing a fork of the block chain.
The incentive is high for other miners to verify the solution submitted by someone else, and to continue on the "right" block chain :
First, a false solution gives the opportunity to repost a solution (and therefore take the reward).
Second, posting solutions on top of a false solution knowing that everybody else will reject this branch warrants a negative outcome for the miner.
RandomCoin - to earn RandomCoin you have to provide "true" randomness to the system (I'm not sure "true" randomness e.g. quantum can be distinguished from simulated randomness). Would be a neat distributed replacement for
random.org.
In theory it's possible to distinguish. In practice a good PRNG with a not-too-long truly random seed can fool pretty much anything you throw at it. In other words, much harder to verify randomness than to generate it.
Also, Intel IVB will have integrated "digital" true RNG making randomness generation easy.
I agree for RNG, it can and must take a huge amount of data to detect with a reasonable confidence that the process is not really random.
Not practical as a proof of work.
Another possibility could be to predict the outcome of a publicly known random process : let's call it GuessCoin
For instance, the Nth decimal of an exchange rate in 3mn from now.
Low decimals are so volatile that there is no practical model to predict them, and can be considered as random for our purpose.
Every 3mn, miners input their guess (randomly) over a fixed period (say 30s).
Because the outcome is random, the reward will effectively be evenly distributed between the miners over time.
Because many miners are rational, they will place their bet on numbers where less people bet so all the solutions will be covered.
The chain doesn't need to know the value of the exchange rate : at next round, the majority of miners will post their answer to the answer that they believe was the right one.
They could even be imprecise and sometime wrong. What matters is that the way their answers are distributed will decide for the "right" path of the chain.
To prevent the case where a miner will cheat by betting on all the possible outcomes at once, he must loose money by playing.
His reward will be proportional to how much money he has bet, and how soon he did so (sooner pays better to compensate for having less information on other participants bets).
With a truly random process and without the ability to predict the future, participating to such a chain would be a zero sum game without some external subsidy.
This is where the minted coins get involved : by being added to the potluck that the lucky winners of the draw will share.
One interesting side effect is that the block chain will fit the random variable on which it is based, with one cycle of delay.
This can be used as a distributed digital recorder of quantifiable random processes.
