Author

Topic: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience (Read 1053 times)

legendary
Activity: 2142
Merit: 1010
Newbie
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.
legendary
Activity: 990
Merit: 1108
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/
legendary
Activity: 1008
Merit: 1007
Do we have any 'branching hard' POW variations yet? Branching is what really makes optimisation difficult, not memory useage.
legendary
Activity: 1764
Merit: 1018
Great works!  Smiley Waiting for the coin which use this algo.  Smiley
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.  Sad

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


Excellent! Thanks for clarification.
legendary
Activity: 2968
Merit: 1198
Great works!  Smiley Waiting for the coin which use this algo.  Smiley
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.  Sad

That's already addressed in the paper. Search for [27]
legendary
Activity: 1764
Merit: 1018
Great works!  Smiley Waiting for the coin which use this algo.  Smiley
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.  Sad
hero member
Activity: 524
Merit: 500
given a list of binary vectors X1, X2,..XN and number k find i1,i2,..ik such that Xi1 + Xi2 +.. + Xik =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? Wink

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.
legendary
Activity: 1260
Merit: 1000
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".
hero member
Activity: 718
Merit: 545
Congratulations! A lot of work went into that.

I skimmed it..

But there seems to be something missing ?

..

the NAME ?  Grin

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.
newbie
Activity: 3
Merit: 0
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 X1, X2,..XN and number k find i1,i2,..ik such that
Xi1 + Xi2 +.. + Xik =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
Jump to: