VDF (Verifiable Delay Function) and PRP

[preda]

Originally Posted by chris2be8

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

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.

[preda]

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

[preda]

Originally Posted by preda

1. publish a PRP "probable-prime" for a composite candidate
2. publish a PRP "composite" for a prime candidate

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.

[preda]

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.

[kriesel]

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.

[preda]

Originally Posted by kriesel

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.

Let's focus the discussion on PRP attacks, excluding TF attacks or others.

[LaurV]

Originally Posted by preda

The goal of using the PRP-proof with primenet is to eliminate the double-checks.

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 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! ), 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 correct work (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.

[preda]

Originally Posted by LaurV

But we still need to DC, at least for now. What we would need would be a proof of correct work (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.

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.

[preda]

Originally Posted by LaurV

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 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! ), 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 correct work (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.

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?

[preda]

Originally Posted by preda

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.

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.

[preda]

Originally Posted by LaurV

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.

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.

Anything else, can either be faked (well... almost...more or less) or could be reconstructed without doing the work,

Yet, the point of the PRP-proof is that it cannot be faked, and cannot be constructed 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 and we will still have to DC it.

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?