Quote from: haltingprobability on December 17, 2017, 08:15:44 PM

Quote from: ir.hn on December 12, 2017, 11:03:16 PM

Here is a whitepaper about how to define a new proof of work system that gives preference to CPU's forever theoretically and is immune to velnerabilities that encryption algorithms are prone to.
(link is to wayback machine so you can trust visiting it)

https://web.archive.org/web/20171212224738/http://www.naturehackerproducts.com/2017/12/new-proof-of-work-pow-method-based-on.html?m=1

The take home message is to find a single factor (of a length defined by the difficulty) of a very large number (over 100 digits).

Since it is such a large number GPU's become very slow at attempting it.

I have a quibble with your "GPU-resistant" claims. We don't know that factorization cannot be efficiently randomized. If it can, it can also be trivially parallelized by randomly dividing the search space and sending each range to a different processing unit. In short, you can't claim a lower bound on parallelization without formal proof. Even if no one knows how to parallelize factorization (is this the case?), it doesn't prove that factorization can't be parallelized.

IMO, the effort expended on trying to democratize mining is wasted. Centralization of mining will always occur. Even factors like bandwidth and network latency are favored by centralized mining. Differences in electricity costs and so on only amplify this effect.

But there is no reason that the effort spent solving PoW puzzles has to be useless. Any problem in NP (including factoring) is a potential candidate and I recommend Circuit-SAT as an ideal candidate for PoW puzzles. Using this approach has the benefit that any real-world problem can be encoded as a circuit and then submitted for solution by the mining network.

When you learn more about factorization you will discover that for factoring numbers of 100 digits or more the best way to narrow down the options to use trial factoring on is by using a process called GNFS sieving. This process simply cannot be efficiently done on graphics cards. Graphics cards can help with the process (step 1) but the longest part is step 2 so CPU's have had an overall advantage. Ideally GPU would be used in tandem with a CPU... which just so happens to be a GREAT way to block botnets or server farms and give the advantage to personal computers.

This is a well known state of affairs as these problems have been done for decades and people have been working for years on making CUDA variants of the software to do it.

To give you a counter example to your proposal that my "GPU resistant" claim needs to be definitively proven, SHA-256 has never been definitively proven to not be crackable without brute force yet we still use it. Experience has taught us that it is secure and experience has show us that factoring very large numbers cannot be efficiently randomized.

Mining will always tend towards centralization but if we can very much disincentivize using GPU or ASIC or server farm or botnet then it will be decentralized for longer. I never claim an infinite utopia, the constitution in America only lasted 200 years before it broke down and if this next coin can last 100 years before centralizing I will consider it a success.