Topic: ASIC-resistant Proof of Work (Read 5119 times)
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.
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.
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 pi on the elliptic curve. The proof is valid if pi = λiGj and h XOR hash(λi) is less than the target difficulty, where λi > 1. Gj 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 pi = λiGj for all points pi.
The point pi is calculated by setting x to hash(i) MOD M, where M is the order of the finite field FM for the elliptic curve y2 = x3 + 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 pi and λiGj 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.
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 pi on the elliptic curve. The proof is valid if pi = λiGj and h XOR hash(λi) is less than the target difficulty, where λi > 1. Gj 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 pi = λiGj for all points pi.
The point pi is calculated by setting x to hash(i) MOD M, where M is the order of the finite field FM for the elliptic curve y2 = x3 + 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 pi and λiGj 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.
Ouch. The equation pi = λiG has no general solution in the sense that there is always at least one nontrivial value λi for all points pi. I have to go back to the drawing board.
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: y2 = x3 + 7.
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: y2 = x3 + 7.
This is similar to, but more complicated than Momentum, which asks for a simple hash collision.
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.
This is similar to, but more complicated than Momentum, which asks for a simple hash collision.
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.
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 pi on the elliptic curve. The proof is valid if pi = λ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 pi have switched since the previous version.)
The point pi is calculated by setting x to hash(i) MOD M, where M is the order of the finite field FM for the elliptic curve y2 = x3 + 6. If no solution y is found for x, then x = x + 1 until a solution is found.
Since the calculations of pi 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.
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 pi on the elliptic curve. The proof is valid if pi = λ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 pi have switched since the previous version.)
The point pi is calculated by setting x to hash(i) MOD M, where M is the order of the finite field FM for the elliptic curve y2 = x3 + 6. If no solution y is found for x, then x = x + 1 until a solution is found.
Since the calculations of pi 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 FM.
I will take a look at Momentum.
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 pi on the elliptic curve. The proof is valid if pi = λ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 pi have switched since the previous version.)
The point pi is calculated by setting x to hash(i) MOD M, where M is the order of the finite field FM for the elliptic curve y2 = x3 + 6. If no solution y is found for x, then x = x + 1 until a solution is found.
Since the calculations of pi 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.
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 pi on the elliptic curve. The proof is valid if pi = λ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 pi have switched since the previous version.)
The point pi is calculated by setting x to hash(i) MOD M, where M is the order of the finite field FM for the elliptic curve y2 = x3 + 6. If no solution y is found for x, then x = x + 1 until a solution is found.
Since the calculations of pi 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.
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 pi on the elliptic curve. The proof is valid if pi = λ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 pi have switched since the previous version.)
The point pi is calculated by setting x to hash(i) MOD M, where M is the order of the finite field FM for the elliptic curve y2 = x3 + 6. If no solution y is found for x, then x = x + 1 until a solution is found.
Since the calculations of pi 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.
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 pi on the elliptic curve. The proof is valid if pi = λ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 pi have switched since the previous version.)
The point pi is calculated by setting x to hash(i) MOD M, where M is the order of the finite field FM for the elliptic curve y2 = x3 + 6. If no solution y is found for x, then x = x + 1 until a solution is found.
Since the calculations of pi 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.
"Re: ASIC-resistant Proof of Work"
this has essentially been solved in two ways, are you new to Crypto?
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?
"can't see the forest for the trees"
http://dictionary.reference.com/browse/can%27t+see+the+forest+for+the+trees
No, in EC crypto the λ is the private key. The difficult part is finding λ given P and G.
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 y2 = x3 + 6 can be used with P as a constant point on the elliptic curve.
The value λi is calculated from P and Gi with x = hash(i) MOD M in the same way as described earlier. And i = h MOD N as before.
Quote
So your previous description of what the verifier does is wrong.
No, the verifier calculates Gi based on i as a result of h MOD N. And for that A is needed. The value Pi comes from the miner and λPi from the miner is compared with the value of Gi that the verifier itself has calculated.
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?
No, in EC crypto the λ is the private key. The difficult part is finding λ given P and G.
Quote
Yes, A is a predefined constant. It's needed so that the verifier can calculate Gi and then compare it with λPi.
So your previous description of what the verifier does is wrong.
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.
G is calculated from i and A. Or more correct Gi. There is an exact defined point G for every i.There can be many Ps for which λP is a point on the elliptic curve, so many possible Gs.
Quote
No; that's about as easy, since P = (λ-1 λ) P = λ-1 (λ P) =λ-1 G.
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?
Quote
Why do you say the[\b] correct value for P, when there can be many?
The correct value for Pi. Think of P as the list and Pi as the values in the list. I should have been clearer about that.
Quote
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.
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.
Yes, A is a predefined constant. It's needed so that the verifier can calculate Gi and then compare it with λPi.
Yes, λP is a point on the elliptic curve. And the point must fulfill G = λP.
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.
Quote
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.
No; that's about as easy, since P = (λ-1 λ) P = λ-1 (λ P) =λ-1 G.Quote
The miner on the other hand must produce the correct value for P, which is a very difficult calculation.
Why do you say the correct value for P, when there can be many?Quote
When the miner uses lots of memory then the points Pi are pre-calculated and put into a list for direct lookup. Each value Pi is calculated by setting x to a predefined constant A in the elliptic curve equation y2 = x3 + 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 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.
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 y2 = x3 + i. The second part of the verification is to check that h XOR hash(P) is less than the target difficulty.
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 FM 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 y2 = x3 + 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 Pi are pre-calculated and put into a list for direct lookup. Each value Pi is calculated by setting x to a predefined constant A in the elliptic curve equation y2 = x3 + 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) = Gi. So to get Pi the condition Gi = λPi 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 Pi interchangeably here. The value i is simply the index position for all the P values.
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 y2 = x3 + i. The second part of the verification is to check that h XOR hash(P) is less than the target difficulty.
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 FM 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 y2 = x3 + i, where i = h MOD N ?
Then where do the points P_i come in, and how is P_i defined?
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 y2 = x3 + i. The second part of the verification is to check that h XOR hash(P) is less than the target difficulty.
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 FM there will be an enormous number of random trials needed.
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 y2 = x3 + i. The second part of the verification is to check that h XOR hash(P) is less than the target difficulty.
This looks pretty symmetric to me. The miner just keeps trying random Ps until verification succeeds,
just as in hashcash.
Large memory PoW algorithm with fast verification:
A large list of N elliptic curve points Pi is constructed by using the equation y2 = x3 + i over a field FM. This means that each point is on a different elliptic curve over the same finite field. N < M to keep the list size within FM.
The miner starts with an ordinary block hash h and calculates i = h MOD N, and then uses y2 = x3 + 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 FM.
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 Pi, 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 y2 = x3 + 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 FM.
A large list of N elliptic curve points Pi is constructed by using the equation y2 = x3 + i over a field FM. This means that each point is on a different elliptic curve over the same finite field. N < M to keep the list size within FM.
The miner starts with an ordinary block hash h and calculates i = h MOD N, and then uses y2 = x3 + 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 FM.
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 Pi, 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 y2 = x3 + 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 FM.
Jump to: