(copied from the mimblewimble mailing list)
A few days ago I wondered if grin could accept not only cuckoo30
solutions, but cycles in larger graphs as well. A cuckoo31 graph for
instance has twice as many nodes, and takes about twice as much effort
to search. But scaling the difficulty only by half provides little
incentive to work on larger graphs, since the longer runtime also
hurts progress freeness.
There is however a natural difficulty scaling factor that provides
proper incentives. Recall that a cycle passes the difficulty test if
the 64 most significant bits of the cyclehash are below a difficulty
target.
With graph size scaling, we first divide this 64 bit number by
2^(N-M)*(N-1), where M is the minimum allowed value of N.
This is the number of siphash output bits that define the cuckoo graph.
It also matches the amount of work performed by a radix sorting based solver.
As a result, a cuckoo34 solution is valued 8.8 times more than a
cuckoo31 solution; a 10% bonus on top of the node ratio.
So I propose to just set a minimum value, e.g. N >= 30, and allow
simultaneous mining by cuckoo30, cuckoo31, … , cuckoo64.
To increase the memory requirements, i.e. to upgrade the PoW,
we need only increment M, which is a mere soft fork!
(EDIT: For this to be a soft-fork the scaling factor above cannot contain M. It should instead just be the starting value of M, like 30).
We’ll probably never see cuckoo64 solutions, since it would require Petabytes of memory to solve (and take close to forever), but I’m looking forward to a cuckoo42 cycle some day.
Miner manufacturers are incentivized to produce hardware for larger
graphs, both because of the bonus in cycle valuation, and to make the
miner more future proof against PoW upgrades.
The large and growing memory requirements aim to deter single-chip
ASICs in favor of simpler memory-controller like ASICs that connect
commodity memory chips together. Such ASICs only need to run efficient
enough to saturate the limited memory bandwidth/latency. With power
consumption and cost dominated by that of the memory chips, and the
roles of ASIC design skills and fab access diminished, miner
manufacturers can hopefully compete on more equal terms.
Thanks to Igno and other grin devs for discussions on this proposal.
regards,
-John