VDF (Verifiable Delay Function) and PRP

[kruoli]

Weird, it seems like current cat behaves differently. On Windows, it works fine with type.

Correction, Windows uses 0x1A, Unix uses 0x04. But it still does not behave like I expected.

Forget my addition; head -n1 filename does the job.

[kriesel]

Assuming power 9 and ~95M exponent, the interim residues are spaced ~185547 iterations apart. A random number generator at the server could be used to choose which submissions to spot verify at the server in this additional way, perhaps one in 4K of them, and randomly select between which successive submitted interim residues. A user found to be submitting nonmatching residues could be subjected to an increasing rate of verifications, or other measures. The server would need to receive a LOT of data to do this.

[R. Gerbicz]

Challenge-response type of proof using only 2*p bits of memory sent to the server (that would send it to the verifier), and with ~1/1024 chance to fake it by a clever cheater (assuming a single verification, but you can repeat it to lower the chance). If this is working then the prover could also do part of the computation needed for the verification and the independent prover would need only 2 residues to check the whole computation.

First request for the full residue: rn=3^mp mod mp. Then let d a random number in [L,2*L], the server sends back only d, and ask for a (2^d-1)-th root for A=(3*res)^(2^(d-p%d))/3.

Let rn=lift(Mod(3,mp)^mp)
then you can get one(!) (2^d-1)-th root of A, because A==3^(2^e-1) mod mp

Here e is divisible by d, so one root will be root=3^((2^e-1)/(2^d-1)) mod mp
that is root=3^(2^0)*3^(2^d)*...*3^(2^(e-d)) mod mp.

If we have a stored residue list, spaced at L (this L is different from my notation's error check),
say if we want 1024 residues then L=p\1023 is a good choice (only the last is past of p).
Then the problem is how to get the "root" faster than the trivial O(p) mulmod method?
The solution is not that hard: for each residue=3^(2^(i*L)) mod mp we can get how many squarings will be needed,
and with this we can get the root with O(d+p/d) multiplication.
This is similar to the idea used in calculation of (n!) with iterated squarings and multiplication by a "small" number.

Example:

ff(p,g,L,maxe)={gettime();ret=[];res=Mod(g,2^p-1);for(i=0,maxe,if(i%L==0,ret=concat(ret,lift(res)));res=res^2);
print("Prp took ",gettime/1000.0," seconds");return(ret)}

getroot(p,g,L,d,v)={mp=2^p-1;len=length(v);r=p%d;S=vector(d+1,i,Mod(1,mp));
forstep(i=0,p,d,S[d-(i%L)]*=v[i\L+1]);
res=Mod(1,mp);for(i=1,d,res=res^2*S[i]);return(res)}

validate_proof(p,g,L,v)={gettime();mp=2^p-1;d=L+random(L);root=getroot(p,g,L,d,v);expo=d-(p%d);maxe=L*(p\L+1);
rn=lift(1/g*Mod(v[length(v)-1],mp)^(2^(p-maxe+L)));
b=(root^(2^d-1)*g==Mod(g*rn,mp)^(2^expo));
if(b==1,print("Valid proof"),print("Broken proof"));print("Validation took ",gettime()/1000.0," seconds")}

p=60013;
sh=8;
L=p\(-1+2^sh);
g=3;
mp=2^p-1;
maxe=L*(p\L+1);
v=ff(p,g,L,maxe);

validate_proof(p,g,L,v)

Prp took 14.36600000 seconds
? ? Valid proof
Validation took 0.2510000000 seconds

note: the verifier needs only root and rn for the verification, not the whole v residue array.

How to fake it? It is pretty hard if you'd use only random residue for rn, but with clever cheating it is possible to cheat with 1/d probability:
if you'd compute 3^(h-1) mod mp with small "h" and you hit (2^d-1)|(2^p-h) then you can cheat, it seems that you've very low chance to get it, but
not if you set h=2^m, in this case you have 1/d chance to fake the proof. Otherwise in general case you'd need to extract a (2^d-1)-th root, what is hard.

[preda]

Originally Posted by LaurV

I still didn't get how this works.

1. I am reserving Mx for PRP.
2. I generate x random residues in a file, without doing any work, just garbage data.
3. I apply your calculus on my garbage data and generate the verification file.
4. I send it to PrimeNet and get the LL/PRP credit in just 5 minutes (including the "trusted" particle attached to it, because it is verified, you know?).

Which of this step would be impossible, and why?

Of course the first is not necessary, I don't want to create suspicion by reporting results at a very short time after reservation, so I will just report results, without reservation.

Of course, I understand the part that there is some relation between some residues in that list, and they are not totally random, but this is where we are stuck. Say the residue at iteration h has some relation with residue at iteration k. Then either there is a small difference between h and k (to allow the verification process to be fast, without a lot of squarings) and in this case I can also produce this relation fast, starting with a random h (and squaring, or whatever), or either there is a large distance between h and k, to be difficult for me to fake it, but then in such case you have to spend a huge amount of time to verify it (practically repeating a part of the initial test, and yet, being unsure the iteration h was true, except when it was the first). What we are currently doing today, h is 1 and k is x-1, and the verification process is called "Double Checking", except we just use residues directly, and not hashes of them.

Did you read Pietrzak's paper about VDF? https://eprint.iacr.org/2018/627.pdf

The key element from that paper is the logarithmic-effort verification enabled by this schema:

if prp(A, k)==M
and prp(M, k)==B
then I suppose you agree that prp(A, 2*k)==B, ok?

Now let's assume that I want to verify that prp(A,2*k)==B. The naive way requires me to do 2*k PRP iterations. But here comes the trick, this check can in fact be done in half that work, in k interations, like this:

instead of verifying prp(A, k)==M *and* prp(M,k)==B (each requiring k iterations, thus 2*k iterations in total), I'm going to combine the two and verify them simultaneuosly in just k iterations. Choose a random h, and verify that:
prp(A^h * M, k)==M^h * B
that's the core of the trick.

Let me give an example, which applies one halving step.
Let's say I do a PRP test (E iterations), and I give you my final residue for verification. The best you can do is to repeat the E iterations, and check whether you get the same final residue. That was a DC done in E iterations, 100% of 1xPRP test.

Now let's try something different: assuming E is even, in addition to my final residue, I'm also going to give you my "middle" residue M at iteration E/2. This simple bit of information allows you, magically, to DC my work in only E/2 iterations, 50% of 1xPRP test, like this:
1. you choose a random 64-bit value h.
2. compute A:=3^h * M, B:=M^h * "my final residue"
3. verify that E/2 iterations starting from A produces B.
You see? -- you only needed to do E/2 iterations to double check my work! that's one halving.

Now, is this clear up to here, do you agree it works?
Do you see some way for me to "cheat"? by using garbage in strategic places, whatever, how can I cheat your verification? it's solid, there's no way for me to cheat.

So, look what happened -- you just solidly double-checked my result, using only 50% of one full PRP test. Impossible, you say?

[preda]

Originally Posted by kriesel

Assuming power 9 and ~95M exponent, the interim residues are spaced ~185547 iterations apart. A random number generator at the server could be used to choose which submissions to spot verify at the server in this additional way, perhaps one in 4K of them, and randomly select between which successive submitted interim residues. A user found to be submitting nonmatching residues could be subjected to an increasing rate of verifications, or other measures. The server would need to receive a LOT of data to do this.

Ken, that's not at all how the verification scheme works. There's no need to send all those residues to the verifier. Are you proposing a different schema, or is this a misunderstanding of the proof I'm proposing?

[preda]

Originally Posted by R. Gerbicz

Challenge-response type of proof using only 2*p bits of memory sent to the server (that would send it to the verifier), and with ~1/1024 chance to fake it by a clever cheater (assuming a single verification, but you can repeat it to lower the chance). If this is working then the prover could also do part of the computation needed for the verification and the independent prover would need only 2 residues to check the whole computation.

Robert, is your proposal similar to Wesolowski's proof https://eprint.iacr.org/2018/623.pdf ?

[R. Gerbicz]

Originally Posted by preda

Robert, is your proposal similar to Wesolowski's proof https://eprint.iacr.org/2018/623.pdf ?

They consider more r-th roots, not only (in our case) the (2^d-1)-th root. But regarding only this form allows us to compute the (2^d-1)-th root with just d+p/d mulmods if we have stored p/L residues while we computed the g^(2^p-1). Their time complexity was p/log(p) mulmods.
Notice how nicely this is matching with the other type of verification (what you've implemented) in speed: if you fix L~O(sqrt(p)) then the verfication takes O(sqrt(p)) mulmods with a storage of sqrt(p) residues. And the cheater has no chance because: lcm(2^d-1: L<=d<2*L)~2^(c*L^2), choosing the other type of cheating is even worse because you can't use three d that are relative prime.

[LaurV]

Originally Posted by preda

Now let's try something different: assuming E is even, in addition to my final residue, I'm also going to give you my "middle" residue M at iteration E/2. This simple bit of information allows you, magically, to DC my work in only E/2 iterations, 50% of 1xPRP test, like this:
1. you choose a random 64-bit value h.
2. compute A:=3^h * M, B:=M^h * "my final residue"
3. verify that E/2 iterations starting from A produces B.
You see? -- you only needed to do E/2 iterations to double check my work! that's one halving.

Now, is this clear up to here, do you agree it works?
Do you see some way for me to "cheat"? by using garbage in strategic places, whatever, how can I cheat your verification? it's solid, there's no way for me to cheat.

So, look what happened -- you just solidly double-checked my result, using only 50% of one full PRP test. Impossible, you say?

Yes, impossible. I just pick a random M and do E/2 iterations from it, to get whatever final F, and send you M and F. I don't give a dime about the first half iterations, as long as your verification test doesn't give a dime about them either. Your test still pass, and I got my LL credit with only half of the work. Note that you don't need all the 3^whatever trick, you could just do E/2 "normal" iterations, possible with some shift (mod 2^p-1) to avoid the FFT operating with the same input data. What your verification proves is the fact that I did some work of E/2 iterations starting from an arbitrary M and got F, and that such calculation is correct. But nothing about M or F having anything to do with testing mersenne numbers for (pr)primality.

[R. Gerbicz]

Originally Posted by LaurV

Yes, impossible. I just pick a random M and do E/2 iterations from it, to get whatever final F, and send you M and F. I don't give a dime about the first half iterations, as long as your verification test doesn't give a dime about them either. Your test still pass, and I got my LL credit with only half of the work. Note that you don't need all the 3^whatever trick, you could just do E/2 "normal" iterations, possible with some shift (mod 2^p-1) to avoid the FFT operating with the same input data. What your verification proves is the fact that I did some work of E/2 iterations starting from an arbitrary M and got F, and that such calculation is correct.

Ok, a very small test, but this is better than the usual tests with multi million digits.
So fake me:
Fix the base=A=3, we are claiming that
M=3^(2^(top/2)) mod N
B=3^(2^top) mod N

for N=997 and top=500 (note: top should be even).
Show me two residues M, B to fake the proof (obviously not that 3^(2^250) mod N and 3^(2^500) mod N pair).
And for a quite bounded interval for h in the original proof (but using only the M,B residues) I'll tell you how many tests you have failed.
To get a candidate pair you can use more than top squarings.

[preda]

Originally Posted by LaurV

Yes, impossible. I just pick a random M and do E/2 iterations from it, to get whatever final F, and send you M and F. I don't give a dime about the first half iterations, as long as your verification test doesn't give a dime about them either. Your test still pass, and I got my LL credit with only half of the work. Note that you don't need all the 3^whatever trick, you could just do E/2 "normal" iterations, possible with some shift (mod 2^p-1) to avoid the FFT operating with the same input data. What your verification proves is the fact that I did some work of E/2 iterations starting from an arbitrary M and got F, and that such calculation is correct. But nothing about M or F having anything to do with testing mersenne numbers for (pr)primality.

If you do that, my verification will catch your cheating right away. The verification checks both halves, covers all the iterations, and as such does detect your cheat attempt easily.

Let me try to explain why your cheat attempt is detected:

3 is the base (starting point) of the PRP test.

prp(3^h * M, k) == prp(3^h, k) * prp(M, k) == prp(3, k)^h * B
(because prp(M, k) == B (B is "F" in your naming))

The verification compares for equality:
prp(3, k)^h * B == M^h * B,

which would pass if prp(3, k) == M.
But as you chose M "at random" the verification above fails with high probability, and your cheat it detected.

Does this make sense? I'm sure you could have worked through the above algebra without the hand-holding.

[LaurV]

Originally Posted by R. Gerbicz

Ok, a very small test, but this is better than the usual tests with multi million digits.
So fake me:
Fix the base=A=3, we are claiming that
M=3^(2^(top/2)) mod N
B=3^(2^top) mod N

for N=997 and top=500 (note: top should be even).
Show me two residues M, B to fake the proof (obviously not that 3^(2^250) mod N and 3^(2^500) mod N pair).
And for a quite bounded interval for h in the original proof (but using only the M,B residues) I'll tell you how many tests you have failed.
To get a candidate pair you can use more than top squarings.

This doesn't make sense. 997 is prime. Is my "reserved task" to test if 997 is prime? or to test if 2^997-1 is prime?

In any case, I can pick ANY B=M, run 250 iterations of B=B^2 (mod 997), give you M and B, and ALL such pairs will pass your test, and I got out with "testing" M997 by running only 250 iterations, instead of 995 or 996 (as the normal PRP would be).

This is because you have no way to know if M is indeed the residue after 500 iterations, or fake value.

Examples of M and B that pass the test, as you described it:
249 and 804 - these are 3^(2^250) (mod 997) and 3^(2^500) (mod 997), of course, provided just for fun; what follows are random values, generated like described, pick a random M=B and run for(i=1,250,B=B^2), print M and B. Pick your favorite.

gp > Mod(3,997)^(2^250)
%1 = Mod(249, 997)
gp > Mod(3,997)^(2^500)
%2 = Mod(804, 997)
gp > M=Mod(249,997); B=M; for(i=1,250,B=B^2); [lift(M),lift(B)]
time = 16 ms.
 %3 = [249, 804]
gp > for(k=2, 996/2, M=Mod(k,997); B=M; for(i=1,250,B=B^2); print([lift(M),lift(B)]))
[2, 731]
[3, 249]
[4, 966]
[5, 718]
[6, 565]
[7, 672]
[8, 270]
[9, 187]
[10, 436]
[11, 482]
[12, 257]
[13, 404]
[14, 708]
[15, 319]
[16, 961]
[17, 522]
[18, 108]
[19, 767]
[20, 673]
[21, 829]
[22, 401]
[23, 408]
[24, 431]
[25, 75]
[26, 212]
[27, 701]
[28, 105]
[29, 228]
[30, 888]
[31, 565]
[32, 603]
[33, 378]
[34, 728]
[35, 945]
[36, 185]
[37, 75]
[38, 363]
[39, 896]
[40, 442]
[41, 799]
[42, 820]
[43, 983]
[44, 13]
[45, 668]
[46, 145]
[47, 306]
[48, 9]
[49, 940]
[50, 987]
[51, 368]
[52, 437]
[53, 683]
[54, 970]
[55, 117]
[56, 983]
[57, 556]
[58, 169]
[59, 618]
[60, 81]
[61, 337]
[62, 257]
[63, 42]
[64, 119]
[65, 942]
[66, 149]
[67, 229]
[68, 767]
[69, 895]
[70, 871]
[71, 765]
[72, 640]
[73, 807]
[74, 987]
[75, 729]
[76, 151]
[77, 876]
[78, 944]
[79, 861]
[80, 74]
[81, 74]
[82, 824]
[83, 772]
[84, 223]
[85, 921]
[86, 733]
[87, 940]
[88, 530]
[89, 356]
[90, 775]
[91, 304]
[92, 313]
[93, 108]
[94, 358]
[95, 362]
[96, 597]
[97, 914]
[98, 207]
[99, 404]
[100, 666]
[101, 504]
[102, 815]
[103, 975]
[104, 407]
[105, 13]
[106, 773]
[107, 681]
[108, 203]
[109, 421]
[110, 782]
[111, 729]
[112, 733]
[113, 798]
[114, 657]
[115, 823]
[116, 908]
[117, 773]
[118, 117]
[119, 837]
[120, 388]
[121, 23]
[122, 88]
[123, 548]
[124, 431]
[125, 12]
[126, 792]
[127, 73]
[128, 250]
[129, 502]
[130, 672]
[131, 282]
[132, 246]
[133, 972]
[134, 900]
[135, 830]
[136, 363]
[137, 548]
[138, 213]
[139, 376]
[140, 615]
[141, 422]
[142, 895]
[143, 313]
[144, 247]
[145, 196]
[146, 690]
[147, 762]
[148, 666]
[149, 337]
[150, 501]
[151, 147]
[152, 711]
[153, 905]
[154, 282]
[155, 888]
[156, 140]
[157, 519]
[158, 284]
[159, 577]
[160, 256]
[161, 1]
[162, 256]
[163, 79]
[164, 156]
[165, 220]
[166, 30]
[167, 603]
[168, 502]
[169, 705]
[170, 276]
[171, 858]
[172, 434]
[173, 42]
[174, 207]
[175, 550]
[176, 594]
[177, 344]
[178, 19]
[179, 358]
[180, 229]
[181, 710]
[182, 890]
[183, 165]
[184, 490]
[185, 12]
[186, 185]
[187, 360]
[188, 484]
[189, 488]
[190, 417]
[191, 140]
[192, 718]
[193, 30]
[194, 144]
[195, 263]
[196, 770]
[197, 360]
[198, 212]
[199, 830]
[200, 310]
[201, 192]
[202, 531]
[203, 675]
[204, 556]
[205, 407]
[206, 867]
[207, 524]
[208, 411]
[209, 804]
[210, 530]
[211, 807]
[212, 761]
[213, 58]
[214, 308]
[215, 915]
[216, 837]
[217, 820]
[218, 675]
[219, 546]
[220, 361]
[221, 521]
[222, 501]
[223, 482]
[224, 434]
[225, 67]
[226, 93]
[227, 85]
[228, 710]
[229, 673]
[230, 422]
[231, 778]
[232, 743]
[233, 645]
[234, 761]
[235, 368]
[236, 782]
[237, 34]
[238, 686]
[239, 328]
[240, 480]
[241, 824]
[242, 861]
[243, 480]
[244, 520]
[245, 948]
[246, 791]
[247, 798]
[248, 9]
[249, 804]
[250, 796]
[251, 911]
[252, 692]
[253, 247]
[254, 522]
[255, 19]
[256, 299]
[257, 625]
[258, 66]
[259, 550]
[260, 708]
[261, 762]
[262, 760]
[263, 350]
[264, 366]
[265, 867]
[266, 668]
[267, 908]
[268, 877]
[269, 326]
[270, 554]
[271, 34]
[272, 151]
[273, 921]
[274, 791]
[275, 258]
[276, 171]
[277, 877]
[278, 681]
[279, 970]
[280, 915]
[281, 866]
[282, 409]
[283, 327]
[284, 213]
[285, 408]
[286, 490]
[287, 542]
[288, 100]
[289, 303]
[290, 705]
[291, 270]
[292, 905]
[293, 529]
[294, 696]
[295, 59]
[296, 310]
[297, 896]
[298, 88]
[299, 327]
[300, 332]
[301, 562]
[302, 778]
[303, 871]
[304, 304]
[305, 692]
[306, 544]
[307, 393]
[308, 760]
[309, 504]
[310, 81]
[311, 521]
[312, 646]
[313, 321]
[314, 529]
[315, 246]
[316, 228]
[317, 417]
[318, 56]
[319, 226]
[320, 697]
[321, 79]
[322, 731]
[323, 577]
[324, 697]
[325, 390]
[326, 920]
[327, 144]
[328, 378]
[329, 250]
[330, 303]
[331, 124]
[332, 993]
[333, 67]
[334, 119]
[335, 914]
[336, 66]
[337, 159]
[338, 903]
[339, 299]
[340, 362]
[341, 149]
[342, 85]
[343, 579]
[344, 208]
[345, 542]
[346, 792]
[347, 945]
[348, 770]
[349, 40]
[350, 259]
[351, 56]
[352, 519]
[353, 966]
[354, 220]
[355, 920]
[356, 928]
[357, 40]
[358, 484]
[359, 701]
[360, 900]
[361, 59]
[362, 570]
[363, 742]
[364, 546]
[365, 169]
[366, 975]
[367, 366]
[368, 267]
[369, 860]
[370, 796]
[371, 356]
[372, 640]
[373, 645]
[374, 949]
[375, 994]
[376, 866]
[377, 388]
[378, 799]
[379, 531]
[380, 742]
[381, 231]
[382, 646]
[383, 147]
[384, 436]
[385, 858]
[386, 993]
[387, 373]
[388, 579]
[389, 890]
[390, 829]
[391, 615]
[392, 562]
[393, 428]
[394, 949]
[395, 58]
[396, 437]
[397, 421]
[398, 554]
[399, 754]
[400, 291]
[401, 520]
[402, 772]
[403, 944]
[404, 328]
[405, 291]
[406, 907]
[407, 258]
[408, 657]
[409, 306]
[410, 411]
[411, 860]
[412, 682]
[413, 544]
[414, 196]
[415, 961]
[416, 344]
[417, 903]
[418, 491]
[419, 159]
[420, 594]
[421, 319]
[422, 690]
[423, 393]
[424, 962]
[425, 267]
[426, 524]
[427, 145]
[428, 823]
[429, 171]
[430, 875]
[431, 754]
[432, 686]
[433, 876]
[434, 223]
[435, 948]
[436, 907]
[437, 875]
[438, 326]
[439, 203]
[440, 683]
[441, 308]
[442, 994]
[443, 16]
[444, 332]
[445, 376]
[446, 401]
[447, 165]
[448, 208]
[449, 958]
[450, 124]
[451, 276]
[452, 187]
[453, 711]
[454, 321]
[455, 926]
[456, 570]
[457, 192]
[458, 442]
[459, 23]
[460, 409]
[461, 16]
[462, 428]
[463, 743]
[464, 765]
[465, 775]
[466, 911]
[467, 682]
[468, 962]
[469, 350]
[470, 815]
[471, 618]
[472, 361]
[473, 231]
[474, 926]
[475, 696]
[476, 972]
[477, 105]
[478, 488]
[479, 259]
[480, 933]
[481, 390]
[482, 156]
[483, 249]
[484, 284]
[485, 226]
[486, 933]
[487, 928]
[488, 263]
[489, 728]
[490, 73]
[491, 100]
[492, 958]
[493, 373]
[494, 93]
[495, 942]
[496, 597]
[497, 625]
[498, 491]
time = 37 ms.
gp >