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

Come-from-Beyond

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: khovratovich on September 30, 2015, 06:47:54 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.

tromp

legendary

Activity: 988

Merit: 1108

Quote from: khovratovich on September 30, 2015, 06:47:54 AM

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/

monsterer

legendary

Activity: 1008

Merit: 1002

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

testz

legendary

Activity: 1764

Merit: 1018

Quote from: smooth on October 01, 2015, 06:23:38 AM

Quote from: testz on October 01, 2015, 05:32:32 AM

Quote from: khovratovich on September 30, 2015, 06:47:54 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. Sad

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

Excellent! Thanks for clarification.

smooth

legendary

Activity: 2968

Merit: 1198

Quote from: testz on October 01, 2015, 05:32:32 AM

Quote from: khovratovich on September 30, 2015, 06:47:54 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. Sad

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

testz

legendary

Activity: 1764

Merit: 1018

Quote from: khovratovich on September 30, 2015, 06:47:54 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. Sad

Andrelvogue

full member

Activity: 140

Merit: 100

Quote from: khovratovich on September 30, 2015, 06:47:54 AM

That looks awesome, Nice!

smolen

hero member

Activity: 524

Merit: 500

Quote from: khovratovich on September 30, 2015, 06:47:54 AM

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? 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.

r0ach

legendary

Activity: 1260

Merit: 1000

Quote from: spartacusrex on September 30, 2015, 07:08:07 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".

spartacusrex

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.

khovratovich

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 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

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