VDF (Verifiable Delay Function) and PRP

[Prime95]

With these advances in the cost of creating a proof, we need to consider power=11,12 ... maybe even 13 or more for a 100M test. Each halving of the work the verifier must perform makes an AWS solution more attractive (cheaper). If 600 PRP tests a day can be verified with ~600*100000000/4096 = 15 million PRP iterations, then just a few AWS instances could be running at spot pricing to easily keep up. We definitely need an experienced AWS person to weigh in on the feasibility and daily cost of such a setup. I really, really, really like all PRP proofs being verified by a single trusted setup rather than assignments to random folks on the internet.

The proof file format should change in a minor way. The preferred topK value should be the next multiple of 2^power above the exponent. That is what prime95 will do.

[R. Gerbicz]

Originally Posted by Prime95

So for preda's power==9 example, we'll do 511 exponentiations (each costing 63 squarings plus on average 31.5 multiplications) and 511 multiplications. Assume multiply cost approximately equals squaring cost and we get a total proof building cost of 48,800 PRP iterations.

You forget the topK/2^e squarings. And there is no other cost in the proof.

Originally Posted by Prime95

Now a question. Are we gaining anything by using a 64-bit h value? Why not 32 or 16 bits reducing cost to 24,300 or 12,000 PRP iterations.

Maybe the original paper talked about 64 bit values, I'd say 16 bits would be still OK.

[retina]

Since the proof file is going to be deleted once it has been sufficiently checked, then I suggest to have the server permanently save the normal 64-bit residue (like we have now) so that any interested parties can run a full test to verify the integrity.

If some future researcher were to randomly choose candidate exponents and check the PRP against the 64-bit residue it would give good confidence that all the numbers were really run.

[R. Gerbicz]

Originally Posted by Prime95

With these advances in the cost of creating a proof, we need to consider power=11,12 ... maybe even 13 or more for a 100M test.

That doesn't needs uploading 2^power full residues per test?

[axn]

Originally Posted by Prime95

Each halving of the work the verifier must perform makes an AWS solution more attractive (cheaper). If 600 PRP tests a day can be verified with ~600*100000000/4096 = 15 million PRP iterations, then just a few AWS instances could be running at spot pricing to easily keep up.

This sounds like a use case for AWS Lambda (serverless) set up. Probably not the cheapest option, though.

[preda]

Originally Posted by Prime95

I believe we can reduce the space cost considerably. We are saving 2^power residues because we cannot know the values of h0, h1, h2, h3 ... until the PRP completes. In the academic paper, this is because the author and the prover cannot communicate in advance. We can!

I propose the h values be predetermined by the some formula agreement. The author still has no ability to select the h values, thus the proof is still safe from fakery. Here's one proposal: h0 = sha256("We love PRP proofs" || exponent). h1 = sha256(h0 || exponent), etc.

knowing the h-values in advance reduces temp space requirement from 2^power residues to power residues.

I thought about that too, but I think it doesn't work. The core idea of the "Shamir heuristic", which allows to transform the interactive proof into an non-interactive one, requires that the author *can not* change any bit of the result without also changing the "challenge values" (in our case, the hashes).

If the hashes are fixed ahead of time (including fixed "per exponent" as you propose), this kind of attack becomes possible:

The verification is:
(A^h * M)^q == M^h * B. (where q=2^k, but that's not important)

If "h" is fixed, the attacker can satisfy the equality by using
B:= (A^h)^q * M^(q-h)

which represents a cheat. (this line of attack does not work if "h" is backward-dependent on B)

[preda]

Originally Posted by R. Gerbicz

That doesn't needs uploading 2^power full residues per test?

What needs uploading is the proof. The proof contains "only" (power + 1) residues.

[preda]

Originally Posted by Prime95

With these advances in the cost of creating a proof, we need to consider power=11,12 ... maybe even 13 or more for a 100M test. Each halving of the work the verifier must perform makes an AWS solution more attractive (cheaper). If 600 PRP tests a day can be verified with ~600*100000000/4096 = 15 million PRP iterations, then just a few AWS instances could be running at spot pricing to easily keep up. We definitely need an experienced AWS person to weigh in on the feasibility and daily cost of such a setup. I really, really, really like all PRP proofs being verified by a single trusted setup rather than assignments to random folks on the internet.

The proof file format should change in a minor way. The preferred topK value should be the next multiple of 2^power above the exponent. That is what prime95 will do.

OK for defining topK to be the first multiple of 2^power after the exponent.

(My initial idea of having topK a multiple of a fixed power of 2 originated from my desire to be able to generate proofs of different powers from the same set of "saved residues" from a PRP test; (this was mainly for debugging). I don't think we need this feature anymore, and thus the first multiple of 2^power is the natural choice for topK)

I have an idea for how to speed up the proof generation for higher powers. Then power==14 becomes feasible. There a verification would cost about 8K iterations, yay! I'll try to validate this.

Correction: with power==14 the tail (the iterations past E up to topK) will be 8K iterations on average, thus the total average cost of about 16K iterations, or 24K if the verifier also computes prp(9, topK - E) to decide compositeness. Thus power==14 is too large.

power==13 would have a tail of 4K iterations on average. Thus total verification cost estimated to 2K + 12K + 2*4K == 22K iterations for a 100M exponent.
power==12, tail of 2K, verification estimated 2K + 25K + 2*2K == 31K iterations. (the first 2K approximates the cost of the exponentiations in the "walking the middles" part of verification)
power==11, tail of 1K, estimated cost 2K + 50K + 2*1K == 54K its.

Maybe power==12 looks like a good choice then?

[preda]

Originally Posted by Prime95

The proof file format should change in a minor way. The preferred topK value should be the next multiple of 2^power above the exponent. That is what prime95 will do.

Now the topK is not store in the file anymore. It is defined to be what we spec here. (an implicit value, not stored in the file, not hashed).

[preda]

Originally Posted by Prime95

Now a question. Are we gaining anything by using a 64-bit h value? Why not 32 or 16 bits reducing cost to 24,300 or 12,000 PRP iterations.

The size of the hash gives the security of the proof, i.e. the effort needed to produce a fake proof. I would certanly not go with anything less than 32bits for the "h" exponents. I was not sure whether 32bits is secure enough though; from an abundance of caution I chose to go one step up to 64bits, which IMO seems big enough (secure enough).

I might agree with changing that to 32bits (even if that significantly reduces the "security" of the proof). But note also that reducing this size from 64b to 32b also does not gain much either.

[preda]

Originally Posted by R. Gerbicz

You can do those costly residue^product(h) computations in the proof much faster than the described trivial way. And basically the same trick worked what I've already written in a post. After writing checked the current source code and it seems you still used those slowish product(h) way (somewhat hard to read it without comments).

The setup, fix the base=3,
and let r[i]==3^(2^(i*topK/2^e)) mod N
store the residue with space=topK/2^e for i=0,1,2,..,2^e (ofcourse r[0]=3).

What would be the proof check say for e=2 ? Easy it is checking:

( r[0]^(h0*h1)*r[1]^h0*r[2]^h1*r[3] )^(2^(topk/4)) == r[1]^(h0*h1)*r[2]^h0*r[3]^h1*r[4]  mod N

[guessing that h_k is in the exponent for r[d] in the left side iff the (e-1-k)-th bit of d is zero;
then the right side is easy, because just write r[d+1] for r[d])

You can rewrite the left side in a more compact form, using much less computation:

(r[0]^h0*r[2])^h1*r[1]^h0*r[3] and you can write the right side similarly.

Each r[i] term appears exactly once, for t=2^e you'll do t-1 exponentations (to a 64 bits exponent) and t-1 multiplications.
Big gain over your trivial way, now counting everything in powering to a 64 bits number: (e/2)*t exponentations and (t-1) multiplications.

And that makes sense for e=10. And in these costs you can double everything, because you'll do the same
in the right side of the equation.

ps. e=2 is still small example but you see the idea (r[0]=3 the only small base in the left side)

Thanks, I'll look into implementing it this way.