Pump up GIMPS power? (Wishful thinking)

[chalsall]

Originally Posted by VictordeHolland

Wouldn't this mean if somebody wanted to start mining or open up a wallet he/she needed to download the entire mersenne.org database + James additional data up to 2^32 (http://www.mersenne.ca/status/tf/0/0/0/0) + part of the factordb for low mersenne candidates? I don't know how much this is exactly (even with compression or saved as some sort of bitmap?)

Yes.

Further, someone has to define the coin. And why it is worth money.

It amuses me somewhat that few people understand the term "fiat value".

[CRGreathouse]

Originally Posted by chalsall

It amuses me somewhat that few people understand the term "fiat value".

What's not to understand?

[M344587487]

Originally Posted by science_man_88

What are all the primes up to : ~31622776601683793319988935444327185337195 ?

I honestly don't know how long it takes to determine primality of a 128 bit number (I naively hoped pretty quick), as described you'd need to generate thousands of them before you could use them as candidates for factoring. Determining the candidates should take maybe 20 seconds max on a quad core processor, as the setup before factoring begins. You asking suggests I'm orders of magnitude off.

Which is a shame as I'm assuming we'd need to rely on a vast bit-space to deter abuse. Maybe I'm being too paranoid though, 64 bits is still a pretty massive space and we can determine primality of those quick enough (right? If it came to it I guess we'd have to resort to PRP). Using 64 bits would also put the results in the range of "potentially useful before the heat-death of the universe" so that's another plus ;)

Originally Posted by VictordeHolland

Wouldn't this mean if somebody wanted to start mining or open up a wallet he/she needed to download the entire mersenne.org database + James additional data up to 2^32 (http://www.mersenne.ca/status/tf/0/0/0/0) + part of the factordb for low mersenne candidates? I don't know how much this is exactly (even with compression or saved as some sort of bitmap?)

Broad inexact ranges would be OK, just enough to catch and avoid needlessly redoing the majority of work already done. It could be as simple as "don't do any p under 28 bits" or whatever. Not that it's likely that we'll hit that in a 128-bit space, or even a 64-bit space, so using a list would likely be more trouble than it's worth. If used though, you'd need it for a node (like a full wallet, a pool or solo mine), but you wouldn't need it to pool mine as the pool would take care of that.

The more I read it, the more I think 128-bits is way too vast to be useful. I've changed my opinion to a 64-bit space being better suited for now. I also realise I'm being sloppy when it comes to defining an "n-bit space" as either the first 2^n primes or primes below 2^n. I mean the former but there's an argument to be made for the latter.

[science_man_88]

Originally Posted by M344587487

I honestly don't know how long it takes to determine primality of a 128 bit number (I naively hoped pretty quick), as described you'd need to generate thousands of them before you could use them as candidates for factoring. Determining the candidates should take maybe 20 seconds max on a quad core processor, as the setup before factoring begins. You asking suggests I'm orders of magnitude off.

Which is a shame as I'm assuming we'd need to rely on a vast bit-space to deter abuse. Maybe I'm being too paranoid though, 64 bits is still a pretty massive space and we can determine primality of those quick enough (right? If it came to it I guess we'd have to resort to PRP). Using 64 bits would also put the results in the range of "potentially useful before the heat-death of the universe" so that's another plus ;)


Broad inexact ranges would be OK, just enough to catch and avoid needlessly redoing the majority of work already done. It could be as simple as "don't do any p under 28 bits" or whatever. Not that it's likely that we'll hit that in a 128-bit space, or even a 64-bit space, so using a list would likely be more trouble than it's worth. If used though, you'd need it for a node (like a full wallet, a pool or solo mine), but you wouldn't need it to pool mine as the pool would take care of that.

The more I read it, the more I think 128-bits is way too vast to be useful. I've changed my opinion to a 64-bit space being better suited for now. I also realise I'm being sloppy when it comes to defining an "n-bit space" as either the first 2^n primes or primes below 2^n. I mean the former but there's an argument to be made for the latter.

Admittedly you can store them more efficiently than a full bit array but the worst (okay maybe best) case scenario using that is of order 2^65 exbibytes where an exbibyte is 2^60 bytes. EDIT: for comparison 2^64 primes by the same methods is at least 2 exbibytes.

[CRGreathouse]

Originally Posted by science_man_88

What are all the primes up to : ~31622776601683793319988935444327185337195 ?

If you're looking for the 2^128-th prime, it should be in the range from
31385451756339630843423037847304347844574
to
31387177659913587550099489927037384891112
(and yes, there are better bounds than this, I'm lazy).

[CRGreathouse]

Originally Posted by M344587487

I honestly don't know how long it takes to determine primality of a 128 bit number (I naively hoped pretty quick), as described you'd need to generate thousands of them before you could use them as candidates for factoring. Determining the candidates should take maybe 20 seconds max on a quad core processor, as the setup before factoring begins. You asking suggests I'm orders of magnitude off.

On the order of 10 milliseconds for a proof, though you could save 2-3 orders of magnitude (microseconds, not milliseconds) if you allowed BPSW probable primes.

[chalsall]

Originally Posted by airsquirrels

One way I could think of to prevent users from pre-factoring specific ranges is to the make factoring only a portion of the proof of work, or make the hash of the previous block that must be part of the input some how restrict which factors are considered value.
...
5. Server rejects any duplicate solutions, rather than compete for time the nodes operate on a fixed block time, and the solution with the highest sum of log2(factors) is chosen to seal the block and get the reward.

I've been racking my brain (it's a small brain) trying to think of a way this could be done, and have come up empty handed...

1. Somehow manipulating the previous block's hash with all the post sieving dividing candidates wouldn't work, because someone could simply modify mfakt[c|o] to record this vector during any run (a large amount of data, but nothing unmanageable in this day-and-age).

2. Choosing a random set of candidates to TF wouldn't work because someone could simply TF a large range, and then have the results ready to report when specified as "valid".

Both of these situations require someone(s) with a great deal of compute ability, but they already exist.

More than happy to hear from anyone who can think of a way to make this work.

[Mark Rose]

So I got to thinking about this a bit more.

Couldn't we simply reward the smallest N factors found per round?

Then we don't actually care how hard it is to find a factor. Then clients will have to balance their depth vs breadth first searching of their validate set of candidates. We can leave it up to the clients/pools to find the most optimal algorithm (and avoid repeating work). We won't find factors for the smallest candidates right away, but I don't think it will take long for the higher candidates to be mined out before we start finding more relevant factors for GIMPS.

The total number of coins would be capped by never increasing the candidate exponent range. We could launch a second coin if we ever needed to work on a different range. If we start with a high enough range we can guarantee to generate enough factors to certify transactions in every round. As long as a bitmap of the unfactored candidates fits on a reasonably sized hard disk, we should be good.

[kriesel]

Is anyone else visualizing Tom Hanks as Forrest in $200 shoes, an ankle length coat with fur trim, and a flat brim hat with a pheasant feather in the band?

[chalsall]

Originally Posted by Mark Rose

Couldn't we simply reward the smallest N factors found per round? Then we don't actually care how hard it is to find a factor. Then clients will have to balance their depth vs breadth first searching of their validate set of candidates.

This doesn't get around the problem of those with a lot of compute being able to prefactor, and only report factors they've already found when it is "profitable".

Again, more than happy to be proven wrong, but I just don't think this can work for our particular goal.

As an aside, I absolutely loved ewmayer's link to "Bacoin"!!! Perhaps we simply offer slices of bacon for factors of leading edge MP candidates. Might be less expensive than some of us spend on AWS et al....

[Mark Rose]

Originally Posted by chalsall

This doesn't get around the problem of those with a lot of compute being able to prefactor, and only report factors they've already found when it is "profitable".

Again, more than happy to be proven wrong, but I just don't think this can work for our particular goal.

I think if we integrate two ideas, that's a solved problem:

1. Each mining node is given a subset of exponents to test. It could only find factors for those exponents.
2. Only N smallest factors per round are rewarded.

I suppose someone could still try pre-mining everything, but in each round it would be unlikely their eligible exponents would match the kept-back factors. Each factor submitted would be recorded, regardless of if it's rewarded or not.

In a sense, pre-mining would be the natural outcome, as each miner/pool would probably want to track how far they TF'ed a given exponent to not repeat work in the future.

The only problem I can see is someone coming along and owning more than 50% of the nodes.

As an aside, I absolutely loved ewmayer's link to "Bacoin"!!! Perhaps we simply offer slices of bacon for factors of leading edge MP candidates. Might be less expensive than some of us spend on AWS et al....

I love bacon.