Topic: New PoW method using factorization of large numbers. - page 3. (Read 916 times)

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.

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.

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

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.

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?

Ya sounds good.  This incentivizes developing unique mining methods.



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.

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.

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.

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://bitcointalksearch.org/topic/asic-resistant-proof-of-work-783110

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

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.

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

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.

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

Interesting article.

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.

Are you the author?

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