We have recently developed a memory-hard proof-of-work, which is based on the well known Generalized Birthday problem: given a list of binary vectors X₁, X₂,..X_N and number k find i1,i2,..ik such that
X_i1 + X_i2 +.. + X_ik =0.

The non-trivial algorithm for it was developed by Wagner in 2001 and has been studied extensively since then.

Our proof-of-work is tunable for time, memory, and time-memory tradeoff independently, and verification is instant. Uniquely, by varying k  any tradeoff resilience level can be chosen (e.g., one may require that the time grows as 4-th power of the memory reduction).

 For example, the proof for 700-MB memory is 148 bytes long. The implementation exists but is not optimized.

In our paper we explore in details all the related time-space tradeoffs, compare the scheme to existing alternatives such as Momentum and Cuckoo, discuss its implementations on ASICs and GPUs, and estimate its performance and bandwidth requirements.

The full paper is available at http://eprint.iacr.org/2015/946

Comments are welcome.

Alex Biryukov
Dmitry Khovratovich