VDF (Verifiable Delay Function) and PRP

[R. Gerbicz]

Originally Posted by Prime95

Residues are written to disk as the PRP test progresses. At test end, the residues are read from disk - only one in memory at a time - to produce the proof.

I took "grouped" to mean that we do not raise a residue to the power of a product of hashes (e.g. r0 ^ (h0 * h1 * h2)). My proof-of-concept proof generator is attached. calc_middle is the recursive routine that calculates a Middle value to output.

You could use sliding window technique in void exponentiate (gwhandle *gwdata, gwnum x, uint64_t power) .

[preda]

Originally Posted by Prime95

I changed my random exponent to a prime number between 33 and 48 bits. Stole some Rosetta C code for Miller-Rabin test.

To allow portable verification of proofs, producers/verifiers must agree exactly on the hash algorithm (identical hash output). To make software errors less likely, it's best not to share the code but to use independent implementations. That's why I try to keep the hash schema simple, to make it easy to specify and independently implement correctly. I don't see yet why it's beneficial to have the hash be prime.

[Prime95]

Originally Posted by Prime95

I changed my random exponent to a prime number between 33 and 48 bits. Stole some Rosetta C code for Miller-Rabin test.

Silly me. The code did not work for 64-bit ints.

Originally Posted by preda

To allow portable verification of proofs, producers/verifiers must agree exactly on the hash algorithm (identical hash output). To make software errors less likely, it's best not to share the code but to use independent implementations. That's why I try to keep the hash schema simple, to make it easy to specify and independently implement correctly. I don't see yet why it's beneficial to have the hash be prime.

We're not talking about the hash values. This is the A[N]^random value sent to the user to run topK/(2^N) squarings. The user's result is compared to B[N]^random. Only the Primenet server ever sees the random value.

I haven't coded any hash algorithms yet, pending an agreement on algorithm. My proof-of-concept hash_function is h0=const, h[i]=(prev_hash + 15). I have plenty other work to do.

[patnashev]

Originally Posted by preda

So you find R3!=1 such that R3^3==1, ok. You multiply Y (the final residue) by R3, this is the "faked result". What do you next?

Just compute and upload the proof like it's a regular composite number.

Originally Posted by preda

If you compute the middles in the usual way from the true saved residues, the proof would not verify. -- isn't that so?

Yes, the proof would not verify, x_t^distance != y_t. But consider the additional anti-cheating step at the end of the certificate generation (x_t^random, y_t^random). If the random is divisible by 3, then R3^random = 1, and y_t turns into true value. The verification passes, but the decision of the primality test is compromised.

This works only for prime numbers and is easy to prevent, just require gcd(random,N-1)=1. Alternatively, if N-1 has specific form, you can test just specific factors. Proth N-1 is very smooth, Mersenne N-1 has divisors that look like Mersenne numbers themselves (if I understand correctly).

Also consider the possible real world scenarios, which apply to all such cheating schemes. If you going to cheat with 1/1000 chance of success, you better hit it at the first time. Because if you fail, instead of being credited with a prime find you'll be banned from the prime universe.

[preda]

Originally Posted by Prime95

We're not talking about the hash values. This is the A[N]^random value sent to the user to run topK/(2^N) squarings. The user's result is compared to B[N]^random. Only the Primenet server ever sees the random value.

Originally Posted by patnashev

Just compute and upload the proof like it's a regular composite number.

Yes, the proof would not verify, x_t^distance != y_t. But consider the additional anti-cheating step at the end of the certificate generation (x_t^random, y_t^random). If the random is divisible by 3, then R3^random = 1, and y_t turns into true value. The verification passes, but the decision of the primality test is compromised.

This works only for prime numbers and is easy to prevent, just require gcd(random,N-1)=1. Alternatively, if N-1 has specific form, you can test just specific factors. Proth N-1 is very smooth, Mersenne N-1 has divisors that look like Mersenne numbers themselves (if I understand correctly).

It seems I was misunderstanding, thinking that you're talking about the hash algorithm and the whole 64/48/32 bits discussion. Instead you were talking about the random used for the final verification, which is server's business only. I have absolutely nothing against using primes or whatever for that final random.

For the hash algorithm, the question still stands whether any hardening is needed. Unless hardening in shown to be needed, the simple truncation of SHA3-256 of the agreed-upon size should be used as being the simplest.

[patnashev]

I use 64-bit md5 with no divisors <1000 "just in case". But I see the appeal of shorter unhardened hashes. Server load is linear with hash size.

[R. Gerbicz]

Originally Posted by Prime95

My proof-of-concept proof generator is attached. calc_middle is the recursive routine that calculates a Middle value to output.

With those recursive calls it will use power residues in stack memory.
Is it intended? You could do this also in disk (using the same size).

[preda]

Originally Posted by R. Gerbicz

With those recursive calls it will use power residues in stack memory.
Is it intended? You could do this also in disk (using the same size).

That's fine, in this case the max amount of residues alive at any time because of the recursion is the max-depth of the recursion, equal to the "power" of the proof. That would be under 1GB total normally.

Edit: I missed "on the stack". I think they are not on the stack, but on the heap (gwalloc/gwfree)

[patnashev]

Brute-force attack:

for (h0 = 1; h0 < max_hash; h0++)
{
    y = x^(h0*h0);
    u_1 = x^(-h0);
    if (hash(y) == h0)
        break;
}
u_i[i>1] = 1;

[wedgingt]

The ecm program (which uses libgmp) has a simple format for P-1 and P+1 save files:

METHOD=P+1; B1=4299950000; N=71214505243381290342289358884062903424409248782929244751545497061659676830181069893652125357260888204241872521545920863671266091156523160599053871978101713571014846232692265302193576
41629634637632902818929376633641165995708421341209033069328278856607776384578328080846029713646218471064646270016968312691054210973840071649700163924918271; X=0x41a4cc7860dfb15fcdd98bcdbccc9b8b63796ad4e38c6fb055
967b800ea0c27fb8c1b5ff8f2a1d87c50196bc5869ced0d93597a447d7f7e233ead9e7036256b64a1ce7720274b605632205655335a629c10691284cce6ef7528b871a71e7e022c4ccc5a152b6e6b858dcda73ba0fde2f769912d837a4b164d5626ad62bc0752b2f7a1
73626a51231ba139d12; CHECKSUM=3059612973; PROGRAM=GMP-ECM 7.0.4; Y=0x0; X0=0xf7b36de6; Y0=0x0; WHO=wedgingt@wedgingt; TIME=Thu Apr 11 13:58:53 2019

This example is for M1207; the N value here is M1207 itself since there are no known factors. B1 is the stage 1 bound of P+1 and X is the residue mod M1207. I already have a small Perl module to deal with this format that allows arbitrary values and "keys" (like METHOD, B1, and N) and it could easily be supported in Python as well.


-- Will

Originally Posted by Prime95

Let's change "exponent" to number being proved - in gpuowl's case "Mexponent". When prime95 adds PRP proofs, the number being PRP'ed can be (k*b^n+/-c)/known_factors.
Examples: M1234567, M4321/8768767, 653*3^123456-15

We need a file naming scheme. I've not done any research, but suggest a .proof or .vdf extension. So for a Mersenne number, Mexponent.proof. For a Mersenne cofactor, maybe Mexponent_cofactor.proof or Mexponent_number_known_factors.proof. I'll come up with something for the more general (k,b,n,c) case.

[preda]

Originally Posted by patnashev

Brute-force attack:

for (h0 = 1; h0 < max_hash; h0++)
{
    y = x^(h0*h0);
    u_1 = x^(-h0);
    if (hash(y) == h0)
        break;
}
u_i[i>1] = 1;

The above attack would not be practical for 32-bit hash already, as it require in average 2B loopings, and each loop body requires significant work.

The attack would be so-much-more less practical for 48 or 64 bit hash. So, I'd take the above attack more like an indication of "lack of a practical attack", right?