mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > News

Reply
 
Thread Tools
Old 2020-06-16, 20:52   #1
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

714110 Posts
Default The Next Big Development for GIMPS

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.

Last fiddled with by Prime95 on 2020-08-05 at 03:23
Prime95 is offline   Reply With Quote
Old 2020-06-16, 22:54   #2
kladner
 
kladner's Avatar
 
"Kieren"
Jul 2011
In My Own Galaxy!

2×3×1,667 Posts
Default

Bandwidth and temp storage are not issues for me unless the storage needs are in the terabyte range.
kladner is offline   Reply With Quote
Old 2020-06-16, 23:35   #3
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

4,643 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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.
kriesel is offline   Reply With Quote
Old 2020-06-17, 00:58   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

37×193 Posts
Default

Quote:
Originally Posted by kriesel View Post
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.
Prime95 is offline   Reply With Quote
Old 2020-06-17, 06:22   #5
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

110001100002 Posts
Default

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
S485122 is offline   Reply With Quote
Old 2020-06-17, 09:05   #6
M344587487
 
M344587487's Avatar
 
"Composite as Heck"
Oct 2017

23×83 Posts
Default

  • 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.
M344587487 is offline   Reply With Quote
Old 2020-06-17, 10:48   #7
Fan Ming
 
Oct 2019

5·19 Posts
Default

Quote:
Originally Posted by S485122 View Post
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.

Quote:
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.

Last fiddled with by Fan Ming on 2020-06-17 at 10:52
Fan Ming is offline   Reply With Quote
Old 2020-06-17, 11:41   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

56318 Posts
Default

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?
ATH is online now   Reply With Quote
Old 2020-06-17, 13:39   #9
axn
 
axn's Avatar
 
Jun 2003

4,721 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
axn is online now   Reply With Quote
Old 2020-06-17, 15:40   #10
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

4,643 Posts
Default

Quote:
Originally Posted by M344587487 View Post
  • 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.

Last fiddled with by kriesel on 2020-06-17 at 15:45
kriesel is offline   Reply With Quote
Old 2020-06-17, 16:36   #11
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

4,643 Posts
Default Worth a read for background (Thanks Pavel!)

Efficient Proth/PRP Test Proof Scheme thread
https://mersenneforum.org/showthread...633#post538633
kriesel is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Your help wanted - Let's buy GIMPS a KNL development system! airsquirrels Hardware 313 2019-10-29 22:51
Is GMP-ECM still under active development? mathwiz GMP-ECM 0 2019-05-15 01:06
LLR 3.8.6 Development version Jean Penné Software 0 2011-06-16 20:05
LLR 3.8.5 Development version Jean Penné Software 6 2011-04-28 06:21
LLR 3.8.4 development version is available! Jean Penné Software 4 2010-11-14 17:32

All times are UTC. The time now is 05:03.

Sat Oct 31 05:03:00 UTC 2020 up 51 days, 2:13, 2 users, load averages: 1.55, 1.67, 1.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.