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+1st 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 ≥ 29, and use edge indices (items) 0 .. N-1, where N = 2ⁿ. 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 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₀ = 1, and a_i+1 = 1 - e^-a_i

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