Grin's Cuckoo Implementation

[Edgecombe]

Grin's Cuckoo implementation uses an EDGEMASK that is half of the reference EDGEMASK for cuckoo cycle. This causes great weakness.

I wrote a solver to see how bad it was. I could not get my full solver up to 2^30 graph size, but at 2^13 graph size I was finding 200,000+ solutions per graph. This number was increasing as I increased the problem size. Drawing the line, I suspect the 2^30 graph size has more than 1 billion valid unique solutions in it. This means most of the time is spent on blake2b to validate the solutions in the best implementation.

The PoW for grin needs to be fixed. My recommendation is to remove the non-standard cuckoo-cycle changes - they appear to both be broken (I believe the easiness factor is also broken).

[tromp]

the mask is applied correctly. the number of nodes is 1<<sizeshift, and the number of edges is half of that. each edge has an odd and an even endpoint. the endpoints can be generated with this parity bit either explicit (as in cuckoo.rs) or implicit (as in my repo).

[tromp]

If you are finding 200k + solutions, then all but a handful should fail the verification check. Could there be another issue with your code?

[Edgecombe]

the mask is applied correctly. the number of nodes is 1<<sizeshift, and the number of edges is half of that.

https://github.com/mimblewimble/grin/blob/master/core/src/pow/cuckoo.rs#L58

size is (1 << sizeshift) = 30 bits

https://github.com/mimblewimble/grin/blob/master/core/src/pow/cuckoo.rs#L94

easiness is (ease * size / 100) ~= 29.6 bits for ease=75

https://github.com/mimblewimble/grin/blob/master/core/src/pow/cuckoo.rs#L99

number of edges is easiness ~= 29.6 bits for ease=75

https://github.com/mimblewimble/grin/blob/master/core/src/pow/cuckoo.rs#L69

mask is size / 2 - 1 = 29 bits

https://github.com/mimblewimble/grin/blob/master/core/src/pow/cuckoo.rs#L103

https://github.com/mimblewimble/grin/blob/master/core/src/pow/cuckoo.rs#L77

nodes can either be even, or odd. number of nodes = 30 bits.

the mask is applied correctly. the number of nodes is 1<<sizeshift, and the number of edges is half of that.

but number of edges is 29.6 bits, and number of nodes is 30 bits. For ease=100, the number of edges and number of nodes is the same, not half. This creates very many graphs, right?

[tromp]

ease should be fixed at 50% for all proof-of-work applications (indeed the number of cycles explodes as ease goes above 50%). edges must connect an even node to an odd node.

[Edgecombe]

ease should be fixed at 50% for all proof-of-work applications (indeed the number of cycles explodes as ease goes above 50%). edges must connect an even node to an odd node.

if easiness is to be fixed at 50%, why have easiness as a parameter at all?

and, why 50% for default? I assume 100% is the right value for default. if 50% is the right value though, then its not broken its okay.

[Edgecombe]

and, why 42 as a cycle size? according to paper, chance of cycle is 1/L - cycle of length 12 is still unlikely, blake2b still allows difficulty control, but proof size only 50 bytes. still high entropy

[tromp]

Easiness is potentially useful in non-PoW applications, like spam control or rate limiting, where a single solution attempt should have a large chance of success. 42 is a trade-off between proof size and risk of algorithmic shortcuts. it's more likely that some alternative algorithm can find 12 cycles more efficiently. the paper shows that time-memory trade-offs are more effective on shorter cycle lengths.