We (myself, Adhyyan1252 and yush_g) are undergrad students that hacked out this side project last month during Hack Lodge[1] (the ideas and many of the underlying circuits for which came from the 0xPARC community[2])! We’re extremely excited to share this new primitive.
Besides the technical challenges building this project that folks here would find interesting (fixing the ZK proof compiler, modifying nodeJS V8 params etc.), we think this is a very novel use case for ZK tech, and ECDSA inside ZK-SNARKs is a starting point that unlocks many other ideas! :D
A summarized version of our README, with more thoughts on why you would want to enable this in the first place, is also in this Twitter thread[3]!
[2]: https://0xparc.org
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.
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...
Using a community chest to reward front-runners for submitting claims is clever. Would the ETH reward still need to be at least as large as the transaction cost to incentivize front-runners? Or is there still a cut of the token being taken, in the hopes the token value will make up the difference?
It seems like there would still be a basic gas problem any time the receiving account wants to use the (ERC-20) token, eg to send the token somewhere else via a wallet or some other standard UI?
Very useful exercise, thanks for sharing.
Yeah, it definitely needs to be at least as large as the gas fee (otherwise front runners will just run the transaction locally and notice that it’s not worth rebroadcasting). Our mechanism doesn’t take a cut of the token, mostly because it is hard to put a value to the token as we mention in the post.
> It seems like there would still be a basic gas problem any time the receiving account wants to use the (ERC-20) token, eg to send the token somewhere else via a wallet or some other standard UI?
That’s certainly true, but if, for instance, your primary use case was as a governance token, most governance happens off-chain(on Snapshot Labs[1], for instance), so that wouldn’t require any funds.
The same is seen with asset holdings within known addresses, especially registered ENS domains. Known selling can mess with the future reputation in the community. Of course, it is super easy to build a new reputation from a new identity, a couple weeks in this market, but this is an unnecessary waste of time.
In fact, I see that as the potential #1 usecase: enabling zero-trust voting, with the "drop" simply being a way to instantiate the set of voters at time t to prevent a takeover by freshly created accounts created just for the vote.
A weighting by history (say give 20% more weight to a vote per year the address has existed) and activity (say on HN to give more weight to people who post regularly comments that do not get too many downvotes) could have interesting feature for online communities
I think the capability should be developed and easily applied, I don't think every project needs the ponzinomics to incentivize holding
As long as "crypto" requires absolute perfection, and even experts have difficulty achieving that it isn't reasonable to suggest crypto for everyday use. This always annoys me when people blame victims for not simply "reading the contract" to verify it's correct. People don't have to carefully audit everything a bank does when they open an account, people don't need to be expert auditors to have a reasonable sense of security when depositing their paycheck.
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/
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 numbers of people it's effectively inflating away the value of the coin. Ironic given the initial anti-inflation ethos that drove the early days of cryptocurrency.
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?
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.
Thank you!
Real coin is mined.
