mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-05-30, 14:36   #45
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52×73 Posts
Default

You got me wrong, I am not "against" improving the current situation (which indeed, kinda sucks! and this is known for long time, and it was discussed repeatedly on the forum!). My objection is ONLY to the phrase I quoted. I highly salute your initiative and effort, and I am convinced you CAN improve the things (as explained below). I just want to stress out that you CANNOT eliminate DC with things like GC, or VDF.

A proof of work is easy to implement, but that only shows that you did the work, not that the work is correct. If an unlucky bit flips, you are screwed, and yet the proof of work is valid.

On the other hand, any residue-like information you got after any kind of test you do, which can be verified in x% of the time of a test as being correct, can also be produced in about the same x% of the time of a test, without doing the test, just following the same steps that the "verifier" would do. If you can do that, then you just discovered a new testing method that only takes x% of the LL/PRP tests, and well, who will need LL/PRP anymore? GC, by the way, is just a probabilistic stuff, and accepting it without a DC is the same as accepting a probable prime as being prime without a rigorous proof. Actually, a bit worse, probabilistic.

So, yes, PLEASE make the LL/PRP/whatever tests, more error proof, more cheat proof, more whatever proof, we will help where we can, like we can help with testing, even give you access to our toys, or even help with math, but don't expect to eliminate DCs until your "tests" can also produce a factor. Maybe my understanding of all these things is plain wrong... but I can't see any other way to eliminate the DCs.

Last fiddled with by LaurV on 2020-05-30 at 14:47
LaurV is offline   Reply With Quote
Old 2020-05-30, 21:12   #46
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

1,093 Posts
Default

Quote:
Originally Posted by LaurV View Post
A proof of work is easy to implement, but that only shows that you did the work, not that the work is correct. If an unlucky bit flips, you are screwed, and yet the proof of work is valid.

On the other hand, any residue-like information you got after any kind of test you do, which can be verified in x% of the time of a test as being correct, can also be produced in about the same x% of the time of a test, without doing the test, just following the same steps that the "verifier" would do. If you can do that, then you just discovered a new testing method that only takes x% of the LL/PRP tests, and well, who will need LL/PRP anymore?
The PRP-Proof discussed here is not a proof of work, it is a proof of the corectness of the PRP residue (at iteration topK). While it can be verified by anybody fast, in can not be generated faster than doing the PRP test. Your assertion above that the verifier could produce the proof in the same amount of time as the verification by "following the same steps" simply does not hold.

It is similar in a way to finding a factor (hard) and verifying the factor (easy). Or in general, to what is called one-way functions where there is difficutly asymetry between the two directions.

Last fiddled with by preda on 2020-05-30 at 21:17
preda is offline   Reply With Quote
Old 2020-05-31, 07:35   #47
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

1,093 Posts
Default SHA-3 hash

By popular demand (@retina) I changed the hash in the "reference implementation" in gpuowl to SHA-3.

The hash is run with an output of 256bits. This full output (256bits) is chained (when generating the sequence of hashes such as h1=hash(h0, M1) etc) but when computing the exponents a truncated 64-bit value of the hash is used (please see the gpuowl source code if interested in details). I hope this raises no concerns.
preda is offline   Reply With Quote
Old 2020-05-31, 08:02   #48
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

1,093 Posts
Default Security of the proof

The PRP-Proof is based on Pietrzak's VDF article. The math in Pietrzak's article is solid, but I think our setup departs from Pietrzak's assumptions in one aspect. I'd like to explicitly disclose this here before it's "exposed as a fatal flaw of the proof".

In my understanding (math people please correct me), the proof becomes weak (can be faked) if the author knows a factorization of the modulo (the mersenne candidate in our case).

But the case we want to be protected against through the proof mecanism is the situation of a mersenne prime acquiring a false proof showing it being composite. This is not possible because, for a prime, the proof cannot be faked (because no factorization is available).

[maybe] the theoretical possibility remains that an agent may produce a fake proof of a composite candidate being prime based on a factor known to the agent. While this possibility is slightly annoying, it's not dangerous because such a case would be exposed immediatelly because of the interest in the new presumed prime.

Last fiddled with by preda on 2020-05-31 at 08:04
preda is offline   Reply With Quote
Old 2020-05-31, 08:17   #49
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2·32·307 Posts
Default

Quote:
Originally Posted by preda View Post
By popular demand (@retina) ...
OMG I'm popular?

Quote:
Originally Posted by preda View Post
[maybe] the theoretical possibility remains that an agent may produce a fake proof of a composite candidate being prime based on a factor known to the agent. While this possibility is slightly annoying, it's not dangerous because such a case would be exposed immediatelly because of the interest in the new presumed prime.
If you know a factor that no one has then ...

People are weird (yes they are) and sooner of later someone will try it. For some brief fame or something.
retina is online now   Reply With Quote
Old 2020-05-31, 10:52   #50
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

1,093 Posts
Default

Quote:
Originally Posted by retina View Post
If you know a factor that no one has then ...

People are weird (yes they are) and sooner of later someone will try it. For some brief fame or something.
Yes, but it's not a problem. First, it may be difficult to build such a proof even knowing a factorization of the candidate (it may well be more difficult than just running the PRP the honest way). I say if somebody does do it, they deserve kudos for the non-trivial analysis effort and for showing that it can be done. And for the project (GIMPS) it's not a big deal to have somebody claim a prime that wasn't.
preda is offline   Reply With Quote
Old 2020-05-31, 12:02   #51
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101010100102 Posts
Default

Quote:
Originally Posted by preda View Post
Yes, but it's not a problem. First, it may be difficult to build such a proof even knowing a factorization of the candidate (it may well be more difficult than just running the PRP the honest way). I say if somebody does do it, they deserve kudos for the non-trivial analysis effort and for showing that it can be done. And for the project (GIMPS) it's not a big deal to have somebody claim a prime that wasn't.
With a knowledge of a new factor (after the published proof) actually the verifier will have an advantage to catch cheaters even in a faster way:
just check ((g^(2^L) mod N) mod q), where the g^(2^L) mod N is a single residue from the proof. If it isn't g^(2^L) mod q then gotcha, the proof is broken. And for this you need only one full residue and the cheater has only 1/q chance to fake it whatever he does.
R. Gerbicz is offline   Reply With Quote
Old 2020-05-31, 15:40   #52
chris2be8
 
chris2be8's Avatar
 
Sep 2009

183710 Posts
Default

Quote:
Originally Posted by preda View Post
In my understanding (math people please correct me), the proof becomes weak (can be faked) if the author knows a factorization of the modulo (the mersenne candidate in our case).
Would that make it possible for someone who has found a factor to report a bogus proof it's composite, thus appearing to have done a lot more work than they really did? It's not a big issue because the number would really be composite but might be used to move up the work done table.

(I've obviously spent too much time looking for ways to break things when I was working on computer security.)

Chris
chris2be8 is offline   Reply With Quote
Old 2020-06-02, 07:59   #53
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

21058 Posts
Default PRP-Proof file spec moved

The proof file spec is now maintained here:
https://github.com/preda/gpuowl/wiki/PRProof-File-Spec

Feel free to provide feedback, ask for clarifications, etc.
preda is offline   Reply With Quote
Old 2020-06-02, 15:29   #54
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52×73 Posts
Default

I still didn't get how this works.

1. I am reserving Mx for PRP.
2. I generate x random residues in a file, without doing any work, just garbage data.
3. I apply your calculus on my garbage data and generate the verification file.
4. I send it to PrimeNet and get the LL/PRP credit in just 5 minutes (including the "trusted" particle attached to it, because it is verified, you know?).

Which of this step would be impossible, and why?

Of course the first is not necessary, I don't want to create suspicion by reporting results at a very short time after reservation, so I will just report results, without reservation.

Of course, I understand the part that there is some relation between some residues in that list, and they are not totally random, but this is where we are stuck. Say the residue at iteration h has some relation with residue at iteration k. Then either there is a small difference between h and k (to allow the verification process to be fast, without a lot of squarings) and in this case I can also produce this relation fast, starting with a random h (and squaring, or whatever), or either there is a large distance between h and k, to be difficult for me to fake it, but then in such case you have to spend a huge amount of time to verify it (practically repeating a part of the initial test, and yet, being unsure the iteration h was true, except when it was the first). What we are currently doing today, h is 1 and k is x-1, and the verification process is called "Double Checking", except we just use residues directly, and not hashes of them.

Last fiddled with by LaurV on 2020-06-02 at 15:35
LaurV is offline   Reply With Quote
Old 2020-06-02, 16:19   #55
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

B116 Posts
Default

Quote:
Originally Posted by preda View Post
Feel free to provide feedback, ask for clarifications, etc.
What about having an EOF (0x1A) after the \n like in the PNG header? That way cat etc. will exit after printing the header.
kruoli is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
phi function rula Homework Help 3 2017-01-18 01:41
delay in crediting? ixfd64 PrimeNet 7 2008-10-20 20:45
Why delay between posts? JHagerson Forum Feedback 1 2006-05-13 21:30
Minimum delay between server connections vaughan ElevenSmooth 5 2005-09-08 17:17
Stats delay ltd Prime Sierpinski Project 10 2005-08-08 13:38

All times are UTC. The time now is 14:54.

Fri Jul 3 14:54:48 UTC 2020 up 100 days, 12:27, 2 users, load averages: 1.75, 1.39, 1.48

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.