20220517, 14:09  #1 
Feb 2022
2^{4}·3 Posts 
Integer Factorization as PoW in a Blockchain
Has anyone thought about creating a blockchain with integer factorization as Proof of Work? Perhaps factoring strong semiprimes to solve blocks? And perhaps adding a deadpool feature where people could submit integers to be factored and assign an award in coins of the blockchain?
Although, submitting a solution for any number in the deadpool would be open to miners just stealing the answer and claiming the rewards for themselves. So, a secure mechanism to submit the answer to the deadpool would have to be created. Any thoughts? Thanks! N 
20220517, 14:14  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·3·1,093 Posts 
Who generates the numbers? If they are truly created provably at random via some algorithm, then you couldn't ensure the "hardness" of the factoring effort. If they are created by "someone" (who?) then how can you trust them not to favour their buddies by passing on the factors?

20220517, 14:27  #3 
Feb 2022
60_{8} Posts 
True, but suppose for a moment that was a solved problem. Which, granted, it is not. Would such a blockchain be of interest to this community?

20220517, 14:57  #4 
Feb 2022
2^{4}·3 Posts 
@retina, the problem as you describe it is actually not easily solvable by any methods I know of. Even Elliptive Curve stuff, there are some papers on that. It seems the factors must be known in advance no matter what. So,
How do you pick the number to factor, predictably and with 100% confidence that the factors weren't know a priori? You don't. You make this problem the PoW in such a way that factoring is the computationally cheapest way to find them and reward miners for finding them. You only admit strong semiprimes as the solution for a block. You hash the block header to get pseudorandom bits to generate a candidate to solve a block. You factor it, and if the two factors have the exact same bitsize and are both primes you admit it to the blockchain. If not, you must keep generating new candidates and factoring them until you get a strong semiprime. See gHash for how the new numbers are generated. See CheckProofofWork to see how new block are validated. For every gHash candidate, you are allowed to search for semiprimes up to a distance of 16*nBits around that candidate. So for example, if your blockchain is at a level of difficulty of 250 bits and gHash generates the number W of 250 bits then you are allowed to search for a strong semiprime in [ W  16*250, W + 16*250] by factoring until you find a strong semiprime. If you do not find one, choose a different nonce and generate a new W and try again. What do you do if it's prime (how do you verify that it's prime)? You use MillerRabin primality testing with 50 rounds, giving you a 2^(200) probability of a false positive and being fast enough so that verification is not time consuming. 50 because that is the higher end the GNUGMP library recommends. Additionaly, you also perform the BailliePSW Primality test. Last fiddled with by factorn on 20220517 at 15:21 Reason: Fix spacing and probability that was missing the exponent part. Explain a little more and add links to code. 
20220517, 15:20  #5 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2×3×1,093 Posts 
Okay, I suppose that could be workable.
Get some bits from the previous block. Users generate new bits randomly. Mash them together with SHA or something. See if the result is a semiprime of the required character. 
20220517, 15:24  #6 
Feb 2022
30_{16} Posts 
The whitepaper will be out next week. I figure I would ask here about this since folks care about factoring here. I still haven't figured out the deadpool stuff yet. Would be nice to get some ideas to implement it safely. Any ideas to improve things would be greatly appreciated if anyone has thought about this for a bit.

20220517, 16:18  #7 
"Curtis"
Feb 2005
Riverside, CA
5372_{10} Posts 
What problem does this idea solve that isn't solved by an existing blockchain? Why is this better, from a crypto standpoint?
How would you make the numbers to be factored of any interest whatsoever mathematically? That is, how could this help the forum community? I don't click on posted links in general, but the post seems like "we put the words factoring and blockchain together. Cool, huh?" 
20220517, 16:50  #8  
Feb 2022
2^{4}×3 Posts 
Hi VBCurtis,
Happy to see you here! What problem does this idea solve that isn't solved by an existing blockchain? Perhaps "solve" is a strong term, but to the extent that it applies, hashing is not an area of as much interest in terms of research as factoring is. The only improvements that can be done for hashing SHA2/SCRYPT/etc are implementation improvements in hardware ASICS whereas in factoring we have been finding both better theoretical and implementation improvements since the 1600's with Fermat's difference of square observation. And, we still don't know if factoring is in P or NP. See the CADONFS and YAFU for just two examples of continuous improvements on theoretical and implementation grounds over the past two decades or so. In this blockchain, if you want to "beat the other miners" it is not enough to invest in good hardware, you have to invest in mathematical research as well. A new algorithm on a cheap computer might mine faster than what is known today on a massive cluster. Why is this better, from a crypto standpoint? Because it encourages research in an area of crypto upon which the RSA system is based. A cryptographic system that is widely used today. Also, factoring is such a hard problem that RSA is based on it. Imagine this blockchain as the 21st century RSA Challenge that the RSA Labs put out in 1991 and ended in 2007 where they paid tens of thousands of dollars just for factoring, only now the financial incentive is provided by blockchain technology. How would you make the numbers to be factored of any interest whatsoever mathematically? I don't. The interesting feature of the blockchain in this regard is the deadpool feature where folks can incentivize folks to factor numbers of interest by rewarding them with coins to do so. For example, take the thread at https://www.mersenneforum.org/showthread.php?t=27511 and look at retina's response: Quote:
That is, how could this help the forum community? I think the points above address this. If not, clarify the question and I would be happy to address it. I don't click on posted links in general, but the post seems like "we put the words factoring and blockchain together. Cool, huh?" The blockchain is FACT0RN. With a zero, not the letter O. You can find it on github at FACT0RN/FACT0RN. ~N Last fiddled with by factorn on 20220517 at 16:51 Reason: Fix Spacing. 

20220517, 20:09  #9 
Feb 2022
2^{4}·3 Posts 
A few corrections and clarifications are in order:
First, 1. Most PoW schemes use computing hashes forward as the PoW. Not breaking them. 2. FACT0RN uses "breaking" strong semiprimes as the PoW. Not computing them. When I say "hashing is not an area of as much interest in terms of research as factoring is" I mean it in this way. Hashing is very active area of research; but computing SHA2 forward, as is done in bitcoin, is not. Whereas factoring ever larger strong semiprimes, as is the PoW of FACT0RN, is an active area of research. Second, I misspoke when I wrote "And, we still don't know if factoring is in P or NP." I meant to say factoring is not known to be in P. I had to look up the definition of NP and immediately realized I had forgotten this fact. And third, because I am dealing with crypto, math, finance and cryptocurrencies I sometimes use terms that perhaps are not the best for a particular usage. I used the word paid in "get paid in FACT0RN coins", though technically it should be "get rewarded in FACT0RN coins" as that is the right terminology in cryptocurrencyland. Last fiddled with by factorn on 20220517 at 20:10 Reason: Fix spacing. 
20220517, 20:19  #10  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·3·1,093 Posts 
Quote:


20220517, 22:51  #11 
Dec 2016
2^{3}·3·5 Posts 
If that works out and someone finds a vastly superior way of factoring integers, they can completely take over the blockchain because they now contribute most of the work. Sounds like a bug rather than a feature.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Why integer factorization is in P/FP?  tetramur  Factoring  4  20190123 20:51 
Integer factorization?  bearnol2  Information & Answers  7  20101209 02:50 
Integer factorization with q < 2p  mgb  Math  36  20091107 15:59 
Integer Factorization  mgb  Math  16  20071217 10:43 
Integer Factorization 2  mgb  Math  5  20070723 12:55 