The number of trimming rounds estimation


I’ve red the article “Cuckoo Cycle: a memory bound graph-theoretic proof-of-work” but haven’t understand sentence:“The number of trimming rounds, which can be set with option -n, defaults to 1+(B+3)*(B+4)=2, which was determined empirically to achieve a load close to 50%.”

I think that it’s possible to estimate number of trimming rounds to achieve a (some) load using binomial distribution. And it should be more precious than empirically data.

Or may be I don’t understand something?


Apparently someone has proven the following Cuckoo Cycle Conjecture:

which allows us to compute exactly how many rounds are needed to reduce the number of remaining edges to any desired fraction.


Oh, thx a lot. I should learn it…


I think that before your article you need to read this,
there is a foundation, and then you already have the analysis.

1 Like

Yes. I’ve make a mistake.

Of course it’s possible use binomial distribution but just for the first trimming step. So the calculation gives us good estimation 63%. But a lot off different kind of graphs can lead to the same graph after the first step. These are dependent probability events.

Thx for attention