Quote from: tromp on October 01, 2014, 08:55:05 PM

Quote from: Anders on October 01, 2014, 07:15:06 PM

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.