[pksebben]

the more I think about it, the more I feel like I need someone with deep knowledge to explain ZKPs to me.

So like, we've got this algorithm that gets sent our way and we run it and that provides kind of a cryptographic hash or whatever. But if we're running the algorithm ourselves what's to stop us from lying? Where does the 'proof' come from? What's the check that it's running and why do we inherently trust the source it's checking?

[kahnclusions]

I’m not exactly sure about ZKPs but for age verification the “proof” can come from the government but in such a way that the web service doesn’t know anything more than whether an assertion is true, and the government doesn’t know anything more than you wanted to verify some assertion.

This is a simplified method for age verification:

I want to buy alcohol from my phone and need to prove I’m over 18. SickBooze.com asks me for proof by generating a request to assert “age >= 18”.

My phone signs this request with my own private key, and forwards it to the government server.

The government verifies my signature against a public key I previously submitted to them, checks my age data in their own register of residents, and finally signs the request with one of their private keys.

My phone receives the signed response and forwards it back to SickBooze.com, which can verify the government’s signature offline against a cached list of public keys. Now they can sell me alcohol.

- the “request” itself is anonymous and doesn’t contain any identifying information unless that is what you intended to verify

- the government doesn’t know what service I used, nor why I used it, they only know that I needed to verify an assertion about my age

- the web service I used doesn’t know my identity, they don’t even know my exact age, they just know that an assertion about being >= 18 is true.

[hunter2_]

> the government [...] only know[s] that I needed to verify an assertion about my age

This is problematic if a majority of things needing age verification are looked down upon; for example, insurance companies would love to know what people don't do things needing age and therefore don't buy alcohol (at least not online).

[cycomanic]

The first question is how would the insurance find out that you are doing lots of things requiring age verification? The only body that could tell them is the government, while a distrust in the government can be healthy, I think this is the least thing to worry about, the government typically knows already much more damaging things than how often you ask for age verification.

Moreover, that would only work if there are relatively few things that require age verification and it needs more than just being looked down upon, i.e. while alcohol buying might be interesting information for insurances, watching porn is likely less interesting. Even worse, if the insurance can't distinguish between porn and alcohol (which they can't by design even if the government would give them the information about how often you ask for age verification).

[notpushkin]

I would throw in Privacy Pass [1], just in case the government and SickBooze.com can exchange info.

Sadly, it‘s still hard to explain how exactly it works, but conceptually simpler than arbitrary ZKPs.

[1]: https://privacypass.github.io/

[shermanyo]

Excellent, clear example.

[MatteoFrigo]

I am someone with "deep knowledge", but HN is not the proper place for this discussion. See https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.htm... for the gory details.

Here is a hopefully simple example of how this ZKP thing may even be possible. Imagine that you give me a Sudoku puzzle. I solve it, and then I want to prove to you that I have solved it without telling you the solution. It sounds impossible, but here is one way to do it. I compute the solution. I randomly scramble the digits 1-9 and I put the scrambled solution in a 9x9 array of lock boxes on a table. I have the keys to the 81 locks but I am not giving you the key yet. You randomly ask me to open either 1) one random row chosen by you; 2) one random column chosen by you; 3) one random 3x3 block chosen by you; or 4) the cells corresponding to the original puzzle you posed to me. In total you have 28 possibilities, and assume that you choose them with equal probability. You tell me what you want and I open the corresponding lockboxes. You verify that the opened lock boxes are consistent with me knowing a solution, e.g. all numbers in a row are distinct, the 3x3 block consists of distinct numbers, etc. If I am cheating, then at least one of your 28 choices will be inconsistent, and you catch me with probability 1/28, so if we repeat this game 1000 times, and I don't know the solution, you will catch me with probability at least 1-(1/28)^1000 which is effectively 1. However, every time we repeat the game, I pick a different random scrambling of the integers 1-9, so you don't learn anything about the solution.

All of ZKP is a fancy way to 1) encode arbitrary computations in this sort of protocol, and 2) amplify the probability of success via clever error-correction tricks.

The other thing you need to know is that the protocol I described requires interaction (I lock the boxes and you tell me which ones to open), but there is a way to remove the interaction. Observe that in the Sudoku game above, all you are doing is flipping random coins and sending them to me. Of course you cannot let me pick the random coins, but if we agree that the random coins are just the SHA256 hash of what I told you, or something else similarly unpredictable, then you will be convinced of the proof even if the "coins" are something that I compute myself by using SHA256. This is called the "Fiat-Shamir transformation".

How do we implement the lock boxes? I tell you SHA256(NONCE, VALUE) where the NONCE is chosen by me. Given the hash you cannot compute VALUE. To open the lock box, I tell you NONCE and VALUE, which you believe under the assumption that I cannot find a collision in SHA256.

[sdwr]

> How do we implement the lock boxes? I tell you SHA256(NONCE, VALUE) where the NONCE is chosen by me. Given the hash you cannot compute VALUE. To open the lock box, I tell you NONCE and VALUE, which you believe under the assumption that I cannot find a collision in SHA256.

That's the bit I was missing! The prover pre-registers the scrambled solution, so they can't cheat by making up values that fit the constraints.

[MatteoFrigo]

Yes. The whole trick is a delicate balance between 1) committing to enough information that uniquely pins down the solution, assuming that one can open all the lock boxes, and 2) not opening too many lock boxes so that the verifier does not learn the solution.