Topic: Hash algorithm that cannot be implemented in ASIC ? (Read 2949 times)

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.


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.


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

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.

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.

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 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.

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

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?)

PoWs can also get bigger over time, e.g. double the memory usage whenever difficulty rises too much.

What about another solution which I haven't yet seen mentioned:

Every x blocks, you change algorithm.

You don't need a pool of 1000 algorithms and could get by with a rotation of 3 or 4. Even if someone built an ASIC for 1 algorithm, they'd only be able to use it on your coin for 25-33% of the time which is unlikely to be viable for the ASIC manufacturer. I'm sure I'm missing some terminal complication on the client side which would prevent algorithm hopping, but I think it works on the hardware side of things in terms of preventing ASICs.

OK, but that's a moving target. Over time, ASICs get bigger.


In our context, I assume you mean that the revenue benefits from mining would be insufficient to compensate for their production costs, but this is also a moving target (for healthy coins on the rise, that is).

Eventually either the two meet and create a profitable market for ASIC production, or the coin dies off.

As a coin designer selecting a PoW, the only questions you have control over is how long before this happens, and how expensive are ASICs (relative to other PoW choices) when they arrive.

If only the super-rich can afford ASICs, then you'd end up with increased centralization (relative to having used a simpler PoW) when ASICs first appear, no?

thank you!

Asic proof would mean that the PoW doesn't fit on a single chip.
Asic resistant would mean that the performance benefits of a custom asic solution would be
insufficient to compensate for their production costs.


The first example was Primecoin's PoW. Several others are listed in

http://en.wikipedia.org/wiki/Proof-of-work_system#List_of_proof-of-work_functions

and http://cpucoinlist.com/cryptocurrency-algorithms/  (4 non-hashcash entries).

Any algorithm ends up running on silicon (for scrypt you need a GPU and memory cells). The question is only which design of the silicon is the optimum solution in terms of cost and performance (bang for the buck). The optimum solution will change due to Moore's Law constantly.

Thanks.  Interesting, but i'm not convinced it is a necessity, nor that it would really be "asic proof"..     in fact I'm not convinced the idea of "asic proof" has much meaning.  "Optimized for x86 chips" perhaps has some meaning.. but still not much really?  

But wait..  isn't a proof attempt fundamentally the same thing as a verification?  Do you have an example of such an asymmetric scheme?   Maybe the birthday proof of work idea? 

One that's NOT of the form

deterministic_hash_function(block_header||some_nonce) < target_difficulty

Hashcash is symmetric in that a proof attempt necessarily takes the same effort as a proof verification. Other, asymmetric, PoW schemes allow proof attempts to take much more effort,
so they could be made ASIC resistant without making verification impractically slow.

What's a non-hashcash proof-of-work? 

Sure, take any hashing algorithm that requires more gates than fit on the largest imaginable chip;
e.g. scrypt using 16GB.

The downside is that verification of the Hashcash proof-of-work becomes way too slow to be of
any practical use. Non-Hashcash proofs-of-work don't face this limitation though.

Correct, gridseed has made 2 generations of scrypt chips, KNC made 1 and Bitmain designed but never used 1. The memory isn't expensive, it just takes up die space you'd have preferred to put another 1x10^x pipelines in.


Unfortunately there are a few things which prevent this:
1) CPUs have insane markups from $ to make to $ to sell, even amortising the huge upfront costs. Any company who simply manufactured their own chips would still have an insurmountable advantage.
2) Almost any of the non-super-exotic algorithms would be significantly faster on a GPU than a CPU because of their basic makeup. A GPU core runs 1000-3000 threads where as a CPU is of course 4-8 (with some smaller multipliers depending on exactly what it is). It would be amazing if someone could find something that is so inefficient on a GPU that you'd buy a CPU over one to mine it with.
3) ASIC design isn't expensive, making the chips is (in up front costs). That means you're free to theoretically prospect with designs and do small runs on older cheap processes to see if it actually works. If it does, you win. The cost barrier only comes when you then decide to make the chips on a modern process.


Same problem with 1) above. Even if you did a terrible clone of the core features required to mine, you'd have a huge price advantage when you self manufacture compared to retail. And then huge advantage in related components (you make your own mobo + OS + barebones), density, cooling, availability and centralised elec.

These are only CPU mineable because they don't have enough market to warrant the creation of asics to be developed. It is not cost effective to develop an ASIC and mine a coin that very little people use or is of very little value.

this list is so interesting, but that list is up to date?

btw about the main question, i cant remember the exact day but i remember a guy called "wolf0" or something like that who made some good sw minners, who sayd that anything can me implemented with more or less efficience, but in the end im pretty sure that can be done.

Anything can be implemented in ASIC. The proper solution is to come up with an algorithm that an ASIC will have to implement a large fraction of a general-purpose CPU. This way the cost of developing a competitive ASIC will have to rise to match the cost of developing a competitive CPU.

If you are thinking of developing an altcoin I think the good suggestion is to include some of the extended-floating-point (10-byte) operations in some steps of the "hash" function. But the "hash" shouldn't be considered a "cryptographic hash" but a "chaotic map" that is sensitive to the details of the arithmetic implementation. Examples:

http://en.wikipedia.org/wiki/Tinkerbell_map
http://en.wikipedia.org/wiki/Logistic_map

I've seen many ASIC/FPGA hardware libraries, but all of them implement only IEEE 754 floating point in 4- and 8- byte precision. There isn't anyone who does 10-byte precision. On the other hand the detailed, bit-accurate implementations of it are freely available since the famous Pentium FDIV bug.

So it is both an open-source code and something very expensive to build an implementation faster than the generic AMD/Intel CPU.