[HN Gopher] Computer scientists combine two 'beautiful' proof me...
___________________________________________________________________
Computer scientists combine two 'beautiful' proof methods
Author : tambourine_man
Score : 63 points
Date : 2024-10-04 13:48 UTC (9 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| ChadNauseam wrote:
| 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
| joshuamorton wrote:
| > 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 wrote:
| Oh, maybe it was unrelated, I think I misread the article
| treyd wrote:
| 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 wrote:
| 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
| ianandrich wrote:
| 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 wrote:
| It does seem like the article touches on concerns relevant to
| homomorphic encryption. Maybe someone knows if there is a
| connection.
| ChadNauseam wrote:
| 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.
| scotty79 wrote:
| > 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 wrote:
| 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 wrote:
| Verifying that a path/tour is shortest is in co-NP.
___________________________________________________________________
(page generated 2024-10-04 23:00 UTC)