|
Title: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: khovratovich on September 30, 2015, 10:47:54 AM 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 Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: spartacusrex on September 30, 2015, 11:08:07 AM Congratulations! A lot of work went into that.
I skimmed it.. But there seems to be something missing ? .. the NAME ? ;D 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. Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: r0ach on September 30, 2015, 11:16:51 AM 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". Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: smolen on October 01, 2015, 12:46:00 AM given a list of binary vectors X1, X2,..XN and number k find i1,i2,..ik such that Xi1 + Xi2 +.. + Xik =0. Binary matrix kernel, Krylov subspaces and block Lanczos algorithm (https://en.wikipedia.org/wiki/Block_Lanczos_algorithm).The non-trivial algorithm for it was developed by Wagner in 2001 and has been studied extensively since then. 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. Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: Andrelvogue on October 01, 2015, 07:04:37 AM That looks awesome, Nice!
Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: testz on October 01, 2015, 09:32:32 AM 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. :( Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: smooth on October 01, 2015, 10:23:38 AM 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] Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: testz on October 01, 2015, 11:49:59 AM 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. Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: monsterer on October 01, 2015, 08:43:51 PM Do we have any 'branching hard' POW variations yet? Branching is what really makes optimisation difficult, not memory useage.
Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: tromp on October 02, 2015, 06:06:14 PM 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/ Title: Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience Post by: Come-from-Beyond on October 03, 2015, 10:50:23 AM 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. |