mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-06-23, 01:43   #177
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

34×17 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Residues are written to disk as the PRP test progresses. At test end, the residues are read from disk - only one in memory at a time - to produce the proof.

I took "grouped" to mean that we do not raise a residue to the power of a product of hashes (e.g. r0 ^ (h0 * h1 * h2)). My proof-of-concept proof generator is attached. calc_middle is the recursive routine that calculates a Middle value to output.
You could use sliding window technique in void exponentiate (gwhandle *gwdata, gwnum x, uint64_t power) .
R. Gerbicz is offline   Reply With Quote
Old 2020-06-23, 02:32   #178
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

27·32 Posts
Default

Quote:
Originally Posted by Prime95 View Post
I changed my random exponent to a prime number between 33 and 48 bits. Stole some Rosetta C code for Miller-Rabin test.
To allow portable verification of proofs, producers/verifiers must agree exactly on the hash algorithm (identical hash output). To make software errors less likely, it's best not to share the code but to use independent implementations. That's why I try to keep the hash schema simple, to make it easy to specify and independently implement correctly. I don't see yet why it's beneficial to have the hash be prime.
preda is online now   Reply With Quote
Old 2020-06-23, 03:01   #179
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11011011001012 Posts
Default

Quote:
Originally Posted by Prime95 View Post
I changed my random exponent to a prime number between 33 and 48 bits. Stole some Rosetta C code for Miller-Rabin test.
Silly me. The code did not work for 64-bit ints.

Quote:
Originally Posted by preda View Post
To allow portable verification of proofs, producers/verifiers must agree exactly on the hash algorithm (identical hash output). To make software errors less likely, it's best not to share the code but to use independent implementations. That's why I try to keep the hash schema simple, to make it easy to specify and independently implement correctly. I don't see yet why it's beneficial to have the hash be prime.
We're not talking about the hash values. This is the A[N]^random value sent to the user to run topK/(2^N) squarings. The user's result is compared to B[N]^random. Only the Primenet server ever sees the random value.

I haven't coded any hash algorithms yet, pending an agreement on algorithm. My proof-of-concept hash_function is h0=const, h[i]=(prev_hash + 15). I have plenty other work to do.
Prime95 is offline   Reply With Quote
Old 2020-06-23, 04:23   #180
patnashev
 
"Pavel Atnashev"
Mar 2020

37 Posts
Default

Quote:
Originally Posted by preda View Post
So you find R3!=1 such that R3^3==1, ok. You multiply Y (the final residue) by R3, this is the "faked result". What do you next?
Just compute and upload the proof like it's a regular composite number.

Quote:
Originally Posted by preda View Post
If you compute the middles in the usual way from the true saved residues, the proof would not verify. -- isn't that so?
Yes, the proof would not verify, x_t^distance != y_t. But consider the additional anti-cheating step at the end of the certificate generation (x_t^random, y_t^random). If the random is divisible by 3, then R3^random = 1, and y_t turns into true value. The verification passes, but the decision of the primality test is compromised.

This works only for prime numbers and is easy to prevent, just require gcd(random,N-1)=1. Alternatively, if N-1 has specific form, you can test just specific factors. Proth N-1 is very smooth, Mersenne N-1 has divisors that look like Mersenne numbers themselves (if I understand correctly).

Also consider the possible real world scenarios, which apply to all such cheating schemes. If you going to cheat with 1/1000 chance of success, you better hit it at the first time. Because if you fail, instead of being credited with a prime find you'll be banned from the prime universe.
patnashev is offline   Reply With Quote
Old 2020-06-23, 05:00   #181
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

48016 Posts
Default

Quote:
Originally Posted by Prime95 View Post
We're not talking about the hash values. This is the A[N]^random value sent to the user to run topK/(2^N) squarings. The user's result is compared to B[N]^random. Only the Primenet server ever sees the random value.
Quote:
Originally Posted by patnashev View Post
Just compute and upload the proof like it's a regular composite number.

Yes, the proof would not verify, x_t^distance != y_t. But consider the additional anti-cheating step at the end of the certificate generation (x_t^random, y_t^random). If the random is divisible by 3, then R3^random = 1, and y_t turns into true value. The verification passes, but the decision of the primality test is compromised.

This works only for prime numbers and is easy to prevent, just require gcd(random,N-1)=1. Alternatively, if N-1 has specific form, you can test just specific factors. Proth N-1 is very smooth, Mersenne N-1 has divisors that look like Mersenne numbers themselves (if I understand correctly).
It seems I was misunderstanding, thinking that you're talking about the hash algorithm and the whole 64/48/32 bits discussion. Instead you were talking about the random used for the final verification, which is server's business only. I have absolutely nothing against using primes or whatever for that final random.

For the hash algorithm, the question still stands whether any hardening is needed. Unless hardening in shown to be needed, the simple truncation of SHA3-256 of the agreed-upon size should be used as being the simplest.
preda is online now   Reply With Quote
Old 2020-06-23, 08:13   #182
patnashev
 
"Pavel Atnashev"
Mar 2020

3710 Posts
Default

I use 64-bit md5 with no divisors <1000 "just in case". But I see the appeal of shorter unhardened hashes. Server load is linear with hash size.
patnashev is offline   Reply With Quote
Old 2020-06-23, 09:12   #183
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

34·17 Posts
Default

Quote:
Originally Posted by Prime95 View Post
My proof-of-concept proof generator is attached. calc_middle is the recursive routine that calculates a Middle value to output.
With those recursive calls it will use power residues in stack memory.
Is it intended? You could do this also in disk (using the same size).
R. Gerbicz is offline   Reply With Quote
Old 2020-06-23, 11:13   #184
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

27×32 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
With those recursive calls it will use power residues in stack memory.
Is it intended? You could do this also in disk (using the same size).
That's fine, in this case the max amount of residues alive at any time because of the recursion is the max-depth of the recursion, equal to the "power" of the proof. That would be under 1GB total normally.

Edit: I missed "on the stack". I think they are not on the stack, but on the heap (gwalloc/gwfree)

Last fiddled with by preda on 2020-06-23 at 11:19
preda is online now   Reply With Quote
Old 2020-06-23, 15:30   #185
patnashev
 
"Pavel Atnashev"
Mar 2020

2516 Posts
Default

Brute-force attack:
Code:
for (h0 = 1; h0 < max_hash; h0++)
{
    y = x^(h0*h0);
    u_1 = x^(-h0);
    if (hash(y) == h0)
        break;
}
u_i[i>1] = 1;
patnashev is offline   Reply With Quote
Old 2020-06-23, 19:08   #186
wedgingt
 
"Will Edgington"
Nov 2010
Utah, USA

23·3 Posts
Default Possible flexible file format

The ecm program (which uses libgmp) has a simple format for P-1 and P+1 save files:

Code:
METHOD=P+1; B1=4299950000; N=71214505243381290342289358884062903424409248782929244751545497061659676830181069893652125357260888204241872521545920863671266091156523160599053871978101713571014846232692265302193576
41629634637632902818929376633641165995708421341209033069328278856607776384578328080846029713646218471064646270016968312691054210973840071649700163924918271; X=0x41a4cc7860dfb15fcdd98bcdbccc9b8b63796ad4e38c6fb055
967b800ea0c27fb8c1b5ff8f2a1d87c50196bc5869ced0d93597a447d7f7e233ead9e7036256b64a1ce7720274b605632205655335a629c10691284cce6ef7528b871a71e7e022c4ccc5a152b6e6b858dcda73ba0fde2f769912d837a4b164d5626ad62bc0752b2f7a1
73626a51231ba139d12; CHECKSUM=3059612973; PROGRAM=GMP-ECM 7.0.4; Y=0x0; X0=0xf7b36de6; Y0=0x0; WHO=wedgingt@wedgingt; TIME=Thu Apr 11 13:58:53 2019
This example is for M1207; the N value here is M1207 itself since there are no known factors. B1 is the stage 1 bound of P+1 and X is the residue mod M1207. I already have a small Perl module to deal with this format that allows arbitrary values and "keys" (like METHOD, B1, and N) and it could easily be supported in Python as well.


-- Will


Quote:
Originally Posted by Prime95 View Post
Let's change "exponent" to number being proved - in gpuowl's case "Mexponent". When prime95 adds PRP proofs, the number being PRP'ed can be (k*b^n+/-c)/known_factors.
Examples: M1234567, M4321/8768767, 653*3^123456-15

We need a file naming scheme. I've not done any research, but suggest a .proof or .vdf extension. So for a Mersenne number, Mexponent.proof. For a Mersenne cofactor, maybe Mexponent_cofactor.proof or Mexponent_number_known_factors.proof. I'll come up with something for the more general (k,b,n,c) case.
wedgingt is offline   Reply With Quote
Old 2020-06-23, 21:54   #187
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

27×32 Posts
Default

Quote:
Originally Posted by patnashev View Post
Brute-force attack:
Code:
for (h0 = 1; h0 < max_hash; h0++)
{
    y = x^(h0*h0);
    u_1 = x^(-h0);
    if (hash(y) == h0)
        break;
}
u_i[i>1] = 1;
The above attack would not be practical for 32-bit hash already, as it require in average 2B loopings, and each loop body requires significant work.

The attack would be so-much-more less practical for 48 or 64 bit hash. So, I'd take the above attack more like an indication of "lack of a practical attack", right?

Last fiddled with by preda on 2020-06-23 at 21:55
preda 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 11:52.

Fri Aug 7 11:52:02 UTC 2020 up 21 days, 7:38, 1 user, load averages: 3.22, 2.66, 2.49

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.