Bitcoin Forum

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!

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.

For all future scam coins, yea I absolutely agree.

perfect timing as the Scrypt ASICs are getting better and better

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?

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

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

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

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 -  :P - but is there any chance you could knock up a JAVA version ?

I would love to play around with it..

Cuckoo Cycle won't work (https://bitcointalk.org/index.php?topic=355532.msg5112752#msg5112752) as a cpu-only PoW.

Because it's too slow ?

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

no problem..  ;D

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

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

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

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

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.

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

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

You don't think what?

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

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!

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

I addressed your (mistaken) criticism in your thread.

Already a bit clearer..

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

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

Excellent!!

Thank you..

It's playtime :-)

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

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.

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

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

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

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

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

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

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.

You need about 33% for 1 in a million odds of less than 2 L-cycle edges in your sample.


To have 50% odds of at least one L-cycle edge, you need to sample about 1.5%
log(n) doesn't cut it.


So you're saying I mismarketed Cuckoo Cycle. I could have said.

Let's have a PoW based not on number-theoretical, but on graph-theoretical structures.
Existence of a certain small-size subgraph in a large random graph makes for an easily
verifiable PoW. We could look for cliques, or for ... cycles!

Then you'd be fine with it?!


In the first round of full U and V trimming, you pass through a state of the bit vector
having about half 0s and half 1s. At that point it's completely incompressible.
Even with a 10% vs 90% distribution (that takes at least 2 full rounds to reach)
it would be practically infeasible to compress.

Actually, that could be quite interesting. Since proof size grows quadratically with clique size,
you'd want to limit it to cliques of size 10 (giving proofs of 45 nonces).
One can set the desired probability of finding such a clique (in the range 1% to 50%)
and figure out what number of edges in a large random graph makes that happen.

As with Cuckoo Cycle, edge trimming could be successfully applied:
repeatedly count vertex degrees (using 4-bit counters) and remove all
edges incident to a vertex of degree < k-1, where k is the clique size.
Perhaps this even keeps up a high enough reduction rate that
you can afford to keep going until either nothing or a clique is left...

We could make the following little table of "scientific" coins/PoWs:

                              chain-structure         cluster-structure
number-theoretic       primecoin                riecoin
graph-theoretic         cuckoo cycle            cliquecoin

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.

That's why I mentioned 50%. Settling for 20% or 50% makes little difference.
You can settle for 0.1% and still the log(n) doesn't cut it.

Again, this makes no difference except for small constant factors, since you expect to
find about only 3 cycles on average.


You're right. I was wrong to claim hardness without proof.
I rewrote the README and shall rewrite the paper as well when I have time,
possibly dropping the hardness hypothesis.


Thanks for elaborating on how to pass the incompressibility threshold.
Rephrasing, you paint half the edges red and half blue, and eliminate red leaf-edges.
Now remaining red edges are separated from the leaves by blue edges.
So you identify a small fraction of these separating blue edges that touch a remaining red edge,
and paint them purple. Identifying some leaf purple edges let's you eliminate some
more green edges. Choose different red edges to paint purple and repeat.
If necessary, try to identify blue edges separated by two red edges from a leaf
by recursing deeper.

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

Us boys over at MyriadCoin will keep an eye on this algorithm ;)

A complete working implementation of Dave's scheme is now available on my github.
Makefile targets cuckooNN still use the old memory hungry algorithm,
while targets tomatoNN use his edge trimming (12 rounds by default).
I haven't figured out how to achieve speed parity:-(

Suggestions for further improvement are more than welcome!

-John

Next on the to-do list is another of Dave's suggestions:
to bucketize the array of nodes to work on, to improve
main-memory locality. That will help the edge trimming,
which works on only one edge endpoint at a time,
but won't help the original algorithm, which needs to work
on both edge endpoints at the same time.
So that may well achieve speed-parity...

And so it did! Reducing the number of page faults is a big gain.

Edge-trimming is 33% faster single-threaded, but multi-threading
speedups are very erratic, e.g. 7-11 threads are all worse than
6 threads, 12 is much faster but then slow down through
19 threads, and finally gain more than double at 20 threads.

The new code is up at https://github.com/tromp/cuckoo,
as Makefile targets cuckooNN (for various value of NN).
The old code is now only useful for small instances and
relative easiness > 50% (at which edge trimming fails).

Apparently this is due to the use of C++ atomic datatypes.
Experiments using plain non-atomic datatypes instead,
show negligable differences, so that is now the default.

Current performance is listed in the README as

 6) running time on high end x86 is 9min/GB single-threaded, and 1min/GB for 20 threads.

The big open question is still how well a GPU can perform Cuckoo Cycle.

Most main memory accesses in (the current algorithm for) Cuckoo Cycle
are to different 64-byte segments (GPU cache line size), making latency
of prime importance. And that's where GPUs fare worse than CPUs...

Actually, the bucketing doesn't affect page faults.
Profiling shows that the large speedup is due to big reductions in
stalled-cycles-frontend and stalled-cycles-backend. Somehow
alternating siphash computations with main memory accesses causes
lots of stalls, while doing a bunch of hashes followed by a bunch of
main memory accesses is much better.
Damn; performance optimization is hard...

Bucketing at the size you're doing isn't about page faults, it's more about cache misses.  A cache miss causes a stalled cycle.

Also, you don't mean page faults:  You mean TLB misses.  Page faults are huge and rare.  A TLB miss, at various levels of the hierarchy, is common.

You can eliminate the TLB misses as a factor by allocating your data structures in hugepages.  see, for example,

http://lxr.free-electrons.com/source/tools/testing/selftests/vm/map_hugetlb.c

You're right about the TLBs. Bucketing reduces TLB load misses from 2.8 billion to 0.56 billion
(even while increasing TLB store misses from 1.7 million to 467 million).

My stalled cycles do not appear due to cache misses though.
The bucketed version has slightly more cache misses; 3.51 billion versus 3.14 billion.

Maybe the stalled cycles are also due to the TLB misses?!

It cannot "underperform compared to Momentum in its memory requirements"
because Cuckoo Cycle generalizes Momentum.

Momentum looks for collisions of a hash function mapping 2^{26} nonces to 50-bit outputs.
Each nonce corresponds to an edge in a bi-partite graph on nodes M union L, where
M is all possible 25-most-significant bits of hash output, and
L is all possible 25-least-significant bits of hash output,
and so each collision is a 2-cycle in this graph.

Thus, it is more likely that Momentum, being a special case of Cuckoo Cycle,
underperforms in its memory requirements.

any coins using this algo atm?

Nope...

tromp - after our discussion on k-SUM (https://bitcointalk.org/index.php?topic=659728), I went back and tried to categorize why I was uncomfortable with Cuckoo Cycle in its present state right now.  Basically it comes down to:

- It seems like the selection of 42 for the cycle length was based on experimentation, but there doesn't seem to be a hard proof for this (dga mentions this).  I was originally looking at kSUM because the difficulty of kSUM is well known.  In the case of cycle finding, I'm not sure if the difficulty is proven.

- One way of proving this might be to instead establish the probability of a cycle of length k occurring in a randomly generated graph, and then tweaking parameters so the expectation is only 1 cycle is found.

- Separately might it make sense to look deeper at k-cliques? Their probability seems to be much better understood, and might provide a more provably secure basis.

Quick starting point:

Assume G(n,p) - Erdős–Rényi graph
let pK = Probability k nodes are a clique p^(k choose 2)
let pNK = Probability no k-clique exists (1-pK)^(n choose k)
Probability at least 1 k-clique exists = 1-pNK

Thoughts?

You can find the motivation for choice of cycle length in the whitepaper; I devoted a section to it.


Proofs are for theorems, not for parameter choices.

There is more literature on cycle detection in graphs than on k-SUM, and very little
on k-SUM in cyclic groups as you consider.


My whitepaper has sufficient data on probability of cycles occurring. You don't need
expectation equal to 1. Any non-negligable constant less than 1 works just as well.
[/quote]

While the Cuckoo Cycle paper does devote a section to this, the section lacks any hard guarantees on whether the parameter choices are correct or optimal.  The graphs in the paper were derived from what seem like experimentation, but the problem with such an approach is it leaves open the possibility that more efficient and effective attacks exist.

There needs to be provable formulae establishing the relationships between parameter choices, the likelihood of cycles, and in turn the theoretical bounds that any attacking implementation could have.  Without this, it leaves open the possibility of novel attacks that may not have been identified yet, which is no basis for a currency.


I'm not advocating k-SUM as I think we've established it is a dead-end.  That said, while there is much literature on cycle detection in graphs, I haven't found much in terms of proofs that concretely establish the probability of n-length such cycles existing in a G(n,p) graph.  Would certainly appreciate information here if you are familiar with work in this area, and I think it would go a long way towards strengthening the fundamentals of Cuckoo Cycle as proposed.

Remind me again, which other Proof-of-Works have guarantees of parameter optimality,
and where to find proof of these?

Momentum is trivial to prove for any parameter selection because it is based on a well known problem.

Cuckoo Cycle is based on a novel graph-theoretic approach which may or may not have vulnerabilities, but without a proof of difficulty for a particular set of parameters, there is no way to asses the vulnerability to future attacks.

Optimality comes through applying engineering requirements to a defined set of provable algorithm characteristics.  We don't have that (yet) for Cuckoo Cycle.

EDIT #2: Grammar, also some searching turned up this recent (2009) paper "Deviation inequality for the number of k-cycles in a random graph" by Wang and Gao.  Perhaps it may be of use?

I'm afraid you're not making much sense.

If we're going to continue this discussion you should first define your terminology.
What mathematical statement about Momentum is trivial to proof?
What constitutes a vulnerability of a proof-of-work?
What is a proof of difficulty?

And how do you rhyme the above with my Apr 30 observation that Momentum is a special case of
Cuckoo Cycle where cycle length equals 2, a choice which leads it to be particularly memory-easy?
[/quote]

What doesn't make sense?


It is an instance of the birthday problem, where complexity is understood.


The possibility implementations exist that exploit unaccounted for (lower and amortized) bounds in memory and/or execution time.


A proof the amortized limits of memory and execution time cannot be less than the proposed implementation for a PoW.


Cycle lengths of 2 and 3 are special cases because they can be restated in terms of the birthday problem and 3-cliques respectively.  They do not generalize to k-cycle (nor 42-cycle), which is the concern.

I don't think this is understood.


What is the minimum memory usage for a Momentum implementation?

Why don't you think the complexity of Momentum understood/proven?

From your Cuckoo Cycle paper:

I observed that length 2 Cuckoo Cycle is equivalent to Momentum is equivalent to finding birthday collisions
(ignoring differences in choice of hash function and in number of edges).

What makes you think that says anything about lower bounds for space and time use?

We don't know how much memory and time is needed for finding birthday collisions.
We just have some upperbounds, and some linear trade-offs of memory for time.

We similarly have some upper bounds for the more general Cuckoo Cycle and fewer known trade-offs
(no linear one), which in your terminology makes Momentum the more vulnerable one.

We explored this when looking at k-SUM, where it became clear there was an amortized O(sqrt(n)) compute cost and an O(n) space cost, rooted in the probability of a collision which has been proven via the birthday paradox.

AFAIK the probability of there being a k-cycle in a bipartite undirected G(n,p) graph, where k > 3 has not been proven, so we don't have a strong basis to judge the bounds of an ideal solution for Cuckoo Cycle.  This is were I would love to be proven wrong, as it would lay to rest the possibility of there being unknown backdoors in Cuckoo Cycle.

By backdoor, do you mean time-memory trade-offs?
These do not depend in any way on the exact value of the probability of the Cuckoo graph
having a k-cycle. The whitepaper already has numerical approximations for those probabilities,
which suffice for any run-time or memory-use analysis...

I share some of optimiz3's concerns.  Let me give an incorrect hypothetical example:

What if it were possible to establish, with P(error) < 10%, whether or not a graph *had* a 42 cycle using, e.g., a histogram of the counts of edges incident upon vertices?

(I doubt this is true - I'm pulling something plausible-sounding out of that place we pull such things.)

In other words, if there were some relatively simple-to-measure characteristics of the graph that would let you rapidly find good candidates to spend your effort on, an optimized solver might spend a lot of time *generating graph instances* and relatively little time evaluating them using much memory at all.  With your default parameters of about 2.5% of graphs having a 42-cycle, this could easily result in a 10x speedup using comparatively little chip area or memory.

I'm not saying at all that such a thing exists.  But it's the kind of avenue of attack I worry about.

I think you're misreading my answer.
I was telling optimiz3 that it doesn't matter whether the probability is 2.4% or 2.6%, so he should not require me to prove some exact closed form expression for the probability and just accept my numerical approximations as being good enough for analyzing resource usage.

As to your hypothetical graph-statistics filter, that is not something I worry about in the least:-(

Sorry - i was overgeneralizing from his note.  I agree with you that the expected probabilities (for the specific N you evaluated) are pretty clear given that the graph is random.

But I was trying to re-introduce the higher-level issue that, while the graph is random, a solver always has two options:  continue working on the current graph or throw it away and try a new one.

Indeed. And this could very well be taken to the extreme with the cuckoo tmto you identified;
when looking at vertex subsets of size N/k, only look at the first one, and skip all the k-1 others,
since they will have less chance (even if ever so slightly, due to partial overlap) of producing a solution.

The only cost to switching to the next graph is one sha256 to compute a new siphash key...

.

Sorry to necro bump but I suspect this is going to be relevant again soon and this is the thread for it.

Any theories about the bottlenecks in mining with Cuckoo Cycle?  I mean I know it's supposed to be memory hard but here is a platform with 96 DIMM slots http://www.tyan.com/datasheets/DataSheet_FT76-B7922.pdf This thing can hold up to 6 TERABYTES of DRAM. Surely one would start to run into processor bottlenecks before that point but when? And also just more generally curious on peoples thoughts on the most efficient way to mine with Cuckoo Cycle.

Also fancy seeing you here aminorex.

Lots of memory is not enough. You need lots of memory bandwidth, and enough cores to saturate it.
Currently, GPUs seem superior to CPUs:

https://github.com/tromp/cuckoo/blob/master/GPU.md

Note there is $35000 in bounties for various performance doublings.

He's not the only one that has monitored this thread. :)

This was a little ahead of it's time but I agree it will become relevant soon.

Tromp how will this hold up against HBM? It seems to be taking longer than expected to become cost effective.

Too early to tell. The current GPU solver writes + reads about 27GB of data within 1 second on a 1080Ti, which has a bandwidth of 484GB/s. So there are still other bottlenecks to overcome...

Ahh, I haven't read enough to know it is cuda dependent. I'll try to catch up in the next week, what the best link for that? I think was the last thing I read on this.

http://cryptorials.io/beyond-hashcash-proof-work-theres-mining-hashing/

EDIt: I just remembered this is hardware agnostic isn't it? It should be IIRC. Were you just using the Nvidia as an example?

Pretty agnostic indeed.
My benching was done on intel Core i5/i7 and that NVidia, and I happen to have the memory bandwidth data
available for the latter.

I'm rewriting my Cuckoo Cycle paper to have more details on mean miner. For now, it's best to study its source code.

I wish I still could, unfortunately those days are past for me. :)

I'll just keep an eye on grin and assume (yeah I know) that we will see the latest mirroring there as well.

BTW this threads OP needs some +M.