Integer Factorization as PoW in a Blockchain

factorn · 2022-05-17, 14:09

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

retina · 2022-05-17, 14:14

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?

factorn · 2022-05-17, 14:27

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?

factorn · 2022-05-17, 14:57

@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 Miller-Rabin 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 GNU-GMP library recommends. Additionaly, you also perform the Baillie-PSW Primality test.

retina · 2022-05-17, 15:20

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 semi-prime of the required character.

factorn · 2022-05-17, 15:24

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.

VBCurtis · 2022-05-17, 16:18

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?"

factorn · 2022-05-17, 16:50

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 CADO-NFS 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:

Ability to do so doesn't guarantee an equivalent amount of desire or motivation to do so. I wonder if the OP is willing to offer something in return?

The FACT0RN blockchain would create a market of sorts where the motivation to factor is to get paid in FACT0RN coins. It would create a market for factoring, and by the looks of the thread I linked to above, there is a demand for such a thing.

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

factorn · 2022-05-17, 20:09

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 cryptocurrency-land.

retina · 2022-05-17, 20:19

Quote:

Originally Posted by VBCurtis

What problem does this idea solve that isn't solved by an existing blockchain? Why is this better, from a crypto standpoint?

None of the crypto stuff is good for anything, except for increasing the profit of power companies.

Quote:

Originally Posted by VBCurtis

How would you make the numbers to be factored of any interest whatsoever mathematically?

None of the crypto stuff generates interesting numbers for anyone. But the more extra steps you make people do, then hopefully the more people get bored with it and do other things that are more productive.

nordi · 2022-05-17, 22:51

Quote:

Originally Posted by factorn

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.

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.

2022-05-17, 14:09	#1
factorn Feb 2022 2³×7 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

2022-05-17, 14:57	#4
factorn Feb 2022 2³·7 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 16nBits 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 - 16250, W + 16250] 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 Miller-Rabin 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 GNU-GMP library recommends. Additionaly, you also perform the Baillie-PSW Primality test. Last fiddled with by factorn on 2022-05-17 at 15:21 Reason: Fix spacing and probability that was missing the exponent part. Explain a little more and add links to code.

2022-05-17, 20:09	#9
factorn Feb 2022 2³·7 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 cryptocurrency-land. Last fiddled with by factorn on 2022-05-17 at 20:10 Reason: Fix spacing.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Why integer factorization is in P/FP?	tetramur	Factoring	4	2019-01-23 20:51
Integer factorization?	bearnol2	Information & Answers	7	2010-12-09 02:50
Integer factorization with q < 2p	mgb	Math	36	2009-11-07 15:59
Integer Factorization	mgb	Math	16	2007-12-17 10:43
Integer Factorization 2	mgb	Math	5	2007-07-23 12:55

2022-05-17, 14:14	#2
retina Undefined "The unspeakable one" Jun 2006 My evil lair 1A73₁₆ 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?

2022-05-17, 14:27	#3
factorn Feb 2022 2³·7 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?

2022-05-17, 15:20	#5
retina Undefined "The unspeakable one" Jun 2006 My evil lair 3×37×61 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 semi-prime of the required character.

2022-05-17, 15:24	#6
factorn Feb 2022 2³×7 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.

2022-05-17, 16:18	#7
VBCurtis "Curtis" Feb 2005 Riverside, CA 7×829 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?"