4 ms·

Computer scientists combine two 'beautiful' proof methods

119 points by tambourine_man 2y ago

ChadNauseam 2y ago
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 program was truly produced from the inputs[^1], and continued to do more research like this. While I’m not a cryptographer, I think this sort of thing is super cool and I’m glad there’s a lot of attention and effort going into it. ^[1] the cool thing about these proofs is that they can be verified in much less time than is required to run the program. IIRC, starks can be verified in log-polynomial time, and snarks can be verified in constant time. This allows cryptocurrency protocols to have one computer in the network generate a proof of the state of the chain given a new block, and all other are able to quickly check it. Without this, you have a ton of waste because every computer in the network must duplicate the work of computing the new chain state. (although some new waste is introduced by the fact that producing a proof is very slow, although this is another area that cryptocurrency-funded research has improved dramatically) Another cool bit of cryptography research that I think was motivated by crypto was “verkle trees”, an improvement on merkle trees that uses vector commitments rather than your typical hash. A vector commitment is like a hash, but it hashes an array of items and you can check that the hash was produced from an array with a certain item at a certain index without knowing the other items in the array. If you use this to back a merkle tree, you can increase the branching factor a lot and end up with much smaller proofs that a particular item is in the tree. This is because the proof size for a merkle tree is b * log_b n (where b is the branching factor and n is the number of items in the tree). The proof size for a verkle tree is just log_b n, so you can increase b as much as you want without making the proofs bigger. Full disclosure: I work for a blockchain company, but not one mentioned here. I have no equity or stake in crypto outside of the fact that if the price goes to 0 my company probably can no longer afford to employ me
- monero-xmr 2y ago
  [dead]
- joshuamorton 2y ago
  > The article claims that this research was developed for StarkWare, Does it? Starkware is mentioned only as the company run by some.guy who commented on how pivotal this work was. It doesn't say he was related, and I can't find any affiliation between the researchers (all uk based at Cambridge and Warwick) and the US based StarkWare.
  - ChadNauseam 2y ago
    Oh, maybe it was unrelated, I think I misread the article
- treyd 2y ago
  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.
  - ChadNauseam 2y ago
    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
    - a1369209993 2y ago
      > vitalik didn't credit him in his article You mean this article? https://vitalik.eth.limo/general/2021/06/18/verkle.html https://vitalik.eth.limo/general/2021/06/18/verkle.html > Verkle trees are still a new idea; they were first introduced by John Kuszmaul in this paper from 2018[link to [0]], 0: https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf https://math.mit.edu/research/highschool/primes/materials/20...
ianandrich 2y ago
I know this is useful for crypto, but I think think I'm actually more interested in what new modes of remote code running on untrusted platforms this enables.
- drhodes 2y ago
  It does seem like the article touches on concerns relevant to homomorphic encryption. Maybe someone knows if there is a connection.
- ChadNauseam 2y ago
  That is exactly the reason it's useful for crypto, nodes need to verify the output of code running on other nodes without trusting them.
- Ar-Curunir 2y ago
  This scheme in particular is not useful for cryptocurrencies; we already knew how to make efficient zkSNARKs with perfect zero-knowledge before this result. This paper is a beautiful work of theory.
scotty79 2y ago
> 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?
- JohnKemeny 2y ago
  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.
  - JohnKemeny 2y ago
    Verifying that a path/tour is shortest is in co-NP.
  - Zamiel_Snawley 2y ago
    I think this is a great distinction that deserves elaboration for those less familiar with the topic. Can you explain a bit further?
    - ChadNauseam 2y ago
      A decision problem is a problem with a yes or no answer. An NP problem is one where a "yes" answer can be verified quickly if they also give you some proof or "witness" of it. If I say "is there a route that goes through all these cities that's less than 500 miles long", and you answer yes, you can prove that such a route exists by showing me one of these and I can simply check how long the route is. So the problem is in NP because a "yes" answer can be proven or checked quickly. However, if you say "no, there is no such route", there's not obviously any way to quickly show that. Despite that, the problem is still in NP because to be in NP there only needs to be a quickly-checkable proof of a "yes" answer. If you want a quickly checkable proof of a "no" answer, you need a separate class of problem called co-np. A problem can also be in np and co-np at the same time, if both "yes" answers and "no" answers can have a proof that can be checked quickly.
ziofill 2y ago
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.”
- firejake308 2y ago
  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 appreciate an ELI5 from anyone who has one.
  - jonjonsonjr 2y ago
    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.
    - zmgsabst 2y ago
      Or they have a way to measure your removal, eg, they don’t count leaves but branches without leaves (in the hypothetical tree example).
- ChadNauseam 2y ago
  This is a nice example, but couldn't he add a constant to his count as long as he adds the same constant each time? Regardless, it's nice
- auggierose 2y ago
plank 2y ago
There seems to be a problem with the article: the example shown is with colouring the map. But showing two adjacent regions to have different colours proves nothing: they will always be different (if colouring is possible). Perhaps if one shows two regions that do not share a border, and state that they are or are not the same colour...
- kevinwang 2y ago
  I think the example is fine. Two adjacent regions will indeed always be different if the coloring is correct. But it may not be if the coloring is incorrect.
ljlolel 2y ago
I once took a graduate level course at Princeton and the whole course for months was just spent understanding step by step the PCP proof. It was beautiful and subtle and had layers of complexity built on itself in layers. It was very hard —I can’t say I got it fully. (Arora himself taught it) Zero knowledge proofs are way simpler to understand but also brilliant. I applaud Quanta's effort to try to explain both these concepts. I love to learn the limits of our knowledge and what is provable and how to exploit that for fun and profit.

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 program was truly produced from the inputs[^1], and continued to do more research like this. While I’m not a cryptographer, I think this sort of thing is super cool and I’m glad there’s a lot of attention and effort going into it. ^[1] the cool thing about these proofs is that they can be verified in much less time than is required to run the program. IIRC, starks can be verified in log-polynomial time, and snarks can be verified in constant time. This allows cryptocurrency protocols to have one computer in the network generate a proof of the state of the chain given a new block, and all other are able to quickly check it. Without this, you have a ton of waste because every computer in the network must duplicate the work of computing the new chain state. (although some new waste is introduced by the fact that producing a proof is very slow, although this is another area that cryptocurrency-funded research has improved dramatically) Another cool bit of cryptography research that I think was motivated by crypto was “verkle trees”, an improvement on merkle trees that uses vector commitments rather than your typical hash. A vector commitment is like a hash, but it hashes an array of items and you can check that the hash was produced from an array with a certain item at a certain index without knowing the other items in the array. If you use this to back a merkle tree, you can increase the branching factor a lot and end up with much smaller proofs that a particular item is in the tree. This is because the proof size for a merkle tree is b * log_b n (where b is the branching factor and n is the number of items in the tree). The proof size for a verkle tree is just log_b n, so you can increase b as much as you want without making the proofs bigger. Full disclosure: I work for a blockchain company, but not one mentioned here. I have no equity or stake in crypto outside of the fact that if the price goes to 0 my company probably can no longer afford to employ me

monero-xmr 2y ago
[dead]
joshuamorton 2y ago
> The article claims that this research was developed for StarkWare, Does it? Starkware is mentioned only as the company run by some.guy who commented on how pivotal this work was. It doesn't say he was related, and I can't find any affiliation between the researchers (all uk based at Cambridge and Warwick) and the US based StarkWare.
- ChadNauseam 2y ago
  Oh, maybe it was unrelated, I think I misread the article
treyd 2y ago
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.
- ChadNauseam 2y ago
  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
  - a1369209993 2y ago
    > vitalik didn't credit him in his article You mean this article? https://vitalik.eth.limo/general/2021/06/18/verkle.html https://vitalik.eth.limo/general/2021/06/18/verkle.html > Verkle trees are still a new idea; they were first introduced by John Kuszmaul in this paper from 2018[link to [0]], 0: https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf https://math.mit.edu/research/highschool/primes/materials/20...

ianandrich 2y ago

I know this is useful for crypto, but I think think I'm actually more interested in what new modes of remote code running on untrusted platforms this enables.

drhodes 2y ago
It does seem like the article touches on concerns relevant to homomorphic encryption. Maybe someone knows if there is a connection.
ChadNauseam 2y ago
That is exactly the reason it's useful for crypto, nodes need to verify the output of code running on other nodes without trusting them.
Ar-Curunir 2y ago
This scheme in particular is not useful for cryptocurrencies; we already knew how to make efficient zkSNARKs with perfect zero-knowledge before this result. This paper is a beautiful work of theory.

scotty79 2y ago

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

JohnKemeny 2y ago
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.
- JohnKemeny 2y ago
  Verifying that a path/tour is shortest is in co-NP.
- Zamiel_Snawley 2y ago
  I think this is a great distinction that deserves elaboration for those less familiar with the topic. Can you explain a bit further?
  - ChadNauseam 2y ago
    A decision problem is a problem with a yes or no answer. An NP problem is one where a "yes" answer can be verified quickly if they also give you some proof or "witness" of it. If I say "is there a route that goes through all these cities that's less than 500 miles long", and you answer yes, you can prove that such a route exists by showing me one of these and I can simply check how long the route is. So the problem is in NP because a "yes" answer can be proven or checked quickly. However, if you say "no, there is no such route", there's not obviously any way to quickly show that. Despite that, the problem is still in NP because to be in NP there only needs to be a quickly-checkable proof of a "yes" answer. If you want a quickly checkable proof of a "no" answer, you need a separate class of problem called co-np. A problem can also be in np and co-np at the same time, if both "yes" answers and "no" answers can have a proof that can be checked quickly.

ziofill 2y ago

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

firejake308 2y ago
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 appreciate an ELI5 from anyone who has one.
- jonjonsonjr 2y ago
  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.
  - zmgsabst 2y ago
    Or they have a way to measure your removal, eg, they don’t count leaves but branches without leaves (in the hypothetical tree example).
ChadNauseam 2y ago
This is a nice example, but couldn't he add a constant to his count as long as he adds the same constant each time? Regardless, it's nice
auggierose 2y ago

plank 2y ago

There seems to be a problem with the article: the example shown is with colouring the map. But showing two adjacent regions to have different colours proves nothing: they will always be different (if colouring is possible). Perhaps if one shows two regions that do not share a border, and state that they are or are not the same colour...

kevinwang 2y ago
I think the example is fine. Two adjacent regions will indeed always be different if the coloring is correct. But it may not be if the coloring is incorrect.

ljlolel 2y ago

I once took a graduate level course at Princeton and the whole course for months was just spent understanding step by step the PCP proof. It was beautiful and subtle and had layers of complexity built on itself in layers. It was very hard —I can’t say I got it fully. (Arora himself taught it) Zero knowledge proofs are way simpler to understand but also brilliant. I applaud Quanta's effort to try to explain both these concepts. I love to learn the limits of our knowledge and what is provable and how to exploit that for fun and profit.