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.
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.
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.
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.
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?
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
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?
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.