Cuckoo Cycle: a new memory-hard proof-of-work system

[tromp]

I finished designing and implementing a new memory-hard proof-of-work system
based on Cuckoo Hashtables.

A preliminary version of the whitepaper is available online at
https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf

Please have a look!

[mehmehspazumweh]

POS is the future!

[tromp]

POS is the future!

I think both PoW and PoS have their place in the future.
PoW is useful in the startup phase to establish a sufficiently large
base of coins that can later be leveraged by PoS.

But as far as PoW go, Cuckoo Cycle has some very distinct advantages over hashcash-scrypt.

Both were designed not to be easily parallellizable. But computing a single scrypt is as demanding
on the prover as it is on the verifier, which means we cannot just make the prover's work harder
(i.e. use more memory) without also making life (too) hard on the verifier, i.e. every client.

Cuckoo cycle on the other hand has trivially verifiable proofs, while you can make the prover
use up to 14GB of memory and spend many minutes even at the lowest diffculty setting.

[kwukduck]

POS is the future!

For all future scam coins, yea I absolutely agree.

[Denna]

perfect timing as the Scrypt ASICs are getting better and better

[oleganza]

Excellent suggestion. I'm interested in applying this as PBKDF to be used in full-wallet encryption. The idea is to require 256Mb of memory and 2-3 seconds of computation per password to greatly increase the cost of bruteforce comparing to PBKDF2, bcrypt and scrypt. How would you suggest doing that with Cuckoo?

[franky1]

yet another waste of resources........

so much of a waste i wont even rant to explain why

[tromp]

Excellent suggestion. I'm interested in applying this as PBKDF to be used in full-wallet encryption. The idea is to require 256Mb of memory and 2-3 seconds of computation per password to greatly increase the cost of bruteforce comparing to PBKDF2, bcrypt and scrypt. How would you suggest doing that with Cuckoo?

I wouldn't base a PBKDF on Cuckoo, since you'd forego its best feature, namely trivial proof verifiabilty.

Are you preparing an entry for the Password Hashing Competition
at https://password-hashing.net/ ?
They also like candidates to have a limited amount of parallelizability, so that a multicore server
could use multiple cores to compute it. This is hard to arrange with Cuckoo.

Still, if you must use Cuckoo, you could use a size of 2^25, which uses 128MB,
and takes about 5s to run on a 3.2Ghz intel i5 with sha256 replaced by siphash
(which may well become permanent) and the default easiness setting.
The output could be sha256 applied to the sequence of all writes to the cuckoo array
(including the path reversals).

[spartacusrex]

Hi tromp,

Like the look of cuckoo.. Well done for coming up with it. Original work always gets an A+ in my book.

Sorry to ask for more -  - but is there any chance you could knock up a JAVA version ?

I would love to play around with it..

[AnonyMint]

Cuckoo Cycle won't work as a cpu-only PoW.

[spartacusrex]

Because it's too slow ?

And you'd get lots of stale blocks.. ?

no problem.. 

[AnonyMint]

Because it's too slow ?

And you'd get lots of stale blocks.. ?

no problem.. 

No you don't comprehend all the issues of the design of a coin.

[abhay81]

We have three words for you:

Design by vision

Intuition

Steve              (For it to make a dent in the world I'll go crazy and one day fade away)


Would you like to join a different open source revolution...

We need developers... more than you know (like really these are the kind of no.s that are mixed and matched so there is no way or sufficient cause for

breaking the bank)

Openly Backed Bitcoin Governing Protocol


Design by encouraging empathy

Judgement

Gandhi


The revolution you believed was coming has already come it was a part of the Bitcoin puzzle...

To emit the right signs...you hide your communication in puzzles so It is harder to get to

therefore the intuitive...

those on the edge of intelligence can only understand the message...also it is only those on the sharp edge of intelligence that have any valuable information

[benjyz]

I don't think so. it seems you can map-reduce the table, which is perfect for botnets.

"Bucketized versions of Cuckoo hashingcan achieve 95-99% occupancy, without any space overhead for pointers or other structures.

http://domino.research.ibm.com/library/cyberdig.nsf/papers/DF54E3545C82E8A585257222006FD9A2/$File/rc24100.pdf

[abhay81]

Yes my friend I hope you keep you eyes peeled and judge how many you believe you should invite to support for it to happen fast and yet secure...

I don't really care who does it in the end...It's just that If it has to be what it could be...It's value, has to completely outweigh the costs

I hope some people would like to take the responsibility of helping it happen...

Call everyone now...

I'm talking about honestCoins only

[DeepCryptoanalist3]

I'm talking about honestCoins only

Word honest require you to make mining reward proportional to the size of a network. To not allow creators and first involved persons to become nouveau riche just because of luck and adoption of their coins. Unless you fulfill this goal you can't say that your new currency system is honest.

[abhay81]

Exactly...therefore all bull and bear traps have been laid for whatever type of candidacy volunteers to help

 and I am showing you how you define or confine your losses

but pool ensures your + pool gain...

[tromp]

Hi tromp,

Like the look of cuckoo.. Well done for coming up with it. Original work always gets an A+ in my book.
Sorry to ask for more -  - but is there any chance you could knock up a JAVA version ?
I would love to play around with it..

Thanks!
I will write a Java version eventually, but it's pretty low on my list of priorities,
and I'm busy with many other things. Perhaps you can find some other Java programmer
to port it sooner. I will have more time in March...

[tromp]

I don't think so. it seems you can map-reduce the table, which is perfect for botnets.

"Bucketized versions of Cuckoo hashingcan achieve 95-99% occupancy, without any space overhead for pointers or other structures.

http://domino.research.ibm.com/library/cyberdig.nsf/papers/DF54E3545C82E8A585257222006FD9A2/$File/rc24100.pdf

You don't think what?

Bucketization is irrelevant to implementations of Cuckoo Cycle, which is *defined* based on plain cuckoo hashing.

[spartacusrex]

I will write a Java version eventually, but it's pretty low on my list of priorities,
and I'm busy with many other things. Perhaps you can find some other Java programmer
to port it sooner. I will have more time in March...

No problem..

I am a bit of a java boy myself and will admit to having tried to convert your code already.. and failed.. ha!

It's quite obfuscated.. with lots of 2 letter variables, pointers and no comments!  (I'm a bit comments OCD..)

What perturbed me is that there are literally only 20 or 30 lines of pertinent code, so I thought it would be easy.

Is there any chance you could just write a very simple pseudo code explanation ? I would convert that to java. (and SHARE of course)

I have looked through the pdf but that too is just a bit - gruesome..

Sorry to hassle, I would just love to play with it a bit..

Thanks again for your contribution!