> In other words, you could theoretically have no knowledge and just get astronomically lucky to an arbitrary degree (whatever degree it would take to cross that proof threshold).

Even if you remove all the statistical nature from the system: They're trying to prove they have a piece of knowledge of finite size. If astronomical luck is a real concern, then you have to worry that even a non-probabilistic prover could have just guessed the knowledge.

Or as an analogy, even if you had a perfect and magically irreversible hash, someone could still guess the password first try.

In many applications of zero knowledge proofs, you prove knowledge of solution to a puzzle that need not have a solution. E.g. graph isomorphism, a 3-coloring, a Sudoko puzzle. So the probability of guessing the solution can be 0, while there's a nonzero probability of convincing a verifier.

ZKP inherit this definition from the complexity class of interactive proofs (IP) that is usually defined this way. As pointed out in a comment below, IP = PSPACE. Interestingly enough, changing the definition of IP to perfect correctness (1 instead of 2/3) does not make IP any weaker. However, requiring perfect soundness (0 instead of 1/3) would result in IP = NP.

Sure but by the same token I could guess a 256 bit key and decrypt anything I want. The placement of the statistical boundary vs a given adversary compute power is the part we care about, every time.

Yes, these proof protocols allow you to get arbitrary certainty very quickly, so there’s little practical difference.

Scott Aaronson (of quantum computing and P=NP blogging fame) likes to joke that, “okay, fine fine, so these statistical proofs are good enough for the launch codes, military encryption, and multi-billion dollar financial transactions… but what about theorem proving, where you just can’t take any chances?”

Hence why this is a completeness "probability". In practice this is fine as alternative mechanisms to prove such things as identity involve mechanisms like signatures and hashes, which also can be guessed.

But isn't that how RSA works? Generate pseudoprimes - prove that they "should" be primes. That doesn't sound like "completeness" either but all modern asymmetric encryption uses public keys.

Right, but that astronomical probability is, as you say astronomical. In fact, it’s even better: even i have you a number of trials equal to the number of atoms in the h overs, your expected number of wins would still be astronomically small.

With that way of thinking nothing is secure because random byte generator can reveal it.

Note that it's true for any cryptographic algorithm.