Understanding Zero-knowledge proofs through illustrated examples • Hacker News Board

Re: Understanding Zero-knowledge proofs through illustrated examples

#81

Post by JofArnold » Fri, Dec 03, 2021, 9:35 AM UTC

omeze wrote: post #48

JofArnold wrote: post #4

In addition to Nalin's great sudoku example elsewhere, here's a couple of my repos that use SNARKS: 1) Some experiments/learnings https://github.com/JofArnold/zkp-learning-in-public 2) A blockchain-based Dungeon crawler built for a hackathon that uses a SNARK (Circom, snarkjs) to validate that the user hasn't cheated when getting to the end of the maze https://github.com/Derked/FantasyCampaign

Wow, fantasy campaign is the first crypto-native game that actually looks like it could be _fun_ (as an avid gamer, it pains me to see stuff like Axie Infinity as the poster child for "web3 games"). A roguelike with re-usable /remixable items across games and players would be super fun to play!

Thanks. It was a very fast last-minute hack and the frontend code's a bit buggy! Plus, we need to make some major changes to how it works since at present some of the decisions were made to promote the Chainlink integration make it much more cumbersome than it needs to be.

We briefly considered making this a completely open-source, decentralized thing completely controlled by the community. Your comment has definitely made us a bit more motivated to do that!

I'm completely onboard with the Axie thing. It's an interesting start but I think these kinds of play-to-earn models are fairly toxic.

Re: Understanding Zero-knowledge proofs through illustrated examples

#82

Post by [deleted] » Fri, Dec 03, 2021, 11:23 AM UTC

jstanley wrote: post #7

Does anyone know if all provable things are zero-knowledge provable? As an example: given a chess position, would you be able to construct a zero-knowledge proof that you can force checkmate in N moves or less without revealing anything about the particular moves involved? If so, what would such a proof look like?

[deleted]

Re: Understanding Zero-knowledge proofs through illustrated examples

#83

Post by alanfranz » Fri, Dec 03, 2021, 1:04 PM UTC

runeks wrote: post #74

alanfranz wrote: post #72

Earlier quoted context omitted.

Why would you leverage signatures? An hash would be enough for showing knowledge. Maybe you meant you needed to show proof that only you (not somebody else) knows some data? Even for such scenario I would not be sure it’s correct. Many signature implementations hash the data, then sign the hash; if I happen to know the hash but not the data, I could just sign it without owning it. (I should verify a few things, this…

> Why would you leverage signatures? Because in order to verify that a hash over some secret data is correct you need access to the secret data, which makes it pointless. Only using a signature can the signer prove that they have knowledge of a secret number (their private key) by providing information that does not reveal the secret (public key, message hash, signature).

> Because in order to verify that a hash over some secret data is correct you need access to the secret data, which makes it pointless.

No. You could have access to the hash.

For the private/public key signing, of course; the signature guarantees that you have access to the private key. But if the ‘private secret data’ is not the private key?

Re: Understanding Zero-knowledge proofs through illustrated examples

#84

Post by tzs » Fri, Dec 03, 2021, 1:36 PM UTC

I first heard of ZKPs in the context of mathematical theorems rather than cryptographic protocols, probably sometime in the late '80s I think and probably from an article in the MAA's "Focus" magazine.

If I remember correctly the article said that it is possible for any given mathematical theorem and proof it is possible to produce a graph such that (1) the proof is correct if and only if the graph has a Hamiltonian circuit, and (2) you can show people the graph and prove to them that it is such a graph for that theorem.

The article then gave a ZKP scheme for showing that you know a Hamiltonian circuit on a given graph.

Putting it all together then someone who claimed to have a proof of the Riemann Hypothesis or Goldbach's Conjecture or any other famous unsolved mathematical problem could produce the corresponding graph, and produce a ZKP that they know a Hamiltonian circuit for that graph, and we'd have to accept that they have in fact solved the problem.

I wonder what would happen if someone actually did that for one of the Millennium Prize Problems [1] or some other high profile problem that has a substantial reward behind it? When offering prizes for proofs nowadays should you include a clause in the rules that states to win the prize you have to publish a conventional proof?

[1] https://en.wikipedia.org/wiki/Millennium_Prize_Problems

Re: Understanding Zero-knowledge proofs through illustrated examples

#85

Post by runeks » Sat, Dec 04, 2021, 10:10 AM UTC

alanfranz wrote: post #83

runeks wrote: post #74

Earlier quoted context omitted.

> Why would you leverage signatures? Because in order to verify that a hash over some secret data is correct you need access to the secret data, which makes it pointless. Only using a signature can the signer prove that they have knowledge of a secret number (their private key) by providing information that does not reveal the secret (public key, message hash, signature).

> Because in order to verify that a hash over some secret data is correct you need access to the secret data, which makes it pointless. No. You could have access to the hash. For the private/public key signing, of course; the signature guarantees that you have access to the private key. But if the ‘private secret data’ is not the private key?

> But if the ‘private secret data’ is not the private key?

It is in the example you were replying to. That’s my point.

Re: Understanding Zero-knowledge proofs through illustrated examples

#86

Post by spir » Sat, Dec 04, 2021, 8:57 PM UTC

runeks wrote: post #75

spir wrote: post #67

StarkNet is a turing complete virtual machine built on top of zero-knowledge proofs. The output of any StarkNet program can be transformed into an extremely succinct zero-knowledge proof. This proof generation process is quite costly. But then, the proof itself is extremely tiny and may be verified extremely inexpensively. Coincidentally with this post, StarkNet launched this week after seven years of R&D. https://st…

Interesting! > This proof generation process is quite costly. Where can I find some benchmarks for creating various proofs? This technology can be groundbreaking or useless solely depending on how long it takes to create a given proof.

I don't have stats on that, but I'm sure the StarkWare community would love to help

- a recent tweet by StarkWare President Eli on some performance stats https://twitter.com/EliBenSasson/status/1467161132569931784

- StarkWare discord server https://t.co/klHVDhQokP

- StarkWare research forum https://community.starknet.io/