11.21.2017

Prime factorization of the Nonce: a new way to increase difficulty of ASIC and GPU mining.

Limiting cryptocurrency mining to CPU is a difficult task.  GPU's and ASIC's can be made to make the task faster but this centralizes mining and makes average Joe unable to compete using his regular CPU.  If we can make the mining only accessible to CPU or at least make CPU competitive to mine then we achieve much better distribution of power in the cryptocurrency.  Also it is more beneficial for society to have excess cheap used PC's retired from mining for the poor to buy.

The "header" is what determines what the "nonce" - the key to winning a block - has to be.  The header of a block is composed of functions that hash the nonce into a random value.  The only way to crack the code is to try every possible nonce value until you find the one that works.  When you do, it is easy for other miners to verify that you found the right one and you won the block and get the reward.

Bitcoin uses SHA256 to hash the 32 bit random nonce into a big random number.

The following idea can be used alone or in conjunction with other methods.  It can be used with or without any hashing algorithm or function or combination of algorithms or functions.

My proposal is to require that the nonce be reported as a product of prime factors.  This would add virtually zero time into verifying that the nonce was correct (multiplying a few numbers together to create the nonce would take virtually no time at all). This means that not only does the nonce need to be found, but that it needs to be factored.  This factoring would help promote the abilities of a CPU.  Also the nonce must be chosen not only to create the correct hash difficulty, but also to not be prime (since then it would have no factors, and thus just saying it is prime does not lend to validation like a list of prime factors would).  This is not a strict requirement but I believe not alowing nonces to be prime would be beneficial.  We could also even say that nonces cannot be prime squares if we want which may improve the speed of verifying correct nonces and also increasing the dataset size required to check against disallowed nonces.  If more restrictions are desired then even perfect squares could be disallowed as nonces and/or any other testable requirement.  Since the nonce is typically 32 bit, a list of prime factors can be made so that the miner, after generating a nonce, checks it with the prime list to make sure it isn't prime.  If it is on the list the miner needs to create a new nonce.  This prime list contains about 200 million values and takes up roughly 800 mb of space.  This is also important since each miner would need to use about 1 gb of ram just to store the dataset to check to make sure a generated nonce is valid.  The list could also be used to speed up the process of sieving which nonces to check during mining since you can save time by eliminating primes from being checked.  Also the list would be used to check if the list of prime nonce factors proposed by another miner are indeed prime numbers.  If they are then they would be multiplied together to give the nonce and then that nonce checked to see if it gives the correct hash.

This also would help even the playing field giving normal computers an edge or at least a fighting chance against low memory GPU's or ASIC's.

1 comment:

  1. I would add that, even if someone builds a factorization ASIC, such hardware acceleration would likely quickly be integrated on-chip to general purpose CPU's so that such chips can do public key cryptography securely against the new threat of ASIC attacks.

    ReplyDelete

Thank you for your feedback! Sharing your experience and thoughts not only helps other customers but also helps me to improve what I do!