mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-05-17, 14:09   #1
factorn
 
Feb 2022

24×3 Posts
Default 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
factorn is offline   Reply With Quote
Old 2022-05-17, 14:14   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×3,257 Posts
Default

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?
retina is offline   Reply With Quote
Old 2022-05-17, 14:27   #3
factorn
 
Feb 2022

3016 Posts
Default

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 is offline   Reply With Quote
Old 2022-05-17, 14:57   #4
factorn
 
Feb 2022

24·3 Posts
Default

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


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.
factorn is offline   Reply With Quote
Old 2022-05-17, 15:20   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

145628 Posts
Default

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.
retina is offline   Reply With Quote
Old 2022-05-17, 15:24   #6
factorn
 
Feb 2022

24·3 Posts
Default

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.
factorn is offline   Reply With Quote
Old 2022-05-17, 16:18   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5·11·97 Posts
Default

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?"
VBCurtis is offline   Reply With Quote
Old 2022-05-17, 16:50   #8
factorn
 
Feb 2022

24×3 Posts
Default

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

Last fiddled with by factorn on 2022-05-17 at 16:51 Reason: Fix Spacing.
factorn is offline   Reply With Quote
Old 2022-05-17, 20:09   #9
factorn
 
Feb 2022

24·3 Posts
Default

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.
factorn is offline   Reply With Quote
Old 2022-05-17, 20:19   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

651410 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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 View Post
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.
retina is offline   Reply With Quote
Old 2022-05-17, 22:51   #11
nordi
 
Dec 2016

23·3·5 Posts
Default

Quote:
Originally Posted by factorn View Post
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.
nordi is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 09:23.


Wed Jul 6 09:23:17 UTC 2022 up 83 days, 7:24, 0 users, load averages: 0.85, 1.13, 1.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔