20200619, 04:21  #144  
"Pavel Atnashev"
Mar 2020
100101_{2} Posts 
Quote:
No, it allows to cheat with only first two intermediate points. Basically, for free. Pietrzak VDF is secure as long as you use hashes that depend on the current result. You can't do any proof calculations before the end of test. 

20200619, 05:28  #145 
P90 years forever!
Aug 2002
Yeehaw, FL
7,043 Posts 

20200619, 05:48  #146 
"Pavel Atnashev"
Mar 2020
37 Posts 
As a matter of fact, yes! I have an idea and already presented it.
Don't go that deep. 6..8 is enough. Offload exponentiation at the final iteration to participants, there's a secure way to do it. You slash upload size in half, VDF overhead in half, with almost the same amount of computation necessary. Also temp storage size stops exploding. And the verification process becomes scalable, the server has to do only a small amount of work. At least consider this as an option. It's not the only way to do Pietrzak VDF, but it's an option. 
20200619, 06:35  #147  
"Mihai Preda"
Apr 2015
3·5·7·11 Posts 
Quote:
The hash size only affects the producer of the proof; the proof generation overhead (i.e. on top of the PRP test) is roughly linear with the hash size. 

20200619, 07:49  #148 
"Pavel Atnashev"
Mar 2020
100101_{2} Posts 
In cheating scenario with u_i = const the probability of finding a solution increases with the decrease of hash size. Lower distance also helps. I personally like 64 bit, but that's a feeling. I also prefer hashes to not be divisible by small primes to decrease the probability of roots of unity messing around.

20200619, 11:49  #149  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
1098_{16} Posts 
Quote:


20200619, 15:23  #150  
P90 years forever!
Aug 2002
Yeehaw, FL
7,043 Posts 
Quote:
Algorithm: x = sha3256(something) x = x & (2^48  1) if (x < 2^32) x += 2^48 x = x  1 while (some combo of x divisible by 3,5,7 or x is composite or x == previous_hash_value) x += 2 return x Last fiddled with by Prime95 on 20200619 at 15:53 

20200619, 16:56  #151  
P90 years forever!
Aug 2002
Yeehaw, FL
7043_{10} Posts 
Quote:
Quote:
Last fiddled with by Prime95 on 20200619 at 17:05 

20200619, 17:28  #152  
"Pavel Atnashev"
Mar 2020
37 Posts 
Quote:
prp(A[N1], topK/(2^N)) == B[N1] Only this one is offloaded to a verifier. In Pietrzak terminology A[N1] = x_t, B[N1] = y_t, and let's call 2^(topK/(2^N)) = distance. So, the server sends A[N1] (one number, not the whole proof) to a verifier and asks to perform topK/(2^N) modular squarings. The verifier returns the result, it doesn't have to be the whole number, res64 is enough. The server compares the res64 to res64(B[N1]) and if it matches, the test is verified. The verifier makes no decisions, just performs a few iterations. Computation of (x_t, y_t) have to be done by a trusted authority (otherwise it can be just a random number and its ^distance pair). That's why I call this process "certification". And x_t becomes a "certificate" which can be validated by anyone. (For clarity, I omit the additional step of ^random, but it is there, in the certificate). 

20200619, 17:37  #153 
"Pavel Atnashev"
Mar 2020
37 Posts 
My certification/validation scheme allows to securely shift computation between parties with a simple goal to limit depth to 6..8, limit bandwidth, limit server load and limit temporary storage.

20200619, 19:57  #154  
P90 years forever!
Aug 2002
Yeehaw, FL
1B83_{16} Posts 
Quote:
In your opinion, is there any security risk in sending A[N1] to the original tester? In other words, should we apply the "^random" operation on the server just to be safe? The security risk becomes the server database if res64(B[N1]) is stored in the database in plaintext. That is easily solved. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
phi function  rula  Homework Help  3  20170118 01:41 
delay in crediting?  ixfd64  PrimeNet  7  20081020 20:45 
Why delay between posts?  JHagerson  Forum Feedback  1  20060513 21:30 
Minimum delay between server connections  vaughan  ElevenSmooth  5  20050908 17:17 
Stats delay  ltd  Prime Sierpinski Project  10  20050808 13:38 