Bitcoin Forum

Today ASICs can easily calculate SHA-256 for bitcoin mining. As an alternative proof of work (PoW) the miners can be given the problem of solving integer factorization. This type of PoW can perhaps make CPUs more competitive versus ASICs.

"In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly.[1] The prime factorization of a positive integer is a list of the integer's prime factors, together with their multiplicities; the process of determining these factors is called integer factorization. The fundamental theorem of arithmetic says that every positive integer has a single unique prime factorization.[2]" -- http://en.wikipedia.org/wiki/Prime_factor

Each Bitcoin block is hashed to a very large integer N. And the task is to calculate a large enough number of integer factors for N to reach a target d. The difficulty is made variable by requiring different numbers of factors d in the solution. Notice here that the factors can be other integers than primes. This is a different method than ordinary prime factorization. The miners provide a solution S which is a list that contains at least d factors (len(S) >= d). The solution is verified by multiplying all the factors in S and checking if the product equals N (∏s_i = N).

If the prime factorization of N results in less factors than d, then that's a valid solution. When S contains less factors than d then the validation must also do a primality test on the factors to check if they are all primes. "Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input)." -- http://en.wikipedia.org/wiki/Primality_test

Example:

N = 48
d = 3
S = [2, 2, 12]

Another example:

N = 123
d = 3
S = [3, 41]

In the second example, S is the prime factorization of N.

The value N is calculated as a hash value of the Bitcoin block in a way that makes factorization hard.

https://en.wikipedia.org/wiki/Application-specific_integrated_circuit
ASIC is an integrated circuit (IC) customized for a particular use, rather than intended for general-purpose use
There are no such things as "ASIC-resistant algorithms"

Either the community uses your fork and some day somebody creates ASIC for it instead of general-purpose computer
Or your cryptocurrency is dead.

Yes, everything a CPU can do eventually will be possible to do with ASICs, but my idea is that for a problem like factorization of integers an ASIC wouldn't be that much faster than a CPU. And parallel computing can be limited by restricting how a Bitcoin block can be put together.

Why do you think so? The fact is that there are no such ASICs today.
But it will be not a big problem to create such device if it would be economically reasonable.

I was thinking that integer factorization would be difficult to compute in parallel and that the clock speed of ASICs is lower than for CPUs.

https://download.wpsoftware.net/bitcoin/asic-faq.pdf

Questions 2.5 and 2.6 cover the obvious problems with this proposal, but almost the entire document is applicable.

I get this part:

"The proof-of-work must be optimization free; that is, there should not be any algorithmic speedups which would give an advantage over the standard algorithm. If a speedup exists and is found, there is strong motivation for the discoverer to use it secretly rather than publishing it, gaining an unfair advantage. This contributes to centralization."

That's a good point. There is a possibility that the integer factorization I propose, or even ordinary prime factorization, could lead to algorithms being developed in secret. Not good. Maybe if I changed it to only use ordinary prime factorization it would ok, since even though probably not optimization free, the problem of prime factorization is well-known and there's tons of public researched about it available.

This other part I'm more unsure of:

"It is also important that miners with a lot of computational power should not achieve a disproportionate benefit."

Perhaps with integer factorization some miner could become dominant which would open up a risk of 51% attacks.

I have learned that proof of work (PoW) easy to do with ASICs may actually be a good choice. Anyway, I came to think of a PoW algorithm that requires lots of memory which makes it difficult to implement in ASICs:

Random Hash Algorithm (RHA)

The algorithm starts with generating a huge list of N hash values where each new value h_i is the hash of the previous value in the list. Then the following calculation is iterated M times: y_i = h_j, where j = y_i-1 MOD N and y₀ = h_N-1. If a hash value already has been used, then j = (y_i-1 + n) MOD N, n = 1,2,3... until an unused hash value is found. And h₀ is the ordinary hash value (digest) for the message (in the case of Bitcoin the message is the part of the block to do PoW for).

The resulting hash value RHA = y_M. And M < N (to allow enough iterations).

What this means is that the last hash value in the list is used to generate a random index in the list from which the next hash value is taken, and this is iterated M times. Since it's impossible to know beforehand how the random index jumps will be, there are M random positions that have to be examined one by one.

Without a large memory, the list of hash values must be recalculated M times at least partially for each index jump. With a large memory the calculation is simply iterations of hash value lookups in the list. Using a cryptographic hash function, such as SHA-256, makes the direct memory lookup approach optimal. So the algorithm is non-optimizable in the theoretical sense, and the optimal implementation requires large amounts of random access memory.

Remember that the block hash must be quickly verifiable. This means that calculating single hash should be as fast as possible on CPU. Otherwise only miners would be able to verify blocks.

With the RHA algorithm the miners would still need to do zillions of hash calculations while verification is only one RHA calculation. Sure, RHA is hugely more computationally demanding than say plain SHA-256, but verification can be done within a second with a CPU I guess.

Or do you mean ordinary Bitcoin nodes need to do many block verifications per second? That could be problematic with RHA.

Ouch, SHA-256 is pretty slow on a CPU. Crypto++ 5.6.0 Benchmarks -- http://www.cryptopp.com/benchmarks.html

Way too slow to be used in the RHA I proposed. Instead a linear congruential generator (LCG) can be used. That's a super fast calculation:

http://upload.wikimedia.org/math/5/6/c/56cdb2a3e7b9c73522afb089fc17a049.png

This might be a problem: "They also must not be used for cryptographic applications" -- http://en.wikipedia.org/wiki/Linear_congruential_generator#Advantages_and_disadvantages_of_LCGs

On the other hand, it's not about secure cryptography here. A 256-bit LCG can be used for generating the list of values, except the first value in the list which is an ordinary hash value (such as from SHA-256). With an LCG implementation the verification can be done within a second for very large lists. The problem may be that a shortcut is possible in the calculations when using an LCG.

Another solution for RHA is to use a fixed pre-calculated list of values. And the first index position is h MOD N, where h is the original hash value from the message (Bitcoin block). The rest of the algorithm is the same as before except the RHA value is set to y_M XOR h.

Now verification becomes fast and lots of memory is still needed for the algorithm. 8)

Use the search button..  a lot of people have tried to do this in various ways.. All of them have failed.

Every time it goes CPU -> GPU -> FPGA -> ASIC

Yes, that's the trend. Ethereum has a (new) PoW algorithm that could be tricky to do ASICs for but I read that there are other problems with the algorithm. ASICs can already today do scrypt: https://zeusminer.com/product/zeusminer-volcano-300mhs1000wscrypt-asic-miner/

It's fun to think of new solutions anyway. My proposal needs to be modified to a fixed list of random values in order for verification to be fast, plus the index jumps need to include the initial hash in every jump, or else a double-lookup table could shortcut the iterations.

They failed because they were computation dominated.

For a PoW that spends a minority of runtime on computation,
and a majority on random memory access latency, commodity DRAM could be the ASIC.

ASICs can calculate hash functions very fast but not practically have much memory. CPUs can have access to a lot of memory but have slow calculation of hash values.

The PoW algorithm here needs to demand separate memory for each hash function core in the ASICs. Otherwise lots of cores could share a single memory.

By requiring lots of memory accesses, a single shared memory in an ASIC will become a bottleneck.

This can be achieved by having a pre-calculated list of random numbers, large enough so that ASICs will have trouble allocating enough memory to each hash function core. And a random jump indexing in the list is done by taking the initial hash value and repeat hashing it a number of times. The number of iterations should be large enough so that memory access becomes a bottleneck for ASICs with many hash function cores. And the number of iterations must be low enough so that validation of blocks becomes fast enough.

EDIT: No, not hashing several times. The first index position is h MOD N, and the index jumping is done with XOR of (h / N) MOD N. Which means taking the lowest part of the hash value as the first index position and then using another part of the hash value for the random index jumping. Then a huge number of random jumps can be done with very little computation yet with loads of memory access. The list of random numbers can remain fixed. And the two parts of the hash value prevent shortcuts. (Unless I have overlooked something. I'm too lazy at the moment to think this through carefully. :D)

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

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.

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.

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

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.

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

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.

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

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

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.

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 remain convinced non-cryptographic pow will very likely be decentralized. Just too many instructions for effective use of die area.

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?

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

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.

hey guys, what can you say about scrypt-in-motion? aptcoin

https://bitcointalk.org/index.php?topic=743731.0

Scrypt evidently works for big altcoins like Litecoin and Dogecoin. And increasing the memory size according to Moore's law should work too since even though validation requires as much memory and computation as the generation of the scrypt value, small devices like smartphones will also progress in memory size and computing power according to Moore's law.

It would be better however if the validation could be done fast with little computing power and small memory even when the PoW algorithm uses a huge memory like several gigabytes. But such asymmetric algorithm is tricky to design it seems so dynamic scrypt modification is perhaps the best way of doing it at the moment.

Large memory PoW algorithm with fast verification:

A large list of N elliptic curve points P_i is constructed by using the equation y² = x³ + i over a field F_M. This means that each point is on a different elliptic curve over the same finite field. N < M to keep the list size within F_M.

The miner starts with an ordinary block hash h and calculates i = h MOD N, and then uses y² = x³ + i to get a point G. Then a point P is calculated with G = λP. And the resulting value that needs to be less than the target difficulty is h XOR hash(P). The value λ is a constant in F_M.

The idea is that it's very difficult for the miner to calculate point P. Therefore the miner needs to keep a pre-calculated list of all the points P_i, i=0, ... N-1.

As proof, the miner sends h and P. Verification is first done by taking i = h MOD N and checking if G = λP when using the elliptic curve y² = x³ + i. The second part of the verification is to check that h XOR hash(P) is less than the target difficulty.

G is calculated by setting x = A and if no solution is found x = A + 1, 2, 3... until a solution is found. The value A is a constant in F_M.

This looks pretty symmetric to me. The miner just keeps trying random Ps until verification succeeds,
just as in hashcash.

Only P for i = h MOD N is valid. If another value is used then G != λP. With sufficiently large field F_M there will be an enormous number of random trials needed.

I don't understand your definitions. What exactly is the verifier checking when given h and P?

Is he checking that λP is any point on the curve y² = x³ + i, where i = h MOD N ?

Then where do the points P_i come in, and how is P_i defined?

Yes, λP is a point on the elliptic curve. And the point must fulfill G = λP. (The point G is the point P added to itself λ times, so-called scalar multiplication.) If the miner tries to send another P it will be rejected.

And h is the plain block hash, for example like in Bitcoin with SHA-256d. If h is less than the target, then that's insufficient. It's h XOR hash(P) that must be less than the target. So the exclusive-or combination of the original hash h and the hash for P together must reach below the target difficulty.

The verifier can skip the difficult calculation of P. It's enough for the verifier to calculate G from the P it got from the miner multiplied by λ. That's a much easier calculation than calculating P from λ and G. The miner on the other hand must produce the correct value for P, which is a very difficult calculation.

When the miner uses lots of memory then the points P_i are pre-calculated and put into a list for direct lookup. Each value P_i is calculated by setting x to a predefined constant A in the elliptic curve equation y² = x³ + i. For the particular i, there may be no solution for y with x = A, and then x = A + 1,2,3... and so on is calculated until a solution is found. The solution is (x, y) = G_i. So to get P_i the condition G_i = λP_i is used. There is no direct simple formula that can be used for P so a brute force trial-and-error approach or something similar is needed.

I have used P and P_i interchangeably here. The value i is simply the index position for all the P values.

The last part makes no sense since G is defined as λP, so there's nothing to fulfill.
There can be many Ps for which λP is a point on the elliptic curve, so many possible Gs.

No; that's about as easy, since P = (λ^-1 λ) P = λ^-1 (λ P) =λ^-1 G.

Why do you say the correct value for P, when there can be many?


The miner doesn't have to search from any particular A, so I don't know why you bother defining A.
There's also no need to store points on the curve. For each point G you find on the curve, you just
compute the corresponding P as above and check the difficulty target.

G is calculated from i and A. Or more correct G_i. There is an exact defined point G for every i.


This could be a mistake of mine. I'm just learning about elliptic curves and as I understood it, to add a point to itself a number of times is easy, while going backwards to find the original value is very difficult. Isn't that the method used when calculating a public key from a private key in elliptic curve cryptography?


The correct value for P_i. Think of P as the list and P_i as the values in the list. I should have been clearer about that.


Yes, A is a predefined constant. It's needed so that the verifier can calculate G_i and then compare it with λP_i.

No, in EC crypto the λ is the private key. The difficult part is finding λ given P and G.


So your previous description of what the verifier does is wrong.

Ah! Then instead of a single constant λ, the list could contain λ_i. And the miner sends h and λ_i as proof. And instead, a single elliptic curve, such as y² = x³ + 6 can be used with P as a constant point on the elliptic curve.

The value λ_i is calculated from P and G_i with x = hash(i) MOD M in the same way as described earlier. And i = h MOD N as before.


No, the verifier calculates G_i based on i as a result of h MOD N. And for that A is needed. The value P_i comes from the miner and λP_i from the miner is compared with the value of G_i that the verifier itself has calculated.

"can't see the forest for the trees"

http://dictionary.reference.com/browse/can%27t+see+the+forest+for+the+trees

Large memory PoW with fast verification, updated version:

The miner sends h and λ_i as proof.

h is the block hash value.
λ_i is a key for an elliptic curve point.
i is the value h MOD N.
N is the number of keys used.

The verifier calculates a point p_i on the elliptic curve. The proof is valid if p_i = λ_iG and h XOR hash(λ_i) is less than the target difficulty. G is a predefined constant point on the elliptic curve. (Notice here that G and p_i have switched since the previous version.)

The point p_i is calculated by setting x to hash(i) MOD M, where M is the order of the finite field F_M for the elliptic curve y² = x³ + 6. If no solution y is found for x, then x = x + 1 until a solution is found.

Since the calculations of p_i and λ_iG are easy the verification is fast without the need for much memory. The miner on the other hand needs the value λ_i which is difficult to calculate and therefore the miner has to store all keys λ_i, i = 0, ... N-1 in memory as pre-calculated values.

So this asks for a point that can be calculated in two ways:

as the curve point with minimal x>=i, and
as λ_i G

This is similar to, but more complicated than Momentum, which asks for a simple hash collision.

Almost. A curve point with x = hash(i) MOD M + n, and minimal n = 0,1,2,3... The value of x can wrap around M-1.

The reason for this x value instead of simply minimal x>=i is that it makes x become spread out pseudorandomly across the finite field F_M.

I will take a look at Momentum.

I read that Momentum was only used in the initial phase of BitShares. Now they use a form of proof of stake. Are there any other altcoins that have used or are using Momentum? I also read some of the Momentum whitepaper, but not enough to understand how the algorithm works.

It was and still is used in Protoshares (nowadays also called Bitshares PTS).
Not used anywhere else.

I read that there are actually some elliptic curves that are cryptographically weak. For the PoW algorithm it's possible to deliberately choose a weak elliptic curve, since the keys only need to be difficult enough to calculate. That would prevent the finding of future algorithms that improve the calculation speed.

EDIT: On a second thought, a weak elliptic curve can in the future be found to be even weaker. So it's best to stick with a tested elliptic curve, such as the one used in Bitcoin for digital signatures: y² = x³ + 7.

Ouch. The equation p_i = λ_iG has no general solution in the sense that there is always at least one nontrivial value λ_i for all points p_i. I have to go back to the drawing board.

Large memory PoW with fast verification, third version:

The miner sends h and λ_i as proof.

h is the block hash value.
λ_i is a key for an elliptic curve point.
i is the value h MOD N.
N is the number of keys used.

The verifier calculates a point p_i on the elliptic curve. The proof is valid if p_i = λ_iG_j and h XOR hash(λ_i) is less than the target difficulty, where λ_i > 1. G_j is a member of a set G with predefined constant points on the elliptic curve. The points in G are chosen so that there is at least one nontrivial solution to p_i = λ_iG_j for all points p_i.

The point p_i is calculated by setting x to hash(i) MOD M, where M is the order of the finite field F_M for the elliptic curve y² = x³ + 7. N < C < M, where C is a value for 1% hash collisions. If no solution y is found for x, then x = x + 1 until a solution is found.

Since the calculations of p_i and λ_iG_j are easy the verification is fast without the need for much memory. The miner on the other hand needs the value λ_i which is difficult to calculate and therefore the miner has to store all keys λ_i, i = 0, ... N-1 in memory as pre-calculated values.

Anyone interested in implementing an elliptic curve PoW? As a test of concept. Of course, first the algorithm has to be examined to see if it would work. I don't know enough about this kind of programming myself. It could be fun for someone savvy in these kinds of algorithms. Lots of parameters to specify, modify, tweak and measure. And it's copyright and license free.

One problem with a PoW that requires lots of memory is that sooner or later, special custom integrated circuits would be developed, even with gigabytes of memory. And if those chips are more demanding to design and manufacture it would lead to even more centralization than the SHA-256d ASICs.