Pump up GIMPS power? (Wishful thinking)

[airsquirrels]

https://github.com/ethereum/EIPs/iss...ment-377734068

The cryptocurrency space is going through a bit of a crisis, maybe we can convince them that elliptic curve factoring candidates for us is more valuable and to build dedicated factoring hardware for high bitrates isn’t likely to have big advantages over commodity GPUs and CPUs!

[0PolarBearsHere]

Originally Posted by airsquirrels

https://github.com/ethereum/EIPs/iss...ment-377734068

The cryptocurrency space is going through a bit of a crisis, maybe we can convince them that elliptic curve factoring candidates for us is more valuable and to build dedicated factoring hardware for high bitrates isn’t likely to have big advantages over commodity GPUs and CPUs!

Is it be more useful to disprove by finding a factor (using for example ECM), or to prove using LL calculations? Should we instead be trying to get someone to come up with a coin that requires large FFT calcs that we can exploit?

[M344587487]

I've thought about factoring as PoW for a cryptocurrency and it is an interesting idea:

• The PoW needs to rely on the previous block to form a chain. Lets say the choice of candidates to try and factor is dependent on the hash of the previous block.
• Previous factoring results should not be re-usable (for efficiency we don't want to redo work, and it's also insecure if the work can be skipped). So we need a massive set of candidates (2^128 say) such that caching is ineffective. I've gone back-and-forth over using a hash map with a more reasonable number of candidates (2^28 say), but that incentivises caching from external sources (GIMPS, factordb, wherever) and disincentivises publishing of results.
• As complete a list of candidates with known factors as possible is baked in from the offset, minimising repeated work from external sources. Results already encoded in the blockchain are also skipped
• A traditional blockchain aims to emit a block at regular intervals. It does this by looking at the recent history of block times (as a gauge of hash power) and adjusting a difficulty number to increase/decrease the average block time as desired. The difficulty in this case could be used to adjust how many candidates we are allowing to be searched to create the next block.

Block times is a potential stumbling block. We can't accept "no factors found with these parameters" as PoW as there's no proof, the only proof is in finding a factor. To maintain a healthy average block time, you need a minimum rate of hashpower to find factors quick enough. Maybe it's not such a problem as if hashpower is low enough, the difficulty will drop to the point where trial-factoring takes over as more efficient at finding factors we're interested in than ECM (the number of permissible candidates increases, increasing the chance of landing on a candidate that has not been trial-factored to a high bit-depth). I don't think there's a need to lock down the algorithm used for finding factors, just the candidates.

Originally Posted by 0PolarBearsHere

Is it be more useful to disprove by finding a factor (using for example ECM), or to prove using LL calculations? Should we instead be trying to get someone to come up with a coin that requires large FFT calcs that we can exploit?

I can't see a way to use LL as PoW, the only proof is in finding a prime and that would make for some rather excessive block times :P Verifying part of a DC with "I agree", or saying "this LL that took 5 seconds came out as composite check out this totally-real residue" is too easy to fake.

[airsquirrels]

Most of the crypto algorithms now are a bunch of work, memory hard or computationally hard, with a simple efficient hash function at the end of the solution to store the signature of that work in the next block.

The hard part would be taking the previous hash and incorporate it into the work, such that work couldn’t be prepared ahead of time.

[VictordeHolland]

MersenneCoin?
ECMcoin?
FFTcoin?

[Mark Rose]

We find Mersenne primes too irregularly to make even pooled mining a thing.

Making TF coins could be a thing though. Hmmm...

[preda]

Originally Posted by Mark Rose

We find Mersenne primes too irregularly to make even pooled mining a thing.

Making TF coins could be a thing though. Hmmm...

An MTF (Mersenne Trial Factoring) proof-of-work would be excellent. It needs a clear proposal.

If adopted as PoW in some popular coin (ethereum) that would be sweet, but it may be not easy to get the stakeholders' agreement.

MTF could also be the base for a stand-alone crypto coin. This would allow a quantitative incentive for TF (similar to the monetary incentive for LL, the 100M-digit prime prize).

[preda]

Originally Posted by preda

An MTF (Mersenne Trial Factoring) proof-of-work would be excellent.

"Prime Coin" :)

Edit: oops, it seems that name is taken... well then, back to Mersenne coin.

[airsquirrels]

Figure out the algorithm and we could do it!

Requirements:
Input: 32 byte header hash of proposed block, nonce (64 bit worker specific attempt)

Algorithm: ??? Test a range of bits on some candidates???

Output:
List of factors found +
32 byte hash whose 256 bit value is < target

How do you ensure each hash attempt is on previously unfactored candidates?

Perhaps each block includes a range of candidates from a pre-determined pools, iterating through the pool every block? The hash would have to be the mod sum of candidate attempts or some other not so fakeable values. Perhaps nonce represents the low order bits and high order ranges are checked?

[Dubslow]

The major problem with this is that it's ASIC-able. There will be too much centralization.

[GP2]

Originally Posted by Dubslow

The major problem with this is that it's ASIC-able.

That's only a problem for the currency itself. It would be a boon to the project's goal of finding factors with low power expenditure.

In fact, why not make the whole thing a scam by design. It would hardly be the first cryptocurrency to fit that description. Deliberately make it ASIC-able, albeit in a non-obvious way. After the dust settles, we buy up the ASICs at fire-sale prices and use them for our own purposes to find factors. The ASIC designers might even put extra R&D effort into it because of the durable hobbyist aftermarket for their product even after the currency itself fails.