Topic: Cuckoo Cycle: a new memory-hard proof-of-work system - page 3. (Read 10866 times)

We know finding two incident edges in a graph is (way) easier than finding a 42-cycle.
So I don't know what you mean by underperform.


I feel that unnecessarily limits the PoW landscape. And could have left prime-based
PoWs out in the cold as well.


Are you referring to this paragraph of your blog?
"(There is a way to slightly reduce the memory demands:  Split the bit vector in half, and record the live bits only for the first half across multiple iterations of the test, using the full second half.  Then store this bit vector in a compact way, and perform the computation on the second half.  This doesn't extend very far past a factor of two reduction, but it does require only a roughly linear increase in the amount of computation and could possibly get the storage needed down to about 300MB for 2^32.)"

That depends on the reason someone is deploying it.  If someone is deploying a PoW because they desire only a minimum computational amount of work, of course it's safe to deploy something that has a fallback to iterated sha256/hashcash.

But that's not why someone would look at CC:  They'd look at it because they want something with memory requirements that grow in some way that they believe can be used to bias the hash against certain technologies for implementation (e.g., ASICS).

So while your statement is true, it's not necessarily the right truth.  Is Cuckoo Cycle better or worse than adaptive scrypt-N?  Is it better than a variant of Invictus's Momentum PoW that has an adaptive N factor?

Neither of us knows the answer to this question.  There is a chance that it's stronger.  But there's also a very real chance that the requirement to find a cycle, instead of a simple collision, will mean that the approach can yield to something with sublinear memory requirements and, in fact, underperform compared to Momentum in its memory requirements.

That is why I'm being cautionary about this.


Sure, but again:  The best way to design a strong algorithm in a security context is not to generate ideas until you find one you cannot disprove.  It's to start from things that are known to be hard and to base the security of your algorithm upon the hardness of those things.

I've already told you how to modify the algorithm I explained to use 1/2 bit per nonce with a 4x slowdown.  The idea generalizes to using 1/k memory for a > k^2 slowdown.  This is a good tradeoff, but it's not the be-all-end-all.  It does require some very careful compressed representation of the bitvector, but this stuff is known and there are fast implementations available -- see, for example, the SDSL:  https://github.com/simongog/sdsl-lite

Cuckoo Cycle is no less safe to deploy than either prime-based or hash-cash proofs-of-work.
It needs a minimum amount of work, namely computing millions of siphashes.
Dynamic difficulty adjustment will take care of as-yet-undiscovered optimizations to the
current (and new) algorithm.

It's true I haven't done anywhere near as thorough a job as Colin. My hat off to him.
My notion of tmto-hardness is stronger than his though.
I aim to require a barrier that polynomial trade-offs can not cross
(but phrased in concrete terms rather than quantified formulas and big-Oh notations).

The least I can do is encourage the search for a disproof.
As the current README shows:

"Cuckoo Cycle remains tmto-hard assuming at least one bit per nonce is required.
 I offer a $1000 bounty for an implementation using less, with at most 100x slowdown."

I know, that's a very modest sum. And much less than was offered for Momentum.
But then I've seen what happened with that one...

PS: concerning social good. I'd love for a "research coin" to come out that can serve as a laboratory for new ideas, maybe one running only on testnet. It could perhaps be based on NXT source code, with a PoS/PoW hybrid instead of pure PoS, and Myriad's support for multiple PoW algorithms...

Additionally, the designer (me in this case) is probably in a bad position to find attacks
because they want the neat algorithm with nice properties that they found to be the optimal one,
and this wishful thinking clouds their mind...

Back to the drawing board...

Baseline:  My code uses 10x less memory and runs 2x slower (on a laptop instead of an i7).  At 6x less memory, it should have speed parity.  Could be optimized substantially - I sent you some very hacked up code.  Happy to post it publicly if anyone's interested, but it's trashy - I just wrote it as a proof of concept for the pre-filtering before invoking the cycle finder.  But it gets the point across.

But, more generally:  I think it's great that you've put the proposal document out publicly for comment before it's adopted.  That's the right place to start.  But I think it should be taken one step farther.  Consider the approach Colin Percival used in developing scrypt:  A PoW for serious consideration in a cryptocurrency needs a stronger proof of hardness.  I don't put things like Riecoin and Primecoin in this batch, because their goal is social good more than a particular technical goal of memory use, but the care that went into scrypt's theoretical evaluation is worth modeling.  I think there are some very serious approaches that might keep time linear or sublinear and reduce memory to sublinear -- but whether or not one person can think of an attack is not the right approach for determining whether the idea is resistant to attack.  I put some time into thinking about this one because there seemed to be increasing interest in it, but I _really_ hope that the takeaway from this is not "oh, it's what Dave says it is", but "hey, we need to kick the tires of this in a more formal and careful way, by trying to prove that it's _right_."

I realize that's not an easy task.   But security is hard.

  -Dave

Dave has shown my algorithm is not as tmto-hard as I thought it was.
Excellent work, Dave!


For now, I amended my README at https://github.com/tromp/cuckoo with the following


UPDATE: Dave Anderson proposed an alternative algorithm on his blog

http://da-data.blogspot.com/2014/03/a-public-review-of-cuckoo-cycle.html

that uses significantly less memory than mine at potentially less than an order of magnitude slowdown. I hope to soon implement his algorithm and quantify the "tomato" (his pronouncable spelling of tmto, or time-memory trade-off).

At John's request, I've taken a look at this and scribbled up my initial comments.

They might be wrong!  Please take them in the spirit of continuing the discussion, not as the final word.

http://da-data.blogspot.com/2014/03/a-public-review-of-cuckoo-cycle.html

I'll post an addendum to the blog post (and here) with anything that's shown to be wrong.

Try "make java" on the latest version...

Excellent!!

Thank you..

It's playtime :-)

Notice any changes to https://github.com/tromp/cuckoo lately :-?

The verifier is done; I should have the solver ported soon as well.

Already a bit clearer..

I addressed your (mistaken) criticism in your thread.

The code will be easier to understand if you read the paper. try to get through the gruesome...
The algorithm repeatedly generates edges (u,v) and follows paths from u and v.
These paths are stored in arrays us[] and vs[], with nu and nv used as path length.
The edge is actually stored in us[0] (same as *us in c) and vs[0] (same as *vs).

Why don't you fork my repo and translate all the code into java as best as you can.
Then allow other people to contribute. When I have time, I'll look over your progress and
help fix it up...

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!

You don't think what?

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

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

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

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.