mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-06-14, 05:12   #100
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7×1,021 Posts
Default

With these advances in the cost of creating a proof, we need to consider power=11,12 ... maybe even 13 or more for a 100M test. Each halving of the work the verifier must perform makes an AWS solution more attractive (cheaper). If 600 PRP tests a day can be verified with ~600*100000000/4096 = 15 million PRP iterations, then just a few AWS instances could be running at spot pricing to easily keep up. We definitely need an experienced AWS person to weigh in on the feasibility and daily cost of such a setup. I really, really, really like all PRP proofs being verified by a single trusted setup rather than assignments to random folks on the internet.

The proof file format should change in a minor way. The preferred topK value should be the next multiple of 2^power above the exponent. That is what prime95 will do.

Last fiddled with by Prime95 on 2020-06-14 at 05:14
Prime95 is offline   Reply With Quote
Old 2020-06-14, 05:58   #101
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7×199 Posts
Default

Quote:
Originally Posted by Prime95 View Post
So for preda's power==9 example, we'll do 511 exponentiations (each costing 63 squarings plus on average 31.5 multiplications) and 511 multiplications. Assume multiply cost approximately equals squaring cost and we get a total proof building cost of 48,800 PRP iterations.
You forget the topK/2^e squarings. And there is no other cost in the proof.

Quote:
Originally Posted by Prime95 View Post
Now a question. Are we gaining anything by using a 64-bit h value? Why not 32 or 16 bits reducing cost to 24,300 or 12,000 PRP iterations.
Maybe the original paper talked about 64 bit values, I'd say 16 bits would be still OK.
R. Gerbicz is offline   Reply With Quote
Old 2020-06-14, 06:50   #102
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

52×229 Posts
Default

Since the proof file is going to be deleted once it has been sufficiently checked, then I suggest to have the server permanently save the normal 64-bit residue (like we have now) so that any interested parties can run a full test to verify the integrity.

If some future researcher were to randomly choose candidate exponents and check the PRP against the 64-bit residue it would give good confidence that all the numbers were really run.
retina is online now   Reply With Quote
Old 2020-06-14, 07:38   #103
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7×199 Posts
Default

Quote:
Originally Posted by Prime95 View Post
With these advances in the cost of creating a proof, we need to consider power=11,12 ... maybe even 13 or more for a 100M test.
That doesn't needs uploading 2^power full residues per test?
R. Gerbicz is offline   Reply With Quote
Old 2020-06-14, 07:46   #104
axn
 
axn's Avatar
 
Jun 2003

13×192 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Each halving of the work the verifier must perform makes an AWS solution more attractive (cheaper). If 600 PRP tests a day can be verified with ~600*100000000/4096 = 15 million PRP iterations, then just a few AWS instances could be running at spot pricing to easily keep up.
This sounds like a use case for AWS Lambda (serverless) set up. Probably not the cheapest option, though.
axn is offline   Reply With Quote
Old 2020-06-14, 08:07   #105
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

29×41 Posts
Default

Quote:
Originally Posted by Prime95 View Post
I believe we can reduce the space cost considerably. We are saving 2^power residues because we cannot know the values of h0, h1, h2, h3 ... until the PRP completes. In the academic paper, this is because the author and the prover cannot communicate in advance. We can!

I propose the h values be predetermined by the some formula agreement. The author still has no ability to select the h values, thus the proof is still safe from fakery. Here's one proposal: h0 = sha256("We love PRP proofs" || exponent). h1 = sha256(h0 || exponent), etc.

knowing the h-values in advance reduces temp space requirement from 2^power residues to power residues.
I thought about that too, but I think it doesn't work. The core idea of the "Shamir heuristic", which allows to transform the interactive proof into an non-interactive one, requires that the author *can not* change any bit of the result without also changing the "challenge values" (in our case, the hashes).

If the hashes are fixed ahead of time (including fixed "per exponent" as you propose), this kind of attack becomes possible:

The verification is:
(A^h * M)^q == M^h * B. (where q=2^k, but that's not important)

If "h" is fixed, the attacker can satisfy the equality by using
B:= (A^h)^q * M^(q-h)

which represents a cheat. (this line of attack does not work if "h" is backward-dependent on B)

Last fiddled with by preda on 2020-06-14 at 08:17 Reason: rusty algebra
preda is offline   Reply With Quote
Old 2020-06-14, 08:20   #106
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

118910 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
That doesn't needs uploading 2^power full residues per test?
What needs uploading is the proof. The proof contains "only" (power + 1) residues.
preda is offline   Reply With Quote
Old 2020-06-14, 08:29   #107
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

29×41 Posts
Default

Quote:
Originally Posted by Prime95 View Post
With these advances in the cost of creating a proof, we need to consider power=11,12 ... maybe even 13 or more for a 100M test. Each halving of the work the verifier must perform makes an AWS solution more attractive (cheaper). If 600 PRP tests a day can be verified with ~600*100000000/4096 = 15 million PRP iterations, then just a few AWS instances could be running at spot pricing to easily keep up. We definitely need an experienced AWS person to weigh in on the feasibility and daily cost of such a setup. I really, really, really like all PRP proofs being verified by a single trusted setup rather than assignments to random folks on the internet.

The proof file format should change in a minor way. The preferred topK value should be the next multiple of 2^power above the exponent. That is what prime95 will do.
OK for defining topK to be the first multiple of 2^power after the exponent.

(My initial idea of having topK a multiple of a fixed power of 2 originated from my desire to be able to generate proofs of different powers from the same set of "saved residues" from a PRP test; (this was mainly for debugging). I don't think we need this feature anymore, and thus the first multiple of 2^power is the natural choice for topK)

I have an idea for how to speed up the proof generation for higher powers. Then power==14 becomes feasible. There a verification would cost about 8K iterations, yay! I'll try to validate this.

Correction: with power==14 the tail (the iterations past E up to topK) will be 8K iterations on average, thus the total average cost of about 16K iterations, or 24K if the verifier also computes prp(9, topK - E) to decide compositeness. Thus power==14 is too large.

power==13 would have a tail of 4K iterations on average. Thus total verification cost estimated to 2K + 12K + 2*4K == 22K iterations for a 100M exponent.
power==12, tail of 2K, verification estimated 2K + 25K + 2*2K == 31K iterations. (the first 2K approximates the cost of the exponentiations in the "walking the middles" part of verification)
power==11, tail of 1K, estimated cost 2K + 50K + 2*1K == 54K its.

Maybe power==12 looks like a good choice then?

Last fiddled with by preda on 2020-06-14 at 08:53
preda is offline   Reply With Quote
Old 2020-06-14, 09:04   #108
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

29·41 Posts
Default

Quote:
Originally Posted by Prime95 View Post
The proof file format should change in a minor way. The preferred topK value should be the next multiple of 2^power above the exponent. That is what prime95 will do.
Now the topK is not store in the file anymore. It is defined to be what we spec here. (an implicit value, not stored in the file, not hashed).
preda is offline   Reply With Quote
Old 2020-06-14, 09:13   #109
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

4A516 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Now a question. Are we gaining anything by using a 64-bit h value? Why not 32 or 16 bits reducing cost to 24,300 or 12,000 PRP iterations.
The size of the hash gives the security of the proof, i.e. the effort needed to produce a fake proof. I would certanly not go with anything less than 32bits for the "h" exponents. I was not sure whether 32bits is secure enough though; from an abundance of caution I chose to go one step up to 64bits, which IMO seems big enough (secure enough).

I might agree with changing that to 32bits (even if that significantly reduces the "security" of the proof). But note also that reducing this size from 64b to 32b also does not gain much either.
preda is offline   Reply With Quote
Old 2020-06-14, 11:47   #110
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

118910 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
You can do those costly residue^product(h) computations in the proof much faster than the described trivial way. And basically the same trick worked what I've already written in a post. After writing checked the current source code and it seems you still used those slowish product(h) way (somewhat hard to read it without comments).

The setup, fix the base=3,
and let r[i]==3^(2^(i*topK/2^e)) mod N
store the residue with space=topK/2^e for i=0,1,2,..,2^e (ofcourse r[0]=3).

What would be the proof check say for e=2 ? Easy it is checking:
Code:
( r[0]^(h0*h1)*r[1]^h0*r[2]^h1*r[3] )^(2^(topk/4)) == r[1]^(h0*h1)*r[2]^h0*r[3]^h1*r[4]  mod N
[guessing that h_k is in the exponent for r[d] in the left side iff the (e-1-k)-th bit of d is zero;
then the right side is easy, because just write r[d+1] for r[d])

You can rewrite the left side in a more compact form, using much less computation:
Code:
(r[0]^h0*r[2])^h1*r[1]^h0*r[3] and you can write the right side similarly.
Each r[i] term appears exactly once, for t=2^e you'll do t-1 exponentations (to a 64 bits exponent) and t-1 multiplications.
Big gain over your trivial way, now counting everything in powering to a 64 bits number: (e/2)*t exponentations and (t-1) multiplications.

And that makes sense for e=10. And in these costs you can double everything, because you'll do the same
in the right side of the equation.

ps. e=2 is still small example but you see the idea (r[0]=3 the only small base in the left side)
Thanks, I'll look into implementing it this way.
preda is offline   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 12:40.

Sat Sep 19 12:40:00 UTC 2020 up 9 days, 9:50, 1 user, load averages: 1.42, 1.44, 1.39

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.