Grin

Cuckoo Cycle weakness and possible fix (Cuckatoo Cycle)


#1

The stated memory requirements based on 2-bit counters are incorrect, aince we only require counting up to 2.
So they’re really trits (ternary digits) requiring only log 3 bits.
An ASIC would pack 5 trits into a byte, with an atomic 2-bit update becoming an atomic 1-byte update.
cuckoo30 doesn’t need 128 MB for the counters, but only 4/5 times that, or 103 MB.

I consider this a weakness, and would prefer that an optimal ASIC design accesses single bits.

To that end I will later today propose a small change in the Cuckoo Cycle construction, that I hope everyone can agree makes Cuckoo Cycle even more ASIC friendly.


#2

Is that a good thing? I was under the impression that one of the initial purposes of Cuckoo Cycle was to be ASIC unfriendly.


#3

Originally Cuckoo Cycle was designed to make memory latency a bottleneck. Now, many years later, we realize that the SRAM that Cuckoo Cycle makes excellent use of (needing an order of magnitude less than the DRAM needed for efficient mining) is quite affordable in ASICs.
We expect ASICs to have a large efficiency advantage over GPUs.


#4

Here’s the change in construction that allows replacing 2-bit counters by single-bit counters:

Instead of adjacent edges sharing an endpoint in the Cuckoo Graph, we require the two endpoints to differ in the last bit only.

This is a minimal change in the verification function, we replace
line 66 of cuckoo.c

  if (uvs[k] == uvs[i]) { // find other edge endpoint identical to one at i

by

  if (uvs[k]>>1 == uvs[i]>>1) { // find other edge endpoint matching one at i

and line 72

if (j == i) return POW_DEAD_END;  // no matching endpoint

by

if (j == i || uvs[j] == uvs[i]) return POW_DEAD_END;  // no matching endpoint

We also need to replace line 52

node_t xor0 = 0, xor1  =0;

by

node_t xor0, xor1;
xor0 = xor1 = (PROOFSIZE/2) & 1;

to fix early detection of bogus solutions. This has no effect on the distribution of cycle lengths in random graphs; a random endpoint is as likely to match another as it is to differ in the last bit only.

With this change, lean mining only needs a node bitmap to record whether it has any edge adjacent to it.
An edge then survives if the bit for its endpoint^1 is set.

Thus, a graph with 2^n edges will require 2^n bits of SRAM for full speed. It makes more sense to use this n in the name of the PoW.

Let’s call this new version Cuckatoo Cycle.

 )/_
<' \
/)  )
/'-""

We will then denote by cuckatoo32 the problem with 2^32 edges
needing 2^32 bits of SRAM for full speed.
Compare with cuckoo32 that only has 2^31 edges but similarly needed 2^32 bits of SRAM (or 4/5 of that with trit packing).

So I propose that Grin uses cuckatoo32+ as main PoW instead of cuckoo32+.


#5

This seems to make a lot of sense to me, it’s a very minor change and simplifies the memory layout conceptually and practically. What would the impact be on the mean miner? Would that become the default Cuckoo also from your repository?


#6

Mean miner could use bigger buckets, since 48 KB of shared mem can now hold 2^18 counters instead of 2^17. That would be helpful for cuckoo31, since Nvidia apparently is much less efficient bucketing 2^13+ way than 2^12 way.
I haven’t decided how to deal with a pair of PoW in the repo yet.


#7

It turns out that the expected number of cycles of length L on a graph of 2^n edges is slightly different, but in the limit as n->infinity it still converges to 1/L.


#8

Originally Cuckoo Cycle was designed to make memory latency a bottleneck. Now, many years later, we realize that the SRAM that Cuckoo Cycle makes excellent use of (needing an order of magnitude less than the DRAM needed for efficient mining) is quite affordable in ASICs.
We expect ASICs to have a large efficiency advantage over GPUs.

I’m still unclear if this was a political shift or a “fuck it ship it” shift

I can understand the position from either a “each major coin should be asic friendly, but different with asics” or a “I guess my starting assumptions were wrong but now I’m an expert in something and some people like asics, sooooo whatever”