11–20 of 29 posts
I wasn't aware of the huge space requirements to use a proving key. That's somewhat limiting, although we do have the advantage that we have a (mobile) wallet we could potentially allow running ZKSnark inside. Are you aware of any work on that side?
Web2.0 boomer here. Can someone ELI5 what is an, "Airdrop?"
In cryptocurrency, an "airdrop" refers to receiving free tokens in your wallet. Some times they're designed to incentivize certain activities, like promoting the coin or participating in something. As a marketing tactic, they work quite well. Crypto fans will do surprisingly large amounts of free PR and free work for "free" tokens. From an economic perspective, if a token system is giving out free money to large numb…
If you squint even Bitcoin had an airdrop: Bitcoin has been in an inflationary regime for its entire history and for a while was giving out Bitcoin to anybody who ran the right program on their laptop.
Is there a good way of reasoning about what type of ideas this unlocks?
If anyone is curious, here are a couple pointers to related work on problems similar to this.
First, the ideas used here are vaguely related to the way that ZCash works under the hood. The ideas in ZCash come from a sequence of three academic papers: ZeroCoin, PinocchioCoin, and Zerocash:
- ZeroCoin: http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf
- PinocchioCoin: https://www.microsoft.com/en-us/research/wp-content/uploads/...
- Zerocash: https://eprint.iacr.org/2014/349
More directly related in terms of application, but quite different in mechanism: the Handshake airdrop in early 2020 could be claimed anonymously. This was slightly tricky because the idea was to retrofit to existing RSA keys. We (full disclosure, I worked on this project) called the resulting protocol a "GooSig":
- GooSigs: https://eprint.iacr.org/2020/676
Section 3 of that paper gives a way of anonymously airdropping to existing ECDSA or EdDSA keys without using a SNARK. The setup may not be quite the same as in the case being discussed above, though. Notably, it requires sending a short message to the recipient before they can claim their funds. But the message can be encrypted to an existing key of theirs and posted publicly, so this probably isn't much of a limitation in many practical cases.
> ECDSA inside ZK-SNARKs is a starting point that unlocks many other ideas! Is there a good way of reasoning about what type of ideas this unlocks?
At the bottom, this lets you prove that you know a signature without revealing what that signature is. This idea has been used in anonymous credential systems---much like this one! In the cryptographic literature, the underlying idea goes back to David Chaum ("Blind signatures for untraceable payment," Crypto 1982) and as far as I know the first implementation was Camenisch and Lysyanskya ("An efficient system for non-transferable anonymous credentials with optional anonymity revocation", Eurocrypt 2001).
Even without the zero-knowledge property this idea is useful, essentially because the "K" in "SNARK" stands for "knowledge" (as in, argument of knowledge). In other words: a convincing proof tells the verifier that the prover must know a signature, even if the prover doesn't actually publish that signature. You could also prove that you know 10 signatures, or 100, or more (well, up to the somewhat limited reach of existing proof systems).
Meanwhile, the size of the proof and the cost to verify it grows much more slowly than the number of signatures whose knowledge it establishes---so you can think of this as a kind of cryptographic "compression." This is one of the big ideas behind rollups, which are one possible way of improving the scaling behavior of blockchains like Ethereum.
This is very cool and really impressive! Nice work, both on a conceptual level and on getting everything to actually work :) If anyone is curious, here are a couple pointers to related work on problems similar to this. First, the ideas used here are vaguely related to the way that ZCash works under the hood. The ideas in ZCash come from a sequence of three academic papers: ZeroCoin, PinocchioCoin, and Zerocash: - Zer…
Those papers are some of the densest ones, so maybe as a starter I would recommend Vitalik’s blog posts on ZK[1].
If folks are interested in a complexity theoretic introduction to ZK proofs, incidentally, in the interest of being self recommending, I authored one myself I’d be curious to hear thoughts on :)[2]
[1]: https://vitalik.ca/general/2021/01/26/snarks.html
[2]: https://nibnalin.me/dust-nib/a-succinct-story-of-zero-knowle...
> ECDSA inside ZK-SNARKs is a starting point that unlocks many other ideas! Is there a good way of reasoning about what type of ideas this unlocks?
That's a really good write-up. We've been investigating somewhat similar approaches for a problem space we are in. I wasn't aware of the huge space requirements to use a proving key. That's somewhat limiting, although we do have the advantage that we have a (mobile) wallet we could potentially allow running ZKSnark inside. Are you aware of any work on that side?
I know some teams in the 0xPARC community[1] are interested in it and have been looking into using it, but nothing publicly shareable on that yet.
[1]: https://0xparc.org/
This is very cool and really impressive! Nice work, both on a conceptual level and on getting everything to actually work :) If anyone is curious, here are a couple pointers to related work on problems similar to this. First, the ideas used here are vaguely related to the way that ZCash works under the hood. The ideas in ZCash come from a sequence of three academic papers: ZeroCoin, PinocchioCoin, and Zerocash: - Zer…
Thank you! Those papers are some of the densest ones, so maybe as a starter I would recommend Vitalik’s blog posts on ZK[1]. If folks are interested in a complexity theoretic introduction to ZK proofs, incidentally, in the interest of being self recommending, I authored one myself I’d be curious to hear thoughts on :)[2] [1]: https://vitalik.ca/general/2021/01/26/snarks.html [2]: https://nibnalin.me/dust-nib/a-succin…