|
VDF (Verifiable Delay Function) and PRP
On HackerNews today I saw this story talking about VDF, "Verifiable Delay Function", which in one variant is: f(x, N, M) = x^(2^N) mod M
[url]https://news.ycombinator.com/item?id=20587753[/url] [url]https://aws.amazon.com/blogs/startups/competition-forever-change-blockchain/[/url] [url]https://blog.trailofbits.com/2018/10/12/introduction-to-verifiable-delay-functions-vdfs/[/url] Apparently they are planning on developing an ASIC to compute that. It would be nice if that ASIC could be re-purposed to wider modular squarings. Another interesting aspect is the claim that the VDF result is verifiable in time O(log(N)), which might give an idea for a "proof of work" or verification of a PRP result. I don't understand yet how the VDF is verifiable though (in log time), maybe somebody can explain. |
Verifiable correct modular exponentiation, asymptotically fast results verification, and immunity to parallel speedups ... that sounds a lot like the problem described in the [url=https://www.mersenneforum.org/showthread.php?t=24385]20-year-old MIT LCS35 Time Capsule Crypto-Puzzle solved[/url] thread.
|
PRP verification
A list of VDF articles: [url]https://vdfresearch.org/[/url]
I found of interest in particular Pietrzak: [url]https://eprint.iacr.org/2018/627.pdf[/url] Wesolowski: [url]https://eprint.iacr.org/2018/623.pdf[/url] which present two different ways of constructing VDF proofs with different trade-offs. Pietrzak shows a proof that is fast to produce but log(exp)*residues in size; while Wesolowski shows a proof that is 1-residue in size, but costlier to produce. For example for a 90M exponent, Pietrzak's proof would be about 256MB in size vs. Wesolowski's 10MB. OTOH if I understand correctly Pietrzak's proof can be produced with negligeble computation cost (overhead relative to the PRP itself). Anyway, it seems this allows to get rid of the PRP double-check completely, at the cost of the large transfer (256MB per exponent) to a verifier. Such a posibility seems a huge opportunity to me. (of course I would have liked the proof to be smaller than that, but even at this size it seems like a huge gain vs. a double-check). In other words, the double-check is replaced by the verification which is log(doubleCheck) in effort. Maybe somebody more math-inclined can do a confirmation of how this applies to our particular context. |
[QUOTE=preda;523130]For example for a 90M exponent, Pietrzak's proof would be about 256MB in size vs. Wesolowski's 10MB. OTOH if I understand correctly Pietrzak's proof can be produced with negligeble computation cost (overhead relative to the PRP itself).
Anyway, it seems this allows to get rid of the PRP double-check completely, at the cost of the large transfer (256MB per exponent) to a verifier. Such a posibility seems a huge opportunity to me. (of course I would have liked the proof to be smaller than that, but even at this size it seems like a huge gain vs. a double-check). In other words, the double-check is replaced by the verification which is log(doubleCheck) in effort.[/QUOTE] This is very feasible. As a general rule, the AWS cloud only charges for outward data transfers. If you upload data from the Internet into S3 storage in the cloud, it costs absolutely nothing. I imagine that Google and Microsoft (Azure) would have similar policies. This makes sense, because if you upload something, you will be most likely be storing it for a while. So they make the upload bandwidth free and hope to make money over time with data storage fees. Downloading data out of the cloud to the Internet is also not free. So if a future version of Primenet was hosted in the cloud, your large-transfer verification would be entirely practical, and costless. The only question is, what to do with the 10MB or 256 MB file after the file has been processed and checked. If it's discarded, then there's no problem. If you want to archive it for the long term just in case, then the cheapest storage costs would be S3 Glacier Deep Archive, at $1 per TB per month. Normally you would only want to re-access such a file on very rare occasions. |
Discussing the feasibility of a future primenet in the cloud seems like jumping 10 steps ahead.
The main important issue is would this even work for Mersenne PRPs ? I do not claim to understand all the math and the proofs, but Pietrzak requires that N=p*q where (p-1)/2 and (q-1)/2 are also primes, which is not the case at all for the general composite Mersenne number 2[SUP]p[/SUP]-1. They generally have more than 2 factors which are not safe primes. [QUOTE]2.3 On using safe primes Another difference to the setting of [RSW96] is that we assume that N = p ยท q is the product of random safe primes, whereas [RSW96] just assume random primes. We do this to make sure that QR[SUB]N[/SUB] (and thus also QR[SUP]+[/SUP][SUB]N[/SUB]) contains no sub-group of small order, this property is required to prove statistical soundness. [/QUOTE] |
[QUOTE=ATH;523299]Discussing the feasibility of a future primenet in the cloud seems like jumping 10 steps ahead.
The main important issue is would this even work for Mersenne PRPs ? [/QUOTE] I think that it was already discussed, you can check the prp residue with high confidence if you find a factor of mp (obviously in real life after the test): Let res=2^mp mod mp if q divides mp then res=2^(mp mod (q-1)) mod q (and computing this is easy), and it is pretty hard to fake it without the knowledge of q. |
[QUOTE=R. Gerbicz;523301]I think that it was already discussed, you can check the prp residue with high confidence if you find a factor of mp (obviously in real life after the test):
Let res=2^mp mod mp if q divides mp then res=2^(mp mod (q-1)) mod q (and computing this is easy), and it is pretty hard to fake it without the knowledge of q.[/QUOTE] Ok that is nice, but it is not a huge game changer? We are not going to find new factors of a big percentage of Mersenne numbers after the 1st PRP test? I do not think this is what Preda had in mind, he wanted to eliminate PRP double checks completely. |
PRP verification with Pietrzak's protocol
I'll try to describe briefly Pietrzak's verification applied to PRP (as I understand it).
For m=2^p - 1 PRP(p) = 3^(m-1) mod m, or equivalently PRP(p)*9 = 3^(2^p) mod m. Let's fix the modulo m, and let's define f(x, T) := x^(2^T) mod m. for x=3, we compute y = f(x, p). How to prove to a verifier that the result is correct? We call the two actors involved "the author" who does the hard work of computing the PRP and producing the proof, and "the verifier" who receives the proof from the author and checks it. The goal is to convince the verifier that the result of the PRP is genuine and correct even when the verifier does not trust the author. If the author would send the verifier only the PRP result (y), the verifier could re-do the whole PRP computation *again* and thus validate the result (i.e. the double-check we do currently), but this would be very costly to the verifier, and wasteful because of the double computation. To make the verification easier, the author also sends the "middle" point u=f(x, p/2), which the author computed anyway on the way to y. (let's assume for a moment that "p" is even (although it isn't), so we can halve it without additional trouble). The verifier can now verify f(x, p/2)==u and f(u, p/2)==y, and this is equivalent to verifying f(x, p, m)==y; but still no reduction in work for the verifier. Because the two verification "branches" above share the same exponent p/2, they can be combined and verified together. Choosing a randon factor "r1" (let's say "r1" is a 64-bit number), the verifier computes the new seed x1= x^r1 * u, and verifies that: f(x1, p/2)==y1, where y1=u^r1 * y. So we transformed the verification f(x,p)=y into f(x1,p/2)=y1, halving the work. This "halving" is possible because the author sent to the verifier the value "u" (the middle value between x and y) -- so "u" is part of the proof. But if we have a way to halve the work of the verifier, why stop after only one halving step? let's look at the next halving: the author makes available "u1" the middle point between x1 and y1, u1=f(x1, p/4). r2 is another random 64-bit number chosen by the verifier, the verifier computes: x2=x1^r2 * u1 y2=u1^r2 * y1 and verifies f(x2, p/4)=y2 with only a quarter of the work of the author. And we can keep halving a bit more, making the work of the verifier log(work of the author). At some point, after k halvings, when p/(2^k) is small enough, the verifier checks directly f(x_k, p/(2^k))==y_k and this is the outcome of the verification. One may observe that we ask the author to publish as part of the proof the values u, u1, u2 etc, but those (excluding "u") depend on the random factors r1, r2, which in the setup above are chosen by the verifier. We solve this by having the author produce the random factors r1, r2 -- not by choosing them (because we don't trust the author) -- but instead by having these factors determined by applying a hash on the result, like this: r1=hash(y), r2=hash(y,y1) etc. (apparently this trick is called the Fiat-Shamir heuristic) [to be continued] |
It is also related to error checking (why not, because you are doing exactly the same thing, just for a subproblem).
In the recent 2 days I thought that it'd possible to beat the 2*sqrt(block) mulmods extra cost in the checking. Turned out it was wrong, but here (shortly) Let y(0)=b and y(i+1)=y(i)^(2^L) mod N Here when my check computes this there is a reduncancy, because you could compute y(0)*y(1)*...*y(t) in less then t multiplication exploiting the y(i+1)=y(i)^(2^L) mod N, it isn't that hard, the bonus is that you could even get the power also, bpow=b^(2^L*(t+1)) with a modular division (for Mersenne numbers it is cheap) , and a "strong" check, unfortunately here you need two computations, means that you could pass a strong check and still you have an error in the computation. So this is just not working in exactly this way. |
In fact these methods works also for the standard LL test, so there is an incredible fast "proof" to convince ourselves in just only O(sqrt(p)) multiplication, if we limit the exponents in the proof say in 64 bits.
Just let H(n)=(2+sqrt(3))^(2^n) mod Z[sqrt(3),mp]. LL says that mp is prime iff H(p-2)=0 (where here we omit the sqrt(3) stuff). Ofcourse we had to use this ugly sqrt(3) part also to enable the various fast checks for the powers in H(), if we would keep the conjugate part then we lose the power. The error checks goes in the usual way, but in the above ring, not the friendly Z. This is somewhat interesting, I mean having a fast "almost" true primality check. One drawback is the high storage of the ~sqrt(p) residues. (there is a tradeoff here, you can lower the storage by increasing the computation time). |
[QUOTE=R. Gerbicz;523833]In fact these methods works also for the standard LL test, so there is an incredible fast "proof" to convince ourselves in just only O(sqrt(p)) multiplication, if we limit the exponents in the proof say in 64 bits.
Just let H(n)=(2+sqrt(3))^(2^n) mod Z[sqrt(3),mp]. LL says that mp is prime iff H(p-2)=0 (where here we omit the sqrt(3) stuff). Of course we had to use this ugly sqrt(3) part also to enable the various fast checks for the powers in H(), if we would keep the conjugate part then we lose the power. The error checks goes in the usual way, but in the above ring, not the friendly Z. This is somewhat interesting, I mean having a fast "almost" true primality check. One drawback is the high storage of the ~sqrt(p) residues. (there is a tradeoff here, you can lower the storage by increasing the computation time).[/QUOTE] All of mersenne.org's workspace is p<10[SUP]9[/SUP], ~30 bits, and likely to take a century to cover. sqrt(p) residues or ln(p)? (or log[SUB]2[/SUB](p)?) At p=100M, CUDALucas save files are ~12.MB; x sqrt(p) = 12.2 MB x 10000 = 122. GB; 12.2 x ln(p) = 12.2 x ~19 = 224 MB. At p=332M, CUDALucas save files are 40.5MB; x sqrt(p)= 40.5 x 18221 = 738GB; 40.5 x ln(p) = 40.5 x ~20 = 810 MB. I have checkpoint file collections for single exponents up to ~10GB size. Local storage is cheap (3TB US$50, 6TB $120). Does this verification only confirm the LL run was completed, or does it check its correctness? |
[QUOTE=kriesel;523873] sqrt(p) residues or ln(p)? (or log[SUB]2[/SUB](p)?) [/QUOTE]
sqrt(p) residues. [QUOTE=kriesel;523873] Does this verification only confirm the LL run was completed, or does it check its correctness?[/QUOTE] You could even mix these strategies, do fast PRP checks on composites, and fast LL checks on proven (Mersenne) primes. You really need to do this, because in (2+sqrt(3))^(2^n)=U(n)+V(n)*sqrt(3) mod mp you could compute this only 2 times slower than the regular LL/PRP test! |
[QUOTE=kriesel;523873] Does this verification only confirm the LL run was completed, or does it check its correctness?[/QUOTE]
In my methods we check the final residue by simply reusing the (also) verified b^n0 residue in the ring ( for example b=2,3 or 2+sqrt(3) ), here say n-n0<sqrt(n), so doing a few iterations we can reach the final b^n. |
[QUOTE=preda;523438]
We call the two actors involved "the author" who does the hard work of computing the PRP and producing the proof, and "the verifier" who receives the proof from the author and checks it. The goal is to convince the verifier that the result of the PRP is genuine and correct even when the verifier does not trust the author. If the author would send the verifier only the PRP result (y), the verifier could re-do the whole PRP computation *again* and thus validate the result (i.e. the double-check we do currently), but this would be very costly to the verifier, and wasteful because of the double computation. To make the verification easier, the author also sends the "middle" point u=f(x, p/2), which the author computed anyway on the way to y. (let's assume for a moment that "p" is even (although it isn't), so we can halve it without additional trouble). The verifier can now verify f(x, p/2)==u and f(u, p/2)==y, and this is equivalent to verifying f(x, p, m)==y; but still no reduction in work for the verifier. Because the two verification "branches" above share the same exponent p/2, they can be combined and verified together. Choosing a randon factor "r1" (let's say "r1" is a 64-bit number), the verifier computes the new seed x1= x^r1 * u, and verifies that: f(x1, p/2)==y1, where y1=u^r1 * y. So we transformed the verification f(x,p)=y into f(x1,p/2)=y1, halving the work. This "halving" is possible because the author sent to the verifier the value "u" (the middle value between x and y) -- so "u" is part of the proof. But if we have a way to halve the work of the verifier, why stop after only one halving step? let's look at the next halving: the author makes available "u1" the middle point between x1 and y1, u1=f(x1, p/4). r2 is another random 64-bit number chosen by the verifier, the verifier computes: x2=x1^r2 * u1 y2=u1^r2 * y1 and verifies f(x2, p/4)=y2 with only a quarter of the work of the author. ...[/QUOTE] Seems like a good idea. If this technique was used as the verification progress on the server, my understanding is that the bogus PRP result submitted to the server can be denied completely using this check progress. But what about other possible problems, for example, programming bugs? My understanding is that double checking using a different shift can not only reveal bogus results, but possible programming bugs or other tricky problems. The final match means that it's nearly impossible for the result to have problems, so verified. The Gerbicz Error Checking is really a powerful checking technique, but some problems, for example, programming bugs, can still make a bad result "passed" the GEC, so double check is still needed. However, what about implementing this checking technique locally (i.e. on users computer) together with GEC? Is this helpful with excluding possible undetected errors? I mean, can this catch any errors like what double check using different shift does exactly? Or there are still possibility that programming bugs or other problems made a bad result passed this check and GEC simultaneously? (I don't know details about what kind of problems caused bad PRP results in history, and doing this check is somewhat similar to doing just a single GEC if set r1=r2=...=1, so I guess can't) |
PRP-proof
[QUOTE=preda;523438][to be continued][/QUOTE]
I had some progress (finally) with the implementation of PRP-Proof in gpuowl. I would like to add some detail about the implementation, ask for feedback, and discuss how it fits in the grander scheme going forward. Given the exponent E of mersenne candidate 2^E - 1, to work around the problem of E not being a power of 2, we choose a convenient [multiple of] a power of two that is just under E that we call "topK" -- let's take topK as the largest multiple of 1024 that is smaller than E. The proof is going to cover only the PRP iteration range from beginning to topK. The verifier will proceed to first verify the proof up to topK, after which will re-do the remaining number of iterations from topK to E (which is small because the distance from topK to E is less than 1024). Let's call the starting value ("residue") of the PRP test "A", in our case A==3. During the progress of the PRP test, we save the residue (meaning full data residue, not just the 64bits of res64) at the iteration topK. This residue will be part of the proof, let's call it "B" as it represents the final point of PRP iterations covered by the proof. What we want to prove is that a number of topK iterations (squarings) applied to A produces B. (i.e. A^(2^topK) == B ) As a notation let's use prp(C, n) to denote the result of applying n PRP iterations (squarings) to C. Thus we want to prove that prp(A, topK)==B. To facillitate the proof we also save the residue at iteration topK/2, let's call it M (from middle). (M has the properties prp(A, topK/2)==M and prp(M, topK/2)==B) At this point the proof contains {E, M, B}, and the prover can verify the proof in topK/2 iterations by choosing any random value h and verifying that prp(A^h * M, topK/2) == M^h * B. So adding M to the proof halved the verification effort. We recursively apply the same trick a number of times, every addional step halving the verification effort. For example the next step consists in adding to the proof the point M1 that is halfway on the topK/2 iterations between A^h *M and M^h *B, i.e. M1=prp(A^h *M, topK/4). The first middle, M (that we're going to call M0 now) was encountered during the normal progress of original the PRP test (thus, to obtain M0 we simply save that residue). OTOH M1 is not part of the original PRP iterations, nevertheless it can be efficiently computed from two residues (the ones at iterations topK/4 and 3*topK/4) of the original PRP test. We can choose how far to go with this sequence of "middles", M0, M1, ... . I'm going to call the number of middles that are part of the proof the "power" of the proof. When power==1 (the smallest proof), we store in the proof in addition to B only M0, and the verification effort is topK/2 iterations. When power==2, the size of the proof increases by one residue (adding M1), and the verification effort is halved to topK/4 iterations. Let's look next at effort for computing the proof. |
cost of computing the PRP-proof
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 [url]https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic[/url] 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). Next I'll look into the cost of proof verification. |
Proof verification cost
The verifier obtains the proof consisting of:
{E, topK, B, M[0 .. N-1]} (i.e.: the exponent, the upper bound of the proof topK, "B" the final residue at iteration topK, and the vector of middles containing N middles for a proof of power N) The verifier sets: A0 = 3, B0 = B rootHash = hash(E, topK, B) And iteratively computes: h0 = hash(rootH, M0) A1 = A0^h0 * M0, B1 = M0^h0 * B0 h1 = hash(h0, M1) A2 = A1^h1 * M1, B2 = M1^h1 * B1 And continues thus for the full set of middles, obtaining A[N-1] and B[N-1]. At this point the verifier must run topK/(2^N) PRP iterations to verify that: prp(A[N-1], topK/(2^N)) == B[N-1] If this equality holds, the proof is valid, otherwise it isn't. So the bulk of the proof (of power N) verification cost is topK/(2^N) PRP iterations. For power==9 and a 100M exponent this comes to about 200K iterations, 0.2% of the cost of the PRP test. |
Proof file format
We'd like the proof that is generated by one piece of software to be verifiable by a different software -- having multiple software capable of verifying proofs reduces the chances of uniform bugs (affecting both the proof generator and the verifier in the same way) or the possibility of intentional "cheating" by the programmer.
For this we need to agree on a format for the proof file to allow interoperable reading/writing of the proof. We also need to agree on the cryptographic hash that is used, as both sides (proof author and verifier) need to see the same hash values. 1. File format As a starting point proof save/load is already implemented in gpuowl, I'm going to describe the format used. (Of course the goal is to reach agreement on a format that is acceptable to multiple software authors.) 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) All numbers being in decimal except finalHash which is in hexa. Header example: [QUOTE] PROOF 1 2976221 2975744 8 c7b648a462da0b28 [/QUOTE] Right after the header we have a set of residues in binary. A residue is a sequence of 32-bit little-endian words, with the least significant word first. As each residue contains exactly E (E being the exponent) bits, the very last 32-bit word of the residue is only partially filled -- the extra bits (beyond E) are 0. (so the length in bytes of a residue in this format is ((E-1)/32 + 1)*4 ) Right after the header we have one residue representing B (the residue at iteration topK), followed by N residues representing the middles (N being the proof power) in order starting with M0. And that's all file-format wise; I think it's as simple as it gets. I'm looking for feedback from fellow developers whether this format looks acceptable, or what changes are proposed. The finalHash is a value which allows to check both the file for integrity, and the to verify the correct computation of the hashes, to be discussed next. |
[QUOTE=preda;546574]I'm looking for feedback from fellow developers whether this format looks acceptable, or what changes are proposed.[/QUOTE]For certain uses, making res64 very accessible without launching either the originating program, or a special program to produce res64 from the contents, is valuable. I have a situation now where that would be useful for the cudalucas file format.
|
[QUOTE=kriesel;546588]For certain uses, making res64 very accessible without launching either the originating program, or a special program to produce res64 from the contents, is valuable. I have a situation now where that would be useful for the cudalucas file format.[/QUOTE]
Yes that sounds good. (also useful as a check during verification) |
cryptographic hash
We need a cryptographic hash function for choosing the exponents "h" in
prp(A^h * M , k) == M^h * B After a bit of consideration I chose Blake2 (the Blake2b variant) which in addition to being fast, secure is also very simple to implement. Concerning the size of the exponents "h" in the proof, I propose we use 64bits. (The larger the hash-size the more secure is the proof, but also the effort to generate the proof increases proportionally. The proof verification OTOH is not affected much by the hash size). How to compute the hashes: The simplest scheme I came up with is: have the function hash(bytes) which computes a 64-bit Blake2b hash of the bytes. 1. start by computing the "rootHash": rootHash = hash(E, topK, B) which covers pretty much everything except the middles. What it does *not* cover, in addition to the middles, is: the proof power, the finalHash value (a check), the res64 value (redundant). When hashing we need to turn E and topK to bytes -- in my implementation I represent E and topK on 4bytes (32bits) little-endian (which does limit the exponent to 32bits). 2. For every step, update the hash by adding the middle in: h0 = hash(rootHash, M0) A1 = A0^h0 * M0 B1 = M0^h0 * B0 h1 = hash(h0, M1) etc. I realize code may be clearer: [CODE] u64 h = Blake2::hash({E, topK, B}); for (u32 i = 0; i < power; ++i) { Words& M = middles[i]; h = Blake2::hash({h, M}); A = gpu->expMul(A, h, M); B = gpu->expMul(M, h, B); } // check h == finalHash [/CODE] The final value of the hash at the end of the above loop should be compared for equality with the finalHash from the proof file header -- their equality indicates both file integrity and correct implementation of the hash() -- that would be a check that is done before the expensive part of proof verification consisting in doing the large number of PRP iterations. (to prevent paying the verification time just to reject a corrupted file, or just to detect wrong hash application). |
Verification
The proof file contains B, the presumed residue at prp iteration topK.
Verifying the proof proves that B is correct, i.e. that prp(3, topK) == B. After this, the verifier can proceed to run the iterations from topK up to E, which is tiny (less than 1024 iterations). This way the verifier finds out the res64 type1, type4, whether the PRP test outcome is probable-prime or composite, etc. As a convenience, the expected type-1 res64 is included in the proof header as well, and by comparing with it the verifier gains confidence in this final small number (<1024) of iterations (let's call these final iterations on top of B "the tail"). (Of course the verifier can also double-check the tail, although this won't be needed in practice because the whole proof verification will be double-checked anyway). |
Proof and Primenet
The goal of using the PRP-proof with primenet is to eliminate the double-checks. (I estimate right now 10%-20% of the PRP/LL computing power is used for DCs)
The main problem is the size of the proof (e.g. 120MB for a 100M exponent) which makes the internet transfer significant. A secondary question is who contributes the compute-power for proof verification. I'll try to enumerate some possibilities. Setup: User X gets assigned a PRP task. Using software A, he starts the PRP test with proof generation, indicating the desired proof power. The PRP test proceeds and saves a large number of residues (needed for proof generation) as it goes along. Afther the PRP test finishes, the proof is generated (by program A) using this PRP data. After the proof is generated, it is verified by A (to make sure that the generation went without issues), after which all the temporary residues that were needed for proof generation are deleted. At this point X has: - the usual one-line JSON result of the PRP test, indicating (among others): composite/probable-prime and the res64 - the proof, a 120MB file. 1. Local proof verification User X can now do proof verification. For this he uses software B and C, that independently read the proof file and validate it. After validation, B and C sign their results and send them to primenet. (the results being again small JSON files) 2. Primenet-centered verification User X uploads the proof (120MB) to primenet. Primenet queues the proof file for verification. A new task type exists, "proof verification". User Y is assigned the "proof verification" task, he downloads the proof (120MB), verifies it and uploads the result to primenet. At this point primenet has both the initial result from X, and the independent verification from Y. Optionally, primenet can even triple-verify (by user Z) the proof, after which the proof file is deleted from the server to save space or archived. 3. Verifier-node verification User X uploads the proof to a special Verifier server. (the Verifier may run in AWS, and thus have free inbound bandwidth). The Verifier server verifies the proof, twice, using two independent methods. The Verifier signs the results, publishes them to primenet, and removes or archives the proof file. Advantages/disadvantages of these variants to be discussed next. |
I would be more comfortable with a more commonly used hash. Like SHA3. That would make it more accessible. All hashes are fast anyway so saying that blake2 is fast isn't really an advantage IMO.
Also, what happens if/when AWS decides to change the policies about inbound vs outbound traffic? I actually think that a 120MB file is a significant hurdle. And the intermediate local storage of 6GB isn't something to be taken lightly either. |
[QUOTE=retina;546634]I would be more comfortable with a more commonly used hash. Like SHA3. That would make it more accessible. All hashes are fast anyway so saying that blake2 is fast isn't really an advantage IMO.
[/QUOTE] Blake2 is also a well-known and commonly used hash. (Blake, the predecessor of Blake2, was a participant in the NIST hash competition (where SHA-3 was the winner)). It is used in various software products and protocols (wikipedia has details). More notably, it is used as the backbone for the recent Blake3 (the Blake2s variant though). Blake2 has an advantage over SHA-3 in my eyes: it's already implemented in gpuowl. The implementation was easy. It's smaller that SHA-3. I'm open to switching the hash, but I'd need a stronger argement for that. Just to restate, Blake2 is not a niche hash, it's one of the major mainstream crypto hashes. (it may even be more used in products than SHA-3) |
[QUOTE=retina;546634]I actually think that a 120MB file is a significant hurdle. And the intermediate local storage of 6GB isn't something to be taken lightly either.[/QUOTE]
I agree about the size of the proof, and the size of the temporary disk space -- they are both [much] larger than I would have liked. A proof does bring major advantages though, so it's a cost we may be willing to pay (or not). That's why I put up for discussion how to integrate it with primenet. My personal favorite would be the "local verification" which bypasses the upload/download issue, but not without tradeoffs. |
[QUOTE=retina;546634]I would be more comfortable with a more commonly used hash. Like SHA3. That would make it more accessible. All hashes are fast anyway so saying that blake2 is fast isn't really an advantage IMO.[/QUOTE]
What library would you suggest that implements SHA3-256 and is widely available on Linux and Windows? Or a small C source code that implements it that could be easily merged in the project. BTW, reading a bit more, the comparison Blake2 vs. SHA-3 looks roughly like this: both are of the same strength, and Blake2b is 3 times as fast as the fastest SHA-3 in software. |
[QUOTE=preda;546640]What library would you suggest that implements SHA3-256 and is widely available on Linux and Windows? Or a small C source code that implements it that could be easily merged in the project.
BTW, reading a bit more, the comparison Blake2 vs. SHA-3 looks roughly like this: both are of the same strength, and Blake2b is 3 times as fast as the fastest SHA-3 in software.[/QUOTE]I don't have a library suggestion. But since it is [i]the[/i] hash function as chosen by the gods at NIST I have just assumed it would be widely available. Sorry if that isn't so. There are certainly a bunch of websites offering code, but I don't know which is "the best". How much reliance upon speed is required of the hash? I would hope that even at 3X speed it would still be only a minor blip in the overall timing. |
[QUOTE=retina;546642]
How much reliance upon speed is required of the hash? I would hope that even at 3X speed it would still be only a minor blip in the overall timing.[/QUOTE] For one proof (either construction or verification), the amount of data hashed is about the same as the size of the proof (what is hashed is the residues B and all the middles). So let's say 120MB. Even a slow hash would not be a problem, agreed. |
SHA-3 vs. Blake2 hash preference
Anybody else has a preference about the hash function to use?
Blake2 is already implemented in gpuowl For SHA-3 I found source code that I could incorporate here: [url]https://www.fossil-scm.org/home/file?name=src/sha3.c&ci=tip[/url] |
OpenSSL is my go-to library for crypto and it has SHA3, for future reference mbedtls is a nice library of self-contained crypto implementations but it doesn't appear to have SHA3. If speed is a primary concern SHA256 is hardware accelerated on modern x86 and lets be honest SHA256 isn't going to be broken in a meaningful way anytime soon. All three suggestions would do the job fine so IMO stick with what you know.
|
[QUOTE=preda;546638]My personal favorite would be the "local verification" which bypasses the upload/download issue, but not without tradeoffs.[/QUOTE]
The obvious snag is that it would be *possible* for someone to fake the verification. Remember El Dorko. Would he have any qualms about faking results. Chris |
[QUOTE=chris2be8;546661]The obvious snag is that it would be *possible* for someone to fake the verification. Remember El Dorko. Would he have any qualms about faking results.
Chris[/QUOTE] local verification plus El Dorko and his ilk means nonlocal verification also, or PRP DC independently |
[QUOTE=chris2be8;546661]The obvious snag is that it would be *possible* for someone to fake the verification. Remember El Dorko. Would he have any qualms about faking results.
Chris[/QUOTE] Yes that's the remaining issue. What I see helping there is the function that mprime (Prime95) already has, which is to sign the results with a "secret" (a secret bit of code, or a secret key). Working around such a protection, while not impossible, requires significantly more effort. Maybe two independent software would run two independent verification and sign them, and this in conjunction with the initial PRP result would be considered enough to not require a DC by a different user. Please note that this is the case, in practice, right now: if I'm not mistaken, primenet does accept DCs by the same user as valid. This is based, to some degree I think on the assumption that the user is sincere (because it would be trivial to fake such a DC with manual results, just plug in some different offset value). This assumption, while not guaranteed, is valid in the vast majority of users. |
PRP Attack
Let's clarify what a PRP attack, perpertrated by a malevont user or group, consists of.
First let's make clear what the PRP result is: The PRP result is just one bool, which indicates one of: composite, or probable prime. This is the full PRP result. I know we are used to consider the res64 as the PRP result, but we should realize that res64 is a way of validating the PRP result (by running it again (DC) and comparing res64). While res64 is nice, what really matters and what we're really trying to find by doing PRP is the compositeness status of candidates, not the list of res64 of candidates. Let's now consider the PRP Attack. This means that the evil agent wants to make up believe a not-true PRP result. He can do this in two ways: 1. publish a PRP "probable-prime" for a composite candidate 2. publish a PRP "composite" for a prime candidate The attack no. 1 has no teeth, because everybody would jump on the presumed new prime and immediatelly discover the truth. While an annoyance, such an attack is of no serious concern. The attack no. 2 is much worse, because it would cause an actual prime to be stuck forever in the composite state, the project would effectively skip and miss a prime. But how easy is it to pull attack no. 2? well, in order to be able to pull it, the evil agent must first know or discover a new mersenne prime! But if somebody, evil or not, actually did acquire somehow a new mersenne prime, what are the chances he'd decide to use it to misguide the project and keep his new prime hidden.. ? If you look at the attack this way, you see that the "ElDorko" scenario becomes pretty much impossible (i.e. ElDorko would not trigger the attack2). |
[QUOTE=preda;546710]
1. publish a PRP "probable-prime" for a composite candidate 2. publish a PRP "composite" for a prime candidate [/QUOTE] Turns out my previous analysis is.. not correct. The practical attack consists in the agent systematically publishing "composite" for all candidates. To do this the agent does not need to know a prime, but nevertheless has a chance of hiding a prime, thus the attack is worrisome. In other words, somebody can hide a prime without knowing which prime he's hiding. |
Proof archival
If we wanted to keep the PRP proofs around (archiving them) -- this way anybody could easily [re-]verify any proof at any time in the future.
The disk space required would be on the order of 2TB for every 1M exponent range (because: 18K not-factored candidates per 1M range x 120MB). Assuming 1K proofs produced per day, the inbound data to the archiver would be 120GB/day, or 4TB per month. One additional HDD per month. If at any point a candidate is factored, its proof is not needed anymore and can be deleted. Once we have an agreed-upon and public, documented proof format maybe we could ask Internet Archive if they'd like to archive those. |
3. Malicious insertion of false data. Wrong res64 for mersennes of prime exponent; Falsified NF where there might be a readily found factor. Both forms will delay discovery of primes. The first by putting a possible prime into double-check delay which is now multiple years; the second by causing unnecessary primality tests.
|
[QUOTE=kriesel;546719]3. Malicious insertion of false data. Wrong res64 for mersennes of prime exponent; Falsified NF where there might be a readily found factor. Both forms will delay discovery of primes. The first by putting a possible prime into double-check delay which is now multiple years; the second by causing unnecessary primality tests.[/QUOTE]
Let's focus the discussion on PRP attacks, excluding TF attacks or others. |
[QUOTE=preda;546633]The goal of using the PRP-proof with primenet is to eliminate the double-checks.[/QUOTE]
The only way to eliminate double checks is to have a test that says either "yes, this is prime", or in case it is composite, to produce a factor. The factors are the only thingies which are extremely easy to check (i.e. zero work compared with repeating a full test) and extremely impossible to fake. Anything else, can either be faked (well... almost...more or less) or could be reconstructed without doing the work, and you all forget that this is not only about hardware errors, algorithm bugs, cosmic rays, whatever, but also about ill intentions, sick mind of genius kids, etc. Even with a stone-hard proof of work, we still need to do DC, regardless that you call it LL or make it GC-proof and call it PRP, or make it VDF-proof and call it WGDQP, you won't get George's $10k for such a tricks :razz: and we will still have to DC it. Of course, this is not a thesis against trying to vadafuck the LL/PRP/QPWGD whatever (you have to pay royalties for the term I just coined! :razz:), you can try, and anything that raise the safety without a too large speed penalty will be welcome. But we still need to DC, at least for now. What we would need would be a proof of [U]correct[/U] [U]work[/U] (please note the separate underlined words, they are both stressed, and separate), and be easily to verify with close-to-zero computing effort, so we wouldn't need to run another LL to verify that the verification code is good, and that should not be easy to fake or to produce without doing the effective work. And we don't have this yet. |
[QUOTE=LaurV;546794]But we still need to DC, at least for now. What we would need would be a proof of [U]correct[/U] [U]work[/U] (please note the separate underlined words, they are both stressed, and separate), and be easily to verify with close-to-zero computing effort, so we wouldn't need to run another LL to verify that the verification code is good, and that should not be easy to fake or to produce without doing the effective work.
And we don't have this yet.[/QUOTE] Could you explain what you mean by the need for proof of correct work that you emphasized? The PRP with GEC result is correct, but we don't know whether the user is honest. The PRP-Proof that I describe is a proof of the result of a PRP test (independent of user). What do you see different in your request for a "proof of correct, work"? The PRP-Proof can verify a PRP test with a cost on the order of 0.2% of the PRP test. |
[QUOTE=LaurV;546794]The only way to eliminate double checks is to have a test that says either "yes, this is prime", or in case it is composite, to produce a factor. The factors are the only thingies which are extremely easy to check (i.e. zero work compared with repeating a full test) and extremely impossible to fake.
Anything else, can either be faked (well... almost...more or less) or could be reconstructed without doing the work, and you all forget that this is not only about hardware errors, algorithm bugs, cosmic rays, whatever, but also about ill intentions, sick mind of genius kids, etc. Even with a stone-hard proof of work, we still need to do DC, regardless that you call it LL or make it GC-proof and call it PRP, or make it VDF-proof and call it WGDQP, you won't get George's $10k for such a tricks :razz: and we will still have to DC it. Of course, this is not a thesis against trying to vadafuck the LL/PRP/QPWGD whatever (you have to pay royalties for the term I just coined! :razz:), you can try, and anything that raise the safety without a too large speed penalty will be welcome. But we still need to DC, at least for now. What we would need would be a proof of [U]correct[/U] [U]work[/U] (please note the separate underlined words, they are both stressed, and separate), and be easily to verify with close-to-zero computing effort, so we wouldn't need to run another LL to verify that the verification code is good, and that should not be easy to fake or to produce without doing the effective work. And we don't have this yet.[/QUOTE] I don't understand exact what is your objection to PRP-Proof. Let's compare what we have now: 1. User A does PRP test 2. User B does DC by running the same PRP test once more. Cost of verified result: 2x PRP test. Compare with this imaginary, but entirely possible, scenario: 1. User A does PRP test + PRP-Proof (cost: 1 Test + 0.2% Proof-construction overhead) 2. User B obtains the proof from A and verifies it. Cost: 0.2% of 1PRP test. This is a very solid DC, just as strong, with a cost of 1.04 x PRP test. The difficulty in scenario 2 is in coordinating the transfer of the proof. I agree we don't have solution 2 yet. But is the solution that we have now, of running the work twice, so great that we shouldn't strive to improve upon it? |
[QUOTE=preda;546800]I don't understand exact what is your objection to PRP-Proof. Let's compare what we have now:
1. User A does PRP test 2. User B does DC by running the same PRP test once more. Cost of verified result: 2x PRP test. [/QUOTE] In fact, in truthfulness, that's not exactly what we have now. Because if right now I upload a manual result, faking a different offset, twice, it will be wrongly marked DC'ed! By one single user, that self-double-checked his own result, trivial to fake. And yet DCed. Now that's not exactly the paragon of an absolute infaillible DC. In reality we do have the implied notion of "trusted user" (nothing wrong with that), so let's not set the bar absolutely high when the solution that we use in practice is.. pragmatic. |
[QUOTE=LaurV;546794]The only way to eliminate double checks is to have a test that says either "yes, this is prime", or in case it is composite, to produce a factor. The factors are the only thingies which are extremely easy to check (i.e. zero work compared with repeating a full test) and extremely impossible to fake.
[/QUOTE] Yes a factor would be nice, but it's not readily available for every composite candidate, you know that. Asking for a factor as proof of compositeness is not a solution, you know. [QUOTE] Anything else, can either be faked (well... almost...more or less) or could be reconstructed without doing the work, [/QUOTE] Yet, the point of the PRP-proof is that it cannot be faked, and cannot be constructed without doing the work. [QUOTE] and you all forget that this is not only about hardware errors, algorithm bugs, cosmic rays, whatever, but also about ill intentions, sick mind of genius kids, etc. Even with a stone-hard proof of work, we still need to do DC, regardless that you call it LL or make it GC-proof and call it PRP, or make it VDF-proof and call it WGDQP, you won't get George's $10k for such a tricks :razz: and we will still have to DC it. [/QUOTE] Fine, if your point is to call it DC, no problem there. My goal then is to make available a new DC that costs 0.2% of one PRP test vs. the current DC that costs 100% of one PRP test. Are you saying that it should be impossible for one user to DC his own work? |
You got me wrong, I am not "against" improving the current situation (which indeed, kinda sucks! and this is known for long time, and it was discussed repeatedly on the forum!). My objection is ONLY to the phrase I quoted. I highly salute your initiative and effort, and I am convinced you CAN improve the things (as explained below). I just want to stress out that you CANNOT eliminate DC with things like GC, or VDF.
A proof of work is easy to implement, but that only shows that you did the work, not that the work is correct. If an unlucky bit flips, you are screwed, and yet the proof of work is valid. On the other hand, any residue-like information you got after any kind of test you do, which can be verified in x% of the time of a test as being correct, can also be [U]produced[/U] in about the same x% of the time of a test, without doing the test, just following the same steps that the "verifier" would do. If you can do that, then you just discovered a new testing method that only takes x% of the LL/PRP tests, and well, who will need LL/PRP anymore? GC, by the way, is just a probabilistic stuff, and accepting it without a DC is the same as accepting a probable prime as being prime without a rigorous proof. Actually, a bit worse, probabilistic. So, yes, PLEASE make the LL/PRP/whatever tests, more error proof, more cheat proof, more whatever proof, we will help where we can, like we can help with testing, even give you access to our toys, or even help with math, but don't expect to eliminate DCs until your "tests" can also produce a factor. Maybe my understanding of all these things is plain wrong... but I can't see any other way to eliminate the DCs. |
[QUOTE=LaurV;546809]
A proof of work is easy to implement, but that only shows that you did the work, not that the work is correct. If an unlucky bit flips, you are screwed, and yet the proof of work is valid. On the other hand, any residue-like information you got after any kind of test you do, which can be verified in x% of the time of a test as being correct, can also be [U]produced[/U] in about the same x% of the time of a test, without doing the test, just following the same steps that the "verifier" would do. If you can do that, then you just discovered a new testing method that only takes x% of the LL/PRP tests, and well, who will need LL/PRP anymore?[/QUOTE] The PRP-Proof discussed here is not a proof of work, it is a proof of the corectness of the PRP residue (at iteration topK). While it can be verified by anybody fast, in can not be generated faster than doing the PRP test. Your assertion above that the verifier could produce the proof in the same amount of time as the verification by "following the same steps" simply does not hold. It is similar in a way to finding a factor (hard) and verifying the factor (easy). Or in general, to what is called one-way functions where there is difficutly asymetry between the two directions. |
SHA-3 hash
By popular demand (@retina) I changed the hash in the "reference implementation" in gpuowl to SHA-3.
The hash is run with an output of 256bits. This full output (256bits) is chained (when generating the sequence of hashes such as h1=hash(h0, M1) etc) but when computing the exponents a truncated 64-bit value of the hash is used (please see the gpuowl source code if interested in details). I hope this raises no concerns. |
Security of the proof
The PRP-Proof is based on Pietrzak's VDF article. The math in Pietrzak's article is solid, but I think our setup departs from Pietrzak's assumptions in one aspect. I'd like to explicitly disclose this here before it's "exposed as a fatal flaw of the proof".
In my understanding (math people please correct me), the proof becomes weak (can be faked) if the author knows a factorization of the modulo (the mersenne candidate in our case). But the case we want to be protected against through the proof mecanism is the situation of a mersenne prime acquiring a false proof showing it being composite. This is not possible because, for a prime, the proof cannot be faked (because no factorization is available). [maybe] the theoretical possibility remains that an agent may produce a fake proof of a composite candidate being prime based on a factor known to the agent. While this possibility is slightly annoying, it's not dangerous because such a case would be exposed immediatelly because of the interest in the new presumed prime. |
[QUOTE=preda;546862]By popular demand (@retina) ...[/QUOTE]OMG I'm popular?
:tu:[QUOTE=preda;546863][maybe] the theoretical possibility remains that an agent may produce a fake proof of a composite candidate being prime based on a factor known to the agent. While this possibility is slightly annoying, it's not dangerous because such a case would be exposed immediatelly because of the interest in the new presumed prime.[/QUOTE]If you know a factor that no one has then ... People are weird (yes they are) and sooner of later someone will try it. For some brief fame or something. |
[QUOTE=retina;546865]If you know a factor that no one has then ...
People are weird (yes they are) and sooner of later someone will try it. For some brief fame or something.[/QUOTE] Yes, but it's not a problem. First, it may be difficult to build such a proof even knowing a factorization of the candidate (it may well be more difficult than just running the PRP the honest way). I say if somebody does do it, they deserve kudos for the non-trivial analysis effort and for showing that it can be done. And for the project (GIMPS) it's not a big deal to have somebody claim a prime that wasn't. |
[QUOTE=preda;546870]Yes, but it's not a problem. First, it may be difficult to build such a proof even knowing a factorization of the candidate (it may well be more difficult than just running the PRP the honest way). I say if somebody does do it, they deserve kudos for the non-trivial analysis effort and for showing that it can be done. And for the project (GIMPS) it's not a big deal to have somebody claim a prime that wasn't.[/QUOTE]
With a knowledge of a new factor (after the published proof) actually the verifier will have an advantage to catch cheaters even in a faster way: just check ((g^(2^L) mod N) mod q), where the g^(2^L) mod N is a single residue from the proof. If it isn't g^(2^L) mod q then gotcha, the proof is broken. And for this you need only one full residue and the cheater has only 1/q chance to fake it whatever he does. |
[QUOTE=preda;546863]
In my understanding (math people please correct me), the proof becomes weak (can be faked) if the author knows a factorization of the modulo (the mersenne candidate in our case). [/QUOTE] Would that make it possible for someone who has found a factor to report a bogus proof it's composite, thus appearing to have done a lot more work than they really did? It's not a big issue because the number would really be composite but might be used to move up the work done table. (I've obviously spent too much time looking for ways to break things when I was working on computer security.) Chris |
PRP-Proof file spec moved
The proof file spec is now maintained here:
[url]https://github.com/preda/gpuowl/wiki/PRProof-File-Spec[/url] Feel free to provide feedback, ask for clarifications, etc. |
I still didn't get how this works.
1. I am reserving Mx for PRP. 2. I generate x random residues in a file, without doing any work, just garbage data. 3. I apply your calculus on my garbage data and generate the verification file. 4. I send it to PrimeNet and get the LL/PRP credit in just 5 minutes (including the "trusted" particle attached to it, because it is verified, you know?). Which of this step would be impossible, and why? Of course the first is not necessary, I don't want to create suspicion by reporting results at a very short time after reservation, so I will just report results, without reservation. Of course, I understand the part that there is some relation between some residues in that list, and they are not totally random, but this is where we are stuck. Say the residue at iteration h has some relation with residue at iteration k. Then either there is a small difference between h and k (to allow the verification process to be fast, without a lot of squarings) and in this case I can also produce this relation fast, starting with a random h (and squaring, or whatever), or either there is a large distance between h and k, to be difficult for me to fake it, but then in such case you have to spend a huge amount of time to verify it (practically repeating a part of the initial test, and yet, being unsure the iteration h was true, except when it was the first). What we are currently doing today, h is 1 and k is x-1, and the verification process is called "Double Checking", except we just use residues directly, and not hashes of them. |
[QUOTE=preda;546996]Feel free to provide feedback, ask for clarifications, etc.[/QUOTE]
What about having an EOF (0x1A) after the \n like in the PNG header? That way [C]cat[/C] etc. will exit after printing the header. |
Weird, it seems like current [C]cat[/C] behaves differently. On Windows, it works fine with [C]type[/C].
Correction, Windows uses 0x1A, Unix uses 0x04. But it still does not behave like I expected. Forget my addition; [C]head -n1 filename[/C] does the job. |
[INDENT]Assuming power 9 and ~95M exponent, the interim residues are spaced ~185547 iterations apart. A random number generator at the server could be used to choose which submissions to spot verify at the server in this additional way, perhaps one in 4K of them, and randomly select between which successive submitted interim residues. A user found to be submitting nonmatching residues could be subjected to an increasing rate of verifications, or other measures. The server would need to receive a LOT of data to do this.
[/INDENT] |
Challenge-response type of proof using only 2*p bits of memory sent to the server (that would send it to the verifier), and with ~1/1024 chance to fake it by a clever cheater (assuming a single verification, but you can repeat it to lower the chance). If this is working then the prover could also do part of the computation needed for the verification and the independent prover would need only 2 residues to check the whole computation.
First request for the full residue: rn=3^mp mod mp. Then let d a random number in [L,2*L], the server sends back only d, and ask for a (2^d-1)-th root for A=(3*res)^(2^(d-p%d))/3. Let rn=lift(Mod(3,mp)^mp) then you can get one(!) (2^d-1)-th root of A, because A==3^(2^e-1) mod mp Here e is divisible by d, so one root will be root=3^((2^e-1)/(2^d-1)) mod mp that is root=3^(2^0)*3^(2^d)*...*3^(2^(e-d)) mod mp. If we have a stored residue list, spaced at L (this L is different from my notation's error check), say if we want 1024 residues then L=p\1023 is a good choice (only the last is past of p). Then the problem is how to get the "root" faster than the trivial O(p) mulmod method? The solution is not that hard: for each residue=3^(2^(i*L)) mod mp we can get how many squarings will be needed, and with this we can get the root with O(d+p/d) multiplication. This is similar to the idea used in calculation of (n!) with iterated squarings and multiplication by a "small" number. Example: [CODE] ff(p,g,L,maxe)={gettime();ret=[];res=Mod(g,2^p-1);for(i=0,maxe,if(i%L==0,ret=concat(ret,lift(res)));res=res^2); print("Prp took ",gettime/1000.0," seconds");return(ret)} getroot(p,g,L,d,v)={mp=2^p-1;len=length(v);r=p%d;S=vector(d+1,i,Mod(1,mp)); forstep(i=0,p,d,S[d-(i%L)]*=v[i\L+1]); res=Mod(1,mp);for(i=1,d,res=res^2*S[i]);return(res)} validate_proof(p,g,L,v)={gettime();mp=2^p-1;d=L+random(L);root=getroot(p,g,L,d,v);expo=d-(p%d);maxe=L*(p\L+1); rn=lift(1/g*Mod(v[length(v)-1],mp)^(2^(p-maxe+L))); b=(root^(2^d-1)*g==Mod(g*rn,mp)^(2^expo)); if(b==1,print("Valid proof"),print("Broken proof"));print("Validation took ",gettime()/1000.0," seconds")} p=60013; sh=8; L=p\(-1+2^sh); g=3; mp=2^p-1; maxe=L*(p\L+1); v=ff(p,g,L,maxe); validate_proof(p,g,L,v) Prp took 14.36600000 seconds ? ? Valid proof Validation took 0.2510000000 seconds [/CODE] note: the verifier needs only root and rn for the verification, not the whole v residue array. How to fake it? It is pretty hard if you'd use only random residue for rn, but with clever cheating it is possible to cheat with 1/d probability: if you'd compute 3^(h-1) mod mp with small "h" and you hit (2^d-1)|(2^p-h) then you can cheat, it seems that you've very low chance to get it, but not if you set h=2^m, in this case you have 1/d chance to fake the proof. Otherwise in general case you'd need to extract a (2^d-1)-th root, what is hard. |
[QUOTE=LaurV;547018]I still didn't get how this works.
1. I am reserving Mx for PRP. 2. I generate x random residues in a file, without doing any work, just garbage data. 3. I apply your calculus on my garbage data and generate the verification file. 4. I send it to PrimeNet and get the LL/PRP credit in just 5 minutes (including the "trusted" particle attached to it, because it is verified, you know?). Which of this step would be impossible, and why? Of course the first is not necessary, I don't want to create suspicion by reporting results at a very short time after reservation, so I will just report results, without reservation. Of course, I understand the part that there is some relation between some residues in that list, and they are not totally random, but this is where we are stuck. Say the residue at iteration h has some relation with residue at iteration k. Then either there is a small difference between h and k (to allow the verification process to be fast, without a lot of squarings) and in this case I can also produce this relation fast, starting with a random h (and squaring, or whatever), or either there is a large distance between h and k, to be difficult for me to fake it, but then in such case you have to spend a huge amount of time to verify it (practically repeating a part of the initial test, and yet, being unsure the iteration h was true, except when it was the first). What we are currently doing today, h is 1 and k is x-1, and the verification process is called "Double Checking", except we just use residues directly, and not hashes of them.[/QUOTE] Did you read Pietrzak's paper about VDF? [url]https://eprint.iacr.org/2018/627.pdf[/url] The key element from that paper is the logarithmic-effort verification enabled by this schema: if prp(A, k)==M and prp(M, k)==B then I suppose you agree that prp(A, 2*k)==B, ok? Now let's assume that I want to verify that prp(A,2*k)==B. The naive way requires me to do 2*k PRP iterations. But here comes the trick, this check can in fact be done in half that work, in k interations, like this: instead of verifying prp(A, k)==M *and* prp(M,k)==B (each requiring k iterations, thus 2*k iterations in total), I'm going to combine the two and verify them simultaneuosly in just k iterations. Choose a random h, and verify that: prp(A^h * M, k)==M^h * B that's the core of the trick. Let me give an example, which applies one halving step. Let's say I do a PRP test (E iterations), and I give you my final residue for verification. The best you can do is to repeat the E iterations, and check whether you get the same final residue. That was a DC done in E iterations, 100% of 1xPRP test. Now let's try something different: assuming E is even, in addition to my final residue, I'm also going to give you my "middle" residue M at iteration E/2. This simple bit of information allows you, magically, to DC my work in only E/2 iterations, 50% of 1xPRP test, like this: 1. you choose a random 64-bit value h. 2. compute A:=3^h * M, B:=M^h * "my final residue" 3. verify that E/2 iterations starting from A produces B. You see? -- you only needed to do E/2 iterations to double check my work! that's one halving. Now, is this clear up to here, do you agree it works? Do you see some way for me to "cheat"? by using garbage in strategic places, whatever, how can I cheat your verification? it's solid, there's no way for me to cheat. So, look what happened -- you just solidly double-checked my result, using only 50% of one full PRP test. Impossible, you say? |
[QUOTE=kriesel;547025][INDENT]Assuming power 9 and ~95M exponent, the interim residues are spaced ~185547 iterations apart. A random number generator at the server could be used to choose which submissions to spot verify at the server in this additional way, perhaps one in 4K of them, and randomly select between which successive submitted interim residues. A user found to be submitting nonmatching residues could be subjected to an increasing rate of verifications, or other measures. The server would need to receive a LOT of data to do this.
[/INDENT][/QUOTE] Ken, that's not at all how the verification scheme works. There's no need to send all those residues to the verifier. Are you proposing a different schema, or is this a misunderstanding of the proof I'm proposing? |
[QUOTE=R. Gerbicz;547029]Challenge-response type of proof using only 2*p bits of memory sent to the server (that would send it to the verifier), and with ~1/1024 chance to fake it by a clever cheater (assuming a single verification, but you can repeat it to lower the chance). If this is working then the prover could also do part of the computation needed for the verification and the independent prover would need only 2 residues to check the whole computation.[/QUOTE]
Robert, is your proposal similar to Wesolowski's proof [url]https://eprint.iacr.org/2018/623.pdf[/url] ? |
[QUOTE=preda;547048]Robert, is your proposal similar to Wesolowski's proof [url]https://eprint.iacr.org/2018/623.pdf[/url] ?[/QUOTE]
They consider more r-th roots, not only (in our case) the (2^d-1)-th root. But regarding only this form allows us to compute the (2^d-1)-th root with just d+p/d mulmods if we have stored p/L residues while we computed the g^(2^p-1). Their time complexity was p/log(p) mulmods. Notice how nicely this is matching with the other type of verification (what you've implemented) in speed: if you fix L~O(sqrt(p)) then the verfication takes O(sqrt(p)) mulmods with a storage of sqrt(p) residues. And the cheater has no chance because: lcm(2^d-1: L<=d<2*L)~2^(c*L^2), choosing the other type of cheating is even worse because you can't use three d that are relative prime. |
[QUOTE=preda;547031]
Now let's try something different: assuming E is even, in addition to my final residue, I'm also going to give you my "middle" residue M at iteration E/2. This simple bit of information allows you, magically, to DC my work in only E/2 iterations, 50% of 1xPRP test, like this: 1. you choose a random 64-bit value h. 2. compute A:=3^h * M, B:=M^h * "my final residue" 3. verify that E/2 iterations starting from A produces B. You see? -- you only needed to do E/2 iterations to double check my work! that's one halving. Now, is this clear up to here, do you agree it works? Do you see some way for me to "cheat"? by using garbage in strategic places, whatever, how can I cheat your verification? it's solid, there's no way for me to cheat. So, look what happened -- you just solidly double-checked my result, using only 50% of one full PRP test. Impossible, you say?[/QUOTE] Yes, impossible. I just pick a random M and do E/2 iterations from it, to get whatever final F, and send you M and F. I don't give a dime about the first half iterations, as long as your verification test doesn't give a dime about them either. Your test still pass, and I got my LL credit with only half of the work. Note that you don't need all the 3^whatever trick, you could just do E/2 "normal" iterations, possible with some shift (mod 2^p-1) to avoid the FFT operating with the same input data. What your verification proves is the fact that I did some work of E/2 iterations starting from an arbitrary M and got F, and that such calculation is correct. But nothing about M or F having anything to do with testing mersenne numbers for (pr)primality. |
[QUOTE=LaurV;547069]Yes, impossible. I just pick a random M and do E/2 iterations from it, to get whatever final F, and send you M and F. I don't give a dime about the first half iterations, as long as your verification test doesn't give a dime about them either. Your test still pass, and I got my LL credit with only half of the work. Note that you don't need all the 3^whatever trick, you could just do E/2 "normal" iterations, possible with some shift (mod 2^p-1) to avoid the FFT operating with the same input data. What your verification proves is the fact that I did some work of E/2 iterations starting from an arbitrary M and got F, and that such calculation is correct. [/QUOTE]
Ok, a very small test, but this is better than the usual tests with multi million digits. So fake me: Fix the base=A=3, we are claiming that M=3^(2^(top/2)) mod N B=3^(2^top) mod N for N=997 and top=500 (note: top should be even). Show me two residues M, B to fake the proof (obviously not that 3^(2^250) mod N and 3^(2^500) mod N pair). And for a quite bounded interval for h in the original proof (but using only the M,B residues) I'll tell you how many tests you have failed. To get a candidate pair you can use more than top squarings. |
[QUOTE=LaurV;547069]Yes, impossible. I just pick a random M and do E/2 iterations from it, to get whatever final F, and send you M and F. I don't give a dime about the first half iterations, as long as your verification test doesn't give a dime about them either. Your test still pass, and I got my LL credit with only half of the work. Note that you don't need all the 3^whatever trick, you could just do E/2 "normal" iterations, possible with some shift (mod 2^p-1) to avoid the FFT operating with the same input data. What your verification proves is the fact that I did some work of E/2 iterations starting from an arbitrary M and got F, and that such calculation is correct. But nothing about M or F having anything to do with testing mersenne numbers for (pr)primality.[/QUOTE]
If you do that, my verification will catch your cheating right away. The verification checks both halves, covers all the iterations, and as such does detect your cheat attempt easily. Let me try to explain why your cheat attempt is detected: 3 is the base (starting point) of the PRP test. prp(3^h * M, k) == prp(3^h, k) * prp(M, k) == prp(3, k)^h * B (because prp(M, k) == B (B is "F" in your naming)) The verification compares for equality: prp(3, k)^h * B == M^h * B, which would pass if prp(3, k) == M. But as you chose M "at random" the verification above fails with high probability, and your cheat it detected. Does this make sense? I'm sure you could have worked through the above algebra without the hand-holding. |
[QUOTE=R. Gerbicz;547088]Ok, a very small test, but this is better than the usual tests with multi million digits.
So fake me: Fix the base=A=3, we are claiming that M=3^(2^(top/2)) mod N B=3^(2^top) mod N for N=997 and top=500 (note: top should be even). Show me two residues M, B to fake the proof (obviously not that 3^(2^250) mod N and 3^(2^500) mod N pair). And for a quite bounded interval for h in the original proof (but using only the M,B residues) I'll tell you how many tests you have failed. To get a candidate pair you can use more than top squarings.[/QUOTE] This doesn't make sense. 997 is prime. Is my "reserved task" to test if 997 is prime? or to test if 2^997-1 is prime? In any case, I can pick ANY B=M, run 250 iterations of B=B^2 (mod 997), give you M and B, and ALL such pairs will pass your test, and I got out with "testing" M997 by running only 250 iterations, instead of 995 or 996 (as the normal PRP would be). This is because you have no way to know if M is indeed the residue after 500 iterations, or fake value. Examples of M and B that pass the test, as you described it: 249 and 804 - these are 3^(2^250) (mod 997) and 3^(2^500) (mod 997), of course, provided just for fun; what follows are random values, generated like described, pick a random M=B and run for(i=1,250,B=B^2), print M and B. Pick your favorite. [CODE] gp > Mod(3,997)^(2^250) %1 = Mod(249, 997) gp > Mod(3,997)^(2^500) %2 = Mod(804, 997) gp > M=Mod(249,997); B=M; for(i=1,250,B=B^2); [lift(M),lift(B)] time = 16 ms. %3 = [249, 804] gp > for(k=2, 996/2, M=Mod(k,997); B=M; for(i=1,250,B=B^2); print([lift(M),lift(B)])) [2, 731] [3, 249] [4, 966] [5, 718] [6, 565] [7, 672] [8, 270] [9, 187] [10, 436] [11, 482] [12, 257] [13, 404] [14, 708] [15, 319] [16, 961] [17, 522] [18, 108] [19, 767] [20, 673] [21, 829] [22, 401] [23, 408] [24, 431] [25, 75] [26, 212] [27, 701] [28, 105] [29, 228] [30, 888] [31, 565] [32, 603] [33, 378] [34, 728] [35, 945] [36, 185] [37, 75] [38, 363] [39, 896] [40, 442] [41, 799] [42, 820] [43, 983] [44, 13] [45, 668] [46, 145] [47, 306] [48, 9] [49, 940] [50, 987] [51, 368] [52, 437] [53, 683] [54, 970] [55, 117] [56, 983] [57, 556] [58, 169] [59, 618] [60, 81] [61, 337] [62, 257] [63, 42] [64, 119] [65, 942] [66, 149] [67, 229] [68, 767] [69, 895] [70, 871] [71, 765] [72, 640] [73, 807] [74, 987] [75, 729] [76, 151] [77, 876] [78, 944] [79, 861] [80, 74] [81, 74] [82, 824] [83, 772] [84, 223] [85, 921] [86, 733] [87, 940] [88, 530] [89, 356] [90, 775] [91, 304] [92, 313] [93, 108] [94, 358] [95, 362] [96, 597] [97, 914] [98, 207] [99, 404] [100, 666] [101, 504] [102, 815] [103, 975] [104, 407] [105, 13] [106, 773] [107, 681] [108, 203] [109, 421] [110, 782] [111, 729] [112, 733] [113, 798] [114, 657] [115, 823] [116, 908] [117, 773] [118, 117] [119, 837] [120, 388] [121, 23] [122, 88] [123, 548] [124, 431] [125, 12] [126, 792] [127, 73] [128, 250] [129, 502] [130, 672] [131, 282] [132, 246] [133, 972] [134, 900] [135, 830] [136, 363] [137, 548] [138, 213] [139, 376] [140, 615] [141, 422] [142, 895] [143, 313] [144, 247] [145, 196] [146, 690] [147, 762] [148, 666] [149, 337] [150, 501] [151, 147] [152, 711] [153, 905] [154, 282] [155, 888] [156, 140] [157, 519] [158, 284] [159, 577] [160, 256] [161, 1] [162, 256] [163, 79] [164, 156] [165, 220] [166, 30] [167, 603] [168, 502] [169, 705] [170, 276] [171, 858] [172, 434] [173, 42] [174, 207] [175, 550] [176, 594] [177, 344] [178, 19] [179, 358] [180, 229] [181, 710] [182, 890] [183, 165] [184, 490] [185, 12] [186, 185] [187, 360] [188, 484] [189, 488] [190, 417] [191, 140] [192, 718] [193, 30] [194, 144] [195, 263] [196, 770] [197, 360] [198, 212] [199, 830] [200, 310] [201, 192] [202, 531] [203, 675] [204, 556] [205, 407] [206, 867] [207, 524] [208, 411] [209, 804] [210, 530] [211, 807] [212, 761] [213, 58] [214, 308] [215, 915] [216, 837] [217, 820] [218, 675] [219, 546] [220, 361] [221, 521] [222, 501] [223, 482] [224, 434] [225, 67] [226, 93] [227, 85] [228, 710] [229, 673] [230, 422] [231, 778] [232, 743] [233, 645] [234, 761] [235, 368] [236, 782] [237, 34] [238, 686] [239, 328] [240, 480] [241, 824] [242, 861] [243, 480] [244, 520] [245, 948] [246, 791] [247, 798] [248, 9] [249, 804] [250, 796] [251, 911] [252, 692] [253, 247] [254, 522] [255, 19] [256, 299] [257, 625] [258, 66] [259, 550] [260, 708] [261, 762] [262, 760] [263, 350] [264, 366] [265, 867] [266, 668] [267, 908] [268, 877] [269, 326] [270, 554] [271, 34] [272, 151] [273, 921] [274, 791] [275, 258] [276, 171] [277, 877] [278, 681] [279, 970] [280, 915] [281, 866] [282, 409] [283, 327] [284, 213] [285, 408] [286, 490] [287, 542] [288, 100] [289, 303] [290, 705] [291, 270] [292, 905] [293, 529] [294, 696] [295, 59] [296, 310] [297, 896] [298, 88] [299, 327] [300, 332] [301, 562] [302, 778] [303, 871] [304, 304] [305, 692] [306, 544] [307, 393] [308, 760] [309, 504] [310, 81] [311, 521] [312, 646] [313, 321] [314, 529] [315, 246] [316, 228] [317, 417] [318, 56] [319, 226] [320, 697] [321, 79] [322, 731] [323, 577] [324, 697] [325, 390] [326, 920] [327, 144] [328, 378] [329, 250] [330, 303] [331, 124] [332, 993] [333, 67] [334, 119] [335, 914] [336, 66] [337, 159] [338, 903] [339, 299] [340, 362] [341, 149] [342, 85] [343, 579] [344, 208] [345, 542] [346, 792] [347, 945] [348, 770] [349, 40] [350, 259] [351, 56] [352, 519] [353, 966] [354, 220] [355, 920] [356, 928] [357, 40] [358, 484] [359, 701] [360, 900] [361, 59] [362, 570] [363, 742] [364, 546] [365, 169] [366, 975] [367, 366] [368, 267] [369, 860] [370, 796] [371, 356] [372, 640] [373, 645] [374, 949] [375, 994] [376, 866] [377, 388] [378, 799] [379, 531] [380, 742] [381, 231] [382, 646] [383, 147] [384, 436] [385, 858] [386, 993] [387, 373] [388, 579] [389, 890] [390, 829] [391, 615] [392, 562] [393, 428] [394, 949] [395, 58] [396, 437] [397, 421] [398, 554] [399, 754] [400, 291] [401, 520] [402, 772] [403, 944] [404, 328] [405, 291] [406, 907] [407, 258] [408, 657] [409, 306] [410, 411] [411, 860] [412, 682] [413, 544] [414, 196] [415, 961] [416, 344] [417, 903] [418, 491] [419, 159] [420, 594] [421, 319] [422, 690] [423, 393] [424, 962] [425, 267] [426, 524] [427, 145] [428, 823] [429, 171] [430, 875] [431, 754] [432, 686] [433, 876] [434, 223] [435, 948] [436, 907] [437, 875] [438, 326] [439, 203] [440, 683] [441, 308] [442, 994] [443, 16] [444, 332] [445, 376] [446, 401] [447, 165] [448, 208] [449, 958] [450, 124] [451, 276] [452, 187] [453, 711] [454, 321] [455, 926] [456, 570] [457, 192] [458, 442] [459, 23] [460, 409] [461, 16] [462, 428] [463, 743] [464, 765] [465, 775] [466, 911] [467, 682] [468, 962] [469, 350] [470, 815] [471, 618] [472, 361] [473, 231] [474, 926] [475, 696] [476, 972] [477, 105] [478, 488] [479, 259] [480, 933] [481, 390] [482, 156] [483, 249] [484, 284] [485, 226] [486, 933] [487, 928] [488, 263] [489, 728] [490, 73] [491, 100] [492, 958] [493, 373] [494, 93] [495, 942] [496, 597] [497, 625] [498, 491] time = 37 ms. gp >[/CODE] |
[QUOTE=LaurV;547124]This doesn't make sense. 997 is prime. Is my "reserved task" to test if 997 is prime? or to test if 2^997-1 is prime? [/QUOTE]
There is nothing special in 997, for composite/prime the proof check should run in the same way. [QUOTE=LaurV;547124] Examples of M and B that pass the test, as you described it: 249 and 804 - these are 3^(2^250) (mod 997) and 3^(2^500) (mod 997), of course, provided just for fun; what follows are random values, generated like described, pick a random M=B and run for(i=1,250,B=B^2), print M and B. Pick your favorite. [/QUOTE] Asked one. But let's take not the first because you could complain why. Picked the (5,718) [CODE] check_proof(M,B,N,top,A=3,num_iteration=20,maxh=1000)={ for(i=1,num_iteration,h=1+random(maxh); res=Mod(A,N)^h*M; res=res^(2^(top/2)); res2=Mod(M,N)^h*B; print1("Test#"i": h=",h); if(res==res2,print(" passed the test"),print(" failed the test")))} ? check_proof(5,718,997,500) Test#1: h=250 failed the test Test#2: h=992 failed the test Test#3: h=235 failed the test Test#4: h=283 failed the test Test#5: h=116 failed the test Test#6: h=832 failed the test Test#7: h=159 failed the test Test#8: h=133 failed the test Test#9: h=487 failed the test Test#10: h=310 failed the test Test#11: h=568 failed the test Test#12: h=565 failed the test Test#13: h=352 failed the test Test#14: h=269 failed the test Test#15: h=580 failed the test Test#16: h=22 failed the test Test#17: h=601 failed the test Test#18: h=992 failed the test Test#19: h=162 failed the test Test#20: h=136 failed the test ? ? check_proof(249,804,997,500) Test#1: h=548 passed the test Test#2: h=453 passed the test Test#3: h=720 passed the test Test#4: h=551 passed the test Test#5: h=938 passed the test Test#6: h=468 passed the test Test#7: h=40 passed the test Test#8: h=480 passed the test Test#9: h=562 passed the test Test#10: h=942 passed the test Test#11: h=457 passed the test Test#12: h=911 passed the test Test#13: h=742 passed the test Test#14: h=381 passed the test Test#15: h=187 passed the test Test#16: h=208 passed the test Test#17: h=991 passed the test Test#18: h=660 passed the test Test#19: h=240 passed the test Test#20: h=310 passed the test ? [/CODE] You failed all 20 tests. Now it is your turn. (In the second run used the true pair to check my proof checker. |
[QUOTE=preda;547100]If you do that, my verification will catch your cheating right away. The verification checks both halves, covers all the iterations, and as such does detect your cheat attempt easily.
Let me try to explain why your cheat attempt is detected: 3 is the base (starting point) of the PRP test. prp(3^h * M, k) == prp(3^h, k) * prp(M, k) == prp(3, k)^h * B (because prp(M, k) == B (B is "F" in your naming)) The verification compares for equality: prp(3, k)^h * B == M^h * B, which would pass if prp(3, k) == M. But as you chose M "at random" the verification above fails with high probability, and your cheat it detected. Does this make sense? I'm sure you could have worked through the above algebra without the hand-holding.[/QUOTE] This doesn't make sense either. Why do you need B? you can simplify it in both sides. If that is true, you just found a method to run the PRP test in half number of iterations than required. This is just a proof of work of the fact that I start from M and I get B after a number of iterations. But there is no way for you (that we know of) to test if M is correct (i.e. it represents indeed the residue after 250 iterations, in Robert's example). IF you would have any procedure/function/algorithm f(R,k) to test if residue R is the right residue after k iterations and give you true or false, then why don't you just run this function for the last residue (996 in the example) and don't need any other verification? I begin to believe that I am stupid, but really, I don't get this. Please provide an example with numbers, for a PRP of a mersenne number with a small exponent. Even M29 or M41 would be right. |
[QUOTE=R. Gerbicz;547125]
Now it is your turn. (In the second run used the true pair to check my proof checker.[/QUOTE] Wait! Crosspost. Let me digest this! :blush: |
[QUOTE=LaurV;547126]This doesn't make sense either. Why do you need B? you can simplify it in both sides.[/QUOTE]
There are flaws in that post, but probably all previous posts were good, used the same notations from Preda: [url]https://mersenneforum.org/showpost.php?p=546553&postcount=15[/url] the verification for a pair of residue: prp(A^h * M, topK/2) == M^h * B. (in my code top=topK and used N for modulus). And it is a false that the test is passing only for the true (M,B) pair. |
[QUOTE=LaurV;547126]This doesn't make sense either. Why do you need B? you can simplify it in both sides. If that is true, you just found a method to run the PRP test in half number of iterations than required. This is just a proof of work of the fact that I start from M and I get B after a number of iterations. But there is no way for you (that we know of) to test if M is correct (i.e. it represents indeed the residue after 250 iterations, in Robert's example). IF you would have any procedure/function/algorithm f(R,k) to test if residue R is the right residue after k iterations and give you true or false, then why don't you just run this function for the last residue (996 in the example) and don't need any other verification?
I begin to believe that I am stupid, but really, I don't get this. Please provide an example with numbers, for a PRP of a mersenne number with a small exponent. Even M29 or M41 would be right.[/QUOTE] Proof by example it is then. Python3 and modulo M7 [CODE] $ python3 >>> A=3 >>> B=3**64 % 127 >>> M=3**8 % 127 >>> h=5 >>> (A**h * M) ** 8 % 127 == (M**h * B) % 127 True >>> M=42 >>> B=M**8 % 127 >>> (A**h * M) ** 8 % 127 == (M**h * B) % 127 False >>> M=13 >>> B=M**8 % 127 >>> (A**h * M) ** 8 % 127 == (M**h * B) % 127 False [/CODE] |
[QUOTE=preda;547139]Proof by example it is then.
Python3 and modulo M7 [CODE] $ python3 >>> A=3 >>> B=3**64 % 127 >>> M=3**8 % 127 >>> h=5 >>> (A**h * M) ** 8 % 127 == (M**h * B) % 127 True >>> M=42 >>> B=M**8 % 127 >>> (A**h * M) ** 8 % 127 == (M**h * B) % 127 False >>> M=13 >>> B=M**8 % 127 >>> (A**h * M) ** 8 % 127 == (M**h * B) % 127 False [/CODE][/QUOTE]Zero is the only other value here that satisfies the condition:[code]A=3 h=5 N=127 e=8 print("Correct value {}".format(A**e % N)) for M in range(0,N): B=M**e % N if (A**h * M) ** e % N == (M**h * B) % N: print("Found {}".format(M))[/code]Output:[code] Correct value 84 Found 0 Found 84[/code] |
AWS outbound data transfer cost
I don't have experience with AWS and the pricing on their website is not easy to understand.
Could somebody please inform me, how much would it cost to transfer 50GB/day out of AWS, for example by doing HTTP/HTTPS PUT or PUSH to a server that is not in AWS, with a 150MB size per request if that's relevant. (or is there a better way to transfer such data out of AWS?) |
topK under vs. above the exponent E
There is a problem with storing the res64 in the proof file header: if the proof file is public, then the proof reveals the res64, which is supposed to be "secret" in the classic DC setup.
Even without explicitly storing the res64 in the proof header, the proof does store the residue at iteration topK. As topK is under the exponent E (and very close), somebody can simply run a the few iterations from topK to E and thus discover the res64, which again weakens the classic DC which relies on the res64 being "secret" until DCed. An alternative is to set topK to be above E (specifically, let topK be the smallest multiple of 1024 that is larger than E). Let's see what is the impact of this change: First, through the same "proof verificatication" algorithm the verifier can verify that the residue at topK is correct. OTOH the verifier is not able anymore to derive the residue at E, or the res64. Depending on how you look at it, this inability of the verifier to derive the residue at E may seem like something lost (the proof does not allow to derive res64 anymore) or like something gained (the verification does not reveal res64 anymore). In addition to verifying that the residue at topK is correct, we would like to also be able to establish the mersenne candidate status (composite or PRP) based on the proof. We can still do this: if the candidate is PRP, then the residue at E must be 9. So the verifier can run the iterations from E up to topK starting with residue 9, and compare the residues at topK. If equality, the candidate is PRP, othewise it's composite. But.. there is one more point: the proof also exposes the residue M0 (the first middle) which can also be used as a starting point for iterating up towards E. This allows to compute the res64 with only half the iterations of a classic PRP DC. I think we shouldn't sweat over revealing res64 through the proof (or, to be precise, revealing the least significant byte of the res64, which is the only one that's secret), because, once an exponent has a proof available, we can base the DC of that exponent on the proof verification and discount the value of the classic DC (for the particular exponent that has a proof). So, to recap: A) topK under E: allows to extract from the proof res64 type1, type4, res2048, full-residue at E. Reveals res64. B) topK above E: does not reveal res64, and does not allow computing either of those (except by doing one half-PRP starting from M[0]). Oppinions? |
[QUOTE=preda;547267]There is a problem with storing the res64 in the proof file header: if the proof file is public, then the proof reveals the res64, which is supposed to be "secret" in the classic DC setup.
Even without explicitly storing the res64 in the proof header, the proof does store the residue at iteration topK. As topK is under the exponent E (and very close), somebody can simply run a the few iterations from topK to E and thus discover the res64, which again weakens the classic DC which relies on the res64 being "secret" until DCed. An alternative is to set topK to be above E (specifically, let topK be the smallest multiple of 1024 that is larger than E). Let's see what is the impact of this change: First, through the same "proof verificatication" algorithm the verifier can verify that the residue at topK is correct. OTOH the verifier is not able anymore to derive the residue at E, or the res64. Depending on how you look at it, this inability of the verifier to derive the residue at E may seem like something lost (the proof does not allow to derive res64 anymore) or like something gained (the verification does not reveal res64 anymore). In addition to verifying that the residue at topK is correct, we would like to also be able to establish the mersenne candidate status (composite or PRP) based on the proof. We can still do this: if the candidate is PRP, then the residue at E must be 9. So the verifier can run the iterations from E up to topK starting with residue 9, and compare the residues at topK. If equality, the candidate is PRP, othewise it's composite. But.. there is one more point: the proof also exposes the residue M0 (the first middle) which can also be used as a starting point for iterating up towards E. This allows to compute the res64 with only half the iterations of a classic PRP DC. I think we shouldn't sweat over revealing res64 through the proof (or, to be precise, revealing the least significant byte of the res64, which is the only one that's secret), because, once an exponent has a proof available, we can base the DC of that exponent on the proof verification and discount the value of the classic DC (for the particular exponent that has a proof). So, to recap: A) topK under E: allows to extract from the proof res64 type1, type4, res2048, full-residue at E. Reveals res64. B) topK above E: does not reveal res64, and does not allow computing either of those (except by doing one half-PRP starting from M[0]). Oppinions?[/QUOTE] Thinking more about it I think I start to like the variant with topK above E more, as being potentially more resilient againts errors (including programming errors), because the computation that takes place during verification does not retrace the steps of the PRP test to any degree. While a res64-at-topK for the prime case can be computed independently of the proof, even ahead of time (being prp(3, topK - E +1)). |
[QUOTE=R. Gerbicz;547125]You failed all 20 tests.
Now it is your turn. (In the second run used the true pair to check my proof checker.[/QUOTE] The true pair was (249,804), in the follow-up consider another pair (748,193): [CODE] ? check_proof(748,193,997,500) Test#1: h=780 failed the test Test#2: h=613 passed the test Test#3: h=978 failed the test Test#4: h=816 failed the test Test#5: h=21 passed the test Test#6: h=637 passed the test Test#7: h=781 passed the test Test#8: h=236 failed the test Test#9: h=828 failed the test Test#10: h=523 passed the test Test#11: h=85 passed the test Test#12: h=472 failed the test Test#13: h=520 failed the test Test#14: h=419 passed the test Test#15: h=776 failed the test Test#16: h=410 failed the test Test#17: h=967 passed the test Test#18: h=530 failed the test Test#19: h=986 failed the test Test#20: h=73 passed the test [/CODE] 9 passed, and 11 failed, so in 9/20 we successfully faked the proof checker, and note that this trap holds for more than two residues, say when you have 512 residues or more! |
Well, no need to continue here, you convinced me :redface:
My initial understanding of what you (and Mihai) wanted to do was wrong, and the piece of code you provided enlightened me. Now it is much clear, and I played a bit withe the math too. For primes (like provided examples) there are only two square roots of 1, no other pair will match. For composites, especially with many factors) there can be multiple matches (it is related to the number of roots of 1), but yet, finding these matches, i.e. the effort to "fake" the test, is an exponential process; with my limited knowledge, I don't see right now how the test can be faked without trying a lot of pairs, so for large enough numbers, it is MUCH faster to [U]do the test[/U] than to try to fake it. You are totally right. |
[QUOTE=LaurV;547476]For primes (like provided examples) there are only two square roots of 1, no other pair will match. For composites, especially with many factors) there can be multiple matches (it is related to the number of roots of 1), but yet, finding these matches, i.e. the effort to "fake" the test, is an exponential process;[/QUOTE]
I thought that too (so for prime N there is nothing interesting), but it is false for the prime N=997, 2nd follow-up let's consider the 921,151 pair (again the true residue pair was 249,804). [CODE] ? check_proof(921,151,997,500) Test#1: h=594 passed the test Test#2: h=716 failed the test Test#3: h=471 passed the test Test#4: h=538 failed the test Test#5: h=211 failed the test Test#6: h=550 failed the test Test#7: h=510 passed the test Test#8: h=376 failed the test Test#9: h=679 failed the test Test#10: h=958 failed the test Test#11: h=843 passed the test Test#12: h=830 failed the test Test#13: h=911 failed the test Test#14: h=563 failed the test Test#15: h=481 failed the test Test#16: h=243 passed the test Test#17: h=676 failed the test Test#18: h=236 failed the test Test#19: h=46 failed the test Test#20: h=937 failed the test [/CODE] Faked the proof checker in 5/20 of cases (the true probability of fake is not 1/4). But this type of fake is much harder for large N. |
[QUOTE=preda;547268]Thinking more about it I think I start to like the variant with topK above E more, as being potentially more resilient againts errors (including programming errors), because the computation that takes place during verification does not retrace the steps of the PRP test to any degree.
While a res64-at-topK for the prime case can be computed independently of the proof, even ahead of time (being prp(3, topK - E +1)).[/QUOTE] I updated the proof file format and the verification protocol, please see: [url]https://github.com/preda/gpuowl/wiki/PRProof-File-Spec[/url] [url]https://github.com/preda/gpuowl/wiki/Proof-Verification[/url] The file changes are: - topK is above E. topK is defined as the lowest multiple of 1024 larger than E. As such, it is not stored in the proof file anymore (because it's derived from E), and also is not part of the hash anymore (because there's no choice over its value). - the "classic" res64 is not part of the proof file anymore. The verification changes are: once the proof is verified, i.e. the residue at iteration topK is proved correct, a number of topK-E iterations can be run from 9 (or, equivalently, topK-E+1 iterations run from 3) to discover the expected residue at iteration topK for a "probable prime". Comparing the proof residue "B" at iteration topK with this computed residue decides whether the proof corresponds to a probable-prime or to a composite. Because topK is after E, the proof does not allow to obtain the "classic" res64 type-1 or type-4 anymore. Also the gpuowl code has been updated with these changes. |
Choice of proof power
For a 96.5M exponent (around the current wavefront), generating a proof of power 9 takes about 4minutes (on Radeon VII). Verifiying the same proof takes E/512 i.e. 188540 iterations, which on the same GPU comes to ~2min. This seems to me around the optimum, considering that a proof is normally verified twice.
If instead of 9, a power==8 is used, the proof generation time is halved to 2min, but the proof verification time is doubled to 4min. If instead of 9, a power==10 is used, the generation is (a bit more than) doubled let's say to 9minutes, and the verification in halved. Also the temporary disk space needed for residues while the PRP is proceeding is doubled to 1024 residues. The effort ratio generation-to-verification should stay roughly the same as the exponents increase. The size of the proof file is linear to power+1; thus not a big difference there between powers 8 to 10. A verifier would not normally want to verify a proof of power 7 or less, because it would be too expensive for him (relative to verifying a proof of power 8-10). The max power that is allowed by the current spec is 10 (this limitation comes from mandating topK to be equal to E rounded up to a multiple of 1024). This leaves the options for practical proof powers to 8, 9, and 10. I wonder whether we should allow this choice (which probably would be the tester's choice), or whether we should mandate a proof power of e.g. 9 and stop worrying about it. A nice property of the current proof plan is that a proof of a given power is unique for an exponent -- any producer should produce exactly the same proof (assuming correct computation). If the power flexibility is removed, the (correct) proof becomes unique for the exponent (which may simplify things a bit for primenet's integration of proofs). |
practical use of PRP proof (primenet integration)
The simplest solution is centralized management of proofs by primenet. Let's see how big of a cost that represents.
1. The PRP tester The PRP tester, if he chooses to generate a proof, would need to upload it to primenet together with the PRP result. Let's say about 120MB for an 100M exponent, proof size growing proportionally with the exponent. For example a heavy producer that currently does 8 PRP tests per day, would need to upload 1GB per day. An extreme tester that does 400 PRP tests per day, would need to upload 50GB per day (apparently 50GB transferred out of AWS costs about $5 -- assuming the tester runs in AWS and the primenet server outside). 2. The verifier The verifier would need to download a proof of size 120MB, followed by running 200K iterations on it for verification. 3. The primenet server Assuming that primenet handles 1000 PRP proofs per day two-way (1upload+1download), that would be a traffic of 250GB per day, or 7.5TB per month. The server would also need storage. Once the server receives a proof, it would store it into a queue of proofs "available for verification" and would offer it to verifiers. Once a proof is sufficiently verified (twice, one verification originating from the original PRP tester), the proof can be deleted. Thus the server actually needs to store only the proofs that have not been verified yet. A 10TB HDD could store 80'000 proofs. Of course I'm not saying that any of the above is easy or free. I'm just laying out in plain terms what are the implications of the simplest setup. People that are more in the know could express oppinions about the feasibility of such a setup. |
[QUOTE=preda;547701]Once a proof is sufficiently verified (twice, one verification originating from the original PRP tester) ...[/QUOTE]No. I don't like that. We don't self verify.
I think two separate independent verifications are needed. And from two different classes of software. The reason being that if verification code A has a bug, we don't want Evil Mallory to be able to construct proofs quickly that fool verification code A into confirming a bogus proof. So we add in verification code B, from a different code suite, to do another verification. |
[QUOTE=retina;547703]No. I don't like that. We don't self verify.
I think two separate independent verifications are needed. And from two different classes of software. The reason being that if verification code A has a bug, we don't want Evil Mallory to be able to construct proofs quickly that fool verification code A into confirming a bogus proof. So we add in verification code B, from a different code suite, to do another verification.[/QUOTE] Well the proof being on the server, I guess the server can do its choice relative to the desired number of verifications. There's no need to mandate that behavior ahead of time, indeed. But for comparison, for classic-DC we only require *one* independent DC. Even with only *one* independent verification, the proof would be at the same level with the current DC. The secondary self-verification is present only because it's so cheap that it's hard to find a reason to not do it -- the PRP tester already has the proof locally. Also, it would be in the tester's own interest to validate the just-produced proof (by verifying it) before incuring the upload/download cost. But yes, probably the server may want to do at least two independent verifications in the beginning, ideally with different software etc -- and all this in addition to the self-verification done by the PRP tester himself. There is value in the self-verification of the newly-produced proof: first, it makes sure that the server should never receives invalid proofs (wrongly generated). Second, it does validate very strongly the result for the PRP tester himself (against hardware and a large class of software errors). It does not validate the result against a mallicious PRP tester from the server point of view, but that's what the independent verification is there for. Personally I would like the GPU results to be independently-verified on CPU, and vice-versa. |
[QUOTE=preda;547705]But for comparison, for classic-DC we only require *one* independent DC. Even with only *one* independent verification, the proof would be at the same level with the current DC.[/QUOTE]I see this as different. Currently we generate [b]two[/b] proofs (the 64-bit residue) and the server verifies that they match.
Your proposal is that we generate only [b]one[/b] proof. So to balance that we need (at least) two verifications (with different software etc.). Someone self-verifying before uploading is fine, of course, but it doesn't count as a verification to any external observer. Evil Mallory can claim any number of self-verifications, but it doesn't mean any were actually done. |
[QUOTE=retina;547706]I see this as different. Currently we generate [b]two[/b] proofs (the 64-bit residue) and the server verifies that they match.[/QUOTE]
I don't see why you see this as different. 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. [QUOTE] Your proposal is that we generate only [b]one[/b] proof. So to balance that we need (at least) two verifications (with different software etc.). Someone self-verifying before uploading is fine, of course, but it doesn't count as a verification to any external observer. Evil Mallory can claim any number of self-verifications, but it doesn't mean any were actually done.[/QUOTE] Isn't this the same with the current PRP? in which way uploading the initial PRP res64 counts as "a verification", but uploading the result of the proof self-verification does not count as "a verification"? (I mean, either both count, or both don't count, it's the same. It's a result that's trusted by the author and nobody else.) |
The difference is that now: the server verifies and clients create independent proofs.
But now you want one proof only. And if there is a verification software bug then the whole house of cards falls down. Result: We need more than one verification. You can't avoid this IMO. |
I have some catching up to do on this thread. So my comments may not make sense.
As to whether 2 proof verifications are needed, should we hold PRP verification to a higher standard than the current scheme? The current scheme has many weaknesses. Mr. bad guy could create 2 accounts and self-verify. Prime95 could have an obscure bug and be used for both the first and DC runs. There are other holes. It is a system largely built on trust. I see a coding bug in the verifier as minimal risk. I assume any serious bug would spit out "original run no good" errors. Plus, I assume the verifier source will be available for inspection. |
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? |
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.
|
[QUOTE=Uncwilly;547742]What about having known folks, like select forumites, mods, or other well trusted users do some of that as part of their routine work?[/QUOTE]We would be willing to do whatever furthers the project.
We are sure others would as well. Maybe make it a new work-type? :mike: |
[QUOTE=Prime95;547733]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?[/QUOTE] 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. |
[QUOTE=preda;547707]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.[/QUOTE]
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? |
[QUOTE=Prime95;547833]
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?[/QUOTE] 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? |
[QUOTE=preda;547854]Is there a reason for the reverse order?[/QUOTE]
Habit. I'm not averse to LSB to MSB ordering. Only Endian encoding, which IMO encourages architecture-dependent shortcuts in programming. |
If it was a vote then I'd vote for LSB at the lowest address.
It just makes sense that way. |
[QUOTE=preda;546574]
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).[/QUOTE] 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. |
[QUOTE=preda;546557]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 [url]https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic[/url] 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).[/QUOTE] 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. |
| All times are UTC. The time now is 17:31. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.