A Holy Grail PoW for Monero outlined (GNFS)

Support NatureHacker by getting Free Organic Teef Powder!

This is a repost from reddit, see it here with the comments:

https://www.reddit.com/r/Monero/comments/grms1c/a_holy_grail_pow_for_monero_outlined_gnfs/

**EDIT: Quantum computing calculations have been updated and are now correct. Also at the bottom points #2 and #3 have been made to address concerns that the largest mining pool would always win since there is much less random luck in getting proper factors as opposed to current finding the nonce of the hash...meaning that cooperation in this idea would increase the speed of finding the block above that of simple competition. Currently in cryptocurrencies competition is just as fast as cooperation (at least so we think).**

Some of you may be afraid of Quantum Computers being an ASIC on CPU mining. This post isn't about this topic but I will address it first.

The Monero blockchain can currently factor a 745 bit number in 2 minutes (approx).

According to this post a 745 bit number needs 1492 (2n+2) clean logical qubits (which are very hard to achieve, each qubit is exponentially harder to add than the last) and would take around 2 trillion T gates. Looking at the history of quantum computers, this is probably decades off imo, quantum computers can only run for a few microseconds currently as well. By the time we get there the monero blockchain can probably beat it. A million or so noisy qubits might be more practical and also at least decades off of course.

Here is what I believe to be the Holy Grail to Mining and also I will present some alternatives to this which will have a more precisely adjustable difficulty but I don't think that is needed.

Factoring a large number over 100 digits is well known to not benefit significantly from parallelization such as GPU's, FPGA's, and ASIC's. As I explained above, quantum computers are also out of the running for the foreseeable future. The cool thing about this is that there can be moderate speedup by piggybacking a GPU and CPU since the GPU can support the General Number Field Sieve (GNFS) function of the CPU. This is extra beneficial since consumer hardware always has at least one of each but specialized chips, including IoT device botnets do not.

To implement this in Monero we would start with roughly 745 bits which is 225 decimal digits which would currently take about 1.9 minutes on the monero blockchain. If we bumped that up to 226 digits or 748 bits, this would take around 2.1 minutes. So I think this method is just fine in how precise difficulty adjustment will be by just changing the number of digits we are factoring. If we wanted more precision we could try to factor numbers in binary which would give about 5x more precision on difficulty adjustments. I will outline an even more precise possibility at the end of this post.

So the idea is this. We present a 225 digit (adjustable) number to the monero blockchain. The first person (miner) to present the prime factorization of that number wins the block. It is just about that simple. In order to prevent really fast blocks for numbers that happened to be prime or near prime, we can require that any answer to win a block must not contain any factors larger than 113 digits (225/2). This requirement just means that no "really easy" to factor numbers slip in. If an answer is presented to the blockchain that contains prime factors larger than this limit, then a new number is hashed for everyone to work on (this is a point of potential abuse since if a miner finds that the factorization doesn't meet the requirements he could work on the next hash before releasing that info to the public. Somehow we would need to figure out how to prevent this (**EDIT point #2 at the bottom of this post addresses it**). To generate a number we can use Skein-1024 (or SHA-1024) and truncate to the amount of digits we need.

I think that is pretty much it.

PRO's:

Asic, Gpu, FPGA Safe and as Quantum resistant as you can hope for, I say we cross that quantum bridge when we get there.

Simple easy to understand basic concept that has proven itself over decades of research to favor CPU.

Even more favorable is 1 GPU + 1 CPU = 1 Vote which will help disincentivize botnets and crazy big CPU's and favor APU's which are the current consumer standard (or a enthusiast CPU plus an enthusiast GPU).

miner design will contain no surprises since GNFS programs have been written for decades both for CPU and CPU/GPU combo

CON's:

Very different from what we are used to which are cryptographic hashing functions.

Mining software would have to be developed, as well as the code of the PoW will need to be written from scratch.

Difficulty adjustment will be not quite so easy or precise and will require new difficulty adjustment algorithms.

Let me know your input on this idea and if you agree it could be a PoW that lasts monero decades instead of months.

-----

1. To get even more difficulty adjustability we could use larger numbers and just require one or more factors to be presented, not prime factors. So say we ask for one 113 digit long factor of a 300 digit number. The length of the number and the length of the factor required can be both adjusted. Also the number of factors could be changed too. So to raise difficulty of this very slightly we could require both a 100 digit factor and a 113 digit long factor of a 300 digit number. since we aren't looking for prime factors in this version, almost every number will have at least one potential factor of these sizes. But still this version should need GNFS sieve and trial division would take much much much longer.

2. Another possibility is releasing 10 or more numbers at a time and as soon as any single number gets factored, then all 10 expire and the block is won. This will allow mining groups to "audit" the numbers and select one that will complete the requirements (no factors larger than 1/2 of the bit number size). Also there is more random chance that one number of the bunch could be factored faster negating the "largest mining pool always wins" issue brought up in the comments by sech1.

3. Another option is turning the coin code into one large pool that delegates sub-tasks to individual pools or miners. This would also be a method to address the concerns brought up by sech1.

Potential starts for mining software:

https://web.archive.org/web/20180320172551/http://gilchrist.ca/jeff/factoring/index.html

https://sourceforge.net/projects/msieve/files/?source=navbar

https://mersenneforum.org/showpost.php?p=294403&postcount=13