Efficient Proth/PRP Test Proof Scheme

[patnashev]

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_{s-1} = 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.

[R.D. Silverman]

Originally Posted by patnashev

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.

Please define L and a.

[patnashev]

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.

[R.D. Silverman]

Originally Posted by patnashev

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.

I have not looked deeply, but the scheme seems workable.

[patnashev]

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.

[preda]

Please have a look at using VDFs for PRP verification:
https://mersenneforum.org/showthread.php?t=24654

[patnashev]

preda, Pietrzak's VDF looks interesting. A similiar idea, using similiar tools, but more complicated proof calculation. Worth researching.

[patnashev]

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

[patnashev]

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:

        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);
        }

[patnashev]

Pietrzak VDF testing started on the private GFN server. Typical task looks like this:

<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 all-complex 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>
]]>

[patnashev]

And I made infographic explaining how the scheme works. This is my original scheme:


And this is Pietrzak VDF: