20200530, 14:36  #45 
Romulan Interpreter
Jun 2011
Thailand
5^{2}×7^{3} Posts 
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 residuelike 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 20200530 at 14:47 
20200530, 21:12  #46  
"Mihai Preda"
Apr 2015
1,093 Posts 
Quote:
It is similar in a way to finding a factor (hard) and verifying the factor (easy). Or in general, to what is called oneway functions where there is difficutly asymetry between the two directions. Last fiddled with by preda on 20200530 at 21:17 

20200531, 07:35  #47 
"Mihai Preda"
Apr 2015
1,093 Posts 
SHA3 hash
By popular demand (@retina) I changed the hash in the "reference implementation" in gpuowl to SHA3.
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 64bit value of the hash is used (please see the gpuowl source code if interested in details). I hope this raises no concerns. 
20200531, 08:02  #48 
"Mihai Preda"
Apr 2015
1,093 Posts 
Security of the proof
The PRPProof 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 20200531 at 08:04 
20200531, 08:17  #49  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·3^{2}·307 Posts 
OMG I'm popular?
Quote:
People are weird (yes they are) and sooner of later someone will try it. For some brief fame or something. 

20200531, 10:52  #50 
"Mihai Preda"
Apr 2015
1,093 Posts 
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 nontrivial 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.

20200531, 12:02  #51  
"Robert Gerbicz"
Oct 2005
Hungary
10101010010_{2} Posts 
Quote:
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. 

20200531, 15:40  #52  
Sep 2009
1837_{10} Posts 
Quote:
(I've obviously spent too much time looking for ways to break things when I was working on computer security.) Chris 

20200602, 07:59  #53 
"Mihai Preda"
Apr 2015
2105_{8} Posts 
PRPProof file spec moved
The proof file spec is now maintained here:
https://github.com/preda/gpuowl/wiki/PRProofFileSpec Feel free to provide feedback, ask for clarifications, etc. 
20200602, 15:29  #54 
Romulan Interpreter
Jun 2011
Thailand
5^{2}×7^{3} Posts 
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 x1, 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 20200602 at 15:35 
20200602, 16:19  #55 
"Oliver"
Sep 2017
Porta Westfalica, DE
B1_{16} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
phi function  rula  Homework Help  3  20170118 01:41 
delay in crediting?  ixfd64  PrimeNet  7  20081020 20:45 
Why delay between posts?  JHagerson  Forum Feedback  1  20060513 21:30 
Minimum delay between server connections  vaughan  ElevenSmooth  5  20050908 17:17 
Stats delay  ltd  Prime Sierpinski Project  10  20050808 13:38 