Discussion about proof of work changes

[Pttn]

There are already some discussion about that since a while, let's discuss here as well.

Basically, the main idea is to replace the current 6-tuple pattern by something that would allow bigger or more diverse patterns. Indeed, with the current choice will never allow blocks to be a part of a 7-tuple or more, which is really a shame and defeat a lot of the Riecoin's purpose.

If we go in this direction, a hard fork is obviously needed, and we could already do it for 0.16.4, or 0.18.x if we choose to upgrade before. Currently, many in the community are opposed to have a PoW that is GPU friendly so we should have something that is still GPU proof. The change could be simply to use another pattern (probably of length 4, 5 or 7) that is compatible with longer constellations. This would already improve the Riecoin's purpose a lot. We could also reward blocks with longer tuples (and get rid of the current SuperBlock system that confuses so many people with the 22.666... coins blocks) so miners have incentive to accept a slight loss of performance to configure the miner in order to find longer constellations.

There were also some (mainly ziiip) suggesting to improve the difficulty adjustment algorithm and make it much more dynamic and make the network more robust, we could do both to avoid having 2 hard forks.

[cryptapus]

Perhaps as a variation on Myriadcoin's multi-algo implementation, perhaps Riecoin could adopt a multi-length-tuple signaling in the blockheader version field. Essentially, each tuple length would have it's own independent difficulty. That way you can keep rewards the same per block since difficulty would govern rewards as intended.

concept ACK on dropping the superblock implementation, it's confusing and complicated.

concept ACK on faster difficulty adjustments.

[clo-prime]

My original idea was to allow 2 constellations and difficulties with 1 for CPUs and 1 for GPUs. There is some opposition to making things GPU friendly and it will be more difficult to implement so for now I think it makes sense to just change the constellation pattern. The best choices are probably 4 and 7. Current difficulties of around 1230 would correspond to roughly 3300 for 4-tuples and 700 for 7-tuples.

Choosing 4-tuples would allow us to break the 6-tuple record which is currently at 3445. Verification would take longer but would probably be manageable.

Choosing 7-tuples would probably allow us to break records from 8 or 9 to at least 10. 700 might be in the range of some GPU codes. This needs to be checked. It's possible there are some miner improvements that would raise the difficulty. If possible, it would be better to use 7-tuples because we could break more records and verification would be easier.

We should also keep in mind that not too long ago difficulties were almost 50% higher.

I really like the idea of rewards for finding larger constellations. This would encourage miners to sieve for larger constellations which will make them much more likely to be found. It would also add some excitement to mining. I think the reward would have to be paid out in the following block since the miner won't know ahead of time if a larger constellation will be found. I think this is possible.

There haven't been many issues with difficulty but it should be easy to change the difficulty adjustment algorithm and would make things more robust. ziiip recommended an algorithm which was roughly a 144 block moving average.

[cryptapus]

concept ACK on higher tuples.

unsure on lower tuples, anything that makes validation more costly, especially initial sync validation are going to be a problem going forward.

We could increase blocktime and rewards drastically for longer blocks, higher difficulties, lower validation costs (less blocks in the same amount of time), correct? I'm not sure if there is support for that, but might that give a high likelihood to hit more interesting records?

[Pttn]

I think that the transaction processing should remain fast, 2.5 minutes is a good choice. Finding more tuples also means more chances to find longer tuples.

Agree that for the long term, 7-tuples are much better. Not sure how we could manage Difficulties of 5000+ or even 10000+ later... Looks like it is the way to go, even though rieMiner would likely need improvements. I can mine 7-tuples at ~800 as hard as the current Difficulties by increasing the Primorial Number so we might also already need to update the way the solution is encoded.

Rockhawk suggested:

One change that would be nice and would make a small boost to the number size that could be found would be to change the way that the prime is encoded to allow a larger primorial number to be used.

To explain, Riecoin primes must be of the form: P = 2^D + S.2^(D-265) + X where X < 2^(D-265). Additionally, X must be < 2^256 as only 256 bits may be submitted for the proof of work.

In practice, the best way to choose X is to have it of the form: X = n# - (2^D + S*2^(D-9)) % n# + k.n# + x where # denotes the primorial operator (n# is the product of all primes <= n), x = q + (0, 4, 6, 10, 12, 16), with q normally = 16057 though the smallest prime in any small sextuplet will do.

The advantage of this form is that it guarantees that no primes <= n can be factors of P for any k. Sieving is then used to eliminate k with factors up to some limit and finally primality tests are used for candidates.

Choosing a larger n allows for faster sieving and a higher density of candidates across a given range of k, so allowing a larger n could provide a modest boost to the size of primes the network finds.

My suggestion would be to change the proof of work to consist of just k, n and q instead of the full representation of X, as it is easy to calculate X given k, n and q. This would allow X larger than 2^256, and hence larger n values to be used.

Suitable ranges for the values to give plenty of flexibility to the mining implementation would be k < 2^128, n < 2^16, q < 2^96, which would give 16 bits spare in a 256-bit submission, maybe to encode the tuple constellation.

Maybe a bit could be used to indicate whether the client was using this form or not, in case someone wants to continue using an older mining implementation. The bottom bit of the 256-bit submission would do for this, as it must always be 1 in the current implementation (if it is zero then P would be even). I'd suggest reserving another bit to indicate use of a different form in future too.

[Pttn]

Fork changes are now implemented in c8f815925cb2b0dff373a55bc283fe9874a6451c.

After the fork, 7-tuples will be mined instead of sextuplets. After thinking again about it, it would be better to let mining longer tuples be a voluntary choice not incentived by the block rewards. Someone that wants to mine longer tuples will still have fun doing so, and they should be rewarded not by the Riecoin protocol but rather by community donations and publicity. Also not all longer tuples will be records, and it makes less sense to reward many constellations that do not beat a record.

The RockHawk suggestion was implemented. More details about the implementation can be found here. 15 bits are reserved and could be used later to for new encodings or even new/additional PoWs.

The superblocks will be removed after the fork.

The difficulty adjustment algorithm will be replaced by one based on ASERT/EMA, recommended by Zawy12, a reference person in the domain. To enable small variations for a DAA that retargets every block, difficulties can now be fractional, with 1/256 precision (see the link about the PoW above). The implementation is very slightly imprecise, but it should not cause any issue in practice as rounding errors will just be compensated over time, and the simplicity of implementing this is a real advantage. More information on the DAA implementation in Riecoin.

In complement to the DAA change, the adjusted time system was removed and the actual time is used, a node will not connect to ones with more than 5 s offset, and the blocks will have to be within 15 s before the previous one or in the future. These should prevent any attack abusing the large DEFAULT_MAX_TIME_ADJUSTMENT and Timestamp Manipulations abusing the large MAX_FUTURE_BLOCK_TIME and Median Time Past. The only drawback of these changes is that every node are now required to have correct clock and timezone, but really, that is not a problem today and a very reasonable expectation, and most of the Riecoin nodes I connect to already have a 0 s or +/- 1 s time offset.