Hacker News Reader

Comment by SilasX | Hacker News Reader

The same issues come up with interactive zero-knowledge proofs[A], where someone proves that they possess certain private information without leaking said information.

The proofs have the form:

1) Give the prover a challenge that they only have a 50% chance[B] of passing if they don't possess the private info.

2) Repeat as necessary with new, independent challenges.

3) If they keep passing, hooray! The probability that it's a faker decays exponentially. You can get really high confidence, very quickly!

Doing more rounds is just like re-running the computer proof.

[A] I first learned about the issue from reading the Scott Aaronson lectures that became Quantum Computing Since Democritus

[B] Doesn't have to be 50%, any figure will give the exponential decay and only require a linear increase in the number of rounds, so long as the probability stays the same between all rounds.

View on HN

I fail to see the connection - new runs of the compuuter proof isn't going to randomize the code (like it does in zkp), so its not going to reduce the probability of error (excepting cosmic ray induced errors of course)

Yes it is — the fact that the later computations got the same result is evidence that the earlier ones weren’t flukes.

My comment above didn’t even mention randomization. That’s not necessary. All that’s necessary is that the tests be independent. Randomization is one way to achieve that but not a hard requirement.

Even so, it seems you do see the connection, you just dispute one element that you think is critical.

> My comment above didn’t even mention randomization. That’s not necessary. All that’s necessary is that the tests be independent.

But they are obviously not independent.

This is like flipping a coin once, looking at the result 20 times in a row (without flipping it again), concluding you have magic luck powers since you got heads twenty times in a row, and that would be really unusual in the analgous system where you flipped a coin 20 times instead of just looking at it.

> Randomization is one way to achieve that but not a hard requirement.

This is besides the point, but pray tell. How do you reduce the probability of an algorithm being incorrectly programmed by means of running it multiple times without changing the input or introducing some randomness somewhere? I don't think that's possible. Really the ZKP case isn't even checking the algorithm but checking a specific user input is consistent.

I think this would be equivalent to denying that BPP without coin flips is P, which afaik it is.

> Even so, it seems you do see the connection, you just dispute one element that you think is critical.

I mean, i guess you could say that if you modify the system to add the connection you are trying to establish, then yes the connection becomes obvious.

>But they are obviously not independent.

Yes, independent with respect to the variable you're testing. In the ZKP, the independence is between the challenges given to the prover. In the computational proof, independence is between the probability of computational error affecting the calculation. (To be sure, you'd want to run the proof on different hardware!)

>> Randomization is one way to achieve that but not a hard requirement.

>This is besides the point, but pray tell.

Wait, what? Your original comment[1] was specific alleging that the absence of a randomizer completely broke the analogy:

>I fail to see the connection - new runs of the compuuter proof isn't going to randomize the code.

How would this be "beside the point" when it's the point you introduced? Did you forget the point you were trying to make?

>How do you reduce the probability of an algorithm being incorrectly programmed by means of running it multiple times without changing the input or introducing some randomness somewhere?

Even doing the same run on the same hardware would provide evidence against against the earlier result being a fluke (e.g. from cosmic rays), as I said before. But yes, as above, to round out the possibilities, you'd want different people to translate the proof into different languages and hardware and run it there -- that would likewise increase your confidence in the result, just like running different rounds of the interactive ZKP would.

>I mean, i guess you could say that if you modify the system to add the connection you are trying to establish, then yes the connection becomes obvious.

Sorry, are you really saying that you see no parallel whatsoever between:

a) Run the 4-color computer proof multiple times to increase your confidence that the result wasn't just luck, and

b) Run additional rounds of an interactive ZKP to increase your confidence that the prover wasn't just lucky?

If so, that feels like more of a you-problem.

If you were disputing that additional runs of the 4-color computer proof could increase your epistemic confidence in it, then you should have raised that in response to the original comment[2], not one (like mine) that accepted it and pointed out an analogous situation.

[1] https://news.ycombinator.com/item?id=34088094

[2] https://news.ycombinator.com/item?id=34084448

> In the computational proof, independence is between the probability of computational error affecting the calculation. (To be sure, you'd want to run the proof on different hardware!)

But i don't think that is the concern at hand. Yes, re-running can reduce probability of failures due to soft-memory errors and such. But does nothing against logic errors (or non-transient hardware errors). My understanding is the main concern with the proof is not that a cosmic ray hits RAM and flips a bit, but that either the logic may be wrong or a general epistimitic unease that no human directly inspected the cases of the proof.

In any case i said as much in my original comment. To quote: "excepting cosmic ray induced errors of course"

> Wait, what? Your original comment[1] was specific alleging that the absence of a randomizer completely broke the analogy:

Yes, i stand by that (although accept your point that independence not randomization is the salient property). I also maintain that whether or not it is theoretically possible to do independent tests without a randomness is irrelavent to the matter at hand. What matters is if rerunning the code was an independent experiment, not what could theoretically be possible. Even if there exists some non-random way to do that, its irrelavent to whether or not any method was used.

> Sorry, are you really saying that you see no parallel whatsoever between: > >a) Run the 4-color computer proof multiple times to increase your confidence that the result wasn't just luck, and > >b) Run additional rounds of an interactive ZKP to increase your confidence that the prover wasn't just lucky?

Yes.

Although for greater clarity, i would clarify (a) to say i don't see the connection to non-negligibly increasing your confidence the result of the 4 colour is correct. I agree (and said this in my very first comment) that it would increase your confidence that you didn't get an incorrect result due to a soft-memory error. I would say that relative to all the possible reasons why you might get an incorrect answer, transient hardware failure is very low, so the increase in confidence from rerunning is negligible because the meat of the question is programming error.

In the analagous situation, re-running the zkp gives an extremely high increase in confidence the answer is correct, usually at least halving the possibility of error.

> If you were disputing that additional runs of the 4-color computer proof could increase your epistemic confidence in it

Sure, although the original comment was a bit vauge as to exactly what they meant.

Reply on news.ycombinator.com