mid-July PoW hardfork: Cuckaroo29 -> Cuckarood29

A major part of what makes our secondary PoW of Cuckaroo29 ASIC-resistant is frequent tweaking. The first such tweak is due 6 months after genesis, in mid July. Which is now only about 6 weeks away.

In the 133 days of Grin mining so far, there is no sign of any ASIC mining. We do know of several ASIC products planned to come out in Summer.
To the extent that any such ASICs have built in support for Cuckaroo29, we want our tweak to brick that support.

There are 3 separate 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

I’ve chosen to leave 2) entirely alone and make tweaks in 1) and 3).

The tweaked siphash is defined by templating on one of the rotation amounts:

template <int rotE = 21>
class siphash_state {
...
  void sip_round() {
    v0 += v1; v2 += v3; v1 = rotl(v1,13);
    v3 = rotl(v3,16); v1 ^= v0; v3 ^= v2;
    v0 = rotl(v0,32); v2 += v1; v0 += v3;
    v1 = rotl(v1,17);   v3 = rotl(v3,rotE);
    v1 ^= v2; v3 ^= v0; v2 = rotl(v2,32);
  }

and using siphash_state<25> in cuckarood rather than the default 21.

The new type of cycle is a directed one. Half the edges (those with even index) are directed from U to V and the other half (with odd index) is directed from V back to U. Alternatively, we can just say that the cycle must alternate between even-indexed and odd-indexed edges. At the same time the number of nodes in each of U and V is halved. So Cuckarood29 will have 2^28 U-nodes + 2^28 V-nodes, 2^28 U->V edges, and 2^28 V->U edges.

Curiously, this results in twice the expected number of cycles.
We will not be making any difficulty adjustments. That means that if half the current Cuckaroo29 miners fails to upgrade, then the secondary PoW solution rate will remain unchanged. If everyone upgrades in time, then average block time could drop to 36 seconds, but ar_scale will adjust downward to compensate and things will normalize in a few hours.

About the name: the appended ‘d’ mostly stands for directed, but as in SHA256d could also denote a doubling (of solutions).

Implementation wise, there is a new cuckarood directory at https://github.com/tromp/cuckoo/tree/master/src/cuckarood

In there you can find the new verifier in cuckarood.hpp and both a simple CPU miner and a CUDA mean miner.

A Grin PR is available at

7 Likes

I just want to suggest we maybe call the AR variations something simpler like CUCKAROO29A/B/C instead of a whole new name. We already have a pretty clever (and a a little complicated) nomenclature and I don’t think we need any more variations on base naming conventions.

It’s not a whole new name. It’s Cuckaroo[a-z]29 where the extra letter somewhat describes the nature of the tweak.
Furthermore, since the tweaks are not size specific, I chose to put the size after the tweak indicator.
In other words, Cuckarood is a uniform familiy of PoWs ranging from Cuckarood6 through Cuckarood32, and you may want to refer to this family by name without referring to a specific size.

So in six months it will likely be CuckarooE29?

Maybe it could skip to Cuckaroof?

Just a warning to all letters of the alphabet (except ‘d’):

any of you could be next!

1 Like

It remains only to regret all those who have made an advance payment for the GRIN ASIC miners…

The ASICs are for cuckatoo which remains unchanged.

1 Like

Why don’t you just call every algorithm TROMP (in captial letters), just TROMP, and say things like, “It’s a big, beautiful algorithm. Best, safest algorithm ever. No one build a better algorithm than me! And Vitalik Buterin’s going to pay for it!” I think that would be more winning.

Well I think you should go in order at least. All I’m saying.