Integer Factorization as PoW in a Blockchain

[charybdis]

Originally Posted by factorn

Again, it is not an either-or situation.

Again, where did I say it was one?

They both have posibilities, ASICs are likely to happen sooner, but do not exclude faster-than-NFS algorithm discoveries.

I don't recall excluding them? I'd love to see a faster-than-NFS algorithm. And I seem to remember you strongly disagreeing the first time I suggested that ASICs were more likely. Glad to see you've changed your mind.

Nor do we have proofs that such algorithms do not exist.

Enlightening.

It would certainly accelerate the discovery process.

Agreed. If such an algorithm does exist.

[factorn]

And I seem to remember you strongly disagreeing the first time I suggested that ASICs were more likely. Glad to see you've changed your mind.

Strictly speaking, now that I think about it, the fact that I expect it to happen sooner does imply that I must think somewhere deep down that the probability must be higher; I had just not processed that intuition into the frontal cortex yet. Yes, you are correct.

...ASICs would be a more likely development for blockchain-factoring than new algorithms,...

I think my issue with your original statement is that it does not explicitly emphasize that new algorithms remain on the table. While the statement is true, and logically correct, a lay person might read that and think "I guess this only helps ASIC development". But anyhow, you are correct.

If such an algorithm does exist.

It will accelerate it even if it doesn't exist. Because a priori, we don't know. That's the whole point of the discovery process, it might turn out that discovery is a proof that such a thing does not exist. But, that is progress too.

[chalsall]

@factorn... If I may please, a bit of sincere advice to you. Take it or leave it.

I have been where you are now. Multiple times...

You've come up with an absolutely brilliant idea that just /has/ to be workable. Somehow... Someway...

sum($Research + $Experimentation) >= $Lots;

Hmmm... It doesn't work...

Your idea simply doesn't work. In many different dimensions. Including Economics, which is really just math.

Some of the best minds in the spaces you've newly started working in have told you here, repeatedly, that your idea simply won't work.

Not a single person has said it will work.

Several (including me) have encouraged you to use this as a learning experience. But you seem to take that counsel as an insult.

Sometimes it is best to simply stop digging deeper, and instead look around you and ask if your intellectual structure is sound.

Ask yourself if you might have missed something?

Ask yourself if perhaps all those others who actually know more than you do are actually giving their best advice to you? For free.

[Uncwilly]

Originally Posted by chalsall

Sometimes it is best to simply stop digging deeper, and instead look around you and ask if your intellectual structure is sound.

Originally Posted by Uncwilly

A horse, a horse, my kingdom for a horse.

.

[factorn]

@chalsall You don't know that as netiher do I, or anyone else. To claim that you know whether it will or it will not work is rather arrogant. Time will tell...literally. Apparently, reusable rockets and electric cars would not work either, look at Elon Musk now. I've created a thing. Folks will decide to use it or not. Now, that you and others here present don't like it? That's something entirely different.

I am asking for feedback. I am receiving it. Thank you for that.

@Uncwilly There's been a healthy amount of curiosity and interest in this thread in regards to my work so I will continue to address that for as long as folks want to learn more.

[chalsall]

Originally Posted by factorn

Apparently, reusable rockets and electric cars would not work either, look at Elon Musk now. I've created a thing. Folks will decide to use it or not. Now, that you and others here present don't like it? That's something entirely different.

I am asking for feedback. I am receiving it. Thank you for that.

You /really/ don't know how to "read a room", do you? And, you are *so* not Musk!!!

We here at the Mersenne Forum don't like your proposal because, based on our extensive and collective experience and expertise, this simply won't work.

Very similar ideas have already been thought about a lot already; years ago and then abandoned. Why? Because multiple very serious thinkers could find no workable solutions to the problem space.

Please forgive me for this, but you're just not going to be able to achieve this impossible task.

Begging for help here won't change that reality.

[factorn]

You /really/ don't know how to "read a room", do you?

I don't. (No, but seriously, I don't.)

And, you are *so* not Musk!!!

Indeed, I can confirm I am not Musk.

Because multiple very serious thinkers could find no workable solutions to the problem space.

Could you define what problem you refer to, precisely?

Please forgive me for this, but you're just not going to be able to achieve this impossible task.

What task, precisely, are you referring to?

Begging for help here won't change that reality.

I was asking for help. But, feel free to frame in any way makes you feel better. Important to note: I already have a solution, but I don't like it. If possible I would like something simpler.

[retina]

Originally Posted by chalsall

We here at the Mersenne Forum ...

Last time I checked you were not voted the spokesperson for MF.

Or are you using the royal "we"?

[NatureHacker]

Hello Factorn,


I have proposed about the exact same idea you have, I wonder if you saw this:


https://www.reddit.com/r/Monero/comments/grms1c/a_holy_grail_pow_for_monero_outlined_gnfs/



I also talked about it here on the forum under the name naturevault. The takeaway is if you read the comments that it is not a good method for a standard PoW. The person with the fastest supercomputer would win every block.



I have also done a lot of theorycrafting on what it would work in. I designed CollectBit, which would work but didn't get anyone interested in helping me code it.


https://web.archive.org/web/20210212011550/http://www.naturevault.org/wiki/pmwiki.php/NatureVault/DigitalCollectibleNetwork



Which basically uses a standard shared database.


But I believe I have found the holy grail application, a 3D blockchain I call an actionlattice. Basically everyone makes their own transaction and mines it by factoring a large number into two semiprimes just like you also came to the conclusion.


https://web.archive.org/web/20220929004452/https://www.naturevault.org/wiki/pmwiki.php/CryptoProjects/Actionlattice



(Just started with that one)



Anyhow there is nothing for me to gain in starting it myself. If coinbase wants to create it I will participate, I'm sure with millions of others. If you do want to pursue something like the actionlattice, I will help as much as I can.

[Unitome]

Originally Posted by VBCurtis

You're not the first, nor the second, person to think "I know, I'll use factoring as the basis for a coin!"
But you're the least educated one, so far- the lowest expertise about crypto, or about factoring (see your P vs NP comments- good job trying to sound smart on a forum of people who actually know what they're talking about).

Your idea isn't good, and isn't well thought out. Smarter people than you have had the same idea, and went nowhere because it's not a good idea. You can educate yourself- go right ahead. But "help me build this!" for this topic on this forum will get you ridicule, and little else.

Perhaps I would be honored as one of the dummies that tried this before that VB is referencing :). It is possible on a 1D (standard) blockchain, but very difficult to implement, not because "creating semiprimes without knowing the factors first" is hard, it's easy, just let people use a nonce and hash to create the numbers and search until they find a viable semi-prime as the OP rediscovered.

What's hard is setting the type of factors you will accept. If you allow any base-2 brilliant (strong semiprime) of a given bitlength like the OP proposes, then basically all miners have a 1 in 20 or so (depending on the bitlength) chance of the first GNFS sieve they have to do (after ECM) is a "winner". This means that faster computers are getting more "vote" than they democratically deserve, if there are more than 20 miners. Image 1000 miners all with a 1 in 20 chance of winning on their first sieve, and then the fastest gets a much better odds of winning than someone with just a slightly slower computer. The fastest computer has a 1 in 20 chance of winning, while the slowest computer (perhaps only a tiny bit slower than the fastest) has less than 1 in 1000 chance of winning. That is a 5000% increase in "chance to win a block" for only a small marginal improvement in factoring ability.

One of the solutions is to require a certain number of "leading 9's" on the factor(s) themselves. sort of like "leading 0's" on the bitcoin hash. The problem is that this may prove to be a crude way to manage difficulty. Also can the network share rate act as an oracle to base the "leading 9" difficulty on? I'm not sure how this difficulty could auto-adjust.

My (current) solution is with a 3D blockchain where each transaction is mined (factored) individually (or even by the transaction proposer themselves). It is called actionlattice.

[Unitome]

Originally Posted by retina

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.

Actually regrettably this is EXACTLY how ASIC resistance works in practice . That said it can work! Just have to make memory requirement for the hash function scale with moore's law so that only CPU's can keep up with moore's law since they are multi-purpose. ASIC's having to double their memory every 3 years is a death blow because all the architecture changes (typically) unlike with CPU's where they just add a bigger cache.

The commenters talking about energy use and waste, if we can only allow CPU's to mine - and nothing else can do the heavy lifting - then we DRASTICLY reduce power use of the network. It is a theory called CAPEX/OPEX in Optical Proof of Work. That is the main reason OP and I are interested in GNFS. It is the ONLY, truly with full certainty, ASIC resistant algorithm. It is not ASIC proof, like the SHARK paper shows, but it is provably resistant, unlike any other algo out there.