VDF (Verifiable Delay Function) and PRP

[kriesel]

Originally Posted by preda

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).

A little redundancy or more completeness is a good thing.
What happens if you don't have topk in the file, and years from now want to transition to a different power or topk strategy?
Seems simpler for a transition, and reliable before one, to have it explicitly contained in the file.
The server or verified system can check that value and produce an error message if it doesn't match expectations, putting the server or verifier operator on notice there's a new case that needs handling, or some other issue.

[retina]

Originally Posted by kriesel

A little redundancy or more completeness is a good thing.
What happens if you don't have topk in the file, and years from now want to transition to a different power or topk strategy?

Yeah, I wondered about that also.

What is it, 8 extra bytes or something? In a 120MB file. I don't think it makes a major difference to anything.

It's like asking for the 1c change after you just paid $999,999.99 with your million dollar note.

[Prime95]

Originally Posted by preda

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

It is too early for us to decide what the default power should be. It will depend on bandwidth costs, storage costs, and compute costs. I could easily see gpuowl and prime95 offering a choice to reduce the default power value to save 10-20% on bandwidth cost for the user.

You could choose a different default power value if, for a particular exponent, there is no increase in tail iterations when power is increased.

Originally Posted by preda

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).

Agree with those that say storing topK value is cheap.

Originally Posted by preda

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

Would making h backward-dependent on the first middle value also thwart the cheater?(see next post) I think this lets you cut the amount of temp storage in half. If that works, would making h0 dependent on the first middle and h1,h2... computable ahead of time be secure?

[Prime95]

Originally Posted by Prime95

Would making h backward-dependent on the first middle value also thwart the cheater? I think this lets you cut the amount of temp storage in half. If that works, would making h0 dependent on the first middle and h1,h2... computable ahead of time be secure?

Originally Posted by preda

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

OK, I see that making h dependent on M does not help.

A primer on potential cheating might be useful.

For example, if we make h0 dependent on B, but make h1...hn known at startup, does that make cheating easy or just a little less difficult. If this were safe, I can get by with 3*power temporaries -- much better than 6GB at power==9.

I also did not understand how increasing the bit-size of h0...hn makes the proof more secure.

[preda]

Originally Posted by Prime95

OK, I see that making h dependent on M does not help.

A primer on potential cheating might be useful.

For example, if we make h0 dependent on B, but make h1...hn known at startup, does that make cheating easy or just a little less difficult. If this were safe, I can get by with 3*power temporaries -- much better than 6GB at power==9.

I also did not understand how increasing the bit-size of h0...hn makes the proof more secure.

My understanding is partial, so I can't analyze clearly the cheating mechanisms and difficulty.. I relied to some degree on trust in the math-grounded Pietrzak's article about the security claims. I do believe their technique is secure. Now if we start relaxing things, it's likely it won't be as secure as they wanted it anymore. Whether that's still good enough for us, I don't know..

The proof is like a chain of links. The whole chain is secure because each link is secure. The structure of a link is the classic "(A^h * M)^q==M^h * B".

The assumption is that the link above verifies simultaneously the two indepenedent statements: A^q==M *and* M^q==B. Now of course there is more "liberty", or degrees of freedom, in the two statements vs. the compound one (probably in the "linear combinations" sense). The equivalence only holds if the first statement is verified for *multiple* values of h. Afterwards *multiple* is relaxed to "one random value of h", which is in turn relaxed to the hash in the Shamir heuristic setup.

Let's see if we extremely limit the range of "h", let's say we always have h==1. Then the implication above obviously does not hold anymore:
(A*M)^q==M*B does not imply (A^q==M && M^q==B)

If h has values from a small set (i.e. fewer bits), then there is trouble at the step that equivalates "holds for multiple values of h" with "holds for one random value of h", because this equivalence fails at a rate of 1/#h. (thinking of it this way: the attacker can easily manufacture matching fake data for *one* specific value of h. His cheat is detected with a rate of 1/#h (where #h is the cardinality of the set(h)).

Taking a step back, let's look at what would be a practical attack in our specific case. If I were an attacker, I would like to generate a valid proof for an incorrect final-B, any B would do. This is because "any" B would most likely indicate composite, and if I'm able to do this I can hide a prime. Now how much effort would it be reasonable for an attacker to put in this endeavor? how high should we set the effort bar for a successful cheat?

Indeed I would also like to see an analysis of the cheat effort (which might allow us to lower the bits of h).

[Prime95]

The 6GB temp space requirement for a power==9 test is a problem for me. I use 32GB SSDs on a machine with 3 GPUs running 6 gpuowl instances. That's 36GB of temp space.

Or consider someone going after the 100M digit prize. We'd like to use a higher power (say 12) to reduce workload on verifier. That's 4096 40MB residues = 160GB. I can see a lot of users running out of disk space.

In the power==12 example, if we make h0 dependent on B but h1...h11 are fixed we can reduce temp storage to about 150MB. How much have we weakened the proof? I think you are saying (please correct me if I've misunderstood) that a fixed h1 through h11 allows the bad guy to pick a fake B,M pair using roughly this method:

h0 = hash(B)
hh = h0*h1*h2*h3*h4*h5*h6*h7*h8*h9*h10*h11
Find M such that B = (A^hh)^q * M^(q-hh), where q=2^k and k=12

To me, the complete non-expert in security, this seems pretty daunting. I will agree that if h1 through h11 were not fixed then it would be downright impossible. How difficult is it to find the (q-hh)-th root of a 100-megabit number?

[Prime95]

Originally Posted by Prime95

To me, the complete non-expert in security, this seems pretty daunting. I will agree that if h1 through h11 were not fixed then it would be downright impossible. How difficult is it to find the (q-hh)-th root of a 100-megabit number?

I think I can toughen this up some more and still keep temporary space requirements low. Make h1 = hash(M0). Let h2, h3, ... h11 remain pre-computable. This is brutal to Mr. bad guy because "Find M such that B = (A^hh)^q * M^(q-hh)" becomes extremely hard because hh now depends on M -- a nasty feedback loop.

In case it is not obvious why pre-computing h values saves temp space for the proof author, an example. If I understand correctly, if power >= 5 one of the middle values in the proof is computed by combining 16 different intermediate residues:

(((r0^h3 * r1)^h2 * r2^h3 * r3)^h1 * (r4^h3 * r5)^h2 * r6^h3 * r7)^h0 *  ((r8^h3 * r9)^h2 * r10^h3 * r11)^h1 * (r12^h3 * r13)^h2 * r14^h3 * r15

As r0, r1, r2, r3 become available they can be combined because h3 and h2 are known in advance. We are now a quarter way through the PRP test and h1 will not be known until M, the half-way point residue, is available. In the meantime, we can combine r4, r5, r6, r7 because h3 and h2 are known. At the PRP halfway point we can compute h1 and combine r0-r3 and r4-r7 into one value, but we do not know h0 yet. During the second half of the PRP test, we can compute the r8-r15 part of formula with at most 2 temporaries. When the PRP completes, we take B (the final residue) and compute h0, which then lets us complete the computation of this middle value.

[preda]

Originally Posted by Prime95

This is brutal to Mr. bad guy because "Find M such that B = (A^hh)^q * M^(q-hh)" becomes extremely hard because hh now depends on M -- a nasty feedback loop.

But how hard is it to find M when "hh" above is fixed?

Or, the equivalent (I think) question:

how hard is it to find *a* residue X that satisfies the modular equation:
(A^h * X)^q == X^h * B
given A, B, h and q (X, A, B are modular residues, q and h integers, given).

?

(A genuine question for me, maybe a trivial question for the math people around here, thanks!)

[preda]

Originally Posted by Prime95

The 6GB temp space requirement for a power==9 test is a problem for me. I use 32GB SSDs on a machine with 3 GPUs running 6 gpuowl instances. That's 36GB of temp space.

Or consider someone going after the 100M digit prize. We'd like to use a higher power (say 12) to reduce workload on verifier. That's 4096 40MB residues = 160GB. I can see a lot of users running out of disk space.

There is one simple "trick" that I'm going to implement (not implemented yet):
We use the stored temporary residues only to save work ("faster") vs. the trivial way of computing the middle. But after a certain point, the trivial way becomes faster than using saved residues.

Constructing the proof, at some step "i" we have the A[i] and B[i] and want to compute M[i] the middle between A[i] and B[i]. One way is to combine in the fancy way the saved residues, but of course we can also simply do a number of iterations ("half the distance between A[i] and B[i]") from A[i] and find M[i] that way.

As "i" grows, using saved-residues becomes exponentially slower, while doing the iterations becomes exponentially faster. The reversal point, when the later becomes faster, is somewhere around 8.

For example, by saving only 2^8 residues, when building a proof of power 9, we would work out the first 8 middles from residues, and the last one, the 9th, by doing E/512 iterations.

When computing a proof of power 12, the same: save 256 residues only, and afterwards do E/512 + E/1024 + ... + E/4096 iterations. This way the temp storage is capped and smaller.

(In parallel I also try to understand if the "fixed hashes" you proposed would work)

[patnashev]

This is not efficient from the point of view of the whole system. You decrease verifier's computations at the expense of prover's computations AND increased bandwidth requirements.

[Uncwilly]

Originally Posted by patnashev

This is not efficient from the point of view of the whole system. You decrease verifier's computations at the expense of prover's computations AND increased bandwidth requirements.

Eliminating the need for a whole double check is a vast saving to the system. Even if it cost 20% more it will save that 80% later.