Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Opening up ‘Zero-Knowledge Proof’ technology

blog.google

Post reply on HN
Print view View original

181–190 of 217 posts

Re: Opening up ‘Zero-Knowledge Proof’ technology

#181

Post by MatteoFrigo »

hrdwdmrbl wrote: post #144

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

Re: Opening up ‘Zero-Knowledge Proof’ technology

#182

Post by MatteoFrigo »

coldpie wrote: post #66
MatteoFrigo wrote: post #60

Earlier quoted context omitted.

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.

Re: Opening up ‘Zero-Knowledge Proof’ technology

#183

Post by MatteoFrigo »

nixpulvis wrote: post #164
abhv wrote: post #44

Earlier quoted context omitted.

(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…

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.

Re: Opening up ‘Zero-Knowledge Proof’ technology

#184

Post by edanm »

yababa_y wrote: post #119
deegles wrote: post #113

Earlier quoted context omitted.

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.

Re: Opening up ‘Zero-Knowledge Proof’ technology

#185

Post by a_tartaruga »

bobbiechen wrote: post #29

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…

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.

Re: Opening up ‘Zero-Knowledge Proof’ technology

#186

Post by regularfry »

heavyset_go wrote: post #61
regularfry wrote: post #50

Earlier quoted context omitted.

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.

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

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.

Re: Opening up ‘Zero-Knowledge Proof’ technology

#187

Post by regularfry »

gmueckl wrote: post #65
regularfry wrote: post #50

Earlier quoted context omitted.

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.

Is that what happens in this specific case?

Re: Opening up ‘Zero-Knowledge Proof’ technology

#188

Post by MatteoFrigo »

bobbiechen wrote: post #118
quantumgarbage wrote: post #78

Earlier quoted context omitted.

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.

Re: Opening up ‘Zero-Knowledge Proof’ technology

#189

Post by piracyrules »

djoldman wrote: post #69
api wrote: post #8

Earlier quoted context omitted.

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.

[dead]

Re: Opening up ‘Zero-Knowledge Proof’ technology

#190

Post by a_tartaruga »

hrdwdmrbl wrote: post #144

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.

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.
Post reply on HN