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

161–170 of 217 posts

Re: Opening up ‘Zero-Knowledge Proof’ technology

#161

Post by djrj477dhsnv »

koalaman wrote: post #75
djoldman wrote: post #69

Earlier quoted context omitted.

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.

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.

Re: Opening up ‘Zero-Knowledge Proof’ technology

#162

Post by _alternator_ »

remram wrote: post #154
_alternator_ wrote: post #130

Earlier quoted context omitted.

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

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)

Re: Opening up ‘Zero-Knowledge Proof’ technology

#163

Post by [deleted] »

[deleted] wrote: post #156
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…

[deleted]

[deleted]

Re: Opening up ‘Zero-Knowledge Proof’ technology

#164

Post by nixpulvis »

abhv wrote: post #44
coldpie wrote: post #38

Earlier quoted context omitted.

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…

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

Re: Opening up ‘Zero-Knowledge Proof’ technology

#165

Post by jlokier »

remram wrote: post #154
_alternator_ wrote: post #130

Earlier quoted context omitted.

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

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?

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.

Re: Opening up ‘Zero-Knowledge Proof’ technology

#167

Post by throwaway290 »

miki123211 wrote: post #94
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.

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

> 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

Re: Opening up ‘Zero-Knowledge Proof’ technology

#168

Post by CJefferson »

djoldman wrote: post #80
trollbridge wrote: post #71

Earlier quoted context omitted.

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

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

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.

Re: Opening up ‘Zero-Knowledge Proof’ technology

#169

Post by throwaway290 »

prophesi wrote: post #133
heavyset_go wrote: post #61

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