VDF (Verifiable Delay Function) and PRP

[R. Gerbicz]

Originally Posted by LaurV

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?

There is nothing special in 997, for composite/prime the proof check should run in the same way.

Originally Posted by LaurV

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.

Asked one. But let's take not the first because you could complain why. Picked the (5,718)

check_proof(M,B,N,top,A=3,num_iteration=20,maxh=1000)={
for(i=1,num_iteration,h=1+random(maxh);
res=Mod(A,N)^h*M;
res=res^(2^(top/2));
res2=Mod(M,N)^h*B;
print1("Test#"i": h=",h);
if(res==res2,print(" passed the test"),print(" failed the test")))}

? check_proof(5,718,997,500)
Test#1: h=250 failed the test
Test#2: h=992 failed the test
Test#3: h=235 failed the test
Test#4: h=283 failed the test
Test#5: h=116 failed the test
Test#6: h=832 failed the test
Test#7: h=159 failed the test
Test#8: h=133 failed the test
Test#9: h=487 failed the test
Test#10: h=310 failed the test
Test#11: h=568 failed the test
Test#12: h=565 failed the test
Test#13: h=352 failed the test
Test#14: h=269 failed the test
Test#15: h=580 failed the test
Test#16: h=22 failed the test
Test#17: h=601 failed the test
Test#18: h=992 failed the test
Test#19: h=162 failed the test
Test#20: h=136 failed the test
? 
? check_proof(249,804,997,500)
Test#1: h=548 passed the test
Test#2: h=453 passed the test
Test#3: h=720 passed the test
Test#4: h=551 passed the test
Test#5: h=938 passed the test
Test#6: h=468 passed the test
Test#7: h=40 passed the test
Test#8: h=480 passed the test
Test#9: h=562 passed the test
Test#10: h=942 passed the test
Test#11: h=457 passed the test
Test#12: h=911 passed the test
Test#13: h=742 passed the test
Test#14: h=381 passed the test
Test#15: h=187 passed the test
Test#16: h=208 passed the test
Test#17: h=991 passed the test
Test#18: h=660 passed the test
Test#19: h=240 passed the test
Test#20: h=310 passed the test
?

You failed all 20 tests.
Now it is your turn. (In the second run used the true pair to check my proof checker.

[LaurV]

Originally Posted by preda

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.

This doesn't make sense either. Why do you need B? you can simplify it in both sides. If that is true, you just found a method to run the PRP test in half number of iterations than required. This is just a proof of work of the fact that I start from M and I get B after a number of iterations. But there is no way for you (that we know of) to test if M is correct (i.e. it represents indeed the residue after 250 iterations, in Robert's example). IF you would have any procedure/function/algorithm f(R,k) to test if residue R is the right residue after k iterations and give you true or false, then why don't you just run this function for the last residue (996 in the example) and don't need any other verification?


I begin to believe that I am stupid, but really, I don't get this. Please provide an example with numbers, for a PRP of a mersenne number with a small exponent. Even M29 or M41 would be right.

[LaurV]

Originally Posted by R. Gerbicz

Now it is your turn. (In the second run used the true pair to check my proof checker.

Wait! Crosspost.
Let me digest this!

[R. Gerbicz]

Originally Posted by LaurV

This doesn't make sense either. Why do you need B? you can simplify it in both sides.

There are flaws in that post, but probably all previous posts were good, used the same notations from Preda: https://mersenneforum.org/showpost.p...3&postcount=15

the verification for a pair of residue: prp(A^h * M, topK/2) == M^h * B.
(in my code top=topK and used N for modulus).
And it is a false that the test is passing only for the true (M,B) pair.

[preda]

Originally Posted by LaurV

This doesn't make sense either. Why do you need B? you can simplify it in both sides. If that is true, you just found a method to run the PRP test in half number of iterations than required. This is just a proof of work of the fact that I start from M and I get B after a number of iterations. But there is no way for you (that we know of) to test if M is correct (i.e. it represents indeed the residue after 250 iterations, in Robert's example). IF you would have any procedure/function/algorithm f(R,k) to test if residue R is the right residue after k iterations and give you true or false, then why don't you just run this function for the last residue (996 in the example) and don't need any other verification?


I begin to believe that I am stupid, but really, I don't get this. Please provide an example with numbers, for a PRP of a mersenne number with a small exponent. Even M29 or M41 would be right.

Proof by example it is then.
Python3 and modulo M7

$ python3
>>> A=3
>>> B=3**64 % 127
>>> M=3**8 % 127
>>> h=5
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
True
>>> M=42
>>> B=M**8 % 127
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
False
>>> M=13
>>> B=M**8 % 127
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
False

[retina]

Originally Posted by preda

Proof by example it is then.
Python3 and modulo M7

$ python3
>>> A=3
>>> B=3**64 % 127
>>> M=3**8 % 127
>>> h=5
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
True
>>> M=42
>>> B=M**8 % 127
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
False
>>> M=13
>>> B=M**8 % 127
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
False

Zero is the only other value here that satisfies the condition:

A=3
h=5
N=127
e=8
print("Correct value {}".format(A**e % N))
for M in range(0,N):
	B=M**e % N
	if (A**h * M) ** e % N == (M**h * B) % N: print("Found {}".format(M))

Output:

Correct value 84
Found 0
Found 84

[preda]

I don't have experience with AWS and the pricing on their website is not easy to understand.

Could somebody please inform me, how much would it cost to transfer 50GB/day out of AWS, for example by doing HTTP/HTTPS PUT or PUSH to a server that is not in AWS, with a 150MB size per request if that's relevant. (or is there a better way to transfer such data out of AWS?)

[preda]

There is a problem with storing the res64 in the proof file header: if the proof file is public, then the proof reveals the res64, which is supposed to be "secret" in the classic DC setup.

Even without explicitly storing the res64 in the proof header, the proof does store the residue at iteration topK. As topK is under the exponent E (and very close), somebody can simply run a the few iterations from topK to E and thus discover the res64, which again weakens the classic DC which relies on the res64 being "secret" until DCed.

An alternative is to set topK to be above E (specifically, let topK be the smallest multiple of 1024 that is larger than E). Let's see what is the impact of this change:

First, through the same "proof verificatication" algorithm the verifier can verify that the residue at topK is correct. OTOH the verifier is not able anymore to derive the residue at E, or the res64. Depending on how you look at it, this inability of the verifier to derive the residue at E may seem like something lost (the proof does not allow to derive res64 anymore) or like something gained (the verification does not reveal res64 anymore).

In addition to verifying that the residue at topK is correct, we would like to also be able to establish the mersenne candidate status (composite or PRP) based on the proof. We can still do this: if the candidate is PRP, then the residue at E must be 9. So the verifier can run the iterations from E up to topK starting with residue 9, and compare the residues at topK. If equality, the candidate is PRP, othewise it's composite.

But.. there is one more point: the proof also exposes the residue M0 (the first middle) which can also be used as a starting point for iterating up towards E. This allows to compute the res64 with only half the iterations of a classic PRP DC.

I think we shouldn't sweat over revealing res64 through the proof (or, to be precise, revealing the least significant byte of the res64, which is the only one that's secret), because, once an exponent has a proof available, we can base the DC of that exponent on the proof verification and discount the value of the classic DC (for the particular exponent that has a proof).

So, to recap:
A) topK under E: allows to extract from the proof res64 type1, type4, res2048, full-residue at E. Reveals res64.
B) topK above E: does not reveal res64, and does not allow computing either of those (except by doing one half-PRP starting from M[0]).

Oppinions?

[preda]

Originally Posted by preda

There is a problem with storing the res64 in the proof file header: if the proof file is public, then the proof reveals the res64, which is supposed to be "secret" in the classic DC setup.

Even without explicitly storing the res64 in the proof header, the proof does store the residue at iteration topK. As topK is under the exponent E (and very close), somebody can simply run a the few iterations from topK to E and thus discover the res64, which again weakens the classic DC which relies on the res64 being "secret" until DCed.

An alternative is to set topK to be above E (specifically, let topK be the smallest multiple of 1024 that is larger than E). Let's see what is the impact of this change:

First, through the same "proof verificatication" algorithm the verifier can verify that the residue at topK is correct. OTOH the verifier is not able anymore to derive the residue at E, or the res64. Depending on how you look at it, this inability of the verifier to derive the residue at E may seem like something lost (the proof does not allow to derive res64 anymore) or like something gained (the verification does not reveal res64 anymore).

In addition to verifying that the residue at topK is correct, we would like to also be able to establish the mersenne candidate status (composite or PRP) based on the proof. We can still do this: if the candidate is PRP, then the residue at E must be 9. So the verifier can run the iterations from E up to topK starting with residue 9, and compare the residues at topK. If equality, the candidate is PRP, othewise it's composite.

But.. there is one more point: the proof also exposes the residue M0 (the first middle) which can also be used as a starting point for iterating up towards E. This allows to compute the res64 with only half the iterations of a classic PRP DC.

I think we shouldn't sweat over revealing res64 through the proof (or, to be precise, revealing the least significant byte of the res64, which is the only one that's secret), because, once an exponent has a proof available, we can base the DC of that exponent on the proof verification and discount the value of the classic DC (for the particular exponent that has a proof).

So, to recap:
A) topK under E: allows to extract from the proof res64 type1, type4, res2048, full-residue at E. Reveals res64.
B) topK above E: does not reveal res64, and does not allow computing either of those (except by doing one half-PRP starting from M[0]).

Oppinions?

Thinking more about it I think I start to like the variant with topK above E more, as being potentially more resilient againts errors (including programming errors), because the computation that takes place during verification does not retrace the steps of the PRP test to any degree.

While a res64-at-topK for the prime case can be computed independently of the proof, even ahead of time (being prp(3, topK - E +1)).

[R. Gerbicz]

Originally Posted by R. Gerbicz

You failed all 20 tests.
Now it is your turn. (In the second run used the true pair to check my proof checker.

The true pair was (249,804), in the follow-up consider another pair (748,193):

?  check_proof(748,193,997,500)
Test#1: h=780 failed the test
Test#2: h=613 passed the test
Test#3: h=978 failed the test
Test#4: h=816 failed the test
Test#5: h=21 passed the test
Test#6: h=637 passed the test
Test#7: h=781 passed the test
Test#8: h=236 failed the test
Test#9: h=828 failed the test
Test#10: h=523 passed the test
Test#11: h=85 passed the test
Test#12: h=472 failed the test
Test#13: h=520 failed the test
Test#14: h=419 passed the test
Test#15: h=776 failed the test
Test#16: h=410 failed the test
Test#17: h=967 passed the test
Test#18: h=530 failed the test
Test#19: h=986 failed the test
Test#20: h=73 passed the test

9 passed, and 11 failed, so in 9/20 we successfully faked the proof checker, and note that this trap holds for more than two residues, say when you have 512 residues or more!

[LaurV]

Well, no need to continue here, you convinced me

My initial understanding of what you (and Mihai) wanted to do was wrong, and the piece of code you provided enlightened me. Now it is much clear, and I played a bit withe the math too. For primes (like provided examples) there are only two square roots of 1, no other pair will match. For composites, especially with many factors) there can be multiple matches (it is related to the number of roots of 1), but yet, finding these matches, i.e. the effort to "fake" the test, is an exponential process; with my limited knowledge, I don't see right now how the test can be faked without trying a lot of pairs, so for large enough numbers, it is MUCH faster to do the test than to try to fake it. You are totally right.