20200301, 14:04  #1 
"Pavel Atnashev"
Mar 2020
3^{2} Posts 
Efficient Proth/PRP Test Proof Scheme
Executive Summary
Double checking is long considered necessary for coordinated search for prime numbers. Indeed, a prime missed due to hardware error, software misconfiguration or credit cheating can mean years, decades or even centuries of additional work. But the price is high, the resources needed to test a candidate are doubled. Recent developments in hardware error detection (Gerbicz check) allow more certainty in the performance of hardware, but search coordinators still can't be sure that all participants run their software properly, with hardware checks enabled and no malicious intent present. Proposed scheme does not eliminate the double check, but allows more efficient validation of the original result. Instead of redoing the full test, only ~5% of work is need to validate the result. This comes at a price of additional amounts of data needed to be transmitted from the tester to the coordinator, about 10 MB per million decimal digits of tested number. But this data doesn't need to be stored, after a relatively fast processing it is turned into a certificate the size of the number, which is stored and transmitted to a double checker for validation. Implementation Summary The scheme borrows heavily from the Gerbicz check. It's the same idea of verifying a sequence by transforming each member into the next one by a single operation. The coordinator receives s checkpoints at regular interval M from the tester. It is convenient (and reliable) to save the checkpoints right after L^2 Gerbicz check, so it's advised to make M a multiple of L^2. Naturally, we can compute the result by M/2 iterations on average starting from the last checkpoint, but we need to prove the correctness of the last checkpoint first. Instead of proving each checkpoint in the sequence individually, we tag each of them with a random number and multiply all of them into one. The resulting certificate can be proven by M iterations, which requries 1/s of original work. Combined with computing the result, the verification work averages to 1.5/s of total. By keeping s in 20..40 range, we can ensure the verification to be less than 10% while keeping the amount of data transmitted at reasonable level. Note that the certificate is salted with a sequence of random numbers, which makes the information in it scrambled and unusable for any other purpose but verification. Even if the double checker is the same person as the original tester, it gives him no advantage because without knowing the salt one can neither speed up the calculation nor tamper with its outcome. The result of the verification process is sent to the coordinator who compares it with the result obtained during construction of the certificate. Also note that due to checkpoints being saved after the Gerbicz check, no hardware error can cause the verification to fail. A failure of the verification is a strong indicator of cheating and should result in permanent ban in most cases. I've implemented the scheme (and the Gerbicz check) using LLR source code as a base. My implementation can be downloaded here: https://www.dropbox.com/s/1uidmmbw5o...Proof.zip?dl=1 It contains Windows and Linux binaries, bat files with all the steps as well as readme file which describes each step in detail. Note that for b!=2 the test is ~17% slower than the original LLR. Theory Summary The scheme requires the test to be an exponentiation to a power which is itself a power of a relatively small number. So, it works for Proth and Fermat tests of numbers of the form N = k*b^n+c. Both of these tests require exponentiation of a^k to b^n power. Step 1 is performed by the tester, Step 2&4 by the coordinator, Step 3 by a double checker. 2's in the formulas can be replaced with b, a^k is double checked in Step 2, x_i do not need to be stored, and a residue of P_S is enough for Step 4. While proving the correctness of the scheme rigorously is challenging for me, I've run some simulations. For N=5*2^11+1, a=3, s=3, M=3, 10 sets of random x_i, exhaustive search of (Z/NZ)^s yielded only one solution, the correct one. This proves that the general solution is unique. Probabilistic simulations with r_0 = a^k, r_1 = ... = r_{s1} = 1, r_s = (a^k)^(2^m) yielded the false positive rate very close to 1/X_MAX. For X_MAX = 2^64 the probability of cheating the scheme is the same as guessing RES64 for a regular test. 
20200301, 16:51  #2  
Nov 2003
7,417 Posts 
Quote:


20200301, 17:00  #3 
"Pavel Atnashev"
Mar 2020
3^{2} Posts 
L is the constant of Gerbicz check. Can be selected to keep s in 20..40 range. If L = 1024, M is about a million.
a is the parameter of Fermat and Proth tests.Usually a = 3 for big numbers. 
20200301, 17:22  #4 
Nov 2003
7,417 Posts 

20200420, 11:49  #5 
"Pavel Atnashev"
Mar 2020
3^{2} Posts 
Setting L = sqrt(n/s) moves the last checkpoint almost to the end of the test. It allows to save on the calculation of the result, and makes s (the number of uploaded checkpoints) the main configurable parameter of the scheme. If s = 16, the verification of a certificate requires 6% of the work, upload size is 6MB per 1M decimal digits.

20200421, 00:44  #6 
"Mihai Preda"
Apr 2015
2004_{8} Posts 
Please have a look at using VDFs for PRP verification:
https://mersenneforum.org/showthread.php?t=24654 
20200421, 05:17  #7 
"Pavel Atnashev"
Mar 2020
3^{2} Posts 
preda, Pietrzak's VDF looks interesting. A similiar idea, using similiar tools, but more complicated proof calculation. Worth researching.

20200428, 17:40  #8 
"Pavel Atnashev"
Mar 2020
3^{2} Posts 
We started testing this scheme, as well as Gerbicz check implementation, on the private GFN server.
http://boincvm.proxyma.ru:30080/test4vm/ Invitation code "PrimeGrid", select "LLR2 testing" and "Run test applications" in the settings. Source code for LLR2: https://github.com/patnashev/llr2 
20200430, 19:01  #9 
"Pavel Atnashev"
Mar 2020
3^{2} Posts 
I'm very excited about Pietrzak VDF. It has potential to decrease the upload to 2MB per million decimal digits for 6% validation work.
I've implemented it in LLR2, pushed to GitHub already. Not tested yet though. My implementation looks like this: Code:
int[] Prove(int t, int[] r) // t  depth, r  checkpoints { int i, j, k, e; int[] h = new int[t]; // hashes int[] u = new int[t]; // products int s = 1 << t; // number of points int PS = r[s]; // the result u[0] = r[s/2]; for (i = 1; i < t; i++) { h[i] = hash(PS); PS = mul(PS, pow(u[i  1], h[i])); u[i] = 1; for (j = 0; j < (1 << i); j++) { e = 1; for (k = 0; k < i; k++) if ((j & (1 << k)) == 0) e *= h[i  k]; u[i] = mul(u[i], pow(r[(1 + j*2) << (t  i  1)], e)); } } return u; } Cert BuildCert(int t, int r0, int rs, int[] u) { int i, h; int PD = r0; // a^k int PS = rs; // the result for (i = 0; i < t; i++) { h = hash(PS); PD = mul(u[i], pow(PD, h)); PS = mul(PS, pow(u[i], h)); } h = random(); PD = pow(PD, h); PS = pow(PS, h); if (PS == 0  gcd(PS, N) != 1) throw new Exception(); return new Cert(PD, PS); } 
20200513, 08:09  #10 
"Pavel Atnashev"
Mar 2020
3^{2} Posts 
Pietrzak VDF testing started on the private GFN server. Typical task looks like this:
Code:
<core_client_version>7.14.2</core_client_version> <![CDATA[ <stderr_txt> BOINC PrimeGrid wrapper 2.01 (May 8 2020 09:10:05) running ../../projects/boincvm.proxyma.ru_30080_test4vm/llr2_win64_200511.exe v LLR2 Program  Version 0.9.3, using Gwnum Library Version 29.8 running ../../projects/boincvm.proxyma.ru_30080_test4vm/llr2_win64_200511.exe oGerbicz=1 oProofName=proof oProofCount=8 oProductName=prod oPietrzak=1 oCachePoints=1 pSavePoints q19*2^3588874+1 d oDiskWriteTime=1 Starting Proth prime test of 19*2^3588874+1 Using allcomplex AVX FFT length 200K, Pass1=640, Pass2=320, clm=2, a = 3, L2 = 899*499, M = 448601 Compressed 8 points to 3 products. Time : 22.330 sec. Testing complete. 07:28:01 (4572): called boinc_finish(0) </stderr_txt> ]]> 
20200513, 08:17  #11 
"Pavel Atnashev"
Mar 2020
3^{2} Posts 
And I made infographic explaining how the scheme works. This is my original scheme:
And this is Pietrzak VDF: 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Proof for the efficient algorithm used in trial factoring?  neomacdev  Math  5  20190427 20:08 
Efficient Test  paulunderwood  Computer Science & Computational Number Theory  5  20170609 14:02 
Intel Xeon naming scheme change  VictordeHolland  Hardware  5  20170429 06:48 
proof the lucas lehmer test  kurtulmehtap  Math  13  20091002 12:12 
Proth Test Limits  amcfarlane  Math  1  20060723 18:29 