Hash algorithm that cannot be implemented in ASIC ?

[gmaxwell]

I wonder if the network could somehow take psuedorandom data from the block chain and then use this to create a random hash algorithm. It's hard to imagine how this would be done without using a fixed set of algorithm patterns, though. Maybe each node could use the pseudorandom data as input into identical evolutionary algorithms that end up producing one acceptable hash algorithm. (Can a computer prove that a random algorithm is secure enough for PoW?)

The variable portion of the PoW algorithm doesn't have to be secure, one can sandwich the variable portion between a pair SHA-2 for strong cryptographic security. The anti-ASIC meat in between needs to be only sufficiently close-to-bijective and reasonably chaotic. No need to attempt a complete proof of that, just a decent test of in a subspace that there are no fixed-points.

https://en.wikipedia.org/wiki/Fixed-point_theorem

It's not as simple as that, e.g. I could grind the circuit generator to find 'random' hash algorithms which a heuristic solver of mine can answer much faster than naive execution.  There have been some altcoin POW proposals that failed pretty seriously to this.

It's also the case that whatever parameterization you create, someone can just create an ASIC specialized for it... if nothing else stripping excess IO pincount and other costs.  Keep in mind, CPUs are ASIC too, ones with incredibly complex, secret, patented designs-- which can be mass produced by their makers at a marginal price which is a tiny fraction of what they sell for... "Be careful what you ask for".

Basically, all i need is an operation that cannot be executed on an ASIC.

CPUs are asics. The specific thing you're asking for is deeply impossible. The best you could ask for is something where existing general hardware was not worse than specialized hardware, and that seems really likely to be impossible too, simply because by definition general hardware will have "fat". If nothing else it's perfectly fine for a miner to run at a error rate approaching 1% (sometimes more!) but you'd never design a CPU to operate under those conditions. Since mining, by definition seeks towards 0 profits, even small factors like 10x efficiency would easily make a general purpose part totally unusual-- but perhaps your question is not really related to mining. But then as I pointed out above, even if you were successful, the result might just be giving a free license to Intel and AMD, which probably wasn't what you wanted.

I can't say that it's impossible to do better than the work-function bitcoin has... but it's very easy to do substantially worse.

[dogie]

I wonder if the network could somehow take psuedorandom data from the block chain and then use this to create a random hash algorithm. It's hard to imagine how this would be done without using a fixed set of algorithm patterns, though. Maybe each node could use the pseudorandom data as input into identical evolutionary algorithms that end up producing one acceptable hash algorithm. (Can a computer prove that a random algorithm is secure enough for PoW?)

The variable portion of the PoW algorithm doesn't have to be secure, one can sandwich the variable portion between a pair SHA-2 for strong cryptographic security. The anti-ASIC meat in between needs to be only sufficiently close-to-bijective and reasonably chaotic. No need to attempt a complete proof of that, just a decent test of in a subspace that there are no fixed-points.

https://en.wikipedia.org/wiki/Fixed-point_theorem

That actually sounds promising; rather than just varying the service string every block, you also vary the algorithm. I'm looking at this through absolutely naive eyes so there's a good chance that I've completely misunderstood how things works but here goes; simplified:

1) Take previous block header -> Put through a known, standard algorithm to generate a string.
2) Break that string up into areas, ie the first 4 characters = 1 new string, second 4 characters = another new string
3) Map those new strings with range values into configurations of the algorithm either by function or feed. [I just made that up].
     a) By function means you either loop the entire thing X times (not that useful) or run multiple loops on individual some operations in sha2. Ie run S1 multiple times using the outputs as new inputs then continue as normal. Or even more complex, vary how many times the individual operations rotate and by how much.
     b) By feed means you run multiple loops or partial loops, and then repeat it but with a translated character order. So ABCDEFG = FAEBGDC and repeat. The translation string from the block header could include one set of translations or multiple sequential ones to increase the number of combinations and prevent ASICs calculating them all.
4) PoW that, somehow .

As long as the resultant algorithm is sufficiently different or potentially different from say sha-256, it couldn't be overcome by a standard SHA256 ASIC. Even if you made areas on an ASIC to do the component functions of a generic sha2, you'd be limited in speed by your controller which surprise surprise isn't that different than a CPU. And as soon as you stop running a standardised sha2 function then ASIC usage should just be non existent.

[2112]

It's not as simple as that, e.g. I could grind the circuit generator to find 'random' hash algorithms which a heuristic solver of mine can answer much faster than naive execution.  There have been some altcoin POW proposals that failed pretty seriously to this.

It's also the case that whatever parameterization you create, someone can just create an ASIC specialized for it... if nothing else stripping excess IO pincount and other costs.  Keep in mind, CPUs are ASIC too, ones with incredibly complex, secret, patented designs-- which can be mass produced by their makers at a marginal price which is a tiny fraction of what they sell for... "Be careful what you ask for".

CPUs are asics.

I'm sorry. I'm having problems posting reliably now.

The goal shouldn't be "impossible to make an ASIC". The goal should be "an ASIC should be a substantial fraction of a general-purpose CPU", therefore the cost of developing a competitive ASIC should be a substantial fraction of developing a competitive CPU.

It isn't trivial but it also isn't a completely uncharted territory of research.

The general technical methodology of semi-randomly changing algorithms to optimize certain figure of merit is called "genetic programming".

The point is not to make it impossible to develop an ASIC. The goal needs to be that an ASIC should be a substantial fraction of a general-purpose CPU, such that the cost of developing a competitive implementation should be a substantial fraction of developing a competitive CPU.

I know it isn't trivial, but I also know that it isn't impossible.

The required technical framework is called "genetic programming". It provides for the development of nearly-randomly evolving of algorithms to optimize some figure of merit.

If somebody is really interested in application of genetic programming for the evolution of algorithm professor John Koza from Stanford has a really good textbooks on that subject.

If somebody has approx. 9GB of server space available I could upload the ISO DVD images of his 4 lectures on this subject from around the turn of the century. This was a "sales brochure" for his textbooks, I don't think it is copyrighted in any restrictive way. I have very limited Internet connectivity at the moment, I couldn't even seed a torrent reliably. Just please promise that you'll seed it properly afterwards.

[dogie]

It's not as simple as that, e.g. I could grind the circuit generator to find 'random' hash algorithms which a heuristic solver of mine can answer much faster than naive execution.  There have been some altcoin POW proposals that failed pretty seriously to this.

It's also the case that whatever parameterization you create, someone can just create an ASIC specialized for it... if nothing else stripping excess IO pincount and other costs.  Keep in mind, CPUs are ASIC too, ones with incredibly complex, secret, patented designs-- which can be mass produced by their makers at a marginal price which is a tiny fraction of what they sell for... "Be careful what you ask for".

CPUs are asics.

The goal shouldn't be "impossible to make an ASIC". The goal should be "an ASIC should be a substantial fraction of a general-purpose CPU", therefore the cost of developing a competitive ASIC should be a substantial fraction of developing a competitive CPU. It isn't trivial but it also isn't a completely uncharted territory of research.

I agree, the ideal is to set something like an i7 4790K as 1.00 performance and everything else is a proportion of it. Performance from that point won't increase more than 10% YoY and will remain at the same price. If anyone other than AMD / Intel / ARM + other can design a chip that outperforms an i7 4790K then they've got a bigger market than just Bitcoin to play with and several $B in the bank already.

But then as I pointed out above, even if you were successful, the result might just be giving a free license to Intel and AMD, which probably wasn't what you wanted.

Having 2 companies almost too large to care about Bitcoin as the ONLY competitor is a great thing and a significant improvement on now. At the moment its too easy to design an ASIC and there is too much performance improvement YoY. We went from 10W/GH to 1W/GH now to 0.2W/GH. And that best chip is controlled by ONE company who's sole purpose is to mine. If they choose not to sell they simply win the network and no one can do anything. Comparing that to the Intel / AMD self mining scenario, we all have access to the same weaponry with the same performance. That is a much healthier scenario than 5 companies manufacturing the ONLY weapons, most of which who refuse to sell to us peasants.

If somebody has approx. 9GB of server space available I could upload the ISO DVD images of his 4 lectures on this subject from around the turn of the century. This was a "sales brochure" for his textbooks, I don't think it is copyrighted in any restrictive way. I have very limited Internet connectivity at the moment, I couldn't even seed a torrent reliably. Just please promise that you'll seed it properly afterwards.

Why don't you email him to check? I'd reupload but I have less than 1mb of upload bandwidth.