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

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

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

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

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

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