Cuckatoo31+ (im)mutability

Announcements
1

Our primary PoW of Cuckatoo31+ is intended to be mined by ASICs.

As such, it is important to have all rules regarding validity of cycles, validity and weighing of graph sizes, and allocation of block rewards, clearly set out, implemented, and immutable for the foreseeable future, so that ASIC manufacturers can feel confident to invest in ASIC development.

[20190625 UPDATE]: We concretize “foreseeable future” as 18 months. So we do NOT allow any primary PoW consensus changes that take effect in under 18 months.

The rules for cuckatoo validity are codified in C at

and in Rust at

The rules for phasing out smaller sizes are codified in ([20190625 UPDATE] NOTE that phase outs of C32 and beyond have been put on hold)

The rules for balancing block rewards, are codified in

And of course the supply is fixed at 1 Grin per second.

The Grin developers currently have no intention of changing these rules in the foreseeable future, unless Cuckatoo is shown to be broken (e.g. by exhibiting a sublinear time-memory tradeoff), or unless the phasing out of smaller sizes should be delayed in order to ensure public availability of >= 1 GPS miners.

9 Likes
2

This is awesome!

Definitely a silly question, but would time/memory tradeoffs in either direction merit a change to the rules? I.E. if an ASIC could employ double the memory to achieve a greater than 2x speedup.

3

I think you cannot get speedup from using k times more memory, since you’d presumably want to access most of it, and the current solvers already work in linear time.

5

Yeah, that makes sense, although I wouldn’t rule out some crazy design, perhaps that computes multiple solutions in parallel.

6

You can work on multiple graphs in parallel. But each graph need’s its own memory, and its own energy expenditure…

7

Wait wait hear me out on this, what if you generated a large number of graphs, you store it on cheap media like tape drives. Sort them using a metric that somehow put “similar” graphs next to each other, somehow you reuse a tiny amount of work if graphs look alike( and given the birthday pardox, you would only need the square root of the total possiblity space and as we know O() really likes sub linear inputs like that)

If you managed to reuse graph logic in such a way, you would only need to sort thru square root of 2^31 on tape drives which we all know a sort function is n log n, and therefore negligible.

You may need to slow down the network speed to enable this asic design for the start up time this system would need; but 1 minute was kinda fast anyway.

8

Are you talking about adapting Cuckatoo into Proof of Capacity, and being able to mine with HDD additionnaly to asics ?

9

This is the primary problem to solve in Cuckoo Cycle. Mean miner spends a lot of time scattering similar edges into buckets.

10

It would be nice if a hard disk filled with cuckatoo solutions, sorted by cyclehash, could be used as a Proof of Capacity. But I see no way to avoid grinding attacks:

11

/s

I called 2^15 graphs which are megabytes each negligible twice on filmsy logic.

Your not processing a fraction of a pentabyte in under minute or even an hour to save slightly in O()

12

Phaseouts of C32 and beyond have been put on hold, as per the proposal https://forum.grin.mw/t/grin-improvement-proposal-1-put-later-phase-outs-on-hold-and-rephrase-primary-pow-commitment that was accepted today.

1 Like