Next PoW CuckARooM unveiled at GrinCon1

tromp · November 24, 2019, 9:21pm

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:

the underlying hash function, currently siphash-2-4
the computation of endpoints of a whole block of edges
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
[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

tromp · November 25, 2019, 2:31pm

Where do you get that?

Lolliedieb · November 25, 2019, 3:36pm

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.

Lolliedieb · November 26, 2019, 8:12am

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

tromp · November 26, 2019, 8:41am

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.

Kurt · November 27, 2019, 4:05am

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

Gandalf1 · December 13, 2019, 3:27pm

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

slate · January 5, 2020, 3:18pm

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.

Kurt · January 5, 2020, 3:35pm

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

slate · January 5, 2020, 4:05pm

I only offered a proof of the 0 limit for a_n and b_n. The limit of a_n*b_n is different

Kurt · January 5, 2020, 4:16pm

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.

slate · January 5, 2020, 4:22pm

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?

Kurt · January 5, 2020, 4:25pm

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

slate · January 5, 2020, 4:27pm

Ah, yes, I missed the “cumulative” heading

slate · January 5, 2020, 4:50pm

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)

Kurt · January 5, 2020, 4:57pm

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)

kbs1 · January 8, 2020, 7:57am

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

Lolliedieb · January 8, 2020, 2:11pm

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.

kbs1 · January 8, 2020, 3:36pm

Great work, thank you!

Topic		Replies	Views
Introducing the final tweak: CuckARooZ Mining	6	6024	May 20, 2020
mid-July PoW hardfork: Cuckaroo29 -> Cuckarood29 Mining	12	5179	July 18, 2019
Choice of ASIC Resistant PoW for GPU miners Mining	110	15006	February 23, 2019
Critical PoW vulnerability closed; the accidental birth of a new PoW Mining	6	1245	July 27, 2020
I don't understand	1	692	December 27, 2019

Next PoW CuckARooM unveiled at GrinCon1

Related Topics