mersenneforum.org > Math VDF (Verifiable Delay Function) and PRP
 Register FAQ Search Today's Posts Mark Forums Read

2020-06-23, 01:43   #177
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

139310 Posts

Quote:
 Originally Posted by Prime95 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) .

2020-06-23, 02:32   #178
preda

"Mihai Preda"
Apr 2015

29·41 Posts

Quote:
 Originally Posted by Prime95 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.

2020-06-23, 03:01   #179
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

7×1,021 Posts

Quote:
 Originally Posted by Prime95 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 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.

2020-06-23, 04:23   #180
patnashev

"Pavel Atnashev"
Mar 2020

43 Posts

Quote:
 Originally Posted by preda 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 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.

2020-06-23, 05:00   #181
preda

"Mihai Preda"
Apr 2015

29·41 Posts

Quote:
 Originally Posted by Prime95 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 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.

 2020-06-23, 08:13 #182 patnashev   "Pavel Atnashev" Mar 2020 43 Posts 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.
2020-06-23, 09:12   #183
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

7×199 Posts

Quote:
 Originally Posted by Prime95 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).

2020-06-23, 11:13   #184
preda

"Mihai Preda"
Apr 2015

29×41 Posts

Quote:
 Originally Posted by R. Gerbicz 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

 2020-06-23, 15:30 #185 patnashev   "Pavel Atnashev" Mar 2020 43 Posts 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;
2020-06-23, 19:08   #186
wedgingt

"Will Edgington"
Nov 2010
Utah, USA

2410 Posts
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
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 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.

2020-06-23, 21:54   #187
preda

"Mihai Preda"
Apr 2015

29·41 Posts

Quote:
 Originally Posted by patnashev 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

 Similar Threads Thread Thread Starter Forum Replies Last Post rula Homework Help 3 2017-01-18 01:41 ixfd64 PrimeNet 7 2008-10-20 20:45 JHagerson Forum Feedback 1 2006-05-13 21:30 vaughan ElevenSmooth 5 2005-09-08 17:17 ltd Prime Sierpinski Project 10 2005-08-08 13:38

All times are UTC. The time now is 13:28.

Sat Sep 19 13:28:28 UTC 2020 up 9 days, 10:39, 1 user, load averages: 1.05, 1.21, 1.30