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".
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.
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.
I think the Where's Waldo example, while not technically zero knowledge, gives a pretty good intuition of the idea behind it.
It certainly gives a "layperson" example of being able to prove you know something without revealing it, which isn't the whole definition of ZK but is the idea driving it.
Imagine it isn't Waldo, but an unknown figure and you are only given the silhouette to find. If you can draw what's within the silhouette or something, you've proven you've located it to high certainty without saying where.
Say the whole image looked like noise and was generated from quantum measurements, and the coordinates to hash for the problem were generated with quantum measurements, and you were given the silhouette and the hash of the noise within to look for. I could see it for proof of work: you could slide along a hashing window and prove you actually did work examining half the image on average or whatever.
I think my example isn't great and would need to be modified like maybe give the hash of a neighboring area to prove you found it, so your answer couldn't be used by others to find the location much more cheaply.
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.
* The prover commits to a starting value (public input)
* Instead of waiting for an interactive challenge, they hash it and use the resulting hash output as if it were a challenge
If we believe the hash is a random oracle (as we do for cryptographic hash functions), then it is hard for the prover to manipulate the challenges. Is that it?
You got it. There are a few nuisances, e.g. the "theorem statement" must be hashed as well so that proving that name=Mickey has a different oracle than proving that name=Goofy, but your basic understanding is correct.
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.
Was looking to see if someone posted this video. The first few interviews are excellent - the later ones, not so much (in terms of explaining ZK - they're good chats, of course).
Usually in an IP, the prover (Bob) has to answer questions from the verifier (Alice), and Alice chooses her questions by flipping a coin. If the Bob doesn’t really know the answer, he’ll get caught cheating with high probability.
So now the trick: Bob starts generates his initial answer. Then he hashes it (“commits” in the jargon), and uses the hash as “Alice’s first coin flip”. Then he answers the question for that flip, hashes the whole thing for “Alice’s second coin flip”… etc.
Bob does this say, 100 times, and then sends the whole simulated conversation to Alice. Alice can verify that he didn’t cheat by checking the intermediate hashes.
The whole thing depends on the ability to not control the result of the hash function, so it’s vital to use a cryptographically secure one.
It "feels" much easier to generate random non-solutions and check if the random questions happen to pass, though. Is it really all there is to it? You increase the number of questions to compensate and that's the whole scheme? Wouldn't the responses be a ludicrous amount of data?
Yes, basically. The hard work happens in constructing the interactive proof to ensure that you can’t reneg on the earlier steps.
All the proofs that I know of allow one to get lucky with probability about .5 in each round. When you do an interactive proof with 100 rounds, you have a 2^-100 chance of getting away with cheating.
When you go non-interactive with 100 rounds, an adversary could cheat by trying about 2^100 proofs. So you replace a stronger guarantee with a weaker one, but 2^100 is a pretty big barrier.
(I just looked and the Wikipedia page and it’s very confusing fwiw)
The trick is called the Fiat-Shamir transform, and you're right, it does require more questions to get an equivalent security level, precisely because you can try a large number of random non-solutions without anyone catching you doing it.
But the number of questions you need to compensate grows only a little.
For example, interactively if you ask for Merkle tree proof that selected leaf values have a particular property, you only have to ask for about k leaves to get probability 1-(2^-k) that you'd catch a dishonest prover who had committed a Merkle root with less than half the leaves having the property.
Non-interactively, a dishonest prover could secretly grind attempts, say 2^g times, and then you'd have a lower probability of catching them, approximately 1-(2^(g-k)). But g can't be all that large, so you can increase k to compensate without making the proof much larger.
You.can also require certain hashes to have a fixed prefix, like Bitcoin mining, forcing every prover to have to grind 2^p times. This reduces the effective g that a dishonest prover can achieve, allowing k to be smaller for the same security, so allowing the non-interactive proof to be smaller. At the cost of honest provers having to grind.
The surprising part of STARKS and SNARKS comes down to the nature of polynomials. It's surprisingly easy to tell two polynomials apart with a small number of random checks (Schwartz Zippel lemma). In light of this it's not surprising there is good reading comparing them to erasure codes which rely on exactly this property of polynomials.
The non-interactive piece is pretty straightforward you just simulate challenge response conversation with unbiasible public randomness and show the transcript (Fiat Shamir transform).
Another area worth exploring is how some of these proof systems can have such incredibly small proofs (192 bytes for any computation in groth16 zk snarks). That relies on the much more difficult to intuit theory of elliptic curve pairing functions.
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?
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.
> 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?
It depends on local regulations. As far as I can tell Europe will require some sort of blessing of the wallet. To be clear, governments will develop their own apps and it's not clear that Google will be blessed. We (Google) are giving them the code pro bono to improve privacy.
Hmm. This introduces a third party to the protocol, right? Specifically the developer of the wallet. So we now have three parties: the user, the wallet developer, and the relying party. Does this zk protocol protect the user's privacy from the wallet developer as well as the relying party?
In other words, does the protocol give the wallet access to information about the relying party? For example, could this wallet that I don't control tell its owner, or the government, that I am using it to access a certain website?
Yes, a malicious wallet could leak your information. This is why some governments will insist on using only blessed wallets. However, wallet+zk is strictly better than sending the plaintext MDOC to the relying party.
There are no solutions in this space, only tradeoffs, and elected representatives have picked one tradeoff.
That's too bad :( I wish the protocol had been designed with that in mind. Requiring users to trust proprietary software from Google & Apple to be in complete control over their digital identities is a pretty crummy direction to go in.
> Controlled by users: The EU Digital Identity Wallets will enable people to choose and keep track of their identity, data and certificates which they share with third parties. Anything which is not necessary to share will not be shared.
I think where the ZKP stuff being discussed here fails to meet this criteria is the wallet provider is also a third (non-user) party. You stated elsewhere that a malicious wallet could leak data about a transaction: that's exactly the vulnerability that is not being accounted for by this protocol.
> If you think you have a better idea shoot me an email.
Sure, will do. It does seem to me like a solvable problem. I think this kind of tech is really important and I'd love to see this hole get closed so I can feel better about supporting it.
Update: After some email discussion with Matteo, it looks like my fears are unfounded. The EU regulations seem to require wallets to be open source[1]. Assuming that wallets do not need to pass any sensitive transaction data down to the OS libraries, then it should be possible for users to verify the behavior of their wallet software by examining the source and possibly even by building & deploying it themselves.
In principle, you could use an open source implementation, but not a user-modifiable implementation.
Nothing stops a government from making their code open source and providing you with reproducible builds. You just won't be able to change the code to do something the government doesn't deem legal.
(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.
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.
The role of the secure element is only to "bind" the credential to the device, so that if you copy the credential somewhere else then the credential is useless. Concretely, the secure element produces a ECDSA signature that must be presented together with the credential. This is the normal protocol without ZKP. Concretely, the SE is in the phone, but could be a yubikey or something else.
The ZKP library does not run on the secure element. It runs on the normal CPU and produces a proof that the ECDSA signature from the SE is valid (and that the ECDSA signature from the issuer is valid, and that the credential has not expired, and ...) If you crack the ZKP library, all you are doing is producing an incorrect proof that will not verify.
Am I correctly understanding that I'd get the credential from say my state DMV once, and then later whenever I want to prove my age to a website the proof protocol is just between that website and my device? The DMV gets no information about what websites I use the DMV credential with and they get no information about when I use the credential even if the website and the DMV decide to cooperate? All they would be able to get was that at time T someone used a credential on the site that came from the DMV?
I tried to sketch out a design an age verification system, but it involved the DMV in each verification, which made timing attacks a problem. Briefly the website would issue a token, you'd get a blind signature of the token from the DMV's "this person is 18+" service, and return the token and unblinded signature to the website. I think that can be made to work but if the site and DMV cooperated they would likely be able to unmask many anonymous site users by comparing timing.
Getting the DMV out of the picture once your device is set up with the credential from them nicely eliminates that problem.
You are correct. The property that the colluding website and DMV still cannot identify you is called "unlinkability" and as far as I can tell cannot be achieved without zero-knowledge proofs. See https://github.com/user-attachments/files/15904122/cryptogra... for a discussion on this issue.
However, the timing attack resurfaces once you allow the DMV to revoke credentials. Exactly how the revocation is done matters. We are actively pushing back against solutions that require the DMV to be contacted to verify that the credential has not been revoked at presentation time, but this is a very nuanced discussion with inevitable tradeoffs between privacy and security.
>> The DMV gets no information about what websites I use the DMV credential with and they get no information about when I use the credential even if the website and the DMV decide to cooperate?
> You are correct. The property that the colluding website and DMV still cannot identify you is called "unlinkability" and as far as I can tell cannot be achieved without zero-knowledge proofs.
Well, no. This is true only if you trust the unverifiable wallet software on your phone, which was provided by a for-profit, American big tech advertising company. In this protocol, the wallet may secretly leak the transaction details back to the DMV or whoever else they wish[1].
MatteoFrigo is suggesting that unlinkability requires ZKPs.
Your observation that a bad wallet could compromise unlinkability is not a refutation of that. To refute it you need to show that it is possible to achieve unlinkability without using a ZKP.
One part that I don't understand yet: How does the system ensure "sybil resistance"? (not sure if that's the right term in that context)
By providing both attestation of individual attributes combined with "unlikability", how would even a single verifying party ensure that different attestations don't come from the same identity?
E.g. In the case of age attestation a single willing dissenting identity could set up a system to mint attestations for anyone without it being traceable back to them, right? Similar to how a single of-age person could purchase beer for all their under age friends (+ without any feat of repercussions.
Great question. The current thinking, at least in high level-of-assurance situations, is this. The identity document is only usable in cooperation with a hardware security element. The relying party picks a random nonce and sends it to the device. The device signs the nonce using the SE, and either sends the signature back to the relying party (in the non-ZKP case), or produces a ZKP that the signature is correct. The SE requires some kind of biometric authentication to work, e.g. fingerprint. So you cannot set up a bot that mints attestations. (All this has nothing to do with ZKP and would work the same way without ZKP.)
In general there is a tradeoff between security and privacy, and different use cases will need to choose where they want to be on this spectrum. Our ZKP library at least makes the privacy end possible.
That seems a bit like a game of whack-a-mole where as long as the forging side is willing to go further and further into out-of-hardware emulation (e.g. prosthetic finger on a robot hand to trick fingerprint scanners), they are bound to win. Biometrics don't feel like they hold up much if you can have collusion without fear of accountability.
> Our ZKP library at least makes the privacy end possible.
Yes, that's also one of the main things that make me excited about it. I've been following the space for quite some time now, and I'm happy that it becomes more tractable for standard cryptographic primitives and thus a lot more use-cases.
Thanks for your contributions to the space and being so responsive in this thread!
No. ZK has a technical definition I don't want to get into, but note that the described system is deterministic and it always produces the same proof for Alice on a given day, and the proof for a later day can be derived from the proof for an earlier day. So two proofs can be linked back to Alice, and thus the system is not ZK. You need some kind of randomness for ZK.
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.
No. Using the MDOC requires a signature from a hardware security key in the phone, and a lot of the complexity is how to avoid leaking the private key, which would identify you.
An alternative would be some secure chip in a credit-card size plastic document, but nobody seems to like that idea. We (Google) don't make these choices.
Another approach could be for a component in the protocol that I do trust (eg an open source web browser) to serve as an intermediary, providing only the information required to each of the components that I don't trust (wallet, website). The wallet does not need to know who is requesting the proof, right?
I hear you. The main problem is how to prevent you from giving your document to somebody else, and things have converged on certified smartphone with security key plus biometrics.
Yeah, Passkeys are doing the same thing, expecting users to just blindly trust American Big Tech companies. It's distressing that no one working on these protocols considers the developers of the software that implements the protocol to be a party in the protocol. What are the wallet provider's interests in this exchange? How can the user be protected from the wallet provider? Seems no one asks these questions :(
Anyone can implement passkeys. The feature where passkeys can be made to attest to the hardware provider is optional and no site I've used requires it. Firefox defaults to not allowing passkeys to attest to the hardware unless you click through a permission dialog.
I don't want to get into a Passkey derail, but no. The Passkey spec requires clients to handle the user's own data in certain ways, and the Passkey spec authors threaten clients that allow users to manage their own data with client bans.
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?
But to be clear, mdoc already accounts for this through its selective disclosure protocol, without the need for a zero knowledge proof technology. When you share an mdoc you are really just sharing a signed pile of hashes ("mobile security object") and then you can choose which salted pre-images to share along with the pile of hashes. So for example your name and your birth date are two separate data elements and sharing your MSO will share the hashes for both, but you might only choose to share the pre-image representing your birthday, or even a simple boolean claim that you are over 21 years old.
What you don't get with this scheme (and which zero knowledge proofs can provide) is protection against correlation: if you sign into the same site twice or sign into different sites, can the site owners recognize that it is the same user? With the design of the core mdoc selector disclosure protocol, the answer is yes.
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]
The explanation that one person gave me was basically that you use an RNG to generate the challenges. Not sure if this is quite "proper", but it makes sense to me so long as you can't game the system. Perhaps make the RNG slow to prevent picking a convenient sequence?
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.
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.
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.
Indeed. Governments have to worry about 99.9% of cases covered with a law or regulation have punishment in term of fine or imprisonment.
Those remaining very likely have multiple advantages like advance technical knowledge, connection to powerful people in business / governments, money and legal support in case they end up on wrong side of law. There is very little benefit and lot of effort to catch these unless they are running some kind of criminal organization which adversely affects their government/regime.
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.
Shadowsocks is detectable using entropy analysis but not everybody does it. I heard in China they do. you connect at first they collect data, analyze and ban. in Russia they are not that smart yet but in Russia even if you mask VPN traffic they use other tricks. For example if you visit any state adjacent site from your Russian IP and VPN with same cookies they can ban VPN exit node. Or if all your traffic goes to one IP they will probe ports or just ban that.
I think the answer is that it's likely illegal if someone can prove an intent to defraud or commit a theft of service, but the chances of getting caught may be small depending on your technical ability/OPSEC.
Yes, but is that what happens in this specific case? There are enough legitimate uses of VPNs that blocking them solely in case people wriggle out of social media taxes would be extremely heavy-handed.
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?
Today it's age gating porn, but the next move will be age gating sites that talk about LGBTQ issues by moving the 'obscenity' definition to be anyone they don't like. Left to their own devices and unopposed, they'll declare discussion of birth control and interracial marriage to be adults-only.
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.
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?
> Isn’t that the same argument as “Parents should keep kids away from cigarettes” by tobacco companies who were simultaneously marketing to children?
I think most would agree that there's a significant difference between a physical product that shortens the lifespan of virtually all humans who use it, and looking at images and video, no matter how extreme.
> 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?
Agreed.
Parents and guardians should definitely be aware of and concerned about what internet filters are in place at schools.
> Parents and guardians should definitely be aware of and concerned about what internet filters are in place at schools.
Neither of the words you used give parents any control over the situation. Legislation is the circumspect way parents are exerting control over websites that are unable to police themselves.
I do agree there is a significant difference. The images and video are much worse -- one particularly bad video can scar people for months, even years, one cigarette isn't that bad.
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.
I'm fine with that. I'd rather parents make "bad" decisions about protecting their own children than the government forcing their own opinions on them.
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.
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.
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 ?
Somehow this work when dealing with pedophile content, so the tech is already active.
For example, on Discord, all your messages are scanned for such. On Cloudflare as well (for over 5 years).
For now it means they have no interest to remove such content unless coerced or affected by the public opinion.
This would destroy all content though, not just for minors.
Absurd, but it works, in North Korea (death penalty), Iran (death penalty), China (10 year prison), and also protects victims from rape, or "rape" under financial pressure.
The alternative is to let responsibility of the parents to install web filter to their kids, and let others live freely on the internet, without sharing their history or IDing them.
In reality, TikTok also has really traumatizing content, yet is engaging tons of kids and teenagers, and IDing won't solve that, but good parents can.
I agree, that does work, but there are parameters which are different that make it worth the tradeoff to police it that strongly, like the size of the audience and the much more severe real harm caused by its production and distribution.
I just pushed this idea as a "solution" to see what others think, but I don't know. Again perhaps educating the parents about how to educate kids about the dangers of internet, and perhaps a web filter for kids.
This is actually one place where AI could be useful, to do dynamic local content classification (instead of a blocklist), especially if integrated directly in Android / iPhone.
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?
Reddit being considered a space for women is the funniest take I've heard in a while. But regardless, you didn't adequately take into account that being choked is one of the top sexual fantasies of women. Whatever explanation you put forth has to also explain why it's also highly desirable to be on the receiving end.
The "porn has been giving men violent sexual fantasies" line has existed since before I was born but it always ignores that they're the top fantasies among women too. Among my friend group the more common refrain is women who want to be choked but their boyfriends are uncomfortable doing it.
I agree with you, at the end I think it could work if we offer to promote better local solutions (e.g. better tooling on iPhone), rather than the server authenticating the user.
Perhaps find a way to force Windows / Android / iOS to include such "firewall"/webfilter by default.
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.
- Buys or borrows a laptop / phone / whatever from somebody with an authorized private key
- Downloads an authorized private key file from a sketchy forum (maybe hacked from an unwilling target, maybe willingly shared by a free-speech advocate)
- Uses a VPN over HTTPS to visit websites in countries where age checks aren't legally mandated (and non-compliance is implicitly or explicitly encouraged for economic or ideological reasons)
The credential ("driver's license") contains a public key whose secret key is stored securely in a hardware secure element. The standard assumption is that the SE is in the phone, but it could be a yubikey or similar device. In order to use the credential, you need the SE. So you cannot buy a phone from somebody and download a credential from somebody else. You can however buy a phone and the credential from somebody. As a mitigation, the SE only generates the signature when unlocked via a fingerprint or similar biometric input which must match the one that was provided at the time the credential was issued. Whether or not your attack works in this scenario depends on the details. For example, if you only obtain the credential in person at a local government office and provide a fingerprint at that time, it's not that easy to sell the phone and the credential afterwards.
The problem that needs to be solved is, how can a government give you an identity document in a way that you cannot give the document to somebody else. Whether or not this problem needs to be solved is a political question, but it seems like the majority thinks that identity documents should be hard to forge, in the same way as dollar bills should be hard to forge. The only practical solution is to have some sort of hardware that the user cannot forge, and relying parties will insist that the document be bound to such hardware. So yes, the something else could be software, but nobody will accept signatures from an emulated TPM. I had in mind a government-issued yubikey that can be identified as such, or maybe a plastic card with embedded secure chip with the same functionality. See https://github.com/eu-digital-identity-wallet/eudi-doc-archi... for the current thinking at least in the EU.
I should also remark that the above is a western-centric perspective, whatever "West" means. For example, I heard the architect for a similar system already deployed in India remark that in his jurisdiction many households share one phone across many family members, and India chose to accept more possibility for fraud in exchange for wider usability by the population. In that context this choice looks like the correct solution.
It’s more about the device being tamper resistant than “hard to forge”. You don’t want people playing around with the device generating signatures. Algorithmically, there is nothing done on a secure element that can’t be done with software on a general chip. The defining difference is the physical separation of data and the mechanisms put in place to brick the device on detection of physical tampering.
You do not. These measures are targeted against law-abiding and productive citizens to control them further. The other ones (the top 0.1% or the bottom 20%) are uncontrollable anyway.
In the future, you'll need a signed certificate with your PII/KYC to access the internet and get an IP address. China is already on the way there and the west is warming up to this approach.
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.
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 :(
You can have a password manage your passkey private data. Several now have passkey support, including some that work on Linux such as 1Password and Bitwarden letting you use passkeys even if your household is completely Apple-free, Microsoft-free, and Google-free.
> To be very honest here, you risk having KeePassXC blocked by relying parties
Even if the bigtechs don't "officially" make the passkey standards require bigtech involvement, it seems very likely to me that conservative businesses like banks will only accept bigtech implementations. And then you're sunk.
Similarly, look at how OpenID turned into "Sign in with AppleGooFaceSoft".
This ZKP+hardware secure element stuff seems even worse, because how are you going to make it work on old hardware, or with free software, or with open devices?
> Even if the bigtechs don't "officially" make the passkey standards require bigtech involvement, it seems very likely to me that conservative businesses like banks will only accept bigtech implementations.
> This ZKP+hardware secure element stuff seems even worse, because how are you going to make it work on old hardware, or with free software, or with open devices?
I don't love it, but I actually do see an argument that this kind of proof-of-property stuff really does belong in a secure area, backed by approved software. It is making government-backed, legal claims about a person or entity. Unlike with Passkeys, it's not really "your" data, rather it's a way for the government to provide legally-backed information to someone, without the government actually having to be in the loop. I'd probably argue the solution to the big-tech dependency here is the government should be required to provide its own, verifiable solution (such as a physical ID card with open software) for users who do not want to trust big-tech.
Where the ZKP spec authors goofed was in not considering the wallet provider to be a party in the transaction. That third party may have interests that are not aligned with the user's.
Offline transfers don’t work without risk of double spending. The transactions eventually have to be finalized with a mint. The most one could hope for in the DigiCash model is the detection of a double spend once the cheated parties go back online[1].
If only the recipient doesn’t have access, a certain amount of trust can be delegated to the strength of the proof presented in the spend. In an ecash model, the proof would be in the form of a signature made by the mint (assuming the recipient was able to get the public keys the mint was using).
Active research is being done on the ecash model with the resurgence of the concept in the Cashu and Fedimint projects. Cashu takes the online sender, offline receiver approach[2].
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.
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.
Can someone compare their tech to the current research frontier of ZK-p tech?
The reason I ask is that I know that many teams working in the b-word field are _regularly_ making great progress. So I'm just wondering if this work is actually novel / useful or whether it's Google releasing something that is already stale.
As the Google guy who did the system, I really don't want to engage in this discussion.
I'll just say that the b-systems solve a different problem, and for the problem solved by our system there is currently no other solution available.
We spoke with Ying Tong and her colleagues from the Ethereum foundation. They have a project investigating which ZK technology would be best for digital credentials, and they have ran a few benchmarks at https://hackmd.io/@clientsideproving/zkIDBenchmarks For reference, our implementation runs the benchmark in about 200ms on the same hardware. The ETHF folks have had access to our code for a while and they agree with this result, but they decided not to publish numbers until the Google code was open-sourced for all. Our system is thus about 10x faster than the closest contender for this problem.
I don't want to make any general claims about who is better than whom. Our system is designed for our problem, and it's not a surprise that another system designed for another problem would perform worse on our problem. We are big fans of the Binius system of Diamond and Posen at Irreducible, and there is a chance that Binius may eventually work better than our stuff. That's however not the case today.
You also have to be careful about which hardware to use. Our implementation is single-threaded no GPU because it has to run on all phones everywhere in the world. Whether or not one can do better on a high-end GPU is irrelevant to us.
Either way, "stale" is not a word I would use. The word I would use is "works today".
Blockchain people consider Ligero as a modern construction worth using. At least last I checked 6 months ago. This work isn't reinventing the wheel and appears to be targeting a nice problem in service of a practical system. The author's country of origin also makes the work seem more legit because everyone knows Italians are the best at zk.
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.
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.
Well, we can split up the credential into multiple ones sharing a serial number to fix the array signing. To bind to NIST there are some solutions based on ZkAttest (which got fixed, I made a few mistakes in it) to show signature under ECDSA while hiding it.
I disagree that no one is talking about it: the solutions are there, it is a question of getting the resources to put it together. Circuit based solutions have some nice properties, but the actual security assumptions are a bit odd, and the reasons people should trust a complex circuit and verification protocol are a bit hard.
I don't however think this is really the big debate. Rather it's about ensuring SD-JWT and related non-private solutions do not get used. To the extent that this work helps show it's possible, and the tradeoffs are desirable, it's good.
> I don't however think this is really the big debate. Rather it's about ensuring SD-JWT and related non-private solutions do not get used. To the extent that this work helps show it's possible, and the tradeoffs are desirable, it's good
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.
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.
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?
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".
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! :-)
I wonder will the final report and any addressed CVEs be publicly documented, and is there a plan for ongoing third‑party audits to build trust in long‑term usage?
> In layperson’s terms, ZKP makes it possible for people to prove that something about them is true without exchanging any other data. So, for example, a person visiting a website can verifiably prove he or she is over 18, without sharing anything else at all.
But how does it prove that the request is actually made by a person and not a bot? Surely that part is technically impossible right now?
The government gives a signed document to natural persons, and the ZK system proves that the document is signed by the government. Bots don't have passports or driver's licenses.
How does the government guarantee that the natural person is such? Various jurisdictions will decide what's good enough, but as a strawman proposal, you go in person to city hall once and upload a document to your phone.
I'm so tired of old closed minded people that run EU countries since ever.
I know someone in germany that got detected cancer in an MRI scanner. The doctor gave him the images and told him to drive to a specialized hospital ~400km away. Otherwise they would send it there with a physical mail and the treatment would have started a week later.
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.
The context is the US mobile drivers licenses and the forthcoming digital identity documents in the EU. The government gives you an electronic document stored in your device, and now the problem is, why would you ever want to give a copy of your document to a third party.
This code solves the problem via zero-knowledge presentations of the document. This is real stuff already integrated in Google Wallet, not vaporware. See also the paper linked from GitHub.
Ignore the marketing in TFA.
The paper linked from Github is at [1]. Section 6.1 gives a fairly practical example of use with a passport, while 6.2 talks about how it might be used with a drivers license.
How do you prevent kids just obtaining a copy of such electronic document from somewhere? The actual document itself doesn't prove anything about your age; it just proves that you have the document.
To say this has nothing to do with blockchain is like saying RADAR had nothing to do with war. Yes, people knew Maxwell's equations prior, i.e. "knew the proofs," w.r.t. ZKP but it has only really been developed much later, during the war.
The whole field of zero-knowledge mathematics was, if not non-existent, but certainly marginalised, before the crypto investment has hit the scene; this is facts. Yes, Shamir et al. go back to 90s, but it's a far-cry from zkSNARK, zkVM stuff we have nowadays. It has also popularized many applications, like provable auctions (see kyber[1] library in Go as nice starting point...) and opened the door to homomorphic stuff.
The comment didn't say that ZKP had nothing to do with blockchain. The comment said that blockchains are not needed/involved for a zero knowledge proof, just like war is not needed for radar.
Actually I meant blockchain qua blockchain, that is, ledger and consensus. There is no ledger and consensus at all in this system.
If people want to redefine blockchain to mean zero-knowledge, and they want to redefine zero-knowledge to mean succinct as they all seem to have done, it's not my problem.
That’s not accurate; all the industrial interest in ZKPs came from academic research. Yes, after the initial deployments the blockchain folks invested a shit-ton of money and greatly accelerated the available implementations (along with also contributing some new schemes), but it’s not like academic research was in some kind of stone-age beforehand.
Web3 specifically is trying to repeat the dot-com bubble by using the same technology and content delivery system that it used and which led to the runaway adoption, but in a setting where it makes it too easy to separate people from their money.
ZKP can be thought of as a "fancy hash function". It's often puffed up to a mysterious magic level in order to appeal to blockchain audiences, but there's really no magic.
Oversimplification is not helpful either. ZKPs are not glorified hashes. There’s much more mathematics that goes into design of efficient ZKPs and their security proofs.
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...
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.
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.
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
I think the Where's Waldo example, while not technically zero knowledge, gives a pretty good intuition of the idea behind it.
It certainly gives a "layperson" example of being able to prove you know something without revealing it, which isn't the whole definition of ZK but is the idea driving it.
Is that "Draw a Waldo with this outline"?
Imagine it isn't Waldo, but an unknown figure and you are only given the silhouette to find. If you can draw what's within the silhouette or something, you've proven you've located it to high certainty without saying where.
Say the whole image looked like noise and was generated from quantum measurements, and the coordinates to hash for the problem were generated with quantum measurements, and you were given the silhouette and the hash of the noise within to look for. I could see it for proof of work: you could slide along a hashing window and prove you actually did work examining half the image on average or whatever.
Thanks. So is it really different from "what's (the hash of) word x on page y of the manual?"?
I think my example isn't great and would need to be modified like maybe give the hash of a neighboring area to prove you found it, so your answer couldn't be used by others to find the location much more cheaply.
Plot twist: In addition to the cutout paper, the prover also brings their OWN picture of waldo, which they always place behind the cutout.
[dead]
Sorry but that is not intuitive for me. You wrote one line of analogy and then went into 4.5 paragraphs of technical explanation.
"The Ali Baba Cave" example from the Wikipedia article is what made it click for me: https://en.wikipedia.org/wiki/Zero-knowledge_proof.
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.
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.
Thank you!!
If I understand correctly:
* The prover commits to a starting value (public input)
* Instead of waiting for an interactive challenge, they hash it and use the resulting hash output as if it were a challenge
If we believe the hash is a random oracle (as we do for cryptographic hash functions), then it is hard for the prover to manipulate the challenges. Is that it?
You got it. There are a few nuisances, e.g. the "theorem statement" must be hashed as well so that proving that name=Mickey has a different oracle than proving that name=Goofy, but your basic understanding is correct.
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.
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.
Was looking to see if someone posted this video. The first few interviews are excellent - the later ones, not so much (in terms of explaining ZK - they're good chats, of course).
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...
That's only for interactive proofs though. Like GP I have no problem understanding those.
There is a trick to convert an IP to a non-IP.
Usually in an IP, the prover (Bob) has to answer questions from the verifier (Alice), and Alice chooses her questions by flipping a coin. If the Bob doesn’t really know the answer, he’ll get caught cheating with high probability.
So now the trick: Bob starts generates his initial answer. Then he hashes it (“commits” in the jargon), and uses the hash as “Alice’s first coin flip”. Then he answers the question for that flip, hashes the whole thing for “Alice’s second coin flip”… etc.
Bob does this say, 100 times, and then sends the whole simulated conversation to Alice. Alice can verify that he didn’t cheat by checking the intermediate hashes.
The whole thing depends on the ability to not control the result of the hash function, so it’s vital to use a cryptographically secure one.
It "feels" much easier to generate random non-solutions and check if the random questions happen to pass, though. Is it really all there is to it? You increase the number of questions to compensate and that's the whole scheme? Wouldn't the responses be a ludicrous amount of data?
Yes, basically. The hard work happens in constructing the interactive proof to ensure that you can’t reneg on the earlier steps.
All the proofs that I know of allow one to get lucky with probability about .5 in each round. When you do an interactive proof with 100 rounds, you have a 2^-100 chance of getting away with cheating.
When you go non-interactive with 100 rounds, an adversary could cheat by trying about 2^100 proofs. So you replace a stronger guarantee with a weaker one, but 2^100 is a pretty big barrier.
(I just looked and the Wikipedia page and it’s very confusing fwiw)
The trick is called the Fiat-Shamir transform, and you're right, it does require more questions to get an equivalent security level, precisely because you can try a large number of random non-solutions without anyone catching you doing it.
But the number of questions you need to compensate grows only a little.
For example, interactively if you ask for Merkle tree proof that selected leaf values have a particular property, you only have to ask for about k leaves to get probability 1-(2^-k) that you'd catch a dishonest prover who had committed a Merkle root with less than half the leaves having the property.
Non-interactively, a dishonest prover could secretly grind attempts, say 2^g times, and then you'd have a lower probability of catching them, approximately 1-(2^(g-k)). But g can't be all that large, so you can increase k to compensate without making the proof much larger.
You.can also require certain hashes to have a fixed prefix, like Bitcoin mining, forcing every prover to have to grind 2^p times. This reduces the effective g that a dishonest prover can achieve, allowing k to be smaller for the same security, so allowing the non-interactive proof to be smaller. At the cost of honest provers having to grind.
This is Fiat-Shamir, right?
Correct. I didn’t remember the name, so thanks!
The surprising part of STARKS and SNARKS comes down to the nature of polynomials. It's surprisingly easy to tell two polynomials apart with a small number of random checks (Schwartz Zippel lemma). In light of this it's not surprising there is good reading comparing them to erasure codes which rely on exactly this property of polynomials.
The non-interactive piece is pretty straightforward you just simulate challenge response conversation with unbiasible public randomness and show the transcript (Fiat Shamir transform).
Another area worth exploring is how some of these proof systems can have such incredibly small proofs (192 bytes for any computation in groth16 zk snarks). That relies on the much more difficult to intuit theory of elliptic curve pairing functions.
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?
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.
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?
It depends on local regulations. As far as I can tell Europe will require some sort of blessing of the wallet. To be clear, governments will develop their own apps and it's not clear that Google will be blessed. We (Google) are giving them the code pro bono to improve privacy.
Hmm. This introduces a third party to the protocol, right? Specifically the developer of the wallet. So we now have three parties: the user, the wallet developer, and the relying party. Does this zk protocol protect the user's privacy from the wallet developer as well as the relying party?
In other words, does the protocol give the wallet access to information about the relying party? For example, could this wallet that I don't control tell its owner, or the government, that I am using it to access a certain website?
Yes, a malicious wallet could leak your information. This is why some governments will insist on using only blessed wallets. However, wallet+zk is strictly better than sending the plaintext MDOC to the relying party. There are no solutions in this space, only tradeoffs, and elected representatives have picked one tradeoff.
That's too bad :( I wish the protocol had been designed with that in mind. Requiring users to trust proprietary software from Google & Apple to be in complete control over their digital identities is a pretty crummy direction to go in.
See https://github.com/eu-digital-identity-wallet/eudi-doc-archi... for a reference to the nuances on all these topics, at least in the context of the European Union. Other locales have different problems and different solutions.
If you think you have a better idea shoot me an email.
The document states:
> Controlled by users: The EU Digital Identity Wallets will enable people to choose and keep track of their identity, data and certificates which they share with third parties. Anything which is not necessary to share will not be shared.
I think where the ZKP stuff being discussed here fails to meet this criteria is the wallet provider is also a third (non-user) party. You stated elsewhere that a malicious wallet could leak data about a transaction: that's exactly the vulnerability that is not being accounted for by this protocol.
> If you think you have a better idea shoot me an email.
Sure, will do. It does seem to me like a solvable problem. I think this kind of tech is really important and I'd love to see this hole get closed so I can feel better about supporting it.
Update: After some email discussion with Matteo, it looks like my fears are unfounded. The EU regulations seem to require wallets to be open source[1]. Assuming that wallets do not need to pass any sensitive transaction data down to the OS libraries, then it should be possible for users to verify the behavior of their wallet software by examining the source and possibly even by building & deploying it themselves.
[1] See section 33 here https://www.european-digital-identity-regulation.com/Preambl...
In principle, you could use an open source implementation, but not a user-modifiable implementation.
Nothing stops a government from making their code open source and providing you with reproducible builds. You just won't be able to change the code to do something the government doesn't deem legal.
(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.
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.
The role of the secure element is only to "bind" the credential to the device, so that if you copy the credential somewhere else then the credential is useless. Concretely, the secure element produces a ECDSA signature that must be presented together with the credential. This is the normal protocol without ZKP. Concretely, the SE is in the phone, but could be a yubikey or something else.
The ZKP library does not run on the secure element. It runs on the normal CPU and produces a proof that the ECDSA signature from the SE is valid (and that the ECDSA signature from the issuer is valid, and that the credential has not expired, and ...) If you crack the ZKP library, all you are doing is producing an incorrect proof that will not verify.
Am I correctly understanding that I'd get the credential from say my state DMV once, and then later whenever I want to prove my age to a website the proof protocol is just between that website and my device? The DMV gets no information about what websites I use the DMV credential with and they get no information about when I use the credential even if the website and the DMV decide to cooperate? All they would be able to get was that at time T someone used a credential on the site that came from the DMV?
I tried to sketch out a design an age verification system, but it involved the DMV in each verification, which made timing attacks a problem. Briefly the website would issue a token, you'd get a blind signature of the token from the DMV's "this person is 18+" service, and return the token and unblinded signature to the website. I think that can be made to work but if the site and DMV cooperated they would likely be able to unmask many anonymous site users by comparing timing.
Getting the DMV out of the picture once your device is set up with the credential from them nicely eliminates that problem.
You are correct. The property that the colluding website and DMV still cannot identify you is called "unlinkability" and as far as I can tell cannot be achieved without zero-knowledge proofs. See https://github.com/user-attachments/files/15904122/cryptogra... for a discussion on this issue.
However, the timing attack resurfaces once you allow the DMV to revoke credentials. Exactly how the revocation is done matters. We are actively pushing back against solutions that require the DMV to be contacted to verify that the credential has not been revoked at presentation time, but this is a very nuanced discussion with inevitable tradeoffs between privacy and security.
>> The DMV gets no information about what websites I use the DMV credential with and they get no information about when I use the credential even if the website and the DMV decide to cooperate?
> You are correct. The property that the colluding website and DMV still cannot identify you is called "unlinkability" and as far as I can tell cannot be achieved without zero-knowledge proofs.
Well, no. This is true only if you trust the unverifiable wallet software on your phone, which was provided by a for-profit, American big tech advertising company. In this protocol, the wallet may secretly leak the transaction details back to the DMV or whoever else they wish[1].
[1] "Yes, a malicious wallet could leak your information." https://news.ycombinator.com/item?id=44458549
MatteoFrigo is suggesting that unlinkability requires ZKPs.
Your observation that a bad wallet could compromise unlinkability is not a refutation of that. To refute it you need to show that it is possible to achieve unlinkability without using a ZKP.
One part that I don't understand yet: How does the system ensure "sybil resistance"? (not sure if that's the right term in that context)
By providing both attestation of individual attributes combined with "unlikability", how would even a single verifying party ensure that different attestations don't come from the same identity?
E.g. In the case of age attestation a single willing dissenting identity could set up a system to mint attestations for anyone without it being traceable back to them, right? Similar to how a single of-age person could purchase beer for all their under age friends (+ without any feat of repercussions.
Great question. The current thinking, at least in high level-of-assurance situations, is this. The identity document is only usable in cooperation with a hardware security element. The relying party picks a random nonce and sends it to the device. The device signs the nonce using the SE, and either sends the signature back to the relying party (in the non-ZKP case), or produces a ZKP that the signature is correct. The SE requires some kind of biometric authentication to work, e.g. fingerprint. So you cannot set up a bot that mints attestations. (All this has nothing to do with ZKP and would work the same way without ZKP.)
In general there is a tradeoff between security and privacy, and different use cases will need to choose where they want to be on this spectrum. Our ZKP library at least makes the privacy end possible.
Okay, yeah that's what I assumed.
That seems a bit like a game of whack-a-mole where as long as the forging side is willing to go further and further into out-of-hardware emulation (e.g. prosthetic finger on a robot hand to trick fingerprint scanners), they are bound to win. Biometrics don't feel like they hold up much if you can have collusion without fear of accountability.
> Our ZKP library at least makes the privacy end possible.
Yes, that's also one of the main things that make me excited about it. I've been following the space for quite some time now, and I'm happy that it becomes more tractable for standard cryptographic primitives and thus a lot more use-cases.
Thanks for your contributions to the space and being so responsive in this thread!
Would something like this be considered a ZK proof? https://crypto.stackexchange.com/questions/96232/zkp-prove-t...
No. ZK has a technical definition I don't want to get into, but note that the described system is deterministic and it always produces the same proof for Alice on a given day, and the proof for a later day can be derived from the proof for an earlier day. So two proofs can be linked back to Alice, and thus the system is not ZK. You need some kind of randomness for ZK.
Makes sense.
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.
No. Using the MDOC requires a signature from a hardware security key in the phone, and a lot of the complexity is how to avoid leaking the private key, which would identify you.
Well, that's not great. My phone is closed-source and its software is provided by an ad company. I do not trust it to always behave in my interests.
An alternative would be some secure chip in a credit-card size plastic document, but nobody seems to like that idea. We (Google) don't make these choices.
Another approach could be for a component in the protocol that I do trust (eg an open source web browser) to serve as an intermediary, providing only the information required to each of the components that I don't trust (wallet, website). The wallet does not need to know who is requesting the proof, right?
I hear you. The main problem is how to prevent you from giving your document to somebody else, and things have converged on certified smartphone with security key plus biometrics.
Yeah, Passkeys are doing the same thing, expecting users to just blindly trust American Big Tech companies. It's distressing that no one working on these protocols considers the developers of the software that implements the protocol to be a party in the protocol. What are the wallet provider's interests in this exchange? How can the user be protected from the wallet provider? Seems no one asks these questions :(
Anyone can implement passkeys. The feature where passkeys can be made to attest to the hardware provider is optional and no site I've used requires it. Firefox defaults to not allowing passkeys to attest to the hardware unless you click through a permission dialog.
I don't want to get into a Passkey derail, but no. The Passkey spec requires clients to handle the user's own data in certain ways, and the Passkey spec authors threaten clients that allow users to manage their own data with client bans.
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?
But to be clear, mdoc already accounts for this through its selective disclosure protocol, without the need for a zero knowledge proof technology. When you share an mdoc you are really just sharing a signed pile of hashes ("mobile security object") and then you can choose which salted pre-images to share along with the pile of hashes. So for example your name and your birth date are two separate data elements and sharing your MSO will share the hashes for both, but you might only choose to share the pre-image representing your birthday, or even a simple boolean claim that you are over 21 years old.
What you don't get with this scheme (and which zero knowledge proofs can provide) is protection against correlation: if you sign into the same site twice or sign into different sites, can the site owners recognize that it is the same user? With the design of the core mdoc selector disclosure protocol, the answer is yes.
Yes
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...
The explanation that one person gave me was basically that you use an RNG to generate the challenges. Not sure if this is quite "proper", but it makes sense to me so long as you can't game the system. Perhaps make the RNG slow to prevent picking a convenient sequence?
There's a Where's Waldo explanation that I can't find right now but helped me a lot.
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.
Intuition of what it is (ie interface) or how it works (implementation)?
Age assurance will be the gateway to government issued(via corporate proxy) internet usage permits.
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-...
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.
The political answer to circumventing laws is usually some form of punishment. This is often much easier than weird technical solutions.
Indeed. Governments have to worry about 99.9% of cases covered with a law or regulation have punishment in term of fine or imprisonment.
Those remaining very likely have multiple advantages like advance technical knowledge, connection to powerful people in business / governments, money and legal support in case they end up on wrong side of law. There is very little benefit and lot of effort to catch these unless they are running some kind of criminal organization which adversely affects their government/regime.
Is that what happens in this specific case?
> 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.
> People have bothered with downloading low-quality Mp3s from Napster, figuring out video codex and modding game consoles to get free video games
That's not "enough", it was extremely nice and probably less than 1% of population
> 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.
At that point something along the likes of shadowsocks would be more effective, and the question still remains.
Shadowsocks is detectable using entropy analysis but not everybody does it. I heard in China they do. you connect at first they collect data, analyze and ban. in Russia they are not that smart yet but in Russia even if you mask VPN traffic they use other tricks. For example if you visit any state adjacent site from your Russian IP and VPN with same cookies they can ban VPN exit node. Or if all your traffic goes to one IP they will probe ports or just ban that.
I think the answer is that it's likely illegal if someone can prove an intent to defraud or commit a theft of service, but the chances of getting caught may be small depending on your technical ability/OPSEC.
Yes, but is that what happens in this specific case? There are enough legitimate uses of VPNs that blocking them solely in case people wriggle out of social media taxes would be extremely heavy-handed.
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?
VPN or TOR?
And maybe also uniquiness guarantees, so that people can finally stop debating whether the internet is "dead"?
Today it's age gating porn, but the next move will be age gating sites that talk about LGBTQ issues by moving the 'obscenity' definition to be anyone they don't like. Left to their own devices and unopposed, they'll declare discussion of birth control and interracial marriage to be adults-only.
Yep. This is completely kakistocracy-technofeudalism complex enablement.
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.
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.
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?
> Isn’t that the same argument as “Parents should keep kids away from cigarettes” by tobacco companies who were simultaneously marketing to children?
I think most would agree that there's a significant difference between a physical product that shortens the lifespan of virtually all humans who use it, and looking at images and video, no matter how extreme.
> 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?
Agreed.
Parents and guardians should definitely be aware of and concerned about what internet filters are in place at schools.
> Parents and guardians should definitely be aware of and concerned about what internet filters are in place at schools.
Neither of the words you used give parents any control over the situation. Legislation is the circumspect way parents are exerting control over websites that are unable to police themselves.
Fair enough. Sounds like legislation may be a good way to enforce internet filtering on school computers.
Schools have traditionally been ground zero for culture war in the USA, so this fits.
I do agree there is a significant difference. The images and video are much worse -- one particularly bad video can scar people for months, even years, one cigarette isn't that bad.
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.
Is the “right kind of parent” here synonymous with those that regulate what their children see online?
I'm fine with that. I'd rather parents make "bad" decisions about protecting their own children than the government forcing their own opinions on them.
What's the right kind of parent?
> reasonable
I think the real issue is that the definition of "reasonable" is subjective and often changes with time/culture/people in charge at the moment.
[dead]
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.
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.
[dead]
This is a parenting problem, not a technology and everyone else problem.
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.
The parents bare the responsibility. Don't baby-proof the Internet, the same way we are not baby-proofing the streets, subways or anything else.
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 ?
Maybe, but even this is broken with the internet being international. You'd need a system much more advanced than even the GFW.
Somehow this work when dealing with pedophile content, so the tech is already active.
For example, on Discord, all your messages are scanned for such. On Cloudflare as well (for over 5 years).
For now it means they have no interest to remove such content unless coerced or affected by the public opinion.
This would destroy all content though, not just for minors.
Absurd, but it works, in North Korea (death penalty), Iran (death penalty), China (10 year prison), and also protects victims from rape, or "rape" under financial pressure.
The alternative is to let responsibility of the parents to install web filter to their kids, and let others live freely on the internet, without sharing their history or IDing them.
In reality, TikTok also has really traumatizing content, yet is engaging tons of kids and teenagers, and IDing won't solve that, but good parents can.
I agree, that does work, but there are parameters which are different that make it worth the tradeoff to police it that strongly, like the size of the audience and the much more severe real harm caused by its production and distribution.
I genuinely don't know what to think on this :|
I just pushed this idea as a "solution" to see what others think, but I don't know. Again perhaps educating the parents about how to educate kids about the dangers of internet, and perhaps a web filter for kids.
This is actually one place where AI could be useful, to do dynamic local content classification (instead of a blocklist), especially if integrated directly in Android / iPhone.
Like https://support.apple.com/en-us/105121 but more dynamic.
I think it’s pretty damned important that my 8 year old son doesn’t run across Andrew Tate or similar stuff.
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?
Reddit being considered a space for women is the funniest take I've heard in a while. But regardless, you didn't adequately take into account that being choked is one of the top sexual fantasies of women. Whatever explanation you put forth has to also explain why it's also highly desirable to be on the receiving end.
The "porn has been giving men violent sexual fantasies" line has existed since before I was born but it always ignores that they're the top fantasies among women too. Among my friend group the more common refrain is women who want to be choked but their boyfriends are uncomfortable doing it.
I agree with you, at the end I think it could work if we offer to promote better local solutions (e.g. better tooling on iPhone), rather than the server authenticating the user.
Perhaps find a way to force Windows / Android / iOS to include such "firewall"/webfilter by default.
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.
What web browser are you using?! I think this says more about you than about the internet if this is what you're seeing.
A world can be built on this. So many things are broken privacy-wise because we have to overshare our PII. SSNs for example.
Agreed. There is a lot of negativity about this here, but on-balance this seems like a great thing.
How do you defend against someone who:
- Buys or borrows a laptop / phone / whatever from somebody with an authorized private key
- Downloads an authorized private key file from a sketchy forum (maybe hacked from an unwilling target, maybe willingly shared by a free-speech advocate)
- Uses a VPN over HTTPS to visit websites in countries where age checks aren't legally mandated (and non-compliance is implicitly or explicitly encouraged for economic or ideological reasons)
The credential ("driver's license") contains a public key whose secret key is stored securely in a hardware secure element. The standard assumption is that the SE is in the phone, but it could be a yubikey or similar device. In order to use the credential, you need the SE. So you cannot buy a phone from somebody and download a credential from somebody else. You can however buy a phone and the credential from somebody. As a mitigation, the SE only generates the signature when unlocked via a fingerprint or similar biometric input which must match the one that was provided at the time the credential was issued. Whether or not your attack works in this scenario depends on the details. For example, if you only obtain the credential in person at a local government office and provide a fingerprint at that time, it's not that easy to sell the phone and the credential afterwards.
> the SE is in the phone, but could be a yubikey or something else
Just like with passkeys or MFA, the "something else" could be purely software though, right? And hence automated?
For example I can run Windows 11 in a virtual machine on Linux, using softu2f to emulate TPM 2.0, and Windows does not know the difference.
The problem that needs to be solved is, how can a government give you an identity document in a way that you cannot give the document to somebody else. Whether or not this problem needs to be solved is a political question, but it seems like the majority thinks that identity documents should be hard to forge, in the same way as dollar bills should be hard to forge. The only practical solution is to have some sort of hardware that the user cannot forge, and relying parties will insist that the document be bound to such hardware. So yes, the something else could be software, but nobody will accept signatures from an emulated TPM. I had in mind a government-issued yubikey that can be identified as such, or maybe a plastic card with embedded secure chip with the same functionality. See https://github.com/eu-digital-identity-wallet/eudi-doc-archi... for the current thinking at least in the EU.
I should also remark that the above is a western-centric perspective, whatever "West" means. For example, I heard the architect for a similar system already deployed in India remark that in his jurisdiction many households share one phone across many family members, and India chose to accept more possibility for fraud in exchange for wider usability by the population. In that context this choice looks like the correct solution.
It’s more about the device being tamper resistant than “hard to forge”. You don’t want people playing around with the device generating signatures. Algorithmically, there is nothing done on a secure element that can’t be done with software on a general chip. The defining difference is the physical separation of data and the mechanisms put in place to brick the device on detection of physical tampering.
You do not. These measures are targeted against law-abiding and productive citizens to control them further. The other ones (the top 0.1% or the bottom 20%) are uncontrollable anyway.
In the future, you'll need a signed certificate with your PII/KYC to access the internet and get an IP address. China is already on the way there and the west is warming up to this approach.
is it possible to lend your device to your IT hacker cousin?
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.
> 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
You can have a password manage your passkey private data. Several now have passkey support, including some that work on Linux such as 1Password and Bitwarden letting you use passkeys even if your household is completely Apple-free, Microsoft-free, and Google-free.
https://github.com/keepassxreboot/keepassxc/issues/10407#iss...
> To be very honest here, you risk having KeePassXC blocked by relying parties
Even if the bigtechs don't "officially" make the passkey standards require bigtech involvement, it seems very likely to me that conservative businesses like banks will only accept bigtech implementations. And then you're sunk.
Similarly, look at how OpenID turned into "Sign in with AppleGooFaceSoft".
This ZKP+hardware secure element stuff seems even worse, because how are you going to make it work on old hardware, or with free software, or with open devices?
> Even if the bigtechs don't "officially" make the passkey standards require bigtech involvement, it seems very likely to me that conservative businesses like banks will only accept bigtech implementations.
Indeed. It's not a theoretical concern, either. The spec authors themselves actually maintain a "naughty client list": https://passkeys.dev/docs/reference/known-issues/
> This ZKP+hardware secure element stuff seems even worse, because how are you going to make it work on old hardware, or with free software, or with open devices?
I don't love it, but I actually do see an argument that this kind of proof-of-property stuff really does belong in a secure area, backed by approved software. It is making government-backed, legal claims about a person or entity. Unlike with Passkeys, it's not really "your" data, rather it's a way for the government to provide legally-backed information to someone, without the government actually having to be in the loop. I'd probably argue the solution to the big-tech dependency here is the government should be required to provide its own, verifiable solution (such as a physical ID card with open software) for users who do not want to trust big-tech.
Where the ZKP spec authors goofed was in not considering the wallet provider to be a party in the transaction. That third party may have interests that are not aligned with the user's.
Here is one we are working on: https://paygo.wtf/
https://x.com/0x_Osprey/status/1925299005191577921
Nice. I wish you success in this.
Offline transfers don’t work without risk of double spending. The transactions eventually have to be finalized with a mint. The most one could hope for in the DigiCash model is the detection of a double spend once the cheated parties go back online[1].
If only the recipient doesn’t have access, a certain amount of trust can be delegated to the strength of the proof presented in the spend. In an ecash model, the proof would be in the form of a signature made by the mint (assuming the recipient was able to get the public keys the mint was using).
Active research is being done on the ecash model with the resurgence of the concept in the Cashu and Fedimint projects. Cashu takes the online sender, offline receiver approach[2].
[1] https://chaum.com/wp-content/uploads/2021/12/Untraceable_Ele...
^See paragraph in the introduction ending with:
“But if Alice reuses a coin, the bank can trace it to her account and can prove that she has used it twice.”
[2] https://x.com/CashuBTC/status/1901240537866273252
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.
For the sake of sanity - do never rely on Google when building critical sections of your software!
Good thing it's open source
For people interested in zero-knowledge proofs check https://news.zksecurity.xyz/ which is a hackernews but for ZK!
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.
Can someone compare their tech to the current research frontier of ZK-p tech?
The reason I ask is that I know that many teams working in the b-word field are _regularly_ making great progress. So I'm just wondering if this work is actually novel / useful or whether it's Google releasing something that is already stale.
As the Google guy who did the system, I really don't want to engage in this discussion.
I'll just say that the b-systems solve a different problem, and for the problem solved by our system there is currently no other solution available.
We spoke with Ying Tong and her colleagues from the Ethereum foundation. They have a project investigating which ZK technology would be best for digital credentials, and they have ran a few benchmarks at https://hackmd.io/@clientsideproving/zkIDBenchmarks For reference, our implementation runs the benchmark in about 200ms on the same hardware. The ETHF folks have had access to our code for a while and they agree with this result, but they decided not to publish numbers until the Google code was open-sourced for all. Our system is thus about 10x faster than the closest contender for this problem.
I don't want to make any general claims about who is better than whom. Our system is designed for our problem, and it's not a surprise that another system designed for another problem would perform worse on our problem. We are big fans of the Binius system of Diamond and Posen at Irreducible, and there is a chance that Binius may eventually work better than our stuff. That's however not the case today.
You also have to be careful about which hardware to use. Our implementation is single-threaded no GPU because it has to run on all phones everywhere in the world. Whether or not one can do better on a high-end GPU is irrelevant to us.
Either way, "stale" is not a word I would use. The word I would use is "works today".
Blockchain people consider Ligero as a modern construction worth using. At least last I checked 6 months ago. This work isn't reinventing the wheel and appears to be targeting a nice problem in service of a practical system. The author's country of origin also makes the work seem more legit because everyone knows Italians are the best at zk.
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
On the contrary, any undergraduate can understand our solution. In contrast, I don't know anybody who can explain the bilinear pairing in BBS.
Perhaps "unfathomably" was too strong, but "any undergraduate" is at least very easy to falsify.
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.
Well, we can split up the credential into multiple ones sharing a serial number to fix the array signing. To bind to NIST there are some solutions based on ZkAttest (which got fixed, I made a few mistakes in it) to show signature under ECDSA while hiding it.
I disagree that no one is talking about it: the solutions are there, it is a question of getting the resources to put it together. Circuit based solutions have some nice properties, but the actual security assumptions are a bit odd, and the reasons people should trust a complex circuit and verification protocol are a bit hard.
I don't however think this is really the big debate. Rather it's about ensuring SD-JWT and related non-private solutions do not get used. To the extent that this work helps show it's possible, and the tradeoffs are desirable, it's good.
> I don't however think this is really the big debate. Rather it's about ensuring SD-JWT and related non-private solutions do not get used. To the extent that this work helps show it's possible, and the tradeoffs are desirable, it's good
On that we all agree.
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.
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.
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?
Great intro to how zkTLS works: https://blog.zksecurity.xyz/posts/zktls/
im in the background of that talk
Lagrangodamus!
A technical deep dive into how zkTLS works with MPC architecture: https://paragraph.com/@vinny/opacity-network-deepdive
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".
Reclaim Protocol, a YC company, is building an open sourced version for zkTLS. This has been by far the most widely adopted zkTLS project.
You can read the docs and whitepaper here: https://docs.reclaimprotocol.org/ And also take a look at all usecases built on top of this tech: https://reclaimprotocol.org/ecosystem
It works for private user data in adversarial setting. Like the outcome of a rocket league match can settle a $20 bet. Showdown.win
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! :-)
but the server side does not have to support it on their end for it to be used
[dead]
[dead]
I wonder will the final report and any addressed CVEs be publicly documented, and is there a plan for ongoing third‑party audits to build trust in long‑term usage?
A fun mechanism for guaranteeing privacy of information in competitive multiplayer settings that operate on distributed networks.
This might enable something like Scroll (the pay-to-view without ads network, acquired and destroyed by Twitter) but anonymous.
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.
Blockchain => trash
A system that can be trusted needs to work in the real world, with credit card payments, bank accounts, VAT.
> In layperson’s terms, ZKP makes it possible for people to prove that something about them is true without exchanging any other data. So, for example, a person visiting a website can verifiably prove he or she is over 18, without sharing anything else at all.
But how does it prove that the request is actually made by a person and not a bot? Surely that part is technically impossible right now?
The government gives a signed document to natural persons, and the ZK system proves that the document is signed by the government. Bots don't have passports or driver's licenses.
How does the government guarantee that the natural person is such? Various jurisdictions will decide what's good enough, but as a strawman proposal, you go in person to city hall once and upload a document to your phone.
Anyway to verify an email address is valid using zero-knowledge?
Isn't it a pity they did not choose a safer language?
I'm so tired of old closed minded people that run EU countries since ever.
I know someone in germany that got detected cancer in an MRI scanner. The doctor gave him the images and told him to drive to a specialized hospital ~400km away. Otherwise they would send it there with a physical mail and the treatment would have started a week later.
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.
https://en.m.wikipedia.org/wiki/Sparkassen-Finanzgruppe
So ZKP actually works?
It has been working for years in Zcash.
Yes - we've even seen entire virtual machines that allow you to prove arbitrary rust code.
Our team is leveraging zkVMs for paygo.wtf
Ofc, since approx the 80s
[flagged]
Author (of the code) here.
The context is the US mobile drivers licenses and the forthcoming digital identity documents in the EU. The government gives you an electronic document stored in your device, and now the problem is, why would you ever want to give a copy of your document to a third party. This code solves the problem via zero-knowledge presentations of the document. This is real stuff already integrated in Google Wallet, not vaporware. See also the paper linked from GitHub. Ignore the marketing in TFA.
The paper linked from Github is at [1]. Section 6.1 gives a fairly practical example of use with a passport, while 6.2 talks about how it might be used with a drivers license.
[1] https://eprint.iacr.org/2024/2010.pdf
How do you prevent kids just obtaining a copy of such electronic document from somewhere? The actual document itself doesn't prove anything about your age; it just proves that you have the document.
Is it stored in a TEE or something like that?
[flagged]
Nope, no blockchain involved.
To say this has nothing to do with blockchain is like saying RADAR had nothing to do with war. Yes, people knew Maxwell's equations prior, i.e. "knew the proofs," w.r.t. ZKP but it has only really been developed much later, during the war.
The whole field of zero-knowledge mathematics was, if not non-existent, but certainly marginalised, before the crypto investment has hit the scene; this is facts. Yes, Shamir et al. go back to 90s, but it's a far-cry from zkSNARK, zkVM stuff we have nowadays. It has also popularized many applications, like provable auctions (see kyber[1] library in Go as nice starting point...) and opened the door to homomorphic stuff.
[1] https://pkg.go.dev/go.dedis.ch/kyber/v4/shuffle
The comment didn't say that ZKP had nothing to do with blockchain. The comment said that blockchains are not needed/involved for a zero knowledge proof, just like war is not needed for radar.
Actually I meant blockchain qua blockchain, that is, ledger and consensus. There is no ledger and consensus at all in this system.
If people want to redefine blockchain to mean zero-knowledge, and they want to redefine zero-knowledge to mean succinct as they all seem to have done, it's not my problem.
There is no blockchain here, period.
That’s not accurate; all the industrial interest in ZKPs came from academic research. Yes, after the initial deployments the blockchain folks invested a shit-ton of money and greatly accelerated the available implementations (along with also contributing some new schemes), but it’s not like academic research was in some kind of stone-age beforehand.
Web3 is just crypto brought to it's logical conclusion.
That doesn't mean that part of the tech can't be used in traditional IT.
Web3 specifically is trying to repeat the dot-com bubble by using the same technology and content delivery system that it used and which led to the runaway adoption, but in a setting where it makes it too easy to separate people from their money.
I have the impression, that part of the hype cycle is already over.
ZKP can be thought of as a "fancy hash function". It's often puffed up to a mysterious magic level in order to appeal to blockchain audiences, but there's really no magic.
Oversimplification is not helpful either. ZKPs are not glorified hashes. There’s much more mathematics that goes into design of efficient ZKPs and their security proofs.