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.
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 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?
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.
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.
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 :(
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].
- 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.
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.
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.
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.
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.
bobbiechen|8 months ago
https://blog.cryptographyengineering.com/2014/11/27/zero-kno... was a good intro for interactive ZK proofs but I haven't been able to find something for non-interactive ones.
This blog post comparing ZK-STARKs to erasure coding is in the right flavor but didn't quite stick to my brain either: https://vitalik.eth.limo/general/2017/11/09/starks_part_1.ht...
JanisErdmanis|8 months ago
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.
supernikio2|8 months ago
abhv|8 months ago
That doesn't explain the way this scheme works, but it's a nice start.
tptacek|8 months ago
https://blog.cryptographyengineering.com/2014/11/27/zero-kno...
a_tartaruga|8 months ago
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.
coldpie|8 months ago
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?
orblivion|8 months ago
unknown|8 months ago
[deleted]
unknown|8 months ago
[deleted]
noman-land|8 months ago
notfed|8 months ago
krunck|8 months ago
jjmarr|8 months ago
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-...
mullingitover|8 months ago
perching_aix|8 months ago
Jommi|7 months ago
burnt-resistor|8 months ago
api|8 months ago
I don't like this but don't have another solution other than the porn industry self-policing which isn't promising.
natch|8 months ago
consumer451|8 months ago
ChuckMcM|8 months ago
I really like Andy Birrells "micro-cents" which exploited the fact you could not easily reverse an MD5 hash so you one could cheaply do high confidence low value transactions at speed. Another idea that never got anywhere sadly.
ZKP ID cards and ZKP currency are both interesting things from the 90's I'd love to see in real life. Imagine I could pay you phone to phone with no network level of capability using a currency that couldn't be double spent. That was the promise of digicash. The government hated it :-). It was just like cash currency in that serial numbers could let you track the bank it left, and the bank it came back in to, but you couldn't track anywhere it had been between those two points.
Fun times. I'll have to see if some of my ZKP ideas can be built on top of this tech now.
coldpie|8 months ago
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
0xOsprey|8 months ago
https://x.com/0x_Osprey/status/1925299005191577921
derangedHorse|8 months ago
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
csense|8 months ago
- 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)
MatteoFrigo|8 months ago
csomar|8 months ago
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.
esbranson|8 months ago
BimJeam|8 months ago
Ey7NFZ3P0nzAe|8 months ago
baby|8 months ago
WXLCKNO|8 months ago
hrdwdmrbl|8 months ago
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.
MatteoFrigo|8 months ago
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".
a_tartaruga|8 months ago
Confiks|8 months ago
It's also an unfathomably complex solution [1] which only a few people in the world will grok, and far more complex than existing solutions such as Idemix or BBS+, which lack such a hardware binding on existing hardware.
Age verification in a privacy preserving way is a really hot topic at the moment, but it will always be possible to bypass it – as will any commonly held anonymous boolean – in quite trivial ways. For example by setting up an open proxy to disclose genuine attributes. There are some privacy preserving mitigations, for example cryptography that'll make you linkable when disclosing more than k times per time period, or detecting slower-than-near-light-speed disclosure in a face-to-face disclosure scenario.
However, these mitigations will never be completely secure. That might not be a problem if it's admitted beforehand so expectations are correctly set: it's a barrier to protect the naïve, not an impenetrable fortress. However, if the expectations are that only age verification that cannot be bypassed is "adequate", we only have to wait for the first incidents in production apps after which the open source and privacy story will be abandoned in the name of security.
[1] https://eprint.iacr.org/2024/2010.pdf and https://eprint.iacr.org/2022/1608.pdf
MatteoFrigo|8 months ago
Labo333|8 months ago
vvpan|8 months ago
baby|8 months ago
dungeonsndregoo|8 months ago
Sancty|8 months ago
skaramchati|8 months ago
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
dop42069|8 months ago
tucnak|8 months ago
The providers are clutching their OLAP like pearls! :-)
TuretzkyRon|8 months ago
EulerLagrange|8 months ago
[deleted]
rvr89|8 months ago
[deleted]
andy_ng|8 months ago
mumbisChungo|8 months ago
cyberax|8 months ago
0xOsprey|8 months ago
Current benchmarks for proving costs are 33k txns per dollar and we expect this to go down x10-x100 over the coming months/years.
ranger_danger|8 months ago
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?
MatteoFrigo|8 months ago
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.
est|8 months ago
endorphine|8 months ago
randomNumber7|8 months ago
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.
weinzierl|8 months ago
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
unknown|8 months ago
[deleted]
unknown|8 months ago
[deleted]
unknown|8 months ago
[deleted]
dcreater|8 months ago
wmf|8 months ago
0xOsprey|8 months ago
Our team is leveraging zkVMs for paygo.wtf
quantumgarbage|8 months ago
unknown|8 months ago
[deleted]
nielsbot|8 months ago
[deleted]
MatteoFrigo|8 months ago
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.
unknown|8 months ago
[deleted]
EGreg|8 months ago
[deleted]
MatteoFrigo|8 months ago
k__|8 months ago
That doesn't mean that part of the tech can't be used in traditional IT.
dboreham|8 months ago