ASIC-resistant Proof of Work

[arielbit]

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

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

[Anders]

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.

[Anders]

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.

[tromp]

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.

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

[Anders]

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.

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.

[tromp]

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.

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?

[Anders]

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.

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.

[tromp]

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.

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.

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?

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

[Anders]

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 G_i. There is an exact defined point G for every i.

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?

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

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.

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.

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

[tromp]

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.

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

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

[Anders]

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

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

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.

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

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

[Anders]

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.

[tromp]

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.

[Anders]

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.

[Anders]

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.

[tromp]

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.

[Anders]

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.

[Anders]

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.

[Anders]

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.