Programming Zero Knowledge Proofs: From Zero to Hero
zkintro.com
zkintro.com
You can run an arbitrarily large, arbitrary long program, and whatever the program outputs, you can make a tiny proof-signature that says "this is the output you'll get if you run this program yourself".
The proof-signatures are relatively small, and you can verify them on small devices in milliseconds.
Another computer can trust the claimed output without having to run the program itself, by verifying the proof-signature.
This scales to arbitrarily large computations, so for example if a supercomputer says "I ran a quadrillion petaflops of your program for 1 year, and the result was the picture attached to this signature", you actually can verify that the picture is correct, quickly and efficiently - without having to trust the supplier.
It's as good as if you re-ran the program yourself (up to cryptography-grade probabilities, which is good enough).
Or if the big computer says "this entire Debian distribution of binary files was indeed compiled with this version of GCC", you can quickly verify that all the binaries are exactly what they should be - without having to trust anyone.
The proof process is rather slow, but it has gotten a lot faster over the last few years, and will continue to.
I was amazed when I learned that it's possible to securely check an arbitrarily large computation's output or result without running it yourself.
It was so counter to my intuition: it seemed like you would have to trust whoever makes the claim, or run it yourself. But you don't!
(So amazed and intrigued that I had to learn how it's done, and now part of my work these days is optimising the proof process.)
> So amazed and intrigued that I had to learn how it's done
Any chance you could just illustrate this somehow with a basic example? I just don't see how you could possibly verify that a program is produced with GCC without going through approximately as much effort as it'd take to compile it.
More useful cases include decoupling payment information from users, to preserve their privacy. You can prove that somebody paid for the action you want to perform, without identifying the payer. For example to offer cloud storage without knowing which data belongs to which user, so when there is a data breach or law enforcement order, the answer to "tell me everything you know about user X" is their payment history, but not which data is theirs.
Correct.
People who need the privacy can set up isolated bank accounts and legal entities.
Less cryptography, your accountant will even understand.
The basic concept here is: ZKP lets you prove arbitrary statements.
Instead of:
Here is entire bank history, you decide.
Had a fixed income above $X for 12 months.
Had a surplus of $X after fixed expenses in the last 3 months.
Did not buy anything irregular above $1000 in the last 3 months.
Think of a ZK proof as a program that can take both public and private knowledge as input, and produce public and private knowledge as output.
This is what seems magical to me: A program with secret input. You can't run the program to verify that my execution of the program is correct, but you can verify a proof that I ran the program with input you didn't have.
The way private knowledge works is through cryptographic commitments.
For example, the bank may start by giving you a signed, structured document with your transactions.
You can then feed their signature and the document to your program, and produce any derivation.
This requires cooperation from the "bank", ideally providing Merkle trees to make sure no tx is missing in the proof like it would be for a blockchain-based solution.
Eg Goldman Sachs could encode all their compliance rules in a program, and publish a proof that their books pass the check by that program, without revealing anything about their accounting.
More crypto focussed: suppose you build a 'better FTX'. You could publish a proof that you ain't hiding an Alameda, ie that everyone who should have been liquidated actually got liquidated, and doesn't get special treatment.
In a banking context, you could in theory also run your know-your-customer (KYC) rules against customer provided data, store the proof, and delete the original data. That way, you still have proof that your customers don't have ties to North Korea or Russia, but you can't be compelled by anyone to reveal the data later (nor accidentally leak that data, etc).
Of course, for that latter application, you need a sharp lawyer to make sure that storing the proof instead of the original data is enough for your KYC obligations.
If you want to go further, you could have your customers run the KYC rules locally, so that their data never leaves their premises.
(For all these applications, you still have to have a mechanism that connects the real world to the inputs of the programs whose execution you are proving.
So eg Goldman Sachs would still need an auditor that checks that the assets and obligations they have in their balance sheet actually exist, but the auditor does not otherwise need to make judgement calls or apply any rules.)
Digital signatures are useful, we all know that, now imagine if you could sign not only data, but also computation result. As in “I ran this code with these inputs and it produced that output”.
If you imagine that this would work, and it takes less time to verify that signature than running the program myself, you have a succinct proof.
If in addition you can hide some of the inputs you used, then you have a zero knowledge proof.
So ZKPs are “stronger” signatures as they can sign more than data. Sometimes a signature is enough, sometimes you need more. Sometimes you need privacy so you verify a signature inside a ZKP :D
- verifiable, auditable, anonymous online voting
- anonymous signatures, authenticating that a whistleblower complaint comes from a real employee, without knowing who the employee is
- verifying your personal data without making it public. E.g. verifying that you're over 18, either black, disabled or low-income, revealing no other identifying information about yourself. This would require collaboration from the government and "compatible" ID cards.
- Blacklist handling, letting you comment anonymously on line, verifying that none of your previous comments have been banned for abuse.
But it is early days and I think there's going to be many more use cases in the future around data privacy. Take an example of credit bureaus. What if instead of a lender sending over all the personally identifiable information needed to do a lookup it could instead send a ZKP to prove it knows enough information about an individual to be authorized to retrieve their record, meaning instead of sending SSN, DOB, Address, Phone, Name, they could instead just send enough specific values in the hash of a combo of some of those fields to prove that the full hash is known but without exposing the full hash itself (along with the existing shared secret to have authorization do lookup a value in the credit bureau in the first place).
Your server costs would only need to be for the metaprogression/persistence related stuff that could be done relatively infrequently based on updates from the client.
ZK proofs are potentially a transformative tool for real-tine distributed systems in general, not just games. They potentially improve laency ("ping"), by changing the communication patterns in a distributed consensus system. That's great for games and other real-time systems.
Right now, the way this works is essentially through a lot of trust and some guarantees by the fed. This has some downsides: because you need a lot of confirmations, it makes transfers take longer. Also, small players can't really get in on this system, so some regional banks are at a disadvantage.
How do you make this safer and more robust? GS obviously can't send info on all of its clients accounts and balances to Citi. You could imagine a protocol where the client/GS sends Citi a zkp to prove that the client has the money (as long as all inputs are agreed upon).
Of course, you don't really need zkps. You could also have the fed keep a database on all money in all accounts (like they do in Brazil), so that the bank only has to ask the central bank to give you an ok. But that is a whole lot of power in the hands of a central authority, as well as a single point of failure, which is something banking systems should avoid imo
At the moment this is all handled with Swift, and I’m not sure you what you gain from adding ZKPs. Depending on the transaction you might send a Swift MT799 with a pre-advice letter, a proof of funds letter, or a blocked funds letter. Again depending on what you’re doing you might need a MT760 to send a bank guarantee or some sort of letter of credit, and finally a MT103 to initiate the actual transfer of funds.
At this point your counter party risk lies with the banking institution itself, and their willingness and ability to complete the transactions they have legally committed to, rather than the account holder, and this risk doesn’t go away with the addition of ZKPs.
I think what could be gained with a zkp protocol would be timeliness. Not needing to confirm if the client has funds in the other institution manually or from trusting their in house APIs would be pretty nice.
The Brazilian central bank has a system that does essentially that, and wires here (even for very large sums) take seconds to fill, instead of the usual 2 days for US interbank wires.
When using Swift, the financial institution crafts the content of the messages, some of which describe the state of their systems (like an account balance). So as a counterparty, you are trusting the institution, the jurisdiction the institution is based in, and the laws and enforcement in that jurisdiction.
If you introduce ZKPs, perhaps you could take the human out of the message authoring for some message types, but those messages would still be based on the state of systems controlled by that institution, and really a lot of the “trust” involved with Swift transaction is the trust that an institution will meet its future obligations (something ZKPs don’t help with at all). So the end result is that as a counterparty, you would still be trusting… the institution, the jurisdiction the institution is based in, and the laws and enforcement in that jurisdiction.
There are other payment systems that don’t have the same features that Swift has (like the ability to send bank guarantees, or proof of funds letters, etc…) like ACH and SEPA. But if those things are needed, you’ll just use Swift, or a different system entirely.
The delay in processing Swift transactions is also a feature not a bug for large institutions. If I send you a Swift payment for $100, unless one of us is on a watch list or something, it’ll just go through without any additional input required from either of us. But if I wanted to send you $1,000,000,000, at that level the banks want the opportunity to scrutinise the transaction for AML and anti-terrorism reasons. There is no definition of what a transaction that is involved in money laundering or financing terrorism looks like, so these checks cannot be automated in any way. If you want your transaction to go through, you have to answer whatever questions the bank officers ask, provide any material they ask for, and this can include literally anything they deem necessary. If the transaction is successfully completed it is not because you met some statutorily defined requirements, or somehow proved you weren’t money laundering or financing terrorism, it is because you convinced the appropriate bank officer that the risk of them being implicated in money laundering or financing terrorism was small enough to be acceptable in relation to processing your transaction. So ZKPs can’t help you here either.
Sounds you indeed have zero knowledge of zero-knowledge proofs. Congratulations!
If you want, I could prove to you that I know what zero-knowledge proofs are and how they’d be applied in industry, but you’d be no closer to understanding it. I would do it in a specific way that would basically impart zero knowledge to you, beyond the fact that I know what I’m talking about. Interested? :)
- Anonymous credentials (this is what Signal does) - maintain an encrypted blob representing a group chat (members list etc all stay encrypted and Signal cannot tell who is in a group chat). A normal client can provide a zkp that they are in a particular group chat (the decrypted blob contains this member for example) and have a message delivered to other group members. Both the client and the recipient can keep their identities encrypted and the zkp proves the membership of the plaintext client / recipient.
- Encrypt some metadata of a message sent to someone. You can build a ZKP that the plaintext behind the encrypted metadata satsifies some properties such as recipient is not in some blacklist (and so on). All this can be done by maintaining privacy because the metadata stays encrypted.
- Given an electronic medical record, you can prove that the record contains a vaccine without sending the record over the wire to some other party.
Lots more such ideas exist.
zkVMs are a good place to start playing with things.
I guess I'm wondering if Signal still basically has enough info to make good guesses at group existence.
The central authority in this scenario cannot discriminate between transactions - any function that would compare two or more transactions cannot glean any useful information that would allow to discriminate. And and security of the anonymity of past transactions will be reducible to the security of the cryptographic hash function used (the next best thing to Information-theoretic security). As for forging money, depending on what ZKP approach is used even a quantum computer will be insufficient.
The central authority can still print money and can obviously shut the entire system down.
It is interesting to ponder whether or not some government will decide to take such a step and surrender all control (except for the nuclear option) over how their currency is used. It will certainly boost demand for the currency.
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.
A paper-tech protocol for validating Sudoku solutions without revealing the solution:
Thus you can get very fast to a probability smaller than you quantum tunnelling through a wall
You can also use multiple different types of ZK proofs for the same data, same as using multiple hashing algorithms, for more certainty.
Right, but we may be 99.9999999999% sure.
If you are in this articles audience you would simply state the producer of the ID card signs a statement that the person is over 18. No ZKP needed.
The article like many others would be improved with a better example.
If the signer keeps a copy of the signature and who they made it for, someone who gets a hold of that and the records of party you used the signature at they can find out who you are.
There are ZKP based protocols that allow for age verification where even if the party that attests to you age keeps records they do not find out where you are using that attestation, and the party you use the attesting with only finds out that you are above their age threshold and what attesting party you used.
I think that this can be done without ZKP if instead of simple signatures we use blind signatures.
And yes, as previously mentioned the party you are testing to does not know your birthdate or any other information.
There is zero need for zkp with either of these
Eg you could prove that 'either your age is a prime number or that you have green eyes and live in New York'.
* 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.
One of the most obvious flaws of blockchains is that every node needs to re-run every transaction to know that the block is valid, leading to the same computation being run thousands of times.
Instead of having to do this there are new Layer2 chains like Polygon zkEVM or zkSync that post a compressed blob of transaction data and a ZK proof that all transactions in that data are valid according to the rules of the EVM. This makes the chain 1000x more efficient as the computation only needs to be run once and verified 999 times.
The proving is still slow and expensive which is why this isn't fully rolled out, but it's getting faster very quickly with both software improvements and custom ASICs for proving.
> 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.
So, just a form of certificate chaining? With the same old challenges that come up if Bob learns that one of the issuers was compromised for some period of time?
ZKP allows you to run arbitrary logic, without the id providers having to anticipate what you are trying to do nor having to cooperate. Eg you could prove that 'either your age is a prime number or that you have green eyes and live in New York'.
crypto people need to learn crypto.
VCs will allow you to verifiably specify your date of birth or maybe your passport number.
What ZK does is allows a third party to ask questions like "is the date of birth of this person prior to 2-Sep-2006" (ie, are they over 18) or "is this person a passport holder for country X" and the ZKP system can say yes or no without disclosing the actual birthdate or the passport number.
It's is a real improvement in privacy, although I'm unconvinced it is worth the incredible inconvenience of implementing it.
What prevents the birthdate from being gleaned through a simple binary search? Or, if it's specifically an "over 18 today?" query based on some decentralized timestamp source, what prevents the query from just being repeated every day until the result changes (assuming it returns "under 18" at first)?
"Be liberal in what you receive, and strict in what you send."
The protocol would have to specify an authorized inquiry field or use validity by time, using a global consensus (current bitcoin block + challenges that take bitcoin_blocks block production rate on average to solve)
Perhaps a very explicit prompt "This service wants to know if you're > X years old!" might give up the trick, but then users would have to be trained not to click through it within milliseconds, which is never the most viable solution.
What did you implement VCs and ZK for?
It was a crypto/blockchain/decentralized ID thing.
Almost. The result is from CRYPTO89 paper of Bellare and Goldwasser. They derive a signature scheme from a nizk. It is not known whether you can get a nizk from a signature scheme. Moreover, no signature scheme can be a ZK: https://crypto.stackexchange.com/questions/35177/is-using-di...
Even for some ZKP scheme that do require trusted setup, you can perform the setup in a multi-party way that allows anybody to contribute randomness, and as long as even one person is honest, the whole thing is private.
There are zero-knowledge proofs that don’t require a trusted setup phase. A plain old logarithmic equality proof is a very powerful tool, making it possible to ensure correct reencryption shuffle, decryption or encoding. They don’t get the same appeal as generic ZKP systems that get all the hype, which deters practically-minded people from getting familiar with the mechanisms and opportunities. At least, that was my experience when getting into ZKP.
I believe it's possible to do a trusted setup with many hundreds or thousands of anonymous people too, someone would need to get every single contribution to recreate the trusted setup.
> "Zero-knowledge proofs (ZKPs) are a method for one party to cryptographically prove to another that they possess knowledge about a piece of information without revealing the actual underlying information."
So, like this?
1. An app needs to confirm a user login is correct
2. But the app can't know the user's password because it's a secret
3. So the app instead checks for a hash which only the correct password would translate into
4. Now the user can enter their password, and the app can verify the password is correct without actually knowing it
What am I missing?
As to why your example isn’t zero-knowledge proof of knowledge of a password, it’s because hash of the same password is always the same thing. So what if someone copies the hashed password and passes it as their own? You say, sign something? But I can reuse the signature. You say, sign a random challenge? Okay, but what if, on the other side, the verifier (ie. the app) adaptively picks a challenge instead of randomly sampling it? … Continue this line of thought, and once you have the correct solution, simplify it and remove the unnecessary parts (eg. Signing something is too strong of a requirement) and you get something called Zero-Knowledge proof of knowledge out of an honest-verifier sigma protocol.
As for ZK proofs that are not proofs of knowledge, then the easiest way to think of it is an encrypted data structure like a database. Imagine the client wants to check whether an element is in some set on a server, where the server has an “encrypted” form of a set and can’t see what’s in it. How can the server check membership of an element and convince the client? That’s done with a ZK proof. You say what about Fully Homomorphic encryption? That’s also technically ZK… what’s not a ZK? For anything that you can’t write a simulator. What’s a simulator? Pick a cryptography textbook.
In the end all I know is you are older than 18. I don’t know your driver license number or SSN, I don’t know your name. I know nothing but the fact that your are older than 18.
This is also accomplished by just properly scoping the function. Considering the widespread availability of solutions to this well-known* problem, I wonder why anyone would "use ZKPs" - and what does that even mean? What npm should I install - and why?
* where my ACME Challenge fans at
There's no way to check that someone's age is old enough with just a hash unless you break the hash.
The most common but painful way to write ZK circuits is with Circom. Better more modern ways are with Noir or using SP1 which can prove arbitrary rust code.
Apparently not, isn't it designed specifically such that it's scoped to a particular "proof"?
You guys always say "without it linking you to your identity" as if identity is built into JavaScript or something. How does using a password hash inherently leak my PII? What problem does ZKP solve?
Using conventional development you can also do the trivial stuff you mentioned like running password through regexp.
How do you verify the password meets certain requirements sever side without getting that user data? Client side input can't always be trusted as anyone can modify that regex check.
Here's a project doing passport verification for services without needing to send them a photo of your passport: https://github.com/zk-passport/openpassport
With something like TLS notary you can prove anything signed by a https certificate, so you can prove there are enough funds in your bank to get a mortgage without revealing how much money you have.
In response to your comment The ZK proof can prove anything, like that the password has enough special symbols and numbers - you definitely do not need "ZKPs" to do this trivial task.
and
> There's no way to check that someone's age is old enough with just a hash
Yeah you can, you log them in then link them to that userData with an identifier - typically an email address or unique user ID. You can easily write the login API to know nothing but hashes, or you can write it to respond with - to use your example that user's age - if the password is correct (without ever actually knowing the password).
Re: Passport verification
Anybody can verify any document with enough identifying information about the document and a registry to match it up to. You don't need a private/public key library wrapped around any functions to accomplish that, but the government probably requires the photo for a reason. Maybe you can verify the document, but a lot of services are going to require photo identification regardless of what your library can do without a photo. Again trying to find what problem this solves. Would have been way cooler if you said it verified faces with passport photos - that's the hardest part.
You haven't provided an alternative way though? If you're looking for more complicated things they can do see: https://news.ycombinator.com/item?id=41430157
> Yeah you can, you log them in then link them to that userData with an identifier - typically an email address or unique user ID. You can easily write the login API to know nothing but hashes, or you can write it to respond with - to use your example that user's age - if the password is correct (without ever actually knowing the password).
This doesn't make sense, how do you verify someones age without getting their birthday? Hashes are binary yes/no checks, not range checks.
> Anybody can verify any document with enough identifying information about the document and a registry to match it up to.
So your alternate solution is that every government in the world runs an API you can check a passport against? Instead of them just providing a known public key they signed the passport with? Sounds way over complicated compared to a ZK proof.
Check if it has numbers: \d
Check if it has symbols: \W
Check if it's 6-64 chars long: {6,64}
> This doesn't make sense
Promise you it's how it works.
> Hashes are binary yes/no checks
Nope, just means encrypted text.
> every government in the world runs an API
Hilarious you think a decentralized approach where every participant has a copy of an append-only ledger is simpler than a central server with SQL database. The argument for decentralization was never that it was simpler - it's of course way simpler in many ways to have a single source of truth. If you mean using that passport library on a regular server, then you also have to run an API or nobody can use it.
- As you're still not getting it, how about this: This is a sha256 hash of my birthday, write a function that returns if I'm over 21: `1028d7ea22cbbcb17c4926b08b591506227d7b0e32ce6ce76122461e551a5ab2`
- Nothing I've mentioned needs an append only log, where are you even getting that from? A ZK proof is created from only the data stored on the passport chip.
> when to encrypt
It depends on what you want to do, if it's user login over HTTPS you can pass a plaintext password to the server and hash/compare on the server only. It would still be secure because the plaintext is never saved in a db (only the hash is), and was TLS encrypted in transport.
-----
> This is a sha256 hash of my birthday, write a function that returns if I'm over 21: `1028d7ea22cbbcb17c4926b08b591506227d7b0e32ce6ce76122461e551a5ab2`
You hash the point of access like a password or key, not the data itself. When the access is granted, you return the data. sha256 is never meant to be decrypted. It would be like this:
interface User {
id: sha256;
name: string;
age: number;
}
const users: User[] = fetchUsers();
const isOver21 = plaintextId => users[encrypt(plaintextId)]?.age >= 21;
const validHashes: BirthdateHashSha256[] = seedHashesForToday();
const isOver21 = hash => validHashes.includes(hash);This is the situation zero knowledge proofs are used in:
- The client doesn't trust the server and doesn't want to give it any info (that's the zero knowledge part)
- The server doesn't trust the client (that's the proof part)
If you break them of course the problem is much easier to solve.
If the client trusts the server they can give it a scan of their passport.
If the server trusts the client to run that code then you don't need a proof, you may as well just have a popup that says "are you over 21?"
A rainbow table is just breaking the hash and then you may as well not have it, in the real world the client would add a salt so this isn't possible.
:) if I get a penny every time someone logs sensitive information in plain text to some log file without realizing they did.
Also you might not understand web dev 101. Every website including this one that uses HTTPS sends encrypted data, the password you enter in a text input is in plaintext. For the backend - as I said above, the server hashes it and saves the hash, never the plaintext password.
That's how it works - nobody said anything about "log files".
It was very long-winded, so I haven't fully read it yet.
The key difference seems to be that a simple has function has a single argument. To verify the output you need the input value. While a ZKP function has two arguments, and one of them is not needed to verify the output.
Not sure if it makes much sense in a direct login scheme, but the alternative scenarios sound more interesting. For example, proving to an adult website you're over 18 without revealing your identity to that website.
[1]: https://zkintro.com/articles/friendly-introduction-to-zero-k...
If I use an authentication provider, am I now "using ZKPs" because I can log people in without knowing who they are?
Or if I use any identity verification provider (example: Clear), am I using ZKPs since my app doesn't actually see your identity? We just get the OK from Clear?
I found the Sudoku example more illustrative, where you want to share your knowledge of the solution without sharing the solution itself. In that case, others do indeed care about the details of your knowledge.
You can't just provide a hash of the solved board and say "lol solved it", as only those who had also already solved it could verify your statement. Maybe I don't trust those others who claim they also solved it, how can I verify that indeed you solved it? You could tell me the solution but then you'd ruin the puzzle for me, which is no good.
So as I understand it, the point of ZKP is that they allow you to share proof of your Sudoku solution to me, in a way where I can be certain you do indeed have the right solution, without me learning what exactly the solution is.
Wait, why not? You could represent the Sudoku board as matrices, here's an example of one block:
[
[9, 5, 7]
[4, 8, 3]
[6, 1, 2]
]
Imagine a "Sudoku Online" where we all have our own private boards, but we have a shared public chat like an online game. Any of us can click "Check Solution" which hashes our Suduku board and sends it to the chat. A message might look like:
*magicalhippo is checking a hash... f3ghziiv × Failed*
*bschmidt1 is checking a hash... 242eef7z × Failed*
*magicalhippo is checking a hash... zzw4zq3x Passed*
The validity check could run on a central trusted server, like where the game is hosted, or in a peer-to-peer setup a condition of passing could be that a peer machine must validate it. So no client can validate their own hash. It could even be in an "Unverified" state until some threshold % of players have validated it - could do anything you want, but I don't see how "ZKPs" offer any solutions.
Most of the libraries are either utils that have like generateUUID functions in them, or they're private/public key libraries that let you wrap functions in an additional encrypted layer. Haven't seen a goto ZKP npm yet or heard anything about what it improves/solves.
Forgive my simplified/contrived examples but you can do a whole lot more with zero knowledge proofs than you can do with just hashes and access tokens, stuff that has nothing to do with blockchain.
For example:
1. An individual receives a contract via email and needs to confirm that it contains a specific clause ("The client agrees to pay $10,000 within 30 days").
2. However, they don’t want to reveal the rest of the contract to the verifier.
3. The individual uses a ZKP that proves two things:
a. The contract is digitally signed by the specific email domain of the sender (e.g., @example.com).
b. The contract contains the specific clause matching a regular expression pattern (e.g., The client agrees to pay \d+\ within \d+ days).
Here's another one:
1. A passenger needs to prove to a ride-sharing app that they are within a specific pickup zone to request a ride.
2. The passenger doesn’t want to broadcast their exact location due to privacy concerns. They're using a device that can attest to the authenticity of their location.
3. The passenger uses a ZKP that proves:
a) Their current location is within the allowed pickup area.
b) Their mobile device has provided an attestation that their given location wasn't spoofed.
5. The rider can choose to share their exact location with a nearby driver when the time comes, but doesn't need to broadcast their exact location to all drivers.
And yet another one:
A user wants to prove that their edited photo originated from an actual physical camera capable of signing images.
For each consecutive edit, the editing software creates a proof that the input image is either an original signed image or comes with a ZK proof that it's derived from a sequence of edits originating from a signed input image. ZK proofs can be combined in such that we can turn a large number of proofs with dependencies on one another into a single, quickly verifiable proof. So in the end you can quickly verify that a heavily edited image does indeed originate from a trusted camera.
If you were part of multiple orgs and just want to prove you're part of any of them without revealing which in particular, then a ZKP can help.
This is useful in the case of whistle blowing you can prove you do work at a company, or say a US Senator can show the government is up to no good and prove they are a senator without revealing who they are.
I can't get anyone to explain how it's different than a password hash other than in these elaborate hypothetical scenarios that don't relate to technology.
My question is then: What is unique to ZKPs? Are the ZKP folks just asking us to start calling these techniques "ZKPs"?
When I use Clear for IDV is that a ZKP? Just like your example, they show the ID to Clear, but I never see the ID.
Clear is not ZKP because Clear servers learn all data from your documents. With ZKP Clear would only know that you hold an ID with details matching the ticket you also hold. This is just 1 bit of information instead of many.
Anyway, the ZKP concept is not about decrypting hashes at all, but looking at peripheral data to prove something (Alibaba Cave - Victor only knows Peggy knew the password because he had access to some other data - the path she took). "checking length etc." only if those hints are already available to the system in some way. And because of this approach, why would you need the hash? Just don't use passwords at all in the case of ZKP right? Simply rely on the other identifying data that you have access to, that you use anyway. Also - how secure is this loose profiling technique compared to email-backed passwords over HTTPS?
I imagine few product use cases allow for a server to trust all the clients with encryption, while not trusting itself - but there are some use cases like when the server is not the source of truth - file system service, or peer-to-peer stuff like ledgers: If the server's purpose is just to maintain a shared ledger and all the clients in the network are trusted.
But in the case we're talking about, of a service that authenticates clients, you're saying you can't trust the authenticator when that is kinda the point of authentication - they don't trust you, or rather - the server cannot tell for sure that any incoming connection is who they say they are, even if it has "zero knowledge" like their IP address and a face scan (your brother in the same house might pass). The point of a username and password is that you want the server to not trust any connecting clients unless they have this specific data precisely.
So I wouldn't use it for auth.
The verifier would need the government public key and then can see "This ID that has been signed by the governments private key shows XYZ"
The police scanner then verifies the signature and checks that the certificate is correctly signed by the government's public key.
No need for ZKP.
Literally yes, in some places. Passports have a chip in them, and licenses in some countries as well.
> Over the internet?
Tunneling private information over untrusted networks is literally how you're seeing this message.
The whole point of ZK proofs is the zero knowledge part. If you don't care about the person being able to see the information of course there's no need for them.
> It doesn't answer arbitrary questions about the data.
Why would you need a "ZKP" to prevent anyone from "asking arbitrary questions" you simply don't build that functionality.
When I create a web server and allow people to login through an endpoint, they can't ask arbitrary questions about user data either - how would that functionality even exist without me writing it? Typically the server doesn't even know passwords. It simply compares a hash - the hash is computed client-side and the server never sees the real password.
Any peripheral user data you want to return is up to you. Identity is not "built in" to conventional programming languages.
Furthermore, none of the ZKP libraries on npm do anything. Most of them are utility libraries with functions like "generateUUID" and "leftPad". The ones from providers like Cloudflare (their least popular stuff) are just private/public key encryption libraries that they call "ZKP".
I posted this earlier (and it's in the article...) but will reiterate again: ZK proofs are used when the prover (server) and verifier (client) don't trust each other and don't want to give each other data on each other. If you trust the server you can just give it a copy of your passport, if the server trusts the client they can just show a checkbox asking if they're old enough.
I linked to a working library earlier, it's here https://github.com/zk-passport/openpassport
The circuit won’t query DB but rather return your name or maybe a hash that can be used to query the database.
At the moment, producing a zero knowledge proof has roughly a million-fold overhead compared to running a program directly. So there aren't many applications where that's acceptable. So I am very grateful that the blockchain people are more than happy to throw money at the math here. Very generous of them.
In principle, you can use ZKP for privacy preserving compliance work in real (ie traditional) finance.
To quote myself (https://news.ycombinator.com/item?id=41422250):
> Eg Goldman Sachs could encode all their compliance rules in a program, and publish a proof that their books pass the check by that program, without revealing anything about their accounting.
> In a banking context, you could in theory also run your know-your-customer (KYC) rules against customer provided data, store the proof, and delete the original data. That way, you still have proof that your customers don't have ties to North Korea or Russia, but you can't be compelled by anyone to reveal the data later (nor accidentally leak that data, etc).
> Of course, for that latter application, you need a sharp lawyer to make sure that storing the proof instead of the original data is enough for your KYC obligations.
> If you want to go further, you could have your customers run the KYC rules locally, so that their data never leaves their premises.
> (For all these applications, you still have to have a mechanism that connects the real world to the inputs of the programs whose execution you are proving.
> So eg Goldman Sachs would still need an auditor that checks that the assets and obligations they have in their balance sheet actually exist, but the auditor does not otherwise need to make judgement calls or apply any rules.)
"Goldman Sachs could..." but they do NOT. Like they don't use blockcrap for interbank settlements, asset tracking, notary, etc.
So basically, no actual uses so far. And it's not even clear _why_ I would want to use ZKP.
No, they won't.
> worldcoin ID verification is another.
In other words: cryptocrap.
I'm not so sure. That would only make sense, if the lawyers and regulators are on board.
> Like they don't use blockcrap for interbank settlements, asset tracking, notary, etc.
Yes. So far the only way to track real world assets on a blockchain is to have a trusted third party (or third parties) that connect whatever your blockchain says to the real world.
But if you have that trusted third party, you might as well have them run the database that keeps track of who owns what. No need for a blockchain.
ZKP is different in the sense that it's one of only a few things to come out of the 'crypto' world that has at least a _chance_ of being useful in the real world. One day. Perhaps.
(Cryptography in general is enormously useful. Have a look at HTTPS for one example. When I just say 'crypto' I mean specifically everything to do with the blockchain ecosystem. So far the only real applications of crypto / blockchains that I've seen are gambling (generously called 'speculation' or 'investment') and ransomware payments. Cryptocurrencies aren't even good for buying drugs on the black market so far.)
In any case, ZKP is still very immature. But we are very fortunate that the crypto-people are generously funding this area of essentially pure mathematics research.
> examples like confirming someone is of age
When where are the companies that do that? Can I replace my Washington driving license with a ZKP that I can show to police officers or to enter a pub?
There are really no practical examples of the actual usages. Just hand-waving. And moreover, all the examples you provided make no sense. They are far better achieved using classic asymmetric systems.
On the contrary, your sentiment reads less like wisdom and more like hardheadedness. I am glad there are plenty of others here who do not share such a narrow-minded sentiment.
The venn-diagram between cryptocurrency and ZKPs is not a circle, or really even close. They're a mathematical concept first and foremost, and thanks to crypto dumping tons of money into the scaling problem, now much more easily worked with in code across any application. So much for all cryptocrap being, well, cryptocrap!
Your example is terribly contrived. No, you won't replace your drivers license with a ZKP. But a service might validate that you're of age, or meet some other criteria, without you(or they) revealing actual information about yourself.
All of the examples I gave(none of which are my own, but from other commenters who are I'm sure happy to discuss further) require the context of established trust. "Classic asymmetric systems" have problems with this.
Like: "Company XYZ uses ABC to provide asset tracking, and it's now used by 99% of the DEF sector".
> The venn-diagram between cryptocurrency and ZKPs is not a circle, or really even close.
Then it should be treated as such, instead of trying to claim that it has practical applications.
If you can't think of the possibilities that unlocks beyond the examples others have already discussed(none of which were crypto related), that's a limitation on your end.
And? Why is it better than good old PKI?
And even then, it hand-waves away the issues with revoked licenses. How do you do license revocation with ZKPs?