Programming Zero Knowledge Proofs: From Zero to Hero

> The article like many others would be improved with a better example.

It's easy to make this example better:

Assume there are 50 different providers of ID cards, and Alice wants to convince Bob that she's over 18 years old.

Bob trusts all 50 issuers, but Alice doesn't want to reveal who her issuer is.

So here Alice could indeed get the supplier of her ID card to sign such a statement (and perhaps already have one prepared). For ZKP, you can also assume that the ID card issuers are not co-operating (nor do they care about each other), and that different Bobs might trust different sets of providers, and that the sets of trusted providers might change over time.

* The actors are: Individuals I_1, ..., I_n, businesses B_1, ..., B_m, and a central authority A.

* An individual I_j wants to prove to business B_k that A attests that DateOfBirth(I_j) >= 20060902, and that I_j is in possession of a private key, where A attests that it has verified the linkage of the corresponding public key to I_j.

* I_j doesn't want to provide any information about I_j's identity except for the DateOfBirth(I_j) >= 20060902 to B_k. That means, for example, I_j doesn't want to reveal to B_k their ordinal j, nor a single public key that is used everywhere. This means, for example, B_k shouldn't be able to collude with B_{k+1} to combine facts separately provided to the two businesses and build a profile of I_j.

* I_j also doesn't want A to be able to collect information about the fact they provided information to B_k specifically.

With a ZKP, it is possible for a solution like:

* I_j generates a keypair P_1 (private) / p_1 (public) and proves their identity out-of-band to A. A gives them a certificate C_1 typing p_1 to their ordinal j and their date of birth.

* I_j generates a new keypair P_2/p_2 just for dealing with B_k.

* I_j generates a signed certificate C_2 using P_1, tying p_2 to their ordinal j.

* I_j generates a ZKP that there exists a (private input) certificate C_1 signed by A's public key, and that certificate meets the constraint DateOfBirth(I_j) >= 20060902, and there exists a (private input) public key p_1 which is referenced in C_1, and there exists a (private input) certificate C_2 signed by p_1, and that certificate references (public input) public key p_2, and sends the ZKP to B_k.

Now instead you could imagine a solution where A generates certificates for I_j, but that has some downsides:

* The properties to be signed might vary over time. The date of birth cutoff certainly would, and different businesses might want different properties.

* Just one certificate per property isn't enough, because the certificate identifies which public key it relates to. That allows B_k and B_{k+1} to work out they have the same customer I_j. With the ZKP solution, the customer gives a different public key to each. You could work around this by having A provide lots of certificates upfront (inefficient), or by generating certificates on demand (but the A is needed to be involved online in the transaction, and it risks leaking information to A).

So the ZKP solution is, in many ways, simpler in that it removes a lot of constraints while implementing the desired properties, but there are other workarounds if you don't have it.

Roughly: you have 2 secrets that you hash together and the central authority adds the result you disclosed to a list (either to print money or as part of a transaction to transfer money). To spend a note you reveal the hash of one of the secrets (to be added to a list of nullifiers to prevent double spend) and you do ZKP to demonstrate that you possess both of the secrets to *some* note from the public hash list and that the nullifier for that note is what you claim it is. Central authority rejects if nullifier is present in the list.

There are some other approaches to such a system, I believe the Tornado Cash one is the most elegant though it limits you to a discrete number of note denominations.

Note that the proof system Tornado Cash uses is not secure to a quantum computer and such a device will allow to "print money" - in reality, drain the smart contract.