12.12.2017

New Proof of Work (POW) method based on factoring large numbers

The current state of the art in cryptocurrencies is using encryption algorithms to provide a target "hash".  Then the "nonce" (or key) needs to be found by brute force (trying every possible combination) in order to crack the hash and prove that you did work to gain coins and provide your version of the transaction history to the blockchain.

The problem with this is that vulnerabilities can be found in these encryption methods and not only that but the development of these algorithms are centralized, for example the NSA developed SHA-256 used in bitcoin and could theoretically know how to break it without brute force.  Not only this but the NSA already recommends against the continued use of SHA-256, no one knows the real reason why but my guess is that someone has been able to crack it and the NSA found out about it.  It can probably be cracked if given a few example hashes from a given nonce are known.  Also these encryption algorithms are almost always extremely parrallelizable, leading to specialized equipment like gpu's and asic's to be developed to hash very fast.  This practice is bad for cryptocurrency because this leads to central powers usually the ones who can develop such specialized hardware.  In cryptocurrency allowing everyone with a CPU to mine profitably helps ensure a distributed ownership of a coin and mke it less prone to pump and dumps or 51% attacks.

The point is we don't need encryption, we just need proof of work.  Mabye cryptocurrency was the wrong word.  Mabye a more general term like distributed digital currencies (DDC's), as opposed to centralized digital currencies, would be more ubiversally applicable.

We don't need cryptography for proof of work.  We can use prime numbers.  How do we do this?  That is the trillion dollar question.  Primecoin tried to use prime numbers but already it has been cracked by GPU's.  The interesting thing is that GPU's do poorly for large primes or large composite factoring because they aren't smart enough.  The problem is these large composite numbers take forever to prime factorize and thus doesn't seem like a good fit for a 10 minute blocktime or adjusting the difficulty easily.

The secret is we don't need a full prime factorization.  This realization came to me when reading this paper:
http://www.math.rwth-aachen.de/~Greg.Gamble/gap4r3/pkg/factint/htm/CHAP005.htm

We can just find one factor (or any desired number, and the factors need not necessarily be prime) that meets our difficulty requirements.  For example we could ask for any 18 digit factor of a 100 digit number.  On an old computer this takes 50 minutes according to the above paper.  We can increase the digit size of the factor we want and/or increase the number digit size in order to increase the difficulty.  We could ask for 2 factors or any number we desire.  These large numbers would require sieving which would put GPU's at a disadvantage.  In order to generate these large numbers in the first place for example we can (do the following or any other method or combination if methods) hash the factor (with any encryption method(s)) and whole number of the last block; and truncate according to the difficulty.  To make it even easier and not use encryption algorithms at all we could just multiply the last number by it's winning factor and truncate according to the difficulty to give us our next number to factor.

*Edit: the following paragraph was assuming everyone would be attempting the same number.  On bitcointalk.org forum someone (forgot who) suggested everyone work on a different number partly based on the hash of their public key.  I think this is a great idea and would solve the following issue. Also I should mention that the hash which is usually in capital letters, lowercase letters, and numbers can easily be converted into regular numbers for our 100ish digit numbers, its just a matter of converting a base 62 number into base 10.*

If a factor is not found in say 50% plus the blocktime (15 minutes or whatever is desired), then a new number generated (could just be the last number+1) because that previous number may be prime and not have any factors.  A side effect of this mining could give us a list of possible primes for further research.  So it isn't a worthless task.

This is a super clean method of PoW that will give the advantage to cpu's.  Also it can be combined with any other algorithms or methods to achieve any goals including making it even better for cpu's.  Another thing is in order to verify the factor is a winner all one needs to do is divide the number by the factor and see that it gives a whole number result.  This is extremely fast and would reduce the risk of hackers ddosing the network.  Also verify that the number(s) is indeed the amount of digits required.

No comments:

Post a Comment

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