Zero-Knowledge Proofs | Hacker News Reader

Zero-Knowledge Proofs

zkp.science

142 pointsexolymph21 comments

If anyone's interested in working with SNARKs - I'm the primary author of snarky (the OCaml SNARK DSL linked in the above website). It's being used in the development of Coda[0] and we're hiring.

[0]: https://codaprotocol.com

Coda is awesome!

Glad to see someone is addressing the bloat problem. Kinda sucks that every time we improve blockchain design we have to start from scratch with a new chain though.

Have you heard about merged mining? It’s when one chain recognizes the mining being done on another chain. In some way, you aren’t restarting from scratch.

Also, the code powering each cryptocurencies isn’t immutable. People adopt changes; just not at the same pace as most other pieces of software.

What level of experience are you looking for in the protocol engineer role? It checks every box I'm looking for w/r/t my personal interests but I fear that since "junior" isn't in the title that I would not easily qualify.

I just lost 10 minutes reading your whitepaper, and your claims are quite bait-clicky. Yes, your blockchain will be "instant sync", but only for light clients. Just like with any other blockchain, you still need full nodes that stores every transaction, to serve all the light clients. Light wallets are not new in this space, so I wonder what's the innovation in your proposal, apart from using bleeding edge tech like zk-SNARK.

Ordinarily, light wallets compromise on validating blocks, so that’s one benefit.

Light wallets validates blocks by checking PoW in their headers. In Bitcoin, a header is 80 byte long, that's about 40MB as of today (~500k blocks since inception). Saving 39.9 MB on light wallets isn't worth starting a new blockchain.

No, my point is that light wallets don’t validate the content of blocks...so an attacker could create a long chain of invalid blocks and fool light clients. That’s a significant issue.

On this point, light wallets are just as protected as full node. Light wallets are able to validate blocks just from their header, thanks to the structure of a block. Indeed, all transactions in a block are commited in a merkle root hash that is included in the block header, therefore it's impossible to invent fake transactions without forging a whole new branch of blocks, from the fake block up to the last block. Just like for a full node ! Light wallets are not perfect though, potential attacks are summed up here, slide 13: https://breaking-bitcoin.com/slides/SPVSecurity.pdf Coda doesn't improve on this issues at all.

Also, argument of authority: I work for a wallet provider

I’m not sure why there is a misunderstanding here, especially given that you work for a wallet provider. The attack is as described: an attacker forks, mines invalid blocks, which are caught by full nodes, since they validate the contents of blocks, but not by the light client - assume for simplicity that the client connects to the malicious node and doesn’t do anything more than calculate PoW. The SPV client trusts an invalid blockchain, fault occurs. Coda is designed precisely to avoid this problem, and any solution that requires trusting full nodes, because it provides constant time verification of all of the contents of every block.

Coda seems interesting, but I don’t understand how a single feature (fast light client syncing) can be enough of an advantage to launch a new chain - what prevents a new chain from incorporating recursive snarks as well as some new X in the future? Also, I think that the security of recursively computed snarks decreases as the recursion depth increases so for a state transition in a sufficiently long chain, you might only have a few bits of security, but I’m not sure what “sufficiently long” means concretely.

> I think that the security of recursively computed snarks decreases as the recursion depth increases

These proof systems are parameterized to ensure a certain soundness error, like 2^-128. So as long as certain cryptographic assumptions hold (in the case of SNARKs, the hardness of knowledge-of-exponent and commitments), it would take an attacker an expected 2^128 brute force attempts to generate an invalid proof. That should remain the same no matter how deep the recursion goes.

Yes, I agree that the top-level SNARK will obviously have a high level of security wrt soundness, but suppose that I have a SNARK recursively computing 2^128 SNARKs, you’re claiming that the lowest level SNARK would have the same knowledge soundness guarantees? That seems incorrect given the constant size of the top-level SNARK

I don't quite understand where the doubt is coming from; why would recursion depth affect security?

The security proof for SNARKs requires constant-depth compliance predicates, otherwise the proof doesn’t follow because the extractor size could blow up. I would have to read the coda whitepaper to see what their assumptions are for their security proof. I was just curious whether the equivalent of a birthday attack would be possible for some state transition if the depth was increased, since I’m not aware of a formal proof of soundness (and I heard in passing that recursion depth would affect security properties of nested snarks, but hearsay!)

I don't think circuit depth matters for SNARKs? Though there are other proof systems where AND depth matters.

Also, though I haven't read the CODA paper either, I think they would only need a single fixed circuit containing a SNARK verifier. Since for a given security level, SNARK sizes and verification steps are constant.

This is great. I'd love to see something like the Computer Language Benchmark Game[0] but for these proof systems. In the meantime, you can find some interesting benchmark experiments in the papers for Hyrax[1] and STARKs[2]. I'm sure there's a lot more out there, but these are some hard numbers that I've come across. I'm a newbie when it comes to this stuff but it's really exciting to see all the progress.

[0] https://benchmarksgame-team.pages.debian.net/benchmarksgame/ [1] https://eprint.iacr.org/2017/1132.pdf (Section 8) [2] https://eprint.iacr.org/2018/046.pdf (Section 1.3.2)

I would add Katz et al's proof system: https://eprint.iacr.org/2018/475

It has very practical proof times and sizes for a certain range of circuit sizes. E.g. we can prove knowledge of a LowMC-256 key with ~40kb, making it on par with SPHINCS for post-quantum signatures. No implementation yet, but they're working on one.

I wrote a primer on ZKPs[1], with a follow up post[2] that proves and implements ZKPs for 3-coloring (mentioned in the first link of the article, but not proved) in Python, and a third post[3] that gets into more nitty gritty theoretical details about computational and statistical zero knowledge that were swept under the rug in [2].

[1]: https://jeremykun.com/2016/07/05/zero-knowledge-proofs-a-pri...

[2]: https://jeremykun.com/2016/08/01/zero-knowledge-proofs-for-n...

[3]: https://jeremykun.com/2016/09/19/zero-knowledge-definitions-...

I should add, the implementations are neither secure nor fast, but rather designed for ease of human understanding.

Reply on news.ycombinator.com