ASIC-resistant Proof of Work

[tromp]

And the number of iterations must be low enough so that validation of blocks becomes fast enough.

Seems you never heard of asymmetric PoWs, where only proof attempts require a lot of memory,
but verification requires negligible...

But is it really a problem if validation requires an equal amount of memory?

It's a big problem in SPV clients, e.g. on mobile devices,
and also makes the network more susceptible to ddos-attacks with false proofs.

Hmm... Ok. Darn. I think my random index jumping would work, but it does require that the verification algorithm has the same amount of memory. I need to go back to the drawing board I guess.

There are already PoWs that combine a large memory requirement with instant verifiability
(and where memory access dominates computation).

[Anders]

Hmm... Ok. Darn. I think my random index jumping would work, but it does require that the verification algorithm has the same amount of memory. I need to go back to the drawing board I guess.

There are already PoWs that combine a large memory requirement with instant verifiability
(and where memory access dominates computation).

I'm an amateur when it comes to this, but isn't memory access also an important factor? For example, if the memory requirement is large and the memory access rate low, then thousands of computation cores could share the same memory in an ASIC. If on the other hand the memory access rate requirement is high, then a shared memory would become a bottleneck with too many cores on the same chip.

[Anders]

Maybe numbers of an elliptic curve E could be used. And the PoW algorithm uses the value h XOR e_i where h is the plain hash value and e_i is one of the elliptic curve values in the list.

"The group law (addition) is defined as follows: Take 2 K-rational points P and Q. Now 'draw' a straight line through them and compute the third point of intersection R (also a K-rational point). Then P+Q+R=0 gives the identity point at infinity." -- http://mathworld.wolfram.com/EllipticCurveGroupLaw.html

The miner sends both h and e_i as proof. And the validation is done by first checking that the value of h XOR e_i is below the target and then checks that e_i is a point on the elliptic curve. The validation can in this way be done quickly without needing to calculate all the elliptic curve values and without needing the memory to store all the elliptic curve values.

The ASIC will then need either to only use one or a few values of E, or store many or all the E values in memory, or recalculate all or some of the elliptic curve points every time. A CPU and a large memory can easily store all the elliptic curve points and do a fast check of h XOR e for all the elliptic curve values.

[Spoetnik]

http://www.iflscience.com/technology/new-type-computer-capable-calculating-640tbs-data-one-billionth-second-could

New Type Of Computer Capable Of Calculating 640TBs Of Data In One Billionth Of A Second, Could Revolutionize Computing

[Spoetnik]

Maybe numbers of an elliptic curve E could be used. And the PoW algorithm uses the value h XOR e_i where h is the plain hash value and e_i is one of the elliptic curve values in the list.

"The group law (addition) is defined as follows: Take 2 K-rational points P and Q. Now 'draw' a straight line through them and compute the third point of intersection R (also a K-rational point). Then P+Q+R=0 gives the identity point at infinity." -- http://mathworld.wolfram.com/EllipticCurveGroupLaw.html

The miner sends both h and e_i as proof. And the validation is done by first checking that the value of h XOR e_i is below the target and then checks that e_i is a point on the elliptic curve. The validation can in this way be done quickly without needing to calculate all the elliptic curve values and without needing the memory to store all the elliptic curve values.

The ASIC will then need either to only use one or a few values of E, or store many or all the E values in memory, or recalculate all or some of the elliptic curve points every time. A CPU and a large memory can easily store all the elliptic curve points and do a fast check of h XOR e for all the elliptic curve values.

I seen the windows XP keygen source code and how the PID's were reversed
(that was using Elliptic Curve's as part of the protection)
the system was reversed 101%

[Anders]

Maybe numbers of an elliptic curve E could be used. And the PoW algorithm uses the value h XOR e_i where h is the plain hash value and e_i is one of the elliptic curve values in the list.

"The group law (addition) is defined as follows: Take 2 K-rational points P and Q. Now 'draw' a straight line through them and compute the third point of intersection R (also a K-rational point). Then P+Q+R=0 gives the identity point at infinity." -- http://mathworld.wolfram.com/EllipticCurveGroupLaw.html

The miner sends both h and e_i as proof. And the validation is done by first checking that the value of h XOR e_i is below the target and then checks that e_i is a point on the elliptic curve. The validation can in this way be done quickly without needing to calculate all the elliptic curve values and without needing the memory to store all the elliptic curve values.

The ASIC will then need either to only use one or a few values of E, or store many or all the E values in memory, or recalculate all or some of the elliptic curve points every time. A CPU and a large memory can easily store all the elliptic curve points and do a fast check of h XOR e for all the elliptic curve values.

I seen the windows XP keygen source code and how the PID's were reversed
(that was using Elliptic Curve's as part of the protection)
the system was reversed 101%

You mean that the elliptic curve value can be calculated in reverse to reach the target difficulty? Isn't such reverse very hard to calculate?

The proof sent by miners is the hash h and an elliptic curve value e_i. The value e_i is a point p=(x,y) on the elliptic curve. And the value h XOR x XOR y must be less than the target difficulty.

For example, take the hash value h=a0000003f103dfe. That value is larger than the target (it has a leading 'a' which should be zero). By adding an elliptic curve point the value h XOR x XOR y becomes let's say 000000038a1e2b9 which is below the target difficulty. So the miners have the opportunity to try zillions of elliptic curve points for each hash value.

In reality the hash value h could for example be 256 bits and x and y also 256 bits long. This means an elliptic curve over a gigantic field of size around 2²⁵⁶ values. No memory today could hold all those values of course but a CPU can access a very large memory containing pre-calculated values for x XOR y. An ASIC would have difficulty holding a large memory, especially if thousands of hash calculation cores in one chip need to share that memory.

[Anders]

The elliptic curve PoW addition is backward compatible with the current Bitcoin PoW algorithm. The miners can simply set e_i = p(x,y) = (0, 0) and then go on mining as usual with SHA-256d.

I looked up current hash rates for bitcoin. Today you need terahashes per second to only earn a few dollars per day! This means that that the elliptic curve addition wouldn't do much. Maybe a large number of GPUs could have an impact, but even that is doubtful I suspect. On the other hand future ASICs could perhaps use the elliptic curve addition to gain an advantage over the SHA-256-only ASICs.

This ASIC is probably an old version already:

"This product is the bare 28nm SHA256-crunching chip we’ve also used in our Jupiter Bitcoin Miner. We have a surplus of these that's never been used. These ASICs run at approx. 180-190 GH/s on our PCB:s power levels, but with it’s 192 cores it could be made to run faster if using a design that can feed it with more power." -- https://www.kncminer.com/products/knc-28nm-sha256-processor

[tromp]

Hmm... Ok. Darn. I think my random index jumping would work, but it does require that the verification algorithm has the same amount of memory. I need to go back to the drawing board I guess.

There are already PoWs that combine a large memory requirement with instant verifiability
(and where memory access dominates computation).

I'm an amateur when it comes to this, but isn't memory access also an important factor? For example, if the memory requirement is large and the memory access rate low, then thousands of computation cores could share the same memory in an ASIC. If on the other hand the memory access rate requirement is high, then a shared memory would become a bottleneck with too many cores on the same chip.

What part of "where memory access dominates computation" didn't you understand?

[Anders]

Hmm... Ok. Darn. I think my random index jumping would work, but it does require that the verification algorithm has the same amount of memory. I need to go back to the drawing board I guess.

There are already PoWs that combine a large memory requirement with instant verifiability
(and where memory access dominates computation).

I'm an amateur when it comes to this, but isn't memory access also an important factor? For example, if the memory requirement is large and the memory access rate low, then thousands of computation cores could share the same memory in an ASIC. If on the other hand the memory access rate requirement is high, then a shared memory would become a bottleneck with too many cores on the same chip.

What part of "where memory access dominates computation" didn't you understand?

Sorry, I overlooked that part. Yes memory access dominating computing is the same as what I meant. In that case ASICs will be used even for memory-intensive PoW algorithms, at least in the case of bitcoin.

So maybe the scrypt algorithms etc at best can buy some time. And having ASICs also prevents botnets running malware from mining. Still, it's interesting to examine new PoW algorithms, at least as a way of learning about it.

[digitalindustry]

"Re: ASIC-resistant Proof of Work"


this has essentially been solved in two ways, are you new to Crypto?

[Anders]

"Re: ASIC-resistant Proof of Work"


this has essentially been solved in two ways, are you new to Crypto?

I learned about Bitcoin in 2011. But I haven't looked into it much until recently.

Solved, do you mean scrypt? Or do you mean solved as in the battle against ASICs having turned out futile?

[Anders]

Hey! ASICs could check multiple elliptic points in parallel. So when a SHA-256d value is calculated it can immediately be fed through a number of elliptic point XOR additions at essentially zero time delay if the point values are pre-calculated and hard coded (read-only memory). So even if only say 100 points are checked in parallel it would speed up the mining power around two orders of magnitude.

This will lead to a new race for improved ASICs taking advantage of this additional feature. Would that be useful? Maybe as a slight disruption and test to see how the mining community reacts. Since the new algorithm is backward compatible with the existing Bitcoin PoW, the switch to the new algorithm will hopefully be smooth.

The miners can start with zero elliptic points which means using the existing ASICs without any change needed. And then over time new ASICs can be developed that boost the mining power by adding more and more elliptic points.

[digitalindustry]

"Re: ASIC-resistant Proof of Work"


this has essentially been solved in two ways, are you new to Crypto?

I learned about Bitcoin in 2011. But I haven't looked into it much until recently.

Solved, do you mean scrypt? Or do you mean solved as in the battle against ASICs having turned out futile?

1. Quark used the "market" to solve it, it distributed units over a 6 month period but only primarily by CPU (6 algorithms) - this meant no one could get a monopoly and ASICs become irrelevant except for a sponsored attack.

2. Myriad solved(is solving)  it by having multiple Algo's each with their own independent difficulty, lets say your Crypto has 6 algos, you have to try to corner the market on multiple algos simultaneously pretty impossible (all things being equal.)

* side note - see if you can see anything in this equation { demand + human monopoly on distribution = high fixed price } you will find its relevant to ASIC as human algorithms balance.

[MaxDZ8]

I remain convinced non-cryptographic pow will very likely be decentralized. Just too many instructions for effective use of die area.

[Anders]

"Re: ASIC-resistant Proof of Work"


this has essentially been solved in two ways, are you new to Crypto?

I learned about Bitcoin in 2011. But I haven't looked into it much until recently.

Solved, do you mean scrypt? Or do you mean solved as in the battle against ASICs having turned out futile?

1. Quark used the "market" to solve it, it distributed units over a 6 month period but only primarily by CPU (6 algorithms) - this meant no one could get a monopoly and ASICs become irrelevant except for a sponsored attack.

2. Myriad solved(is solving)  it by having multiple Algo's each with their own independent difficulty, lets say your Crypto has 6 algos, you have to try to corner the market on multiple algos simultaneously pretty impossible (all things being equal.)

* side note - see if you can see anything in this equation { demand + human monopoly on distribution = high fixed price } you will find its relevant to ASIC as human algorithms balance.

I think if bitcoin would use for example several algorithms there would still be ASICs developed for that. Some altcoins use scrypt-N in the sense that the memory requirement can be increased. But if the scrypt memory becomes huge, then what about validation performance?

[Anders]

I remain convinced non-cryptographic pow will very likely be decentralized. Just too many instructions for effective use of die area.

Sounds like an interesting idea. Seems tricky though to design a decentralized PoW. Or has this already been done?

[tromp]

Some altcoins use scrypt-N in the sense that the memory requirement can be increased. But if the scrypt memory becomes huge, then what about validation performance?

What part of "There are already PoWs that combine a large memory requirement with instant verifiability" didn't you understand?

[Anders]

Some altcoins use scrypt-N in the sense that the memory requirement can be increased. But if the scrypt memory becomes huge, then what about validation performance?

What part of "There are already PoWs that combine a large memory requirement with instant verifiability" didn't you understand?

I tried to find information about scrypt and verification. I found one paper describing the scrypt details, but it was too complicated for me to quickly understand. Do you mean scrypt values are fast to verify, regardless of amount of memory used? And can the verification be done without the need for the same amount of memory?

[tromp]

Some altcoins use scrypt-N in the sense that the memory requirement can be increased. But if the scrypt memory becomes huge, then what about validation performance?

What part of "There are already PoWs that combine a large memory requirement with instant verifiability" didn't you understand?

I tried to find information about scrypt and verification. I found one paper describing the scrypt details, but it was too complicated for me to quickly understand. Do you mean scrypt values are fast to verify, regardless of amount of memory used? And can the verification be done without the need for the same amount of memory?

Scrypt is just one of many hash functions that can be used in the hashcash proof of work system.
These are all symmetric, in that a proof attempt and verification both consist of computing the hash function,
and thus no hope of faster verification.

You need an asymmetric, non-hashcash PoW to avoid this limitation.

[Anders]

Some altcoins use scrypt-N in the sense that the memory requirement can be increased. But if the scrypt memory becomes huge, then what about validation performance?

What part of "There are already PoWs that combine a large memory requirement with instant verifiability" didn't you understand?

I tried to find information about scrypt and verification. I found one paper describing the scrypt details, but it was too complicated for me to quickly understand. Do you mean scrypt values are fast to verify, regardless of amount of memory used? And can the verification be done without the need for the same amount of memory?

Scrypt is just one of many hash functions that can be used in the hashcash proof of work system.
These are all symmetric, in that a proof attempt and verification both consist of computing the hash function,
and thus no hope of faster verification.

You need an asymmetric, non-hashcash PoW to avoid this limitation.

Yes, I now found:

"It is a misunderstanding to talk about the Scrypt proof-of-work. Scrypt is not intended as a proof-of-work function, but a stretched key-derivation function, and while it is by design expensive to compute with high iterations, it can not be used to make an efficiently publicly auditable proof-of-work, as verifying costs the same as creating." -- https://en.bitcoin.it/wiki/Hashcash

Interesting. I will examine the possibilities of using elliptic curves some more. Maybe that can make it possible to design asymmetric PoW with large memory requirement.