Next PoW CuckARooM unveiled at GrinCon1

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://www.grin-forum.org/t/mid-july-pow-hardfork-cuckaroo29-cuckarood29
[1] https://github.com/mimblewimble/grin-pm/blob/master/presentations/grincon1/10-cuckaroom-tromp.pdf
[2] https://www.youtube.com/playlist?list=PLvgCPbagiHgrQa5KVt4XixK9t_NbfpkuP
[3] https://github.com/tromp/cuckoo/tree/master/src/cuckaroom
[4] https://github.com/tromp/cuckoo/blob/master/src/cuckaroom/cuckaroom.hpp#L133-L164
[5] https://github.com/mimblewimble/grin/pull/3136
[6] https://github.com/mimblewimble/grin-miner/pull/231

14 Likes

Where do you get that?

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.

2 Likes

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 :slight_smile:

1 Like

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.

1 Like

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
1 Like

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