I addressed your (mistaken) criticism in your thread.

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

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

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

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

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

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

I mean that the statement you said there is not necessarily true!  Let's try phrasing it as a question:

Given a fixed hash rate budget and desired rate of finding blocks,
does it require more or less memory to solve the problem of finding a single colliding pair in a large sparse graph,
or to find a length-L cycle in a smaller, more dense graph?

Note the difference in those two problems:  In order to have a non-negligible probability of finding a large cycle, your problem requires a much more dense graph than a problem such as Momentum.  Furthermore, it induces a relationship between the elements in the graph that is not present in Momentum.  In M, you can approximately analyze it by looking at the independent collision probability.  That's not necessarily the case in CC.

This is why I keep mentioning sampling.  Consider this statement:

Given L=42 in the cuckoo cycle problem with N < 2^32,
if a graph G contains an L-cycle,
a random sample of x% of the edges in the graph will contain at least two edges in that L-cycle with probability > 999,999 1,000,000.
Math edit:  Replaced 10% with x% -- there is some x for which this is true.

You can go check the math yourself - it's just a binomial with p=x%.

Does this mean anything?  I don't know -- but it tells me *immediately* that the problem requires a different kind of analysis than what you would do for Momentum!  For example, what if you started by sampling lg(n) edges and then growing and pruning that set through 42 rounds?  With some reasonable probability, you'd extend into one of the cycles.  Not guaranteed, but it doesn't have to be guaranteed - I can always start over.
[/quote]


Not at all.  The primes have an entirely different goal.  The point is that you're advertising cuckoo cycle as having a certain set of desirable properties.  Someone shopping for a PoW wants a certain set of properties - some people want the social/scientific good of primes.  Some people want memory.  Some people want fuzzy teddy bears.  (grin).  For the advertised properties, there needs to be a stronger proof.

I'm not trying to prescribe what choice or properties any coin should pick from a PoW.  That's an entirely different question.


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.)"
[/quote]

Yes.  It's non-trivial to "store this bit vector in a compact way" but it can be done.  See the SDSL link I provided, for example.

To quote myself back:  "Not guaranteed, but ... can always start over."  In other words, you can settle for a 20% chance if you're willing to run the sampling test a few times, if it saves you enough memory.

Remember, part of the game is that you have to take the entire context of the search process into account:  An attacker can change the random seed, as well, at some modest cost.  The definition of the problem is to find a cycle, not the cycle.  Again - time/memory.  There are a lot of different ways to try to exploit such a tradeoff.  This gets back to the issue I emailed you with about searching for a biased initial distribution.  Neither of us knows whether or not it would work.


Your writeup of Cuckoo Cycle, as of Mar 28 09:28, said:

"We introduce the very first proof-of-work system that is both verify-trivial and tmto-hard."

Period.  There were no qualifiers attached to that statement.  No conjectures, no conditionals, until section 10, where you note that it's a conjecture. 

Yes - if you said "We introduce the first Proof-of-Work scheme based upon graph-theoretical structures.  We hypothesize but have not proved that this PoW may lead to certain memory-hardness properties" I'd be totally fine with it, because it would be an accurate description of what you've done.


ok - one last spoonful and I'm done:

Create a bitvector representing the first half of the nonces.  Call it the "lower half".
Iterate on this bitvector using the full nonce state *multiple times* until you have eliminated all candidates in the "lower half" bitvector that you can relative to the full set of candidates in the lower half (some of which are being eliminated) and all candidate nonces in the "upper half" (which you're not eliminating because you don't have memory).

Then, in piecewise fashion, identify a size-appropriate subset of the specific incident edges on the lower half that are causing problems -- in other words, which nonces in the "upper half" are causing collisions in the "lower half" that prevent you from discarding some of the lower-half entries?

For that small subset (of size << 1/2N -- let's say 1/8th N), do the same process:  Eliminate them relative to your now-sparsified lower half and the complete upper half.  This should allow you to eliminate more of the lower-half edges.  Repeat until the lower-half is sufficiently sparse that you can represent it in reasonable compressed space, and move on to the upper half.

Is it awesome?  No.  Have I thought about it for more than 5 minutes?  No.  Could an expert come up with a drastically better algorithm?  Probably.

Stop trying to defend your algorithm for a few minutes and start trying to attack it.  Your goal in this should not be to try to refute individual objections, because that process can go on forever, fruitlessly.  Refute categories of objections based upon sound reasoning and theoretical analysis of the difficulty of the underlying problem!

I'm done.

I think this is really interesting, if only because I think the PoW problem hasn't been solved for good.