# Next PoW CuckARooM unveiled at GrinCon1

**URL:** <https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605>\
**Category:** Mining\
**Created:** [November 24, 2019, 9:21pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605 "2019-11-24T21:21:41Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![tromp](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.grin.mw/tromp/32/22_2.png) [@tromp](https://forum.grin.mw/u/tromp)\
**Post date:** [November 24, 2019, 9:21pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/1 "2019-11-24T21:21:41Z")

</div>

Grin’s unique dual PoW system allows for a smooth transition from GPU  
mining to ASIC mining, with guaranteed rewards for the secondary PoW  
where GPUs need not compete with ASICs.  
The main ingredient for its ASIC resistance is frequent pre-planned PoW changes.

In [0] I introduced Cuckarood as the first tweak of Cuckaroo.

Just like Cuckaroo was only active for the 6 months from Jan 15, 2019 through Jul 17, 2019, so Cuckarood will no longer be active when Grin executes its 2nd pre-planned Hard Fork around Jan 15, 2020.

Its successor, and latest member of the Cuckoo Family,  
“Cuckaroom”, was unveiled last Friday at GrinCon1 as can be seen in slides [1] and video [2].  
In the earlier post linked above I mentioned 3 aspects of Cuckaroo that could be tweaked:

1. the underlying hash function, currently siphash-2-4
2. the computation of endpoints of a whole block of edges
3. the type of cycle

Where Cuckarood made tweaks in 1) and 3), Cuckaroom makes tweaks in 2) and 3) instead.

Regarding siphash, Cuckaroom reverts to the standard siphash.

Regarding edge block computation, instead of xoring intermediate siphashes with the final one:

```
const u64 last = buf[EDGE_BLOCK_MASK];
for (u32 i=0; i < EDGE_BLOCK_MASK; i++)
  buf[i] ^= last;

```

as in Cuckaroo/Cuckarood, in Cuckaroom we xor with all subsequent siphashes:

```
for (u32 i=EDGE_BLOCK_MASK; i; i--)
  buf[i-1] ^= buf[i];

```

The biggest change is in the type of cycle. The CuckarooM graph is no longer bipartite, with the ‘M’ standing for ‘Monopartite’.  
Cuckaroom29 has 2^29 directed edges on 2^29 nodes, resulting in cycles of all possible lengths, including odd ones, and even including unicycles.

Cuckaroom is implemented in the cuckoo repository at [3].  
The proof verification function [4] may serve as the specification,  
while Makefile targets simple19/simple29 implement a simple CPU miner and target cuda29 a reasonably performant CUDA mean miner. Due to the alternation of marking starting-points and end-points, this miner takes twice as many rounds to trim a given fraction of edges.

The expected number of 42-cycles in a Cuckaroom graph is 1/42, as it was in Cuckaroo, which is half of Cuckarood’s current value of 1/21.

So we can expect a large drop in C29 solution rate come hardfork time,  
from 1) slower solvers, 2) halved solution rate, and the seemingly unavoidable 3) unprepared miners. However, difficulty should adjust within a matter of hours.

In the coming week, I will push Pull Request on grin [5] and grin-miner [6] to implement the PoW changes on the Grin side of things. Then we’ll have a chance to see Cuckaroom activate on Floonet around December 19.

Happy Cuckoo Cycling!

[0] [https://forum.grin.mw/t/mid-july-pow-hardfork-cuckaroo29-cuckarood29](https://forum.grin.mw/t/mid-july-pow-hardfork-cuckaroo29-cuckarood29)  
[1] [https://github.com/mimblewimble/grin-pm/blob/master/presentations/grincon1/10-cuckaroom-tromp.pdf](https://github.com/mimblewimble/grin-pm/blob/master/presentations/grincon1/10-cuckaroom-tromp.pdf)  
[2] [https://www.youtube.com/playlist?list=PLvgCPbagiHgrQa5KVt4XixK9t\_NbfpkuP](https://www.youtube.com/playlist?list=PLvgCPbagiHgrQa5KVt4XixK9t_NbfpkuP)  
[3] [https://github.com/tromp/cuckoo/tree/master/src/cuckaroom](https://github.com/tromp/cuckoo/tree/master/src/cuckaroom)  
[4] [https://github.com/tromp/cuckoo/blob/master/src/cuckaroom/cuckaroom.hpp#L133-L164](https://github.com/tromp/cuckoo/blob/master/src/cuckaroom/cuckaroom.hpp#L133-L164)  
[5] [https://github.com/mimblewimble/grin/pull/3136](https://github.com/mimblewimble/grin/pull/3136)  
[6] [https://github.com/mimblewimble/grin-miner/pull/231](https://github.com/mimblewimble/grin-miner/pull/231)

---

<div class="post-metadata">

**Author:** ![tromp](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.grin.mw/tromp/32/22_2.png) [@tromp](https://forum.grin.mw/u/tromp)\
**Post date:** [November 25, 2019, 2:31pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/3 "2019-11-25T14:31:03Z")

</div>

> [@ddd](#):
>
> this new release is just improving highend rigs

Where do you get that?

---

<div class="post-metadata">

**Author:** ![Lolliedieb](https://avatars.discourse-cdn.com/v4/letter/l/e274bd/32.png) [@Lolliedieb](https://forum.grin.mw/u/Lolliedieb)\
**Post date:** [November 25, 2019, 3:36pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/4 "2019-11-25T15:36:50Z")

</div>

Like the changes, but will be interesting to tune the solvers - that monopartite structure makes things interesting. But wrt @ddd: As far as I can see all cards that are now physically able to mine grin-29 should also be able to do so in the future - so I do not see why this would require larger rigs. Only the hash may go down a bit due to a slower solver, but that hits slow and fast cards / small and big rigs the same way and the difficulty adjustment will handle this rather quickly.

---

<div class="post-metadata">

**Author:** ![Lolliedieb](https://avatars.discourse-cdn.com/v4/letter/l/e274bd/32.png) [@Lolliedieb](https://forum.grin.mw/u/Lolliedieb)\
**Post date:** [November 26, 2019, 8:12am UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/7 "2019-11-26T08:12:18Z")

</div>

By the way I did try to calculate the fraction of edges that remains now after each round.  
The formulas have changed compared to cuckaroo and cuckatoo, because there now is a dependency in the 2nd round trimming.

The following formula is still unproven, but fits first experiments very well:

Let a\_0 = b\_0 = 1  
And then a\_n = 1 - exp(- b\_(n-1)) and b\_n = a\_(n-1) for each later round.  
Then the fraction of edges left after round i equals a\_i \* b\_i

Here is a table for the first 50 rounds:

```
round	fraction	cumulative fraction	
0 1 1
1	0,6321205588	1,6321205588
2	0,3995764009	2,0316969597
3	0,2961714876	2,3278684473
4	0,2195263531	2,5473948004
5	0,1752711746	2,722665975
6	0,1399375711	2,8626035461
7	0,1167434973	2,9793470435
8	0,0973937454	3,0767407888
9	0,0836613349	3,1604021237
10	0,0718651791	3,2322673028
11	0,0630385242	3,295305827
12	0,0552959804	3,3506018074
13	0,049275533	3,3998773404
14	0,0439105724	3,4437879128
15	0,0396150783	3,4834029911
16	0,0357397852	3,5191427764
17	0,0325646834	3,5517074598
18	0,0296716558	3,5813791156
19	0,027256743	3,6086358586
20	0,0250383749	3,6336742335
21	0,0231578796	3,6568321131
22	0,0214186181	3,6782507312
23	0,0199250419	3,6981757732
24	0,0185356167	3,7167113898
25	0,01732921	3,7340405998
26	0,0162013234	3,7502419232
27	0,0152126251	3,7654545484
28	0,014284263	3,7797388114
29	0,0134636728	3,7932024841
30	0,0126902231	3,8058927072
31	0,0120015418	3,817894249
32	0,0113502342	3,8292444832
33	0,010766533	3,8400110162
34	0,0102128493	3,8502238655
35	0,0097137542	3,8599376197
36	0,0092390496	3,8691766693
37	0,0088089122	3,8779855815
38	0,0083988006	3,8863843821
39	0,0080254388	3,8944098209
40	0,0076686745	3,9020784954
41	0,0073424885	3,9094209839
42	0,0070301767	3,9164511606
43	0,0067435175	3,923194678
44	0,0064685469	3,929663225
45	0,0062152588	3,9358784838
46	0,0059718887	3,9418503725
47	0,0057469717	3,9475973442
48	0,0055305257	3,9531278699
49	0,0053298844	3,9584577543
50	0,0051365222	3,9635942765

```

The series seems to converge (for over 5000 rounds) to a value at around 4.25.

Also worth a mention that after 2n-1 rounds the same number of edges is left as before after n rounds 🙂

---

<div class="post-metadata">

**Author:** ![tromp](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.grin.mw/tromp/32/22_2.png) [@tromp](https://forum.grin.mw/u/tromp)\
**Post date:** [November 26, 2019, 8:41am UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/8 "2019-11-26T08:41:42Z")

</div>

Alternatively, we could count sorting rounds instead of trimming rounds, in which case the numbers shift down like

```
round	fraction	cumulative fraction	
0 1 1
1 1 2
2	0,6321205588	2,6321205588
3	0,3995764009	3,0316969597
4	0,2961714876	3,3278684473

```

giving a fraction matching between round 2n and cuckaroo(d) round n.

---

<div class="post-metadata">

**Author:** ![Kurt](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.grin.mw/kurt/32/3361_2.png) [@Kurt](https://forum.grin.mw/u/Kurt)\
**Post date:** [November 27, 2019, 4:05am UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/9 "2019-11-27T04:05:00Z")

</div>

Proving that the serie converges is a little math exercise (it does converge).

hints:

- prove that the (a\_n) (or (b\_n)) sequence converges to 0
- do a Taylor expansion (order 2) of the recursive relation
- use Cesàro lemma to get an equivalent of (a\_n), or (b\_n)
- conclude

---

<div class="post-metadata">

**Author:** ![Gandalf1](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.grin.mw/gandalf1/32/2900_2.png) [@Gandalf1](https://forum.grin.mw/u/Gandalf1)\
**Post date:** [December 13, 2019, 3:27pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/10 "2019-12-13T15:27:25Z")

</div>

In the ardent expectation, it is finally coming! Thanks for your hard work, this will be a new era and a new starting point!

---

<div class="post-metadata">

**Author:** ![slate](https://avatars.discourse-cdn.com/v4/letter/s/e9bcb4/32.png) [@slate](https://forum.grin.mw/u/slate)\
**Post date:** [January 5, 2020, 3:18pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/11 "2020-01-05T15:18:15Z")

</div>

> [@Kurt](#):
>
> Proving that the serie converges is a little math exercise (it does converge).
> 
> hints:
> 
> - prove that the (a\_n) (or (b\_n)) sequence converges to 0
> - do a Taylor expansion (order 2) of the recursive relation
> - use Cesàro lemma to get an equivalent of (a\_n), or (b\_n)
> - conclude

Or just denote the limit by L (showing it exists is trivial), where you have that lim\_n a\_n = lim\_n a\_{n-1} = L, and hence L=1-exp(-L), which gives L=0, without any approximations or iterative methods.

---

<div class="post-metadata">

**Author:** ![Kurt](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.grin.mw/kurt/32/3361_2.png) [@Kurt](https://forum.grin.mw/u/Kurt)\
**Post date:** [January 5, 2020, 3:35pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/12 "2020-01-05T15:35:07Z")

</div>

You did not understand my post and what we want to show.

---

<div class="post-metadata">

**Author:** ![slate](https://avatars.discourse-cdn.com/v4/letter/s/e9bcb4/32.png) [@slate](https://forum.grin.mw/u/slate)\
**Post date:** [January 5, 2020, 4:05pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/13 "2020-01-05T16:05:27Z")

</div>

I only offered a proof of the 0 limit for a\_n and b\_n. The limit of a\_n\*b\_n is different

---

<div class="post-metadata">

**Author:** ![Kurt](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.grin.mw/kurt/32/3361_2.png) [@Kurt](https://forum.grin.mw/u/Kurt)\
**Post date:** [January 5, 2020, 4:16pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/14 "2020-01-05T16:16:52Z")

</div>

We need to prove the convergence of a serie, not a sequence.

Plus you did not offer any proof. The fact that the limit exists does not necessarily mean that you can replace the terms in the recursive relation in order to find the value of the limit.  
Here it works, because the function x gives 1 - exp(-x) is continuous on the closed interval 0, 1 (I miss a bunch of characters on my phone keyboard). if it is not continuous you can have pathological cases where finding the value of the limit of the sequence has to be done differently.

---

<div class="post-metadata">

**Author:** ![slate](https://avatars.discourse-cdn.com/v4/letter/s/e9bcb4/32.png) [@slate](https://forum.grin.mw/u/slate)\
**Post date:** [January 5, 2020, 4:22pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/15 "2020-01-05T16:22:40Z")

</div>

We’re dealing with continuous functions, of course I can swap in and out (basic continuity criterion, convergent sequences). What series (sum) are you talking about?

---

<div class="post-metadata">

**Author:** ![Kurt](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.grin.mw/kurt/32/3361_2.png) [@Kurt](https://forum.grin.mw/u/Kurt)\
**Post date:** [January 5, 2020, 4:25pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/16 "2020-01-05T16:25:08Z")

</div>

look at the column on the right of the table provided by Lollidieb and you will be able to find out the serie

---

<div class="post-metadata">

**Author:** ![slate](https://avatars.discourse-cdn.com/v4/letter/s/e9bcb4/32.png) [@slate](https://forum.grin.mw/u/slate)\
**Post date:** [January 5, 2020, 4:27pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/17 "2020-01-05T16:27:58Z")

</div>

Ah, yes, I missed the “cumulative” heading

---

<div class="post-metadata">

**Author:** ![slate](https://avatars.discourse-cdn.com/v4/letter/s/e9bcb4/32.png) [@slate](https://forum.grin.mw/u/slate)\
**Post date:** [January 5, 2020, 4:50pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/18 "2020-01-05T16:50:47Z")

</div>

This is a neat highschool question actually (might also work using D’Alembert’s criterion and L’Hospital since the summand is a\_i\*a\_{i-1} and a\_i=1-exp(-a\_{i-2}) so the D’Alembert ratio gives (1-exp(a\_i))/a\_i, then use continuity again + L’H, i’ll try that when i get home)

---

<div class="post-metadata">

**Author:** ![Kurt](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.grin.mw/kurt/32/3361_2.png) [@Kurt](https://forum.grin.mw/u/Kurt)\
**Post date:** [January 5, 2020, 4:57pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/19 "2020-01-05T16:57:28Z")

</div>

D’Alembert criterion will not work here as (1-exp(-a\_i))/a\_i converges to 1 😉 (no need l’Hospital to show that, just use Taylor order 1)

---

<div class="post-metadata">

**Author:** ![kbs1](https://avatars.discourse-cdn.com/v4/letter/k/cdc98d/32.png) [@kbs1](https://forum.grin.mw/u/kbs1)\
**Post date:** [January 8, 2020, 7:57am UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/20 "2020-01-08T07:57:12Z")

</div>

Does anyone know about a working AMD (RX580 8GB) cuckaroom29 miner implementation on Win 10?

---

<div class="post-metadata">

**Author:** ![Lolliedieb](https://avatars.discourse-cdn.com/v4/letter/l/e274bd/32.png) [@Lolliedieb](https://forum.grin.mw/u/Lolliedieb)\
**Post date:** [January 8, 2020, 2:11pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/21 "2020-01-08T14:11:21Z")

</div>

Well I got one 😉

But still on to improve it and ironing out last flaws here and there - but it already did run in testnet and will be published before the fork.

---

<div class="post-metadata">

**Author:** ![kbs1](https://avatars.discourse-cdn.com/v4/letter/k/cdc98d/32.png) [@kbs1](https://forum.grin.mw/u/kbs1)\
**Post date:** [January 8, 2020, 3:36pm UTC](https://forum.grin.mw/t/next-pow-cuckaroom-unveiled-at-grincon1/6605/22 "2020-01-08T15:36:34Z")

</div>

Great work, thank you! 🙂