Creating an altcoin that self-modifies its proof of work algorithm

[Hyena]

How to create a bitcoin alternative that has its proof of work algorithm randomly changing (self-modifying) so that no ASICS could ever be built for mining?

I propose embedding some scripting language like Lua (or completely custom) to the coin. The script would be saved in the blockchain once and all the next blocks can be mined only with the algorithm described in that script.

If a block is found then the reward for the next block would decrease if a miner used the same script. This means that miners can use the same algorithm only a couple of times and should be constantly proposing new and different algorithms for mining.

The algorithm should be randomly generated and there should be limitations for it. For example the size cannot be larger than 1KB.

Knowing that it's proven to be impossible to make a program that could find out if another program really does what it is supposed to do I suspect that such altcoin remains utopic. However, the problem statement is still there and maybe the means for finding a solution can be changed to achieve the same goal. Discuss.

[1715187171]

1715187171

[1715187171]

1715187171

[1715187171]

1715187171

[1715187171]

1715187171

[wumpus]

Although the idea of a self-evolving code is quite interesting, isn't this kind of what bitcoin is already doing? Except that the thing "evolving" is not the code but single value, the difficulty value. This is sufficient to keep the PoW difficult enough with ever faster hardware.

It looks like you want to select for reprogrammable as well as fast hardware? Why does that make sense in the longer run? How is a "proof of adaptability to different work" superior to just a "proof of work"?

You'd want to evolve an ever-changing benchmark that is as hostile as possible to specific hardware acceleration, and that can also be used as proof of work. This is a very difficult problem as there are strict, specific requirements to code that can be used as proof of work. see also: http://bitcoin.stackexchange.com/questions/5617/why-are-bitcoin-calculation-useless/5618#5618

Good luck with your experiment in any case.

[Sergio_Demian_Lerner]

Check out my old post: http://bitslog.wordpress.com/2011/12/31/mining-for-science/
(section Mining for Algorithm Discovery)

I discuss an "almost"  Turing complete mining idea.

Best regards, Sergio.

[Peter Todd]

You'd want to evolve an ever-changing benchmark that is as hostile as possible to specific hardware acceleration, and that can also be used as proof of work.

With regards to hardware acceleration a lot of people are of the opinion that a PoW function where ASICs can achieve significantly better performance than off-the-shelf computers is obviously superior to a PoW function where that is not true, like scrypt with appropriate parameters.

There are trade-offs with both approaches. ASICs-compatible PoW functions, provided that the 'good guys' have access to them, make it very difficult for an attacker to gain access to a lot of hashing power temporarily or quickly. For instance if you wanted to attack Litecoin you could rent or steal a pile of GPU computing power temporarily for a lot less cost than buying a bunch of Bitcoin ASIC hashing power outright, and renting or stealing Bitcoin hashing power isn't that easy. (although it is much easier than it should be...)

My guess is you only need to perform a temporary attack, like a 100 block deep re-org, to destroy the trust in the system permanently; you don't need to have the ability to sustain the attack indefinitely.

[Vorksholk]

What I think could be a nice midpoint between what you propose and what might be possible to easily implement, as I have proposed before (and may work on in the future) is a coin based on an algorithm that has a step order, or some post-processing steps. Some of the steps would be entropy-reducing (not one-to-one functions) while others would be weak mixing functions, that just act to further complicate the algorithm.

The step order of the hashing algorithm would be determined by the, say, last 8 characters of the most recent block (or the retarget block). Some steps would have huge lookup tables, which would be memory-intensive. The point is that some weeks (or retarget periods), GPU mining would be easier than CPU mining. Others, CPUs would have an advantage.

I have actually already made the algorithm, and did so with a few other people for a programming challenge. However, if I eventually make this alternate currency, I'll likely tweak the algorithm more.

A miner, like cgminer, would simply also be sent the step order from the pool/solo miner, allowing for an algorithm that changes and, in result, is ASIC-resistant, while still being something that could be predictable, with steps made in an intelligent manner so that a program that writes a new algorithm every retarget doesn't make an extremely unbalanced algorithm.

Sadly, I don't know enough C++ (or C, or C# ...) to make this a possibility. It's an interesting idea, though.   

[gmaxwell]

I think this is a fantastic idea.

I look forward to owning all of the resulting coins. (as I will mine blocks that makes the next POW require factoring a large near-prime composite specified in this block...)

 

More seriously, there have been LUA pow proposals before. No one knows how to make them secure against that kind of obvious gamesmanship much less more subtle kinds.