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.