Opening up ‘Zero-Knowledge Proof’ technology
123 comments
·July 3, 2025bobbiechen
Anyone have a good explanation on the intuition of non-interactive zero-knowledge proofs? For example, I thought the "paint-mixing" analogy for Diffie-Hellman key exchange (https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange#Ge...) really helped me handwave the math into "mixing easy, unmixing hard".
https://blog.cryptographyengineering.com/2014/11/27/zero-kno... was a good intro for interactive ZK proofs but I haven't been able to find something for non-interactive ones.
This blog post comparing ZK-STARKs to erasure coding is in the right flavor but didn't quite stick to my brain either: https://vitalik.eth.limo/general/2017/11/09/starks_part_1.ht...
JanisErdmanis
An intuitive explanation is that of proving you can find Waldo in a picture without revealing his exact location. Digital wallets can be interpreted as fancy signature schemes that operate on third-party issued commitments C instead of public keys that directly link users to their identities.
A simple signature scheme is based on proof of knowledge PoK{x : pk = g^x}, which is transformed into a noninteractive variant via the Fiat-Shamir transformation, where the message is appended to the hash. Range proofs work similarly, with the simplest form being for a single bit: PoK{(b,r) : C = g^b * h^r & b(b−1)=0}. This proves that commitment C contains a bit b in {0,1} without revealing which value it is.
Arbitrary ranges can then be constructed using the homomorphic properties of commitments. For an n-bit range, this requires n individual bit proofs. Bulletproofs optimize this to O(log n) proof size, enabling practical applications.
The commitment C can be issued by a trusted third party that signs it, and the user can then prove certain properties to a service provider, such as age ranges or location zones (constructed from latitude and longitude bounds).
A key challenge is that reusing the same commitment C creates a tracking identifier, potentially compromising user privacy.
deegles
for explanation i've seen for the where's waldo analogy: imagine the single page of the where's waldo puzzle, and another giant piece of paper with the shape of waldo cut out of it.
by providing a picture of waldo in the cut-out, you can prove you know where he is without providing the location. a zero knowledge proof.
yababa_y
everyone in this thread needs to read this paper: https://dl.acm.org/doi/abs/10.1145/3411497.3420225
Where’s Waldo as presented isn’t even a proof of knowledge
goopypoop
Is that "Draw a Waldo with this outline"?
pinoy420
[dead]
null
tptacek
If you're looking for something at the level of paint cans, I think you want Matthew Green's "crayons and hats":
https://blog.cryptographyengineering.com/2014/11/27/zero-kno...
remram
That's only for interactive proofs though. Like GP I have no problem understanding those.
abhv
My colleague Amit made a simple video explanation about zkp with Wired. https://youtu.be/fOGdb1CTu5c?si=EyBQS92WyeduIpH-
That doesn't explain the way this scheme works, but it's a nice start.
JW_00000
This is what I was going to post. It helped me a lot by first giving a very intuitive understanding of the concept of ZKPs using the Where's Waldo/puffin-among-the-penguins example, but then also going deeper with the graph-coloring example.
supernikio2
"The Ali Baba Cave" example from the Wikipedia article is what made it click for me: https://en.wikipedia.org/wiki/Zero-knowledge_proof.
bobbiechen
This is an interactive example, isn't it? It doesn't help me understand non-interactive proofs like SNARKs/STARKs, where the verifier isn't communicating live with the prover.
quantumgarbage
Look for the "Fiat Shamir heuristic" to understand the non interactive part.
It basically consists in the prover getting its random challenges from hashing public inputs, rather than from the verifier's coin tosses.
coldpie
Yeah I'm also interested in some of the details here, but the linked library repo is a bit too low-level for my current understanding.
For example, in the usecase of providing a proof-of-age to a website: who provides the verification data (the government?); what form does that take (a file in a standard format?); who holds/owns the verification data (the user?); who runs the verification software (the end-user's web browser?).
Can the user use any implementation to provide the proof, or must it be a "blessed" implementation such as Google Wallet?
abhv
(1) in this case, an identity issuer provides the source of truth identity information. Examples include state DMV, your passport (you can try "Id pass" in Google wallet), etc.
(2) One of the goals of this project was to layer ZK on top of current identity standards that DMVs already issue, so that gov orgs don't have to change what they currently do to support the strongest user privacy. One example format is called Mdoc.
(3) The user holds the identity information on their device only. No other copies. The user's device makes the zkp proof on-device. This was one of the major technical challenges.
(4) The relying party (eg a website) runs the zk verification algorithm on the proof that is produced by the device to ensure soundness.
(5) Yes, the user can use any compatible implementation to produce the proof. We have open-sourced our implementation and we have a spec for the proof format that others can also reimplement.
miki123211
If you can achieve RCE on the chip and run arbitrary code without invalidating signatures, does the protocol still stay secure?
If so, what's the point of requiring your implementation to run on a verified secure element? If not, the protocol seems only as strong as the weakest chip, as obtaining just a single private key from a single chip would let you generate arbitrary proofs.
coldpie
Thanks for the reply. So in theory, I could get this MDOC file and store it on my desktop computer, and use an open-source library whose behavior I can verify, to provide the proof to the website via my web browser. Yeah? This sounds good to me.
doctorpangloss
Are you trying to say that there’s a signed blob called an MDOC, that happens to have the age and name of the user, and this library allows a website to prove that the provided age belongs to the person with the MDOC, but not also see the name?
MatteoFrigo
The specifics depend on local regulations, but roughy speaking: the government gives you a document in a standard format (eg MDOC). Your phone stores the document, with cooperation from a secure element that binds the document to the phone. The website you visit verifies the proof. The government gives documents to whatever wallet they want, which may be a special government wallet. They may or may not give the document to Google Wallet.
coldpie
Thank you.
> Your phone stores the document, with cooperation from a secure element that binds the document to the phone. The website you visit verifies the proof.
So it does require a "blessed" implementation, and I have to trust Google or Apple to handle my data? I cannot own the document myself and use an open-source client that I trust to provide the proof?
esbranson
It is decentralized. The holder provides the data, which was ultimately provided to them by the government, they're the client. The verifier is the entity that wants to know how old the holder is, the server.
The form are eg things like the JSON Web Token (JWT), Digital Credentials, and the Federated Credential Management API (FedCM).[1][2][3][4][5] The software can be anything since they're expected to use open protocols, so yes, web browsers.[6] Per the Commission, "For remote presentation flows, … the Wallet Instance implements the OpenID for Verifiable Presentation protocol OpenID4VP in combination with the W3C Digital Credentials API."[7]
[1] https://en.wikipedia.org/wiki/JSON_Web_Token
[2] https://github.com/w3c-fedid/digital-credentials
[3] https://w3c-fedid.github.io/digital-credentials/
[4] https://github.com/w3c-fedid/FedCM
[5] https://w3c-fedid.github.io/FedCM/
[6] https://github.com/w3c-fedid/FedCM/blob/main/explorations/HO...
[7] https://eu-digital-identity-wallet.github.io/eudi-doc-archit...
noman-land
There's a Where's Waldo explanation that I can't find right now but helped me a lot.
rrakow
You want to prove to everyone that you know where the Waldo on Page 12 of Where's Waldo In Iceland, so you hold a big white sheet of paper with a hole in it in front of the page such that the hole is centered on Waldo. Then you let your friend see. Your friend now knows that you know where Waldo is, but they still don't know where Waldo is, because they don't know the relative position of the book under the sheet. This is also why they can't use your proof to falsely prove to anyone else that they know where Waldo is too.
krunck
Age assurance will be the gateway to government issued(via corporate proxy) internet usage permits.
jjmarr
Not necessary, Uganda has been levying social media taxes on end-users since 2018 by automatically adding it to your cell phone bill if you access a social media website. About 2.7¢ per day of usage.[1]
Virtually everyone gets their internet from an ISP that is regulated in the country that the user lives in. There are no technical barriers to implementing a permitting system in the United States.
Linking connections to real people is self-enforcing when there is a usage-based tax.
[1] https://www.africanews.com/2018/04/13/uganda-s-social-media-...
regularfry
Do you happen to know what the answer of this scheme to "I have a wireguard connection to another country, you can't see my traffic" is? I know that enough of the population would never bother so it wouldn't significantly harm it as a revenue scheme, but if your goal is avoiding identification rather than taxation then the stakes could be high enough to make the effort worthwhile.
gmueckl
The political answer to circumventing laws is usually some form of punishment. This is often much easier than weird technical solutions.
miki123211
> enough of the population would never bother
People have bothered with downloading low-quality Mp3s from Napster, figuring out video codex and modding game consoles to get free video games. If the need is dire enough, the users will figure it out, no matter how high the friction is.
Those with enough technical chops will figure out how to do it by themselves, those with enough intelligence will find resources on the internet, the rest will ask a friend or pay a local IT person to get it set up for them.
heavyset_go
> Do you happen to know what the answer of this scheme to "I have a wireguard connection to another country, you can't see my traffic" is?
WG traffic is easily identifiable and able to be blocked, it's what happens in countries that ban VPNs.
wat10000
Tying usage to connection seems feasible, but age verification (and the hypothetical usage permit) is trying to tie usage to a specific person. You could probably pretend they correspond 1:1 for cellular, but what about wired connections to households with more than one person living in them?
kridsdale1
VPN or TOR?
perching_aix
And maybe also uniquiness guarantees, so that people can finally stop debating whether the internet is "dead"?
api
True, but I'm also not convinced that a ten year old being able to be face to face with hard-core BDSM and incest fetish porn within 40 seconds of opening a web browser is healthy.
I don't like this but don't have another solution other than the porn industry self-policing which isn't promising.
djoldman
For kids with a guardian, the answer is enabling and empowering the guardian to control what the child can access.
Somehow we've inappropriately shifted responsibility away from parents/guardians in some areas like internet access.
In other areas, like letting your kid go outside by themselves, we've criminalized reasonable caregiver actions.
It's a wild world.
trollbridge
Isn’t that the same argument as “Parents should keep kids away from cigarettes” by tobacco companies who were simultaneously marketing to children?
And parents aren’t in control of children 24/7. Schools tend to provide tablets and laptops everywhere, and how much trust should parents have that things like a content filter are adequate to keep children from asking objectionable pornography, hate sites teaching misogyny and so forth?
koalaman
Another way of looking at it, is that when you put the responsibility of protecting a child from harmful content on the parent, you're deciding to only protect the children with the right kind of parent.
mystifyingpoi
Well, you don't have another solution. That doesn't immediately mean that the one presented in the post is the correct one. Far from it.
MatteoFrigo
The post does not present a solution to that problem. Governments around the world, especially in Europe, have legislated the solution, and the solution they have picked is a privacy nightmare. This post solves the privacy problem, which is strictly better than the status quo. We (Google) do not decide what should or should not be regulated.
null
rvnx
Now take an intentionally extreme opposite (as a thought experiment): if we put death penalty to people who participate in distributing or in relaying such content, could all of that be solved without the “internet pass” and IDing your internet history ?
wbl
You mean like the SF city government? This is stuff that a lot of people enjoy doing and taking photos of. The headquarters of a lot of startups are in what used to be the leather neighborhood.
treyd
Maybe, but even this is broken with the internet being international. You'd need a system much more advanced than even the GFW.
api
Adults should be allowed to look at porn. I don't think it's necessarily good for people, but adults are also allowed to binge drink and smoke and eat ultra-processed foods and a lot of other things that are worse for you than porn.
CP is an edge case but that's because it's almost impossible to make CP without abusing children and you could view CP as an incitement to violence -- as incitement to abuse children.
Parents should ultimately monitor what their kids do. I have a pi-hole that subscribes to lists with millions of porn domains, but I'm a technical person. Non-technical parents are helpless, and kids can easily access it at friends' houses etc. The industry has not empowered non-technical parents to do this, probably because there's a conflict of interest. Lots of parents would use such options to keep kids off social media, and like all addictive things social media wants to hook them early. (I think kids should be off social media too, but it's not quite as nuts as letting them watch fetish porn.)
Porn is different now too. It's worse in a way. Like everything else it's subjected to a pressure to get "edgier" to maximize engagement. So today's porn is loaded with simulated incest, simulated rape, extreme BDSM, etc., things that young children are not equipped to properly contextualize. (Some adults aren't either, but at least with adults you can say it's their fault not the porn's fault. The line cuts differently with children which is why children can't smoke, get tattoos, buy alcohol, get credit cards, etc.) If you want to see the consequence of young kids (mostly boys) being raised with unfettered porn access go visit any women-coded space on the Internet (like Reddit) and search for threads discussing why so many men want to choke their girlfriends. Where did this sudden choking fetish come from?
add-sub-mul-div
Teen pregnancy rates are down since the mass adoption of the internet, a kid learning a few years early that there exist sexualities other than the default one will affect them much less than losing internet privacy and anonymity for life.
Spivak
What web browser are you using?! I think this says more about you than about the internet if this is what you're seeing.
natch
A world can be built on this. So many things are broken privacy-wise because we have to overshare our PII. SSNs for example.
Labo333
Very interesting in the context where major porn websites blocked access in France (now reverted) and in some US states as a response to age verification regulations that were too difficult to implement without compromising user experience and privacy.
Confiks
It's a very interesting solution that allows for multi-show unlinkability to be married to hardware binding using existing ECDSA hardware keys. It's not limited to age verification; it can be applied to arbitrary attributes.
It's also an unfathomably complex solution [1] which only a few people in the world will grok, and far more complex than existing solutions such as Idemix or BBS+, which lack such a hardware binding on existing hardware.
Age verification in a privacy preserving way is a really hot topic at the moment, but it will always be possible to bypass it – as will any commonly held anonymous boolean – in quite trivial ways. For example by setting up an open proxy to disclose genuine attributes. There are some privacy preserving mitigations, for example cryptography that'll make you linkable when disclosing more than k times per time period, or detecting slower-than-near-light-speed disclosure in a face-to-face disclosure scenario.
However, these mitigations will never be completely secure. That might not be a problem if it's admitted beforehand so expectations are correctly set: it's a barrier to protect the naïve, not an impenetrable fortress. However, if the expectations are that only age verification that cannot be bypassed is "adequate", we only have to wait for the first incidents in production apps after which the open source and privacy story will be abandoned in the name of security.
[1] https://eprint.iacr.org/2024/2010.pdf and https://eprint.iacr.org/2022/1608.pdf
MatteoFrigo
On the contrary, any undergraduate can understand our solution. In contrast, I don't know anybody who can explain the bilinear pairing in BBS.
wbl
I'm not sure sumcheck and MPC in the head are that easy for undergraduates. By contrast cup products are pretty standard in topology and that's where the pairing comes from.
Confiks
Perhaps "unfathomably" was too strong, but "any undergraduate" is at least very easy to falsify.
MatteoFrigo
Jokes aside, I really believe that once all is said and done our system is way simpler than BBS.
How are you going to check the document expiration date in BBS? Yes I know about range proofs, I know about the quaternion norms and the four prime theorem and all that jazz. But nobody is talking about it.
How are you going to bind to a hardware secure element that only uses NIST primes? Yes, there is a very clever variant called BBS# which I believe works, but that's not simple either.
How are you going to deal with existing standard formats? 80% of our complexity is in this step. BBS most likely cannot do it at all. If we can change the format then a lot of my complexity disappears too.
How are you going to deal with the fact that BBS signs an array and not a set, and thus you are leaking the fact that "family_name" is attribute at array index 42? Are you going to leak the schema (which re-introduces tracking) or are you going to agree in advance, now and forever, on a schema? (Our system hides the schema and works on an arbitrary key/value dictionary, up to a maximum size.)
It's easy to say "simple" when one has not built the real thing.
ChuckMcM
This is great. It really pissed me off when David Chaum locked all the cool uses of ZKPs behind a patent wall. The DigiCash folks were peak dot com greed types, their business model was "We're going to get big chunk of change out of every transaction ever so we should be valued at 1% of the worlds GDP!" And the world responded with "Yeah, no."
I really like Andy Birrells "micro-cents" which exploited the fact you could not easily reverse an MD5 hash so you one could cheaply do high confidence low value transactions at speed. Another idea that never got anywhere sadly.
ZKP ID cards and ZKP currency are both interesting things from the 90's I'd love to see in real life. Imagine I could pay you phone to phone with no network level of capability using a currency that couldn't be double spent. That was the promise of digicash. The government hated it :-). It was just like cash currency in that serial numbers could let you track the bank it left, and the bank it came back in to, but you couldn't track anywhere it had been between those two points.
Fun times. I'll have to see if some of my ZKP ideas can be built on top of this tech now.
coldpie
> This is great.
Do you still feel that way knowing that it introduces a hard requirement for all users to have their private data managed by one of Apple, Google, or Microsoft[1]? I want to be excited about this, and about Passkeys, but the people working in this space keep fumbling this ball :(
[1] "Using the MDOC requires a signature from a hardware security key in the phone" https://news.ycombinator.com/item?id=44458417
baby
For people interested in zero-knowledge proofs check https://news.zksecurity.xyz/ which is a hackernews but for ZK!
WXLCKNO
It's interesting how painful that design is to my eyes compared to the HN home page, I can't say why at a quick glance it's just hard to parse for some reason / doesn't feel good.
esbranson
Good. ZKP is a good way to handle decentralized identity proofs. We can imagine other uses of ZKPs with digital identity wallets, such as proving state political party affiliation for participation in independent e-democracy services without having to provide PII. Good on the Commission for following through on this, not sure we've seen much from them in the protocol space since ISDN.
vvpan
A cool technology that builds on ZK is zkTLS that can prove that you have access to some data on the internet, for example that you have an account with some service without revealing your username. So more private oauth I suppose?
dungeonsndregoo
A technical deep dive into how zkTLS works with MPC architecture: https://paragraph.com/@vinny/opacity-network-deepdive
baby
Great intro to how zkTLS works: https://blog.zksecurity.xyz/posts/zktls/
Sancty
I'm excited for this to be mainstream. OAuth is definitely a step in the right direction, but many times scopes are broader than they need to be and can be abused. AFIAK, zkTLS can provide derivate values; i.e "You are over 18" (T/F?) verse "Your birthdate is".
dop42069
It works for private user data in adversarial setting. Like the outcome of a rocket league match can settle a $20 bet. Showdown.win
TuretzkyRon
but the server side does not have to support it on their end for it to be used
tucnak
This is perhaps more important in the age of AI agents, but before we can tackle all these fancy ZKP constructs in the mainstream — we have to, as the industry (and so far consistently failed to) — implement Zanzibar, or whatever ReBAC, and maybe ZKP stuff could "sneak in" that way, in the form of zero-knowledge warrants, or whatnot. Unfortunately, even though it works consumption-wise, it's fundamentally at odds on the provider side.
The providers are clutching their OLAP like pearls! :-)
EulerLagrange
[dead]
mumbisChungo
A fun mechanism for guaranteeing privacy of information in competitive multiplayer settings that operate on distributed networks.
cyberax
This might enable something like Scroll (the pay-to-view without ads network, acquired and destroyed by Twitter) but anonymous.
0xOsprey
We're building a purpose built self-custodial payment rail using zero knowledge cryptography that could be leveraged for this use case: https://x.com/0x_Osprey/status/1925299005191577921 https://paygo.wtf/
Current benchmarks for proving costs are 33k txns per dollar and we expect this to go down x10-x100 over the coming months/years.
cyberax
Blockchain => trash
A system that can be trusted needs to work in the real world, with credit card payments, bank accounts, VAT.
weinzierl
Sparkasse is not a word I had expected in a post like this, but here we are.
The Sparkasse network is not very well known outside of Germany but is actually Europe's largest financial services group by assets.
What is interesting is that until the 90s the membership banks were public institutions backed by municipal and state guarantees that made them virtually bankruptcy-proof, unlike private banks. EU competition rules then forced Germany to phase out these state guarantees, making Sparkassen subject to normal banking regulations and deposit insurance like other banks.
null
https://github.com/google/longfellow-zk