Computer scientists combine two 'beautiful' proof methods

Post by ChadNauseam » Fri, Oct 04, 2024, 10:13 PM UTC

treyd wrote: post #6

ChadNauseam wrote: post #2

I know cryptocurrencies have a lot of problems, but this is one place where it’s good they exist: they’ve funneled a ton of money into researching new cryptography. The article claims that this research was developed for StarkWare, which developed its own form of zero knowledge proofs they called Starks, developed a programming language in which cryptographic proofs can be generated showing that the output of the pro…

The other cool thing about verkle trees is that they were mostly figured out by a high schooler for a science fair (?) project. They're not actually that complicated in principle, just nobody thought of it before and that's pretty cool.

Post by a1369209993 » Fri, Oct 04, 2024, 11:08 PM UTC

ChadNauseam wrote: post #12

treyd wrote: post #6

Earlier quoted context omitted.

The other cool thing about verkle trees is that they were mostly figured out by a high schooler for a science fair (?) project. They're not actually that complicated in principle, just nobody thought of it before and that's pretty cool.

Wow, that is cool. I'm actually annoyed that vitalik didn't credit him in his article about them. I wonder how many people think that the v stands for vitalk

Post by Zamiel_Snawley » Sat, Oct 05, 2024, 2:03 AM UTC

JohnKemeny wrote: post #9

scotty79 wrote: post #7

> If someone finds a valid solution, they can easily convince a skeptical “verifier” that it really is valid. The verifier, in turn, will always be able to spot if there’s a mistake. Problems with this property belong to a class that researchers call NP. How do you quickly verify that traveling salesman path is indeed the shortest one?

You have discovered that that problem indeed is not in NP, for the reason that it is not a decision problem. The decision problem is in NP, and there the problem is: given a graph and some value k, does there exist a TSP with cost at most k. You can see how that problem then becomes verifiable.

Post by firejake308 » Sat, Oct 05, 2024, 2:57 AM UTC

ziofill wrote: post #17

A professor I know once gave me the most beautiful example of a zero knowledge proof: she said “Imagine I want to prove to you that I can count the leaves on a tree, but I don’t want to reveal how I do it. I start by telling you there are e.g. 756,912 of them. Then I close my eyes and I let you remove as many as you want. We can keep going until you are convinced, and you still won’t know how I did it.”

Post by zmgsabst » Sat, Oct 05, 2024, 5:40 AM UTC

jonjonsonjr wrote: post #19

firejake308 wrote: post #18

Earlier quoted context omitted.

Okay, but I wouldn't be convinced until I've counted up to 756,912 myself and seen that there are no more leaves left after that. Isn't it supposed to be less computationally intensive to verify the proof than to complete the original calculation? I tried learning about zero knowledge proofs during the crypto craze, but I never understood the basic idea of how it was supposed to work, much less the math involved. I'd…

The proof is that they can tell you the number of leaves (again) after you have secretly removed some. Since only you know the number you removed, if the difference between their counts matches your number, it is likely that they can indeed count the leaves on the tree. It is possible they have correctly guessed, which is why you repeat the challenge until you are convinced.