Integer Factorization as PoW in a Blockchain

[chalsall]

Originally Posted by factorn

Ridicule is all fun and stuff.

For those who are serious, this is what is known as the Scientific Method.

A bit like a game of Rugby, where you try to disable your opponent on the field, and then you laugh about it while you buy each other beers and laugh about it after the game.

Or, a bit like a game of Go, where everything is fun and games until someone loses an eye...

Originally Posted by factorn

Who knows? Maybe I will be able to contribute some day.

Perhaps. But, clearly not today.

[factorn]

Originally Posted by chalsall

For those who are serious, this is what is known as the Scientific Method.

A bit like a game of Rugby, where you try to disable your opponent on the field, and then you laugh about it while you buy each other beers and laugh about it after the game.

Or, a bit like a game of Go, where everything is fun and games until someone loses an eye...



Perhaps. But, clearly not today.

Incidentally, have you seen the Coinbase blog today? There is a new article: https://blog.coinbase.com/fact0rn-bl...w-bc48c6f2100b


The whitepaper is here (https://fact0rn.io/FACT0RN_whitepaper.pdf).


Does this count as a contribution? @chalsall

[charybdis]

Originally Posted by factorn

IThe whitepaper is here (https://fact0rn.io/FACT0RN_whitepaper.pdf).

I know next to nothing about blockchain, but unfortunately it appears you know next to nothing about computational number theory. Here are a couple of questions for you to consider:

1. For the sizes that you're interested in, what increase in bit-length corresponds to a doubling of the factoring effort required? (Hint: it's nowhere near 64 bits.)

2. Just how common are what you call "strong semiprimes", or base-2 brilliant numbers as they are otherwise known? (Hint: they're probably rarer than you think. With your interval sizes, most intervals won't contain one.)

Can these issues be sorted out? Of course. They just don't inspire confidence.

[Uncwilly]

Originally Posted by factorn

Incidentally, have you seen the Coinbase blog today?
Does this count as a contribution? @chalsall

No, that is just spam.

[factorn]

Originally Posted by charybdis

I know next to nothing about blockchain, but unfortunately it appears you know next to nothing about computational number theory. Here are a couple of questions for you to consider:

1. For the sizes that you're interested in, what increase in bit-length corresponds to a doubling of the factoring effort required? (Hint: it's nowhere near 64 bits.)

2. Just how common are what you call "strong semiprimes", or base-2 brilliant numbers as they are otherwise known? (Hint: they're probably rarer than you think. With your interval sizes, most intervals won't contain one.)

Can these issues be sorted out? Of course. They just don't inspire confidence.

@charybdis, it would do you well to actually read the paper. Who knows? You might even learn something. It is my understanding, from reading other posts on this forum, that it doubles about every 10 binary digits or so. Of course, I could actually compute it heuristically up to sizes of 300-bit and extrapolate from there. I could also just look at the literature.

What you, Sir, seem to understand is that the reward function should grow exactly like this. What you fail to understand is that there is a whole other area of study called economics that plays into this. It is not just theoretical math -- you know, an inter-disciplinary thing. Go tell bitcoin their reward function should scale with the difficulty of hashing...see how that goes. Or any other PoW blockchain for that matter.

I defined what "strong semiprime" means exactly for this reason. To avoid confusion, then again, reading the actual whitepaper might help. Who knows?

Please, do indicate how these issues can be sorted out. I am interested.

Incidentally, starting the response with "I know next to nothing about blockchain, but" I thought was funny. Your observations are very much welcomed nonetheless.

@Unwilly, there is no winning, uhm... I mean contributing, with you.

[charybdis]

Originally Posted by factorn

@charybdis, it would do you well to actually read the paper. Who knows? You might even learn something. It is my understanding, from reading other posts on this forum, that it doubles about every 10 binary digits or so. Of course, I could actually compute it heuristically up to sizes of 300-bit and extrapolate from there. I could also just look at the literature.

What you, Sir, seem to understand is that the reward function should grow exactly like this. What you fail to understand is that there is a whole other area of study called economics that plays into this. It is not just theoretical math -- you know, an inter-disciplinary thing. Go tell bitcoin their reward function should scale with the difficulty of hashing...see how that goes. Or any other PoW blockchain for that matter.

I defined what "strong semiprime" means exactly for this reason. To avoid confusion, then again, reading the actual whitepaper might help. Who knows?

Please, do indicate how these issues can be sorted out. I am interested.

Incidentally, starting the response with "I know next to nothing about blockchain, but" I thought was funny. Your observations are very much welcomed nonetheless.

Okay, I retract my second comment - I see that you did mention that multiple nonces** might be needed to find a strong semiprime. Apologies.

I understand that there is more than just mathematics involved here, but this is what's confusing me:

The exponential shape is required because the marginal cost of factoring a bigger number is also
exponential; otherwise, the opportunity cost of factoring a smaller number will always be
negative and it will be more profitable to find and factor smaller semiprimes.

In other words, you seem to be saying that the reward has to be higher for larger numbers in order to create an incentive for people to factor larger numbers. But then you set the reward function so that it is still more profitable to factor smaller numbers. You mention bitcoin, but as I understand it, with bitcoin the difficulty of the tasks is periodically increased and cannot be chosen by the miner, so there's no reason for reward to scale with difficulty. Is your blockchain intended to function in a similar way, i.e. every so often the size of the numbers to be factored increases? If so, then your reward function might make more sense, but then your explanation doesn't seem to make sense to me as once the size increases there's no way for the miner to factor smaller numbers anymore. Happy to be enlightened.

FWIW, difficulty doubles roughly every 17-18 bits for numbers with degree 5 GNFS polynomials, i.e. about 360-720 bits.

Also:

Why must the smallest prime be submitted? The measure for work done for PoW uses
an ECM based function to measure how much work was done in the factorization [2]. This
function works based on the smallest factor found, hence the requirement to submit the
smallest prime factor. This is the best proxy I was able to find to compute this quantity
based on the smallest factor found even if the Number Field Sieve is used to factor.

What's the need for this? ECM and NFS are totally different algorithms, and with NFS the size of the smallest factor has no effect on the difficulty, only the size of the number to be factored. Is there some blockchain-related reason for doing this?

**clearly whoever decided to use this word in this context wasn't British. I'm reminded of when the dreadful Last Airbender movie became an accidental comedy in the UK.

[pinhodecarlos]

Regarding the white paper:


1) You call figure (1) to a table and figure (2) to an equation.
2) Please define what's a table, a figure and an equation.

[factorn]

Originally Posted by charybdis

Okay, I retract my second comment - I see that you did mention that multiple nonces** might be needed to find a strong semiprime. Apologies.

I understand that there is more than just mathematics involved here, but this is what's confusing me:

In other words, you seem to be saying that the reward has to be higher for larger numbers in order to create an incentive for people to factor larger numbers. But then you set the reward function so that it is still more profitable to factor smaller numbers. You mention bitcoin, but as I understand it, with bitcoin the difficulty of the tasks is periodically increased and cannot be chosen by the miner, so there's no reason for reward to scale with difficulty. Is your blockchain intended to function in a similar way, i.e. every so often the size of the numbers to be factored increases? If so, then your reward function might make more sense, but then your explanation doesn't seem to make sense to me as once the size increases there's no way for the miner to factor smaller numbers anymore. Happy to be enlightened.

FWIW, difficulty doubles roughly every 17-18 bits for numbers with degree 5 GNFS polynomials, i.e. about 360-720 bits.

Also:

What's the need for this? ECM and NFS are totally different algorithms, and with NFS the size of the smallest factor has no effect on the difficulty, only the size of the number to be factored. Is there some blockchain-related reason for doing this?

**clearly whoever decided to use this word in this context wasn't British. I'm reminded of when the dreadful Last Airbender movie became an accidental comedy in the UK.

Happy to address questions to the extent I am able to answer them.

I think it is far more productive for everyone reading to explain two general concepts associated with PoW blockchains than it is to answer your questions directly...because the answers might raise more questions still.

There is a "thing", it just a number, that is called the difficulty level. I say a "thing" because its meaning may change across blockchains, but it is just a number. In our case, that is the number of digits a strong semiprime must have for the blockchain to accept it as valid for solving a block.

This "thing" updates every 672 blocks on FACT0RN -- the 672 to be explained later. If the mining is "fast", it will go up and make it harder to factor. If the mining is slow, it will lower it and make it easier to factor. In the FACT0RN blockchain the starting difficulty level was 230 bits, and as of right now it is 253-bits. It has gone up 23 digits since launch date: 4/20/2022. (Yes, because 420 and memes.)

What determines whether it will go up or down? There is a "thing", called the 'target block time', which is just a number. The blockchain takes this 'target block time' number and computes the average time it took to solve a block for the past 672 blocks -- let's call this quatinty avg_solve. In FACT0RN, if avg_solve < 28 minutes the difficulty goes up by 1 binary digit, and if avg_solve > 31 minutes it goes down by 1 binary digit. The target block time is between 28-31 minutes per block. The actual target is 30 minutes. Heuristically the above setting should get us close to that. There might be something better. Would be good to know. Research area.

Turns out the hardest part is not factoring....its finding what to factor....but the cheapest way to do it is to factor everything until you find a strong semiprime. Lots of good opportunities for mathematical improvements with sieving in this area.

Bitcoin, and every PoW, do this. Their "difficulty level" number means something different, but the idea is the same. The update happens roughly every two weeks, with a 30 minutes 'target block time', that is 672 blocks. Two weeks because that is how bitcoin and every PoW chain does it, so I follow what has worked for everyone else.

The opportunity cost part, and bitcoin, takes awhile to explain. I am skipping that one for now.

On the ECM thing....yes, you are technically correct. The best kind of correct. Out here, in the real world however, things have to work and an approximation will do, even a bad approximation. Also, given the reason the blockchain uses this it only matters that the function is strictly monotonically increasing and the derivative be somewhere in the vicinity of marginal factoring cost --any exponential or sub-exponential function will do really.

This function is used to measure the work done for every block....its call a blockchain because there are tonnes of blocks connected together and because there can be many chains....how does the system choose the 'true" chain from all them?...well, imagine a partially order set that is also a Directed Acyclic Graph (DAG)...the blockchain takes the chain along the path in the DAG that has the highest cumulative work...add up all the measures of work for every block along that path...that becomes the "blockchain".

I hope this clears up stuff. Do let me know if you have any more questions.

[factorn]

Originally Posted by pinhodecarlos

Regarding the white paper:


1) You call figure (1) to a table and figure (2) to an equation.
2) Please define what's a table, a figure and an equation.

I am bad at Latex. I will try to fix it.

[chalsall]

Originally Posted by factorn

Does this count as a contribution? @chalsall

It does.

I have skimmed your paper twice now. It is formatted very professionally. Is that produced by LaTeX?

I have nowhere near the level of number theory needed to critique your paper in that domain. I will leave that to the able hands of others here.

I understand the theory of CC; I have thought about it a lot. And, my opinion is that ***no*** PoW-based cryptocurrency (CC) can scale. Not even if can somehow be used to "help researchers by finding factors...".

Proof of Stake (PoS) /might/ be workable... But even then you risk the 51% attack... And one step back from that we're back to fiat.

A few questions for you on your paper...


1. Why do you include a "Tip Jar Address" at the bottom of page 2?


2. Do You have a thought as to how many transactions per hour your proposed system would be able to support?

2.1. This, of course, will be a function of how many "miners" are in the swarm.


I do sincerely thank you for sticking with this. It shows character and resolve.

Never be afraid to stand alone. But always be ready to admit when one is wrong.

[charybdis]

Thanks factorn, you've cleared up a lot of things. The one thing that still bugs me a bit is how strict you made the definition of "strong semiprime", as in practice it means many (often >100) QS/NFS jobs per block, with the associated geometric distribution and its long tail. Don't see what would be wrong with loosening it to, say, the lengths being within 20% or even 50% of each other. Sieve algorithms will still be much better than ECM. You wouldn't have to worry about that even-odd 60-to-40 parity issue either. (2-2ln(2) to 2ln(2)-1 in the limit, I guess 60-40 is more reader-friendly haha)

Addressing some of the things mentioned earlier in this thread: given the ubiquity of RSA, there are huge practical and moral issues associated with publishing a new faster-than-NFS factoring algorithm. Anyone who finds one would have to be extremely careful to avoid criminals taking advantage of it before everyone who uses RSA can increase their key sizes as necessary. In particular, putting one on arXiv one day without any prior announcement would be an extremely bad idea! Anyone who finds one is in a bit of a sticky situation: don't alert the US government and you probably find yourself under investigation, alert the US government and you probably still find yourself under investigation...