Hash algorithm that cannot be implemented in ASIC ?

[Galati]

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.

[1713921346]

1713921346

[1713921346]

1713921346

[1713921346]

1713921346

[MCHouston]

This list of CPU altcoins should give you some options.

http://altcoins.com/cpu-altcoins

[Amph]

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

[theymos]

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.

[2112]

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.

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.

[okae]

This list of CPU altcoins should give you some options.

http://altcoins.com/cpu-altcoins

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.

[lemipawa]

This list of CPU altcoins should give you some options.

http://altcoins.com/cpu-altcoins

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.

[dogie]

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

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.

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.

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.

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.

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.

[tromp]

Is there any hashing algorithm that could not be implemented in ASIC ?

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.

[funkenstein]

Is there any hashing algorithm that could not be implemented in ASIC ?

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? 

[tromp]

Is there any hashing algorithm that could not be implemented in ASIC ?

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.

[funkenstein]

Is there any hashing algorithm that could not be implemented in ASIC ?

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? 

[bitbouillion]

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.

[tromp]

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?  

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.

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?  

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

[funkenstein]

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?  

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.

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?  

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!

[btchris]

Asic proof would mean that the PoW doesn't fit on a single chip.

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

Asic resistant would mean that the performance benefits of a custom asic solution would be
insufficient to compensate for their production costs.

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?

[dogie]

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.

[tromp]

Asic proof would mean that the PoW doesn't fit on a single chip.

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

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

[theymos]

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

Every x blocks, you change algorithm.ASICs.

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

[2112]

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