Computer scientists combine two 'beautiful' proof methods
quantamagazine.org
Computer scientists combine two 'beautiful' proof methods
1–10 of 32 posts
Re: Computer scientists combine two 'beautiful' proof methods
#2I 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
Re: Computer scientists combine two 'beautiful' proof methods
#3I 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…
[dead]
Re: Computer scientists combine two 'beautiful' proof methods
#4I 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 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.
Re: Computer scientists combine two 'beautiful' proof methods
#5I 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.
Re: Computer scientists combine two 'beautiful' proof methods
#6I 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.
Re: Computer scientists combine two 'beautiful' proof methods
#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?
Re: Computer scientists combine two 'beautiful' proof methods
#8I 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.
It does seem like the article touches on concerns relevant to homomorphic encryption. Maybe someone knows if there is a connection.
Re: Computer scientists combine two 'beautiful' proof methods
#9> 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.
Re: Computer scientists combine two 'beautiful' proof methods
#10> 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.
Verifying that a path/tour is shortest is in co-NP.