The Next Big Development for GIMPS

[Prime95]

In case some have missed it, there is discussion in an innocuously worded thread about a strategy to eliminate the need for double-checking. A PRP tester also produces (rather cheaply) a proof that they did the work and that is is correct. This proof is then verified, also rather cheaply, by PrimeNet itself (ideal) or another user. Mihai has done a great job explaining how it works.

Adapting this to GIMPS requires some decisions to be made.
1) There are proposals to weaken the security in order to greatly reduce temporary storage needed by the PRP tester. Math and security experts are needed to convince us that this would not weaken security too much.
2) There are tradeoffs that need to be considered regarding proof file size, runtime costs, and bandwidth costs. An AWS or other cloud developer could greatly help in determining how much it would cost to set up and run a cloud based verifier, move big proof files around the Internet cheaply, and perhaps store the proofs forever.
3) Users could weigh in on whether such a proof system would be palatable to them. It comes with increased temporary file storage and increased bandwidth costs.

Double-checking has always lagged first-time testing and the lag gets worse every year. Imagine if 90% of the first time tests did not need a DC? Double-checking could close the gap within a few years.

[kladner]

Bandwidth and temp storage are not issues for me unless the storage needs are in the terabyte range.

[kriesel]

Originally Posted by Prime95

In case some have missed it, there is discussion in an innocuously worded thread about a strategy to eliminate the need for double-checking. ..
Adapting this to GIMPS requires some decisions to be made.
...
3) Users could weigh in on whether such a proof system would be palatable to them. It comes with increased temporary file storage and increased bandwidth costs.

Double-checking has always lagged first-time testing and the lag gets worse every year. Imagine if 90% of the first time tests did not need a DC? Double-checking could close the gap within a few years.

Does it matter whether end users weigh in on this thread or the other? I think the other would be good to leave primarily for the technical math discussion.
How palatable the proof system will be depends on the local data size requirements. Which I think are still in flux while the other driving details and design decisions are.
The current PRP/LL ratio seems closer to 3:1 than 9:1 based on a brief sampling of recent results. It makes sense to me that eliminating need for DC on some future PRP would drive greater adoption or preferential assignment of PRP, widening the ratio.
The growth in and long duration of DC delay has been a concern for a while. (Up to 10 years delay on some exponents.)
Overall, exciting news.

[Prime95]

Originally Posted by kriesel

Does it matter whether end users weigh in on this thread or the other? I think the other would be good to leave primarily for the technical math discussion.

I agree, let other thread be technical.

[S485122]

Concerning the ratio PRP/LL, most participants are not very active, they set and forget, which is why very old versions of Prime95 are still reporting results. AFAIK most GIMPS participants don't care and even don't know how the exponents are tested.
What could be done is for the PrimeNet server to treat LL and PRP as one category : give PRP tests to do whenever the software is up to to it (unless the user explicitly configures the software to do LL tests and no PRP's.) The assignment distinction between the two methods was logical when PRP was introduced, it is counterproductive now.

Another thing that could be done is for Primenet to assign more double-checks to diminish the gap with the first time tests. Unless a user deliberately sets a value, it would do one DC in seven tests (to stay with Mersenne primes : - ) Of course this change, if implemented should take into account the other considerations detailed in Assignment Rule Change (why did I get a double-check?).

As to the need of double-checking, it is not only a way to detect faulty hardware. It is also a way to detect errors in the software. The proof could be theoretically sound, avoiding errors in software is hard. There should be a way to verify with a totally different software that the residue is correct. And sample verifications should be executed regularly. This last point is another argument against self-verification in parallel : one and the same software is used for the test and its verification (this remark is not directed to any particular user : - D

Jacob

[M344587487]

• Has anyone proposed the need to DC the verification step? If it's as cheap to compute as it seems it seems sensible to make that the new "don't trust a single source" step.
• If we're talking 50+MiB upload per test that excludes a minor subset from participating. I'm thinking more of those that manually batch test offline and potentially have gigabytes to burst transfer each batch instead of just a small text file. A few online users will be affected too but most have enough monthly bandwidth to not notice a periodic upload. I can't see any way around the new process having to be opt-in as the requirements have changed, if it comes to it computers that don't opt-in should be given DC work even if they request primary work, assuming we want the old method to be deprecated.
• Has any thought been put into scheduling uploads asynchronous to completing the test? A short result message sent for the status with a checksum of the verification file on test completion, and a user-definable upload window for the verification files. Some connections are affected by background uploads or restrictions at peak hours that would make live uploading burdensome.
• If the idea is for users to perform the verification step as-well-as/in-place-of a central computer, torrents may be the way to handle verification uploads. Instead of directly uploading, the client creates a torrent using a GIMPS tracker that the GIMPS server automatically leeches from. Once the GIMPS server has a complete copy of the verification file the original tester may or may not disconnect from the torrent as they wish (if they stay they reduce the burden on the GIMPS server by being another source for a verifier to download from). The file is then available for another user to verify, the GIMPS server sends them a magnet link to download the file. As a bonus this would solve the problem of uploading largish files from a spotty connection (where for normal uploads partial uploading is inevitable and resuming a partial upload doesn't always work). I always download Linux images via torrent where possible as a direct download that large fails regularly and doesn't always resume as it should.

[Fan Ming]

Originally Posted by S485122

Concerning the ratio PRP/LL, most participants are not very active, they set and forget, which is why very old versions of Prime95 are still reporting results. AFAIK most GIMPS participants don't care and even don't know how the exponents are tested.

But many users are active. And with proper guide, many new participants have enough power to do this. Even don't, it's a fact that this alternative can save >0 compute power, even one exponent don't need double check, it's a progress.

Another thing that could be done is for Primenet to assign more double-checks to diminish the gap with the first time tests. Unless a user deliberately sets a value, it would do one DC in seven tests (to stay with Mersenne primes : - ) Of course this change, if implemented should take into account the other considerations detailed in Assignment Rule Change (why did I get a double-check?).

Jacob

The aim of this VDF proof is to eliminate a lot of required computation power(i.e. double check), and "closing the double check gap" is an effect. I believe that's what George means in the last part instead of "the gap of DC and first-time test is larger and larger, we should solve this problem". Assigning more double check assignments is unnecessary and improper, and also controversal with the goal of GIMPS.

I haven't view it carefully and my math background is not deep either, so I can't judge whether this VDF is indeed feasible and safe either.
But if my understanding is correct, if we set r1=r2=...=1 in the verification progress(as mentioned in this post: https://www.mersenneforum.org/showpo...9&postcount=14), is it just like doing a single "weak" GEC? We indeed need a person to look this deeply and to judge whether it's actually safe.

[ATH]

I have not read and tried to understand the math in the other thread but I followed the discussion a bit, and you talk a lot about security against people who wants to fake the work and result which is important.

But will this test also ensure that the calculation itself and final residue is correct against hardware and software errors during the test?

[axn]

Originally Posted by ATH

But will this test also ensure that the calculation itself and final residue is correct against hardware and software errors during the test?

Yes. That is also part of the goal. Verification validates that the work was done and was done correctly.

[kriesel]

Originally Posted by M344587487

• Has anyone proposed the need to DC the verification step?
• If we're talking 50+MiB upload per test that excludes a minor subset from participating. I'm thinking more of those that manually batch test offline and potentially have gigabytes to burst transfer each batch instead of just a small text file. A few online users will be affected too but most have enough monthly bandwidth to not notice a periodic upload. I can't see any way around the new process having to be opt-in as the requirements have changed, if it comes to it computers that don't opt-in should be given DC work even if they request primary work, assuming we want the old method to be deprecated.
• Has any thought been put into scheduling uploads asynchronous to completing the test? A short result message sent for the status with a checksum of the verification file on test completion, and a user-definable upload window for the verification files. Some connections are affected by background uploads or restrictions at peak hours that would make live uploading burdensome.
• If the idea is for users to perform the verification step as-well-as/in-place-of a central computer, torrents may be the way to handle verification uploads. Instead of directly uploading, the client creates a torrent using a GIMPS tracker that the GIMPS server automatically leeches from. Once the GIMPS server has a complete copy of the verification file the original tester may or may not disconnect from the torrent as they wish (if they stay they reduce the burden on the GIMPS server by being another source for a verifier to download from). The file is then available for another user to verify, the GIMPS server sends them a magnet link to download the file. As a bonus this would solve the problem of uploading largish files from a spotty connection (where for normal uploads partial uploading is inevitable and resuming a partial upload doesn't always work). I always download Linux images via torrent where possible as a direct download that large fails regularly and doesn't always resume as it should.

• Yes to your first point, that has been discussed in the technical thread
• Assume 50MB/PRPverify. Eyeball average primality tests returned per day preCOVID19, 900/day. https://www.mersenne.org/primenet/graphs.php So some small N times 50 x 900, assume N=4; client to server, server to AWS verifier, server to volunteer verifier DC, that's 3. PrimeNet verification result reports are smaller and can be neglected. Allow hefty overhead, say pessimistically 33% for ECC and other overhead adding to transmission size, equivalent to a fourth. 4 x 50 x 900 MB = 180GB/day traffic, all of which flows into or from the PrimeNet server in this assumed configuration; ~16.7Mbits/second average rate. Consumer fiber or cable links could handle that, although the provider may take exception to the large regular load. Madpoo or someone should weigh in on the economics and terms of PrimeNet's network service. Maybe the contemplated configuration is that the PrimeNet server hands out the assignments to clients (small message size, so low traffic volume) and the clients all deal with their share of the high data size traffic directly with the contemplated AWS service. That cuts N by an amount that's one or somewhat more. An unfortunate dialup modem user probably won't be happy. Using a ballpark 20 kbits/second upload rate without compression, one 50MB PRP proof file is 5.5 hours if it works; download at a full US ideal 53.3 kbaud rate is a bit over 2 hours each. He may want to haul them to the local library or McDonalds on a laptop and use their multiMBsec free wireless instead.
• Re scheduling the uploads, prime95 already spools ordinary length results and sends them when it can, and has schedulable memory usage. Making available an option for scheduling the big verification uploads window sounds like a good suggestion to me. Having tens or hundreds of MB coincide with and heavily load an uplink can make interactive use sluggish. Not good while many are working from home via remote desktop and VPN, teleconferencing, etc.
• I trust the PrimeNet server to be well managed and secured, and any AWS additional service employed, FAR more than I trust all 5000+ users' client systems to be free enough of malicious stuff. Requiring torrent peering among all may be an authorization showstopper for a lot of users and systems. Employers may be very unenthusiastic about allowing that.

[kriesel]

Efficient Proth/PRP Test Proof Scheme thread
https://mersenneforum.org/showthread...633#post538633