mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2020-04-27, 20:31   #12
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

212628 Posts
Default

Quote:
Originally Posted by LOBES View Post
Is there perhaps a better use of my 1080 Ti than doing TF'ing? From what I understand, mfaktc-win-64.exe is only used for Trial Factoring.
While you can use it for other things... It is best for GIMPS if you use it for TF. By using GPU's the level of TF that make sense is higher, thus more exponents eliminated. Also, GPU's doing -all- the TF makes sense vs having the CPU's do any.
Uncwilly is online now   Reply With Quote
Old 2020-04-27, 22:14   #13
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by chalsall View Post
Again, I must thank you for your thorough curation of this very technical and rarified space! Very valuable.

I don't have the time to drill down on all the prior discussion. I will say, however, that Oliver asked (many years ago) if anyone had ideas on how to produce a "checksum" or some other "proof of work" mechanism. Several ideas were proposed, but they all failed to be viable because of the unpredictable (and massive) concurrency of the CUDA TF runs.

If Gerbicz has proposed something which /is/ viable, it would be cool to see it codified and beta-tested.

Not that I think there's much, if any, cheating going on. But there /could/ be more "bad kit" out there than we realize. Having mfakt[c|o] be able to provide a long-term sanity data stream would be very useful to many people.
When one requests to perform TD on 2^p-1 have the server provide a set of indices
s = [I1, I2, I3, .....]. Encrypt s with (say) AES. When one does the trial division,
SAVE the remainders r_I = 2^p-1 mod p_{I} for all I \in s. Then return
HASH(r1 | r2 | r3 | ....) for some chosen hash function.

Bury the AES key within the TD code. Yes, a determined hacker can find and extract the key with enough
effort. But people with the skill to do that are unlikely to want to cheat.
One can even change the key periodically if desired to making extracting it a little bit
harder. (via a key exchange). Yes, the new key can also be extracted, but it requires
extra work.


In other words, return a hash of a random set of concatened remainders. This at least
proves that the worker did at least some of the divisions. It can be easily checked by
the server. This is similar to a ZKP technique known as "cut and choose".
Change the set s each time.

Last fiddled with by R.D. Silverman on 2020-04-27 at 22:15
R.D. Silverman is offline   Reply With Quote
Old 2020-04-28, 00:41   #14
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

52×373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Change the set s each time.
Wow! I actually understood some of that!

I guess the question then becomes, what is the (computational) cost in doing this?

Also, it isn't clear to me if this provides any sort of "sanity" check during the TF/TD run? Short of running again (DC'ing a TF -- usually not done), will this help find border-line kit?

That would be a /strong/ motivator for some to run such a code-path. Many use these things for serious work too, where sane, deterministic kit is mission-critical.
chalsall is offline   Reply With Quote
Old 2020-04-28, 02:26   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by chalsall View Post
Wow! I actually understood some of that!

I guess the question then becomes, what is the (computational) cost in doing this?
nil. The required remainders get computed anyway during the TD. The encryption
and Hash take almost no time.
Quote:

Also, it isn't clear to me if this provides any sort of "sanity" check during the TF/TD run?
Please be more specific.
It is almost impossible to correctly guess the set s, so if the hash is correct it means the
TF was done.

Quote:

Short of running again (DC'ing a TF -- usually not done), will this help find border-line kit?
"border-line kit"???? Meaning?
R.D. Silverman is offline   Reply With Quote
Old 2020-04-28, 02:45   #16
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5,879 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
When one requests to perform TD on 2^p-1 have the server provide a set of indices
s = [I1, I2, I3, .....]. Encrypt s with (say) AES. When one does the trial division,
SAVE the remainders r_I = 2^p-1 mod p_{I} for all I \in s. Then return
HASH(r1 | r2 | r3 | ....) for some chosen hash function.

Bury the AES key within the TD code. Yes, a determined hacker can find and extract the key with enough
effort. But people with the skill to do that are unlikely to want to cheat.
One can even change the key periodically if desired to making extracting it a little bit
harder. (via a key exchange). Yes, the new key can also be extracted, but it requires
extra work.


In other words, return a hash of a random set of concatened remainders. This at least
proves that the worker did at least some of the divisions. It can be easily checked by
the server. This is similar to a ZKP technique known as "cut and choose".
Change the set s each time.
I would look at this from the perspective as a puzzle to be solved.

I simple solution to solve this puzzle would be to extract the key from the code and submit the required results. Problem solved. Server fooled. Easy.

So we would still need to monitor the expected frequency of successes to catch anyone using the short-cut. The end result is you've make it slightly more difficult for someone to cheat, at the cost of extra complexity for the server.

And for the amount of cheats we've seen in the past (i.e. zero) I don't think we need to go there yet. Let's not try to solve problems that don't yet exist.
retina is offline   Reply With Quote
Old 2020-04-28, 02:58   #17
axn
 
axn's Avatar
 
Jun 2003

12AA16 Posts
Default

Quote:
Originally Posted by retina View Post
at the cost of extra complexity for the server.
... which pales in comparison to the extra complexity (and performance hit) to the client.

Not to mention the fact that mfaktc/o don't directly communicate to the server, so all the middlemen/scripts also needs to be updated. And people do need to build mfaktc/o from source anyway, so there goes the secrecy of the key.

Also, the index isn't a deterministic thing -- the base sieve used to find the candidate factors have a user-configurable sieve depth (because of efficiency concerns) and so different amounts of candidate factors are TD-ed.
axn is offline   Reply With Quote
Old 2020-04-28, 03:01   #18
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by retina View Post
I would look at this from the perspective as a puzzle to be solved.

I simple solution to solve this puzzle would be to extract the key from the code
It is not as easy as you think. Especially when the key is scattered as bits and pieces
throughout the code.

Quote:

So we would still need to monitor the expected frequency of successes to catch anyone using the short-cut. The end result is you've make it slightly more difficult for someone to cheat, at the cost of extra complexity for the server.
Server complexity/cost is tiny.
R.D. Silverman is offline   Reply With Quote
Old 2020-04-28, 03:13   #19
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by axn View Post
... which pales in comparison to the extra complexity (and performance hit) to the client.
You are confused. The added computation would be hard to measure in a benchmark.
It is tiny: Decrypt the index set, gather the residues during the TF, catenate them.
compute a hash.

Quote:
Not to mention the fact that mfaktc/o don't directly communicate to the server, so all the middlemen/scripts also needs to be updated.
Any scheme will require code changes.

Quote:
And people do need to build mfaktc/o from source anyway, so there goes the secrecy of the key.
Why do they need source? Why can't you just distribute binaries?
(I suspect I know the answer]. It is the main reason I dislike these devices: lack of
interoperability. There are too many hardware variations. Code is not portable.

This problem can be avoided: Just compile a variety of different binaries. Don't give
out source.

Quote:
Also, the index isn't a deterministic thing -- the base sieve used to find the candidate factors have a user-configurable sieve depth (because of efficiency concerns) and so different amounts of candidate factors are TD-ed.
It is not "index". It is "indices". And it should suffice to put a upper bound on the
max element in set s.

Last fiddled with by R.D. Silverman on 2020-04-28 at 03:13
R.D. Silverman is offline   Reply With Quote
Old 2020-04-28, 03:26   #20
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5,879 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It is not as easy as you think. Especially when the key is scattered as bits and pieces
throughout the code.
Key extraction is really easy. Judicious use of a debugger makes it a no brainer. That is how DVDs and BluRay get pwned effortlessly. It doesn't work.
retina is offline   Reply With Quote
Old 2020-04-28, 03:35   #21
axn
 
axn's Avatar
 
Jun 2003

10010101010102 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
You are confused. The added computation would be hard to measure in a benchmark.
It is tiny: Decrypt the index set, gather the residues during the TF, catenate them.
compute a hash.
You have clearly not done any GPU programming. What sounds like a simple operation in CPU land will have a large impact on GPU performance (not like 2x hit, but easily 20-30%). But for the sake of argument, let's say this is acceptable

Quote:
Originally Posted by R.D. Silverman View Post
Any scheme will require code changes.
The problem is that all of these have different authors. Any many people have their own scripts. Some people just manually get assignment from server and launch using command line. This isn't just code change -- it is a complex "system" change. The problem is that the whole "GPU TF" thing isn't very streamlined. Anyway, for the sake of argument, let's assume that this can somehow be coordinated.


Quote:
Originally Posted by R.D. Silverman View Post
Why do they need source? Why can't you just distribute binaries?
(I suspect I know the answer]. It is the main reason I dislike these devices: lack of
interoperability. There are too many hardware variations. Code is not portable.

This problem can be avoided: Just compile a variety of different binaries. Don't give
out source.
Hardware variations, OS variations, device driver variations, development platform (CUDA / OpenCL) variations.
Suppose, somehow we can overcome this problem and force everyone to use only trusted binaries. Then, we don't need to do any of this. We can just send in a nonce and the client can return HASH(nonce, exponent, bit depth). Since we already trust the client, we can trust it to generate this hash after full computation is done. No need to mess up the critical TF logic.


Quote:
Originally Posted by R.D. Silverman View Post
It is not "index". It is "indices". And it should suffice to put a upper bound on the
max element in set s.
I'm trying to understand this part. Suppose the server asks client to compute has for indices {10, 20, 30}. The assumption is that the server knows (or can compute) exactly which candidate factors correspond to the given indices. But that is not deterministic on client side. Because of variable SoE sieve depth (and the inherent nondeterminism in GPU sieve), the exact sequence of candidate factors produced can vary and so the server can't validate the residue.

I suppose I'm misunderstanding you. Maybe you mean the actual factoring candidates (or the k in 2kp+1 for known prime candidates which will never be skipped). It would be tricky to implement such a thing efficiently.
axn is offline   Reply With Quote
Old 2020-04-28, 03:53   #22
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10010011001112 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Just compile a variety of different binaries. Don't give
out source.
As things stand now, mfaktc is GPLV3 licensed and the source is out there, and the license specifies source must be made available. Mfakto was derived from mfaktc.
kriesel is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GPU Trial Factoring FAQ garo GPU Computing 100 2019-04-22 10:58
mfaktc for dummies NBtarheel_33 GPU Computing 10 2011-10-13 00:04
How much Trial Factoring to do? odin Software 4 2010-08-08 20:23
How far to do trial factoring S485122 PrimeNet 1 2007-09-06 00:52
trial factoring and P-1 jocelynl Math 8 2006-02-01 14:12

All times are UTC. The time now is 06:23.

Fri Nov 27 06:23:32 UTC 2020 up 78 days, 3:34, 4 users, load averages: 0.72, 1.11, 1.12

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.