New PoW method using factorization of large numbers.

[ir.hn]

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 vulnerabilities that encryption algorithms are prone to.
(link is to wayback machine so you can trust visiting it)

https://web.archive.org/web/20180609233726/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 by themselves.

It appear this PoW would be the perfect marriage of GPU and CPU as a GPU seems to speed up the first part (the easiest part) of the factorization:
http://www.mersenneforum.org/showthread.php?t=19312

[1714960863]

1714960863

[1714960863]

1714960863

[shensu]

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 like 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).

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

Are you the author?

[ir.hn]

yep.  Let me know what you think.  The first person to submit a factor that meets the requirements would be the winner of the block.  Very similar to how the system currently works but a bit cleaner and slanted towards cpu.  Also any factoring or sieving methods can be used so design of the miner software will be very important.  The network should be even faster than bitcoin too because verification of the factor is extremely easy and faster than verification of a nonce.

[ir.hn]

https://www.wired.com/story/bitcoin-global-warming/

Interesting article.

[achow101]

Here is a whitepaper

It's not a whitepaper, it's a blog post.

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

What about ASICs? This does not look like a problem that would be very hard to design ASICs for and just skip over GPUs entirely.

[ir.hn]

Here is a whitepaper

It's not a whitepaper, it's a blog post.

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

What about ASICs? This does not look like a problem that would be very hard to design ASICs for and just skip over GPUs entirely.

Hehe call it what you like but I have written many open source inventions as "blog posts" since blogs are a great place to self publish.

But no factoring large numbers via sieving is something that is done commonly and there is lots of literature on it.  The most efficient thing is CPU's.  The best "ASIC" currently would probably be built using Intel X series I9 on a mini itx motherboard with very little ram.

[ir.hn]

Interestingly searching google for 'number factoring asic's' lead me to the following post from 2014 which is basically exactly my idea I just take it a step farther and say the number can be so big that only one factor of sufficient size needs to be found to win the block.

https://bitcointalk.org/index.php?topic=783110.0

But ya I only saw papers of theoretical asic's for large number factoring, nothing that has been realized in real life.  And even such an asic to accomplish number sieving factoring would be so complicated and big that it probably wouldn't be financially efficient to build; ie: for the same price you could probably build a better cpu farm.

http://www.hyperelliptic.org/tanja/SHARCS/talks/shark_paper.pdf

More info about state of the art NFS sieving
http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html

It appear this PoW would be the perfect marriage of GPU and CPU as a GPU seems to speed up the first part (the easiest part) of the factorization:
http://www.mersenneforum.org/showthread.php?t=19312

[Taras]

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.

If you can generate a big number to work with, say from the block header, the miner can just regenerate the number by changing one byte of the generation transaction. If a miner can somehow prove that the number is prime, or cannot possibly have desirable factors, they can skip to the next one without waiting.

Also, if the product is dependent on the block header, which contains the merkle root, you don't have to worry about other miners stealing your solution, because the resultant factor is for a product that is dependent on the generation transaction paying you.

The other day I was thinking about the possibility of using a PoW coin to find Taxicab numbers, of which only the first 6 have been found in all of human history. You could theoretically make proof-of-work out of finding Ta(7), where a block is a near-miss (that is, a bigger version of Ta(6)), but it would be harder to turn into a difficulty-adjustable system than dividing huge numbers until you get a whole number of length n.

[ir.hn]

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.

If you can generate a big number to work with, say from the block header, the miner can just regenerate the number by changing one byte of the generation transaction. If a miner can somehow prove that the number is prime, or cannot possibly have desirable factors, they can skip to the next one without waiting.

Ya sounds good.  This incentivizes developing unique mining methods.

Also, if the product is dependent on the block header, which contains the merkle root, you don't have to worry about other miners stealing your solution, because the resultant factor is for a product that is dependent on the generation transaction paying you.

Not sure I am following you.  The generated number should be the same for everyone, the only difference is if someone can figure out the number is not going to work he can skip ahead to the next one because everyone else would eventually have to do the same.  In this situation of a stalled out time limit, the next number would be the same for everyone too and based on the last block number and last block factor and say +1.  Someone can make their miner skip ahead and work on the next number automatically and just wait 15 minutes then propose it as a solution if he wants and be almost guarenteed to win the block.  The risk though is if a solution is found for the last block within the time limit his 'skip ahead' solution is not for the next block so he wasted his time.  This is good because it guarentees the blocktime is no longer than 15 minutes.

The other day I was thinking about the possibility of using a PoW coin to find Taxicab numbers, of which only the first 6 have been found in all of human history. You could theoretically make proof-of-work out of finding Ta(7), where a block is a near-miss (that is, a bigger version of Ta(6)), but it would be harder to turn into a difficulty-adjustable system than dividing huge numbers until you get a whole number of length n.

Right on.  Well a method for pow could be designed to give possible taxicab numbers that can be further investigated later perhaps.  Like my method's side effect would be generating a list of possible large prime numbers.  But I say we focus on my idea for now and get it working in a coin then work on how we can design a pow to provide a list of possible taxicab's or other types like mersenne's.  However it is all about finding prime numbers to use in cryptography and taxicab's and mersennes are just kind of intellectually curious types so I think my idea is more basic and useful.

[Taras]

Also, if the product is dependent on the block header, which contains the merkle root, you don't have to worry about other miners stealing your solution, because the resultant factor is for a product that is dependent on the generation transaction paying you.

Not sure I am following you.  The generated number should be the same for everyone, the only difference is if someone can figure out the number is not going to work he can skip ahead to the next one because everyone else would eventually have to do the same.  In this situation of a stalled out time limit, the next number would be the same for everyone too and based on the last block number and last block factor and say +1.  Someone can make their miner skip ahead and work on the next number automatically and just wait 15 minutes then propose it as a solution if he wants and be almost guarenteed to win the block.  The risk though is if a solution is found for the last block within the time limit his 'skip ahead' solution is not for the next block so he wasted his time.  This is good because it guarentees the blocktime is no longer than 15 minutes.

If the generated number is the same for everyone, then if miner A broadcasts a solution, what is stopping miner B from just stealing that solution and broadcasting it as their own, and stealing the block reward? What if every node on the network wants to steal solutions?

[ir.hn]

Also, if the product is dependent on the block header, which contains the merkle root, you don't have to worry about other miners stealing your solution, because the resultant factor is for a product that is dependent on the generation transaction paying you.

Not sure I am following you.  The generated number should be the same for everyone, the only difference is if someone can figure out the number is not going to work he can skip ahead to the next one because everyone else would eventually have to do the same.  In this situation of a stalled out time limit, the next number would be the same for everyone too and based on the last block number and last block factor and say +1.  Someone can make their miner skip ahead and work on the next number automatically and just wait 15 minutes then propose it as a solution if he wants and be almost guarenteed to win the block.  The risk though is if a solution is found for the last block within the time limit his 'skip ahead' solution is not for the next block so he wasted his time.  This is good because it guarentees the blocktime is no longer than 15 minutes.

If the generated number is the same for everyone, then if miner A broadcasts a solution, what is stopping miner B from just stealing that solution and broadcasting it as their own, and stealing the block reward? What if every node on the network wants to steal solutions?

The generated number is the same for everyone now in the bitcoin network.  As far as I l know currently everyone is working on cracking the same hash.  So if that were a problem then it would be a problem now.  I agree with you though that it seems like that attack could happen.

[Taras]

Also, if the product is dependent on the block header, which contains the merkle root, you don't have to worry about other miners stealing your solution, because the resultant factor is for a product that is dependent on the generation transaction paying you.

Not sure I am following you.  The generated number should be the same for everyone, the only difference is if someone can figure out the number is not going to work he can skip ahead to the next one because everyone else would eventually have to do the same.  In this situation of a stalled out time limit, the next number would be the same for everyone too and based on the last block number and last block factor and say +1.  Someone can make their miner skip ahead and work on the next number automatically and just wait 15 minutes then propose it as a solution if he wants and be almost guarenteed to win the block.  The risk though is if a solution is found for the last block within the time limit his 'skip ahead' solution is not for the next block so he wasted his time.  This is good because it guarentees the blocktime is no longer than 15 minutes.

If the generated number is the same for everyone, then if miner A broadcasts a solution, what is stopping miner B from just stealing that solution and broadcasting it as their own, and stealing the block reward? What if every node on the network wants to steal solutions?

The generated number is the same for everyone now in the bitcoin network.  As far as I l know currently everyone is working on cracking the same hash.  So if that were a problem then it would be a problem now.  I agree with you though that it seems like that attack could happen.

No, it's not. Every miner is hashing a different block header, each containing a different merkle root that has the generation transaction paying that miner exclusively. This attack is therefore impossible on bitcoin, but there's still nothing stopping it from happening with this project.

If it is important that every miner works on the same number (and it may actually be a requirement for Ta(7)), then a miner could submit a hash of their solution along with their address for payment, wait for everyone to get a copy, and then release the solution, along with the block. It would be a lot more difficult to steal a solution in that case. But it would be impossible if every miner worked on a different number, and that number was dependent on the miner's payout address (on which the generation transaction depends, which the merkle root depends on, which the block header depends on).

[ir.hn]

Also, if the product is dependent on the block header, which contains the merkle root, you don't have to worry about other miners stealing your solution, because the resultant factor is for a product that is dependent on the generation transaction paying you.

Not sure I am following you.  The generated number should be the same for everyone, the only difference is if someone can figure out the number is not going to work he can skip ahead to the next one because everyone else would eventually have to do the same.  In this situation of a stalled out time limit, the next number would be the same for everyone too and based on the last block number and last block factor and say +1.  Someone can make their miner skip ahead and work on the next number automatically and just wait 15 minutes then propose it as a solution if he wants and be almost guarenteed to win the block.  The risk though is if a solution is found for the last block within the time limit his 'skip ahead' solution is not for the next block so he wasted his time.  This is good because it guarentees the blocktime is no longer than 15 minutes.

If the generated number is the same for everyone, then if miner A broadcasts a solution, what is stopping miner B from just stealing that solution and broadcasting it as their own, and stealing the block reward? What if every node on the network wants to steal solutions?

The generated number is the same for everyone now in the bitcoin network.  As far as I l know currently everyone is working on cracking the same hash.  So if that were a problem then it would be a problem now.  I agree with you though that it seems like that attack could happen.

No, it's not. Every miner is hashing a different block header, each containing a different merkle root that has the generation transaction paying that miner exclusively. This attack is therefore impossible on bitcoin, but there's still nothing stopping it from happening with this project.

If it is important that every miner works on the same number (and it may actually be a requirement for Ta(7)), then a miner could submit a hash of their solution along with their address for payment, wait for everyone to get a copy, and then release the solution, along with the block. It would be a lot more difficult to steal a solution in that case. But it would be impossible if every miner worked on a different number, and that number was dependent on the miner's payout address (on which the generation transaction depends, which the merkle root depends on, which the block header depends on).

Thanks for explaining that, that was a gap in my understanding.  I think I am with you now and that makes sense that either of those two solutions you proposed should work; that everyone could work on a different number that is determined in part by their public key -  or that everyone works on the same number and encrypts their solution and later broadcasts their encryption key once "everyone" has received their solution.  I think working on different numbers would be more efficient - it sounds like the second solution would add in extra lag.

So there would be no block timeout.  Since everyone is working on a different number, if one person happened to be working on a prime and is destined to never find a factor, it doesn't matter because someone else surely was working on a composite number and will find a factor.

[haltingprobability]

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 an upper 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.

[ir.hn]

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.

[haltingprobability]

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. 

Can you prove an upper bound on parallelization? In other words, can you prove that the advantage of x working units as x->oo goes to zero? Empirical evidence about how hard people have found parallelization of factoring to be is just hand-waving.

[ir.hn]

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.  

Can you prove an upper bound on parallelization? In other words, can you prove that the advantage of x working units as x->oo goes to zero? Empirical evidence about how hard people have found parallelization of factoring to be is just hand-waving.

Once you prove that SHA-256 encryption can't be broken without using brute force.  You trying to draw this hard line of definitive proof shows that you don't have the wisdom to understand how the world works.

[Taras]

So there would be no block timeout.  Since everyone is working on a different number, if one person happened to be working on a prime and is destined to never find a factor, it doesn't matter because someone else surely was working on a composite number and will find a factor.

If a miner suspects that their number is prime, or does not have many (or any) factors of the required size, they can just update the timestamp in the block header and get a new number to try getting factors from. They even get a new number for changing which transactions they want to include in their block. So, there can be a block timeout of 15 minutes, where if it has been that long without a solution, automatically update the timestamp in the header. But that's probably something that was going to be done anyways, at a much faster interval than 15 minutes. However you still cannot guarantee a block is found in 15 minutes.

Bitcoin testnet guarantees a block is found every hour by making the difficulty reset to 1 on any block whose predecessor is at least an hour older than itself. But that's probably not something we would want to do with a real currency. The low probability of happening to have long times without any blocks is just something we all have to deal with in bitcoin.

[ir.hn]

So there would be no block timeout.  Since everyone is working on a different number, if one person happened to be working on a prime and is destined to never find a factor, it doesn't matter because someone else surely was working on a composite number and will find a factor.

If a miner suspects that their number is prime, or does not have many (or any) factors of the required size, they can just update the timestamp in the block header and get a new number to try getting factors from. They even get a new number for changing which transactions they want to include in their block. So, there can be a block timeout of 15 minutes, where if it has been that long without a solution, automatically update the timestamp in the header. But that's probably something that was going to be done anyways, at a much faster interval than 15 minutes. However you still cannot guarantee a block is found in 15 minutes.

Bitcoin testnet guarantees a block is found every hour by making the difficulty reset to 1 on any block whose predecessor is at least an hour older than itself. But that's probably not something we would want to do with a real currency. The low probability of happening to have long times without any blocks is just something we all have to deal with in bitcoin.

That sounds good to me.  Ya the probability, assuming a correctly set difficulty, of a block even bieng 5 minutes late is extremely low given the fact that everyone will be working on different numbers.  I wonder if anyone has analyzed the data for bitcoin and made a normal distribution of how long blocks actually take.

This new understanding of the method would mean there is less ability, as a side effect, to classify numbers as possible primes, but at least we could have a list of large composite numbers which can be used to narrow down the search for primes.  Since even at very large numbers primes are not all that uncommon - one in a few thousand or so.  It isn't much, but it's better than nothing I guess.

Of course the main point of a new algorithm is to resist centralization of mining power but providing useful work is very attractive too.

[haltingprobability]

Can you prove an upper bound on parallelization? In other words, can you prove that the advantage of x working units as x->oo goes to zero? Empirical evidence about how hard people have found parallelization of factoring to be is just hand-waving.

Once you prove that SHA-256 encryption can't be broken without using brute force.  You trying to draw this hard line of definitive proof shows that you don't have the wisdom to understand how the world works.

You're shifting the goalposts. Your opening claim was that factorization does not benefit from GPUs (by which, I assume you mean parallelization). I nitpicked by pointing out that there's no reason to believe that factorization can't be sped up by parallelization. Claiming that factorization cannot benefit from parallelization is tantamount to claiming that there is no linear speedup for factorization. If this were true, it could be proved. There is no other way to know that it is the case than to prove it.