Zero Knowledge Proofs

[@BizVlogs]

1:43 "Leaves on a Tree Superpower" OK, I got it: You turn your back, and have your friend pick a random number of leaves off of the tree and secretly count them. Then you use your superpower again to count the number of leaves and you reveal to your friend how many they picked. Repeat as necessary until your friend is convinced that you really do know how many leaves there are.

[@Danicker]

Wow well done! I didn't solve that one

[@riccardoandreetta9520]

very well done !! Very cool thinking about this stuff, it seems every problem has a peculiar solution ... someone is focuing right now on solving this problem on blockchains, to verify a transaction group made from someone else.

[@andreujuanc]

MIND FUCKING BLOWN

[@trompette4485]

Yeah, I found it too, I was pretty happy about that. Good job to you too!

[@davidf2244]

Brilliant

[@richbodo]

This is the best presentation I have seen on zkp theory. could use a little more love when explaining the Sudoku example, but other than that, perfect.

[@pikolo23]

I'm not a fan of Alibaba's Cave analogy. I know this isn't your fault since you didn't invent it, but still. All Peggy has to do is enter on one side and exit on the other to prove she had the key to the door. No need whatsoever for random picking, repetition, etc. But I suppose it has one property that is desirable, and that is it only Victor "must" believe her. If the video tape showed Peggy entering one side and exiting the other, then Peggy would have essentially verified her knowledge of the key to everyone, and not just victor.

[@akarin-desu]

Except, as mentioned in the video, if Victor had pre-instructed Peggy to exit the cave in a specific series (A, B, A, A, A, B, ...) it still proves nothing to outside observers. If she were given these specific instructions it’s still entirely probable she doesn’t possess the secret.

[@tedchirvasiu]

@@akarin-desu Joseph said you would watch her enter from A and observe her exiting from B. The only way she could do that is if she has the key.

[@toordog1753]

Eliminating the proofs with truth is exactly how i would accomplish this as well. Enter A, exit B; truth revealed.

[@awong7022]

6 years ago: applications: almost none in the wild :)

[@zholud]

Are there non-probabilistic protocols, so that one is convinced “with 100% probability” and after finite number of “interactions”?

[@wilfriedkopp4369]

Since you use Symmetric encryption to ‘scramble‘ the proof sent to the verifier. What prevents the verifier to partially decode the solution? After asking randomly N times he will then be able to rebuild the solution that the prover tries to keep secret.

[@stwom33]

If you're referring to the sudoku example, since this ideal computer program has _perfect_ randomization, no information about the solution can be gleaned from repeat messages. Think of the scrambling computer program as an (verify-ably) honest 3rd party, so that both Victor and Peggy have no knowledge of the key nor the cipher. Also, one of the underlying premises for that example is that both "Peggy" and "Victor" are following the protocol honestly. It is mostly a hypothetical scenario used to illustrate the principles of ZKPs.

[@xyzbesixdouze]

Well if peggy submits any good sodoku (but not the right one of the original), the randomizer will give any good rows, kolumns or blocks, and victor doesn't have proof. I think its even more simple, if u trust the programcode but Victor cannot see the imput, that the program should just check if the input is vallid with the orignal, and has all conditions of a good sudoku on rows, koloms and blocks, and just answers to victor: yes peggy has solved it. Using a third party that has access to your sollution is not a good zero proof sollution

[@ivanvaghi6246]

Scott, how does the easter egg example work?

[@AkhyarKamili]

This is amazing! Very clear presentation.

[@marcpaquin8440]

you never answered the riddles !!!!

[@stwom33]

:) I think all 3 can be googled.... Try to think on them a bit before you do, though!

[@ivanvaghi6246]

@@stwom33 I couldn't find the egg one

[@tobiasthrien1]

7:30 ... or a ONE! This is actually important. Otherwise you could break it in the same way the Enigma machine was broken.

[@rbnn]

I don’t understand this “verifiably honest” computer the prover is using and the verifier is querying. Why not just have this computer take the proof, say the sudoku solution, check the proof itself, and report to the verifier the answer if the answer is correct?

[@charlessharpe2121]

Very good presentation. Thank you for sharing

[@azarghadami3064]

In sudoku problem, why has Victor 28 choices?

[@Danicker]

9 rows, 9 columns, 9 boxes and 1 choice to reveal the original squares

[@MacroBTC]

Fantastic video!

[@invreview]

1. At 10:54, you said 'Almost none "in the wild"' as far as ZKP application is concerned. 2. Zcash was invented on 28 October 2016 3. As of 23 Aug 2018, there are over 400 global patents relating to ZKP and the 1st patent application relating to ZPF was filed in 1998.

[@tobuslieven]

2:22 I don't like the "as long as Peggy is honest" bit. It makes it sound like you have to already trust the prover. But if you trust them, then you don't need a zero knowledge proof, because when they tell you, "I have a proof," you should just believe them.

[@tiaxanderson9725]

Different kind of 'honest'. Basically if Peggy doesn't know the secret, then she can't prove it, and the conclusion of Victor will be "I think you're lying". Example with the cave: Victor asks Peggy to arrive via path A and she arrives via path B. The same is true for Victor, if he doesn't care he can just arbitrarily say: "I think you're honest". Example with the cave: Victor asks Peggy to arrive via path A, Peggy arrives via path B, and Victor says "OK, I believe you". Now a real world application of ZKP is being able to recover your password without actually answering who your first crush was. This means that Victor, the authenticator, is the website you want access to and has 0 incentive to be dishonest. And this means that Peggy, the prover, is someone who pressed the 'forgot password' button. This is either you, who forgot your password, or a hacker who wants to luck their way into an account. If the prover is indeed 'you' then you know the secret and do wish to prove it; Peggy is honest. If the prover is a hacker, they don't know the secret and will likely fail if the proof is repeated a reasonable amount of times; Peggy is dishonest. Ironically, you can even switch this around. With the help of a ZKP protocol you can even verify that Victor is who they claim they are. Again, lets assume the password recovery but this time Victor isn't Victor, but a malicious site designed to look like the real deal and trying to steal your data. As long as Peggy is dishonest (in this case giving false, but consistent data) and Victor is dishonest (they'll 'accept' anything you give them because they think you're being honest and giving them real proofs) you'll be verified by fake-Victor as real, even though you *know* the authentication should've failed. Like said in the video; an eavesdropper wouldn't be able to tell the difference between an honest and scripted ZKP exchange.

[@tomm7273]

Sudoku example is not zero-knowledge.

[@invictusev1184]

Example one sucks Peggy could start by entering path A with victor watching and victor callus stay there and then Peggy could go around through the door to path B for 100% proof...

[@invictusev1184]

Haha just saw someone else already said this whoops

[@Cherry-ug3ru]

Well explained! Thank you for this.

[@maksimivanov5417]

I don't get the sudoku example... :( Why is the proof with renumbering allowed useful? Can't the prover always respond with "123...9" to every request?

[@tiaxanderson9725]

That's where the open source software comes in; you can verify that the code does what it claims it does by.. literally seeing the code. You can compile it yourself and do tests. You can have someone else you already do trust verify it. And the re-numbering occurs so that you couldn't just tell it to show you row 1, row 2, row 3, ..., and row 9 and have the complete puzzle. Sure you'd have it substituted, but you have the real sudoku problem so you can already figure out nearly all of the substitutions (if not all) and then it's the same as just giving you the answer but with extra steps. The point is, that if I *don't* solve the puzzle, if you ask for a block, row, or column to be revealed there's a chance that there's a mistake. After all, I didn't solve the puzzle. So there are either missing spots, or double numbers in at least 1 of the 27 places (27 instead of 28 because it's excluding the original problem options). Which is also where the; there's a 27/28th chance Peggy is cheating probability comes from as long as Victor only chooses 1 option.

[@nunoalexandre6408]

Love 🎉it

[@Vrbik15]

thx for this

[@aaldaihan]

Nice Presentation, but I could barely hear you

[@jojo300001]

THEN TURN UP THE VOLUME!

[@Castle3179]

My volume is at max and I can hardly hear him either.

[@Garganzuul]

Might enable encrypted computation.

[@adrianpavelescu2781]

Great video and concise explanation.

[@AnPham-uz3td]

Actually, for this problem V only needs to stand at the trisection. Then V commands P to move to the left tunnel. If later V can appear at the right tunnel then V knows that P has the secret. With this approach we have a deterministic algorithm.

[@akarin-desu]

Sure, but V is not allowed to stand at the trisection until _after_ P has chosen a path.

[@AgenticAI]

The sound quality is so bad, it is hard to watch. Good explanation. I would love to hear with better quality sound, as it made it difficult to follow the talk. Great contribution.

[@blendedempathy]

i'm sorry. I still don't understand. Do regular blockchain tx's require the private key to be revealed? I don't believe so. Is the information being hidden the amount of coin being transacted?

[@DevinTurner18]

blendedempathy Yes, that is what coins like Zcash do, from my understanding