Bitcoin Forum

As far as i know, SHA256 can be implemented in an ASIC because it only performs bitwise operations and multiplications using 32 bit integers.
Is there any hashing algorithm that could not be implemented in ASIC ?

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

This list of CPU altcoins should give you some options.

http://altcoins.com/cpu-altcoins (http://altcoins.com/cpu-altcoins)

something that require tons of memory maybe, like scrypt-n with a n factor that should be as a big as a possible, so they need to spend tons of money for their memory/that are not cheap, and in the end it will not be worth it, unless the coin skyrocket

usually if a gpu can mine it, an asic can mine it too at some point, the reason why there aren't asic for x11 algo and many other random algo that there are in the altsection, It is only bound to a point of view of profit...

Anything can be implemented in an ASIC, though maybe you could design a hash algorithm that gives modern computers enough of an advantage to discourage ASIC creation. (But I don't know that much about hardware.)

I see two problems with memory-hard PoW:
- If it takes a few seconds to complete one hash, then the network can be DoS-attacked by broadcasting many invalid blocks which nodes then need to waste tons of time checking. It'd be nice to have an asymmetric PoW algorithm that requires much more time to create a PoW than to verify one.
- AFAIK it's not actually that expensive to create ASICs with a lot of memory, and it looks like scrypt ASICs have in fact been created.

I wonder if ASIC design/creation would be made prohibitively expensive if the hash algorithm was especially complex. For example, if the simplest way of representing the algorithm in assembly code was 1 GB in size, I suppose this would be quite difficult to translate to an ASIC, but not any particular obstacle for general-purpose CPUs. You could still create an ASIC that worked like a CPU but with only the subset of CPU features actually used by the hash algorithm, but this'd be pretty expensive to design and might not earn you much extra efficiency.

I also wonder whether it might be good to use a PoW that is especially easy to build an ASIC for, but so simple that the most dead-simple ASIC design is always the best one. Then you'd have to buy hardware to mine, but no ASIC would have much advantage over any other. I don't know if this'd actually help anything since there'd still be economies of scale in power consumption, though.

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.

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.

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.

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.

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.

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

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.

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? 

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.

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

thank you!

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?

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.

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

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

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.

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

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.

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.

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.