Bitcoins

[f1pokerspeed]

Originally Posted by chalsall

This is the question to be answered.

There must be a solution space to this problem.

(Not likely to be implemented quickly, but it's an interesting driving problem.)

Idea for a method of doing this:

RSA-2048+ keys created. Public key transmitted to client. One residue is sent to server encrypted at iteration 1,000 (yeah, it's big but proof of work is required). Once the iteration is verified using the decryption it is assumed that the work is being completed truthfully - in which case, one SHA-256 hash is sent every 1m iterations and stored on server per exponent. The DC run will also hash the residues and the hashes will be compared. Provided the hashes are the same, the coin is awarded.

[Mini-Geek]

Originally Posted by f1pokerspeed

Idea for a method of doing this:

RSA-2048+ keys created. Public key transmitted to client. One residue is sent to server encrypted at iteration 1,000 (yeah, it's big but proof of work is required). Once the iteration is verified using the decryption it is assumed that the work is being completed truthfully - in which case, one SHA-256 hash is sent every 1m iterations and stored on server per exponent. The DC run will also hash the residues and the hashes will be compared. Provided the hashes are the same, the coin is awarded.

All this verifies is that you ran the first 1,000 iterations, which the server must duplicate. The problem is still there, and may be theoretically insoluble: is there any way to verify an LL result (be it at the end or partway through) without rerunning the work? I doubt it, because if there were, some smart mathematician would've figured out how to use it to skip all the iterations of the LL and simply check if the last iteration's residue looked like it might be 0, and greatly reduce the effort required to prove Mersenne primes.

And sending the full residue instead of the last few bits, or a hash of the residue, is only really useful if you plan on resuming from that residue. Verifying that the values match beyond reasonable doubt can be done with the last bits.

[chalsall]

Originally Posted by Mini-Geek

Verifying that the values match beyond reasonable doubt can be done with the last bits.

So the question stands.

Is there a way to solve this problem without having "out of band" trust between the authority and the client?

[f1pokerspeed]

Well, let me pose this question:

How easy is it to perfectly forge a residue? Especially as the residue would be encrypted, something that might be a better way to implement this is to encrypt the residue client-side and only store the encrypted residue on the end system. The only way to break the encryption would be to factor the RSA number! This is computationally infeasible - you could even future-proof this with RSA-4096 or higher, multiple rounds, etc. It all adds up.

A brute force attack seems infeasible, maybe my numbers are wrong - I'll re-calculate and se if I can find something.

Edit: Calculations

Hex chars in residue:

Permutations per res:

Total permuatations per candidate:

Either way you have the quorum defence so I can't see this being broken.

Therefore, why would this system not work? Two layers of protection.. both very, VERY strong.

[chalsall]

Originally Posted by f1pokerspeed

A brute force attack seems infeasible, maybe my numbers are wrong.

You're numbers are wrong.

That's OK.

We're on this.

[Mini-Geek]

Originally Posted by f1pokerspeed

Well, let me pose this question:

How easy is it to perfectly forge a residue?

Practically impossible, as your numbers suggest (even if you just take the last 64 bits of the residue, as GIMPS currently does, the point stands). But the question that reveals the problem is:

How easy is it to verify a claimed residue?

The answer to that appears to be: redo the work. This makes the LL test unsuitable for something like Bitcoin mining, which requires fast verification.

[LaurV]

Originally Posted by Mini-Geek

the question that reveals the problem is:

How easy is it to verify a claimed residue?

The answer to that appears to be: redo the work. This makes the LL test unsuitable for something like Bitcoin mining, which requires fast verification.

Exactly! You (the server) have no way to know that I put a valid residue into the (hash/encryption/magic box/whatever) or just (crap/my prefered pictures with cats/whatever) unless I give to him ALL residues, then he might pick some ranges and redo the work on those ranges, or redo ALL the work. None of the two are feasible, neither any of their combinations/compromises: the last because the server can't do the work of ALL the users combined (as I said "you will need a very strong server") and the former because you will need to send lots of data, not feasible from the communication side.

[Mini-Geek]

Originally Posted by LaurV

Exactly! You (the server) have no way to know that I put a valid residue into the (hash/encryption/magic box/whatever) or just (crap/my prefered pictures with cats/whatever) unless I give to him ALL residues, then he might pick some ranges and redo the work on those ranges, or redo ALL the work. None of the two are feasible, neither any of their combinations/compromises: the last because the server can't do the work of ALL the users combined (as I said "you will need a very strong server") and the former because you will need to send lots of data, not feasible from the communication side.

This is the first theoretically feasible idea on LL-based Mersenne Coin mining I've heard here, so kudos for that! Practically it is not feasible to store all full residues, or even residues at checkpoints. E.g. a checkpoint every 10,000 residues would allow random spot checking, but might take around 50 GB (figuring p~=65M, 8MB per checkpoint; I don't know if these are valid, but ought to be within an order of magnitude at worst) to store the residues for each candidate.

[E_tron]

Wow, thank you guys for thinking this Mersenne Coin idea through.

What if the Mersenne Coin network was a hybrid of suggested factorization mining and a modified LL-based mining (explored next paragraph)? The Mersenne coin LL-Test reward could increase by an order of magnitude to reward verification of the difficult to verify LL-based coins. Perhaps factorization could yield a much less valuable coin called "GIMPS" (Mersenne Cents ) while the LL-based coins yield several Mersenne Coins. The factorization solution's minimum factor size could vary based upon network difficulty (balancing the influx of LL and factorization horsepower).

My initial thought to drive the Mersenne Coin network was to use the LL test and if it produced a rare digest after a predetermined iteration (say... twenty consecutive zeros after iteration 35433 of candidate M51000003; this point floats based upon network difficulty for predictable coin rewards). In order to get the actual coin reward, the miner would be forced to complete the LL test to completion. Verification would come from several "double check" LL tests on the Mersenne Coin network. A slow solution, but the award should be proportionate compared to mining GIMPS (Mersenne Cents awarded via factorization). Double checkers get a exponentially decreasing Mersenne Coin award (i.e. the first to DC gets award X, 2nd gets less, ect... making 10+ double checks not worthwhile). While this does waste some horsepower, the vast majority of LL Candidates will be run only once (or twice by traditional DC), since very few candidates will produce the twenty 0's demanded for a Mersenne Coin award. The process seems sufficiently random to force LL-based miners to complete their LL tests (and drive the discovery of Mersenne Primes). We've got to figure out a way to make sure bogus results are not verified/rewarded by bogus DC though (still haven't figured that out).

I'm still having difficulty seeing how my LL test idea could drive useful verifiable transactions (since it is slow to verify), however the factorization idea seems to work very well (easy to verify by all in a transaction network similar to bitcoin). To overcome this problem, Mersenne Coins generated by the LL test network would have to obtain some form of verifiable trust with the Factorization network (i.e. inject the LL-Test Mersenne Coins into an "everyday transaction" GIMPS Mersenne Cents network based upon easy to verify Factorization Mining).

Merging this slow LL-test network (Mersenne Coins) with a fast factorization transaction network (GIMPS Mersenne Cents) might work (and drive useful discovery of Mersenne Primes). We've just got to figure out how to "inject with trust" generated LL-Test Mersenne Coins into a "GIMPS Mersenne cents" factorization network.

Again, thank you guys for exploring this idea. I'm having fun with this thought experiment.

[E_tron]

The whole Mersenne Coin idea seems like a good idea. Look at all the horsepower thrown away at scrypt and SHA-256 based cryptocurrency networks. https://www.google.com/search?q=bitc...=u&source=univ If we could capture a small amount of that horsepower, we could greatly increase the productivity of the Great Internet Mersenne Prime Search.

If it get popular, maybe an engineering firm will grace the Mersenne Coin network with a custom built FFT ASiC chip for LL-testing too.

[ewmayer]

Re. monetizing the search, I am concerned about the "ripely perverse behavior" Galbraith notes in the preface to his book which I quoted from.

Hey, speaking of bitcoin:

Anonymous online marketplace that replaced Silk Road VANISHES... taking $100MILLION of users' money with it

Gotta admit I'm finding it hard to shed many tears over this particular tale of woe:

Valued at $45 million, 39,918 in Bitcoins could now be in the hands of a those behind the site after scamming untold numbers of hopeful drug users and gun toters out of their hard earned virtual cash.