Understanding Zero-knowledge proofs through illustrated examples • Hacker News Board

Re: Understanding Zero-knowledge proofs through illustrated examples

#61

Post by mabbo » Fri, Dec 03, 2021, 2:09 AM UTC

vikas-kumar wrote: post #57

> Logging into a website: rather than typing your password into a potentially unsafe website, you can simply send a proof that you “know your password”. Authenticating your identity: rather than giving your mother’s maiden name over the phone to a random, bank call center agent, you can simply send a proof (a cryptographic fingerprint), that you are who you say you are. These examples tipped me off. Can someone help…

> Say one can send the exact cryptographic fingerprint and impersonate me. How is this anything better than me just sending password to authenticate?

If you're genuinely interested in this topic, you will, I think, really enjoy what I'm about to tell you.

You can setup a system where: 1- you never tell the server your plaintext password at any time, ever; 2- the server does not know your actual password and cannot determine it; 3- you can prove to the server that you know the password, and they have strong proof that you do know it; 4- nobody that eavesdrops on you can do likewise.

Cryptography is magic. And it mostly has to do with the authentication protocol being multi-step. IE: you don't just send your password or fingerprint, you send X and the server sends back Y, and you send Z, and so on and so on, but after a few steps, you have proven yourself. And since it's all being done on GHZ speed computers and gbps networks, it's fast enough for human use.

There are better algorithms than this one, evolutions on the idea, but the most common one discussed is Secure Remote Password Protocol: https://en.wikipedia.org/wiki/Secure_Remote_Password_protoco...

And honestly, I'm not even doing justice to how cool these protocols are. It's an incredible topic.

Re: Understanding Zero-knowledge proofs through illustrated examples

#62

Post by ben-ray » Fri, Dec 03, 2021, 2:17 AM UTC

vikas-kumar wrote: post #57

> Logging into a website: rather than typing your password into a potentially unsafe website, you can simply send a proof that you “know your password”. Authenticating your identity: rather than giving your mother’s maiden name over the phone to a random, bank call center agent, you can simply send a proof (a cryptographic fingerprint), that you are who you say you are. These examples tipped me off. Can someone help…

> Say one can send the exact cryptographic fingerprint and impersonate me. How is this anything better than me just sending password to authenticate?

The message can be signed with a private key to ensure you are not being impersonated. In cases where you'd also like anonymity, it is possible to add some salt as an input to the 'cryptographic fingerprint,' obfuscating the unsalted proof.

This video is good material for learning to reason about ZK proofs: https://www.youtube.com/watch?v=J3UlqJk3Kl0

Re: Understanding Zero-knowledge proofs through illustrated examples

#63

Post by vecinu » Fri, Dec 03, 2021, 2:18 AM UTC

bntyhntr wrote: post #50

I had an algorithms class (6.006 or 046?) with Silvio Micali, who I learned partway through the semester was one of the first authors about these things. Anyway, he was a great professor. When talking through algorithms, he'd always start with say, an n^4 solution. Then cut it down to n^3, call on people to help out, etc. I remember it being something like this (in an Italian accent that we really enjoyed) "And now w…

My algo class was with Charles Rackoff who I believe was a co-author to the first paper ever written on "zero knowledge proofs" for which he won a Godel prize for in the 90's.

I honestly can't remember much about the class except that it was really difficult and I haven't really used anything I learned from that class in my day to day. Hopefully there's something stored in my brain somewhere if I ever need to recall his lectures in the future.

Re: Understanding Zero-knowledge proofs through illustrated examples

#64

Post by SilasX » Fri, Dec 03, 2021, 2:33 AM UTC

frazbin wrote: post #39

dvt wrote: post #20

I'm not an expert, but coming from a logic background, I always think that ZK proofs are fudging the idea of "completeness" (and "soundness," for that matter). For example, in [1] (Definition 1.1): > We note that the constants 2/3 and 1/3 are arbitrarily chosen for simplicity. We can always amplify the completeness probability to 1 − negl(λ) and the soundness probability to negl(λ) with repetition. But that's not com…

Sure but by the same token I could guess a 256 bit key and decrypt anything I want. The placement of the statistical boundary vs a given adversary compute power is the part we care about, every time.

Yes, these proof protocols allow you to get arbitrary certainty very quickly, so there’s little practical difference.

Scott Aaronson (of quantum computing and P=NP blogging fame) likes to joke that, “okay, fine fine, so these statistical proofs are good enough for the launch codes, military encryption, and multi-billion dollar financial transactions… but what about theorem proving, where you just can’t take any chances?”

Re: Understanding Zero-knowledge proofs through illustrated examples

#65

Post by Ar-Curunir » Fri, Dec 03, 2021, 2:33 AM UTC

dvt wrote: post #20

I'm not an expert, but coming from a logic background, I always think that ZK proofs are fudging the idea of "completeness" (and "soundness," for that matter). For example, in [1] (Definition 1.1): > We note that the constants 2/3 and 1/3 are arbitrarily chosen for simplicity. We can always amplify the completeness probability to 1 − negl(λ) and the soundness probability to negl(λ) with repetition. But that's not com…

Right, but that astronomical probability is, as you say astronomical. In fact, it’s even better: even i have you a number of trials equal to the number of atoms in the h overs, your expected number of wins would still be astronomically small.

Re: Understanding Zero-knowledge proofs through illustrated examples

#66

Post by chaboud » Fri, Dec 03, 2021, 3:15 AM UTC

aan1092j wrote: post #15

Kranar wrote: post #14

Earlier quoted context omitted.

Giving a candidate set of moves that results in a checkmate does not prove that said checkmate was forced. I can provide a candidate set of moves that results in a checkmate after 3 moves (the classic Blitzkrieg), and certainly you can verify that in polynomial time, but that does not mean that it's possible to force a checkmate in 3 moves. To the best that anyone knows, for a generalized chess board of size WxW, to…

Ah my bad. I wrote hastily and did not consider the full implication of the word `forced`, i.e. it would involve proving the opponent has no winning options.

Mate can be forced in N moves. This generally requires involvement of the king (e.g., check, no other pieces, guarding of the king) such that the only legal moves remaining are dictated by the positioning of the attacker.

Re: Understanding Zero-knowledge proofs through illustrated examples

#67

Post by spir » Fri, Dec 03, 2021, 3:31 AM UTC

StarkNet is a turing complete virtual machine built on top of zero-knowledge proofs.

The output of any StarkNet program can be transformed into an extremely succinct zero-knowledge proof. This proof generation process is quite costly. But then, the proof itself is extremely tiny and may be verified extremely inexpensively.

Coincidentally with this post, StarkNet launched this week after seven years of R&D.

https://starkware.co/starknet/

Re: Understanding Zero-knowledge proofs through illustrated examples

#68

Post by chaboud » Fri, Dec 03, 2021, 3:35 AM UTC

fiatjaf wrote: post #55

dan-robertson wrote: post #53

Earlier quoted context omitted.

The face up and face down cards would really be numbers, and the “machine” means applying some algorithm to the numbers to combine and then check them. Bob could do that by himself. The key idea is that these numbers somehow don’t reveal which digit goes where.

Why can't Bob just look at all cards as he pleases?

Typically the “mixing of the cards” is done via a one-way function (e.g., modular arithmetic), making it impractical to fake and impractical to reverse.

Re: Understanding Zero-knowledge proofs through illustrated examples

#69

Post by xrd » Fri, Dec 03, 2021, 3:42 AM UTC

This is great.

Have to say, after reading several tutorials on different languages that allow you to build zk proof circuits, it still seems very difficult to encode the problem a priori into them such that the result is useful. For example, using them in cryptocurrency seems tricky because you often have to encode the actors involved (by way of their addresses) in advance when you put the zkSNARK on the chain, which makes that less useful.

I really enjoyed Cairo tutorials which have similar concepts.

https://www.cairo-lang.org/docs/hello_cairo/puzzle.html

Re: Understanding Zero-knowledge proofs through illustrated examples

#70

Post by lngnmn2 » Fri, Dec 03, 2021, 3:54 AM UTC

This is a sect and abuse of a language in which words supposed to be associated with particular non-imaginary aspects of reality.

Logic "works" not because its rules are absolute, but because Universe has its structure and laws. Ignoring validity and non-contradiction of premises renders any conclusions meaningless (merely abstract Hegelian bullshit).

Causes (and premises) are not arbitrary so the assumption that everything can be deduced (proved) from anything is bullshit.

Applied math require a type discipline and abstract math is just a set of rules, like abstract logic. And this is my contribution to science.