VDF (Verifiable Delay Function) and PRP

[Uncwilly]

What about having known folks, like select forumites, mods, or other well trusted users do some of that as part of their routine work? If one of my machines gets 1 hour of work to verify once a week with a 1 week max turnaround (24 hours nominal), that would be no burden. It would have to jump to the top of the worktodo.

[Xyzzy]

Originally Posted by Uncwilly

What about having known folks, like select forumites, mods, or other well trusted users do some of that as part of their routine work?

We would be willing to do whatever furthers the project.

We are sure others would as well.

Maybe make it a new work-type?

[preda]

Originally Posted by Prime95

Is it feasible for a central server to do all the verifications? at what cost?

Benefits include halving the bandwidth requirements, remove the worry of a malicious verifier.

If there are 500 PRP tests a day coming in, and we went with power = 10, the server would need to do 50M iterations a day. Is AWS the best solution?

That is a valid alternative. Indeed power=10 would make more sense in this setup, pushing a bit more work on the PRP tester to lighten a bit the server; with an approximate ratio of 9-to-1 of effort between the producer and verifier.

The verification effort with power==10 is (a bit more than) 1/1024 of one PRP test. So to verify 500 PRP tests per day, the load would be about half-a-PRP-test per day. This is a bit too much for a single CPU. I think this is doable by either two good CPUs, or by a single GPU.

[Prime95]

Originally Posted by preda

The proof verification also generates a 64-bit verification code that must match (true, this was not discussed here yet). This 64-bit code is used to check that the verification is genuine, if not matching something's amiss and more validation is needed.

I finally have read through the entire thread. A very clever scheme. I want to read the other paper and think on the whole process some more.

I was about to comment "how do we know the verifier did his work?", but I see that you've already come up with a plan for this.

On the save file format, my only comment is a dislike "Endian" formats. Can we make the residues E/8+1 bytes from MSB to LSB?

[preda]

Originally Posted by Prime95

On the save file format, my only comment is a dislike "Endian" formats. Can we make the residues E/8+1 bytes from MSB to LSB?

I'm not against using bytes, but to me it seems more natural to order LSB-to-MSB. And the res64 is nicely aligned at 0. And the "LSB-to-MSB bytes" just so happens to convert very simply to/from the internal format on a LE arch, which is pretty much all of them now. Is there a reason for the reverse order?

[Prime95]

Originally Posted by preda

Is there a reason for the reverse order?

Habit. I'm not averse to LSB to MSB ordering. Only Endian encoding, which IMO encourages architecture-dependent shortcuts in programming.

[retina]

If it was a vote then I'd vote for LSB at the lowest address.

It just makes sense that way.

[Prime95]

Originally Posted by preda

The proof file starts with one line containing textual (ASCII) information with a single '\n' line terminator. This line is called the header, and contains in order:
"PROOF" : a string identifying the file format
1: the version of the proof file format
exponent
topK
power
finalHash, a 64-bit hash value (discussed below).

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.

[Prime95]

Originally Posted by preda

The original tester (that runs the PRP test) is also the one computing (generating) the PRP-proof. The cost is two-fold: a storage (disk space) cost, and a computation cost.

1. Space Cost
For M0, we need to save the residue at iteration topK/2 (one residue).
For M1, we need to save the residues at topK/4 and 3*topK/4 (two residues).
And so on, for M[i] we need to save 2^i residues when going through the initial PRP test.

So for a proof of power N we need to save in total 2^N residues. (for a 100M exponent, a residue is roughly 12MB in size, so for a proof of power==9 we need about 6GB of disk space for residue storage during the progress of the PRP test).

Once the proof has been computed (and presumably verified to make sure it was computed correctly) this storage can be released. The size of the proof itself (of power N) is just N+1 residues, so for power==9 the proof size is 120MB (much smaller than the transient space requirements of 6GB during the PRP test).


2. Computation Cost
In order to be a proof, it must be non-fakeable (i.e. it must be impossible to "prove" something false), even when a dishonest author purposely attempts to fake it. This resistance is achieved through the use of the random value "h" when checking that
prp(A^h * M, topK/2) == M^h * B
the random value "h" being chosen by the verifier.

But the particular choice of "h" above impacts the computation of the follow-up middles (M1, M2, etc) which must be computed by the proof author. This conundrum is solved by using the Fiat-Shamir heuristic https://en.wikipedia.org/wiki/Fiat%E...amir_heuristic

The FS-heuristic allows the proof author to know the value of "h" (i.e. removes the liberty of the verifier to choose any random value he'd like), as long as the proof author has absolutely no liberty in choosing or affecting the value of h in the proof context. (if the proof author could choose the value of "h", he could fake the proof). This is achieved by setting "h" from a secure hash of the proof context: h = hash(E, topK, B, M0).

Similarly to how we have a sequence of middles M0, M1.., we also have a sequence of such exponents "h", we're going to call them h0, h1..:
contextHash = hash(E, topK, B)
h0 = hash(contextHash, M0)
h1 = hash(h0, M1)
h2 = hash(h1, M2)
etc.

For computing the middle M[i], we use a set of saved 2^i residues, raised to powers computed from products of h[0] ... h[i-1]. (thus, M0 is always stored in the proof "unadultered" by any hash). Example:
M0 = residue[topK/2]
M1 = residue[topK/4]^h0 * residue[3*topK/4].
M2 = r[topK/8]^(h1*h0) * r[3*topK/8]^h0 * r[5*topK/8]^h1 * r[7*topK/8]
etc.

The bulk of the proof computation cost is in these exponentiations residue^product(h). It grows a bit faster than 2^proofPower. I estimate the computation cost for a proof of power==9 to be the equivalent of 200K iterations, which for a 100M exponents corresponds to the proof computation cost being 0.2% of the PRP test itself (so, low enough).

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.

[R. Gerbicz]

Originally Posted by preda

For computing the middle M[i], we use a set of saved 2^i residues, raised to powers computed from products of h[0] ... h[i-1]. (thus, M0 is always stored in the proof "unadultered" by any hash). Example:
M0 = residue[topK/2]
M1 = residue[topK/4]^h0 * residue[3*topK/4].
M2 = r[topK/8]^(h1*h0) * r[3*topK/8]^h0 * r[5*topK/8]^h1 * r[7*topK/8]
etc.

The bulk of the proof computation cost is in these exponentiations residue^product(h). It grows a bit faster than 2^proofPower. I estimate the computation cost for a proof of power==9 to be the equivalent of 200K iterations, which for a 100M exponents corresponds to the proof computation cost being 0.2% of the PRP test itself (so, low enough).

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)

[Prime95]

Originally Posted by preda

For computing the middle M[i], we use a set of saved 2^i residues, raised to powers computed from products of h[0] ... h[i-1]. (thus, M0 is always stored in the proof "unadultered" by any hash). Example:
M0 = residue[topK/2]
M1 = residue[topK/4]^h0 * residue[3*topK/4].
M2 = r[topK/8]^(h1*h0) * r[3*topK/8]^h0 * r[5*topK/8]^h1 * r[7*topK/8]
etc.

The bulk of the proof computation cost is in these exponentiations residue^product(h). It grows a bit faster than 2^proofPower. I estimate the computation cost for a proof of power==9 to be the equivalent of 200K iterations, which for a 100M exponents corresponds to the proof computation cost being 0.2% of the PRP test itself (so, low enough).

Originally Posted by R. Gerbicz

You can do those costly residue^product(h) computations in the proof much faster than the described trivial way
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.

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.

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.