20 ms·

Programming Zero Knowledge Proofs: From Zero to Hero

281 points by oskarth 2y ago

cosignal 2y ago
As someone with zero knowledge regarding Zero Knowledge Proofs in a programming context, can someone give me a basic explanation regarding the utility? I do understand the basic principle of ZKP’s, but as yet I’m failing to understand how this would be applied in industry.
- nailer 2y ago
  ZKPs are used for private balances in Solana. Someone can send you a million PYUSD using confidential transfers and your public balance remains 100 dollars.
- EGreg 2y ago
  “I do understand the basic principle of ZKPs, but as yet I’m failing to understand…” 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? :)
- nowayno583 2y ago
  Imagine you are Goldman Sachs and a client wants to make a 100mm USD wire transfer to one of their accounts at Citibank. How does citibank know that the account at GS has the money to cover this transfer? 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
  - AmericanChopper 2y ago
    > How does citibank know that the account at GS has the money to cover this transfer? 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.
    - gbasin 2y ago
      This should not be down-voted
    - nowayno583 2y ago
      But Swift is just a messaging protocol, right? It doesn't handle trust at all - like you said, you need an awful lot of documents for a single transfer. 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.
      - AmericanChopper 2y ago
        Swift is a messaging system, but it absolutely does manage trust. Swift messages can be used to transmit contracts and other financial obligations which are nonrepudiatable. 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.
- baby 2y ago
  The way I always explain it to newcomers now is to start from digital signatures. 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
  - satchel888 2y ago
    [dead]
- coderintherye 2y ago
  The most common example in the talks I've been to have been for verifying anonymous voting amongst a group that you want to verify is valid to vote in the process. ZKPs allow for doing this without needing a central authority to attest to the person's credentials. 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).
- rtg4869 2y ago
  This is a great explainer from one of the pioneers in this space, in case you weren't already familiar with it: https://www.wired.com/video/watch/5-levels-zero-knowledge-proof https://www.wired.com/video/watch/5-levels-zero-knowledge-pr...
- badsandwitch 2y ago
  It is currently possible to use ZKP's to set up via a central authority a digital cash system where the bank notes are all anonymous and all transfers are anonymous. 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.
  - satchel888 2y ago
    [dead]
  - ironSkillet 2y ago
    Do you have any recommended references on this subject? Seems like this sort of system would be able to obfuscate a lot of metadata that can be used to deanonymize activity. Very interesting.
    - badsandwitch 2y ago
      Tornado Cash does this. And you can find articles on how it functions online. You can even read the smart contract that directly implements 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.
- jlokier 2y ago
  For me, the most powerful use of ZKPs is proof of the output of general purpose computations of any kind. 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.)
  - dataflow 2y ago
    > 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. > 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.
    - lifeinthevoid 2y ago
      As far as I understand, you can't just use any gcc binary as it exists today. The program needs to be represented as a specific, mathematical expression that is suitable for zero-knowledge proofs.
- shriphani 2y ago
  Examples of things you can do with ZKPs: - 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.
  - rtpg 2y ago
    in your first example, how does Signal route messages in that model?
    - shriphani 2y ago
      sender specifies recipient but the signal server cannot tell a group-chat message from a non-group chat message.
      - rtpg 2y ago
        so in this world signal still knows I'm sending to N recipients? Or is the fanout happening in a different way? I guess I'm wondering if Signal still basically has enough info to make good guesses at group existence.
        shriphani 2y ago
        Yeah I think you are correct that the protocol isn't safe from traffic analysis.
- eru 2y ago
  I come from a traditional finance background. One underappreciated possible role for ZKP is in compliance. 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.)
  - gbasin 2y ago
    I am building in the mortgage origination space and have these sorts of enhancements on the drawing board... you hit the nail on the head that the bottleneck will be in QC and legal review, as 3rd-parties (especially regulators) may want to manually see the data you used to reach the conclusions you did. Although I'm still digging. You'd be interested in what we're creating btw, it's a crypto-based mechanism that enables instant digital mortgage origination, we should chat!
    - eru 2y ago
      Sounds interesting! I have an email address in my profile.
- p1necone 2y ago
  I can see applications in multiplayer gamedev - imagine being able to run the whole game simulation on a clients machine and have them assert back to you that they killed 7 goblins, looted a rare sword from a chest, and died 3 times - and you could just trust them. 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.
  - k__ 2y ago
    In theory that sounds awesome and I love the idea of ZKP. However, they have quite some overhead that defeats such applications, I think.
    - _alex_ 2y ago
      Yeah prover time is the big challenge rn
  - jlokier 2y ago
    I agree. Exploring this in game worlds came up in a job interview a few years ago :) 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.
    - p1necone 2y ago
      It would be amazing to have a single authoritative server in an mmo for the EU, USA, Asia, Oceania etc regions and only have bad latency if you were actually directly interacting with people from far away.
- ruuda 2y ago
  A toy example: suppose we have some sudoku. You want to show publicly (maybe in a HN comment) that you know the solution, without revealing the solution itself, because then anybody would know it and be able to post that they know it. A zero-knowledge proof enables this. You could also post a hash of the solution, but then you need to know the solution already to verify a submission. (It would also enable others to copy your answers without really knowing the solution, though that can be fixed using a technique that zero-knowledge proofs also use, a blinding factor). 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.
  - sshine 2y ago
    One place I wish there was zero knowledge proofs involved, or even any kind of cryptography, is when you perform credit assessment for loans outside your bank: an external loan provide peeks at your full bank account history to assess whether you’re eligible. They don’t need to know where I buy my socks, or even how much money I have. Only that I have a big enough deposit and a steady enough cashflow.
    - edf13 2y ago
      Where you spend can have an impact on a decision… e.g. you may have the income and savings but if you’re regularly spending on gambling that can be a red flag.
      - hbbio 2y ago
        You can prove that too with zk!
        rrr_oh_man 2y ago
        How could this look like?
- oytis 2y ago
  Judging by job openings mention ZKP it's mostly used in some "crypto" BS.
  - AlchemistCamp 2y ago
    Blockchain development has spurred research that’s more broadly applicable in a number of cases and ZK proofs are one of the more exciting ones!
- miki123211 2y ago
  Good (non-blockchain) use cases include: - 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.
nailer 2y ago
> We can take a digital identity card and prove that we are over 18 years old > Without revealing anything else, like your full name or address 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.
- piotr93 2y ago
  A signature is a zkp. So your example is also a good example :)
  - somezero 2y ago
    A signature is a PoK, but not ZK.
    - piotr93 2y ago
      I was not clear enough, thanks. Whether it is a pok or zk depends on the chosen signature scheme. In any case, zk signature schemes exist and are implied by the existence of one way functions and publicly verifiable nizk
      - somezero 2y ago
        > zk signature schemes exist and are implied by the existence of one way functions and publicly verifiable nizk. 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-digital-signatures-to-prove-identity-a-zero-knowledge-proof/35185#35185 https://crypto.stackexchange.com/questions/35177/is-using-di...
- gchaincl 2y ago
  I think the goal of this is that you can prove, so that your counter party does not need to rely on trust
sshine 2y ago
Another demonstration of Zero-Knowledge Proofs: A paper-tech protocol for validating Sudoku solutions without revealing the solution: https://zudoku.xyz/ https://zudoku.xyz/
- saboot 2y ago
  That's very cool! Here's another cool application for nuclear arms control, https://www.nature.com/articles/nature13457 https://www.nature.com/articles/nature13457
- patrulek 2y ago
  So with ZK-proofs we may never be 100% sure something is true or not? Is it possible that this may be too computational expensive to have certainty at given (or above) level?
  - plopilop 2y ago
    You don't necessary get 100% certainty but the probability of success increases exponentially with each new run. Thus you can get very fast to a probability smaller than you quantum tunnelling through a wall
  - drdrey 2y ago
    It’s the same thing as regular cryptography, I can’t be 100% sure that you signed this message but I can get arbitrarily close, and prohibitively expensive to fake
  - TimJRobinson 2y ago
    Yea it's the same as a hash collision, maybe they managed to type some other message that hashes to the same thing but it's very unlikely. You can also use multiple different types of ZK proofs for the same data, same as using multiple hashing algorithms, for more certainty.
  - sshine 2y ago
    > we may never be 100% sure Right, but we may be 99.9999999999% sure.
cyberax 2y ago
Are there any real uses of ZKP outside of blockcrap?
- knowaveragejoe 2y ago
  There's several already shown in the comments.
  - cyberax 2y ago
    I'm asking about real actual examples, not handwaving.
    - eru 2y ago
      They are useful from a mathematical point of view. (And explore the relationship between P and NP, for example.) Not sure if that counts as a 'real use' to you. See also https://en.wikipedia.org/wiki/PCP_theorem https://en.wikipedia.org/wiki/PCP_theorem 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 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.)
Uptrenda 2y ago
What does everyone think about the 'trusted' setup part of zero-knowledge proofs? Is this a deal breaker for some use-cases or can this phase be done without worrying that the entire process has been hijacked... As has been a core goal of many ah... 'security' councils in the past.
- Ar-Curunir 2y ago
  Only some kinds of ZKPs have that drawback; others don’t. There are many examples of such systems with transparent setup that are used in practice. 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.
  - JanisErdmanis 2y ago
    The multiparty setup is better than a singular-party setup, but it burdens its deployment. How can users be confident of at least one party they can trust whose preferences vary? Further, how can deployment be made so that a malicious party does not sabotage the setup process or is sabotaged by the organiser or network failures? In other words, who would need to be blamed? Doing these things properly makes the process’s deployment significantly more expensive than centralised deployment. Hence, I don’t see them bearing any practical relevance, as any authority that organises their deployment would also be subject to cost optimisation due to human nature and as security can’t be quantified, it suffers first. 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.
    - Ar-Curunir 2y ago
      There are logarithmic-sized proofs with transparent setup for arbitrary computation. These are much better for practically-minded people than ZKPs for ad-hoc computations because you don’t have to be a cryptographer to figure out how to use them
jmakov 2y ago
Can I prove that I'm a part of an org and use this as SSO?
- k__ 2y ago
  Yes, but in that specific example you could also simply use a signature, as the fact that you are part of a single org reveals all information. 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.
- TimJRobinson 2y ago
  Yea you can prove you're some set of users without revealing which one. 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.
zero_k 2y ago
If you wanna do it in a flexible way that is very easy to use and essentially the future of ZK, use Powdr [1]. Just write your code in rust nostd and be done with it. It's a compiler, basically. Once you use it, you'll never go back to hand-massaging polynomials. It'd be like writing assembly. Sure, some can do it, and it can be fun, but why do it if there are compilers out there to do the heavy lifting for you? :) [1] https://github.com/powdr-labs/powdr https://github.com/powdr-labs/powdr
- k__ 2y ago
  For Rust, there is also Sunscreen. https://github.com/Sunscreen-tech/Sunscreen https://github.com/Sunscreen-tech/Sunscreen
- worldsayshi 2y ago
  You sound like you are routinely doing zero knowledge proofs. To me it sounds like a very niche thing. What kind of application area needs knowledge proofs on the regular? Finance?
- kikimora 2y ago
  How about verification speed? The article mentions that avoiding trusted setup would result is sliver verification speed. Could it also increase proof size?
IWeldMelons 2y ago
The language they use looks surpisiningly like Verilog.
shae 2y ago
I recommend the moon math manual, it's a good way to learn this.
WanderPanda 2y ago
This is one of these technologies that is indistinguishable from magic.
- deleted 2y ago
  [deleted]
- 65n56n 2y ago
  Doesn't this open up the way for proof of proofs as well? Maybe math is just the science that describes magic. It is indistinguishable from magic because it is magic.
bschmidt1 2y ago
I wrote ZKPs off as hype ~2 years ago - is it a legit concept outside blockchain marketing? Someone help me understand how it's different from hashes and access tokens? > "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?
- somezero 2y ago
  It’s all just bytes and hashes and alike at the bottom. Absolutely nothing magical. It is the abstractions over them that makes them esoteric, not the fundamental building blocks. 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.
- magicalhippo 2y ago
  The previous article[1] goes a bit into the difference from a simple has function. 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-knowledge https://zkintro.com/articles/friendly-introduction-to-zero-k...
baby 2y ago
If people are interested in trying ZKPs you can write programs in noname[1] in the noname playground[2] and have them compiled down to circuit and also prove/verify them. It's mostly a demo but the language is actively being developed and there's a list of easy tasks to pick up on in the main repo. [1]: https://github.com/zksecurity/noname https://github.com/zksecurity/noname [2]: https://noname-playground.xyz/ https://noname-playground.xyz/

281 points by oskarth 2y ago

As someone with zero knowledge regarding Zero Knowledge Proofs in a programming context, can someone give me a basic explanation regarding the utility? I do understand the basic principle of ZKP’s, but as yet I’m failing to understand how this would be applied in industry.

nailer 2y ago
ZKPs are used for private balances in Solana. Someone can send you a million PYUSD using confidential transfers and your public balance remains 100 dollars.
EGreg 2y ago
“I do understand the basic principle of ZKPs, but as yet I’m failing to understand…” 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? :)
nowayno583 2y ago
Imagine you are Goldman Sachs and a client wants to make a 100mm USD wire transfer to one of their accounts at Citibank. How does citibank know that the account at GS has the money to cover this transfer? 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
- AmericanChopper 2y ago
  > How does citibank know that the account at GS has the money to cover this transfer? 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.
  - gbasin 2y ago
    This should not be down-voted
  - nowayno583 2y ago
    But Swift is just a messaging protocol, right? It doesn't handle trust at all - like you said, you need an awful lot of documents for a single transfer. 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.
    - AmericanChopper 2y ago
      Swift is a messaging system, but it absolutely does manage trust. Swift messages can be used to transmit contracts and other financial obligations which are nonrepudiatable. 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.
baby 2y ago
The way I always explain it to newcomers now is to start from digital signatures. 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
- satchel888 2y ago
  [dead]
coderintherye 2y ago
The most common example in the talks I've been to have been for verifying anonymous voting amongst a group that you want to verify is valid to vote in the process. ZKPs allow for doing this without needing a central authority to attest to the person's credentials. 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).
rtg4869 2y ago
This is a great explainer from one of the pioneers in this space, in case you weren't already familiar with it: https://www.wired.com/video/watch/5-levels-zero-knowledge-proof https://www.wired.com/video/watch/5-levels-zero-knowledge-pr...
badsandwitch 2y ago
It is currently possible to use ZKP's to set up via a central authority a digital cash system where the bank notes are all anonymous and all transfers are anonymous. 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.
- satchel888 2y ago
  [dead]
- ironSkillet 2y ago
  Do you have any recommended references on this subject? Seems like this sort of system would be able to obfuscate a lot of metadata that can be used to deanonymize activity. Very interesting.
  - badsandwitch 2y ago
    Tornado Cash does this. And you can find articles on how it functions online. You can even read the smart contract that directly implements 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.
jlokier 2y ago
For me, the most powerful use of ZKPs is proof of the output of general purpose computations of any kind. 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.)
- dataflow 2y ago
  > 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. > 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.
  - lifeinthevoid 2y ago
    As far as I understand, you can't just use any gcc binary as it exists today. The program needs to be represented as a specific, mathematical expression that is suitable for zero-knowledge proofs.
shriphani 2y ago
Examples of things you can do with ZKPs: - 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.
- rtpg 2y ago
  in your first example, how does Signal route messages in that model?
  - shriphani 2y ago
    sender specifies recipient but the signal server cannot tell a group-chat message from a non-group chat message.
    - rtpg 2y ago
      so in this world signal still knows I'm sending to N recipients? Or is the fanout happening in a different way? I guess I'm wondering if Signal still basically has enough info to make good guesses at group existence.
      - shriphani 2y ago
        Yeah I think you are correct that the protocol isn't safe from traffic analysis.
eru 2y ago
I come from a traditional finance background. One underappreciated possible role for ZKP is in compliance. 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.)
- gbasin 2y ago
  I am building in the mortgage origination space and have these sorts of enhancements on the drawing board... you hit the nail on the head that the bottleneck will be in QC and legal review, as 3rd-parties (especially regulators) may want to manually see the data you used to reach the conclusions you did. Although I'm still digging. You'd be interested in what we're creating btw, it's a crypto-based mechanism that enables instant digital mortgage origination, we should chat!
  - eru 2y ago
    Sounds interesting! I have an email address in my profile.
p1necone 2y ago
I can see applications in multiplayer gamedev - imagine being able to run the whole game simulation on a clients machine and have them assert back to you that they killed 7 goblins, looted a rare sword from a chest, and died 3 times - and you could just trust them. 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.
- k__ 2y ago
  In theory that sounds awesome and I love the idea of ZKP. However, they have quite some overhead that defeats such applications, I think.
  - _alex_ 2y ago
    Yeah prover time is the big challenge rn
- jlokier 2y ago
  I agree. Exploring this in game worlds came up in a job interview a few years ago :) 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.
  - p1necone 2y ago
    It would be amazing to have a single authoritative server in an mmo for the EU, USA, Asia, Oceania etc regions and only have bad latency if you were actually directly interacting with people from far away.
ruuda 2y ago
A toy example: suppose we have some sudoku. You want to show publicly (maybe in a HN comment) that you know the solution, without revealing the solution itself, because then anybody would know it and be able to post that they know it. A zero-knowledge proof enables this. You could also post a hash of the solution, but then you need to know the solution already to verify a submission. (It would also enable others to copy your answers without really knowing the solution, though that can be fixed using a technique that zero-knowledge proofs also use, a blinding factor). 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.
- sshine 2y ago
  One place I wish there was zero knowledge proofs involved, or even any kind of cryptography, is when you perform credit assessment for loans outside your bank: an external loan provide peeks at your full bank account history to assess whether you’re eligible. They don’t need to know where I buy my socks, or even how much money I have. Only that I have a big enough deposit and a steady enough cashflow.
  - edf13 2y ago
    Where you spend can have an impact on a decision… e.g. you may have the income and savings but if you’re regularly spending on gambling that can be a red flag.
    - hbbio 2y ago
      You can prove that too with zk!
      - rrr_oh_man 2y ago
        How could this look like?
oytis 2y ago
Judging by job openings mention ZKP it's mostly used in some "crypto" BS.
- AlchemistCamp 2y ago
  Blockchain development has spurred research that’s more broadly applicable in a number of cases and ZK proofs are one of the more exciting ones!
miki123211 2y ago
Good (non-blockchain) use cases include: - 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.

nailer 2y ago

> We can take a digital identity card and prove that we are over 18 years old > Without revealing anything else, like your full name or address 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.

piotr93 2y ago
A signature is a zkp. So your example is also a good example :)
- somezero 2y ago
  A signature is a PoK, but not ZK.
  - piotr93 2y ago
    I was not clear enough, thanks. Whether it is a pok or zk depends on the chosen signature scheme. In any case, zk signature schemes exist and are implied by the existence of one way functions and publicly verifiable nizk
    - somezero 2y ago
      > zk signature schemes exist and are implied by the existence of one way functions and publicly verifiable nizk. 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-digital-signatures-to-prove-identity-a-zero-knowledge-proof/35185#35185 https://crypto.stackexchange.com/questions/35177/is-using-di...
gchaincl 2y ago
I think the goal of this is that you can prove, so that your counter party does not need to rely on trust

sshine 2y ago

Another demonstration of Zero-Knowledge Proofs: A paper-tech protocol for validating Sudoku solutions without revealing the solution: https://zudoku.xyz/ https://zudoku.xyz/

saboot 2y ago
That's very cool! Here's another cool application for nuclear arms control, https://www.nature.com/articles/nature13457 https://www.nature.com/articles/nature13457
patrulek 2y ago
So with ZK-proofs we may never be 100% sure something is true or not? Is it possible that this may be too computational expensive to have certainty at given (or above) level?
- plopilop 2y ago
  You don't necessary get 100% certainty but the probability of success increases exponentially with each new run. Thus you can get very fast to a probability smaller than you quantum tunnelling through a wall
- drdrey 2y ago
  It’s the same thing as regular cryptography, I can’t be 100% sure that you signed this message but I can get arbitrarily close, and prohibitively expensive to fake
- TimJRobinson 2y ago
  Yea it's the same as a hash collision, maybe they managed to type some other message that hashes to the same thing but it's very unlikely. You can also use multiple different types of ZK proofs for the same data, same as using multiple hashing algorithms, for more certainty.
- sshine 2y ago
  > we may never be 100% sure Right, but we may be 99.9999999999% sure.

cyberax 2y ago

Are there any real uses of ZKP outside of blockcrap?

knowaveragejoe 2y ago
There's several already shown in the comments.
- cyberax 2y ago
  I'm asking about real actual examples, not handwaving.
  - eru 2y ago
    They are useful from a mathematical point of view. (And explore the relationship between P and NP, for example.) Not sure if that counts as a 'real use' to you. See also https://en.wikipedia.org/wiki/PCP_theorem https://en.wikipedia.org/wiki/PCP_theorem 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 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.)

Uptrenda 2y ago

What does everyone think about the 'trusted' setup part of zero-knowledge proofs? Is this a deal breaker for some use-cases or can this phase be done without worrying that the entire process has been hijacked... As has been a core goal of many ah... 'security' councils in the past.

Ar-Curunir 2y ago
Only some kinds of ZKPs have that drawback; others don’t. There are many examples of such systems with transparent setup that are used in practice. 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.
- JanisErdmanis 2y ago
  The multiparty setup is better than a singular-party setup, but it burdens its deployment. How can users be confident of at least one party they can trust whose preferences vary? Further, how can deployment be made so that a malicious party does not sabotage the setup process or is sabotaged by the organiser or network failures? In other words, who would need to be blamed? Doing these things properly makes the process’s deployment significantly more expensive than centralised deployment. Hence, I don’t see them bearing any practical relevance, as any authority that organises their deployment would also be subject to cost optimisation due to human nature and as security can’t be quantified, it suffers first. 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.
  - Ar-Curunir 2y ago
    There are logarithmic-sized proofs with transparent setup for arbitrary computation. These are much better for practically-minded people than ZKPs for ad-hoc computations because you don’t have to be a cryptographer to figure out how to use them

jmakov 2y ago

Can I prove that I'm a part of an org and use this as SSO?

k__ 2y ago
Yes, but in that specific example you could also simply use a signature, as the fact that you are part of a single org reveals all information. 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.
TimJRobinson 2y ago
Yea you can prove you're some set of users without revealing which one. 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.

zero_k 2y ago

If you wanna do it in a flexible way that is very easy to use and essentially the future of ZK, use Powdr [1]. Just write your code in rust nostd and be done with it. It's a compiler, basically. Once you use it, you'll never go back to hand-massaging polynomials. It'd be like writing assembly. Sure, some can do it, and it can be fun, but why do it if there are compilers out there to do the heavy lifting for you? :) [1] https://github.com/powdr-labs/powdr https://github.com/powdr-labs/powdr

k__ 2y ago
For Rust, there is also Sunscreen. https://github.com/Sunscreen-tech/Sunscreen https://github.com/Sunscreen-tech/Sunscreen
worldsayshi 2y ago
You sound like you are routinely doing zero knowledge proofs. To me it sounds like a very niche thing. What kind of application area needs knowledge proofs on the regular? Finance?
kikimora 2y ago
How about verification speed? The article mentions that avoiding trusted setup would result is sliver verification speed. Could it also increase proof size?

IWeldMelons 2y ago

The language they use looks surpisiningly like Verilog.

shae 2y ago

I recommend the moon math manual, it's a good way to learn this.

WanderPanda 2y ago

This is one of these technologies that is indistinguishable from magic.

deleted 2y ago
[deleted]
65n56n 2y ago
Doesn't this open up the way for proof of proofs as well? Maybe math is just the science that describes magic. It is indistinguishable from magic because it is magic.

bschmidt1 2y ago

I wrote ZKPs off as hype ~2 years ago - is it a legit concept outside blockchain marketing? Someone help me understand how it's different from hashes and access tokens? > "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?

somezero 2y ago
It’s all just bytes and hashes and alike at the bottom. Absolutely nothing magical. It is the abstractions over them that makes them esoteric, not the fundamental building blocks. 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.
magicalhippo 2y ago
The previous article[1] goes a bit into the difference from a simple has function. 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-knowledge https://zkintro.com/articles/friendly-introduction-to-zero-k...

baby 2y ago

If people are interested in trying ZKPs you can write programs in noname[1] in the noname playground[2] and have them compiled down to circuit and also prove/verify them. It's mostly a demo but the language is actively being developed and there's a list of easy tasks to pick up on in the main repo. [1]: https://github.com/zksecurity/noname https://github.com/zksecurity/noname [2]: https://noname-playground.xyz/ https://noname-playground.xyz/