Memory-hard proof-of-work with fast verification and tunable tradeoff resilience

[khovratovich]

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

[spartacusrex]

Congratulations! A lot of work went into that.

I skimmed it..

But there seems to be something missing ?

..

the NAME ? 

You mention Cuckoo and Momentum.. but we need a name for your baby ?

'Memory-hard proof-of-work with fast verification and tunable tradeoff resilience' is too much of a mouthful.

[r0ach]

You mention Cuckoo and Momentum.. but we need a name for your baby ?

Since Vertcoin was accused of burning up people's GPUs for fun, let's go with "roaster", "hades", or "torment".

[smolen]

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.

Binary matrix kernel, Krylov subspaces and block Lanczos algorithm.
Did I just deprived myself one more time of possible mining profit?

EDIT: Responded too fast, overlooked that K is fixed. Well, may be first find kernel (note that block Lanczos method allows to calculate the matrix on the fly instead of storing it), then search for linear combination of nullspace vectors with Hamming weight K. Interesting puzzle.

[Andrelvogue]

That looks awesome, Nice!

[testz]

Great works!  Waiting for the coin which use this algo. 
BTW: Please check this algo https://bitshares.org/media/archive/pts/whitepaper/MomentumProofOfWork.pdf it's based on finding birthday collision and already used in BitShares-PTS and some other coins but finally it's was optimized for GPU. 

[smooth]

Great works!  Waiting for the coin which use this algo. 
BTW: Please check this algo https://bitshares.org/media/archive/pts/whitepaper/MomentumProofOfWork.pdf it's based on finding birthday collision and already used in BitShares-PTS and some other coins but finally it's was optimized for GPU. 

That's already addressed in the paper. Search for [27]

[testz]

Great works!  Waiting for the coin which use this algo. 
BTW: Please check this algo https://bitshares.org/media/archive/pts/whitepaper/MomentumProofOfWork.pdf it's based on finding birthday collision and already used in BitShares-PTS and some other coins but finally it's was optimized for GPU. 

That's already addressed in the paper. Search for [27]

Excellent! Thanks for clarification.

[monsterer]

Do we have any 'branching hard' POW variations yet? Branching is what really makes optimisation difficult, not memory useage.

[tromp]

We have recently developed a memory-hard proof-of-work, which is based on the well known Generalized Birthday problem

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

Comments are welcome.

For more extensive discussion, see the reddit thread at

https://www.reddit.com/r/Bitcoin/comments/3n5nws/research_paper_asymmetric_proofofwork_based_on/

[Come-from-Beyond]

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.

Is there any extra advantage to use
- another type of memory (CAM vs RAM)
- another numeral system (trinary vs binary)
- another principle of computing (quantum vs classical)
?

The last point is especially important because of the recent trend to migrate to quantum-resistant cryptographic algorithms. Phenomenal ability of quantum computers to find global extremum of an almost any function could be (probably) utilized to "crack" your algorithm. It would be very interesting to see QC-resistance analysis.