8
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.