Seeking proof of the Cuckoo Cycle Conjecture

Allow me to introduce the Cuckoo Cycle Proof of Work, and conclude with a closely related Conjecture about random graphs, which I hope someone can find a proof for.

Cuckoo Cycle is named after the Cuckoo Hashtable, in which each data item can be stored at two possible locations, one in each of two arrays. A hash function maps the pair of item and choice of array to its location in that array. When a newly stored item finds both its locations already occupied, one is kicked out and replaced by the new item. This forces the kicked-out item to move to its alternate location, possibly kicking out yet another item. Problems arise if the corresponding Cuckoo graph, a bipartite graph with array locations as nodes and item location pairs as edges, has cycles.

While $$n$$ items, whose edges form a cycle, could barely be stored in the table, any $$n+1$$st item mapping within the same set of locations (a chord in the cycle) would not fit, as the pigeonhole principle tells us.

In the Proof-of-Work problem, we typically set $$n \ge 29$$, and use edge indices (items) $$0 \dots N-1$$, where $$N = 2^n$$. The endpoints of edge $$i$$ are (siphash(i|0) % N, siphash(i|1) % N), with siphash being a popular keyed hash function. A solution is a cycle of length $$L$$ in this bipartite Cuckoo graph, where typically $$L = 42$$.

Cuckoo Cycle solvers spend nearly all cycles on edge trimming; identifying and removing edges that end in a leaf node (of degree 1), as such edges cannot be part of a cycle. Trimming rounds alternate between the two node partitions.

The fraction $$f_i$$ of remaining edges after $$i$$ trimming rounds (in the limit as $$N$$ goes to infinity) appears to obey

The Cuckoo Cycle Conjecture: $$f_i = a_{i-1} * a_i$$, where $$a_{-1} = a_0 = 1$$, and $$a_{i+1} = 1 - e^{-a_i}$$

$$f_i$$ could equivalently be defined as the fraction of edges whose first endpoint is the middle of a (not necessarily simple) path of length $$2i$$. So far I have only been able to prove the conjecture for $$i \le 3$$. For instance, for i = 1, the probability that an edge endpoint is not the endpoint of any other edge is (1-1/N)N-1 ~ 1/e.

Here's hoping someone finds an elegant proof...

• What does $e < ^{-a_i}$ mean? Typo? – darij grinberg Apr 5 '19 at 19:35
• Sorry; the < was leftover from attempt to use html <sup> tag. Fixed now. – John Tromp Apr 6 '19 at 16:10